Boolean Algebra: The Mathematics That Made Computers Possible

In 1854, the English mathematician George Boole published a book with the ambitious title An Investigation of the Laws of Thought. Boole’s claim was that reasoning itself — the process of drawing logical conclusions from premises — could be formalized as algebra, with the operations of “and”, “or”, and “not” playing roles analogous to multiplication, addition, and negation in ordinary arithmetic.

The book was admired by some philosophers and ignored by most mathematicians. For 80 years, Boolean algebra remained an interesting curiosity. Then in 1937, a 21-year-old MIT graduate student named Claude Shannon noticed something. The “true” and “false” of Boolean algebra mapped exactly to the “on” and “off” of electrical switches. The “and”, “or”, and “not” of Boolean operations mapped exactly to series, parallel, and inverse switch combinations.

This observation — published in Shannon’s master’s thesis, A Symbolic Analysis of Relay and Switching Circuits — turned Boolean algebra from a philosophical curiosity into the mathematical foundation of every electronic device ever built. The chips in your phone, the routers running the internet, the satellites in orbit, all run on extensions of Boole’s 1854 ideas.

This article is about what Boolean algebra is, how it became the language of computing, and why this 170-year-old mathematics still defines how computers compute.

The basics

A Boolean value is either TRUE (often written 1) or FALSE (written 0). That’s it. Just two values.

Three operations combine Boolean values:

NOT (¬, also $\lnot$ or overline): flips a value. NOT TRUE = FALSE; NOT FALSE = TRUE.
AND (∧, also &, ⋅, or just juxtaposition): TRUE only if both inputs are TRUE.
OR (∨, also +): TRUE if at least one input is TRUE.

These can be summarized in truth tables:

These three operations, combined freely, can express any logical function. The phrase “It’s raining AND I have an umbrella OR (it’s not raining AND I’m late)” is a Boolean expression of three variables. Computing whether it’s true is mechanical: look up the truth values, apply AND, OR, and NOT rules.

The axioms

Boolean algebra has a small set of axioms that capture all of its laws. The standard axioms (Huntington’s, 1904) are:

Commutativity: $A \land B = B \land A$ , $A \lor B = B \lor A$ .

Associativity: $(A \land B) \land C = A \land (B \land C)$ .

Distributivity (a Boolean specialty — both directions hold): $A \land (B \lor C) = (A \land B) \lor (A \land C)$ $A \lor (B \land C) = (A \lor B) \land (A \lor C)$

Identity: $A \land 1 = A$ , $A \lor 0 = A$ .

Complement: $A \land \lnot A = 0$ , $A \lor \lnot A = 1$ .

That’s it. From these axioms, all of Boolean algebra follows. Many additional “laws” can be derived:

De Morgan’s laws: $\lnot(A \land B) = \lnot A \lor \lnot B$ , and $\lnot(A \lor B) = \lnot A \land \lnot B$ .

Idempotence: $A \land A = A$ , $A \lor A = A$ . Doing the same operation twice gives the same result.

Absorption: $A \land (A \lor B) = A$ , $A \lor (A \land B) = A$ .

Double negation: $\lnot(\lnot A) = A$ .

These laws are exactly analogous to laws of ordinary algebra, with some differences (e.g. distributivity working both ways in Boolean but not in ordinary algebra).

Shannon’s discovery

In 1937, Claude Shannon was a master’s student at MIT. He noticed that the analysis of telephone-switching circuits could be done using exactly Boolean algebra. The contribution wasn’t subtle — his thesis title was A Symbolic Analysis of Relay and Switching Circuits.

The connection:

An open switch = FALSE = 0.
A closed switch = TRUE = 1.
Two switches in series = AND (both must be closed for current to flow).
Two switches in parallel = OR (either being closed allows current).
A normally-closed switch controlled by signal $A$ = NOT $A$ .

Every Boolean expression corresponds to a switching circuit; every switching circuit corresponds to a Boolean expression. Designing a circuit becomes equivalent to simplifying a Boolean expression — and Boolean algebra has well-known simplification techniques.

This insight is what made modern digital electronics possible. Before Shannon, circuit design was empirical — engineers built and tested. After Shannon, circuit design was algebraic — engineers wrote Boolean expressions, simplified them, and translated them to circuits with guaranteed correctness.

