Sufficiently connected
Encyclopedia : S : SU : SUF : Sufficiently connected
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
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.