Functional completeness

A set of logical connectives or Boolean operations is functionally complete (or expressively adequate) when any Boolean function, regardless of its number of inputs or complexity, can be constructed using only operations from that set. The standard trio of AND, OR, and NOT is complete, but so are the smaller sets {AND, NOT} and {OR, NOT}, and even the singletons {NAND} and {NOR} — each sufficient, alone, to build every other logical operation. This property is not merely an algebraic curiosity: it is the reason modern digital circuits can be fabricated from a single type of transistor configuration, and it reveals that the apparent diversity of logical operations collapses to a single generative principle. The study of minimal complete sets connects directly to universal computation and the Sheffer stroke, which showed in 1913 that a single binary operation suffices for all of propositional logic.