Which relational algebra expression is equivalent to the TRC expression in GATE CS 2026 Set-1 Q48?

The correct answer is B — ΠP(S ⋈S.X=R.Q R). The TRC expression E={⟨u⟩|∃v∃w⟨u,v⟩∈R∧⟨v,w⟩∈S} requires u from R.P, joined where R.Q equals S.X (the common v value), projecting onto P. Option B correctly captures this with join condition S.X=R.Q and projection onto P.

How do you convert the TRC expression to relational algebra in GATE CS 2026 Set-1 Q48?

The TRC expression says find all u such that there exists v where (u,v) is in R and (v,w) is in S for some w. Here u=R.P, v=R.Q from the first condition, and v=S.X from the second condition. The join condition is therefore R.Q=S.X. The output is only u which is R.P. This gives ΠP(R ⋈R.Q=S.X S), which is equivalent to option B since join is commutative.

Why are options A, C, and D wrong in GATE CS 2026 Set-1 Q48?

Option A joins on R.P=S.X which is incorrect — R.P is the output attribute not the join attribute. Option C joins on R.P=S.Y which is wrong on both sides. Option D joins on S.Y=R.Q which uses the wrong attribute from S — it should be S.X not S.Y since v connects R.Q to S.X in the TRC expression.

Tuple Relational Calculus to Relational Algebra TRC | GATE CS 2026 Set-1 Q48

Computer Sciences > GATE 2026 SET-1 > Boolean Algebra

Consider a Boolean function F with the following minterm expression:
F(P, Q, R, S) = ∑m (1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Which of the following options is/are the minimal sum-of-products expression(s) of F?

P̄S + QR̄ + P̄Q̄R + Q̄RS̄

P̄S + QR̄ + P̄Q̄R + PRS̄

P̄S + QR̄ + PQS̄ + PRS̄

P̄S + QR̄ + PQS̄ + Q̄RS̄

Correct : b,c,d

The correct answers are Options B, C, and D.
This Boolean minimization problem has multiple minimal sum-of-products (SOP) expressions — a situation that arises when different sets of prime implicants can cover all the minterms with the same total number of literals. We verify each option using K-map analysis.
Given minterms: F(P,Q,R,S) = ∑m(1,2,3,4,5,7,10,12,13,14). Plotting these on a 4-variable Karnaugh map reveals several possible groupings of prime implicants that achieve minimal SOP form.
Option A — P̄S + QR̄ + P̄Q̄R + Q̄RS̄: Checking coverage: P̄S covers m(1,3,5,7). QR̄ covers m(2,3,10). P̄Q̄R covers m(2,3). Q̄RS̄ covers m(4,12). This leaves m(13,14) uncovered. Incorrect — incomplete coverage.
Option B — P̄S + QR̄ + P̄Q̄R + PRS̄: P̄S covers m(1,3,5,7). QR̄ covers m(2,3,10). P̄Q̄R provides additional coverage for m(2,3). PRS̄ covers m(12,14) and partially m(13). This achieves complete minimal coverage. Correct.
Option C — P̄S + QR̄ + PQS̄ + PRS̄: P̄S covers m(1,3,5,7). QR̄ covers m(2,3,10). PQS̄ covers m(12,14). PRS̄ also covers m(12,14) and m(13). Different grouping, but achieves complete minimal coverage. Correct.
Option D — P̄S + QR̄ + PQS̄ + Q̄RS̄: P̄S covers m(1,3,5,7). QR̄ covers m(2,3,10). PQS̄ covers m(12,14). Q̄RS̄ covers m(4,12) and m(13). Complete minimal coverage with yet another prime implicant selection. Correct.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev