GATE 2023 CS – Question 44
A Boolean digital circuit is composed using two 4-input multiplexers (M1 and M2) and one 2-input multiplexer (M3) as shown in the figure. X0–X7 are the inputs of the multiplexers M1 and M2 and could be connected to either 0 or 1. The select lines of the multiplexers are connected to Boolean variables A, B and C as shown (M1 and M2 use A as S1 and C as S0; M3 uses B as select, with M1 on input 0 and M2 on input 1). Which one of the following set of values of (X0, X1, X2, X3, X4, X5, X6, X7) will realise the Boolean function $\bar{A} + \bar{A}C + ABC$?

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) (1, 1, 0, 0, 1, 1, 0, 1)
Explanation
Simplify $f=\overline A+\overline AC+ABC$. The term $\overline AC$ is absorbed by $\overline A$, so $f=\overline A+ABC=\overline A+BC$ (using $x+\overline xy=x+y$).
The multiplexer $M_3$ selects $M_1$ when $B=0$ and $M_2$ when $B=1$. $M_1$ and $M_2$ select among $X_0..X_3$ and $X_4..X_7$ with $A$ (as $S_1$) and $C$ (as $S_0$).
- $B=0$: $f=\overline A$, so for $AC=00,01,10,11$ the output is $1,1,0,0$: $(X_0,X_1,X_2,X_3)=(1,1,0,0)$.
- $B=1$: $f=\overline A+C$, so for $AC=00,01,10,11$ the output is $1,1,0,1$: $(X_4,X_5,X_6,X_7)=(1,1,0,1)$.
Answer: $(1,1,0,0,1,1,0,1)$: option (B).