In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression.
Each of the singleton sets { NAND } and { NOR } is functionally complete.
However, the set { AND, OR } is incomplete, due to its inability to express NOT.
In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.
[3] From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set.
Modern texts on logic typically take as primitive some subset of the connectives: conjunction (
(Its functional completeness is also proved by the Disjunctive Normal Form Theorem.
With this stronger definition, the smallest functionally complete sets would have 2 elements.
[5][6][7] Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives: Post gave a complete description of the lattice of all clones (sets of operations closed under composition and containing all projections) on the two-element set {T, F}, nowadays called Post's lattice, which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal nontrivial clones.
[8] When a single logical connective or Boolean operator is functionally complete by itself, it is called a Sheffer function[9] or sometimes a sole sufficient operator.
NAND and NOR, which are dual to each other, are the only two binary Sheffer functions.
The following are the minimal functionally complete sets of logical connectives with arity ≤ 2:[11] There are no minimal functionally complete sets of more than three at most binary logical connectives.
[11] In order to keep the lists above readable, operators that ignore one or more inputs have been omitted.
Note that an electronic circuit or a software function can be optimized by reuse, to reduce the number of gates.
For instance, the "A ∧ B" operation, when expressed by ↑ gates, is implemented with the reuse of "A ↑ B", Apart from logical connectives (Boolean operators), functional completeness can be introduced in other domains.
In quantum computing, the Hadamard gate and the T gate are universal, albeit with a slightly more restrictive definition than that of functional completeness.
The more popular "Minimal complete operator sets" are {¬, ∩} and {¬, ∪}.
If the universal set is forbidden, set operators are restricted to being falsity (Ø) preserving, and cannot be equivalent to functionally complete Boolean algebra.