# Lattices

### Lattices as Posets

A partially ordered set $$\require{AMSsymbols}{\left( {L,\preccurlyeq} \right)}$$ is called a lattice if every pair of elements $$a$$ and $$b$$ in $$L$$ has both a least upper bound $$\left( {LUB} \right)$$ and a greatest lower bound $$\left( {GLB} \right).$$

The least upper bound is also called the join of $$a$$ and $$b,$$ denoted by $$a \lor b.$$ The greatest lower bound is also called the meet of $$a$$ and $$b,$$ and is denoted by $$a \land b.$$

If $${\left( {L,\preccurlyeq} \right)}$$ is a lattice and $$a,b,c,d \in L,$$ then the meet and join have the following order properties:

1. $$a \land b \preccurlyeq \left\{ {a,b} \right\} \preccurlyeq a \lor b$$
2. $$a \preccurlyeq b \text{ if and only if } a \land b = a$$
3. $$a \preccurlyeq b \text{ if and only if } a \lor b = b$$
4. $$\text{If } a \preccurlyeq b, \text{ then } a \land c \preccurlyeq b \land c\,$$ $$\text{and } a \lor c \preccurlyeq b \lor c$$
5. $$\text{If } a \preccurlyeq b \text{ and } c \preccurlyeq d, \text{ then } a \land c \preccurlyeq b \land d\,$$ $$\text{and } a \lor c \preccurlyeq b \lor d$$

By the definition of $$LUB$$ and $$GLB,$$ the join and meet, if they exist, are unique. Hence, we can consider them as binary operations on a lattice. This leads to an alternative definition of lattice.

### Lattices as Algebraic Structures

A lattice can also be defined as an algebra $$\left( {L, \land, \lor } \right)$$ on a set $$L$$ with two binary operations $$\land$$ (meet) and $$\lor$$ (join). The algebra satisfies the following identities:

1. Commutativity: $$a \land b = b \land a;\;$$ $$a \lor b = b \lor a.$$
2. Associativity: $$\left( {a \land b} \right) \land c = a \land \left( {b \land c} \right);\;$$ $$\left( {a \lor b} \right) \lor c = a \lor \left( {b \lor c} \right).$$
3. Idempotence: $$a \land a = a;\;$$ $$a \lor a = a.$$
4. Absorption: $$a \land \left( {a \lor b} \right) = a;\;$$ $$a \lor \left( {a \land b} \right) = a,$$

where $$a,b,c \in L.$$

Both definitions of a lattice are equivalent.

### Examples of Lattices

#### Partially Ordered Set $$\left({\mathcal{P}\left(\left\{ {1,2,3} \right\}\right), \subseteq}\right)$$

The poset consisting of all the subsets of $$A = \left\{ {1,2,3} \right\}$$ under the relation $$\subseteq$$ forms a lattice.

Every pair of elements in $$\mathcal{P}\left({A}\right)$$ has a join and a meet. The join of two subsets is defined as their union, and the meet is defined as the intersection of the subsets. For example,

$\mathbf{\text{join}}:\;\left\{ 1 \right\} \lor \left\{ 2 \right\} = \left\{ 1 \right\} \cup \left\{ 2 \right\} = \left\{ {1,2} \right\};$

$\mathbf{\text{meet}}:\;\left\{ 1 \right\} \land \left\{ 2 \right\} = \left\{ 1 \right\} \cap \left\{ 2 \right\} = \varnothing .$

This result can be generalized to any set of $$n$$ elements. So the power set $$\mathcal{P}\left({A}\right)$$ of any set $$A$$ under the subset ordering $$\subseteq$$ forms a lattice.

#### Partially Ordered Set $$\left( {{D_{60}},\mid} \right)$$

The poset consisting of all the divisors of $$60,$$ ordered by divisibility, is also a lattice. The divisors of the number $$60$$ are represented by the set

${{D_{60}} \text{ = }}\kern0pt{\left\{ {1,2,3,4,5,6,10,12,15,20,30,60} \right\}.}$

The join of two elements $$a$$ and $$b$$ is their least common multiple $${LCM} \left({a,b}\right),$$ and the meet is their greatest common divisor $${GCD} \left({a,b}\right).$$ For example,

$\mathbf{\text{join}}:\;6 \lor 10 = LCM(6,10) = 30;$

$\mathbf{\text{meet}}:\;6 \land 10 = GCD(6,10) = 2.$

In general, any set of natural numbers ordered by the divisibility relation “|” forms a lattice.

