De Morgan's Laws

Boolean logic is fundamental to the design of computer hardware even if it isn’t the whole story. The same holds true for programming. A program also needs the element of time built into it to make it work and this takes it beyond the bounds of simple Boolean logic. However, there are times when simple common sense reasoning lets even the best programmer down. For example, a common task is making a decision using an IF statement:

IF (A>0 AND A<10) THEN do something

The bracket following the IF is almost pure Boolean logic and the something only gets done if it works out to be true. So far, so simple. So simple, in fact, that many programmers decide that they don’t need to know anything about Boolean logic at all; a serious error. Consider how you would change this example so that the “something” was done when the condition was false. The simplest way is to write:

IF NOT(A>0 AND A<10) THEN do something

However, this offends some programmers who want to rewrite the condition not using the NOT. Try it and see what you come up with.

A common mistake is to use:

IF (A<=0 AND A>=10) THEN do something

This isn’t correct and if you don’t believe it simply write out the truth table for both. The correct NOT of the condition is:

IF (A<=0 OR A>10) THEN do something

The switch from AND to OR shocks many experienced programmers and it is a source of many programming errors.

My advice is that if you can write a logical condition in a natural form, but you really need the NOT of it then just write NOT in front of it! Otherwise learn De Morgan’s laws which make the fundamental connection between expressions that involve AND and OR:

NOT(A AND B) = NOT(A) OR NOT(B)

and

NOT(A OR B) = NOT(A) AND NOT(B)

You can see that the first law changes an expression that involves AND into one that involves OR and the second does the opposite. You can see this more clearly if the laws are written as:

A AND B = NOT(NOT(A) OR NOT(B))

and

A OR B = NOT(NOT(A) AND NOT(B))

You can see that you can use the first to replace A AND B by a more complicated expression involving OR and NOT. The second can be used to replace A OR B by an expression involving AND and NOT.

The 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, while AND operator isn't universal, the NAND, i.e. NOT AND, is. The truth table for NAND is just NOT(P AND Q):

To make a NOT all you have to do is write:

P NAND P= NOT(P)

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, though, 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. However, what about P XOR True?

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.