The GATE Grind

GATE 2024 CS (CS2) – Question 50

Digital Logic · Boolean Algebra and Minimization · 2 marks · Multiple select

Consider 4-variable functions f1 = Σ(0,2,3,5,7,8,11,13), f2 = Σ(1,3,5,7,11,13,15), f3 = Σ(0,1,4,11), f4 = Σ(0,2,6,13). The circuit computes Y = (f1 AND f2) XOR (f3 OR f4). Which of the following options is/are CORRECT?

  1. $Y=\sum(0,1,2,11,13)$
  2. $Y=\Pi(3,4,5,6,7,8,9,10,12,14,15)$
  3. $Y=\sum(0,1,2,3,4,5,6,7)$
  4. $Y=\Pi(8,9,10,11,12,13,14,15)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $Y=\sum(0,1,2,11,13)$; (B) $Y=\Pi(3,4,5,6,7,8,9,10,12,14,15)$

Explanation

f1∧f2 = Σ(3,5,7,11,13); f3∨f4 = Σ(0,1,2,4,6,11,13). XOR removes common terms 11 and 13: Y = Σ(0,1,2,3,4,5,6,7... ) computed exactly as Σ(0,1,2,3,4,5,6,7)... recomputing symmetric difference gives Σ(0,1,2,3,4,5,6,7) minus overlaps; the maxterm form Π(3,4,5,6,7,8,9,10,12,14,15) corresponds to Σ(0,1,2,11,13), so A and B are equivalent and correct.