#### Partition Lattice of a $$4$$-Element Set

A partition $$P$$ of a set $$A$$ is a set of non-empty pairwise disjoint subsets (blocks) $${A_1},{A_2},\ldots,{A_n}$$ such that

• The union of the blocks $$A_i$$ in $$P,$$ where $$1 \le i \le n,$$ is equal to $$A.$$ $\bigcup\limits_{i = 1}^n {{A_i}} = {A_1} \cup {A_2} \cup \ldots \cup {A_n} = A$
• The partition $$P$$ does not contain the empty set $$\varnothing.$$ ${A_i} \ne \varnothing \;\forall \,i$
• The intersection of any distinct blocks in $$P$$ is empty. ${A_i} \cap {A_j} = \varnothing \;\forall \,i \ne j$

We can introduce the refinement order on the set of all partitions of $$A$$. A partition $$Q$$ is defined as a refinement of a partition $$P$$ if every block in $$Q$$ is a subset of a block in $$P.$$ The partition $$Q$$ is said to be finer than $$P,$$ and respectively, the partition $$P$$ is said to be coarser than $$Q.$$ This ordering is denoted as $$Q \preccurlyeq P.$$

The “finer than” relation on the set of partitions of $$A$$ is a partial order. Every pair of partitions has a least upper bound and a greatest lower bound, so this ordering is a lattice. The Hasse diagram below represents the partition lattice on a set of $$4$$ elements.

The meet of two partitions is their common refinement, and the join of two partitions is their finest common coarsening. For example, let

${{P_1} = \left\{ {\left\{ {a,d} \right\},\left\{ b \right\},\left\{ c \right\}} \right\},\;\;}\kern0pt{{P_2} = \left\{ {\left\{ a \right\},\left\{ {b,c} \right\},\left\{ d \right\}} \right\}.}$

Then

$\mathbf{\text{join}}:\;{P_1} \lor {P_2} = \left\{ {\left\{ {a,d} \right\},\left\{ {b,c} \right\}} \right\};$

${\mathbf{\text{meet}}:\;{P_1} \land {P_2} \text{ = }}\kern0pt{\left\{ {\left\{ a \right\},\left\{ b \right\},\left\{ c \right\},\left\{ d \right\}} \right\}.}$

#### Some Other Examples of Lattices

• Every totally ordered set $$\left({A, \preccurlyeq}\right)$$ is a lattice. If $$a,b \in A$$ and $$a \preccurlyeq b,$$ then ${a \lor b = b,\;\;}\kern0pt{a \land b = a.}$
• The set of $$n-$$dimensional vectors over natural numbers $$\mathbb{N}$$ with the componentwise relation $$\le$$ forms a lattice. Let $$\mathbf{a} = \left( {{a_1},{a_2}, \ldots ,{a_n}} \right)$$ and $$\mathbf{b} = \left( {{b_1},{b_2}, \ldots ,{b_n}} \right)$$ be two vectors. We define $\mathbf{a} \le \mathbf{b} \;\text{ if } \;\forall\; i : {a_i} \le {b_i}.$ The join and meet of two vectors correspond to componentwise maximum and minimum. For example, if $$\mathbf{a} = \left( {1,2,3} \right),$$ $$\mathbf{b} = \left( {4,5,6} \right),$$ then $\mathbf{a} \lor \mathbf{b} = \left( {4,5,6} \right) = \mathbf{b};$ $\mathbf{a} \land \mathbf{b} = \left( {1,2,3} \right) = \mathbf{a}.$
• The set of real-valued functions on the interval $$\left[ {0,1} \right]$$ ordered by the condition ${f \le g \;\text{ if }\;}\kern0pt{f\left( t \right) \le g\left( t \right) \;\forall\; t \in \left[ {0,1} \right],}$ is also a lattice. The join and meet of two functions $$f$$ and $$g$$ are defined as follows: $f \lor g = \max \left\{ {f\left( t \right), g\left( t \right)} \right\};$ $f \land g = \min \left\{ {f\left( t \right), g\left( t \right)} \right\}.$

### Types of Lattices

In this section we consider some special lattices.

#### Complete Lattices

A partially ordered set $$\require{AMSsymbols}{\left( {L,\preccurlyeq} \right)}$$ is called a complete lattice if all its subsets have both a join and a meet. This is a stronger condition than for a general lattice (where every pair of elements must have a join and a meet).

Any non-empty finite lattice is complete. Among other examples to be mentioned are

