Programmers are master logicians - well they sometimes are. Most of the time they are as useless at it as the average joe. The difference is that the average joe can avoid logic and hence the mistakes. How good are you at logical expressions and why exactly is Augustus De Morgan your best friend, logically speaking?

It is commonly held that programming is a logical subject.

Programmers are great at working out the logic of it all and expressing it clearly and succinctly, but logic is tough to get right.

IFs and Intervals

A logical expression is just something that works out to be true or false.

Generally you first meet logical expressions as part of learning about if statements. Most languages have a construct something like

if  condition then other instructions

or just

if (condition) other instructions

Usually the conditions that you first meet are things like

if(A>0)


or

if(A==0)


At this stage the only real difficulty you are likely to have is with the use of strange symbols to replace the usual mathematical ones like == for equality, <= for less than or equal to and so on.

Languages have never standardized on what symbols to use, but most use something like:

A little later on you discover that you need to create compound conditionals that involve comparing multiple values.

For example

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


clearly this means that both conditions have to be true. In the same way

if(A>=0 OR A<=10)


means that either condition has to be true.

You might regard both of these as obvious, but such logical compounds have a meaning in terms of the range of values they allow. That is, these compound conditions define intervals that A has to be in for the condition to be true.

The first if statement means that A has to be in the range 0 to 10. Easy.

What about the second if statement?

Surely it is easy, after all we have only changed an AND to an OR?

The answer is that the first condition says that A has to be non-negative, i.e. greater than or equal to zero. The second condition is that A has to be less than or equal to 10.

Put the two together and you find that one of them is true for any value of A - so the condition is true for all A.

This looks trickier than it first seems.

How can we check what interval corresponds to true?

The answer is very simple.

Each condition that you write down specifies a region of the number line  e.g. A>=0 is the section to the right of the zero and A<=10 is the section to the left of 10:

Put the two together with an AND and the region where they are both true is the overlap:

Same reasoning applies if you put them together with OR only in this case the area where one or more of them is true is the entire colored area:

In other words the AND of the two intervals is the intersection of the areas that they cover and the OR is the union of the areas.

Now where have you heard this before?

The answer is in a Venn diagram.

In this case the areas are usually drawn as circles but the rules for overlapping are the same - AND is where they intersect and OR is the total area they cover.

Intervals in logical conditionals work in the same way.

Next question what is the NOT of an interval?

Easy its just the area it doesn't cover just as in the case of the Venn diagram:

It is the NOT of an interval that often causes trouble. Notice that the NOT of a less than or equal to is just greater than i.e. no equals. Similarly the NOT of a greater than is a less than or equal to. You just have to remember to drop or add the final point at the start of the interval.

It's all obvious really - but how many times do you see it pointed out or explained in this way?

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)

Related Articles

Boolean Logic

The Greeks, George Boole and Prolog

Javascript Jems - active logic, truthy and falsey

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