Introduction to Boolean Logic

### New Book Reviews!

 Introduction to Boolean Logic
Article Index
Introduction to Boolean Logic
Binary arithmetic and flip-flops
Universal Gate

## Universal Gate

One final and slightly deep thought.

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.

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 Dummies by 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.

#### Related Articles

Celebrate the 200th Birthday of George Boole With Logic

Dangerous Logic - De Morgan & Programming

CPU

Getting Started With Digital Logic - Logic Gates

Binary Arithmetic

Binary - Negative Numbers

The Greeks, George Boole and Prolog

Claude Shannon - Information Theory And More

How Memory Works

The Computer

 Confronting The Unprovable - Gödel And All ThatGiven infinite computing power surely there cannot be any problem or puzzle that is incapable of solution? The famous or infamous incompletenes theory of Kurt Gödel says different. + Full Article The Lost Art Of The Storage Mapping FunctionYou may not have heard of SMFs, Storage Mapping Functions, but you are likely to have used them. They tend to be overlooked because there are more exciting methods of implementing storage, such as has [ ... ] + Full Article Other Articles

<ASIN:1856175073 >

<ASIN:0471799416>

<ASIN:0486477673>

<ASIN:0486216942>

<ASIN:1782050043>