Introduction to Boolean Logic

### New Book Reviews!

 Introduction to Boolean Logic
Written by Harry Fairhead
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.

You can find out more about these books in the side panels of this article.

#### 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

blog comments powered by Disqus

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.

 Hashing - The Greatest Idea In ProgrammingAlthough it is a matter of opinion, you can't help but admire the idea of the hash function. It not only solves one of the basic problems of computing - finding something that you have stored som [ ... ] + Full Article Data Compression The Dictionary WayOne of the most important lossless forms of compression is the LZW dictionary based method. It turns up in lots of compression utilities - ZIP, Compress, Deflate and in GIF and PNG format files. It is [ ... ] + Full Article Other Articles

<ASIN:1856175073 >

<ASIN:0471799416>

<ASIN:0486477673>

<ASIN:0486216942>

<ASIN:1782050043>

 RSS feed of all content Copyright © 2016 i-programmer.info. All Rights Reserved. Joomla! is Free Software released under the GNU/GPL License.