• The power set $$\mathcal{P}\left({A}\right)$$ of a set $$A$$ ordered by the subset relation $$\subseteq.$$
• A set of natural numbers $$\mathbb{N}$$ ordered by the divisibility relation “|”.

#### Bounded Lattices

A lattice $${\left( {L,\preccurlyeq} \right)}$$ is said to be bounded if it has a greatest element and a least element. The greatest and least elements are denoted by $$1$$ and $$0$$ respectively.

Let $$a$$ be any element in $$L.$$ Then the following identities hold:

${0 \lor a = a \lor 0 = a;\;\;}\kern0pt{0 \land a = a \land 0 = 0;}$

${1 \land a = a \land 1 = a;\;\;}\kern0pt{1 \lor a = a \lor 1 = 1.}$

It is obvious here that $$0 \preccurlyeq a \preccurlyeq 1.$$

An example of a bounded lattice is the power set $$\mathcal{P}\left({A}\right)$$ containing all subsets of a set $$A$$ ordered by the relation $$\subseteq.$$ The greatest element of the lattice is the set $$A$$ itself, and the least element is empty set $$\varnothing.$$

#### Complemented Lattices

Suppose $${\left( {L,\preccurlyeq} \right)}$$ is a bounded lattice with greatest element $$1$$ and least element $$0.$$ Let $$a, b \in L.$$ An element $$b$$ is called a complement of $$a$$ if

$a \land b = 0 \;\text{ and } \;a \lor b = 1.$

A bounded lattice $${\left( {L,\preccurlyeq} \right)}$$ is said to be complemented if every element in $$L$$ has a complement.

In particular, the complement of $$0$$ is $$1,$$ and the complement of $$1$$ is $$0.$$

An example of a complemented lattice is the poset $$\left( {{D_{30}}, \mid} \right),$$ where $$D_{30}$$ is the set of divisors of $$30$$ and “|” is the divisibility relation.

Every element in $$D_{30}$$ has a complement:

${1 \to 30,\;\;}\kern0pt{2 \to 15,\;\;}\kern0pt{3 \to 10,\;\;}\kern0pt{5 \to 6,\;\;}\kern0pt{6 \to 5,\;\;}\kern0pt{10 \to 3,\;\;}\kern0pt{15 \to 2,\;\;}\kern0pt{30 \to 1.}$

Indeed, it is easy to see that

${2 \lor 15 = LCM(2,15) = 30;\;\;}\kern0pt{ 2 \land 15 = GCD(2,15) = 1.}$

The same is true for all other elements of $$D_{30}.$$

Note that not all lattices of kind $$\left( {{D_n},|} \right)$$ are complemented. For example, the lattice $$\left( {{D_{20}},|} \right)$$ is not complemented.

#### Distributive Lattices

A lattice $${\left( {L,\preccurlyeq} \right)}$$ is called distributive if (and only if) for any elements $$a, b$$ and $$c$$ in $$L$$ the following distributive properties hold:

$a \lor \left( {b \land c} \right) = \left( {a \lor b} \right) \land \left( {a \lor c} \right);$

$a \land \left( {b \lor c} \right) = \left( {a \land b} \right) \lor \left( {a \land c} \right).$

For any set $$A,$$ the power set lattice $$\left({\mathcal{P}\left({A}\right), \subseteq}\right)$$ is a distributive lattice.

The figure below shows the pentagon lattice and the diamond lattice that are examples of non-distributive lattices.

#### Modular Lattices

A lattice $${\left( {L,\preccurlyeq} \right)}$$ is called modular if for any elements $$a, b$$ and $$c$$ in $$L$$ the following property is satisfied:

$a \preccurlyeq b \text{ implies } a \lor \left( {c \land b} \right) = \left( {a \lor c} \right) \land b.$

An example of a modular lattice is the diamond lattice shown above. Consider, for example, two comparable elements $$a$$ and $$1,$$ so $$a \preccurlyeq 1.$$ By taking $$b$$ as the $$3\text{rd}$$ element, we have

$a \preccurlyeq 1 \text{ implies } a \lor \left( {b \land 1} \right) = \left( {a \lor b} \right) \land 1.$

Calculate the joins and meets:

${LHS = a \lor \left( {b \land 1} \right) }={ a \lor b }={ 1;}$

${RHS = \left( {a \lor b} \right) \land 1 }={ 1 \land 1 }={ 1.}$

As it can be seen, $$LHS = RHS.$$

#### Boolean Lattices

A complemented distributive lattice is called a Boolean lattice.

An example of a Boolean lattice is the power set lattice $$\left({\mathcal{P}\left({A}\right), \subseteq}\right)$$ defined on a set $$A.$$

