GATE CS 2024 Set 1 — Question 64

To find the number of combinations of $A, B, C$ that result in $Y=1$, we analyze the logic of the multiplexers given the specific inputs: The output $Q_1$ is given by the expression for a 2-to-1 MUX: $Q_1 = \bar{A}X_1 + AX_2$.
Given $X_1 = 1$ and $X_2 = 1$:
$Q_1 = \bar{A}(1) + A(1) = \bar{A} + A = 1$.
Thus, $Q_1$ is always $1$, regardless of the value of the select line $A$. The output $Q_2$ is given by: $Q_2 = \bar{B}X_3 + BX_4$.
Given $X_3 = 0$ and $X_4 = 0$:
$Q_2 = \bar{B}(0) + B(0) = 0$.
Thus, $Q_2$ is always $0$, regardless of the value of the select line $B$. The final output $Y$ is given by: $Y = \bar{C}Q_1 + CQ_2$.
Substituting the values of $Q_1$ and $Q_2$ obtained above:
$Y = \bar{C}(1) + C(0) = \bar{C}$. We require the output $Y = 1$. From the expression $Y = \bar{C}$, this implies $\bar{C} = 1$, which means $C = 0$.

• The select line $A$ can be either $0$ or $1$ ($2$ possible values).
• The select line $B$ can be either $0$ or $1$ ($2$ possible values).
• The select line $C$ must be $0$ ($1$ possible value).

The total number of combinations of $(A, B, C)$ is the product of the number of choices for each variable:
Total combinations = $2 \times 2 \times 1 = 4$. The specific combinations are $(0, 0, 0), (0, 1, 0), (1, 0, 0),$ and $(1, 1, 0)$.