A Boolean algebra is a set $B$ with two binary operations $\land$ (AND) and $\lor$ (OR), one unary operation $\neg$ (NOT), and two distinguished elements $0$ (false) and $1$ (true), satisfying:

Idempotent laws: $a \land a = a$, $a \lor a = a$

Commutative laws: $a \land b = b \land a$, $a \lor b = b \lor a$

Associative laws: $(a \land b) \land c = a \land (b \land c)$, $(a \lor b) \lor c = a \lor (b \lor c)$

Absorption laws: $a \land (a \lor b) = a$, $a \lor (a \land b) = a$

Distributive laws: $a \land (b \lor c) = (a \land b) \lor (a \land c)$, $a \lor (b \land c) = (a \lor b) \land (a \lor c)$

Complement laws: $a \land \neg a = 0$, $a \lor \neg a = 1$

Identity laws: $a \land 1 = a$, $a \lor 0 = a$

A Boolean function $f: \{0,1\}^n \to \{0,1\}$ maps $n$ binary inputs to one binary output. There are $2^{2^n}$ Boolean functions of $n$ variables.

For $n=2$, there are 16 functions including AND, OR, XOR, NAND, NOR. These can be expressed using truth tables listing outputs for all $2^n$ input combinations.

A lattice is a partially ordered set $(L, \leq)$ where every pair of elements $a, b$ has:

• A least upper bound (join): $a \lor b = \sup\{a,b\}$
• A greatest lower bound (meet): $a \land b = \inf\{a,b\}$

A lattice is bounded if it has a least element $0$ and greatest element $1$.

A lattice is distributive if $a \land (b \lor c) = (a \land b) \lor (a \land c)$ for all $a,b,c$.

A complemented lattice has complements: for each $a$, there exists $a'$ with $a \land a' = 0$ and $a \lor a' = 1$.