Boolean Algebra: The Mathematics of True and False

Boolean Algebra: The Mathematics of True and False | Ideasthesia

Boolean algebra has exactly two numbers: 0 and 1.

True and false. On and off. Yes and no.

That's it. No fractions. No negatives. No irrational numbers. Just two states.

And from this impossibly simple system, we built every computer, every circuit, every processor, every piece of digital technology that exists.

The Origin

In 1854, George Boole published The Laws of Thought, attempting to formalize logic using mathematics. He wanted to treat true/false statements as algebraic objects—variables that could be manipulated with operations like AND, OR, and NOT.

At the time, it was pure philosophy. Abstract symbol manipulation with no practical use.

Eighty years later, Claude Shannon—a 21-year-old master's student at MIT—realized Boole's algebra perfectly described electrical circuits. Switches could be on (1) or off (0). Gates could combine signals using AND, OR, NOT.

Shannon's 1937 master's thesis, "A Symbolic Analysis of Relay and Switching Circuits," is arguably the most important master's thesis ever written. It founded digital circuit design and made modern computing possible.

Boolean algebra—born as philosophical logic—became the mathematics of computation.

The Basics

The Domain

Boolean variables take one of two values: {0, 1} or {false, true} or {F, T}.

Convention: We'll use 0 and 1.

The Operations

AND (conjunction, ∧, ·): Output is 1 only if both inputs are 1.

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

OR (disjunction, ∨, +): Output is 1 if at least one input is 1.

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

NOT (negation, ¬, ~, '): Flips the value.

A	NOT A
0	1
1	0

These three operations are functionally complete—you can build any Boolean function from AND, OR, NOT.

Boolean Expressions

You can combine operations into expressions:

Example: (A AND B) OR (NOT C)

For A=1, B=0, C=1:

A AND B = 1 AND 0 = 0
NOT C = NOT 1 = 0
0 OR 0 = 0

Boolean expressions evaluate left-to-right with precedence (NOT > AND > OR), just like arithmetic.

Truth Tables

A truth table lists all possible input combinations and their outputs.

Example: A XOR B (exclusive OR—true if exactly one input is true)

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

For n variables, a truth table has 2ⁿ rows (every possible combination).

Truth tables completely specify a Boolean function. If two functions have identical truth tables, they're equivalent.

Boolean Laws

Boolean algebra obeys algebraic laws (like regular algebra, but with some differences).

Identity Laws

A AND 1 = A
A OR 0 = A

Null Laws

A AND 0 = 0
A OR 1 = 1

Idempotent Laws

A AND A = A
A OR A = A

Complement Laws

A AND (NOT A) = 0
A OR (NOT A) = 1

Commutative Laws

A AND B = B AND A
A OR B = B OR A

Associative Laws

(A AND B) AND C = A AND (B AND C)
(A OR B) OR C = A OR (B OR C)

Distributive Laws

A AND (B OR C) = (A AND B) OR (A AND C)
A OR (B AND C) = (A OR B) AND (A OR C)

The second distributive law is weird—OR distributes over AND. In regular algebra, multiplication distributes over addition, but addition doesn't distribute over multiplication. Boolean algebra is more symmetric.

De Morgan's Laws

NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)

De Morgan's laws are crucial for simplifying circuits. They show how to "push" NOT through AND/OR by flipping the operation.

Simplifying Boolean Expressions

Why simplify? Fewer operations = smaller circuits = faster, cheaper hardware.

Example: Simplify (A AND B) OR (A AND NOT B)

Apply distributive law: = A AND (B OR NOT B)

Apply complement law (B OR NOT B = 1): = A AND 1

Apply identity law: = A

The complex expression reduces to just A. Same function, simpler circuit.

Canonical Forms

Every Boolean function can be expressed in two standard forms.

Sum of Products (SOP, Disjunctive Normal Form)

OR of AND terms.

Example: (A AND B) OR (A AND NOT C) OR (NOT A AND B AND C)

How to construct from truth table:

For each row where output is 1, create an AND term combining all inputs (NOT if 0, as-is if 1)
OR all those terms together

This always works but may not be minimal.

Product of Sums (POS, Conjunctive Normal Form)

AND of OR terms.

Example: (A OR B) AND (A OR NOT C) AND (NOT A OR B OR C)

How to construct:

For each row where output is 0, create an OR term combining all inputs (as-is if 0, NOT if 1)
AND all those terms together

SOP and POS are canonical—unique for a given function (once simplified). They're useful for systematic circuit design.

Karnaugh Maps: Visual Simplification

Karnaugh maps (K-maps) are grids for simplifying Boolean expressions visually.

For 2 variables:

     B=0  B=1
A=0   □    □
A=1   □    □

Fill in output values. Look for rectangular groups of 1s (sizes: 1, 2, 4, 8...). Each group corresponds to a simplified term.

Example: Simplify F(A,B,C) where F=1 for (A,B,C) = (0,1,1), (1,0,1), (1,1,0), (1,1,1)

Draw 3-variable K-map, fill in 1s for those inputs, identify groups, extract simplified expression.

K-maps work well for up to 4 variables. Beyond that, algorithmic methods (Quine-McCluskey) are better.

Logic Gates

Boolean operations become physical circuits via logic gates.

AND Gate

Two inputs, one output. Output HIGH only if both inputs HIGH.

Symbol: D-shaped with flat input side.

OR Gate

Two inputs, one output. Output HIGH if any input HIGH.

Symbol: Curved input side.

NOT Gate (Inverter)

One input, one output. Flips value.

Symbol: Triangle with circle (bubble) at output.

NAND Gate

NOT-AND. Output LOW only if both inputs HIGH.

Symbol: AND gate with bubble at output.

