GATE CS 2024 Set 1 Q54 — Combinational Circuits

Let the outputs of the multiplexers $M_1$ and $M_2$ be $Y_1$ and $Y_2$, respectively. For a standard $2$-to-$1$ multiplexer with select line $S$ and inputs $I_0$ (at select $0$) and $I_1$ (at select $1$), the output is given by $Y = \bar{S}I_0 + SI_1$.

Given the input values:

• $X_1 = 1$ and $X_2 = 1 \implies Y_1 = \bar{A}(1) + A(1) = 1$ (independent of $A$)
• $X_3 = 0$ and $X_4 = 0 \implies Y_2 = \bar{B}(0) + B(0) = 0$ (independent of $B$)

The multiplexer $M_3$ takes $Y_1$ and $Y_2$ as its inputs, with $C$ as the select line. Its output $Y$ is:

Substituting $Y_1 = 1$ and $Y_2 = 0$ into the equation:

For the final output to be $Y = 1$, we must have:

Since the output $Y$ depends only on $C$, the select lines $A$ and $B$ can take any binary value. Thus, the valid combinations of $(A, B, C)$ are:

Therefore, there are exactly 4 combinations of $A, B, C$ that yield $Y = 1$.