XOR from NAND — universal gates
corewith one shared subexpression
Answer
4 NAND gates realising A′ · B + A · B′
Why this example is worth doing
Four gates rather than the five a naive expansion gives, because (A·B)′ is computed once and used twice. The page uses this as the introduction to logic sharing: two-level minimisation assumes each product term is built independently, so it systematically overestimates the cost of functions with common subexpressions. Multi-level synthesis exists precisely to find them, and this four-gate XOR is the smallest convincing example.
Try your own input in the Universal gates. Rebuild any of the other gates using only NAND, or only NOR, with the gate count.
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 |