# Lattices

## 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 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. This poset is not a lattice (same as $$1$$).
4. A lattice.

### Example 2.

Which of the Hasse diagrams 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.$