Jump to content

Complete set of Boolean operators

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ruud Koot (talk | contribs) at 00:43, 9 December 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In propositional logic, a set of Boolean operators is called sufficient if it permits the realisation of any possible truth table.

Example truth table (Xor):

a b Result
0 0 0
0 1 1
1 0 1
1 1 0

Using a complete Boolean algebra which does not include XOR (such as the well-known AND OR NOT set), this function can be realised as follows:

(a or b) and not (a and b).

However, other complete Boolean algebras are possible, such as NAND or NOR (either gate can form a complete Boolean algebra by itself - the proof is detailed on their pages).

Note that just because a set of gates forms a complete Boolean algebra does not mean that the resulting expressions will be simple. To gain an XOR function using only NAND gates, for example, is a fairly complex expression - the important thing is that it exists.

See also

References

  • . ISBN 0133963756. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)