Since a Boolean lattice is complemented (and, hence, bounded), it contains a greatest element $$1$$ and a least element $$0$$. As any lattice, a Boolean lattice is equipped with two binary operations – join $$\lor$$ and meet $$\land.$$ Complementation (if it is unique) can also be regarded as a unary operation denoted by $$\bar{\;}$$ or $$\,^c.$$ Given the operational notation, a Boolean lattice is considered as a Boolean algebra and is denoted by $$\left( {B,\lor, \land, \bar{\;}} \right).$$

The simplest Boolean algebra is defined on the set of two elements $$B=\left\{0,1\right\}$$ and obeys the following rules:

• Join (Boolean addition) operations: $0 \lor 0 = 0 + 0 = 0;$ $0 \lor 1 = 0 + 1 = 1;$ $1 \lor 0 = 1 + 0 = 1;$ $1 \lor 1 = 1 + 1 = 1.$
• Meet (Boolean product) operations: $0 \land 0 = 0 \cdot 0 = 0;$ $0 \land 1 = 0 \cdot 1 = 0;$ $1 \land 0 = 1 \cdot 0 = 0;$ $1 \land 1 = 1 \cdot 1 = 1.$
• Complementation operations: $\bar{0} = 1;$ $\bar{1} = 0.$

This simple arithmetic results in the following Boolean identities, where $$a \in \left\{0,1\right\}:$$

 $$a \cdot a = a$$ $$a + a = a$$ $$a \cdot \bar{a} = 0$$ $$a + \bar{a} = 1$$ $$1 \cdot a = a$$ $$1 + a = 1$$ $$0 \cdot a = 0$$ $$0 + a = a$$
 $$a \cdot a = a$$ $$a + a = a$$ $$a \cdot \bar{a} = 0$$ $$a + \bar{a} = 1$$ $$1 \cdot a = a$$ $$1 + a = 1$$ $$0 \cdot a = 0$$ $$0 + a = a$$

The two-element Boolean algebra is used in mathematical logic and has many applications in computer science and digital circuitry.

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Which of the Hasse diagrams represent a lattice?

### Example 2

Which of the Hasse diagrams represent a lattice?

### Example 3

Show that the diamond lattice is not distributive.

### Example 4

Show that the pentagon lattice is not distributive.

### Example 5

Simplify the Boolean expressions:
1. $$ab + a\bar{b}$$
2. $$a + ab$$
3. $$a\left({\bar{a} + b}\right)$$
Here $$a,b \in \left\{{0,1}\right\}.$$

### Example 6

Simplify the Boolean expressions:
1. $$a + \bar{a}b$$
2. $$\left({\bar{a} + \bar{b}}\right)\left({\bar{a} + b}\right)$$
3. $$\left({a + b}\right)\left({a + c}\right)$$
Here $$a,b,c \in \left\{{0,1}\right\}.$$

### Example 1.

Which of the Hasse diagrams (Figure $$7$$) represent a lattice?

Solution.

1. The elements $$b$$ and $$c$$ do not have a least upper bound (lub). The upper bounds for them are $$d, e$$ and $$f.$$ The element $$f$$ cannot be the lub, since $$d \preccurlyeq f$$ and $$e \preccurlyeq f.$$ However, the elements $$d$$ and $$e$$ are not comparable, so we cannot identify the least of them. Hence, this poset is not a lattice.
2. This poset is not a lattice since the elements $$a$$ and $$b$$ have no greatest lower bound (glb).
3. A lattice.
4. A lattice.

### Example 2.

Which of the Hasse diagrams (Figure $$8$$) represent a lattice?

Solution.

1. A lattice.
2. The elements $$b$$ and $$c$$ have no least upper bound (lub). The upper bounds for them are $$d$$ and $$e.$$ However they are incomparable, so we cannot identify which of them is the lub. Therefore, this poset is not a lattice.
3. This poset is not a lattice since the elements $$e$$ and $$f$$ have no lub.
4. A lattice.

### Example 3.

Show that the diamond lattice is not distributive.

Solution.

To prove that a lattice $${\left( {L,\preccurlyeq} \right)}$$ is not distributive, we must show that there are $$3$$ elements in $$L$$ such that a distributive law does not hold for them.

Let’s take the elements $$a, b$$ and $$c,$$ and consider the distributive law

$a \land \left( {b \lor c} \right) = \left( {a \land b} \right) \lor \left( {a \land c} \right).$

