De Morgan's laws

Breaking the bar and changing the sign, NAND and NOR, and rewriting the robot's loop condition.

A8.4Boolean algebra and logic circuitsA level20 min

At GCSE, challenge 3 of lesson F9.2 asked you to show that NOT (A AND B) is always the same as (NOT A) OR (NOT B). That is one of De Morgan's laws, named after the nineteenth century mathematician Augustus De Morgan. They are the most useful rules in Boolean algebra, because they are the only ones that let you move a NOT through a bracket, and almost every simplification question needs them.

The two laws

¬(A ∧ B) = ¬A ∨ ¬B

¬(A ∨ B) = ¬A ∧ ¬B

In words: to take a NOT inside a bracket, invert every term inside and swap AND for OR (or OR for AND).

The columns match in pairs, on every row, so the laws hold.

They also make sense in words. "It is not true that the robot is both close and bumped" means at least one of them is false: "not close or not bumped". "It is not true that the robot is close or bumped" means neither is true: "not close and not bumped".

Break the bar, change the sign

In AQA notation, where NOT is a bar, the rule has a well-known memory aid: break the bar, change the sign. A long bar over A · B breaks into two short bars, one over A and one over B, and the dot becomes a plus: A̅ + B̅. A long bar over A + B breaks into A̅ · B̅.

Going the other way, you can join bars: A̅ · B̅ becomes a long bar over A + B.

This is the most common source of lost marks in this topic. A̅ · B̅ (two short bars) is NOR. A long bar over A · B is NAND. They are different functions: look at row 01 of the table.

More than two inputs, and nested brackets

The laws extend to any number of terms, because of association:

¬(A ∧ B ∧ C) = ¬A ∨ ¬B ∨ ¬C and ¬(A ∨ B ∨ C) = ¬A ∧ ¬B ∧ ¬C

When a bracket contains a NOT of its own, apply the law and then use double negation:

¬(A ∨ ¬B) = ¬A ∧ ¬¬B = ¬A ∧ B

With brackets inside brackets, work from the outside in, one law per line:

def check(name, f, g):
    ok = True
    for a in [0, 1]:
        for b in [0, 1]:
            for c in [0, 1]:
                if f(a, b, c) != g(a, b, c):
                    ok = False
    print(name, "holds" if ok else "FAILS")

NOT = lambda x: 1 - x
check("NOT(A AND B AND C) = NOT A OR NOT B OR NOT C",
      lambda a, b, c: NOT(a & b & c), lambda a, b, c: NOT(a) | NOT(b) | NOT(c))
check("NOT(NOT A AND (B OR C)) = A OR (NOT B AND NOT C)",
      lambda a, b, c: NOT(NOT(a) & (b | c)), lambda a, b, c: a | (NOT(b) & NOT(c)))
check("a common mistake: NOT(A AND B) = NOT A AND NOT B",
      lambda a, b, c: NOT(a & b), lambda a, b, c: NOT(a) & NOT(b))

Run this in the simulator

Why NAND and NOR are universal

De Morgan explains the constructions in lesson A8.1. The first law says NAND is the same as OR with both inputs inverted:

A NAND B = ¬(A ∧ B) = ¬A ∨ ¬B

So feed NAND with ¬A and ¬B, and double negation gives ¬¬A ∨ ¬¬B = A ∨ B. That is OR built from NAND gates. In a diagram, a NAND gate can equally be drawn as an OR gate with bubbles on its inputs; the two symbols mean the same thing.

De Morgan in your programs

Conditions in code follow the same laws, and De Morgan is how you rewrite a condition that is hard to read. A robot should keep driving while it is not the case that it is close or has bumped:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

while not (distance() < 20 or bumped()):
    forward(50)
    wait(0.1)
stop()
print("stopped", distance(), "cm from the wall")

Run this in the simulator

By the second law, not (X or Y) is not X and not Y, and not (distance() < 20) is distance() >= 20. So the loop can be written as while distance() >= 20 and not bumped():, which reads as a list of conditions for carrying on.

A related bug: not a or b means (not a) or b, because NOT binds more tightly than OR. If you meant "not (a or b)", you need the brackets, or De Morgan.

Task: De Morgan at the wall

The robot starts facing a wall. First print four check lines, one for each combination of close and hit (each 0 or 1, close in the outer loop), in exactly this form:

close=0 hit=1 original=0 rewritten=0

where original is NOT (close OR hit) and rewritten is your De Morgan version, (NOT close) AND (NOT hit), each worked out as 0 or 1 by a function of your own.

Then drive the robot towards the wall and stop in the band before it. The loop must be a while loop whose condition reads distance(), stops when the distance is under 20 cm or bumped() is true, and is written using De Morgan so that it joins its two parts with and not, with no not in front of a bracket.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

while not (distance() < 20 or bumped()):
    forward(50)
    wait(0.1)
stop()

Challenges

1. Rewrite if not (battery() > 20 and distance() > 30): without a not in front of the bracket.
2. Simplify ¬(¬A ∨ ¬B) in two lines. Which single gate is left?
3. Draw NOR as an AND gate with bubbles. Build NOT, OR and AND from NOR functions alone, and prove each by printing its truth table.