De Morgan rewrites in Python

Why this matters

Many if conditions are hard to read because they start with not in front of a long group. A shipping rule written as "not (paid and not cancelled and in stock and address valid)" makes the reader work out what the rule means. Sometimes the same rule is easier to read in another form, and sometimes that form is also easier to check for mistakes.

De Morgan's rules give you that other form. They were described by the mathematician Augustus De Morgan in the 1800s. They say how a negation (the word not) moves through and and or. If you know the two rules, you can rewrite a condition and be sure it means the same thing.

This lesson covers the two rules, shows them on a truth table, and applies them to conditions of increasing length. It ends with the mistakes that cause a rewritten condition to be wrong, including one that only appears with decimal numbers.

The idea: a negated group flips its operators

Start with a plain-language example. Suppose a sign on a shop door says: "The shop is not open when the door is locked and the alarm is off." Think about what that means. The shop is not open when both things are true. The shop is open when at least one of them is false. So the shop is open if the door is unlocked or the alarm is on.

Someone who rewrote the sign with "not" on each part and kept the word "and" would make a mistake. "The shop is open when the door is not locked and the alarm is not off" says both must be true. That is a different rule, and it would leave the shop shut in cases where it should be open.

Python works the same way. A not in front of a group flips the group, and that flip turns and into or and or into and. Each part of the group also gets its own not. The two rules are:

not (a and b)   is the same as   (not a) or (not b)
not (a or b)    is the same as   (not a) and (not b)

In words: the not of "a and b" is "not a or not b". The not of "a or b" is "not a and not b". The letters a and b stand for any conditions, such as age >= 18 or has_ticket.

Checking the rules with a truth table

A truth table lists every possible combination of the true and false inputs, then shows the result for each. For two conditions there are four rows. You can check the two rules with a small program that prints the table. The function product from the itertools module gives every pair of values from a list.

Output:

a      b      | not (a and b)  not a or not b | same?
True   True   | False          False         | True
True   False  | True           True          | True
False  True   | True           True          | True
False  False  | True           True          | True
 
a      b      | not (a or b)   not a and not b | same?
True   True   | False          False         | True
True   False  | False          False         | True
False  True   | False          False         | True
False  False  | True           True          | True

Every row in the last column says True, so both rules hold for all four combinations. The left == right check compares the two results in each row. A rewrite that holds for every row is safe to use, because it gives the same answer for every input.

Python writes the boolean values as True and False, with a capital letter. The str(...) calls turn each value into text so that the columns line up.

First example: rewriting an entry check

Suppose a club lets people in when they are 18 or older and have a ticket. The check that turns someone away is "not (adult and has a ticket)". Here is that rule in the first form, with a short function that prints the decision.

Output:

Turned away: age 17, ticket True
Turned away: age 17, ticket True
Turned away: age 17, ticket False
Turned away: age 17, ticket False
Let in
Let in
Turned away: age 18, ticket False
Turned away: age 18, ticket False
Let in
Let in
Turned away: age 30, ticket False
Turned away: age 30, ticket False

Each pair of lines is the same, so the two versions agree for all six inputs. The rewrite has two steps, and you can use them on any condition of this shape:

1. Write the condition as the not in front of a group. Here it is not (age >= 18 and has_ticket).
2. Apply the rule. The not goes onto each part and the and becomes or. The part age >= 18 gets its negation, so not (age >= 18) becomes age < 18. The part has_ticket becomes not has_ticket. The result is age < 18 or not has_ticket.

The rewritten form reads closer to the rule as a person would state it. "Turned away if under 18, or if there is no ticket" is the sentence that the code now says.

Second example: a long shipping rule

The next rule is longer. An order is blocked from shipping when any of these is true: it is not paid, it was cancelled, it is not in stock, or the address is not valid. In code, the blocked check is not (paid and not cancelled and in_stock and address_valid). The first version below writes that check directly. The second gives the good-case rule a name first, so that the if reads as one idea. The third applies De Morgan's rule to every part.

The function product([True, False], repeat=4) gives all 16 combinations of four values. Each combination is a tuple, which is a fixed group of values. The *combo in the loop passes the four values to a function as four separate arguments.

Output:

rows checked: 16
mismatches: 0
paid, not cancelled, in stock, valid address: blocked = False
paid, cancelled, in stock, valid address: blocked = True

With four conditions there are 16 combinations, so the program loops over all of them and checks that the three versions agree. The count of mismatches is 0.

