functional completeness of NAND

Here is a surprising fact: you do not need a kit of different gates to build a computer. The single NAND gate is enough. Give a factory nothing but NAND gates and they can wire up AND, OR, NOT, XOR — every logic function that exists. This property is called functional completeness, and NAND (along with NOR) is a universal gate. It is like discovering that one shape of Lego brick can, in enough copies, assemble any model at all.

The proof is just three constructions. NAND(A,B) means not(A AND B). First, NOT: feed the same signal to both inputs — NAND(A,A) = not(A AND A) = not A. Now that you have NOT, you can make AND: NAND already gives not-AND, so put a NOT after it, AND(A,B) = NOT(NAND(A,B)). And OR comes from De Morgan: A OR B = not((not A) AND (not B)) = NAND(NOT A, NOT B), and each NOT is itself a NAND. So from NAND alone you reconstruct the whole basic set, and from those you can build anything a truth table can specify.

Why it matters in practice: in CMOS, NAND and NOR are actually the natural, cheapest gates to fabricate — a plain AND or OR is built as a NAND or NOR followed by an inverter, so it costs more, not less. Chip designers therefore often think in NAND/NOR. Honest caveat: 'you only need NAND' is a statement about possibility, not efficiency. Real designs use a rich library of gates of many sizes because building everything from one gate type, while always possible, would be needlessly slow and large.