GATE 2018 IN Q.46: solution and answer

Official answer: ASource: Official answer key, GATE 2018 IN (IIT Guwahati)

1. Complement is written with $\overline{}$ throughout. All four gates are 2-input NAND gates. Label them G1 (middle), G2 (top), G3 (bottom) and G4 (output).

2. G1 takes X and Y: $P=\overline{XY}$.

3. G2 takes X and P: $A=\overline{X\overline{XY}}$. G3 takes P and Y: $B=\overline{Y\overline{XY}}$.

4. G4 NANDs A and B. Write $A=\overline{u}$ with $u=X\overline{XY}$ and $B=\overline{v}$ with $v=Y\overline{XY}$. By De Morgan, $\overline{\overline{u}\cdot \overline{v}}=u+v$, so $$F=\overline{AB}=X\overline{XY}+Y\overline{XY}=(X+Y)\overline{XY}$$

5. Apply De Morgan again, $\overline{XY}=\overline{X}+\overline{Y}$: $$F=(X+Y)(\overline{X}+\overline{Y})=X\overline{X}+X\overline{Y}+\overline{X}Y+Y\overline{Y}=\overline{X}Y+X\overline{Y}$$ since $X\overline{X}=Y\overline{Y}=0$.

6. Check with a truth table: $(X,Y)=(0,0)$ gives $P=1$, $A=1$, $B=1$, $F=0$. $(0,1)$ gives $P=1$, $A=1$, $B=0$, $F=1$. $(1,0)$ gives $P=1$, $A=0$, $B=1$, $F=1$. $(1,1)$ gives $P=0$, $A=1$, $B=1$, $F=0$. The output is 1 exactly when the inputs differ, so the circuit is an XOR gate, $F=\overline{X}Y+X\overline{Y}$, which is option (A).