De Morgan rewrites

Why this matters

Conditions grow. A rule such as "refuse entry unless the person is an adult and has an ID" becomes hard to read once a ! is placed in front of it. A reader then has to flip every && and every comparison in their head before they know what the code does. A rewritten condition often reads more directly, and the code stays the same in what it does.

The rewrite uses two rules that the mathematician Augustus De Morgan described in the 1800s. They are called De Morgan's laws. This lesson covers how to apply them, how to check a rewrite, and the mistakes people make when they apply them by hand.

The guard clauses lesson comes before this one, and the range checks lesson comes after it. This lesson covers only the rewrite itself.

The idea in plain words

Three words need definitions first.

! means NOT. It flips a bool. !true is false, and !false is true.
&& means AND. It is true only when both sides are true.
|| means OR. It is true when at least one side is true.

Here is a rule in ordinary speech. "The club is closed to people who are not adults and do not have an ID." A person is refused when they are under 18, or when they have no ID. The "not both" form and the "either" form say the same thing.

De Morgan's laws turn the "not both" form into the "either" form:

!(a && b) is the same as !a || !b.
!(a || b) is the same as !a && !b.

Read the first one out loud. Not (both a and b) is the same as (not a) or (not b). The ! moves inside the brackets, and the operator flips from && to ||. The second law flips the other way.

A truth table is the way to check a rule. Each row is one combination of values for a and b, and each column is one form of the expression. If two columns always match, the rewrite is correct for every input.

C++ · editable

The output is:

a=false b=false | !(a && b)=true !a || !b=true | !(a || b)=true !a && !b=true
a=false b=true | !(a && b)=true !a || !b=true | !(a || b)=false !a && !b=false
a=true b=false | !(a && b)=true !a || !b=true | !(a || b)=false !a && !b=false
a=true b=true | !(a && b)=false !a || !b=false | !(a || b)=false !a && !b=false

Read the first pair of columns. The first column is !(a && b) and the second is !a || !b. They match in all four rows, which is what the first law says. The last two columns show the second law, and they match in all four rows too.

The for (bool a : {false, true}) line loops over the two values in the braces. With two inputs there are four rows. Each extra input doubles the number of rows, so three inputs give eight rows and four inputs give sixteen.

Example 1: the club door

The rule is that a person is refused entry unless they are 18 or older and have an ID. In code, the refusal test is !(age >= 18 && has_id). The rewrite is age < 18 || !has_id. The change has two parts. The && becomes ||, and each comparison is negated: >= becomes <, and has_id gets its own !.

C++ · editable

The output is:

17 true -> true true
17 false -> true true
18 true -> false false
18 false -> true true
25 true -> false false
25 false -> true true
mismatches: 0

Each line shows one combination of age and ID. The -> gives the answer from the original form and then from the rewritten form. The two answers match in all six rows, and mismatches: 0 says the same thing as a count.

Check one row by hand. A person aged 18 with an ID should be let in. The original form is !(true && true), which is !true, which is false, so the person is not refused. The rewritten form is 18 < 18 || !true, which is false || false, which is false. Both forms agree.

The rewrite is easier to read in one way. age < 18 says "too young" directly, and !has_id says "no ID" directly. The reader does not have to flip anything.

Example 2: a long list of characters

A common condition checks whether a character is not a space, a tab or a newline. A character here is one symbol in a piece of text. '\t' is the tab character, and '\n' is the newline character. Written with a negated group, the test looks like this: !(c == ' ' || c == '\t' || c == '\n').

Each == is a comparison. The three comparisons are joined by ||, so the group is true when c is any of the three. The ! in front of the group turns that into "none of them."

De Morgan's law for three terms works the same way as for two. Each == becomes !=, and each || becomes &&.

C++ · editable

The output is:

original: 4
rewritten: 4

The text "a b\tc\nd" has seven characters, and three of them are white space: a space, a tab and a newline. That leaves four letters, and both versions count four.

The rewritten version is easier to scan. Each line says one thing that the character is not. A reader can check each != on its own, and a reader can add a fourth case by adding one more line with &&.

Example 3: a long condition with four variables

Now a longer condition. Take this test with four bool values a, b, c and d.

!(a && (b || !c)) || (d && !a)

The rewrite happens in steps. Each step applies one rule and leaves the rest alone.

Step 1. The outer ! covers a && (b || !c). The first law says !(x && y) is !x || !y. Here x is a and y is (b || !c). So !(a && (b || !c)) becomes !a || !(b || !c).

Step 2. The !(b || !c) is the second law. It becomes !b && !(!c). Two ! signs in a row cancel out, so !(!c) is c. The part becomes !b && c.

After steps 1 and 2 the whole condition is (!a || (!b && c)) || (d && !a).

Step 3. Look at d && !a. It is true only when !a is true. So whenever that part is true, !a is already true in the first part of the ||. The second part adds nothing, and it can be removed. The condition becomes !a || (!b && c).

