Simplifying expressions

A method for simplifying by algebra, worked exam-style examples, and checking the result.

A8.5Boolean algebra and logic circuitsA level25 min

You now have the identities, the laws and De Morgan. This lesson puts them to work. A simpler expression means a circuit with fewer gates, which is cheaper, uses less power and is faster, because each gate adds a small delay. In a program it means a condition someone can read. Exam questions on this are worth several marks, and most of those marks are for showing each step.

What "simpler" means

An expression is simpler when it has fewer terms and fewer literals (a literal is a letter, with or without a NOT). (A ∧ B) ∨ (A ∧ ¬B) has two terms and four literals. It simplifies to A: one literal, no gates at all.

A method

There is no single algorithm for algebraic simplification, but this order of attack works for almost every exam question:

1. Remove NOTs over brackets with De Morgan, and cancel double negatives straight away.
2. Multiply out brackets with distribution, so you have terms joined by OR.
3. Look for pairs of terms that differ only in one letter being inverted: (X ∧ Y) ∨ (X ∧ ¬Y) = X ∧ (Y ∨ ¬Y) = X.
4. Absorb: X ∨ (X ∧ Y) = X, and X ∨ (¬X ∧ Y) = X ∨ Y.
5. Tidy up: remove repeated terms (X ∨ X = X), and factor out a shared letter if it saves gates.
6. Check the answer with a few rows of the truth table, or all of them.

Worked examples

Example 1. Simplify (A ∨ B) ∧ (A ∨ ¬B).

Example 2. Simplify ¬(A ∨ B) ∨ (¬A ∧ B).

A two-input NOR, an AND, a NOT and an OR have become one NOT gate.

Example 3, in AQA notation. Simplify A · B + A · B̅ + A̅ · B.

Steps 5 to 7 prove X + X̅ · Y = X + Y. Once you know that result, you may quote it in one step.

Example 4. Simplify ¬(A ∧ B) ∨ (A ∧ ¬B).

The answer is ¬A ∨ ¬B, which is ¬(A ∧ B) again by De Morgan: the extra term added nothing, so the whole expression is one NAND gate.

Checking each step by machine

A computer cannot always find the simplest form for you, but it can check that every line of your working is still the same function. One wrong step is found at once:

def same(f, g):
    return all(f(a, b) == g(a, b) for a in [0, 1] for b in [0, 1])

NOT = lambda x: 1 - x
steps = [
    ("start",        lambda a, b: NOT(a & b) | (a & NOT(b))),
    ("De Morgan",    lambda a, b: NOT(a) | NOT(b) | (a & NOT(b))),
    ("absorption",   lambda a, b: NOT(a) | NOT(b)),
    ("wrong step",   lambda a, b: NOT(a) & NOT(b)),
]
for i in range(1, len(steps)):
    name, f = steps[i]
    ok = same(steps[i - 1][1], f)
    print(f"step {i} ({name}):", "still the same function" if ok else "CHANGED THE FUNCTION")

Run this in the simulator

The last step makes the most common error in the topic: swapping OR for AND without the bar over the whole that De Morgan needs.

Simplifying a robot's condition

A robot's "safe to reverse" rule was written as rules were added over time:

safe = (clear_behind and not hit) or (clear_behind and hit) or (not clear_behind and False)

The first two terms differ only in hit, so they combine to clear_behind. The last term is AND with 0, which is 0, and OR with 0 changes nothing. So safe = clear_behind. Three terms, and a sensor reading that made no difference, have gone.

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

forward(40, distance=10)
clear_behind = True                 # the robot came this way, so nothing is behind it
hit = bumped()
long_rule = (clear_behind and not hit) or (clear_behind and hit) or (not clear_behind and False)
short_rule = clear_behind
print("long rule:", long_rule, " short rule:", short_rule)
if short_rule:
    backward(40, distance=10)

Run this in the simulator

Task: simplify, then prove it

The function original(a, b, c) computes Q = ¬(A ∨ ¬B) ∨ (A ∧ B) ∨ (A ∧ ¬B ∧ C). Its inputs are bits (0 or 1) and it returns 0 or 1.

Simplify Q on paper, then write simplified(a, b, c), taking and returning the same, as a single return line that uses at most two of and, or and not in total. It may not call original or use the bitwise operators &, |, ^ or ~.

Print eight lines, one per row in binary order (A outermost, then B, then C), in exactly this form, with every value 0 or 1:

A=0 B=1 C=0 original=1 simplified=1

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

def original(a, b, c):
    return int((not (a or not b)) or (a and b) or (a and not b and c))

def simplified(a, b, c):
    return 0

Challenges

1. Simplify (A ∧ B ∧ C) ∨ (A ∧ B ∧ ¬C) ∨ (A ∧ ¬B) by algebra. Check it with same, extended to three inputs.
2. How many two-input gates does Q need as written, and how many after simplifying? Count a NOT as a gate.
3. Write the working for the task as a steps list and check every step by machine.