01Overview
In 1854 Boole did something that looked odd at the time: he wrote true and false as 1 and 0, and mapped and, or and not onto multiplication, addition and complement. Reasoning could then be computed like an equation. For a long while the algebra was treated as an elegant toy — beautiful, apparently useless.
In 1937 a 21-year-old Shannon showed in his master’s thesis A Symbolic Analysis of Relay and Switching Circuits that a circuit’s open and closed contacts are isomorphic to 1 and 0: series is and, parallel is or, a normally-closed contact is not. Designing a circuit became simplifying an expression. Often called one of the most important master’s theses of the century, it turned digital design from craft into mathematics.
The simplification methods are still in use: write the truth table, read off the canonical sum of products, then reduce it with a Karnaugh map or Quine–McCluskey. Modern synthesis tools do the same, only the variable count grows from four to millions. And “one NAND gate suffices to express any Boolean function” is exactly why a whole computer can be built from NAND.
02History
- 1854
Boole, The Laws of Thought
Described propositional logic in algebra: truth values 0/1, with and, or, not as multiply, add, complement.
- 1937
Shannon's master's thesis
Proves switching circuits are isomorphic to Boolean algebra: circuit design gains a mathematical tool.
- 1952
Quine–McCluskey algorithm
A tabular method for minimal sum-of-products, implementable as a program.
- 1953
Karnaugh maps
Adjacent minterms in a grid make hand simplification visual.
- 1970
Logic synthesis tools appear
Simplification moves from paper into programs, and scale takes off.
03Core concepts
Truth table
Enumerates every input combination; the plainest representation of a Boolean function and the standard test for equivalence.
Canonical sum of products
One minterm per input combination that outputs 1, ORed together; every Boolean function can be written this way.
Karnaugh map
Puts adjacent minterms in adjacent cells; the bigger the group, the fewer the terms — the standard hand method.
De Morgan’s laws
¬(A∧B) = ¬A∨¬B; this is why NAND alone can build every gate.
Functional completeness
NAND (or NOR) alone expresses any Boolean function — the starting point of nand2tetris.
04Hands-on
Do it once — it beats reading it ten times
Reduce a four-variable truth table to a minimal sum of products: draw the Karnaugh map, check it with Quine–McCluskey, then build it from Nand gates and run the tests
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Truth table"?
Enumerates every input combination; the plainest representation of a Boolean function and the standard test for equivalence.
Can you explain "Canonical sum of products"?
One minterm per input combination that outputs 1, ORed together; every Boolean function can be written this way.
Can you explain "Karnaugh map"?
Puts adjacent minterms in adjacent cells; the bigger the group, the fewer the terms — the standard hand method.
Can you explain "De Morgan’s laws"?
¬(A∧B) = ¬A∨¬B; this is why NAND alone can build every gate.
Can you explain "Functional completeness"?
NAND (or NOR) alone expresses any Boolean function — the starting point of nand2tetris.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
George Boole
1815 – 1864
Turned logic into algebra; Boolean algebra carries his name.
Claude Shannon
1916 – 2001
Proved in 1937 that switching circuits are isomorphic to Boolean algebra.
Maurice Karnaugh
1924 – 2022
Invented the Karnaugh map, making simplification pencil-and-paper work.
07Further reading
- An Investigation of the Laws of Thought
- A Symbolic Analysis of Relay and Switching Circuits
- Discrete Mathematics and Its Applications