The Thinking Machine Chronicles #0002: Electricity Learns to Think: Shannon's Boolean Algebra for Circuits

Era 1 · The Foundations (1936–1955) An engineer reads a mathematician. A century of abstract algebra becomes silicon.

The World in 1937

Nineteen thirty-seven was a year of creeping catastrophe. Japan invaded China in July; the Hindenburg had burned in May; Picasso completed Guernica in response to the bombing of a Basque town. In the United States, the New Deal was reshaping the economy, and AT&T's Bell Labs was at the height of its influence over the world's telecommunications infrastructure. At MIT, a 21-year-old master's student named Claude Shannon was working in the differential analyser lab, a room-sized mechanical computer made of gears, shafts, and spinning discs, and noticing that something was deeply inefficient about the way relay switching circuits were designed. Engineers were building them by trial and error, intuition, and costly physical prototyping. Shannon believed there had to be a better way. He was right, and the tool he reached for had been sitting unused in a mathematics library since 1854.

The Tool: Boolean Algebra

George Boole published An Investigation of the Laws of Thought in 1854. He showed that logical reasoning, the classical Aristotelian syllogism, could be reduced to algebraic manipulation of symbols constrained to one of two values: true and false (or equivalently, 1 and 0). Boole's algebra had three fundamental operations:

• Conjunction (logical AND): $A \cdot B = 1$ iff both $A = 1$ and $B = 1$
• Disjunction (logical OR): $A + B = 1$ iff at least one of $A, B$ equals 1
• Complement (logical NOT): $\bar{A} = 1 - A$

Boole's algebra obeyed a set of elegant laws. For any $A$, $B$, $C \in \{0, 1\}$:

Law	AND form	OR form
Identity	$A \cdot 1 = A$	$A + 0 = A$
Null	$A \cdot 0 = 0$	$A + 1 = 1$
Idempotency	$A \cdot A = A$	$A + A = A$
Complement	$A \cdot \bar{A} = 0$	$A + \bar{A} = 1$
Commutativity	$A \cdot B = B \cdot A$	$A + B = B + A$
Associativity	$(A \cdot B) \cdot C = A \cdot (B \cdot C)$	$(A+B)+C = A+(B+C)$
Distributivity	$A \cdot (B + C) = A \cdot B + A \cdot C$	$A + B \cdot C = (A+B)(A+C)$
De Morgan	$\overline{A \cdot B} = \bar{A} + \bar{B}$	$\overline{A + B} = \bar{A} \cdot \bar{B}$

For eighty years after Boole, this algebra was used almost exclusively by logicians. It was beautiful mathematics. But no one had connected it to anything physical.

Shannon's Key Insight

Shannon's master's thesis, submitted to MIT in November 1937 and published in the Transactions of the American Institute of Electrical Engineers in 1938, established a precise, one-to-one correspondence between Boolean algebra and switching circuits:

Boolean concept	Physical counterpart
Variable $A \in \{0,1\}$	Switch (open = 0, closed = 1)
$A \cdot B$	Two switches in series
$A + B$	Two switches in parallel
$\bar{A}$	Normally-closed relay contact
Boolean expression	Circuit schematic
Algebraic simplification	Fewer relays, less wire, lower cost

Under this correspondence, every relay circuit is a Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, and every Boolean function can be realised as a relay circuit. The mapping was not approximate or metaphorical; it was exact.

This meant that engineers could:

1. Describe a circuit as a Boolean expression.
2. Simplify the expression using algebraic laws.
3. Build the simplified expression: fewer components, lower cost, greater reliability.

Before Shannon, simplifying a relay circuit required physically rewiring the hardware. After Shannon, it required algebraic manipulation on paper.

Truth Tables and Canonical Forms

A Boolean function of $n$ variables is completely specified by its truth table, the $2^n$-row table listing the output for every possible input combination. From a truth table, two canonical forms follow mechanically:

