De Morgan’s Law

Simplify logical conditions using de Morgan's Laws, without all the strange symbols of Boolean Algebra

If you have been coding for a little while you will no doubt have used a logical condition in one form or another. Logical expressions result in a (Boolean) value of true or false and are regularly used to branch the flow of control through a program.

A logical expression employs a combination of the following fundamental operators:

• NOT, converts true into false and false into true, and is sometimes known as an 'inverter'.
• AND, takes two values and only returns true when both are true, otherwise it returns false.
• OR, also takes in two values but this returns false only when both inputs are false, otherwise it returns true.

Note these are the 'fundamental' operations (sometimes known as logic gates) as there are others such as XOR, NAND, NOR, etc. But these are a combination of the first three and outside the scope of this article. Add a comment if you would like to know more.

A convenient way to visualise Boolean operators is to map inputs to outputs through a Truth Table; the simplest being the NOT as it only has one input and output.

NOT	Input	Output
	False	True
	True	False

When we have more than one input it is more useful to form columns and rows out of the inputs and express the outputs in the cell where they intersect.

AND		Input B
		False	True
Input A	False	False	False
	True	False	True

To complete the trio:

OR		Input B
		False	True
Input A	False	False	True
	True	True	True

Logical expressions can quickly get complicated when you combine more than a couple of terms, so it is useful to know a trick or two to simplify the logic. Here is where we have to thank the 19th-century mathematician Augustus de Morgan.

De Morgan’s Law

In basic terms Mr de Morgan observed there is a combination of Boolean operators that are equivalent and this can be used to convert one expression into another without affecting the result/output.

Consider the expression:

NOT(A) AND NOT(B)

Here is the Truth Table:

NOT(A) AND NOT(B)	Input B
Input A	False	True
False	False	True
True	True	True

This should look similar to the OR Truth Table above, except all the values are inverted. This means, as observed by Mr de Morgan, the following expressions are equivalent.

NOT(A) AND NOT(B)   is the same as       NOT(A OR B)

Arguably NOT(A OR B) is simpler, in terms of the number of logical operators used and is easier to understand.

A worked example

You might say, most of my conditions do not involve Boolean values. They are expressions such as:

• hourlyPay > 1000
• !stringValue.length
• object != null.

However, the result of all three of the above is a Boolean value of true or false. So, consider the following if statement.

if (not(A) and (B or not(C)) then
    /* Do nothing */
else 
    /* Do something */

This sort of case arises more often than you might think where the obvious logical expression is the exact opposite of what you actually need but it looks too complicated to reverse it. One option would be to ‘not the lot’.

if (not(not(A) and (B or not(C))) then  /* Do something */

But this makes the expression even more difficult to understand, but here comes de Morgan’s Law to the rescue. Before we apply the Law, let’s start with the truth table, with three inputs; A, B and C.

not(not(A) and (B or not(C))		Input C
Input A	Input B	False	True
False	False	False	True
	True	False	False
True	False	True	True
	True	True	True

From the truth table we can see the result should be true when A is true or when B is false and C is true. This means we can rewrite the expression as:

if (A or (not(B) and C)) then   /* Do something */

Figuring out the truth table with three terms is not trivial and to be honest I used a spreadsheet to do it for me using the following formula for the output column O1.

A	B	C	O1
FALSE	FALSE	FALSE	FALSE
FALSE	FALSE	TRUE	TRUE
FALSE	TRUE	FALSE	FALSE
FALSE	TRUE	TRUE	FALSE
TRUE	FALSE	FALSE	TRUE
TRUE	FALSE	TRUE	TRUE
TRUE	TRUE	FALSE	TRUE
TRUE	TRUE	TRUE	TRUE

O1  =not(and(not(A2),or(B2,not(C2))))

Using de Morgan’s Law

1. Starting with the expression not(not(A) and (B or not(C)) we apply the law to remove the outer not operation without affecting the result. a. Remove the outer not => (not(A) and (B or not(C)) b. Invert the left and right terms => (A and not(B or not(C)) c. Swap the operation between the two terms to get: (A or not(B or not(C))
2. Next, we apply the law to the inner not expression using the same three steps as above to get, (A or (not(B) and C))

We can check the result using the spreadsheet function:

O2  =or(A2,and(not(B2),C2))

A	B	C	O1	O2
FALSE	FALSE	FALSE	FALSE	FALSE
FALSE	FALSE	TRUE	TRUE	TRUE
FALSE	TRUE	FALSE	FALSE	FALSE
FALSE	TRUE	TRUE	FALSE	FALSE
TRUE	FALSE	FALSE	TRUE	TRUE
TRUE	FALSE	TRUE	TRUE	TRUE
TRUE	TRUE	FALSE	TRUE	TRUE
TRUE	TRUE	TRUE	TRUE	TRUE

Conclusion

In the same way you might change (a*b + b*c) in to (a+c) *b, or vice-a-versa, to make it more readable, De Morgan's Law provides a useful way to simplify logical expressions. Hopefully this article has demonstrated its utility and how to apply the law.

Personally, I find drawing out truth-tables laborious and error prone, especially once you get more than three terms; even if you do have a spreadsheet to hand. Spotting opportunities to employ de Morgan’s Law becomes second nature and, I hope you agree, applying the steps is trivial.

Bonus material

Lazy evaluation

Many programming languages support the facility of lazy evaluation of conditional expressions. Consider the following:

A and B

Because of the And operation, if A is false it does not matter what B is, the result will always be false. If A is true, the result will be the value of B. Conversely, in an Or expression,

A or B

If A is true, it does not matter what B is, the result will always be true. If A is false the result will be whatever value B has.

Avoid returning Boolean values resulting from a condition

When reviewing code I occasionally see Boolean values being returned from a conditional statement as follows.

if (A === B) {
    return true;
}
else {
    return false;
}

In a more modern form I also see this, which is only slightly better.

return (A === B) ? true : false;

Even when the logic is reversed, using the conditional expression is unnecessary and the following is equivalent to both of the above examples.

return (A === B);

Comments

[Luke Poirrier]

Interesting read! You did a great job of explaining the why, what, and how of De Morgan’s Law. As a self-taught developer I really appreciate any CS knowledge I can pick up on the way.

Keep 'em coming, TGJ!

[Tracy Gilmore]

Luke, I have published another post in this mini-series on the topic of recursion that might interest you. I have another post in draft on Regular Expressions but I am always on the look-out for topics. If you have any question that might make a post please send them my way.
Thanks for the positive feedback and I wish you well on your CS journey. TGJ.

[cubiclesocial]

If you want some formal CS knowledge, there's nothing better than grabbing a copy of the 800+ page PDF assembly opcode manual for your hardware and a suitable assembly language compiler and going to town. You'll learn that your computer is WAY faster than you imagined as well as better understand how the technology works under the hood and even get a taste for over-optimization for every clock cycle you can squeeze out of that CPU. But you'll also appreciate the sugar-coated, bloated, generally cross-platform/cross-architecture languages we've grown accustomed to that make our lives as developers easier at the cost of performance.

I grew up typing in little assembly language, batch files, and various other programs from magazines. Also taught myself ANSI C from books. No Internet back then. Everyone's got it easy and we're all lazy now that an answer is a quick Google Search away.