Special property: NAND is universal—you can build any Boolean function using only NAND gates.

NOR Gate

NOT-OR. Output HIGH only if both inputs LOW.

Also universal.

XOR Gate

Exclusive OR. Output HIGH if inputs differ.

XNOR Gate

NOT-XOR. Output HIGH if inputs are the same.

Building Circuits

Combine gates to implement Boolean functions.

Example: Implement F = (A AND B) OR (NOT C)

Feed A and B into AND gate → output X
Feed C into NOT gate → output Y
Feed X and Y into OR gate → output F

The circuit computes F from inputs A, B, C.

Half Adder: Add two 1-bit numbers.

Inputs: A, B
Outputs: Sum = A XOR B, Carry = A AND B

Full Adder: Add three 1-bit numbers (A, B, carry-in).

Sum = A XOR B XOR Cin
Carry-out = (A AND B) OR (Cin AND (A XOR B))

Chain full adders together → multi-bit adder. Chain adders → ALU (arithmetic logic unit). This is how computers do arithmetic—billions of tiny Boolean operations.

Multiplexers and Demultiplexers

Multiplexer (MUX): Select one of several inputs based on control signals.

A 2-to-1 MUX has inputs A and B, a select line S, and output F:

If S=0, F=A
If S=1, F=B

Boolean expression: F = (NOT S AND A) OR (S AND B)

MUXes route data. CPUs use them to select which register to read, which operation to perform.

Demultiplexer (DEMUX): Route one input to one of several outputs based on control signals. The inverse of a MUX.

Sequential Logic: Memory

So far, all circuits are combinational—output depends only on current inputs. No memory.

Sequential logic adds memory via flip-flops—circuits that store state.

SR Latch (Set-Reset)

Two inputs (S, R), one output (Q).

S=1: Set Q=1
R=1: Reset Q=0
S=R=0: Hold current value

Built from cross-coupled NOR or NAND gates.

D Flip-Flop

One data input (D), one clock input (CLK), one output (Q).

On clock edge (rising or falling), Q = D. Otherwise, Q holds value.

Why it matters: D flip-flops store bits. Chain them → registers. Registers store variables, instructions, addresses—everything a computer remembers.

Finite State Machines

Combine sequential logic (flip-flops) and combinational logic (gates) → finite state machines (FSMs).

An FSM has:

A finite set of states
Transitions between states based on inputs
Outputs based on current state (and/or inputs)

Example: Traffic light

States: Green, Yellow, Red
Transitions: Green → Yellow (after timer), Yellow → Red, Red → Green
Outputs: Light signals

FSMs model controllers, protocols, parsers—anything with discrete states and transitions.

CPUs are FSMs. Each instruction moves the CPU through states (fetch, decode, execute, write-back).

Boolean Algebra in Programming

Every if statement, every while loop, every logical expression in code is Boolean algebra.

if (age >= 18 and hasLicense) or isEmergency:
    allowDriving = True

This is Boolean algebra: F = (age ≥ 18 AND hasLicense) OR isEmergency

Compilers translate this into machine code, which becomes gates, which execute the logic.

Bitwise operations: Programming languages expose Boolean operations on bits.

& (AND), | (OR), ^ (XOR), ~ (NOT)
<< (left shift), >> (right shift)

Bitwise tricks optimize performance (checking if a number is even: n & 1 == 0; swapping without temp variable using XOR; fast multiplication/division by powers of 2 via shifts).

Boolean Satisfiability (SAT)

SAT problem: Given a Boolean formula, does there exist an assignment of variables making it true?

Example: (A OR B) AND (NOT A OR C) AND (NOT B OR NOT C)

Does any assignment of A, B, C satisfy this?

Try: A=1, B=0, C=1

(1 OR 0) = 1 ✓
(NOT 1 OR 1) = (0 OR 1) = 1 ✓
(NOT 0 OR NOT 1) = (1 OR 0) = 1 ✓

Yes, satisfiable.

Why it matters: SAT is NP-complete—the first problem proven to be NP-complete (Cook-Levin theorem, 1971). If you can solve SAT efficiently, you can solve any NP problem efficiently.

Applications:

Hardware verification: Check if a circuit design satisfies specifications
Software verification: Prove code correctness
Planning and scheduling: Find valid assignments
Cryptanalysis: Break certain encryption schemes

Modern SAT solvers handle millions of variables using clever heuristics. They're used in industry for formal verification, AI planning, and optimization.

Boolean Functions Are Ubiquitous

Boolean algebra isn't just circuits. It's everywhere.

Database queries: SQL WHERE clauses are Boolean expressions.

SELECT * FROM users WHERE age >= 18 AND country = 'US' OR isPremium = true

Search engines: Boolean search (Google's AND, OR, NOT operators).

Access control: Permissions are Boolean logic.

canEdit = (isOwner OR isAdmin) AND NOT isBanned

Machine learning: Decision trees split on Boolean conditions. Neural network activations are (smooth approximations of) Boolean thresholds.

Formal methods: Verifying software/hardware correctness using Boolean logic and SAT solvers.

Why Two Numbers Are Enough

Boolean algebra seems trivial. Only two values. Only three operations.

But it's Turing complete—you can build any computable function from Boolean gates. The simplicity is the power.

Computers don't need the richness of real numbers, complex numbers, or infinite structures. They need something robust, reliable, and physically implementable. Binary is perfect:

Noise tolerance: High/low voltage states are easy to distinguish. Analog values drift; binary is stable.
Simplicity: Fewer components, simpler design, easier manufacturing.
Composability: Gates stack. Millions of them. Billions. Without exponentially increasing complexity.
Universality: NAND gates alone suffice. Simple building block → infinite computational possibility.

The universe of computation reduces to 0 and 1.