GATE 2022 EC Q.49: solution and answer

GATE 2022 · ECQ.49 · 2 marks · MSQ

Consider a Boolean gate (D) where the output $Y$ is related to the inputs $A$ and $B$ as, $Y = A + \overline{B}$ , where $+$ denotes logical OR operation. The Boolean inputs '0' and '1' are also available separately. Using instances of only D gates and inputs '0' and '1', ________ (select the correct option(s)).

(A)
NAND logic can be implemented
(B)
OR logic cannot be implemented
(C)
NOR logic can be implemented
(D)
AND logic cannot be implemented

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

(A) and (C). The gate $D (A, B) = A + \overline{B}$ with $A$ tied to '0' gives NOT, and with a NOT on its $B$ input it gives OR. NOT plus OR is functionally complete, so NAND, NOR, OR and AND can all be built, and only the two "can be implemented" statements are true.

Official answer: A, CSource: Official answer key, GATE 2022 EC (IIT Kharagpur)

Write the gate as a function. Here an overline means complement: $D (A, B) = A + \overline{B}$ .
Tie input $A$ to the constant '0': $D (0, B) = 0 + \overline{B} = \overline{B}$ . One D gate therefore works as an inverter (NOT gate).
Feed the inverter's output into input $B$ of a second D gate: $D (A, D (0, B)) = A + \overline{\overline{B}} = A + B$ . So OR can be implemented, and (B) is false.
OR and NOT together form a functionally complete set, so any Boolean function can be built from D gates and the constants. The next three steps give the explicit circuits.
NAND, using De Morgan's law $\overline{A B} = \overline{A} + \overline{B}$ : $D (D (0, A), B) = \overline{A} + \overline{B} = \overline{A B}$ . So (A) is true.
NOR: $D (0, A + B) = 0 + \overline{A + B} = \overline{A + B}$ , where $A + B$ is the OR circuit from step 3. So (C) is true.
AND: $D (0, \overline{A B}) = \overline{\overline{A B}} = A B$ , where $\overline{A B}$ is the NAND circuit from step 5. So AND can be implemented, and (D) is false.
Correct options: (A) and (C).

KEY IDEA

$D (A, B) = A + \overline{B}$ is the implication gate $B \to A$ . On its own it cannot make NOT, because it outputs 1 whenever both inputs are 1. The constant '0' breaks that: $D (0, B) = \overline{B}$ . Once you have NOT, $D (A, \overline{B}) = A + B$ gives OR, and {OR, NOT} is functionally complete, so every gate can be built.

WATCH OUT FOR

Stopping at "D is not a universal gate". Implication with no constants is indeed not complete, and that leads students to tick (B) or (D). The question explicitly supplies '0', which turns D into an inverter and makes the set complete. A second trap is reading (B) and (D) as true statements: both say "cannot", and both are false because OR and AND can be built.

From the GATE 2022 EC paper. Every question of this paper · Download the full paper · All 22 Boolean logic questions, with notes

GATE 2022 EC Q.49: solution and answer

Answer and solution

More Boolean logic questions