Lattices

Solved Problems

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.

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.

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

For the diamond lattice, we have

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

Solution.

We take the elements \(a, b, c\) and check for the distributive law

Calculate the left and right sides of the identity:

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

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.\)

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.\]