GATE 2018 EE Q.14: solution and answer

Official answer: DSource: Official answer key, GATE 2018 EE (IIT Guwahati)

1. All three gates are two-input NAND gates: each is an AND body with a bubble on its output. Complement is written with an overline, $\overline{}$.

2. First-level outputs: the upper gate gives $P=\overline{AB}$ and the lower gate gives $Q=\overline{CD}$.

3. The output gate is a NAND of $P$ and $Q$: $$Y=\overline{P\cdot Q}=\overline{\overline{AB}\cdot \overline{CD}}$$

4. By De Morgan's theorem, $\overline{X\cdot Z}=\overline{X}+\overline{Z}$, with $X=\overline{AB}$ and $Z=\overline{CD}$: $$Y=\overline{\overline{AB}}+\overline{\overline{CD}}$$

5. Double complementation, $\overline{\overline{X}}=X$, gives $$Y=AB+CD$$ This is the standard NAND-NAND form of a sum of products.

6. Check with $A=B=1$, $C=D=0$: $P=0$ and $Q=1$, so $Y=\overline{0\cdot 1}=1$, and $AB+CD=1$ agrees. Option (A) gives $ABCD=0$ and option (B) gives $(1+1)(0+0)=0$, so both are ruled out.

7. Check with $A=1$, $B=C=D=0$: $P=1$ and $Q=1$, so $Y=\overline{1\cdot 1}=0$, and $AB+CD=0$ agrees. Option (C) gives $A+B+C+D=1$, so it is ruled out. Option (D) is correct.