Boolean identities and laws

The identities, commutation, association, distribution, double negation and absorption, proved by truth table.

A8.3Boolean algebra and logic circuitsA level20 min

Ordinary algebra has rules you use without thinking: a + b = b + a, and a × (b + c) = ab + ac. Boolean algebra has rules too, some the same as ordinary algebra and some surprisingly different. With them you can rewrite an expression into a simpler one that is guaranteed to have the same truth table, which means a circuit with fewer gates, or a program condition that is easier to read.

The identities

Each identity can be checked by trying A = 0 and A = 1. OCR notation is on the left, AQA on the right.

Two of these are where Boolean algebra parts company with ordinary arithmetic. A + 1 = 1, whereas in arithmetic A + 1 is one more than A. And A · A = A, not A².

The laws

These are the laws your specification names. Each one comes in an AND version and an OR version.

Commutation: the order of the inputs does not matter. A ∧ B = B ∧ A and A ∨ B = B ∨ A

Association: when the operators are all the same, the brackets do not matter. (A ∧ B) ∧ C = A ∧ (B ∧ C) and (A ∨ B) ∨ C = A ∨ (B ∨ C)

Distribution: AND distributes over OR, like multiplying out brackets. A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)

and, unlike ordinary algebra, OR also distributes over AND: A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)

Double negation: ¬¬A = A.

Absorption: a term that already contains A adds nothing when combined with A. A ∨ (A ∧ B) = A and A ∧ (A ∨ B) = A

Absorption is not a new rule; it follows from the others. Here is the proof of the OR form, one law per step:

In words: if A is 1 the whole thing is 1; if A is 0 then A ∧ B is 0 too; so the result is always just A.

A result that follows from these laws and is used constantly is:

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

"A, or else not A but B" is simply "A or B".

Two ways to prove an equation

An exam may ask you to show that two expressions are equal. There are two ways.

1. Algebra: rewrite one side into the other, one law per line, naming each law. This is what most simplification questions want.
2. Truth tables: work out both expressions for every row. If every row matches, they are equal; if one row differs, they are not. This is proof by exhaustion: with n inputs there are only 2ⁿ cases, so you can check them all.

A computer is very good at the second way:

def show(name, f, g):
    rows = []
    for a in [0, 1]:
        for b in [0, 1]:
            rows.append((a, b, f(a, b), g(a, b)))
    same = all(left == right for _, _, left, right in rows)
    print(name, "same on every row" if same else "DIFFERENT")
    for a, b, left, right in rows:
        print("  ", a, b, left, right)

show("A OR (A AND B) vs A", lambda a, b: a | (a & b), lambda a, b: a)
show("A OR (NOT A AND B) vs A OR B", lambda a, b: a | ((1 - a) & b), lambda a, b: a | b)
show("A AND B vs A OR B", lambda a, b: a & b, lambda a, b: a | b)

Run this in the simulator

Laws in robot code

The laws apply to conditions in programs as well as circuits. A student writes:

if (close and moving) or (close and turning):

Distribution takes out the shared close: close and (moving or turning). The condition tests close once rather than twice, and the intention is clearer. Absorption catches a common redundancy: if bumped or (bumped and fast): is just if bumped:.

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

drive(40, 0)
for step in range(30):
    close = distance() < 30
    moving = True
    turning = False
    if close and (moving or turning):       # was (close and moving) or (close and turning)
        stop()
        print("stopped at", distance(), "cm")
        break
    wait(0.1)

Run this in the simulator

Task: prove it by brute force

Write equivalent(f, g). Its inputs f and g are functions of three bits, f(a, b, c), each returning 0 or 1. It tries all eight rows in binary order (a, then b, then c, each 0 then 1) and returns the first row where f and g give different results, as a tuple (a, b, c), or None if they agree on every row.

Then, for each (name, f, g) in the list laws, in order, print one line: <name>: equivalent if they agree, or <name>: not equivalent at A=<a> B=<b> C=<c> using the row equivalent returned. That makes six lines.

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

laws = [
    ("distribution", lambda a, b, c: a & (b | c), lambda a, b, c: (a & b) | (a & c)),
    ("absorption", lambda a, b, c: a | (a & b), lambda a, b, c: a),
    ("association", lambda a, b, c: (a | b) | c, lambda a, b, c: a | (b | c)),
    ("OR over AND", lambda a, b, c: a | (b & c), lambda a, b, c: (a | b) & (a | c)),
    ("false friend", lambda a, b, c: a | (b & c), lambda a, b, c: (a | b) & c),
    ("half absorbed", lambda a, b, c: a & (a | b), lambda a, b, c: a | b),
]

def equivalent(f, g):
    return None

Challenges

1. The "false friend" looks like association but mixes two operators. Explain in one sentence why the brackets matter there.
2. Prove A ∧ (A ∨ B) = A by algebra, naming the law at each step.
3. Add a check that f and g only ever return 0 or 1, and use it to catch a function written with ~.