Posted on

Sometimes the logic in your application get a bit out of hand, and ends up an unreadable, tangled mess of negated conjunctions and disjunctions. A judicious application of De Morgan's Laws can help you translate confusing expressions or sub-expressions to something a bit more readable, while maintaining the same logical truths and falsehoods that you originally intended.

De Morgan's Laws are expressed as the following set of statements in the notation commonly used in formal logic:

¬(A ∧ B) ⇔ (¬A) ∨ (¬B)
¬(A ∨ B) ⇔ (¬A) ∧ (¬B)

When implemented in Python, they take on the following form:

not (a and b) == (not a or not b)
not (a or b) == (not a and not b)

A good way of remembering the rules is: the application of the negation to the elements of the sub-expression flips the conjunction to a disjunction, and vice versa. You can think of this as a pseudo-"distributive" law. Or, if you want to be pedantic:

The negation of a conjunction is the disjunction of the negations; The negation of a disjunction is the conjunction of the negations.

Reducing the Number of Negated Expressions

I firmly believe that the difficulty in comprehending a complex boolean expression increases with the number of negated sub-expressions. Thus, going from the right-hand side to the left-hand side of the above stated De Morgan's Law can often be an improvement in readability:

(not is_expensive or not is_well_built) == not (is_expensive and is_well_built)

By factoring out the negation, the parenthetical expression (is_expensive and is_well_built) can be mentally evaluated in a more straightforward manner, and the boolean result can simply be flipped at the end.

Flipping Inequality Relations

A more complex but perhaps ultimately more useful application of De Morgan's Laws allow for the rewriting of inequality relations. The expression not (price < 9.99 or quantity > 30) can make you scratch your head for a few seconds, but you might find the equivalent expression more comprehensible:

not (price < 9.99 or quantity > 30) == (price >= 9.99 and quantity <= 30)

Reducing Overly Complex Expressions

We've all been there. Your very tight, well thought out code that encapsulate fundamental business logic morph into a tangle of boolean expressions as the requirements of the application and/or the business evolve over time. Suddenly, you come across this wonderful mess:

not A or not B or not (A or B)

And, thanks to the application of De Morgan's Law and the commutative property, it can be simplified:

= not A or not B or not A and not B
= not A or not A and not B or not B
= not A or not B
= not (A and B)

Which, I think we can agree, is much easier to understand than the original expression.