What is the minimum number of 2-input NAND gates required to implement the…

Concept: NAND is a universal gate — any Boolean function can be realized using only NAND gates. Two De Morgan-based rules make this systematic: a two-variable AND term's complement, NOT(AB), comes directly out of a single NAND(A,B); and a single literal's complement, NOT(C), comes from a self-NAND — both inputs of one NAND gate tied to C. A sum A + B is then rebuilt by NAND-ing NOT(A) with NOT(B), since NAND(NOT(A), NOT(B)) = NOT(NOT(A)·NOT(B)) = A + B.

Application: For F = WX + Y, set A = WX and B = Y.

1. Produce NOT(WX) with one NAND gate: NAND(W, X) = NOT(WX).

2. Produce NOT(Y) with one NAND gate used as an inverter: NAND(Y, Y) = NOT(Y).

3. Combine the two complemented signals with a final NAND gate: NAND(NOT(WX), NOT(Y)) = NOT(NOT(WX)·NOT(Y)) = WX + Y = F, by De Morgan's theorem.

Circuit layout (gate-by-gate signal flow):

Cross-check: Take W = X = 0, Y = 1, so F should equal 1. NAND(0,0) = 1, giving NOT(WX) = 1. NAND(1,1) = 0, giving NOT(Y) = 0. The final gate NAND(1,0) = 1, matching F = WX + Y = 0 + 1 = 1. Fewer than three gates cannot work: with only two gates, the raw (uninverted) literal Y would have to feed the final NAND directly, and since a NAND always inverts the product of its inputs, that changes which function comes out — the single literal genuinely needs its own inverting gate before the final combination.

Total = 3 two-input NAND gates.