Boolean Algebras and Lattices

Introduction

This is the first article of the Boolean system in Part V, and it occupies the algebra slot of that system. The system is the two-element Boolean domain $\mathbf{2} = \{0,1\}$ together with the propositional connectives, and the article develops the equational algebra that the domain generates: the Boolean algebras. It is the synthetic counterpart of the general order theory of Part I, and it states for this one system what Order Theory and Lattices states for orders in general.

The boundary against the general theory is deliberate. Lattices, distributivity, modularity, Galois connections and the fixed-point theorems belong to Order Theory and Lattices and are used here, not re-derived. The topological slot of the Boolean system is a separate article,which supplies the Stone space, the compactness and the total disconnectedness; nothing topological is developed below. Because the Boolean system is finite in a strong sense — every finitely generated Boolean algebra is finite, and the two-element algebra generates the whole variety — the system supports an algebra and no analysis, and the closing section records why.

Throughout, a lattice is written $(L, \wedge, \vee)$ with meet $\wedge$ and join $\vee$, and its order is $\leq$. The two-element algebra is $\mathbf{2} = \{0,1\}$ with $0 < 1$, and the power set of a set $X$ is $\mathcal{P}(X)$. The complement of an element $\alpha$ of a Boolean algebra is written $\neg\alpha$. The elementary connectives and the satisfaction relation are those of Logic and Proof, and the natural numbers that index the generators are those of The Natural Numbers, written in parallel in this Part.

Lattices and Their Operations

The Two Operations of an Order

Definition. A lattice is a partially ordered set $(L, \leq)$ in which every pair of elements has a least upper bound and a greatest lower bound. The least upper bound of $\{a,b\}$ is the join $a \vee b$, and the greatest lower bound is the meet $a \wedge b$. A lattice is bounded if it has a least element $0$ and a greatest element $1$.

The two operations are related to the order by the equivalences

$$ a \wedge b = a \iff a \leq b \iff a \vee b = b, $$

which is the form in which inequalities are verified in a lattice. Written as equations, the operations satisfy the lattice laws

$$ a \wedge a = a, \qquad a \vee a = a, \qquad a \wedge b = b \wedge a, \qquad a \vee b = b \vee a, $$

$$ (a \wedge b) \wedge c = a \wedge (b \wedge c), \qquad (a \vee b) \vee c = a \vee (b \vee c), $$

together with the two absorption laws

$$ a \wedge (a \vee b) = a, \qquad a \vee (a \wedge b) = a, $$

and a bounded lattice satisfies $a \wedge 1 = a$ and $a \vee 0 = a$. Conversely, any set with two binary operations satisfying the lattice laws and the absorption laws is a lattice for the order defined by $a \leq b \iff a \wedge b = a$, so the order-theoretic and the equational presentations are equivalent. This is the content of Order Theory and Lattices, where the argument is given.

Example. Every total order is a lattice, with $a \wedge b = \min(a,b)$ and $a \vee b = \max(a,b)$. The real line with its usual order is a lattice of this kind; it is not bounded, and its completion $\mathbb{R} \cup \{-\infty, +\infty\}$ is a complete lattice, the standard order-theoretic completion of Order Theory and Lattices.

Example. The subgroups of a group, ordered by inclusion, form a lattice with $H \wedge K = H \cap K$ and $H \vee K$ the subgroup generated by $H \cup K$. This lattice is bounded by the trivial subgroup and the whole group; it is modular but not distributive whenever the group contains a nonabelian composition factor, which is the standard reason modularity rather than distributivity is the natural hypothesis in group theory.

Example. The set of equivalence relations on a set $X$, ordered by refinement, is a bounded lattice: the meet is the intersection of the two relations and the join is the equivalence relation they generate. This is the lattice in which the congruence lattices of universal algebra live, and it is the setting of the quotient construction below.

Distributivity and Modularity

Definition. A lattice is distributive if either of the two equivalent identities

$$ a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c), \qquad a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c) $$