Sum of Products (SOP): Write a product term (minterm) for each row where the output is 1. Each minterm is the product of all $n$ variables, complemented for each input variable that equals 0 in that row. The SOP is the disjunction of all minterms.

For the majority function $\text{maj}(A,B,C) = 1$ iff at least two inputs equal 1:

$A$	$B$	$C$	$f$	Minterm
0	0	0	0	:
0	0	1	0	:
0	1	0	0	:
0	1	1	1	$\bar{A} \cdot B \cdot C$
1	0	0	0	:
1	0	1	1	$A \cdot \bar{B} \cdot C$
1	1	0	1	$A \cdot B \cdot \bar{C}$
1	1	1	1	$A \cdot B \cdot C$

$\text{maj}(A,B,C) = \bar{A}BC + A\bar{B}C + AB\bar{C} + ABC$

Simplifying by applying distributivity and complement laws:

$= AB(\bar{C} + C) + C(A\bar{B} + \bar{A}B) = AB + C(A \oplus B) = AB + BC + AC$

This is the minimum SOP form: three 2-input AND gates feeding a 3-input OR gate, versus the four 3-input AND gates the canonical form required.

The Full Adder: Boolean Algebra Meets Arithmetic

The most important combinational circuit is the full adder, a 3-input, 2-output circuit that adds two bits and a carry-in, producing a sum bit and a carry-out. Cascaded in sequence, full adders form the ripple-carry adder, the simplest integer arithmetic unit, which became the foundation of every CPU's ALU (arithmetic logic unit).

For inputs $A$, $B$, and $C_{in}$:

$S = A \oplus B \oplus C_{in}$

$C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))$

where $\oplus$ denotes XOR ($A \oplus B = A\bar{B} + \bar{A}B$).

The sum is a 3-way XOR: 1 iff an odd number of inputs are 1. The carry is 1 iff at least two inputs are 1, the majority function again. You can verify this against the truth table:

$A$	$B$	$C_{in}$	$S$	$C_{out}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Shannon's Expansion Theorem

Beyond simplification, Shannon's thesis introduced what is now called the Shannon expansion (or cofactor decomposition). For any Boolean function $f$ and any variable $x$:

$f(x,\, x_1, \ldots, x_n) = x \cdot f(1,\, x_1, \ldots, x_n) \;+\; \bar{x} \cdot f(0,\, x_1, \ldots, x_n)$

The two functions $f(1, \ldots)$ and $f(0, \ldots)$ are called the positive and negative cofactors of $f$ with respect to $x$. This expansion is recursive: apply it again to the cofactors, splitting on another variable, and you build a binary tree of sub-functions. Applied exhaustively, this tree is a Binary Decision Diagram (BDD), the data structure at the heart of hardware verification tools used by Intel, ARM, and every chip designer in the world.

When Intel verifies that the Pentium 4 multiplier is correct before taping out a $2 billion chip, it uses BDDs. Shannon's 1937 theorem is what makes that verification computationally tractable.

De Morgan's Laws and NAND Completeness

One of the most practically significant identities in Shannon's framework is De Morgan's theorem, which he systematically applied to circuit transformation:

$\overline{A \cdot B} = \bar{A} + \bar{B} \qquad \overline{A + B} = \bar{A} \cdot \bar{B}$

De Morgan's laws have a remarkable consequence for hardware design: the NAND gate (which computes $\overline{A \cdot B}$) is functionally complete. Every Boolean function, AND, OR, NOT, XOR, and any combination thereof, can be expressed using only NAND gates. Similarly for NOR. This is why early transistor-transistor logic (TTL) integrated circuits were manufactured almost entirely as NAND and NOR gates. Fewer part types, simpler manufacturing, universal capability.

The Code

The Python implementation below models the formal circuit algebra. Each Gate is a composable object that evaluates recursively over a variable assignment, following the same evaluation semantics as Shannon's correspondence.

from typing import Callable, Dict, FrozenSet
import itertools

