Difficulty: Medium · Puzzle 3 of 6 · Topic: Digital Logic Puzzles
Implement XOR using only 2-input NAND gates. What is the minimum number of NAND gates and one valid construction?
n1 = ~(A & B);
n2 = ~(A & n1);
n3 = ~(B & n1);
Y = ~(n2 & n3); // XORUse the canonical 4-NAND XOR network.
1) Create n1 = NAND(A,B) = ~(A&B).
2) Create n2 = NAND(A,n1) and n3 = NAND(B,n1).
3) Final output Y = NAND(n2,n3).
4) Substituting shows Y = A^B.
5) This uses 4 NAND gates, which is the known minimum for XOR with 2-input NAND-only logic.Answer: Minimum is 4 NAND gates.
Checked by running a model of the rule in a Python model. A computational check: exhaustive search over every 2-input NAND network shows XOR needs 4 gates (3 are impossible) and XNOR needs 5.
Claiming 3 NANDs are enough because the shared n1 'looks' like it replaces two gates; with 3 two-input NANDs XOR's truth table cannot be matched. The shared n1 term is what makes 4 possible.
What is the minimum NAND count for XNOR? Model answer: 5 NAND gates. Take the 4-NAND XOR and add a fifth NAND with both inputs tied together as an inverter on the output.
I build the shared term first: n1 is the NAND of A and B. Then n2 is the NAND of A and n1, n3 is the NAND of B and n1, and the output is the NAND of n2 and n3, which works out to A XOR B. That is four NAND gates, which is the known minimum for XOR with two-input NANDs. The trap is claiming three are enough; the shared n1 term is what makes four possible, but you cannot do it with three.