Boolean Algebra

Part of Basic Computing

Boolean algebra is the mathematical system underlying all digital logic — a formal calculus of true and false that enables circuit analysis and simplification.

Why This Matters

Boolean algebra, developed by George Boole in 1847, describes logical relationships mathematically. It was an abstract curiosity until Claude Shannon proved in 1937 that electrical relay circuits could implement Boolean operations, connecting the mathematics directly to hardware. Every logic circuit ever built since is governed by Boolean algebra.

Understanding Boolean algebra means being able to analyze what a circuit does, simplify it to use fewer components, prove two circuit designs are equivalent, and derive circuits from logical specifications. These skills apply whether you are designing transistor circuits from scratch, writing assembly code with branching conditions, or implementing decision logic in any system.

Boolean algebra is also simple — far simpler than ordinary algebra with its real numbers and continuous operations. There are only two values, and all operations reduce to truth tables with finite rows. This makes formal proof and analysis tractable for any careful thinker.

Fundamental Operations and Axioms

Boolean algebra operates on variables that can only be 0 (false) or 1 (true). Three primary operations:

AND (·, multiplication): A AND B = 1 only when both A = 1 and B = 1 OR (+, addition): A OR B = 1 when either or both inputs are 1 NOT (overbar, complement): NOT A = 1 when A = 0, and vice versa

Fundamental axioms (take these as given — they define the system):

Identity laws:

• A + 0 = A (OR with false leaves A unchanged)
• A · 1 = A (AND with true leaves A unchanged)

Null (domination) laws:

• A + 1 = 1 (OR with true always gives true)
• A · 0 = 0 (AND with false always gives false)

Idempotent laws:

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

Complement laws:

• A + NOT A = 1 (a variable OR its complement is always true)
• A · NOT A = 0 (a variable AND its complement is always false)

Double negation: NOT(NOT A) = A

These axioms are verifiable by truth table. For example, A + NOT A: when A=0, 0+1=1; when A=1, 1+0=1. Always 1. The axiom holds.

Key Theorems for Circuit Simplification

Building on the axioms, several important theorems allow complex expressions to be simplified:

Commutative laws: A + B = B + A; A · B = B · A (order doesn’t matter)

Associative laws: (A + B) + C = A + (B + C); grouping doesn’t matter

Distributive laws: A · (B + C) = A·B + A·C; A + (B · C) = (A+B) · (A+C)

Absorption laws: A + (A · B) = A; A · (A + B) = A (one term absorbs the other)

De Morgan’s laws (extremely important):

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

De Morgan’s laws show how to push negation inside a complex expression, converting AND to OR (or vice versa). They also show that NAND = NOT(AND) and NOR = NOT(OR) can each implement all other operations, making them “universal gates.”

Consensus theorem: A·B + NOT A·C + B·C = A·B + NOT A·C (the term B·C is redundant)

This theorem is important for circuit minimization — identifying and removing redundant logic.

Truth Tables and Expression Derivation

A truth table enumerates all possible input combinations and their outputs. For N variables, there are 2^N rows.

For a 3-variable function F = A·B + NOT A·C:

A	B	C	A·B	NOT A	NOT A·C	F
0	0	0	0	1	0	0
0	0	1	0	1	1	1
0	1	0	0	1	0	0
0	1	1	0	1	1	1
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	1	0	0	1
1	1	1	1	0	0	1

From any truth table, you can derive a Boolean expression using Sum of Products (SOP): write an AND term for each row where F=1, OR them all together. For row (A=0,B=0,C=1): NOT A · NOT B · C. For row (A=1,B=1,C=0): A · B · NOT C. And so on.

Conversely, Product of Sums (POS) form uses each row where F=0.

Karnaugh Maps for Simplification

A Karnaugh map (K-map) is a visual tool for simplifying Boolean expressions. It arranges truth table rows in a grid so adjacent cells differ in exactly one variable, making visual grouping of 1s straightforward.

For two variables (A, B) — a 2×2 grid:

      B=0  B=1
A=0 |  F00  F01 |
A=1 |  F10  F11 |

For three variables (A, B, C) — a 2×4 grid with Gray code column ordering (00, 01, 11, 10):

        BC=00  BC=01  BC=11  BC=10
A=0  |   0      1      1      0   |
A=1  |   0      0      1      1   |

Group adjacent 1s in rectangles of size 1, 2, 4, or 8. Larger groups give simpler terms. The K-map above has the 1s at positions (A=0,BC=01), (A=0,BC=11), (A=1,BC=11), (A=1,BC=10). Grouping the right column pair: A=0,BC=11 and A=1,BC=11 → B·C (A drops out). Grouping (A=0,BC=01) and (A=0,BC=11) → NOT A · B (C drops out). Grouping (A=1,BC=11) and (A=1,BC=10) → A · B (C drops out).

Minimal cover: F = NOT A · B + A · B = B. Wait — verify: wherever B=1, F=1? Check: (0,1,0)→1 yes, (0,1,1)→1 yes, (1,1,0)→1 yes, (1,1,1)→1 yes. Wherever B=0, F=0? (0,0,0)→0 yes, (0,0,1)→1 — no, that’s the entry at BC=01, which is B=0, C=1. So F is not simply B.

K-maps reward practice. Work through examples systematically, being careful with variable labeling. The payoff is direct circuit minimization — fewer gates, lower cost, less power, higher speed.

Application: Deriving Circuits from Specifications

Practical use of Boolean algebra:

1. Write the truth table from the verbal specification
2. Identify output function via SOP or POS
3. Simplify using K-map or algebraic manipulation
4. Map each operation to available gate types
5. Apply De Morgan’s if needed to use only available gates (e.g., NAND-only)

Example: “Output is 1 when at least two of three inputs are 1” (majority function):

Truth table produces: F = A·B·NOT C + A·NOT B·C + NOT A·B·C + A·B·C

K-map simplification yields: F = A·B + A·C + B·C

This three-gate-OR-of-three-AND design requires 3 AND gates + 1 three-input OR gate. Further NAND conversion: apply De Morgan’s to get NAND-NAND implementation using only 4 NAND gates — a significant simplification for construction.

Boolean algebra is not just theoretical. Every gate saved is a component not needed, a solder joint not made, and a potential failure point eliminated.