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.

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

Dangerous Logic - De Morgan & Programming

CPU

Getting Started With Digital Logic - Logic Gates

Binary Arithmetic

Binary - Negative Numbers

The Greeks, George Boole and Prolog

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.

 

Banner


Public Key Encryption

Public key encryption is vital to the commercial Internet. We look at how it works and explain the RSA system in detail.



Magic of Merging

The merge sort is an under-appreciated algorithm - yet it is neat, clever and it still has its uses. With the rise of big data, parallel methods and online processing, you can even argue that it is gr [ ... ]


Other Articles

<ASIN:1856175073 >

<ASIN:0471799416>

<ASIN:0486477673>

<ASIN:0486216942>



 
 

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