[Discrete Mathematics] lecture 7 - lattice

Overview

This lecture covers the lattice theory and boolean algebra.

Introduction to Lattice

Definition 1 (lattice) 
A poset $\left<L, \preceq \right>$ which every pair of elements in L has lub and glb is called a lattice.

lub is denoted as $+$ and glb is denoted as $*$.
We say that $a$ and $b$ join at $a+b$ and meet at $a*b$.

Example 1.

Consider a poset $\left<L, \preceq \right>$ where $L = {a, b, c, d}$ and $ \preceq = I_L ∪ {(a, c),(a, d),(b, c),(b, d)}$. Is this poset a lattice?

Example 2.

Consider a poset $\left<L, \preceq \right>$ where $L = {a, b, c, d}$ and $ \preceq = I_L ∪ {(a, d),(b, d),(c, a),(c, b),(c, d)}$. Is this poset a lattice?

The hasse diagram helps to visualize the poset.

Exercise

Prove $\min(a, \max(a,b)) = a$ using a lattice.

Theorem 1 
Let $\left<L, \preceq \right>$ be a lattice. Then the following properties hold: 
‣ $a * a = a$ 
‣ $a * b = b * a$ 
‣ $a * (b * c) = (a * b) * c$ 
‣ $a * (a+b) = a$ 
‣ $a+a = a$ 
‣ $a+b = b+a$ 
‣ $a+(b+c) = (a+b)+c$ 
‣ $a+(a*b) = a$

These properties are Idempotent, Commutative, Associative, Absorption. Note that distributivity is not a property of lattice.

Theorem 2 
Let $\left<L, \preceq \right>$ be a lattice.
Then $\forall a,b \in L, a \preceq b$ if and only if $a*b = a$ (or $a+b = b$).

Theorem 3 
Let $\left<L, \preceq \right>$ be a lattice.
Then $\forall a,b \in L, a*b = a \Leftrightarrow a+b=b$

Theorem 4 
Let $\left<L, \preceq \right>$ be a lattice. Then $\forall a,b,c \in L$ if $b \preceq c$, then $ab \preceq ac$ and $ a+b \preceq a+c$.

Theorem 5 
Let $\left<L, \preceq \right>$ be a lattice. Then $\forall a,b,c \in L$ , $a+(bc) \preceq (a+b)(a+c)$ and $(ab)+(a*c) \preceq a(b+c)$

Theorem 6 
Let $\left<A, *, +\right>$ be an algebra with two binary operations $*$ and $+$. If the following conditions hold, then there exists a lattice $\left<A, \preceq \right>$ s.t. $ * $ is a glb and $+$ is a lub, and $\preceq$ is defined as $\preceq = {(x, y) | x,y \in A, x * y = x (\text{or} ; x+y=y)}$. 
‣ $x * x = x$ 
‣ $x * y = y * x$ 
‣ $x * (y * z) = (x * y) * z$ 
‣ $x * (x+y) = x$ 
‣ $x+x = x$ 
‣ $x+y = y+x$ 
‣ $x+(y+z) = (x+y)+z$ 
‣ $x+(x*y) = x$

Proof?

Start by showing that $\preceq$ is a partial order. Then show that $*$ and $+$ are glb and lub respectively.

This theorem is important because it shows that we can construct a lattice from an algebra with two binary operations. Now, a lattice can be seen as a special case of algebra.

Definition 2 
A lattice is an algebraic structure $\left<L, * , +\right>$ with two binary operations $ * $ and $+$ that are both commutative and associative, and satisfy the absorption laws.

Note that the idempotent law can be derived from the absorption law.

 

So far we discussed how a lattice can be defined - with a poset or as an algebraic structure. Now, we would like to focus more on the lattice itself.

Boolean Lattice

Bounded Lattice

Definition 3
The least and the greatest elements of a lattice, if they exist, are called the bounds of the lattice, and are denoted by 0 and 1, respectively. 

Definition 4
A lattice is called a bounded lattice if it has the least element and the greatest element.

Example: $\left<D_6 , \preceq\right>$ is a bounded lattice where the greatest element is $6$ and the least element is $1$

 

Note: $D_n$ denotes the set of all divisors of $n$

Complemented lattice

If a lattice is bounded, we can define a complement of the lattice

Definition 5
In a bounded lattice $\left<L, ∗, +, 0, 1\right>$ an element $b \in L$ is called a complement of an element $a \in L$ if $a ∗ b = 0$ and $a + b = 1$.

Theorem 7
In a bounded lattice $\left<L, ∗, +, 0, 1\right>$ $1$ is the only complement of $0$ and $0$ is the only complement of $1$. 

Definition 7
If every element in  $\left<L, ∗, +, 0, 1\right>$ has at least one complement, it is call a complemented lattice.

 

Example: In $\left<D_6 , \preceq\right>$, $2$ is a complement of $3$

Sublattice

Definition 6
Let  $\left<L, ∗, +\right>$ be a lattice and let $S$ be a subset of $L$. The algebra  $\left<S, ∗, +\right>$ is a sublattice of  $\left<L, ∗, +\right>$ if and only if,
‣ $\forall a, b \in S$, $ a ∗ b \in S$ and $a + b \in S$ (that is, $S$ is closed under $∗$ and $+$)
‣ $ 2 $ the $ a ∗ b $ and  $ a + b $ of  $ S $ must be the same as the  $ a ∗ b $ and  $ a + b $ of $ L $

 

Boolean Lattice

Definition 8
A lattice  $\left<L, ∗, +, 0, 1\right>$ is called a distributive lattice if $\forall a, b, c \in L, a ∗ (b + c) = (a ∗ b) + (a ∗ c)$ and $a + (b ∗ c) = (a + b) ∗ (a + c)$.

Definition 9
A complemented and distributive lattice is called a boolean lattice.

 

Theorem 8
Let $\left<L, ∗, +\right>$ be a lattice.
$$\begin{align*} & \forall a,b,c \in L, \: a ∗ (b + c) = (a ∗ b) + (a ∗ c)\\&\Leftrightarrow \forall a,b,c \in L , \:   a + (b ∗ c) = (a + b) ∗ (a + c)\end{align*}$$