Practical Math for Programmers: DeMorgan’s and Other Logical Equivalences

The “Why This Should Matter to You” Story

TL;DR: You read my post about conditional bloopers and thought, “what’s wrong with that?!?”

Let’s say that you recall the lesson from last time and you make sure that you also avoid statements like “if(A && (A || B))”. You draw out truth tables whenever you feel you have time (and when no one is looking because, if you’re honest with yourself, you feel a little awkward doing it when people are watching). And yet things like this still happen to code you’ve written:

public void DoNightThings()
{
    if (!(!_itsLate || !_iAmTired))
        GoToBed();
}

gets refactored to:

public void DoNightThings()
{
    if (_itsLate && _iAmTired)
        GoToBed();
}

When you notice this in the source history, you check with your truth tables, and sure enough, it’s right. You kind of get it, in the end, but you always feel like you’re a step behind.

Math Background

In Boolean algebra, truth tables are sort of the equivalent of rote arithmetic memorization such as learning multiplication tables and using them to perform long-hand multiplication of larger numbers. It’s a rote, brainless, and time-consuming algorithm that you follow when there isn’t something better to use to get you to the answer more quickly. But the good news is that if you memorize a different set of information — some axiomatic laws of equivalence — you can get a lot of answers more quickly and easily. Here is the series of equivalences paired with explanations that will really help you understand the finer points of simplifying your conditional logic.

Identity Laws:  (A ^ TRUE) = A and also (A v FALSE) = A.  These identity laws simply point out the identity of variables compared with special constants.  This is like talking about additive identity (x + 0 = x) or multiplicative identity (x*1 = x) in elementary algebra (i.e. what you learn in junior high).

Domination Laws:  (A ^ FALSE) = FALSE and also (A v TRUE) = TRUE.  These are the opposites of the identity laws and have elementary algebra annihilator equivalent (x*0=0) or (x/x = 1).  These operate simply in that any false in a conjunction or any true in a disjunction renders the entire expression false or true, respectively.

Double Negative:  ~~A = A.  (Probably more formally known as “double negation” or negation of negation, but I think this easier to remember).  This quite simply says that if something is not not there, then it is there or, in Boolean logic, two falses make a true.

Commutativity:  (A v B) = (B v A) and (A ^ B) = (B ^ A).  This simple but important law    shows that the order of arguments to the conjunction and disjunction operators do not matter.  Think back to your arithmetic days when you learned that 4+3 = 3+4.  Same principle.

Associativity:  (A v B) v C = A v (B v C) and (A ^ B) ^ C = A ^ (B ^ C).  You can think of this as demonstrating that the location of parantheses is irrelevant when all operations are conjunction or disjunction operations.  If you reach ever further back in your brain from arithmetic, you may remember this guy as 3 + (4 + 5) = (3 + 4) + 5.

Tautology:  (A v ~A) = True and (A ^ ~A) = False.  We went over this in more detail last time, but suffice it to say that conjunction and disjunction with a variable’s negation leads to vacuously true or false results.

Idempotence:  (A v A) = A and also (A ^ A) = A.  Idempotence in general is the idea that an operation can be applied multiple times but only have a single effect.  For a rather practical example, consider turning a light switch on; the first time you push up a light turns on, but subsequent pushes up don’t turn the light somehow “more on”.  Idempotence in Boolean expressions means that redundant conjunctions and disjunctions simply have no effect.

Distribution:  A ^ (B v C) = (A ^ B) v (A ^ C) and A v (B ^ C) = (A v B) ^ (A v C).  This is a powerful equivalence because it provides a means to “move” parentheses around in Boolean expressions and retain their exact truth values.  Consider this in English and there is sense to it: “If A is true and also either B or C is true then A or C is true and A or B is true.”  Should that be a little abstract for your taste, think of it conversationally “It’s raining and either I’m inside or I’m wet” is the same as “It’s raining and I’m wet or it’s raining and I’m inside.”

