Boolean Algebra

Boolean algebra is the mathematical foundation of digital circuits. Every digital system — from a single gate to a billion-transistor processor — is built on Boolean operations.

Boolean Functions

A Boolean function maps n Boolean inputs to one Boolean output:

f: {0, 1}ⁿ → {0, 1}

With n inputs, there are 2ⁿ possible input combinations and 2^(2ⁿ) possible functions.

| n inputs | Input combinations | Possible functions | |---|---|---| | 1 | 2 | 4 | | 2 | 4 | 16 | | 3 | 8 | 256 | | 4 | 16 | 65,536 |

Truth Tables

A truth table lists the output for every input combination.

Example: f(A, B) = A·B + A'·B (which simplifies to B):

| A | B | A·B | A'·B | f | |---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 1 | 1 | | 1 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 |

Canonical Forms

Sum of Products (SOP) — Disjunctive Normal Form

OR of AND terms. Each AND term (minterm) corresponds to a row where f = 1.

Minterm mᵢ: Product of all variables, each complemented if 0 in row i, uncomplemented if 1.

f(A, B, C) = Σm(1, 3, 5, 7)  = A'B'C + A'BC + AB'C + ABC

Product of Sums (POS) — Conjunctive Normal Form

AND of OR terms. Each OR term (maxterm) corresponds to a row where f = 0.

Maxterm Mᵢ: Sum of all variables, each complemented if 1 in row i, uncomplemented if 0.

f(A, B, C) = ΠM(0, 2, 4, 6) = (A+B+C)(A+B'+C)(A'+B+C)(A'+B'+C)

Minterms and maxterms are complements: mᵢ = M̄ᵢ.

Boolean Identities

Basic Identities

Identity:      A + 0 = A         A · 1 = A
Null:          A + 1 = 1         A · 0 = 0
Idempotent:    A + A = A         A · A = A
Complement:    A + A' = 1        A · A' = 0
Involution:    (A')' = A

Algebraic Properties

Commutative:   A + B = B + A              A · B = B · A
Associative:   (A+B)+C = A+(B+C)          (A·B)·C = A·(B·C)
Distributive:  A·(B+C) = A·B + A·C        A+(B·C) = (A+B)·(A+C)
Absorption:    A + A·B = A                A·(A+B) = A

De Morgan's Theorems

(A + B)' = A' · B'
(A · B)' = A' + B'

Generalized: (A₁ + A₂ + ... + Aₙ)' = A₁' · A₂' · ... · Aₙ'

Practical use: Convert between AND/OR/NOT. Transform SOP ↔ POS. Implement using only NAND or only NOR.

Consensus Theorem

AB + A'C + BC = AB + A'C

The term BC is redundant (the consensus term). It can be added or removed without changing the function.

Duality Principle

Every Boolean identity remains valid when AND ↔ OR and 0 ↔ 1 are swapped simultaneously.

Example: If A + 0 = A, then by duality A · 1 = A.

This doubles the number of theorems you need to remember.

Shannon Expansion

Any Boolean function can be decomposed:

f(x₁, x₂, ..., xₙ) = x₁ · f(1, x₂, ..., xₙ) + x₁' · f(0, x₂, ..., xₙ)

Cofactors: f₁ = f(x₁=1, ...) and f₀ = f(x₁=0, ...).

f = x₁·f₁ + x₁'·f₀

This is the basis for:

BDD construction (Binary Decision Diagrams)
Multiplexer implementation: f = MUX(f₀, f₁, x₁)
Recursive function evaluation

Functional Completeness

A set of operations is functionally complete if any Boolean function can be expressed using only those operations.

Complete Sets

{AND, OR, NOT} — standard
{AND, NOT} — since A+B = (A'·B')'
{OR, NOT} — since A·B = (A'+B')'
{NAND} alone — since A' = A↑A, A·B = (A↑B)↑(A↑B)
{NOR} alone — since A' = A↓A, A+B = (A↓B)↓(A↓B)

NAND-Only Implementation

NAND (↑): A↑B = (A·B)' = NOT(A AND B).

Deriving all operations from NAND:

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

Why NAND/NOR are important: CMOS technology naturally implements NAND and NOR gates efficiently. Most real circuits are built entirely from NAND or NOR gates.

Non-Complete Sets

{AND, OR} — cannot produce NOT (always monotone)
{XOR} — cannot produce AND or OR
{AND} — cannot negate
Any set of monotone functions — cannot produce NOT

Simplification Techniques

Algebraic Simplification

Apply Boolean identities manually:

f = ABC + ABC' + A'BC
  = AB(C + C') + A'BC       (factor AB)
  = AB + A'BC               (C + C' = 1)
  = B(A + A'C)              (factor B)
  = B(A + C)                (absorption: A + A'C = A + C)

Karnaugh Maps

Visual simplification for 2-6 variables (covered in combinational circuits).

Quine-McCluskey

Systematic tabular method for minimization (covered in combinational circuits). Can be automated.

Binary Decision Diagrams (BDDs)

A BDD represents a Boolean function as a directed acyclic graph.

Ordered BDD (OBDD)

Variables are tested in a fixed order. Each internal node has two children (for 0 and 1). Leaves are 0 or 1.

Reduced Ordered BDD (ROBDD)

Apply reduction rules:

Merge isomorphic subgraphs (share identical sub-functions)
Remove nodes where both children are the same

Properties:

Canonical: For a given variable order, the ROBDD is unique.
Efficient: Many practical functions have compact ROBDDs.
Operations: AND, OR, NOT, equivalence checking — all polynomial in BDD size.

Variable ordering matters enormously: some orderings give exponential-size BDDs while others give linear. Finding the optimal ordering is NP-hard, but heuristics work well.

Applications: Hardware verification, model checking, symbolic simulation, SAT solving, network reliability.

Applications in CS

Digital circuit design: Every gate implements a Boolean function. Minimization reduces chip area and power.
Compiler optimization: Dead code elimination, constant folding use Boolean simplification.
SAT solvers: Boolean satisfiability. CDCL solvers process CNF formulas.
Database queries: WHERE clauses are Boolean expressions. Query optimization applies Boolean simplification.
Network ACLs/Firewalls: Rule matching is Boolean function evaluation.
Configuration management: Feature flags, conditional compilation — Boolean constraint satisfaction.
Hardware verification: BDDs verify circuit equivalence and model-check temporal properties.
Bitwise operations: Systems programming uses AND, OR, XOR, NOT on integers as parallel Boolean operations on bits.