Σm(0,1,2,5,6,7) as a NAND-only network — universal gates
exam standardthe mechanical SOP-to-NAND conversion
Answer
7 NAND gates realising A′ · B′ + B · C′ + A · C
Why this example is worth doing
The end-to-end conversion on a real function: minimise to SOP, then replace every AND and the final OR with a NAND. It works because the double bubbles introduced between the two levels cancel — which is the whole trick, and why any two-level SOP maps to NAND-NAND with no change in gate count. The page walks it on the cyclic example from the K-map pages so the input is already familiar.
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 |
|---|---|---|
| na | nand | A, A |
| nb | nand | B, B |
| nc | nand | C, C |
| t1 | nand | na, nb |
| t2 | nand | A, C |
| t3 | nand | B, nc |
| out | nand | t1, t2, t3 |
NAND-only realisation
((A ↑ A ↑ (B ↑ B)) · (A ↑ C) · (B ↑ (C ↑ C)))′A′ · B′ + B · C′ + A · C— 7 NAND gates, verified by reading the network back out.
Truth table
| # | A | B | C | ((A ↑ A ↑ (B ↑ B)) · (A ↑ C) · (B ↑ (C ↑ C)))′ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |