Boolean algebra

In 1854 the English mathematician George Boole published an algebra of logic in which variables stand for true or false and are combined with AND, OR and NOT. For eighty years it was a branch of philosophy. Then in 1938 Claude Shannon, a master's student at MIT, showed that Boole's algebra describes exactly how networks of relay switches behave, and digital design was born. Boolean algebra lets a designer write down what a circuit must do as an expression, transform the expression into a simpler or faster equivalent, and prove that two circuits do the same thing. This lesson covers the operations, the truth table, the laws and theorems, and the canonical sum-of-products and product-of-sums forms that connect a specification to a circuit.

Variables and operations

A Boolean variable has one of two values, 0 or 1. There are three basic operations. NOT, or complement, inverts a value: the complement of A is written Ā or A′, and it is 1 when A is 0. AND gives 1 only when all its inputs are 1; it is written as a product, A·B or simply AB. OR gives 1 when at least one input is 1; it is written as a sum, A + B. The plus sign does not mean arithmetic addition here: in Boolean algebra 1 + 1 = 1.

When operations are combined, NOT has the highest precedence, then AND, then OR, just as in ordinary algebra where multiplication comes before addition. So A + BC̄ means A OR (B AND (NOT C)). Parentheses override precedence when needed. A bar over a whole expression complements the whole expression after it has been evaluated.

Truth tables

A Boolean function of n variables can be described completely by a truth table that lists the output for every one of the 2ⁿ input combinations. The rows are normally written in binary counting order, so a function of three variables has eight rows from 000 to 111. The truth table is the most basic and least ambiguous specification of combinational logic: any two expressions or circuits with the same truth table are equivalent, however different they look.

Amara's first task on the pedestrian crossing is the walk-request logic. The controller should register a walk request (W = 1) when the pedestrian button P is pressed, but only if the system is not in maintenance mode (M = 0), or when the remote test input T from the traffic center is active, regardless of the button. Writing the behavior as a truth table makes it exact.

Reading the rows where W = 1 gives the function directly, and the words of the specification give the same thing as an expression: W = PM̄ + T. Checking the expression against all eight rows confirms it. For small functions, this check is the simplest proof of correctness, and Python can do it automatically for larger ones.

Postulates and basic laws

Boolean algebra rests on a few postulates, from which every other law follows. Each law comes in a pair: the dual of a law is obtained by swapping AND with OR and 0 with 1, and the dual of a true law is always true. This principle of duality halves the number of laws to remember.

Most laws look like ordinary algebra, but three do not. A + A = A and A + 1 = 1 have no counterpart in arithmetic, and the second distributive law, A + BC = (A + B)(A + C), is false for numbers but true for Booleans. Each can be proved by perfect induction: check all combinations of the variables in a truth table. For A + BC = (A + B)(A + C), the eight rows of A, B and C give identical columns on both sides.

De Morgan's theorems

The two most useful theorems in digital design were stated by Augustus De Morgan, a contemporary of Boole. They say how to complement an AND or an OR: the complement of a product is the sum of the complements, and the complement of a sum is the product of the complements.

The theorems extend to any number of variables, and they give a mechanical rule for complementing any expression: change every AND to OR and every OR to AND, and complement every variable, keeping the original grouping. De Morgan's theorems are what make NAND and NOR gates universal (lesson 4), and they let a designer move inversion bubbles around a circuit to suit the gates available.

Consensus and other theorems

The consensus theorem removes a redundant term. In XY + X̄Z + YZ, the term YZ is the consensus of the first two terms, formed from the variables left after removing X and X̄, and it adds nothing: whenever YZ = 1, either XY or X̄Z is already 1. So XY + X̄Z + YZ = XY + X̄Z. Its dual is (X + Y)(X̄ + Z)(Y + Z) = (X + Y)(X̄ + Z). Interestingly, lesson 11 shows that the redundant consensus term is sometimes deliberately kept in a circuit to remove a timing glitch called a hazard.

Shannon's expansion theorem splits any function around one variable: F = X·F(X = 1) + X̄·F(X = 0). The two restricted functions, called cofactors, have one fewer variable. Shannon expansion is the basis of the multiplexer implementation of logic (lesson 6), of the binary decision diagrams that verification tools use, and of the lookup tables inside programmable chips (lesson 12).

