Collapsing Code Using DeMorgan's Laws

I ran across this Boolean logic law back in 2011, and it's stuck with me ever since.

De Morgan's Laws deal with taking multiple Boolean expressions and simplifying them. The transformations don't seem correct at first glance. It feels like there are logic holes, but they are solid, with mathematical proof.

Augustus De Morgan

If you're dealing with a lot of logical ands and ors, and logical not (negation), you can simplify code. Here's an example in C++:

Simplifying an expression with De Morgan's Law

You might change the code in a couple of iterations to remove the nested if statements. Because 2 nested if statements can be represented with an and (&&).

Original:

    if (not foundEnd) {
      if (not isSpace) {
        endPos = i;
        foundEnd = true;
        break;
      }
    }

So you simplify it to:

    if ((not foundEnd) and (not isSpace)) {
      endPos = i;
      foundEnd = true;
      break;
    }

Which makes sense, and is flawlessly logical. But you can do better with our buddy De Morgan:

    if (not (foundEnd or isSpace)) {
      endPos = i;
      foundEnd = true;
      break;
    }

Note when you group the two expressions and move the not out, your and turns into an or.

How does this work? Here's a bit more detail:

By the way, C++ (and C) does support using and, or, and not as keywords instead of &&, ||, or !. I like the English words better for natural readability, not nerd readability, and keeps from being confused (or making a typo) with & and |. I'm probably not of popular opinion here.

Not all keyboards provide all the symbols used for the logical operators, so the C++ Standard provides alternative representations. The identifiers and, or, and not are C++ reserved words, meaning that you can’t use them as names for variables and so on. They are not considered keywords because they are alternative representations of existing language features. Incidentally, these are not reserved words in C, but a C program can use them as operators, provided that the program includes the iso646.h header file. C++ does not require using a header file.

-- C++ Primer Plus (6th Edition), page 270

Read more about De Morgan's Laws.

comments powered by Disqus