How many operators do you need to implement Boolean logic?
The obvious answer is three - AND, OR and NOT - but this isn't correct.
The correct answer is that you only need one operation. Clearly it can't be just any operation. For example, it is impossible to make an OR from combinations of AND - try it.
However if you pick an operation that includes an element of the NOT operator then you can make anything you like using it.
For example the AND operator isn't universal but the NAND, i.e. Not AND is. The truth table for NAND is just NOT(P AND Q):
P
Q
P NAND Q
F
F
T
F
T
T
T
F
T
T
T
F
To make a NOT all you have to do is write:
P NAND P= NOT(P)
P
P
P NAND P
F
F
T
T
T
F
Once you have a NOT you can make an AND:
NOT(P NAND Q)= P AND Q
The only operation that remains is to make an OR out of NAND and NOT and the solution to this is one of De Morgan’s laws:
NOT(P AND Q)=NOT(P) OR NOT(Q)
A little work soon gives:
NOT(P) NAND NOT(Q)=P OR Q
So with a NAND operator you can build a NOT, an AND and an OR. This means that a single operator does everything that the usual three can do.
In practical terms this means that every circuit in a computer could be built using just a NAND gate. In practice electronic engineers like to use a variety of gates because it is simpler.
NAND isn't the only universal operator. You might guess that NOR, i.e. NOT(P OR Q) is also universal but what about XOR? There isn't a hint of a NOT gate here - is there?
However, what about P XOR True?
P
True
P XOR P
F
T
T
T
T
F
Yes, P XOR True = NOT P and from this you can build an AND and an OR operator. XOR Is also a universal operator for Boolean logic.
It is something to think about that the whole of logic can be built from just one operation.
More Information
If you need a simple introduction to the hardware side of logic then Bebop to the Boolean Boogie: An Unconventional Guide to Electronics by Clive Maxfield is an easy read. If you like "For Dummies" then Logic For Dummiesby Mark Zegarelli is worth a look but notice that it goes well beyond the logic needed for computing and into phillosophical logic. For a more serious introduction, but it is dry and mathematical, try: Boolean Algebra and Its Applications by J. Eldon Whitesitt.Great Finally, even though it is out of print, Ideas in Information Theory, Language and Cybernetics by Jagjit Singh is essential reading for many of the topics in Babbage's Bag.
You can find out more about these books in the side panels of this article.
Classic data structures produce classic tutorials. In this edition of Babbage's Bag we investigate the advanced ecology of trees - perfectly balanced trees, AVL trees and B-Trees.
Error correcting codes are essential to computing and all sorts of communications. At first they seem a bit like magic. How can you possibly not only detect an error but correct it as well? How do the [ ... ]
