Prerequisite: Complemented LatticePermalink

Definition 3.1: Let $L$ be a bounded lattice.

1. An element $x\in L$ is said to be complemented (by $y$) if $\mathrm{\exists }y\in L$ such that $x\wedge y=\mathrm{\perp }$ and $x\vee y=\mathrm{\top }$.
2. We call $y$, also denoted by $x^{\ast }$, the complement of $x$.
3. Accordingly, lattice $R$ is said to be complemented if $\mathrm{\forall }x\in L$, $x$ has a complement.

Theorem 3.3: In a bounded, distributive lattice, every element has at most one complement.

Proof: Consider a bounded distributive lattice $L$ and elements $a,b,c\in R$. Suppose $b,c$ are both complements of $a$. We have:

which implies $b\le c$.

A similar argument can show that $c\le b$. Therefore $b=c$ and there is only one complement of $a$. $◼$

Boolean LatticesPermalink

Definition 3.4: A lattice $L$ is said to be Boolean if it is bounded, distributive, and complemented.

The most common example of a Boolean lattice is the powerset Boolean lattice. Given a positive integer $n$ and a set $[n]=\{1,2,\dots ,n\}$, the poset $B_n=(2^{[n]},\subseteq )$ is called a powerset boolean lattice of order $n$.

E.g. when $n=2$, $B_2=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$

Some textbooks simply call $B_n$ the “Boolean lattice of order $n$”.

Boolean AlgebrasPermalink

Definition 3.6: A Boolean algebra is a structure $(L,\wedge ,\vee ,\ast ,\mathrm{\perp },\mathrm{\top })$ such that:

• $(L,\wedge ,\vee ,\mathrm{\perp },\mathrm{\top })$ is a Boolean lattice
• $\ast$ is the unary complement operation.

The most common example of a Boolean algebra is the powerset Boolean algebra such as $(B_n,\cap ,\cup ,\stackrel{―}{},\varnothing ,[n])$

ReferencesPermalink

• https://arxiv.org/abs/2307.16671
• https://moraschini.github.io/files/teaching/OLBA.pdf