Step 3 uses a different idea from De Morgan. The check that makes it safe is the table. The program below compares the long form and the short form for all sixteen combinations of the four values.

C++ · editable

The output is:

true in 10 of 16 cases
mismatches: 0

The two forms agree in every one of the sixteen cases. The short form is true in ten of them. A check like this takes a few seconds to write, and it catches the mistake that algebra on paper can hide.

Example 4: a loop condition

A while loop repeats its body as long as its condition is true. Negating a condition is a common way to write "keep going until." The program below counts steps in a loop. A search sets found to true at a given step, and a limit caps the number of steps. The loop should run while the search has not found the target and the limit has not been reached.

C++ · editable

#include <iostream>
using namespace std;

// Keeps counting while the search has not found the target and the limit is not reached.
int run_original(int limit, int stop_at) {
    int count = 0;
    bool found = false;
    while (!(found || count >= limit)) {
        ++count;
        if (count == stop_at) {
            found = true;
        }
    }
    return count;
}

int run_rewritten(int limit, int stop_at) {
    int count = 0;
    bool found = false;
    while (!found && count < limit) {
        ++count;
        if (count == stop_at) {
            found = true;
        }
    }
    return count;
}

int run_wrong(int limit, int stop_at) {
    int count = 0;
    bool found = false;
    while (!found || count < limit) {
        ++count;
        if (count == stop_at) {
            found = true;
        }
    }
    return count;
}

int main() {
    int cases[][2] = {{5, 2}, {3, 10}, {4, 4}};
    for (auto& c : cases) {
        int limit = c[0];
        int stop_at = c[1];
        cout << "limit " << limit << ", found at " << stop_at << ": original "
             << run_original(limit, stop_at) << ", rewritten " << run_rewritten(limit, stop_at)
             << ", wrong " << run_wrong(limit, stop_at) << "\n";
    }
    return 0;
}

The output is:

limit 5, found at 2: original 2, rewritten 2, wrong 5
limit 3, found at 10: original 3, rewritten 3, wrong 10
limit 4, found at 4: original 4, rewritten 4, wrong 4

Start with the first row. The limit is 5 and the target is found at step 2. The loop body runs twice, and at step 2 found becomes true. The original test is !(found || count >= limit). With found true, the part in the brackets is true, and the ! makes the whole test false, so the loop stops at 2.

The rewrite applies the first law, with found as the first part and count >= limit as the second. The outer ! turns || into &&, so the test becomes !found && !(count >= limit). The second ! flips >= to <, which gives !found && count < limit.

The wrong version keeps the || and does not change the inner comparison. It is !found || count < limit. After found becomes true, !found is false, but count < limit is still true until the count reaches 5. So the loop keeps going past the step where the target was found. The wrong version differs in the first two rows, and the third row is the same only because the target was found on the limit itself.

How to rewrite a negated condition

Use these steps for any negated test.

Write down the condition inside the !, with one comparison or bool per part.
Negate each part. A comparison flips its operator, and a plain bool gets a ! in front of it.
Change && to ||, or || to &&.
Remove any pair of ! signs in a row, because two ! signs cancel out.
Check the rewrite with a truth table, or with a program like the ones above, before you rely on it.

When the original reads better

A rewrite is a tool, not a rule that must always be used. Leave a condition alone when the original reads better to the people who maintain the code.

Consider if (!file_is_open). This is one ! on one bool, and it already says what it means. Rewriting it would add nothing. Likewise, if (!(x > 0)) is clear to most readers, although if (x <= 0) is shorter. The rewrite is worth doing when a negated group of two or more parts is hard to read, as in the club door example, or when the ! sits in front of a long bracket that a reader has to flip in their head.

Ask one question before you rewrite: will a reader understand the new form faster than the old one? If the answer is no, keep the old form. If the answer is yes, check the rewrite with a truth table, then keep it.

Naming the parts before combining them

A long condition is easier to check when each part has a name. Instead of one line with three comparisons and a !, write one bool for each part, then combine the names.

For the club door, the parts are is_adult and has_id. The refusal test can then be written as bool refused = !(is_adult && has_id);, and a reader sees the two facts by name. A rewrite for the refusal test is then !is_adult || !has_id, and the two names make it easy to see that each part is negated separately.

Naming does not change the logic, so the truth table still applies. It only makes the parts easier to read and to check one at a time.

Common mistakes

Changing the operator but not the sign

The most common mistake is to flip the operator without negating each part. !(a && b) is not !a && !b. The program below prints both forms for every combination of a and b.

C++ · editable

The output is:

a=false b=false right=true wrong=true
a=false b=true right=true wrong=false
a=true b=false right=true wrong=false
a=true b=true right=false wrong=false
mismatches: 2

The wrong form disagrees with the right form in two rows. In the second row, a is false and b is true. !(false && true) is true, but !false && !true is false. A wrong rewrite can look right on one row and fail on another, which is why the table matters.

Forgetting to negate a comparison