The rewrite is (not paid) or cancelled or (not in_stock) or (not address_valid). Read it as a list of reasons to block: not paid, or cancelled, or not in stock, or a bad address. Each reason is one short piece, and a reader can check each one on its own. This is the main benefit of the rule. A long negated group is hard to scan, but a list of separate reasons joined by or can be read one line at a time.

The middle version is also useful. Naming the good case as ready_to_ship gives the reader a word for the idea, and the last line says "blocked is the opposite of ready".

Use the named version when the rule is needed in more than one place, or when the name makes the code easier to discuss with other people. Use the rewritten version when each reason needs to appear separately, for example to print a different message for each reason.

Flipping comparisons when you negate them

A negated comparison can also be written as the opposite comparison. The not in front of x >= 0 is the same as x < 0, because "not greater than or equal to zero" means "less than zero". For whole numbers (int) this holds for every value.

Output:

int -3: not (n >= 0) is True, n < 0 is True

The table of flips is short:

Flipping < to >= (and <= to >) is correct. Flipping < to <= is not. The mistake is shown in a later section.

For decimal numbers (float), one special value breaks this rule. The value nan means "not a number". The math module gives it as math.nan, and Python produces it from some calculations, such as float("inf") - float("inf"). Every comparison with nan is False, including nan >= 0 and nan < 0. So the negation of nan >= 0 is True, but nan < 0 is False. Rewriting not (score >= 0) as score < 0 changes the answer when score is nan.

Output:

NaN: not (score >= 0) is True
NaN: score < 0 is False
NaN: math.isnan(score) is True

A nan reaches a comparison only when an earlier calculation produced it. When that is possible, keep the not form, or check for it first with math.isnan(score).

Worked example: a password rule with three parts

A password is rejected unless it has at least 8 characters, at least one digit and at least one letter. Put in words, it is rejected when it is too short, or has no digit, or has no letter. The first version below uses not directly. The second writes the rewrite with a not on each part.

Python strings have the methods isdigit() and isalpha(), but they check every character in the string. The password abc1 has a digit, but "abc1".isdigit() is False, because not all of its characters are digits. So the functions below use any(...). The function any gives True when at least one item in a sequence is True. The part inside the brackets, ch.isdigit() for ch in s, is a generator expression. It checks each character in turn.

Output:

sunshine1 rejected: False / False
sunshine rejected: True / True
12345678 rejected: True / True
abc1 rejected: True / True
Quartz2024 rejected: False / False
isdigit on mixed text: False True

The two functions agree on every sample. Look at sunshine. It has 8 characters and a letter, but no digit, so it is rejected. Look at abc1. It has a letter and a digit, but only 4 characters, so it is rejected.

The rewrite puts each reason on its own line in a single return. Each part is a small question with a clear name: is it too short, has no digit, has no letter. The named version keeps the good case in a variable called good. Both are correct. Pick the one that matches how the team talks about the rule.

A double negation

A negation can contain a part that is already negated. Take not (not is_logged_in and is_guest). Treat not is_logged_in as one part, and apply the rule to the outer not. Each part gets a not, and and becomes or. That gives not not is_logged_in or not is_guest. Two not words in a row cancel each other, so not not is_logged_in is the same as is_logged_in. The final form is is_logged_in or not is_guest.

The example below checks all four combinations of the two inputs. The two forms agree in every row.

Output:

double negation rows 4, mismatches 0

When the negated form is clearer

Not every negation needs rewriting. not os.path.exists(path) reads as one clear question, and rewriting it would not help anyone. The rewrite is worth doing when the negated group is long, when a reader has to stop and work out what it means, or when you need the rule in a different form for a test or a comment. If the original reads as a sentence, leave it.

Common mistakes

Negating each part but keeping the operator

This is a common error. A reader sees not (a and b) and writes (not a) and (not b). The operator stayed and, so the rule is wrong. Take the row of the first table where a is True and b is False. The correct value of not (a and b) is True, because a and b is False. The wrong form, (not a) and (not b), is False and True, which is False. The two disagree, so the rewrite is wrong.

The fix is to change and to or at the same time as you add the not words. Check the rewrite by plugging in one row where the two parts differ, as in the example above.

Forgetting the outer negation

Writing not (paid and in_stock) as not paid and not in_stock is the same mistake from another angle. Apply the rule in one step: the outer not goes away, and and becomes or. The result is not paid or not in_stock.

Dropping the parentheses

In Python, not applies only to the next item unless parentheses say otherwise. So not paid and in_stock means (not paid) and in_stock, which is a different rule from not (paid and in_stock). The next program prints both with the same values.

Output:

not (paid and in_stock): True
not paid and in_stock:   False
not paid or not in_stock: True

