exercises-boolean.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section19.4Exercises

¶

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. Is this poset a Boolean algebra?

Hint

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 36. 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{.}$

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. $(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)'$

Hint

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

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

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.

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.

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

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