De Morgan’s Laws:  ~(A ^ B) = (~A v ~B) and ~(A v B) = (~A ^ ~B).  This is another heavy hitter like distribution except that this one allows us to “move” negations when simplifying Boolean expressions.  This one also makes sense conversationally: “If it’s not true that person X is male and person x is female, then either person X is not male or person X is not female.”  De Morgan’s Laws also have an interesting incarnation in higher order logics like first order logic, but that’s probably going to be beyond the scope of this series for quite some time.

Absorption: A v (A ^ B) = A and A ^ (A v B) = A.  This was the main example we covered last time, so you can work out the truth table if you like.  As it turns out, this is a formally defined equivalence as well.

How It Helps You

In the last post in this series, I covered truth tables, which are sort of like the Boolean algebra equivalent of long division.  They’re a mechanical, inelegant process by which you can brute force a correct answer.  Logical equivalences are algebraic axioms that provide you with the building blocks for deductive reasoning — the building blocks for really thinking things through and critically solving problems.

You don’t necessarily need to memorize these, but I would study them enough at least to have something tickle the back of your mind the next time that you’re staring at an incredibly complex looking conditional.  That something will be “I think we can do better than this” and then, even if you don’t have the equivalences memorized, at least you’ll know enough to go look them up.  Armed only with truth tables, this can feel like flailing around in the dark while looking for a pattern.  But armed with logical equivalences you’ll say “oh, that’s right — I can eliminate the not here and I can turn these ors into ands over here, and… yeah, much better.”

Memorizing these equivalence laws would be even better, but not for the sake of pedantry or winning obscure trivia games.  I say that memorizing them is better because if you memorize them, you will practice them and conditionals, particularly complex ones, will start to work themselves into simpler forms automatically in your mind.  You will see things like Neo in the Matrix when he’s about to defeat Agent Smith, if the movie were a lot more boring.  Point is, though, you’ll develop an extremely good sense for when conditional logic could be simplified, corrected, or clarified and that has powerful ramifications for the readability, correctness and maintainability of the code you work with.

To circle back to the small example of a real world situation, understanding these Boolean laws of inference is likely to put you ahead of the curve, rather than behind it, when it comes to understanding conditional simplification.  Rather than the person whose code is always getting refactored, you’ll be the one doing the refactoring and doing it confidently.

Further Reading

  1. Wikipedia
  2. A bit more circuit flavored, but with some applied examples at the bottom.
  3. An introduction to the idea of proofs in Boolean algebra
  4. Very theoretical, with formal proof for most of the inference laws.
  • Eric Olsson

    Funny you cover this today…I ran into some existing code that I needed to cover with unit tests, and it was using 3 variables to ultimately return a CanExecute() for a Command.

    It turned out, I couldn’t reduce the expression any further, but working it out certainly helped clarify which variables to change in different unit tests to ensure good coverage.

    As a follow-up to the Absorption equivalence, I found a good explanation for it coming from a digital logic background:

    http://www.allaboutcircuits.com/vol_4/chpt_7/5.html

    I figured someone else may find it helpful as well.

  • http://www.daedtech.com/blog Erik Dietrich

    I think I’ve seen that site before… I definitely like the link and the visualization. And I think it goes almost without saying that while it’s nice and confidence inspiring to be able to know rules for simplification, there’s nothing like a good suite of unit tests to really tell you whether you’re borking anything or not :)

  • JamieCollins

    Rewrite rules are better than truth tables but a calculation engine is better than both. I was recently looking at converting a SQL search condition in a CHECK constraint from disjunctive normal form (DNF) to conjunctive normal form (i.e. convert one complex constraint into several simpler ones that together are logically equivalent). I discovered Wolfram Alpha. Enter a logical expression and it gives various outputs, including minimal forms (CNF, DNF and others), plus Venn diagram, circuit diagram and truth tables (if the expression isn’t too involved). For example, here’s your first example, substituting single letters for your variable names:

    http://www.wolframalpha.com/input/?i=NOT+%28+%28++NOT+P+%29+AND+%28+NOT+Q+%29+%29

    I agree one should be familiar with the rewrite rules but it is good to be able to check one’s answer quickly!

  • http://www.daedtech.com/blog Erik Dietrich

    That is awesome! Thanks for the link!