GATE 2024 IN Q.16: solution and answer

Official answer: ASource: Official answer key, GATE 2024 IN (IISc Bengaluru)

1. Notation: $\overline{X}$ is the complement of $X$, and a dot (or two letters side by side) means AND. Start with the first bracket. The redundancy theorem $X+\overline{X}Y=X+Y$ with $X=A$, $Y=B$ gives $$A+\overline{A}.B=A+B$$

2. Expand the second term with the distributive law: $$\overline{A}.(A+\overline{B}).C=\overline{A}AC+\overline{A}\overline{B}C$$

3. Complement law: $\overline{A}A=0$. So the second term is just $\overline{A}\overline{B}C$.

4. Put the two parts together: $$F=A+B+\overline{A}\overline{B}C$$

5. Apply the redundancy theorem again, with $X=A$ and $Y=\overline{B}C$: $A+\overline{A}(\overline{B}C)=A+\overline{B}C$. So $F=A+B+\overline{B}C$.

6. Apply it once more, with $X=B$ and $Y=C$: $B+\overline{B}C=B+C$. Therefore $$F=A+B+C$$

7. Check: $F=A+B+\overline{A}\overline{B}C$ is 0 only when $A=0$, $B=0$ and $\overline{A}\overline{B}C=0$. With $A=B=0$ the last term is just $C$, so $C=0$ as well. $F$ is therefore 0 only at $ABC=000$, which is exactly $A+B+C$. The other options fail at a single input. At $ABC=001$ we have $F=1$, but (B) $A.B.C=0$. At $ABC=100$ we have $F=1$, but (C) $B+\overline{A}.C=0$ and (D) $\overline{A}+B.C=0$. The answer is option (A).