Boolean Algebra

Definition

A Boolean algebra is a complemented distributive lattice. It is a formal algebraic structure $(B,\vee ,\wedge ,\neg ,0,1)$ consisting of a set $B$ equipped with two binary operations, join ($\vee$) and meet ($\wedge$), one unary operation, negation ($\neg$), and two distinct elements $0$ (bottom) and $1$ (top).

For all $a,b,c\in B$, the following axioms must hold:

• Associativity: $a\vee (b\vee c)=(a\vee b)\vee c$ and $a\wedge (b\wedge c)=(a\wedge b)\wedge c$.
• Commutativity: $a\vee b=b\vee a$ and $a\wedge b=b\wedge a$.
• Absorption: $a\vee (a\wedge b)=a$ and $a\wedge (a\vee b)=a$.
• Identity: $a\vee 0=a$ and $a\wedge 1=a$.
• Distributivity: $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$ and $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$.
• Complementation: $a\vee \neg a=1$ and $a\wedge \neg a=0$.

Relation to Type Theory and Logic

In the context of logic and type theory:

• Classical Logic: The truth values $\{\perp ,\top \}$ form the simplest Boolean algebra, often denoted $2$.
• Constructive Logic: In intuitionistic logic, the collection of propositions forms a Heyting algebra rather than a Boolean algebra, as the law of excluded middle ($a\vee \neg a=1$) is not required to hold.
• Subsets: The power set $\mathcal{P}(S)$ of any set $S$ forms a Boolean algebra under union, intersection, and complement.

Properties

• De Morgan’s Laws: $\neg (a\vee b)=\neg a\wedge \neg b$ and $\neg (a\wedge b)=\neg a\vee \neg b$.
• Idempotence: $a\vee a=a$ and $a\wedge a=a$.
• Duality: Every identity in Boolean algebra remains valid if $\vee$ and $\wedge$ are interchanged alongside $0$ and $1$.

References

boole1854-laws-thought - G. Boole, “An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities,” Walton and Maberly, 1854. halmos1963-boolean-algebras - P. Halmos, “Lectures on Boolean Algebras,” Van Nostrand, 1963. givant2009-intro-boolean - S. Givant and P. Halmos, “Introduction to Boolean Algebras,” Springer-Verlag, 2009.