GATE 2025 IN Q.29: solution and answer

Official answer: BSource: Official answer key, GATE 2025 IN (IIT Roorkee)

1. Complement is written with $\overline{}$ throughout. Factor out the common literal first: $$X=\overline{A}\overline{B}+\overline{A}\overline{C}=\overline{A}(\overline{B}+\overline{C})$$

2. Apply De Morgan's theorem to the product $\overline{A}\cdot (\overline{B}+\overline{C})$: $$\overline{X}=\overline{\overline{A}(\overline{B}+\overline{C})}=\overline{\overline{A}}+\overline{(\overline{B}+\overline{C})}=A+\overline{(\overline{B}+\overline{C})}$$

3. Apply De Morgan's theorem again, to the sum: $\overline{\overline{B}+\overline{C}}=\overline{\overline{B}}\overline{\overline{C}}=BC$. Therefore $$\overline{X}=A+BC$$

4. Check with minterms (taking $A$ as the most significant bit). $X=1$ only when $A=0$ and $B$, $C$ are not both 1, so $X=\sum m(0,1,2)$. Hence $\overline{X}=\sum m(3,4,5,6,7)$: minterms 4 to 7 are exactly $A$, and minterm 3 is $\overline{A}BC$. So $\overline{X}=A+\overline{A}BC=A+BC$ (absorption: $A+\overline{A}Y=A+Y$).

5. Rule out the other options with a single input each. At $A=B=C=0$ we have $\overline{X}=0$, but (A) $\overline{A}+\overline{B}+\overline{C}=1$ and (C) $\overline{A}+\overline{B}+C=1$, so both are wrong. At $A=1,B=C=0$ we have $\overline{X}=1$, but (D) $B+AC=0$, so (D) is wrong. The answer is option (B), $A+BC$.