Complete set of Boolean operators
In Boolean algebra, a complete set of Boolean operators is a set of Boolean operators which permits the realization of any possible truth table. Synonyms of this term include complete set of Boolean functions and complete system of Boolean algebra. From the point of view of propositional logic the same concept is known as functional completeness.
Example truth table (Xor):
a | b | Result |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
A familiar complete set consists of the operators AND, OR and NOT. In it a XOR b can be expressed as (a OR b) AND NOT (a AND b).
However, other more exotic complete system of Boolean algebra exist such as NAND or NOR, each of which forms a complete set on its own. In some cases the expressions reducing an operation such as XOR to a given complete set such as NAND can be fairly complex.
See also
References
- Schneeweiss, Winfrid G. (1989), Boolean functions, Springer, ISBN 9780387188928