Sufficiently connected
From Wikipedia, the free encyclopedia
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.
[edit] See also
[edit] References
- Kelly, John (1996). The Essence of Logic. Prentice Hall. ISBN 0-13-396375-6.
