GATE 2024 CS (CS2) – Question 50
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?

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $Y=\sum(0,1,2,3,4,5,6,7)$; (D) $Y=\Pi(8,9,10,11,12,13,14,15)$
Explanation
Minterms of each function:
- $f_1=\Sigma(0,2,3,5,7,8,11,13)$, $f_2=\Sigma(1,3,5,7,11,13,15)$
- $f_3=\Sigma(0,1,4,11)$, $f_4=\Sigma(0,2,6,13)$
$f_1\wedge f_2$ keeps the common minterms: $\{3,5,7,11,13\}$.
$f_3\vee f_4$ is the union: $\{0,1,2,4,6,11,13\}$.
$Y=(f_1\wedge f_2)\oplus(f_3\vee f_4)$ keeps minterms present in exactly one of the two sets, i.e. the symmetric difference. Common minterms 11 and 13 cancel, leaving
$$Y=\Sigma(0,1,2,3,4,5,6,7).$$
The maxterm form is the complement set: $Y=\Pi(8,9,10,11,12,13,14,15)$.
- (A) $\Sigma(0,1,2,11,13)$: no. (B) $\Pi(3,4,5,6,7,8,\dots)$ equals $\Sigma(0,1,2,11,13)$: no.
- (C) $\Sigma(0,\dots,7)$: yes. (D) $\Pi(8,\dots,15)$: yes.
Answer: C, D.