When a comparison is negated, its operator changes. !(age >= 18) is age < 18. !(x <= 5) is x > 5. A rewrite that keeps the same operator, such as writing !(x <= 5) as x <= 5, is wrong for the value 5. Write the negation as the opposite test, and check the boundary value with the table.

Writing `!` without parentheses

! binds more tightly than >=, so !age >= 18 does not mean "not (age is at least 18)". It means (!age) >= 18, which first turns age into a bool and then compares it with 18. The program below shows the difference.

C++ · editable

Saved as l07_prec.cpp, g++ with -Wall reports both forms:

l07_prec.cpp: In function ‘int main()’:
l07_prec.cpp:7:42: warning: logical not is only applied to the left hand side of comparison [-Wlogical-not-parentheses]
    7 |     cout << "!age >= 18 gives " << (!age >= 18) << "\n";
      |                                          ^~
l07_prec.cpp:7:37: note: add parentheses around left hand side expression to silence this warning
    7 |     cout << "!age >= 18 gives " << (!age >= 18) << "\n";
      |                                     ^~~~
      |                                     (   )
l07_prec.cpp:7:42: warning: comparison of constant ‘18’ with boolean expression is always false [-Wbool-compare]
    7 |     cout << "!age >= 18 gives " << (!age >= 18) << "\n";
      |                                     ~~~~~^~~~~

The output is:

!age >= 18 gives false
!(age >= 18) gives true

The two warnings say the same thing in two ways. The ! is applied to age alone, and the comparison with 18 is always false because !age is only 0 or 1. Put parentheses around the whole comparison whenever you negate it. The output shows that the two lines disagree for a person aged 5.

Negating a value that can be NaN

For whole numbers, !(x < 1) and x >= 1 always agree. For floating-point numbers (numbers with a decimal point, such as double), there is one exception. A floating-point number can hold NaN, which stands for "not a number." It appears after an invalid operation such as dividing zero by zero. Every comparison with NaN is false, including < and >=. So a negated < can be true when the plain >= is false.

C++ · editable

The output is:

!(x < 1.0)  = true
x >= 1.0    = false
!(n < 1)    = false
n >= 1      = false

The integer lines agree, and the floating-point lines do not. If a value might be NaN, keep the original negated form, or check for NaN with a separate test before the comparison. The rewrite is safe for integers and for values you know are not NaN.

Practice

Exercise 1

Rewrite !(a < 0 || b > 10) so that it has no ! in front of a bracket. Then check the rewrite with the values from the program in Example 2.

Show the answer

a >= 0 && b <= 10

The outer ! turns || into &&. Then each comparison is negated: < becomes >=, and > becomes <=. A check over a values -2, -1, 0 and 3 and b values 5, 10, 11 and 20 finds no mismatches with the original form.

Exercise 2

Rewrite !(x == 0 || x == 1) without a ! in front of the bracket.

Show the answer

x != 0 && x != 1

Each == becomes !=, and the || becomes &&. The rewrite matches the original for x values -1, 0, 1 and 2.

Exercise 3

Simplify !(score < 50 && !passed) into a form with no ! in front of a bracket.

Show the answer

score >= 50 || passed

Apply the first law to the outer !. It becomes !(score < 50) || !(!passed). A ! in front of !passed cancels out, so the second part is passed. Then !(score < 50) is score >= 50. A check over scores 0, 49, 50 and 80, with passed set to both values, finds no mismatches.

Exercise 4

Predict the output of !(n > 5 && n < 10) for n equal to 7, 3 and 12.

Show the answer

The output is false, true, and true.

For 7, both parts of the && are true, so the bracket is true, and the ! makes it false.
For 3, the first part n > 5 is false, so the bracket is false, and the ! makes it true.
For 12, the second part n < 10 is false, so the bracket is false, and the ! makes it true.

Exercise 5

A programmer rewrote if (!(age >= 18 && has_id)) as age < 18 && !has_id. Find the mistake, and say how many of the six combinations of age and ID give a different answer.

Show the answer

The && should be ||. The correct rewrite is age < 18 || !has_id. The wrong version disagrees with the original in 3 of the 6 combinations. For example, a 17-year-old with an ID is refused by the original, because !(false && true) is true. The wrong version lets that person in, because 17 < 18 && !true is false.

Summary

!(a && b) is !a || !b, and !(a || b) is !a && !b.
When you negate a comparison, flip the operator, such as >= to <.
Put parentheses around a comparison that you negate, because ! binds more tightly than comparisons.
Check each rewrite with a truth table over all combinations of its inputs.
For floating-point numbers that can be NaN, a negated < is not always the same as >=.

De Morgan rewrites

Why this matters

The idea in plain words

Example 1: the club door

Example 2: a long list of characters

Example 3: a long condition with four variables

Example 4: a loop condition

How to rewrite a negated condition

When the original reads better

Naming the parts before combining them

Common mistakes

Changing the operator but not the sign

Forgetting to negate a comparison

Writing ! without parentheses

Negating a value that can be NaN

Practice

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Summary

Stuck? Ask the tutor

Writing `!` without parentheses