Boolean Algebra and Logic Gates

The Mathematician Who Rewired the World

In 1847, a 32-year-old self-taught mathematics teacher in Lincoln, England published a slim pamphlet called The Mathematical Analysis of Logic. His name was George Boole, and he had no university degree, no prestigious laboratory, and no idea that his work would one day be called the theoretical foundation of the digital age.

Boole's insight was radical: logic could be treated as algebra. Instead of numbers, his variables held only two values — TRUE or FALSE. Instead of multiplication and addition, he defined AND, OR, and NOT operations. His 1854 book An Investigation of the Laws of Thought formalized the entire system.

Boole died in 1864 at age 49, still unknown outside mathematics. It wasn't until 1937 — 73 years later — that a 21-year-old MIT master's student named Claude Shannon realized that Boole's algebra described exactly how electrical relay circuits work. That thesis, A Symbolic Analysis of Relay and Switching Circuits, is considered one of the most important master's theses ever written.

Every logic gate in every CPU, GPU, and smartphone today is Boolean algebra made physical.

---

Why Boolean Algebra?

The connection between Boolean algebra and computing is not accidental — it is fundamental.

A transistor has two states: conducting (1, ON, TRUE) and non-conducting (0, OFF, FALSE). Boolean algebra is precisely the mathematics of two-valued logic. Therefore:

• Boolean variables map directly to transistor states
• Boolean operations map directly to transistor circuits
• Complex Boolean expressions map directly to complex circuits

"A CPU with 19 billion transistors is, at its mathematical core, a very large Boolean expression being evaluated billions of times per second."

---

The Three Fundamental Operations

NOT (Complement / Inverter)

NOT inverts its input. If A is TRUE, NOT A is FALSE.

Expression: Y = A' or Y = ¬A or Y = NOT A

AND (Conjunction)

AND outputs TRUE only when all inputs are TRUE.

Expression: Y = A · B or Y = A AND B

OR (Disjunction)

OR outputs TRUE when at least one input is TRUE.

Expression: Y = A + B or Y = A OR B

---

Extended Gates: NAND, NOR, XOR, XNOR

NAND (NOT AND)

Y = (A · B)' — AND followed by NOT. NAND outputs 0 only when all inputs are 1.

NOR (NOT OR)

Y = (A + B)' — OR followed by NOT. NOR outputs 1 only when all inputs are 0.

XOR (Exclusive OR)

Y = A ⊕ B — outputs 1 when inputs are different. The workhorse of addition circuits.

XNOR (Exclusive NOR)

Y = (A ⊕ B)' — outputs 1 when inputs are equal. Used in comparators.

Complete Truth Table

---

Boolean Laws

These laws let you simplify circuits (fewer transistors = faster, cheaper chips).

Identity Laws:

• A + 0 = A
• A · 1 = A

Null Laws:

• A + 1 = 1
• A · 0 = 0

Idempotent Laws:

• A + A = A
• A · A = A

Complement Laws:

• A + A' = 1
• A · A' = 0

Commutative Laws:

• A + B = B + A
• A · B = B · A

Associative Laws:

• A + (B + C) = (A + B) + C
• A · (B · C) = (A · B) · C

Distributive Laws:

• A · (B + C) = (A · B) + (A · C)
• A + (B · C) = (A + B) · (A + C)

De Morgan's Theorems

The most practically important laws in digital design:

NOT(A AND B) = (NOT A) OR (NOT B) (A · B)' = A' + B'

NOT(A OR B) = (NOT A) AND (NOT B) (A + B)' = A' · B'

Why they matter: De Morgan's theorems let you convert NAND gates to OR gates with inverted inputs (and vice versa), enabling circuit optimization. Modern chip synthesis tools use De Morgan's theorems millions of times during the chip design process.

---

Logic Gates as Physical Components: CMOS

Modern logic gates are built from CMOS (Complementary Metal-Oxide-Semiconductor) transistors — paired PMOS and NMOS transistors that complement each other:

• NMOS transistor: conducts when input is HIGH (1)
• PMOS transistor: conducts when input is LOW (0)

A CMOS NOT gate (inverter) uses 2 transistors. The pull-up network (PMOS) connects to VDD when input is 0; the pull-down network (NMOS) connects to GND when input is 1.

The elegance of CMOS: in steady state, either the pull-up OR pull-down is conducting, never both. This means near-zero static power consumption — the reason CMOS dominates every battery-powered device.

---

Gate Propagation Delay

Physical gates are not instantaneous. After an input changes, a small time elapses before the output settles. This is the propagation delay (tpd), typically in the range of 10–500 picoseconds for modern CMOS gates at 5nm process.

Why it matters: in a circuit with 20 gates in series, the total delay is the sum of each gate's propagation delay. This critical path delay determines the maximum clock frequency of the entire chip.

Intel Core i9 at 5.8 GHz means the clock period is 1/5.8×10⁹ = ~172 picoseconds. Every logic path in the CPU must complete within this window.

---

Universal Gates: NAND and NOR

A stunning result of Boolean algebra: any logic function can be implemented using only NAND gates (or only NOR gates).

NAND and NOR are called functionally complete or universal gates.

NOT from NAND: Connect both NAND inputs together → (A·A)' = A' AND from NAND: NAND followed by NOT-NAND = AND OR from NAND: Apply De Morgan's: A+B = (A'·B')' — three NANDs

Practical impact: Chip manufacturers can fabricate a design using only one type of gate cell, simplifying the manufacturing process. Many ASICs (Application-Specific Integrated Circuits) are designed this way.

---

Gates Overview Diagram

---

Gate Reference Table

---

Key Takeaways

• George Boole (1815–1864) invented Boolean algebra for logic; Claude Shannon (1937) connected it to electrical circuits
• Boolean variables hold only 0 (FALSE) or 1 (TRUE)
• The three fundamental operations are NOT, AND, OR; all others derive from these
• De Morgan's Theorems — (A·B)' = A'+B' and (A+B)' = A'·B' — are essential for circuit simplification
• CMOS transistor pairs implement gates with near-zero static power, enabling battery-powered devices
• Propagation delay (~10–500 ps per gate) limits the maximum clock frequency of a CPU
• NAND and NOR are universal gates — any logic function can be built from either alone
• Every adder, comparator, multiplexer, and memory cell in a CPU is ultimately a network of these seven gate types