GATE 2022 PH – Question 59

Electronics · basics of digital logic circuits, combinational and sequential circuits, flip- flops, timers, counters, registers, A/D and D/A conversion. · 2 marks · Numerical answer

What is the minimum number of two-input NAND gates for $Y=[A\bar B(C+BD)+\bar A\bar B]C$?

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 3

Explanation

Simplify the Boolean expression
$$Y=\left[A\bar B(C+BD)+\bar A\bar B\right]C .$$

**Step 1:** distribute inside the bracket: $A\bar B(C+BD)=A\bar BC+A\bar BBD$. Since $\bar BB=0$, the second term vanishes:
$$A\bar B(C+BD)=A\bar BC .$$

**Step 2:** the bracket becomes
$$A\bar BC+\bar A\bar B=\bar B\,(AC+\bar A)=\bar B\,(C+\bar A),$$
using $AC+\bar A=C+\bar A$.

**Step 3:** multiply by $C$:
$$Y=\bar B\,(C+\bar A)\,C=\bar B\,C .$$

**NAND implementation of $\bar BC$** with two-input NAND gates:
1. One NAND with both inputs tied to $B$ gives $\bar B$.
2. A second NAND with inputs $\bar B$ and $C$ gives $\overline{\bar BC}$.
3. A third NAND with both inputs tied to that output inverts it, giving $\bar BC$.

The minimum number is **3** gates.