Functional Completeness
A set of logic operations is functionally complete if every Boolean function can be expressed using only that set.
The idea
A collection of operations is functionally complete when any Boolean function of any number of variables can be written using only those operations. Completeness is what guarantees a gate library can implement anything.
Complete sets
- AND, OR, NOT together are complete; this is the classic baseline.
- AND and NOT alone are complete, since OR follows by De Morgan.
- OR and NOT alone are complete, by the dual argument.
- NAND alone is complete.
- NOR alone is complete.
Incomplete sets
Some sets cannot express everything. AND and OR without NOT are incomplete, because they can never produce an inverting function; they are monotone, so raising an input can never lower the output. XOR and AND together also fall short of full completeness on their own without a constant. The missing ingredient is almost always the ability to invert.
How to prove completeness
The standard method is constructive: show the candidate set can build NOT, AND, and OR. Since those three are known to be complete, reproducing them proves the new set is complete too. This is exactly how NAND and NOR are shown to be universal.
Post's theorem
A deeper result, Post's characterization, gives the exact condition: a set is complete unless every operation in it shares one of a small number of preserving properties, such as preserving 0, preserving 1, being monotone, being self-dual, or being affine. Escaping all of those classes guarantees completeness.
Why it matters
Functional completeness is the theoretical license for building all of digital logic from a tiny primitive set, which simplifies fabrication and lets a single well-optimized gate serve as the foundation of an entire technology.