The first and third lines agree, because they are the two sides of the first De Morgan rule. The second line is a different test. Keep the parentheses whenever the not is meant to cover a group.

Expecting and and or to return only True or False

Python's and and or return one of their two values, not always a boolean. Most of the time the values are booleans, so this does not show. When a value is text or a number, the result can be that value.

Output:

guest
True
yes
False
0

The empty string "" counts as false, so name or "guest" gives "guest". The function not always gives True or False. The value cancelled or False gives "yes", which is not a boolean, and the code that uses it may behave in a way you did not intend. In a rewrite, convert values to booleans with bool(...) when the rule needs True or False.

Flipping the wrong operator

When you flip a comparison, < becomes >= and > becomes <=. A common error is to write < where <= belongs. Take not (x >= 0). Its correct flip is x < 0. The wrong flip x <= 0 gives a different answer when x is 0:

Output:

not (x >= 0) with x = 0: False
x <= 0 with x = 0: True

The two results differ, so the flip to <= is wrong. The flip of >= is <, with no equals sign.

Not checking the rewrite

Beginners often rewrite a condition, run the program once, and trust the result. A single run tests one input, and the rewrite may still be wrong for other inputs. Loop over every combination for the boolean parts, as the truth table program does. For numbers, pick a few values on the boundary, such as the smallest and largest allowed, plus one value on each side of the boundary. For the >= case, that means 0 itself, which is the value that catches the <= mistake above.

Confusing the rewrite with a shorter rule

A De Morgan rewrite does not always make the code shorter. not (a and b) has one not, and (not a) or (not b) has two. The goal is a form that reads well and matches the rule as people state it. A longer form is fine if it is clearer.

Practice

Exercise 1

Rewrite this condition without a not in front of the group:

if not (9 <= hour < 17):
    print("Closed")

Show the answer

if hour < 9 or hour >= 17:
    print("Closed")

The not moves onto each part, and and becomes or. The part 9 <= hour becomes hour < 9, and the part hour < 17 becomes hour >= 17. The result is "closed before nine or at five or later", which is what the first form means.

Exercise 2

Rewrite not (is_admin or is_owner) using De Morgan's rule. Then say in one sentence what the new form means.

Show the answer

not is_admin and not is_owner

Read it as "not an admin and not an owner". A user passes this check only when neither flag is set.

Exercise 3

Write a function can_edit(logged_in, is_owner, locked) that returns True when the user may edit a document. The rule is: the user must be logged in, and must be the owner or the document must not be locked. Write the rewritten version as your first function and the negated form as a second function. Check that the two functions agree for all 8 combinations of the three inputs.

Show the answer

def can_edit_first(logged_in, is_owner, locked):
    return logged_in and (is_owner or not locked)
 
def can_edit_negated(logged_in, is_owner, locked):
    return not (not logged_in or (not is_owner and locked))

Both functions return True in the same cases. The second function negates the "blocked" rule. The blocked rule says: not logged in, or (not the owner and locked). De Morgan's rules turn that into the first form. A loop over all 8 combinations shows that the two functions agree in every row. Exactly 3 of the 8 combinations give True: logged in and the owner (locked or not), and logged in, not the owner, and not locked.

Exercise 4

The condition below is written in a hard-to-read form. Rewrite it with De Morgan's rules so that not is applied to each part and no not appears in front of a group. Then say why the new form is equal to the old one.

if not (age >= 16 and (has_parent or has_licence)):
    print("Cannot drive alone")

Show the answer

if age < 16 or (not has_parent and not has_licence):
    print("Cannot drive alone")

The outer not turns and into or, so the first part becomes age < 16. The inner group (has_parent or has_licence) is negated as a group, so its or becomes and and each part gets a not. The result says: under 16, or neither a parent nor a licence.

Exercise 5

A student writes not (x > 10) and wants a flipped form. Is x < 10 or x <= 10 correct? Test your answer with x = 10.

Show the answer

The correct flip is x <= 10. The negation of "greater than 10" is "less than or equal to 10". For x = 10, not (x > 10) is True, and x <= 10 is True. The form x < 10 is wrong, because it gives False for x = 10.

Summary

• not (a and b) is the same as (not a) or (not b), and not (a or b) is the same as (not a) and (not b).
• When you move a not through a group, change and to or and or to and at the same time.
• A negated comparison can be written as the opposite comparison, such as not (x >= 0) as x < 0, for whole numbers.
• Check a rewrite by testing every combination of the inputs, not only the one you have in mind.
• A long rule is often easier to read as a list of separate reasons joined by or.
• With decimal numbers, nan makes a flipped comparison give a different answer, so keep the not form when nan is possible.