Logical connectives | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||
Related concepts | ||||||||||||||||||||||
Applications | ||||||||||||||||||||||
![]() | ||||||||||||||||||||||
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.[1][2] A well-known complete set of connectives is { AND, NOT }. 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.
A gate (or set of gates) that is functionally complete can also be called a universal gate (or a universal set of gates).
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. In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates.