A set of gate types is functionally complete when you can build any Boolean function using only gates from that set. The idea tells you which building blocks are enough.
The starting point is {AND, OR, NOT}. Every function has a sum of products form, which uses only those three, so that set is complete.
From there, a set is complete if it can make NOT plus either AND or OR. De Morgan's law supplies the missing one, for example = . So:
- {AND, NOT} and {OR, NOT} are complete.
- {NAND} alone and {NOR} alone are complete. A single gate type that does this is a universal gate.
- {AND, XOR} is complete if a constant 1 is available, since = .
Sets that are not complete, and why:
- {AND, OR}: raising an input from 0 to 1 can never make their output fall, so they can't build NOT.
- {XOR, XNOR}, even with constants: they only ever build parity-style functions, never AND.
- {NOT} alone: it has only one input, so it can't combine signals.
When checking a claim, always ask whether constants 0 and 1 are allowed. The answer can change.