Simplifying with algebra

A simpler expression usually means fewer gates, fewer inputs per gate, less power and often more speed. Algebraic simplification applies the laws step by step until no law makes the expression smaller. It requires some practice and judgment, which is why lesson 5 introduces Karnaugh maps as a more systematic method for up to four or five variables, and why software tools are used for large functions.

Minterms and the sum of products

A minterm is a product term that contains every variable exactly once, complemented or not, and is 1 for exactly one row of the truth table. For three variables A, B and C, the minterm for row 101 is AB̄C. Minterms are numbered by the row they represent, so AB̄C is m₅. Any function can be written as the OR of the minterms for the rows where it is 1. This is the canonical sum of products (SOP), often written compactly with the Σ notation.

The canonical form is long but completely mechanical, and it maps straight onto a two-level circuit: one AND gate per minterm feeding one OR gate. Simplification then merges minterms that differ in one variable, using XY + XȲ = X. The five minterms of W shrink to PM̄ + T, two terms instead of five.

Maxterms and the product of sums

A maxterm is a sum term containing every variable once, and it is 0 for exactly one row. The maxterm for row 010 is A + B̄ + C: each variable appears complemented where the row has a 1. Any function can also be written as the AND of the maxterms for the rows where it is 0, the canonical product of sums (POS), written with Π notation. The minterm list and the maxterm list of a function are complementary: together they cover every row exactly once.

Which form is better depends on the function. If a function is 1 for only a few rows, SOP is shorter; if it is 0 for only a few rows, POS is shorter. Simplified POS for W is (M̄ + T)(P + T), which expands back to PM̄ + T. Both describe the same truth table and both are correct.

# Build a truth table and check that several expressions are the same function
from itertools import product

exprs = {
    "canonical SOP": lambda P, M, T: (not P and not M and T) or (not P and M and T) or (P and not M and not T)
                                      or (P and not M and T) or (P and M and T),
    "simplified SOP": lambda P, M, T: (P and not M) or T,
    "simplified POS": lambda P, M, T: ((not M) or T) and (P or T),
}
print("P M T | " + " | ".join(exprs))
columns = {name: [] for name in exprs}
for P, M, T in product((0, 1), repeat=3):
    row = [int(bool(f(P, M, T))) for f in exprs.values()]
    for name, v in zip(exprs, row):
        columns[name].append(v)
    print(f"{P} {M} {T} | " + " | ".join(f"{v:^{len(n)}}" for v, n in zip(row, exprs)))
minterms = [i for i, v in enumerate(columns["canonical SOP"]) if v]
print("minterms:", minterms, " all equal:", len({tuple(c) for c in columns.values()}) == 1)

P M T | canonical SOP | simplified SOP | simplified POS
0 0 0 |       0       |       0        |       0       
0 0 1 |       1       |       1        |       1       
0 1 0 |       0       |       0        |       0       
0 1 1 |       1       |       1        |       1       
1 0 0 |       1       |       1        |       1       
1 0 1 |       1       |       1        |       1       
1 1 0 |       0       |       0        |       0       
1 1 1 |       1       |       1        |       1       
minterms: [1, 3, 4, 5, 7]  all equal: True

This brute-force check is how Amara confirms each simplification before drawing it. It costs nothing for a few variables. For many variables, 2ⁿ rows become too many and verification tools switch to cleverer methods, but the principle, that equal truth tables mean equal functions, stays the same.

Other two-input functions

With two inputs there are 2⁴ = 16 possible Boolean functions, because each of the four rows of the truth table can be 0 or 1. Besides AND and OR, the important ones are NAND (NOT-AND), NOR (NOT-OR), XOR (exclusive OR) and XNOR (equivalence). XOR is 1 when its inputs differ, A ⊕ B = AB̄ + ĀB. It is the heart of adders, comparators, parity and Gray code circuits. XNOR is 1 when the inputs are equal, which makes it an equality detector.

XOR has useful algebraic properties: it is commutative and associative, A ⊕ 0 = A, A ⊕ 1 = Ā and A ⊕ A = 0. The last property means XORing a value with the same key twice gives back the original, which is used in simple encryption, in RAID storage parity and in swapping registers without a temporary location.