XOR from four NAND gates — XOR gate
exam standardthe standard universal construction
Answer
4 NAND gates realising A′ · B + A · B′
Why this example is worth doing
The classic four-NAND XOR, and the reason a naive count would say five: the intermediate (A·B)′ is computed once and fanned out to two gates rather than being duplicated. Sharing a subexpression is the first optimisation in any real synthesis flow, and this is the smallest circuit where it visibly saves a gate. The page draws the fan-out explicitly and links to the read-back example on the circuit-to-expression page.
Try your own input in the XOR gate. Truth table, symbol and algebraic form for A ⊕ B, the difference detector.
How the answer is reached
Gate list
| Node | Gate | Inputs |
|---|---|---|
| g1 | nand | A, B |
| g2 | nand | A, g1 |
| g3 | nand | g1, B |
| g4 | nand | g2, g3 |
NAND-only realisation
A ↑ (A ↑ B) ↑ (A ↑ B ↑ B)A′ · B + A · B′— 4 NAND gates, verified by reading the network back out.
Truth table
| # | A | B | A ↑ (A ↑ B) ↑ (A ↑ B ↑ B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 1 |
| 3 | 1 | 1 | 0 |