GATE 2018 EC Q.31: solution and answer

Official answer: CSource: Official answer key, GATE 2018 EC (IIT Guwahati)

1. Complement is written with $\overline{}$ throughout. A $4\times 1$ MUX with select lines $S_1{S}_0$ gives $Y=\overline{S_1}\overline{S_0}{I}_0+\overline{S_1}{S}_0{I}_1+S_1\overline{S_0}{I}_2+S_1{S}_0{I}_3$.

2. First MUX, with $S_1=U$ and $S_0=V$: the inputs are $I_0=0$ (ground), $I_1=1$ ($V_{CC}$), $I_2=1$ ($V_{CC}$) and $I_3=0$ (ground).

3. Its output is therefore $Y_1=\overline{U}V\cdot 1+U\overline{V}\cdot 1=\overline{U}V+U\overline{V}=U\oplus V$. It is 1 only for $UV=01$ and $UV=10$.

4. Second MUX, with $S_1=W$ and $S_0=X$: the inputs are $I_0=I_1=Y_1$ and $I_2=I_3=0$ (ground).

5. $$F=\overline{W}\overline{X}{Y}_1+\overline{W}X{Y}_1+W\overline{X}\cdot 0+WX\cdot 0=\overline{W}{Y}_1(\overline{X}+X)=\overline{W}{Y}_1$$

6. So $F=(U\overline{V}+\overline{U}V)\overline{W}$. $X$ drops out because it only chooses between two identical inputs, $I_0$ and $I_1$.

7. This matches option (C). Option (D) is the same function but is not minimized, since $\overline{W}\overline{X}+\overline{W}X=\overline{W}$. Options (A) and (B) use $UV+\overline{U}\overline{V}$, which is XNOR, but the first MUX produces XOR.