GATE 2022 IN Q.23: solution and answer

GATE 2022 · INQ.23 · 1 mark · MSQ

The output F of the digital circuit shown can be written in the form(s) ________

GATE 2022 IN question 23: Two 2×1 multiplexers connected in cascade. — Figure from the GATE 2022 IN paper. It is part of the question.

(A)
$\overline{A . B}$
(B)
$\overset{ˉ}{A} + \overset{ˉ}{B}$
(C)
$\overline{A + B}$
(D)
$\overset{ˉ}{A} . \overset{ˉ}{B}$

Answer and solution

ANSWER

F = $\overline{A} + \overline{B} = \overline{A \cdot B}$ (a NAND of A and B), so options (A) and (B) are correct.

Official answer: A, BSource: Official answer key, GATE 2022 IN (IIT Kharagpur)

2×1 MUX rule: $Y = \overline{S} I_{0} + S I_{1}$ , where denotes complement (the select line picks $I_{0}$ when $S = 0$ and $I_{1}$ when $S = 1$ ).
First MUX ( $S_{0} = B$ , $I_{0} = 1$ , $I_{1} = 0$ ): $Y_{1} = \overline{B} \cdot 1 + B \cdot 0 = \overline{B}$ .
Second MUX ( $S_{0} = A$ , $I_{0} = 1$ , $I_{1} = Y_{1} = \overline{B}$ ): $F = \overline{A} \cdot 1 + A \overline{B} = \overline{A} + A \overline{B}$ .
Absorption theorem $X + \overline{X} Y = X + Y$ , with $X = \overline{A}$ (so $\overline{X} = A$ ) and $Y = \overline{B}$ : $F = \overline{A} + \overline{B}$ .
De Morgan's theorem: $\overline{A} + \overline{B} = \overline{A \cdot B}$ , so F is the NAND of A and B. Truth-table check: $A = 0 \Rightarrow F = I_{0} = 1$ ; $A = 1, B = 0 \Rightarrow F = Y_{1} = 1$ ; $A = 1, B = 1 \Rightarrow F = Y_{1} = 0$ . Only $A = B = 1$ gives 0, which is NAND.
Checking the options: (A) $\overline{A . B}$ and (B) $\overset{ˉ}{A} + \overset{ˉ}{B}$ are both F. (C) $\overline{A + B} = \overset{ˉ}{A} \overset{ˉ}{B}$ and (D) $\overset{ˉ}{A} . \overset{ˉ}{B}$ are both NOR, which is wrong: at $A = 1, B = 0$ , F is $1$ but NOR gives $0$ . Correct options: A and B.

KEY IDEA

Work each 2×1 MUX with $Y = \overline{S} I_{0} + S I_{1}$ . The first MUX, with inputs 1 and 0 and select B, is just an inverter: $Y_{1} = \overline{B}$ . The second gives $F = \overline{A} + A \overline{B} = \overline{A} + \overline{B}$ , which is NAND. This is an MSQ, so both equivalent forms of NAND (the De Morgan pair) must be marked.

WATCH OUT FOR

Marking only one of (A) and (B) and forgetting that De Morgan makes them the same function, or mixing up $\overline{A \cdot B}$ (NAND) with $\overline{A} \cdot \overline{B}$ (NOR) and picking (C) or (D). Another slip is wiring the first MUX output into $I_{0}$ of the second MUX instead of $I_{1}$ , which gives a different function.

From the GATE 2022 IN paper. Every question of this paper · Download the full paper · All 12 Combinational questions, with notes

GATE 2022 IN Q.23: solution and answer

Answer and solution

More Combinational questions