holds for all $a,b,c$; that the two are equivalent is a theorem of Order Theory and Lattices, and either may be taken as the axiom. A lattice is modular if

$$ a \leq c \implies a \vee (b \wedge c) = (a \vee b) \wedge c . $$

Theorem. Every distributive lattice is modular, and a lattice is distributive if and only if it contains neither of the two lattices $M_3$ nor $N_5$ as a sublattice.

Proof. Distributive implies modular is an immediate substitution. The forbidden-sublattice criterion is the theorem of Dedekind and Birkhoff: $N_5$ is modular but not distributive and $M_3$ is not modular, and every non-distributive lattice contains one of them as a sublattice. The proof is in Order Theory and Lattices and is not repeated.

The theorem is the reason the Boolean system is so rigid: a Boolean algebra is a distributive lattice, so it contains neither $M_3$ nor $N_5$, and the congruence lattice of a distributive lattice is itself distributive. Non-distributive logic, which is the subject, begins exactly where this criterion fails.

Boolean Algebras

Definition and the Complement

Definition. A Boolean algebra is a bounded distributive lattice $(B, \wedge, \vee, 0, 1)$ in which every element $\alpha$ has a complement, an element $\neg\alpha$ with

$$ \alpha \wedge \neg\alpha = 0, \qquad \alpha \vee \neg\alpha = 1 . $$

A homomorphism of Boolean algebras is a map $\varphi : B \to B'$ preserving $\wedge$, $\vee$, $\neg$, $0$ and $1$. A subalgebra is a subset closed under the three operations; an ideal is a nonempty subset $I$ closed under finite joins and downward closed, $\alpha \in I$ and $\beta \leq \alpha$ implying $\beta \in I$; a filter is the order-dual notion. The algebra $B$ is trivial if $0 = 1$.

Theorem. In a bounded distributive lattice, a complement, when it exists, is unique.

Proof. Let $\beta$ and $\gamma$ both complement $\alpha$. Then

$$ \beta = \beta \wedge 1 = \beta \wedge (\alpha \vee \gamma) = (\beta \wedge \alpha) \vee (\beta \wedge \gamma) = 0 \vee (\beta \wedge \gamma) = \beta \wedge \gamma, $$

so $\beta \leq \gamma$; the same computation with $\beta$ and $\gamma$ interchanged gives $\gamma \leq \beta$, whence $\beta = \gamma$ by antisymmetry.

Uniqueness is what makes $\neg$ an operation and not merely a relation, and it is what fails in the non-distributive ortholattices. The following identities are then forced, and they are the reason Boolean algebra is an equational theory.

Theorem. Let $B$ be a Boolean algebra and $\alpha, \beta \in B$. Then

$$ \neg \neg \alpha = \alpha, \qquad \neg 0 = 1, \qquad \neg 1 = 0, \qquad \neg(\alpha \wedge \beta) = \neg \alpha \vee \neg \beta, \qquad \neg(\alpha \vee \beta) = \neg \alpha \wedge \neg \beta, $$

and

$$ \alpha \leq \beta \iff \alpha \wedge \neg \beta = 0 \iff \neg \alpha \vee \beta = 1 . $$

Proof. That $\alpha$ is a complement of $\neg \alpha$ follows from the symmetry of the two defining equations, so $\neg\neg \alpha = \alpha$ by uniqueness. The identities $\neg 0 = 1$ and $\neg 1 = 0$ are the defining equations at $\alpha = 0$ and $\alpha = 1$. For De Morgan, put $\gamma = \neg \alpha \vee \neg \beta$; then

$$ (\alpha \wedge \beta) \wedge \gamma = (\alpha \wedge \beta \wedge \neg \alpha) \vee (\alpha \wedge \beta \wedge \neg \beta) = 0 \vee 0 = 0 $$

and

$$ (\alpha \wedge \beta) \vee \gamma = (\alpha \vee \neg \alpha \vee \neg \beta) \wedge (\beta \vee \neg \alpha \vee \neg \beta) = 1 \wedge 1 = 1, $$

