How deMorgan's Theorems Can Help Programmers


Logic is an important aspect of programming and two important theorems in logic can be a big help to programmers.

Basics of computer logic

In software, logic is generally found in an if statement. This implements the idea that if some condition is true, then do something. For example,

If the user clicks a link then display that web page

if a equals 10 then b = 7 or more often if (a==10) b=7

And these can be more complex by using the ideas of and and or. For "x and y" both x and y must be true; likewise for "x or y" either can be true. It is just like the words in a natural language such as English.

These can be expressed visually with truth tables or Venn diagrams:

Venn diagram 01
Here, the top row and left column show the inputs: the values of x and y in our example. Both have to be true for the value of and to be true. It's like the addition tables use to teach children to add.

Venn diagram 02

Here, the top row and left column show the inputs: the values of x and y in our example. Only one has to be true for the value of or to be true.

With Venn diagrams:

Venn diagram 03

Here all the colored are is the or and the green area where the circles overlap is the and. There is an additional operation called not. If we talk about "not x" we mean everything that is not in the blue circle. That includes all the white space and all the yellow that does not overlap with the blue "x" circle.

Complex expressions

The operators and, not and or are fairly straightforward. The issues come when we combine them.

Consider the case where "x is even and x is greater than 0" (so x is 2, 4, 6, 8, and so on). What if I wanted to exclude those positive even numbers? I could say "not 'x is even and x is greater than 0'", but many programmers would consider that ugly and difficult to read.

even(x) and x > 0

not (even(x) and x>0)

[the parens are for grouping here]

What we mean by "not 'x is even and x is greater than 0'" is really "x is odd or x is less than or equal to zero". What we did is apply one of deMorgan's theorems: we changed the senses of the comparisons ('even' became 'odd', and 'greater than zero' became less than or equal to zero') and we changed and to or. Our pseudocode then becomes odd(x) or x<= 0. That is generally believed to be more clear.

Here are both of deMorgan's theorems:

deMorgan's theorem

And some examples:
deMorgan's theorem examples

These theorems are simple yet powerful. I hope you can use them to make your code more readable!

John McDermott

Written by John McDermott

John McDermott, CPTD, started his work in computer security in 1981 when he caught an intruder in a system he was managing. In recent years his consulting has included security consulting for small businesses. He is Security+ and CCP certified. In his 30 years with Learning Tree John has written and taught courses in programming, networking and computer security. He is the co-author of Learning Tree’s course System and Network Security: A Comprehensive Introduction. John is currently a learning and development consultant in northern New Mexico. He lives in a house made of earth with his wife, who is an artist.