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 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
if (condition) other instructions
Usually the conditions that you first meet are things like
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:
= or ==
less than or equal to
greater than or equal to
!= or <>
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 fo teh 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
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 -
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)
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.