Boolean algebra

A simpler expression means a circuit with fewer gates: cheaper, smaller, faster and using less power. Boolean algebra gives the rules for simplifying. Variables are 0 or 1, + is OR, · is AND (often left out: AB) and ' is NOT.

The laws

The second distributive law has no twin in ordinary algebra: try it with A = 1.

De Morgan's laws say: to complement an expression, swap AND with OR and complement each variable. "Not (rain or snow)" is "not rain and not snow".

Simplifying by hand

F = A'B + AB + AB'

• Group the first two: A'B + AB = (A' + A)B = 1 · B = B.
• So F = B + AB'. By the distributive law (A + BC form): B + AB' = (B + A)(B + B') = (A + B) · 1.
• F = A + B: three ANDs and an OR became one OR gate.

Proof by truth table

Algebra can go wrong. A truth table cannot: two expressions are equal exactly when they agree on every input. With n variables there are 2ⁿ cases, few enough to check by machine.

from itertools import product

def same(f, g, n):
    for values in product([0, 1], repeat=n):
        if f(*values) != g(*values):
            return "differ at " + str(values)
    return "equal for all " + str(2 ** n) + " inputs"

# De Morgan: (A + B)' = A'B'
print("De Morgan:", same(lambda a, b: 1 - (a | b), lambda a, b: (1 - a) & (1 - b), 2))
# A wrong 'law': (AB)' = A'B'
print("Wrong law:", same(lambda a, b: 1 - (a & b), lambda a, b: (1 - a) & (1 - b), 2))

from itertools import product

for a, b in product([0, 1], repeat=2):
    f = ((1 - a) & b) | (a & b) | (a & (1 - b))     # A'B + AB + AB'
    print(a, b, "F =", f, " A + B =", a | b)

The next lessons give a systematic way to simplify: canonical forms and Karnaugh maps.

Mark lesson complete