Boolean Algebras and Stone Duality
Boolean Algebra Identities and Duality
The identity calculus of Boolean algebras: De Morgan's laws, involution, absorption, and the duality principle that halves every proof.
Learning objectives
- Derive the standard Boolean identities from the axioms
- State and apply the duality principle
- Use the normal form results for computation
The core identities
| Name | Identity |
|---|---|
| Involution | (x′)′ ≈ x |
| De Morgan (join) | (x ∨ y)′ ≈ x′ ∧ y′ |
| De Morgan (meet) | (x ∧ y)′ ≈ x′ ∨ y′ |
| Bounds | x ∨ 1 ≈ 1, x ∧ 0 ≈ 0 |
| Complement of bounds | 0′ ≈ 1, 1′ ≈ 0 |
| Absorption | x ∨ (x ∧ y) ≈ x |
| Idempotence | x ∨ x ≈ x |
Since 2 generates the variety, each identity holds in all Boolean algebras exactly when it holds in 2. De Morgan's laws are a four-row check.
Duality
If an identity holds in every Boolean algebra, so does its dual — obtained by interchanging ∨ with ∧ and 0 with 1 throughout, leaving complementation alone.
The axiom set is self-dual under this interchange, so the principle follows immediately. It is stronger than the lattice duality principle because the constants swap as well.
Duality in action
Having proved x ∨ (y ∧ z) ≈ (x ∨ y) ∧ (x ∨ z), the dual x ∧ (y ∨ z) ≈ (x ∧ y) ∨ (x ∧ z) requires no further work.
In a Boolean algebra the duality is not merely formal: the map x ↦ x′ is an anti-isomorphism onto the dual algebra. De Morgan's laws are exactly the statement that complementation converts joins into meets.
Normal forms
A join of meets of literals, where a literal is a variable or its complement.
Every Boolean term in n variables is equivalent to a term in disjunctive normal form, and to one in conjunctive normal form.
The full disjunctive normal form uses only complete meets involving every variable exactly once, and is unique. This gives a decision procedure for Boolean identities and shows the free Boolean algebra on n generators has exactly 22n elements.
| Generators | Size of free algebra | Interpretation |
|---|---|---|
| 0 | 2 | The constants alone |
| 1 | 4 | 0, x, x′, 1 |
| 2 | 16 | All two-variable truth functions |
| 3 | 256 | |
| n | 22n | All n-ary truth functions |
The free Boolean algebra on n generators is the power set of the 2n-element set of truth assignments. Elements of the free algebra are Boolean functions; the atoms are the individual assignments.
Decidability
The equational theory of Boolean algebras is decidable: to test an identity in n variables, evaluate both sides on all 2n assignments.
The procedure is exponential, and the corresponding satisfiability problem is NP-complete. Decidability of the equational theory says nothing about tractability, and the contrast is worth keeping in view when Chapter V discusses decidability questions.
Frequently asked questions
Is the duality principle a theorem or a meta-theorem?
A meta-theorem — a statement about which identities are provable, justified by the self-duality of the axiom set. It is not itself an identity.
Are Boolean algebras the only self-dual variety of lattices?
No. Distributive lattices are self-dual as a variety, as are modular lattices. What is special about Boolean algebras is that the duality is implemented by an operation within the algebra.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section IV.1, book pages 131-133.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.