Lattices and Boolean Algebras

Lattice

A partially ordered set L is a lattice if for any two elements a, b there exist:

• sup{a,b} = a∨b (join, least upper bound)
• inf{a,b} = a∧b (meet, greatest lower bound)

Examples: (2^A, ⊆) — the lattice of subsets. (ℕ, |) — the lattice under divisibility: a∨b = LCM(a,b), a∧b = GCD(a,b). Subspaces in a vector space.

Boolean Algebra

A distributive complemented lattice: the distributive laws hold, $a\land(b\lor c) = (a\land b)\lor(a\land c)$, and complement $a^c$ such that $a\land a^c = 0$, $a\lor a^c = 1$.

Stone's Theorem: Every finite Boolean algebra is isomorphic to the power set algebra of some finite set. The size is a power of two.

Boolean Functions

A function $f: {0,1}^n \to {0,1}$. Defined by a truth table ($2^n$ rows).

Basic ones: NOT(x) = 1−x; AND(x,y) = min(x,y) = x·y; OR(x,y) = max(x,y) = x+y−xy; XOR = $x⊕y = (x+y) \bmod 2$.

NAND = NOT AND: a self-sufficient basis — all functions can be expressed using only NAND.

All Boolean functions = $2^{2^n}$ (grows very rapidly: for $n=3$ already 256 functions).

Huntington Algebra and Lattice Identities

Boolean algebra is an algebra with two binary operations ($\land$, $\lor$), one unary (¬), and two constants (0, 1), satisfying Huntington’s postulates: commutativity, distributivity of $\land$ over $\lor$ and $\lor$ over $\land$, and the law of complement. From these axioms, all other identities follow: idempotence ($x\land x = x$), absorption ($x\land(x\lor y) = x$), double negation ($\neg\neg x = x$), De Morgan’s laws.

Distributivity is a key difference between Boolean algebra and general lattices: not every lattice is distributive. Examples of non-distributive lattices: $M_5$ (a diamond with three elements in the middle layer) and $N_5$ (a five-element lattice in the shape of a pentagon). Birkhoff’s theorem: a lattice is distributive if and only if it does not contain a sublattice isomorphic to $M_5$ or $N_5$.

Minimization of Boolean Functions: Practice

The minimization problem is to find an equivalent formula with the minimum number of literals (variables and their negations). This directly affects circuit manufacturing cost: fewer gates → smaller chip area → cheaper production.

Karnaugh Map (1953) — a two-dimensional table where adjacent cells differ by exactly one literal (Gray code). By grouping cells with ones in rectangles of size power of two, prime implicants are found. The method works visually for functions up to 5–6 variables.

Quine–McCluskey Method (1956) — a tabular algorithm equivalent to Karnaugh maps, but suitable for any number of variables. Operates in two steps: finding all prime implicants (minterms differing in one bit are merged); selecting a cover with minimum number of implicants. The complexity is NP-hard in the general case.

Applications of Boolean Algebra in EDA and Verification

In EDA (Electronic Design Automation) systems, digital circuit synthesis is the problem of finding a minimal-size circuit implementing a given Boolean function. Modern tools (Synopsys Design Compiler, Cadence Genus) use heuristics based on algebraic transformations of Boolean formulas.

Formal verification uses Boolean methods to prove circuit correctness. BDD (Binary Decision Diagram, Bryant, 1986) is a canonical graph for Boolean functions. BDD allows checking the equivalence of two circuits in polynomial time, which is critical for processor core verification. The SAT solver method (Boolean Satisfiability) — finding input for which the function equals 1 — is the basis for formal verification of software and hardware.

Finite Fields and Reed–Solomon Codes

Finite field GF($p^n$) is a field with $p^n$ elements. GF($2^n$) is used in cryptography (AES operates in GF($2^8$)) and coding theory. The elements of GF($2^8$): polynomials of degree ≤ 7 over GF(2), with multiplication modulo an irreducible polynomial of degree 8.

Reed–Solomon codes (RS codes) are error-correcting codes over finite fields. RS(n, k) over GF(q) encodes k symbols into n > k. It can correct up to $(n−k)/2$ errors and $(n−k)$ erasures. Used in DVD/Blu-Ray, QR codes, satellite communication. The decoding algorithm uses Lagrange interpolation in a finite field.

Boolean Circuit Complexity

The circuit complexity of function $f: {0,1}^n \to {0,1}$ is the minimum number of AND/OR/NOT gates required to compute f. Most functions require exponential-size circuits, but obtaining concrete lower bounds for natural functions is hard. This is one of the central open problems in Computer Science. Shannon's theorem: a random n-variable Boolean function with high probability requires a circuit of size $\Theta(2^n/n)$.

BDD and Symbolic Representation of Boolean Functions

Binary Decision Diagram (BDD): a directed acyclic graph compactly representing a Boolean function. Ordered BDD (OBDD): variables occur in a fixed order — a normal form. Reduced OBDD (ROBDD): canonical. Operations (AND, OR, NOT) in $O(\lvert \mathrm{BDD}_1 \rvert \cdot \lvert \mathrm{BDD}_2 \rvert)$. Used in hardware verification (model checking). Some functions have exponential-size BDD for any variable order.

Numerical Example: Boolean Function Minimization

Problem: Minimize $f(a,b,c)$ with truth table: $f=1$ for $(a,b,c)\in{(0,0,1),(0,1,1),(1,0,1),(1,1,1)}$.

Step 1: $f=1$ if and only if $c=1$, for any $a,b$. In total, 4 one-valued minterms out of 8.

Step 2: Karnaugh map (3 variables): the $c=1$ column is completely filled with ones — one group of 4.

Step 3: Grouping 4 cells corresponds to the literal $c$ (neither $a$ nor $b$ affect the value of $f$). Minimal DNF: $f = c$.

Step 4: BDD for $f = c$: a graph with a single internal node “$c$” and two leaves (0 and 1) — BDD size is 1 gate, while the DNF with 4 minterms would require 4 AND + 3 OR = 7 gates. Optimization via BDD reduced the circuit by a factor of 7.