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.

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.

To complete the trio:

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:

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.

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.

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))

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);