Boolean Algebra

A Boolean variable takes exactly one of two values, conventionally written `0` and `1`, standing for false and true. A Boolean function maps some number of Boolean input variables to a single Boolean output, $f: \{0,1\}^n \to \{0,1\}$. Because each input can independently be 0 or 1, a function of $n$ variables has $2^n$ possible input combinations, and since each combination can independently map to 0 or 1, there are exactly $2^{2^n}$ distinct Boolean functions of $n$ variables — for $n=2$ that is already 16 distinct functions, including AND, OR, XOR, NAND, and more exotic ones. Three operators generate everything. AND (written $A \cdot B$, $AB$, or $A \wedge B$) is 1 only when both operands are 1. OR (written $A + B$ or $A \vee B$) is 1 when at least one operand is 1. NOT (written $\overline{A}$, $A'$, or $\neg A$) flips 0 to 1 and 1 to 0. These three are functionally complete: any Boolean function whatsoever, no matter how many inputs, can be built from just AND, OR, and NOT. This is what makes Boolean algebra the right abstraction for hardware — a designer never needs more primitive operations than these three (and in fact NAND alone suffices, a fact exploited heavily in Logic Gates). Boolean algebra is formally an algebraic structure: a set (here $\{0,1\}$) equipped with two binary operations (AND, OR) and one unary operation (NOT), satisfying a fixed list of axioms. This mirrors ordinary algebra on numbers, but with a crucial difference — the idempotent laws ($A + A = A$, $A \cdot A = A$) and the existence of a complement for every element have no counterpart in the algebra of real numbers. Because it is a genuine algebraic system with axioms, every identity used to simplify a circuit is a theorem, not a rule of thumb — it can be proved once and reused forever.

The axioms. Every valid Boolean identity follows from a small axiom set (Huntington's postulates, as adapted by Shannon). Let $A$, $B$, $C$ be Boolean variables.

Notice each row comes in a pair that is identical except AND and OR (and 0 and 1) are swapped. This is the duality principle: replace every $\cdot \leftrightarrow +$ and every $0 \leftrightarrow 1$ in a true statement, and the result is also true. Duality is not itself an axiom — it is a theorem about the axioms, since the axiom list itself is symmetric under the swap. It halves the work of memorization: prove one law, get its dual for free.

De Morgan's laws, the two identities most heavily used in simplification, state:

In words: the complement of an OR is the AND of the complements, and the complement of an AND is the OR of the complements. These are dual to each other and let a designer convert freely between "sum of products" (OR of AND terms) and "product of sums" (AND of OR terms) circuit styles — essential when only NAND or only NOR gates are available in a fabrication library.

Deriving new identities. Because the axioms are proven true for all 0/1 assignments, any chain of algebraic rewrites using only axioms (or previously derived theorems) produces another universally true identity. Two standard proof techniques: 1. Algebraic derivation — rewrite the expression step by step, citing an axiom or theorem at each step, until it matches the target. 2. Perfect induction (truth-table proof) — since there are only $2^n$ input combinations for $n$ variables, exhaust them all and check both sides agree on every row. This is always valid because a Boolean function is completely determined by its truth table. Worked derivation of the absorption law $A + AB = A$, using only axioms: ``` A + AB = A·1 + A·B [identity: A = A·1] = A·(1 + B) [distributive, factoring A] = A·1 [null law: 1 + B = 1] = A [identity] ``` Worked derivation of consensus $AB + \overline{A}C + BC = AB + \overline{A}C$ (the third term is redundant): ``` AB + A'C + BC = AB + A'C + BC·1 [identity] = AB + A'C + BC·(A + A') [complement: 1 = A + A'] = AB + A'C + ABC + A'BC [distribute] = AB(1 + C) + A'C(1 + B) [factor, using AB+ABC=AB(1+C), A'C+A'BC=A'C(1+B)] = AB·1 + A'C·1 [null: 1+C=1, 1+B=1] = AB + A'C ``` This identity is the algebraic engine behind Karnaugh Maps: recognizing consensus terms lets you delete literals that add gate cost without changing the function.

De Morgan's law proved by perfect induction (a template for verifying any 2-variable identity):

The two right columns agree on all four rows, so the identity holds for every assignment — a complete proof, since there are no other cases.

Simplification as an algorithm. Turning a raw expression into a minimal one is a repeated-rewrite procedure: ``` function SIMPLIFY(expr): repeat: changed = false for each subexpression s in expr: if s matches a known identity pattern (idempotent, absorption, De Morgan, consensus, complement, null): replace s with its simplified form changed = true until not changed return expr ``` ``` function EVAL(expr, assignment): // assignment maps each variable to 0 or 1 switch expr.kind: case VAR: return assignment[expr.name] case NOT: return 1 - EVAL(expr.child, assignment) case AND: return EVAL(expr.left, assignment) AND EVAL(expr.right, assignment) case OR: return EVAL(expr.left, assignment) OR EVAL(expr.right, assignment) ``` ``` function TRUTH_TABLE(expr, vars): // vars = list of n variable names n = length(vars) rows = [] for i in 0 .. 2^n - 1: assignment = BINARY_DIGITS(i, n) // build n-bit assignment from counter i row = (assignment, EVAL(expr, assignment)) append row to rows return rows ``` `TRUTH_TABLE` is the bridge between the algebraic and tabular views of a function: every Boolean expression has exactly one truth table, and (up to relabeling) every truth table can be read directly into a canonical sum-of-products expression by OR-ing together one AND term per row where the output is 1.

Space and time to represent a function. A Boolean function of $n$ variables has a truth table with $2^n$ rows, so writing it out explicitly costs $O(2^n)$ space and $O(2^n)$ time to construct (`TRUTH_TABLE` above visits each of the $2^n$ assignments once, doing $O(1)$ work — or $O(k)$ work for an expression with $k$ operators — per row, giving $O(k \cdot 2^n)$ total). This exponential blow-up is unavoidable in the worst case: some functions (e.g., a random function, or the parity/XOR of all $n$ inputs) genuinely need to inspect essentially all $2^n$ rows to be distinguished from another function, since two functions can agree on all but one input and still be different functions. Algebraic expressions avoid this blow-up when the function has structure — an $n$-bit AND is one gate with $n$ inputs and one line of algebra, not a $2^n$-row table, even though its truth table still formally has $2^n$ rows.

Simplification is not free. The `SIMPLIFY` procedure above is a rewrite system: it repeatedly matches identity patterns until no more apply. Two honest facts:

• Termination is guaranteed for the axioms and theorems listed here because each valid rewrite strictly decreases a measure — typically the literal count (number of variable occurrences) or expression size — so the process cannot loop forever. Idempotent, absorption, and null-law rewrites all shrink the expression; commutative and associative rewrites only reorder, so a real implementation applies them only when they enable a shrinking rewrite next.
• Finding the minimum-literal expression is itself computationally hard. Boolean minimization (exact two-level logic minimization) is known to be NP-hard in general — this is why practical tools use Karnaugh Maps for small instances and heuristic/exact covering algorithms (e.g., the Quine–McCluskey method with a set-cover step) for larger ones, rather than brute-force search over all equivalent expressions.

Correctness of the axioms and derived laws. Every identity stated here is provable by perfect induction: since a Boolean function of $n$ variables is by definition a table of $2^n$ input/output pairs, two expressions are equal as functions if and only if they agree on all $2^n$ assignments. Checking all $2^n$ rows is a finite, exhaustive, and therefore fully rigorous proof method — there is no "adversarial" input space left unchecked once every row is verified, unlike proofs about infinite domains. For a fixed small $n$ (2 or 3, as used above for De Morgan and absorption), this is a few lines of table; the axioms themselves (Huntington's postulates) are taken as given, and every other law here — idempotent, absorption, consensus, De Morgan — is a theorem, derivable from the axioms alone without appeal to a truth table, exactly as shown in the algebraic derivations above.

Tradeoff to be honest about. Boolean algebra guarantees that a minimal or simplified form exists and how to verify equivalence, but it does not by itself give an efficient algorithm to find the global minimum for large $n$. This is precisely the gap that Karnaugh maps (visual, for $n \le 4$–5) and the Quine–McCluskey / Espresso-style algorithms (systematic, for larger $n$) are built to close.

Simplify $F(A,B,C) = AB + A\overline{B}C + \overline{A}C$ and verify against a truth table.

Algebraic route: ``` F = AB + AB'C + A'C = A(B + B'C) + A'C [factor A from first two terms] = A(B + C) + A'C [since B + B'C = B + C, by distributive/absorption: B + B'C = (B+B')(B+C) = 1·(B+C) = B+C] = AB + AC + A'C [distribute] = AB + C(A + A') [factor C from last two terms] = AB + C·1 [complement law] = AB + C ``` The original expression used 3 product terms and 7 literals; the simplified form uses 2 terms and 3 literals — a direct reduction in gate count.

Verification by perfect induction (all 8 rows for 3 variables):

The last two columns match on all 8 rows, confirming the algebraic simplification is correct — not just plausible-looking symbol shuffling, but a proven equivalence. Note the middle row-by-row work also shows why: whenever $A\overline{B}C$ contributes a 1 (row `101`), $AB+C$ already covers it via the $C$ term, so nothing is lost by dropping the middle product term.

Claude Shannon's 1938 thesis, later called "possibly the most important master's thesis of the century," is the pivot point: it recognized that open/closed relay contacts behave exactly like Boolean 0/1 values, and that series and parallel wiring behave exactly like AND and OR. This single insight converted Boole's abstract logic into the working mathematics of every digital circuit built since.

Boolean algebra underlies every stage of digital hardware design. Hardware description languages like Verilog and VHDL compile assign-statements and always-blocks into Boolean expressions that synthesis tools then simplify using these exact identities before mapping them to a standard cell library. CPU control units, ALUs, cache tag comparators, and branch predictors are all specified as Boolean functions of status bits and instruction fields. Database query optimizers use Boolean algebra to simplify WHERE-clause predicates (`De Morgan` transformations are routine when pushing NOT through AND/OR in query planning). Digital logic simulators, formal verification tools, and SAT/SMT solvers used in chip validation and security analysis all operate on Boolean expressions as their core data structure. Even network firewall rule optimization and search-engine boolean queries (`AND`, `OR`, `NOT` operators) trace their correctness guarantees back to this same algebra. Every topic that follows — Logic Gates as physical implementations of AND/OR/NOT, Karnaugh Maps as a visual minimization tool, and Combinational Logic Design as the discipline of building correct multi-gate circuits — is built directly on the identities introduced here.

Ask the tutor: Can you walk me through simplifying a 4-variable Boolean expression step by step using these identities?