Skip to main content

Exercises 18.5 Exercises

1.

Draw the lattice diagram for the power set of \(X = \{ a, b, c, d \}\) with the set inclusion relation, \(\subset\text{.}\)

2.

Draw the diagram for the set of positive integers that are divisors of \(30\text{.}\) Is this poset a Boolean algebra?

3.

Draw a diagram of the lattice of subgroups of \({\mathbb Z}_{12}\text{.}\)

4.

Let \(B\) be the set of positive integers that are divisors of \(210\text{.}\) Define an order on \(B\) by \(a \preceq b\) if \(a \mid b\text{.}\) Prove that \(B\) is a Boolean algebra. Find a set \(X\) such that \(B\) is isomorphic to \({\mathcal P}(X)\text{.}\)

Hint.

What are the atoms of \(B\text{?}\)

5.

Prove or disprove: \({\mathbb Z}\) is a poset under the relation \(a \preceq b\) if \(a \mid b\text{.}\)

Hint.

False.

6.

Draw the switching circuit for each of the following Boolean expressions.

  1. \(\displaystyle (a \vee b \vee a') \wedge a\)

  2. \(\displaystyle (a \vee b)' \wedge (a \vee b)\)

  3. \(\displaystyle a \vee (a \wedge b)\)

  4. \(\displaystyle (c \vee a \vee b) \wedge c' \wedge (a \vee b)'\)

Hint.

(a) \((a \vee b \vee a') \wedge a\)

A graph from left to right which splits into three paths, a b, and b' and then rejoins into a single path and goes through a.

(c) \(a \vee (a \wedge b)\)

A graph from left to right which splits into two paths and then rejoins.  The top path is a then b.  The bottom path is a.
7.

Draw a circuit that will be closed exactly when only one of three switches \(a\text{,}\) \(b\text{,}\) and \(c\) are closed.

8.

Prove or disprove that the two circuits shown are equivalent.

Two graphs.  The graph on the left splits into three paths, a-b-c, a'-b, and a-c', and then rejoins.  The graph on the right splits into two paths, a-b and a-c', and then rejoins.
Hint.

Not equivalent.

9.

Let \(X\) be a finite set containing \(n\) elements. Prove that \(|{\cal P}(X)| = 2^n\text{.}\) Conclude that the order of any finite Boolean algebra must be \(2^n\) for some \(n \in {\mathbb N}\text{.}\)

10.

For each of the following circuits, write a Boolean expression. If the circuit can be replaced by one with fewer switches, give the Boolean expression and draw a diagram for the new circuit.

Three graphs.  The top graph from left to right is a', then splits into a top path a-b' and a on the bottom and then rejoins.  The middle graph from left to right splits into two paths with a on the top path and b on the bottom path.  The graph then rejoins and splits into three paths with the top path a-b, the middle path a', and the bottom path a'-b.  The graph then rejoins.  The bottom graph splits into three paths with top path a-b-c, middle path a'-b'-c, and the bottom path a-b'-c'.  The paths then rejoin.
Hint.

(a) \(a' \wedge [(a \wedge b') \vee b] = a \wedge (a \vee b) \text{.}\)

11.

Prove or disprove: The set of all nonzero integers is a lattice, where \(a \preceq b\) is defined by \(a \mid b\text{.}\)

12.

Let \(L\) be a nonempty set with two binary operations \(\vee\) and \(\wedge\) satisfying the commutative, associative, idempotent, and absorption laws. We can define a partial order on \(L\text{,}\) as in TheoremĀ 18.14, by \(a \preceq b\) if \(a \vee b = b\text{.}\) Prove that the greatest lower bound of \(a\) and \(b\) is \(a \wedge b\text{.}\)

13.

Let \(G\) be a group and \(X\) be the set of subgroups of \(G\) ordered by set-theoretic inclusion. If \(H\) and \(K\) are subgroups of \(G\text{,}\) show that the least upper bound of \(H\) and \(K\) is the subgroup generated by \(H \cup K\text{.}\)

14.

Let \(R\) be a ring and suppose that \(X\) is the set of ideals of \(R\text{.}\) Show that \(X\) is a poset ordered by set-theoretic inclusion, \(\subset\text{.}\) Define the meet of two ideals \(I\) and \(J\) in \(X\) by \(I \cap J\) and the join of \(I\) and \(J\) by \(I + J\text{.}\) Prove that the set of ideals of \(R\) is a lattice under these operations.

Hint.

Let \(I, J\) be ideals in \(R\text{.}\) We need to show that \(I + J = \{ r + s : r \in I \text{ and } s \in J \}\) is the smallest ideal in \(R\) containing both \(I\) and \(J\text{.}\) If \(r_1, r_2 \in I\) and \(s_1, s_2 \in J\text{,}\) then \((r_1 + s_1) + (r_2 + s_2) = (r_1 + r_2) +(s_1 + s_2)\) is in \(I + J\text{.}\) For \(a \in R\text{,}\) \(a(r_1 + s_1) = ar_1 + as_1 \in I + J\text{;}\) hence, \(I + J\) is an ideal in \(R\text{.}\)

15.

Let \(B\) be a Boolean algebra. Prove each of the following identities.

  1. \(a \vee I = I\) and \(a \wedge O = O\) for all \(a \in B\text{.}\)

  2. If \(a \vee b = I\) and \(a \wedge b = O\text{,}\) then \(b = a'\text{.}\)

  3. \((a')'=a\) for all \(a \in B\text{.}\)

  4. \(I' = O\) and \(O' = I\text{.}\)

  5. \((a \vee b)' = a' \wedge b'\) and \((a \wedge b)' = a' \vee b'\) (De Morgan's laws).

16.

By drawing the appropriate diagrams, complete the proof of TheoremĀ 18.30 to show that the switching functions form a Boolean algebra.

17.

Let \(B\) be a Boolean algebra. Define binary operations \(+\) and \(\cdot\) on \(B\) by

\begin{align*} a + b & = (a \wedge b') \vee (a' \wedge b)\\ a \cdot b & = a \wedge b\text{.} \end{align*}

Prove that \(B\) is a commutative ring under these operations satisfying \(a^2 = a\) for all \(a \in B\text{.}\)

18.

Let \(X\) be a poset such that for every \(a\) and \(b\) in \(X\text{,}\) either \(a \preceq b\) or \(b \preceq a\text{.}\) Then \(X\) is said to be a totally ordered set.

  1. Is \(a \mid b\) a total order on \({\mathbb N}\text{?}\)

  2. Prove that \({\mathbb N}\text{,}\) \({\mathbb Z}\text{,}\) \({\mathbb Q}\text{,}\) and \({\mathbb R}\) are totally ordered sets under the usual ordering \(\leq\text{.}\)

Hint.

(a) No.

19.

Let \(X\) and \(Y\) be posets. A map \(\phi : X \rightarrow Y\) is order-preserving if \(a \preceq b\) implies that \(\phi(a) \preceq \phi(b)\text{.}\) Let \(L\) and \(M\) be lattices. A map \(\psi: L \rightarrow M\) is a lattice homomorphism if \(\psi( a \vee b ) = \psi(a) \vee \psi(b)\) and \(\psi( a \wedge b ) = \psi(a) \wedge \psi(b)\text{.}\) Show that every lattice homomorphism is order-preserving, but that it is not the case that every order-preserving homomorphism is a lattice homomorphism.

20.

Let \(B\) be a Boolean algebra. Prove that \(a = b\) if and only if \((a \wedge b') \vee ( a' \wedge b) = O\) for \(a, b \in B\text{.}\)

Hint.

\(( \Rightarrow)\text{.}\) \(a = b \Rightarrow (a \wedge b') \vee (a' \wedge b) = (a \wedge a') \vee (a' \wedge a) = O \vee O = O\text{.}\) \(( \Leftarrow)\text{.}\) \(( a \wedge b') \vee (a' \wedge b) = O \Rightarrow a \vee b = (a \vee a) \vee b = a \vee (a \vee b) = a \vee [I \wedge (a \vee b)] = a \vee [(a \vee a') \wedge (a \vee b)] = [a \vee (a \wedge b')] \vee [a \vee (a' \wedge b)] = a \vee [(a \wedge b') \vee (a' \wedge b)] = a \vee 0 = a\text{.}\) A symmetric argument shows that \(a \vee b = b\text{.}\)

21.

Let \(B\) be a Boolean algebra. Prove that \(a = O\) if and only if \((a \wedge b') \vee ( a' \wedge b) = b\) for all \(b \in B\text{.}\)

22.

Let \(L\) and \(M\) be lattices. Define an order relation on \(L \times M\) by \(( a, b) \preceq (c, d)\) if \(a \preceq c\) and \(b \preceq d\text{.}\) Show that \(L \times M\) is a lattice under this partial order.