Jump to content

Complete set of Boolean operators

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Hans Adler (talk | contribs) at 10:51, 16 May 2009 (moved Sufficiently connected to Complete set of Boolean operators: Original name was one author's ad hoc terminology; move to standard name). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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