Functional completeness
From Wikipedia, the free encyclopedia
In logic, a set of logical connectives is functionally complete if all other possible connectives can be defined in terms of it.
Usually, in an exposition of classical logic, the following connectives are defined: conjunction (
), disjunction (
), negation (
), implication (
) and possibly bi-implication (
). This constitutes a functionally complete set. However, it is not a minimal functionally complete set, as implication and bi-implication may be defined as:
So 
is also functionally complete. But then, can be defined as:
( can also be defined in terms of in a similar manner.)
This cannot be further simplified, so 
(and 
) are each minimal functionally complete subsets of 
. Moreover, the binary connectives NOR and NAND are functionally complete on their own, and are called sole sufficient operators.
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
