I do not usually write lab notes on specific programming issues. I try to keep my web site general so many people can understand it. This note is an exception, its a real simple software related issue. Over the years of writing software I keep coming back to DeMorgan’s Theorem. It was one of those things that in college I never thought I would use, but it seems to pop up on a regular basis at work. I think this is fascinating stuff, particularly when academia meets the pavement.
First, the background. DeMorgan’s Theorem states:
DeMorgan’s theorem cannot be proved or reduced using math. The only proof is a brute force proof. At this point your probably thinking, "how can this academic theorem prove to be useful at work?" Let me show by example.
This is going to be a real simple contrived example to demonstrate DeMorgan. Suppose the programming job is to read two switch inputs and to turn a motor on if both switches are closed. Perhaps to drive the motor ON we also have to output a LOW. It is common in computer to have negative I/O logic. Here is a schematic for this. We can see that if either switch is closed the input to the computer will go low.
I can now write software to implement the required function.
If ( SW1 = 0) AND ( SW1=0)
THEN MOTOR = 0
ELSE MOTOR =1
Do you see the correlation between this software statement and DeMorgan’s Theorem? Now we can simplify the programming statement using DeMorgan’s. Two simplifications make the statement easier to read. We take advantage of BOOLEAN type's and we can switch around the THEN and ELSE part to get rid of a NOT operator.
If (SW1 OR SW2)
THEN MOTOR =1
ELSE MOTOR =0
An astute programmer might note a further simplification by writing a single algebraic Boolean expression for this statement such as
MOTOR = SW1 OR SW2.
Understanding and using DeMorgan’s Theorem has simplified the programming, if only a little here. In larger applications we would get a larger return on our simplification investment.
Even though many compilers will reduce expressions internally, simplifying your programming pays rewards in understandable code. ALWAYS simplify code and remember to use DeMorgan.