Boolean Algebra¶
Job: Algebra of truth values and idempotent rings; connect classical propositional logic, set algebras, and switching theory.
Core¶
Boolean algebra: bounded distributive lattice \((B,\vee,\wedge,0,1)\) with complements \(x\vee x'=1\), \(x\wedge x'=0\). Equivalently: ring with identity of characteristic \(2\) that is idempotent (\(x^2=x\)) — Boolean ring \(x+y=(x\wedge y')\vee(x'\wedge y)\), \(xy=x\wedge y\).
Stone representation: every Boolean algebra is isomorphic to a field of sets (clopen sets of its Stone space); finite BAs are isomorphic to \(\mathcal{P}([n])\).
Examples: \(\mathbb{B}=\{0,1\}\) with OR/AND/NOT; \(\mathcal{P}(X)\); regular open algebras; Lindenbaum–Tarski algebra of propositional theories (mod logical equivalence).
Boolean functions \(f:\mathbb{B}^n\to\mathbb{B}\). Representable by formulas / circuits. DNF / CNF normal forms. Shannon expansion: $$ f(x_1,\ldots,x_n)=x_1 f(1,x_2,\ldots)\vee x_1' f(0,x_2,\ldots). $$
Functional completeness: \(\{\neg,\wedge,\vee\}\), \(\{\uparrow\}\) (NAND), \(\{\downarrow\}\) (NOR) generate all Boolean functions. Linear functions over \(\mathbb{F}_2\) form a proper subclass (XOR, affine).
Duality: interchange \(0/1\) and \(\vee/\wedge\); De Morgan \((x\vee y)'=x'\wedge y'\).
SAT (pointer): satisfiability of CNF is NP-complete (Cook–Levin). 2-SAT linear-time; Horn-SAT P; resolution proof systems.
Order / atoms: finite BA atomic; infinite may be atomless (e.g. Borel algebra mod null ideals in measure algebras).
See it¶
Karnaugh / Quine–McCluskey minimize sum-of-products for small \(n\): prime implicants cover the onset. Algebraically: consensus method computes prime implicants.
Check¶
Prove that a Boolean ring has characteristic 2 and is commutative.
\(x+x=(x+x)^2=x^2+x^2+x+x\Rightarrow x+x=0\) after using idempotence carefully: expand \((x+y)^2=x+y\Rightarrow xy+yx=0\Rightarrow xy=yx\) in char 2. Standard textbook calculation.
Is every finite distributive lattice Boolean?
No. Boolean requires complements. A chain of length \(\ge3\) is a distributive lattice that is not complemented.
Pitfalls¶
- Classical Boolean algebra \(\neq\) intuitionistic Heyting algebra (no excluded middle in general).
- "XOR algebra" alone is the affine \(\mathbb{F}_2\) fragment — not full Boolean without AND or majority, etc.
- Measure algebras identify a.e.-equal sets — Stone space is not the original point set.
Refs¶
Halmos, Lectures on Boolean Algebras; Sikorski; Davey–Priestley (lattices); Clote–Kranakis (Boolean functions / complexity).