so $\gamma$ complements $\alpha \wedge \beta$ and equals $\neg(\alpha \wedge \beta)$ by uniqueness; the other De Morgan law is dual. For the last display, if $\alpha \leq \beta$ then $\alpha \wedge \neg \beta \leq \beta \wedge \neg \beta = 0$; conversely $\alpha \wedge \neg \beta = 0$ gives $\alpha = \alpha \wedge 1 = \alpha \wedge (\beta \vee \neg \beta) = (\alpha \wedge \beta) \vee (\alpha \wedge \neg \beta) = \alpha \wedge \beta \leq \beta$, and the equivalence with $\neg \alpha \vee \beta = 1$ is the De Morgan law applied to $\alpha \wedge \neg \beta = 0$.

The Duality Principle

The axioms of a Boolean algebra are self-dual under the interchange

$$ \wedge \longleftrightarrow \vee, \qquad 0 \longleftrightarrow 1, $$

the complement being unchanged. Consequently every theorem of Boolean algebra has a dual, obtained by this interchange, and the dual is a theorem; the order is reversed by the passage to the dual, since $\alpha \leq \beta$ is $\alpha \wedge \beta = \alpha$ in one reading and $\alpha \vee \beta = \beta$ in the other.

Example. The statement that the join of two elements is their least upper bound dualises to the statement that the meet is their greatest lower bound; the identity $\alpha \vee (\beta \wedge \gamma) = (\alpha \vee \beta) \wedge (\alpha \vee \gamma)$ dualises to $\alpha \wedge (\beta \vee \gamma) = (\alpha \wedge \beta) \vee (\alpha \wedge \gamma)$. The duality is a symmetry of the equational theory rather than a map of an individual algebra into itself; it corresponds to the order-reversing bijection $\alpha \mapsto \neg \alpha$ of the algebra onto its opposite.

The Two-Element Algebra and the Algebra of Subsets

Example (the two-element algebra). Let $\mathbf{2} = \{0,1\}$ with the order $0 < 1$. The meet is the conjunction, the join is the disjunction, and $\neg 0 = 1$, $\neg 1 = 0$. This is a Boolean algebra, and it is the smallest nontrivial one.

Example (the power set). For any set $X$, the power set $\mathcal{P}(X)$ ordered by inclusion is a Boolean algebra with

$$ A \wedge B = A \cap B, \qquad A \vee B = A \cup B, \qquad \neg A = X \setminus A, \qquad 0 = \emptyset, \qquad 1 = X . $$

The distributive law is the identity $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, and the complement identities are the defining properties of a complement in a set. The finite power sets $\mathcal{P}(\{1,\dots,n\})$ are the finite Boolean algebras up to isomorphism, by the theorem below.

Example (the free algebra). The Boolean algebra generated by $n$ free generators is the algebra of Boolean functions on $n$ variables; it is described in the section on normal form and has $2^{2^n}$ elements.

The power-set example is the source of the intuition, and the representation theorem of the topological slot of this system makes it exhaustive: every Boolean algebra is a subalgebra of a power set, and in the finite case it is a power set.

Boolean Functions and Algebraic Normal Form

Boolean Polynomials over $\mathbb{F}_2$

Let $n \geq 0$. A Boolean function of $n$ variables is a map $f : \mathbf{2}^n \to \mathbf{2}$. The set of all such maps carries the Boolean operations pointwise: $(f \wedge g)(x) = f(x) \wedge g(x)$, and similarly for $\vee$ and $\neg$. With the constant functions $0$ and $1$ this is a Boolean algebra.

Over the field $\mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z}$, a polynomial is an element of $\mathbb{F}_2[\alpha_1,\dots,\alpha_n]$. Because every element of $\mathbb{F}_2$ satisfies $u^2 = u$, the polynomial $\alpha_i^2 - \alpha_i$ vanishes on all of $\mathbf{2}^n$, and every Boolean function is represented by the reduced polynomial obtained by imposing $\alpha_i^2 = \alpha_i$. The reduced monomials are

