Negation and De Morgan's Law

The big problem with conditions and logical expressions in general is that we often want them the other way around. For example, if you have a condition that is true if there is an error you might want to write:

if(ERROR) then do something

or perhaps

if(NOT ERROR) then do something

If you want to be safe then just write things exactly like this. But for strange reasons some programmers hate writing the NOT of an expression. I've even seen programmers write things like:

if(ERROR) then
 else do something

to avoid it.

It is even more tempting to try to convert the logic when you have an expression like:

if(NOT (A>=0 AND A<=10))


This is where the problems begin and the errors get introduced.

What is the equivalent of the above?

Some programmers will write:

if( NOT(A>=0) AND NOT(A<=10)


and simplify this to:

if( A<0 AND A>10)


Many just go straight to the final expression without the intermediate step but it doesn't matter how you get there -

it's wrong.

To see this, just consider the way the intervals in the two expressions intersect.

The key to this sort of manipulation are  De Morgan's laws.

The first law is that

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

You can see that this gives you a way of getting rid of the overall NOT in front of the expression but notice that you have two NOTS and the AND has changed to an OR.

The second law you can probably guess:

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

and this has the same form, only it swaps an OR for and AND.

Sometimes De Morgan's laws are used for this very purpose, i.e. to swap an AND for an OR. Sometimes they are used to get rid of lots of NOTs inside the expression and replace it with a single NOT.

Whatever the reason, De Morgan's laws are really useful.

For example to convert:

if( NOT(A>=0 AND A<=10) then...

into something that doesn't have NOTs, you would first apply De Morgan;s first law:

if( NOT(A>=0) OR NOT(A<=10) then...

Then you could use the Venn diagram approach to convert the two intervals into:

NOT(A>=0)  =   (A<0)

and

NOT(A<=10) = (A>10)

Putting this all together gives:

if( (A<0) OR (A>10) then...

Again if you compare the interval diagrams you will see that the two ways of writing the expressions are the same.

Yes, I know that you would never make such silly mistakes, but the real life situations are always more complicated. Many programmers find that the idea of switching a NOT around also involves swapping an AND for an OR or an OR for an AND just doesn't seem right.

There are many simple looking simplifications of logic that we are all tempted to do "in our heads". How many hours have been wasted trying to debug such trivia?

My advice is that if you have a logical expression in a natural understandable form, then leave it as it is and if you need it's negation use a NOT. If you really want to optimize then check the algebra carefully.

If you are wondering about the man who is known for De Margan's Law, he was a British mathematician and logician who tutored Ada Lovelace in the nineteenth century.

Augustus De Morgan

(June 27, 1806 - March 18, 1871)

• Mike James is the author of Programmer's Guide To Theory, a book which presents and explains core ideas in Computer Science in an informal and yet informative way.

Related Articles

Boolean Logic

The Greeks, George Boole and Prolog

When Lovelace Met Babbage 

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

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:1871962439>