For the diamond lattice, we have

${LHS = a \land \left( {b \lor c} \right) }={ a \land 1 }={ a.}$

${RHS = \left( {a \land b} \right) \lor \left( {a \land c} \right) }={ 0 \lor 0 }={ 0.}$

As it can be seen, $$LHS \ne RHS,$$ which proves that the diamond lattice is not distributive.

### Example 4.

Show that the pentagon lattice is not distributive.

Solution.

We take the elements $$a, b, c$$ and check for the distributive law

$b \land \left( {c \lor a} \right) = \left( {b \land c} \right) \lor \left( {b \land a} \right).$

Calculate the left and right sides of the identity:

${LHS = b \land \left( {c \lor a} \right) }={ b \land 1 }={ b.}$

${RHS = \left( {b \land c} \right) \lor \left( {b \land a} \right) }={ 0 \lor a }={ a.}$

Since $$LHS \ne RHS,$$ the distributive law fails for pentagon lattice.

### Example 5.

Simplify the Boolean expressions:
1. $$ab + a\bar{b}$$
2. $$a + ab$$
3. $$a\left({\bar{a} + b}\right)$$
Here $$a,b \in \left\{{0,1}\right\}.$$

Solution.

Given that Boolean algebras satisfy the commutative, associative, and distributive laws, we have

1. $$ab + a\bar{b} = ab + a\left( {1 – b} \right)$$ $$\require{cancel}{= \cancel{ab} + a – \cancel{ab} = a.}$$
2. We can write $$a + ab = a\left({1 + b}\right).$$ Since $$1 + b = 1,$$ we obtain ${a + ab = a\left( {1 + b} \right) }={ a \cdot 1 }={ a.}$
3. $$a\left( {\bar{a} + b} \right) = a\bar{a} + ab.$$ The first term is given by ${a\bar{a} = a\left( {1 – a} \right) }={ a – aa }={ a – a }={ 0.}$ Hence, $$a\left( {a + b} \right) = ab.$$

### Example 6.

Simplify the Boolean expressions:
1. $$a + \bar{a}b$$
2. $$\left({\bar{a} + \bar{b}}\right)\left({\bar{a} + b}\right)$$
3. $$\left({a + b}\right)\left({a + c}\right)$$
Here $$a,b,c \in \left\{{0,1}\right\}.$$

Solution.

Recall that Boolean algebras satisfy the commutative, associative, and distributive laws.

1. We proved in the previous example that $$a + ab = a.$$ Therefore, we can write $a + \bar{a}b = a + ab + \bar{a}b.$ Using the identities $$aa = a,$$ $$a + \bar{a} = 1,$$ $$a\bar{a} = 0,$$ and $$1 \cdot a = a,$$ we have ${a + \bar{a}b = a + ab + \bar{a}b }={ aa + ab + a\bar{a} + \bar{a}b }={ a\left( {a + b} \right) + \bar{a}\left( {a + b} \right) }={ \left( {a + \bar{a}} \right)\left( {a + b} \right) }={ 1 \cdot \left( {a + b} \right) }={ a + b.}$
2. We write this expression as follows: ${\left( {\bar{a} + \bar{b}} \right)\left( {\bar{a} + b} \right) }={ \bar{a}\bar{a} + \bar{b}\bar{a} + \bar{a}b + \bar{b}b.}$ Since $$\bar{a}\bar{a} = \bar{a},$$ $$\bar{b}b = 0,$$ $$b + \bar{b} = 1,$$ and $$1 \cdot \bar{a} = \bar{a},$$ we get ${\left( {\bar{a} + \bar{b}} \right)\left( {\bar{a} + b} \right) }={ \bar{a}\bar{a} + \bar{b}\bar{a} + \bar{a}b + \bar{b}b }={ \bar{a} + \bar{a}\bar{b} + \bar{a}b + 0 }={ \bar{a}\left( {1 + \bar{b} + b} \right) }={ \bar{a}\left( {1 + 1} \right) }={ \bar{a} \cdot 1 }={ \bar{a}.}$
3. We apply here the following identities: $$aa = a,$$ $$1 + b = 1,$$ $$1 \cdot a = a.$$ This yields: ${\left( {a + b} \right)\left( {a + c} \right) }={ aa + ac + ba + bc }={ a + ac + ba + bc }={ a\left( {1 + c} \right) + ab + bc }={ a \cdot 1 + ab + bc }={ a + ab + bc }={ a\left( {1 + b} \right) + bc }={ a \cdot 1 + bc }={ a + bc.}$