Complete set of Boolean operators
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)