Implementation of XOR Gate from NAND Gate
NAND is functionally complete, so a XOR gate can be built from it alone. Here is the construction, and why it works.
The NAND gate is functionally complete, which means every other gate can be built from it alone, and this page builds an XOR gate from nothing else. Along the way you will see why the construction works and how many gates it costs.
Why XOR can be built from NAND
XOR is the classic four-NAND puzzle. The trick is that the middle NAND output feeds back into both branches, so you never need a separate inverter.
Functional completeness is the reason chip designers care: a fab only has to get one gate right, and every circuit can be built from copies of it. NAND and NOR are both functionally complete; no other two-input gate is, on its own.
Step-by-step construction
Step 1
N = NAND(A, B).
Step 2
NAND(A, N).
Step 3
NAND(B, N).
Step 4
The boolean expression
A XOR B = NAND(NAND(A, N), NAND(B, N)) where N = NAND(A, B)
Truth table
| A | B | XOR |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Build the circuit, then check every row. If all four match, the construction is correct: a truth table is a complete specification for a combinational circuit, so agreeing on every row means the two circuits are the same function.
Gate count
This construction uses 4 NAND gates. Gate count matters in real hardware because every gate costs area, power and a small propagation delay, which is why a circuit built entirely from one gate type is usually larger than the same logic built from mixed gates.
Build it yourself
Reading the construction is not the same as getting it working. Open the editor, drop in the gates, and watch the output change as you toggle the inputs, since that is the only way to be sure the circuit does what the truth table claims.
Related pages
Every conversion in this track follows the same two moves: get the un-inverted version, then cancel or add an inversion. Once you have seen XOR built this way, the rest are variations on the same idea. The wider digital logic track covers where these gates end up, in adders, latches, and memory.