Calculus

Set Theory

Set Theory Logo

Lattices

Solved Problems

Click or tap a problem to see the solution.

Example 1

Which of the Hasse diagrams represent a lattice?

Hasse diagrams for lattices and non-lattices - example 1.

Example 2

Which of the Hasse diagrams represent a lattice?

Hasse diagrams for lattices and non-lattices - example 2.

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.

Hasse diagrams for lattices and non-lattices - example 1.
Figure 8.
  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.

Hasse diagrams for lattices and non-lattices - example 2.
Figure 9.
  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.

Diamond lattice
Figure 10.

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.

Pentagon lattice
Figure 11.

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.\]
Page 1 Page 2