$$ \alpha^{e} = \alpha_1^{e_1} \alpha_2^{e_2} \cdots \alpha_n^{e_n}, \qquad e = (e_1, \dots, e_n) \in \mathbf{2}^n, $$

there being one for each exponent vector $e$, hence exactly $2^n$ of them.

Theorem (algebraic normal form). Every Boolean function $f$ of $n$ variables has a unique expression

$$ f(\alpha) = \bigoplus_{e \in \mathbf{2}^n} c_e \, \alpha^{e}, \qquad c_e \in \mathbb{F}_2, $$

where $\oplus$ is addition in $\mathbb{F}_2$ and the product is taken in $\mathbb{F}_2$.

Proof. The $2^n$ reduced monomials are linearly independent over $\mathbb{F}_2$ as functions. Suppose a combination vanishes and let $e$ be an exponent vector with $c_e \neq 0$ minimal for coordinatewise comparison: if $e' < e$ coordinatewise then $c_{e'} = 0$, and evaluating the combination at the point $e$ (read as an element of $\mathbf{2}^n$) kills every monomial $\alpha^{e'}$ with $e'$ not above $e$, while $\alpha^{e}(e) = 1$; hence $c_e = 0$, a contradiction. So the span of the reduced monomials has dimension $2^n$. There are exactly $2^{2^n}$ functions $\mathbf{2}^n \to \mathbf{2}$ and exactly $2^{2^n}$ coefficient vectors $(c_e)$, so the span is everything and the expression is unique.

The expansion is the Reed–Muller expansion. It says that the Boolean functions on $n$ variables form the free $\mathbb{F}_2$-vector space on the $2^n$ reduced monomials, equivalently the free Boolean ring on $n$ generators, discussed.

Corollary. There are exactly $2^{2^n}$ Boolean functions of $n$ variables. For $n = 0$ there are two, the two constants $0$ and $1$; for $n = 1$ there are four; for $n = 2$ there are sixteen; for $n = 3$ there are two hundred and fifty-six.

Example. For $n = 2$ the reduced monomials are $1, \alpha, \beta, \alpha\beta$, and the $16$ functions are the $\mathbb{F}_2$-combinations of them. The conjunction is $\alpha \wedge \beta = \alpha\beta$, the disjunction is $\alpha \vee \beta = \alpha \oplus \beta \oplus \alpha\beta$, and the NAND is $\alpha \uparrow \beta = 1 \oplus \alpha\beta$. The expansion of the disjunction is verified from the table

so the expression is correct at all four inputs.

Disjunctive and Conjunctive Normal Form

The disjunctive normal form of $f$ is the join of the minterms on which $f$ takes the value $1$:

$$ f = \bigvee_{x \in \mathbf{2}^n,\ f(x)=1} m_x, \qquad m_x = \bigwedge_{i=1}^{n} \begin{cases} \alpha_i & x_i = 1 \\ \neg \alpha_i & x_i = 0,\end{cases} $$

where the algebra variables are written $\alpha_1,\dots,\alpha_n$ to distinguish them from the points $x$. Dually, the conjunctive normal form is the meet of the maxterms on which $f$ vanishes. Every minterm is an atom of the free algebra, the $2^n$ minterms are pairwise disjoint and their join is $1$, and the disjunctive normal form is the expansion of $f$ in the basis of atoms. The algebraic normal form is the corresponding expansion in the basis of reduced monomials; the two bases are related by the identity $\alpha \vee \beta = \alpha \oplus \beta \oplus \alpha\beta$, which converts one normal form into the other.

The Free Boolean Algebra

Theorem (free Boolean algebra). The free Boolean algebra on $n$ generators is isomorphic to the algebra of Boolean functions on $n$ variables and to the power set $\mathcal{P}(\mathbf{2}^n)$. It has $2^{2^n}$ elements, and its atoms are the minterms.

Proof. A homomorphism from the free algebra on $\alpha_1,\dots,\alpha_n$ to $\mathbf{2}$ is determined by the images of the generators, an arbitrary point of $\mathbf{2}^n$; hence the homomorphisms biject with $\mathbf{2}^n$. The map that sends a function $f$ to the set of points where it is $1$ is a bijection with $\mathcal{P}(\mathbf{2}^n)$, and the pointwise operations correspond to the set operations, so it is an isomorphism onto the power set; its cardinality is $2^{2^n}$. The atoms of a power set are the singletons, corresponding to the functions that vanish except at one point, which are exactly the minterms.

Boolean Algebras as the Algebra of Propositional Logic

The Lindenbaum–Tarski Algebra

Let $L$ be the propositional language on a set of variables, built from the connectives $\wedge, \vee, \neg, \to, \leftrightarrow$ as in Logic and Proof, and let $T$ be a set of propositions. Define a relation on the propositions by

$$ \varphi \sim_T \psi \iff T \vdash \varphi \leftrightarrow \psi, $$

that is, $T$ proves that $\varphi$ and $\psi$ are equivalent. The Lindenbaum–Tarski algebra of $T$ is the quotient of the propositions by $\sim_T$, with the operations induced by the connectives and the classes of the always-false and always-true propositions as $0$ and $1$.

Theorem (Lindenbaum–Tarski). The relation $\sim_T$ is a congruence on the propositional algebra, and the quotient is a Boolean algebra. It is the trivial algebra exactly when $T$ is inconsistent.

Proof. The relation is an equivalence relation because $\leftrightarrow$ is reflexive, symmetric and transitive in the propositional calculus, and it is a congruence because the connectives are compatible with provable equivalence; the quotient therefore inherits the operations. The distributive, complementation and bound laws hold because their instances in the connectives are tautologies, each provable from the axioms of Logic and Proof; for instance $\varphi \wedge \neg \varphi$ is refutable and $\varphi \vee \neg \varphi$ is provable in the classical calculus. If $T$ is inconsistent then every proposition is provable, so all classes coincide and $0 = 1$; conversely if $0 = 1$ then $T$ proves a contradiction.

Semantics and the Two-Element Model

A valuation is a map $v$ from the propositional variables to $\mathbf{2}$, extended to all propositions by the truth tables; equivalently, by the theorem above, a homomorphism from the free propositional algebra to $\mathbf{2}$. A proposition is a tautology if every valuation gives it the value $1$, and satisfiable if some valuation does.

Theorem (soundness and completeness, semantic form). For a set $T$ of propositions and a proposition $\varphi$,

$$ T \vdash \varphi \iff \text{every valuation satisfying } T \text{ satisfies } \varphi . $$

Pro. Soundness is induction on the length of a derivation, each axiom being a tautology and each rule preserving truth. For completeness, suppose $T \nvdash \varphi$; then the class of $\varphi$ is not $1$ in the Lindenbaum–Tarski algebra $B$ of $T$, and since $B$ is a nontrivial Boolean algebra it has a homomorphism to $\mathbf{2}$ — in the finite case by the finite representation theorem above, and in general by the prime-filter theorem — pulling back to a valuation satisfying $T$ and falsifying $\varphi$. A direct proof from the syntax is in Logic and Proof.

Remark. The completeness theorem identifies the semantic models of propositional logic with the homomorphisms into $\mathbf{2}$. This is the reason the two-element algebra is the object of study: the variety generated by $\mathbf{2}$ is the variety of all Boolean algebras, so the equational theory of the system is the theory of this single finite algebra.

Constructions

Products and Quotients

Definition. The product of Boolean algebras $B_1, B_2$ is the Cartesian product $B_1 \times B_2$ with the operations defined componentwise. The quotient of $B$ by a filter $F$ is $B/\sim_F$, where

$$ \alpha \sim_F \beta \iff \text{there is } \gamma \in F \text{ with } \alpha \wedge \gamma = \beta \wedge \gamma, $$

and dually for an ideal.

Theorem. The product is a Boolean algebra, with $\neg(\alpha_1,\alpha_2) = (\neg \alpha_1, \neg \alpha_2)$ and bounds $(0,0)$ and $(1,1)$, and it is the categorical product of $B_1$ and $B_2$. The quotient $B/F$ is a Boolean algebra, and it is trivial if and only if $F = B$.

Proof. The componentwise verification is immediate, and the projection maps $B_1 \times B_2 \to B_i$ have the universal property of the product because a pair of homomorphisms assembles into one. For the quotient, the relation $\sim_F$ is a congruence: if $\gamma \in F$ witnesses $\alpha \sim_F \beta$ and $\gamma' \in F$ witnesses $\alpha' \sim_F \beta'$, then $\gamma \wedge \gamma' \in F$ witnesses $\alpha \wedge \alpha' \sim_F \beta \wedge \beta'$, and for the complement one uses that $\alpha \wedge \gamma = \beta \wedge \gamma$ implies $\neg \alpha \wedge \gamma = \neg \beta \wedge \gamma$; the standard filter-quotient computation is in Order Theory and Lattices. The quotient identifies $0$ and $1$ exactly when $F$ contains an element $\gamma$ with $0 \wedge \gamma = 1 \wedge \gamma$, that is $\gamma = 0$, and since $0 \in F$ forces $F = B$, the quotient is trivial exactly when $F = B$.

Example. The power set $\mathcal{P}(X)$ is the product over $x \in X$ of copies of $\mathbf{2}$: a subset is a $0$–$1$ function on $X$, and the product is taken pointwise. In the finite case every Boolean algebra arises this way, by the following theorem.

Atoms and the Finite Structure Theorem

Definition. An atom of a Boolean algebra $B$ is a minimal nonzero element: an $\alpha \neq 0$ such that $0 \leq \beta \leq \alpha$ implies $\beta = 0$ or $\beta = \alpha$. The algebra is atomic if every nonzero element lies above an atom, and atomless if it has no atoms.

Theorem (finite representation). Every finite Boolean algebra is isomorphic to the power set of its set of atoms. In particular a finite Boolean algebra has $2^n$ elements for some $n \geq 0$, and it is determined up to isomorphism by the number $n$ of its atoms.

Proof. Let $A$ be the set of atoms of the finite algebra $B$. For $\alpha \in B$ let $A_\alpha = \{\beta \in A : \beta \leq \alpha\}$. If $\alpha \neq 0$, then some atom lies below $\alpha$: the interval $[0,\alpha]$ is finite, so a minimal element of the nonempty set $\{\delta : 0 < \delta \leq \alpha\}$ is an atom of $B$ lying below $\alpha$. Hence $\alpha = \bigvee A_\alpha$. Indeed the join $\gamma = \bigvee A_\alpha$ satisfies $\gamma \leq \alpha$; if $\gamma < \alpha$ then $\alpha \wedge \neg \gamma \neq 0$ contains an atom $\beta \leq \alpha \wedge \neg \gamma$, and $\beta$ lies in $A_\alpha$ but not below $\gamma$, contradicting the definition of $\gamma$. Distinct atoms have meet $0$, since their meet lies below both and is neither of them. The map $\alpha \mapsto A_\alpha$ is therefore injective, and it preserves joins, meets, complements and bounds, so it is an isomorphism onto $\mathcal{P}(A)$; the cardinality is $2^{\lvert A \rvert}$.

Example (the atomless algebra). The algebra of finite and cofinite subsets of an infinite set is Boolean and atomless; so is the algebra of measurable subsets of $[0,1]$ modulo null sets, the measure algebra of Measure Theory and Integration, which is the standard atomless Boolean algebra of cardinality continuum. These show that the finite representation theorem does not extend to the infinite case in the form in which atoms determine the algebra: the measure algebra has no atoms at all. The general representation is the Stone theorem of the topological slot.

The Boolean System Supports No Analysis

The Boolean system carries an algebra in the strongest sense: a finitely axiomatised equational theory, a free algebra on every finite set of generators, arbitrary products and quotients, and a complete semantic model in the two-element algebra. What it does not carry is analysis, and the reason is structural rather than incidental.

There is no distance on a Boolean algebra that the algebra itself supplies, and there is no notion of limit to define: a sequence of elements of a Boolean algebra cannot converge in the algebra, because the only available convergence is eventual constancy, and the completeness theorem above already extracts from the algebra everything a limit could contribute — the homomorphisms to $\mathbf{2}$ — without a metric. Equivalently, the Boolean system is finite in the sense that its free algebra on $n$ generators is finite, so every function of finitely many Boolean variables is continuous in every topology that makes $\mathbf{2}$ Hausdorff, and the subject is the algebra of these functions.

The enrichment the system does admit is topological, and it lies outside this article. A Boolean algebra can be read as a ring under symmetric difference and intersection, and the prime ideals of that ring form a compact Hausdorff totally disconnected space whose clopen sets reproduce the algebra; this is Stone duality, the first instance in the corpus of the algebra–topology dictionary that Gelfand duality completes. Even there analysis is absent: the Stone space is totally disconnected, so the only continuous functions that matter are locally constant, and no derivative or integral arises. The Boolean system supports an algebra, a topology, and no analysis.

Summary

A Boolean algebra is a bounded distributive lattice in which every element has a complement; the complement is unique in a distributive lattice, so complementation is an operation and the theory is equational. The axioms are self-dual under the interchange of $\wedge$ with $\vee$ and $0$ with $1$, which gives the duality principle, and the basic identities — double complement, De Morgan, and the characterisation $\alpha \leq \beta \iff \alpha \wedge \neg \beta = 0$ — are forced by the axioms. The two-element algebra $\mathbf{2}$ and the power sets $\mathcal{P}(X)$ are the examples, and the finite Boolean algebras are exactly the power sets of finite sets: every finite Boolean algebra is isomorphic to the power set of its atoms, and so has $2^n$ elements. The infinite case is different, the atomless algebras showing that atoms need not determine the algebra.

The Boolean functions on $n$ variables form a Boolean algebra of $2^{2^n}$ elements, which is simultaneously the free Boolean algebra on $n$ generators and the power set of $\mathbf{2}^n$. Every such function has a unique algebraic normal form as an $\mathbb{F}_2$-combination of the $2^n$ reduced monomials, and dually a disjunctive normal form as a join of minterms; the two are exchanged by the identity $\alpha \vee \beta = \alpha \oplus \beta \oplus \alpha\beta$. The Lindenbaum–Tarski construction turns any propositional theory into a Boolean algebra, and the homomorphisms of that algebra into $\mathbf{2}$ are exactly the valuations, so the completeness theorem of propositional logic is the statement that $\mathbf{2}$ generates the variety of Boolean algebras. Products and filter-quotients of Boolean algebras are Boolean algebras, the product being the categorical product.

The Boolean system supports an algebra and no analysis. Its free algebras are finite, it carries no distance of its own, and the enrichment it admits is the topological one of Stone duality, in which the prime ideals form a compact totally disconnected space. That topology, and with it the representation theorem, is not covered here.

Summary of Notation

Further Reading

• Garrett Birkhoff, Lattice Theory (American Mathematical Society Colloquium Publications, 3rd ed. 1967), for the lattice laws, distributivity, modularity and the forbidden-sublattice criterion.
• George Boole, An Investigation of the Laws of Thought (Walton and Maberly, 1854), for the origin of the algebra of logic.
• Paul R. Halmos, Lectures on Boolean Algebras (Van Nostrand, 1963), for the equational theory, ideals and filters, and the representation theorem.
• Roman Sikorski, Boolean Algebras (Springer, 3rd ed. 1969), for the infinite theory, free algebras and the measure algebra.
• Steven Givant and Paul Halmos, Introduction to Boolean Algebras (Springer, 2009), for a modern systematic treatment with the Stone theorem.
• Herbert B. Enderton, A Mathematical Introduction to Logic (Academic Press, 2nd ed. 2001), for the Lindenbaum–Tarski construction and the completeness theorem of propositional logic.
• Ingo Wegener, The Complexity of Boolean Functions (Wiley, 1987), for the normal forms and the representation of Boolean functions, treated as finite mathematics.