What 'functionally complete' means
A set of gate types is functionally complete if any Boolean function at all can be built using only gates from that set. AND, OR, and NOT together are complete, but none of them is complete alone — you always need at least two of the three. NAND is the surprising exception: a single NAND gate type, used repeatedly, is enough to build NOT, AND, OR, and every other Boolean function. The same is true of NOR on its own.
Building NOT, AND, and OR from NAND alone
Three constructions cover everything:
- NOT: feed the same signal to both inputs of a NAND gate. NAND(A,A) = ¬A.
- AND: negate a NAND with a second NAND wired as NOT. AND(A,B) = ¬(NAND(A,B)).
- OR: apply De Morgan's laws — negate each input first (using the NOT trick above), then NAND the results. OR(A,B) = NAND(¬A,¬B).
Why fabrication prefers one gate type
In CMOS, a NAND gate is built directly from four transistors; an AND gate is the same four transistors plus two more to invert the output again. NAND and NOR are therefore the physically simplest gates to fabricate, and standard-cell libraries are built around them — an OR gate in a real chip is usually a NOR followed by an inverter internally, not a separate primitive. Reducing an arbitrary design down to one gate type also simplifies manufacturing test patterns, since every cell on the die behaves identically.
Try it yourself
Rebuild the half adder using nothing but NAND gates — no AND, OR, or XOR primitives — in the circuit editor, then compare its truth table against the original two-gate version to confirm the two are logically identical.