class Gate:
    """
    A single logic gate: f: {0,1}^n → {0,1}.
    Inputs can be variable names (str), booleans, or other Gates.
    """
    def __init__(self, name: str, fn: Callable[..., bool], *inputs):
        self.name   = name
        self.fn     = fn
        self.inputs = inputs

    def evaluate(self, assignment: Dict[str, bool]) -> bool:
        resolved = [
            inp.evaluate(assignment) if isinstance(inp, Gate)
            else assignment[inp]     if isinstance(inp, str)
            else bool(inp)
            for inp in self.inputs
        ]
        return self.fn(*resolved)

    def variables(self) -> FrozenSet[str]:
        result = set()
        for inp in self.inputs:
            result |= inp.variables() if isinstance(inp, Gate) else {inp} if isinstance(inp, str) else set()
        return frozenset(result)

    def truth_table(self):
        vars_sorted = sorted(self.variables())
        return [
            (dict(zip(vars_sorted, vals)), self.evaluate(dict(zip(vars_sorted, vals))))
            for vals in itertools.product([False, True], repeat=len(vars_sorted))
        ]

# Full adder
def XOR(a, b): return a != b
def AND(*args): return all(args)
def OR(*args):  return any(args)

xor_ab   = Gate("xor_ab", XOR, "A", "B")
sum_gate = Gate("sum",    XOR, xor_ab, "Cin")
and_ab   = Gate("and_ab", AND, "A", "B")
cout     = Gate("cout",   OR, and_ab, Gate("xor_cin", AND, xor_ab, "Cin"))

The full project includes the majority circuit, a 2-bit ripple-carry adder, verification of De Morgan's laws, the Shannon cofactor expansion, and a truth table generator for arbitrary Boolean expressions.

Why It Mattered

Shannon's thesis is, by a fair accounting, the most important master's thesis in the history of science. Claude Shannon was 21 when he wrote it. It did three things that together define the entire digital age:

It gave engineers a mathematical language. Before 1938, circuit design was a craft. After Shannon, it was algebra. Complex circuits could be described, compared, and optimised using pencil and paper before a single component was ordered.

It enabled reliable minimisation. Boolean simplification reduces the number of gates in a circuit, which reduces cost, power consumption, propagation delay, and failure probability. Every chip that has ever been manufactured has been designed using techniques that trace back to Shannon's algebraic framework.

It unified logic and engineering. Boole's abstract logic, designed to capture human reasoning, turned out to be the exact language of physical switching. The bridge between mind and machine was mathematical, and it had been waiting in a library for eighty years. Shannon saw it.

Without Shannon's thesis, there is no digital computer as we know it. Not the vacuum tube machines of the 1940s, not the transistor machines of the 1960s, not the VLSI chips of the 1980s. They all build on this 71-page document written by a graduate student who noticed that relay circuits had something to do with algebra.

What Came Next

The algebraic framework was in place. The next question was whether a physical machine could be built that embodied Turing's universal machine. In 1938, Konrad Zuse, a German civil engineer working in his parents' living room, built the Z1: the world's first programmable, electromechanical computer. That story is next: The Thinking Machine Chronicles #0003: Gears and Logic.

---

References

1. Shannon, C. E. (1938). A Symbolic Analysis of Relay and Switching Circuits. Transactions of the AIEE, 57, 713–723.
2. Boole, G. (1854). An Investigation of the Laws of Thought. Walton and Maberly, London. The source of Boolean algebra; freely available on Project Gutenberg.
3. Rota, G.-C. (1997). The many lives of lattice theory. Notices of the AMS, 44(11), 1440–1445. On the algebraic structure Shannon was drawing on.
4. Shannon, C. E., & Weaver, W. (1949). A Mathematical Theory of Communication. University of Illinois Press. Shannon's later information theory work, which built on the same algebraic foundations.
5. Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. Chapter 4 covers Boolean function minimisation.
6. Bryant, R. E. (1986). Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, 35(8), 677–691. The BDD paper; the direct descendant of Shannon expansion.