Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section19.4Exercises

1

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

2

Draw the diagram for the set of positive integers that are divisors of 30. Is this poset a Boolean algebra?

3

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

4

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

5

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

6

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

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

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

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

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

7

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

8

Prove or disprove that the two circuits shown are equivalent.

<<SVG image is unavailable, or your browser cannot render it>>

9

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

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.

<<SVG image is unavailable, or your browser cannot render it>>

11

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

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\), as in Theorem 19.14, by \(a \preceq b\) if \(a \vee b = b\). Prove that the greatest lower bound of \(a\) and \(b\) is \(a \wedge b\).

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\), show that the least upper bound of \(H\) and \(K\) is the subgroup generated by \(H \cup K\).

14

Let \(R\) be a ring and suppose that \(X\) is the set of ideals of \(R\). Show that \(X\) is a poset ordered by set-theoretic inclusion, \(\subseteq\). 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\). Prove that the set of ideals of \(R\) is a lattice under these operations.

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

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

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

  4. \(I' = O\) and \(O' = I\).

  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 19.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. \end{align*} Prove that \(B\) is a commutative ring under these operations satisfying \(a^2 = a\) for all \(a \in B\).

18

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

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

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

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

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

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\). Show that \(L \times M\) is a lattice under this partial order.