Shannon’s thesis has been called “the most important master’s thesis of the 20th century.” The pure mathematics of Boole (a logical curiosity from 1854) became the design language of every electronic device built afterward.

Logic gates

In modern terms, Boolean operations are implemented as logic gates — small circuits that compute one operation. Each has a standard symbol:

These symbols are universal. Every circuit diagram, every CPU design, every microcontroller datasheet uses some version of these shapes. They’ve been standard since the early days of digital electronics.

Other common gates:

NOR: NOT OR — TRUE only when both inputs are FALSE.
XOR: exclusive OR — TRUE when exactly one input is TRUE.
XNOR: NOT XOR — TRUE when both inputs match.

Universal gates

A remarkable fact: NAND alone is sufficient to implement any Boolean function. So is NOR alone.

This is non-obvious. NOT, AND, and OR seem like three different operations. But:

$\text{NOT}(A) = \text{NAND}(A, A)$
$\text{AND}(A, B) = \text{NAND}(\text{NAND}(A, B), \text{NAND}(A, B))$
$\text{OR}(A, B) = \text{NAND}(\text{NAND}(A, A), \text{NAND}(B, B))$

With NAND alone, you can build anything. NAND is a universal gate — also called “functionally complete.”

This matters practically. Modern CPU chips are largely composed of NAND gates. The reason: a single NAND gate requires fewer transistors to implement (4 transistors in CMOS technology) than AND or OR gates separately. By using NAND as the basic building block, designers minimize transistor count, which reduces chip area, power consumption, and manufacturing cost.

A modern CPU has billions of NAND gates wired together — and from those NANDs, every arithmetic operation, every memory operation, every logical decision is constructed.

Building arithmetic from Boolean

Boolean algebra describes logic. Computers do arithmetic. How does Boolean lead to arithmetic?

The bridge is binary representation. Each integer is encoded as a sequence of bits — Boolean values. Then arithmetic operations become Boolean operations on these bit sequences.

Addition of two bits, ignoring carry: this is XOR.

0 + 0 = 0 (no carry)
0 + 1 = 1 (no carry)
1 + 0 = 1 (no carry)
1 + 1 = 0 with carry

The carry is generated when both inputs are 1: AND.

So a “half adder” — adding two bits — is two gates: XOR for the sum, AND for the carry. A “full adder” — adding two bits plus an incoming carry — uses a few more gates.

Chain $n$ full adders together and you have an $n$ -bit adder that adds two $n$ -bit numbers. From the same building blocks, more complex operations (subtraction, multiplication, division) follow.

Every arithmetic operation in your computer is implemented as a Boolean circuit composed of basic gates. The CPU’s “arithmetic logic unit” (ALU) is, at the deepest level, just a vast Boolean circuit.

De Morgan’s laws and circuit transformations

De Morgan’s laws are practical tools for circuit design:

$\lnot(A \land B) = \lnot A \lor \lnot B$ $\lnot(A \lor B) = \lnot A \land \lnot B$

In words: the negation of an AND becomes an OR of negations, and vice versa. These laws let you transform a circuit using one kind of gate into an equivalent circuit using the other.

This matters because, depending on the technology, some gates are cheaper to implement than others. CMOS technology naturally produces inverted outputs (NAND, NOR), so designs typically use those. De Morgan’s laws translate between AND/OR designs and NAND/NOR implementations.

In symbolic logic and in mathematical proof, De Morgan’s laws appear constantly. Whenever you negate a conjunction or disjunction, you’re applying De Morgan implicitly.

Boolean algebra in software

Beyond hardware, Boolean logic is fundamental to software.

Conditionals in programming: if (A && B) is exactly a Boolean AND. Programming with conditional logic is, at heart, manipulating Boolean expressions.

Database queries: SQL’s WHERE name = 'Alice' AND age > 25 is a Boolean filter. Database query optimization includes Boolean simplification — recognizing equivalent expressions to find the cheapest evaluation order.

Search engines: Boolean queries with AND, OR, NOT (and refinements like proximity) are the foundation of search. Modern search engines use much more than Boolean logic, but Boolean is the bedrock.

Type theory: in programming language theory, types form a Boolean-like algebra. Union types, intersection types, the “any” and “never” types — these mirror Boolean operations.

Formal verification: model checking and theorem proving for software use Boolean satisfiability (SAT solvers) as a core engine. SAT, the problem of determining whether a Boolean formula has a satisfying assignment, is the canonical NP-complete problem. Decades of research have produced SAT solvers that handle problems with millions of variables — and they’re used to verify chip designs, prove programs correct, and solve combinatorial problems across many domains.

Set theory connection

Boolean algebra and set theory are essentially the same structure with different interpretations:

Boolean	Set theory
TRUE / 1	Universe $U$
FALSE / 0	Empty set $\emptyset$
$A \land B$	$A \cap B$ (intersection)
$A \lor B$	$A \cup B$ (union)
$\lnot A$	$U \setminus A$ (complement)
Implication $A \to B$	$A \subseteq B$ (subset)

Both systems satisfy the same axioms (a Boolean algebra). This is why Venn diagrams work for both: they visualize the underlying lattice structure that both interpretations share.

The unification is not accidental. Both Boolean values and sets are instances of more general structures called Boolean lattices or Boolean rings. The mathematical theory developed in the late 19th and 20th centuries showed that any system satisfying the Huntington axioms behaves like both Boolean values and sets — and there are many other concrete examples (events in probability, subsets of any space, propositions in classical logic).

What Boolean algebra teaches

The deepest lesson of Boolean algebra is that abstract structures can find unexpected concrete homes. Boole invented his algebra to formalize reasoning — to make the laws of thought as precise as the laws of arithmetic. He had no inkling that 80 years later, his framework would describe electrical circuits, or that a century later it would underlie every digital device on Earth.

This is the same lesson we see in tensors, Lie groups, matrices, and many other mathematical structures: the abstraction outlives its original motivation. The mathematics retains validity even when the application changes.

For a student, Boolean algebra is one of the cleanest introductions to abstract algebra: a small set of axioms, a few derived laws, concrete computations, and a precise correspondence to a real-world domain (digital circuits). After Boolean algebra, the move to other algebraic structures (groups, rings, fields, lattices) becomes natural.

For an engineer, Boolean algebra is the daily working language. Designing a hardware controller? Boolean simplification. Writing a program with conditionals? Boolean logic. Querying a database? Boolean predicates. Configuring a firewall? Boolean rules. The mathematics is everywhere.

For a working computer, Boolean algebra is the substrate. Every bit in every register, every signal in every wire, every memory cell — they all have only two states, and they all combine according to Boole’s rules. The vast complexity of modern software is, ultimately, structured combinations of TRUE and FALSE.

A 19th-century mathematician trying to formalize philosophy gave us the mathematical foundation of every device on Earth. That kind of cross-century impact is rare — and Boolean algebra is one of the cleanest examples of it.

Boole died in 1864 — pneumonia after a walk home in the rain. He never saw an electrical relay, much less a transistor. The algebra he invented has now been computed at by approximately $10^{30}$ logical operations per second worldwide, every second, by trillions of devices. He would have been astonished. The mathematics, of course, didn’t care.

True or false: a great mathematical idea lives forever? Boole’s answer would have been: TRUE.

Frequently asked

Did George Boole really invent Boolean algebra?

He created the framework — his 1854 book 'An Investigation of the Laws of Thought' formalized algebra over true/false values. The modern axiomatization (the 'Boolean lattice') was refined by mathematicians including Charles Sanders Peirce and Edward Huntington in the late 19th and early 20th centuries. Claude Shannon's master's thesis (1937) showed the connection to electronic circuits.

Why are NAND and NOR gates 'universal'?

A universal gate is one from which all other Boolean functions can be constructed. NAND alone can build AND, OR, NOT — therefore any Boolean function. Same for NOR. This is why CPU chips often use mostly NAND gates: fewer transistors per gate, and the gate is functionally complete. Modern chips fabricate billions of NAND gates as their fundamental building blocks.

Is Boolean algebra related to set theory?

Yes — they have the same structure. Boolean operations (AND, OR, NOT) on values correspond to set operations (intersection, union, complement) on subsets. Both form a 'Boolean lattice' with the same axioms. This is why Venn diagrams work for both: they visualize the same algebraic structure with different interpretations.