# Exercises1.1.3Exercises for Section 1.1

##### Exercise1

List four elements of each of the following sets:

1. $\{k \in \mathbb{P} \mid {k - 1} \textrm{ is a multiple of 7}\}$

2. $\{x \mid x \textrm{ is a fruit and its skin is normally eaten}\}$

3. $\{x \in \mathbb{Q}\mid \frac{1}{x} \in \mathbb{Z}\}$

4. $\{2n \mid n \in \mathbb{Z}, n < 0 \}$

5. $\{s \mid s = 1 + 2 + \cdots + n \textrm{ for some } n \in \mathbb{P}\}$

##### Exercise3

Describe the following sets using set-builder notation.

1. $\{ 5, 7, 9, \dots , 77, 79\}$

2. the rational numbers that are strictly between $-1$ and $1$

3. the even integers

4. $\{-18, -9,0,9, 18,27, \dots \}$

##### Exercise5

Let $A = \{0, 2, 3\}\text{,}$ $B = \{2, 3\}\text{,}$ and $C = \{1, 5, 9\}\text{.}$ Determine which of the following statements are true. Give reasons for your answers.

1. $3 \in A$

2. $\{3\} \in A$

3. $\{3\} \subseteq A$

4. $B\subseteq A$

5. $A\subseteq B$

6. $\emptyset \subseteq C$

7. $\emptyset \in A$

8. $A\subseteq A$

# Exercises1.2.4EXERCISES FOR SECTION 1.2

##### Exercise1

Let $A = \{0, 2, 3\}\text{,}$ $B = \{2, 3\}\text{,}$ $C = \{1, 5, 9\}\text{,}$ and let the universal set be $U = \{0, 1, 2, . . . , 9\}\text{.}$ Determine:

1. $A \cap B$

2. $A \cup B$

3. $B \cup A$

4. $A \cup C$

5. $A - B$

6. $B - A$

7. $A^c$

8. $C^c$

9. $A\cap C$

10. $A\oplus B$

##### Exercise3

Let $U= \{1, 2, 3, . . . , 9\}\text{.}$ Give examples of sets $A\text{,}$ $B\text{,}$ and $C$ for which:

1. $A\cap (B\cap C)=(A\cap B)\cap C$

2. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

3. $(A \cup B)^c= A^c\cap B^c$

4. $A \cup A^c = U$

5. $A \subseteq A\cup B$

6. $A\cap B \subseteq A$

##### Exercise5

What can you say about $A$ if $U = \{1, 2, 3, 4, 5\}\text{,}$ $B = \{2, 3\}\text{,}$ and (separately)

1. $A \cup B = \{1, 2, 3,4\}$

2. $A \cap B = \{2\}$

3. $A \oplus B = \{3, 4, 5\}$

##### Exercise7

Given that $U$ = all students at a university, $D$ = day students, $M$ = mathematics majors, and $G$ = graduate students. Draw Venn diagrams illustrating this situation and shade in the following sets:

1. evening students

# Exercises1.3.4EXERCISES FOR SECTION 1.3

##### Exercise1

Let $A = \{0, 2, 3\}\text{,}$ $B = \{2, 3\}\text{,}$ $C = \{1, 4\}\text{,}$ and let the universal set be $U = \{0, 1, 2, 3, 4\}\text{.}$ List the elements of

1. $A \times B$

2. $B \times A$

3. $A \times B\times C$

4. $U \times \emptyset$

5. $A \times A^c$

6. $B^2$

7. $B^3$

8. $B\times \mathcal{P}(B)$

##### Exercise3

List all two-element sets in $\mathcal{P}(\{a,b,c,d\})$

##### Exercise5

How many singleton (one-element) sets are there in $\mathcal{P}(A)$ if $\lvert A \rvert =n$ ?

##### Exercise7

Let $A = \{+,-\}$ and $B = \{00, 01, 10, 11\}\text{.}$

• List the elements of $A \times B$

• How many elements do $A ^4$ and $(A \times B)^3$ have?

##### Exercise9

Let $A$ and $B$ be nonempty sets. When are $A \times B$ and $B \times A$ equal?

# Exercises1.4.1Exercises for Section 1.4

##### Exercise1

Find the binary representation of each of the following positive integers by working through the algorithm by hand. You can check your answer using the sage cell above.

1. 31

2. 32

3. 10

4. 100

##### Exercise3

What positive integers have the following binary representations?

1. 10010

2. 10011

3. 101010

4. 10011110000

##### Exercise5

The number of bits in the binary representations of integers increases by one as the numbers double. Using this fact, determine how many bits the binary representations of the following decimal numbers have without actually doing the full conversion.

1. 2017

2. 4000

3. 4500

4. $2^{50}$

##### Exercise7

If a positive integer is a multiple of 100, we can identify this fact from its decimal representation, since it will end with two zeros. What can you say about a positive integer if its binary representation ends with two zeros? What if it ends in $k$ zeros?

# Exercises1.5.1Exercises

##### Exercise1

Calculate the following series:

1. $\sum_{i=1}^3 (2 + 3i)$

2. $\sum_{i=-2}^1 i^2$

3. $\sum_{j=0}^n 2^j\text{ }$ for $n= 1, 2, 3, 4$

4. $\sum_{k=1}^n (2k-1)$ for $n = 1, 2, 3, 4$

##### Exercise3

1. Express the formula $\sum_{i=1}^n \frac{1}{i(i+1)}= \frac{n}{n+1}$ without using summation notation.

2. Verify this formula for $n=3\text{.}$

3. Repeat parts (a) and (b) for $\sum_{i=1}^n i^3=\frac{n^2(n+1)^2}{4}$

##### Exercise5

Rewrite the following without summation sign for $n = 3\text{.}$ It is not necessary that you understand or expand the notation $\left( \begin{array}{c} n \\ k \\ \end{array} \right)$ at this point. $(x + y)^n= \sum_{k=0}^n \left( \begin{array}{c} n \\ k \\ \end{array} \right)x^{n-k}y^k\text{.}$

##### Exercise7

For any positive integer $k\text{,}$ let $A_k = \{x \in \mathbb{Q}:k-1 < x \leq k\}$ and $B_k = \{x \in \mathbb{Q}: -k < x < k\}\text{.}$ What are the following sets?

1. $\underset{i=1}{\overset{5}{\cup }}A_i$

2. $\underset{i=1}{\overset{5}{\cup }}B_i$

3. $\underset{i=1}{\overset{5}{\cap }}A_i$

4. $\underset{i=1}{\overset{5}{\cap }}B_i$

##### Exercise9

The symbol $\Pi$ is used for the product of numbers in the same way that $\Sigma$ is used for sums. For example, $\prod _{i=1}^5 x_i=x_1 x_2 x_3 x_4 x_5\text{.}$ Evaluate the following:

1. $\prod _{i=1}^3 i^2$

2. $\prod _{i=1}^3 (2i+1)$

# Exercises2.1.3Exercises

##### Exercise1

In horse racing, to bet the “daily double” is to select the winners of the first two races of the day. You win only if both selections are correct. In terms of the number of horses that are entered in the first two races, how many different daily double bets could be made?

##### Exercise3

A certain shirt comes in four sizes and six colors. One also has the choice of a dragon, an alligator, or no emblem on the pocket. How many different shirts could you order?

##### Exercise5

The Pi Mu Epsilon mathematics honorary society of Outstanding University wishes to have a picture taken of its six officers. There will be two rows of three people. How many different way can the six officers be arranged?

##### Exercise7

A clothing manufacturer has put out a mix-and-match collection consisting of two blouses, two pairs of pants, a skirt, and a blazer. How many outfits can you make? Did you consider that the blazer is optional? How many outfits can you make if the manufacturer adds a sweater to the collection?

##### Exercise9

(a) Suppose each single character stored in a computer uses eight bits. Then each character is represented by a different sequence of eight 0's and l's called a bit pattern. How many different bit patterns are there? (That is, how many different characters could be represented?)

(b) How many bit patterns are palindromes (the same backwards as forwards)?

(c) How many different bit patterns have an even number of 1's?

##### Exercise11

(a) Let $A = \{1, 2, 3, 4\}\text{.}$ Determine the number of different subsets of $A\text{.}$

(b) Let $A = \{1, 2, 3, 4, 5\}\text{.}$ Determine the number of proper subsets of $A$ .

##### Exercise13

Consider three persons, A, B, and C, who are to be seated in a row of three chairs. Suppose A and B are identical twins. How many seating arrangements of these persons can there be

1. If you are a total stranger?

2. If you are A and B's mother?

This problem is designed to show you that different people can have different correct answers to the same problem.

##### Exercise15

Suppose you have a choice of fish, lamb, or beef for a main course, a choice of peas or carrots for a vegetable, and a choice of pie, cake, or ice cream for dessert. If you must order one item from each category, how many different dinners are possible?

##### Exercise17

A questionnaire contains six questions each having yes-no answers. For each yes response, there is a follow-up question with four possible responses.

1. Draw a tree diagram that illustrates how many ways a single question in the questionnaire can be answered.

2. How many ways can the questionnaire be answered?

##### Exercise19

How many ways can you separate a set with $n$ elements into two nonempty subsets if the order of the subsets is immaterial? What if the order of the subsets is important?

# Exercises2.2.1Exercises

##### Exercise1

If a raffle has three different prizes and there are 1,000 raffle tickets sold, how many different ways can the prizes be distributed?

##### Exercise3

How many eight-letter words can be formed from the 26 letters in the alphabet? Even without concerning ourselves about whether the words make sense, there are two interpretations of this problem. Answer both.

##### Exercise5

The state finals of a high school track meet involves fifteen schools. How many ways can these schools be listed in the program?

##### Exercise7

All 15 players on the Tall U. basketball team are capable of playing any position.

1. How many ways can the coach at Tall U. fill the five starting positions in a game?

2. What is the answer if the center must be one of two players?

##### Exercise9

The president of the Math and Computer Club would like to arrange a meeting with six attendees, the president included. There will be three computer science majors and three math majors at the meeting. How many ways can the six people be seated at a circular table if the president does not want people with the same majors to sit next to one other?

##### Exercise11

Let $A = \{1, 2, 3, 4\} \text{.}$ Determine the cardinality of

1. $\{ (a_1,a_2) \mid a_1 \neq a_2 \}$

2. What is the answer to the previous part if $\lvert A \rvert = n$

3. If $\lvert A \rvert =n\text{,}$ determine the number of $m$-tuples in $A\text{,}$ $m \leq n\text{,}$ where each coordinate is different from the other coordinates.

# Exercises2.3.1Exercises for Section 2.3

##### Exercise1

List all partitions of the set $A =\{a, b, c\}\text{.}$

##### Exercise3

A student, on an exam paper, defined the term partition the following way: “Let $A$ be a set. A partition of $A$ is any set of nonempty subsets $A_1, A_2, A_3, \dots$ of $A$ such that each element of $A$ is in one of the subsets.” Is this definition correct? Why?

##### Exercise5

Show that $\{\{2 n \mid n \in \mathbb{Z}\}, \{2 n + 1 \mid n \in \mathbb{Z}\}\}$ is a partition of $\mathbb{Z}\text{.}$ Describe this partition using only words.

##### Exercise7

A survey of 90 people, 47 of them played tennis and 42 of them swam. If 17 of the them participated in both activities, how many of them participated in neither?

##### Exercise9

1. Use the Two Set Inclusion-Exclusion Law to derive the Three Set Inclusion-Exclusion Law. Note: a knowledge of basic set laws is needed for this exercise.

2. State and derive the Inclusion-exclusion law for four sets.

Solution
##### Exercise11

The definition of $\mathbb{Q} = \{a/b \mid a, b \in \mathbb{Z}, b \neq 0\}$ given in Chapter 1 is awkward. If we use the definition to list elements in $\mathbb{Q}\text{,}$ we will have duplications such as $\frac{1}{2}\text{,}$ $\frac{-2}{-4}$ and $\frac{300}{600}$ Try to write a more precise definition of the rational numbers so that there is no duplication of elements.

# Exercises2.4.4Exercises

##### Exercise1

The judiciary committee at a college is made up of three faculty members and four students. If ten faculty members and 25 students have been nominated for the committee, how many judiciary committees could be formed at this point ?

##### Exercise2

Suppose that a single character is stored in a computer using eight bits.

a. How many bit patterns have exactly three 1's?

b. How many bit patterns have at least two 1's?

HintSolution
##### Exercise3

How many subsets of $\{1, 2, 3, \dots , 10\}$ contain at least seven elements?

##### Exercise5

Expand $( 2x - 3y )^4\text{.}$

##### Exercise7

A poker game is played with 52 cards. At the start of a game, each player get five of the cards. The order in which cards are dealt doesn't matter.

1. How many “hands” of five cards are possible?

2. (b) If there are four people playing, how many initial five-card “hands” are possible, taking into account all players?

##### Exercise9

How many five-card poker hands using 52 cards contain exactly two aces?

##### Exercise11

A class of twelve computer science students are to be divided into three groups of 3, 4, and 5 students to work on a project. How many ways can this be done if every student is to be in exactly one group?

##### Exercise13

There are ten points, $P_1, P_2, \dots , P_{10}$ on a plane, no three on the same line.

1. How many lines are determined by the points?

2. How many triangles are determined by the points?

##### Exercise15

Use the binomial theorem to prove that if $A$ is a finite set, then $\lvert P(A)\rvert =2^{\lvert A \rvert}$

##### Exercise17

Use the binomial theorem to calculate $9998^3\text{.}$

# Exercises3.1.3Exercises for Section 3.1

##### Exercise1

Let $d$ = “I like discrete structures”, $c$ = “I will pass this course” and $s$ = “I will do my assignments.” Express each of the following propositions in symbolic form:

1. I like discrete structures and I will pass this course.

2. I will do my assignments or I will not pass this course.

3. It is not true that I both like discrete structures, and will do my assignments.

4. I will not do my assignment and I will not pass this course.

##### Exercise3

Let $p =$“$2 \leq 5$”, $q$ = “8 is an even integer,” and $r$ = “11 is a prime number.” Express the following as a statement in English and determine whether the statement is true or false:

1. $\neg p \land q$

2. $p\rightarrow q$

3. $(p \land q)\to r$

4. $p \rightarrow (q \lor (\neg r))$

5. $p \rightarrow ((\neg q)\lor (\neg r))$

6. $(\neg q) \rightarrow (\neg p)$

##### Exercise5

Write the converse of the propositions in exercise 4. Compare the truth of each proposition and its converse.

# Exercises3.2.3Exercises for Section 3.2

##### Exercise1

Construct the truth tables of:

1. $p\lor p$

2. $p\land (\neg p)$

3. $p\lor (\neg p)$

4. $p \land p$

##### Exercise3

Rewrite the following with as few extraneous parentheses as possible:

1. $(\neg ((p) \land (r))) \lor (s)$

2. $((p) \lor (q)) \land ((r) \lor (q))$

##### Exercise5

Determine the number of rows in the truth table of a proposition containing four variables $p, q, r, \textrm{ and } s$.

# Exercises3.3.4Exercises for Section 3.3

##### Exercise1

Given the following propositions generated by $p\text{,}$ $q\text{,}$ and $r\text{,}$ which are equivalent to one another?

1. $(p \land r) \lor q$

2. $p\lor (r\lor q)$

3. $r \land p$

4. $\neg r \lor p$

5. $(p\lor q)\land (r\lor q)$

6. $r\to p$

7. $r \lor \neg p$

8. $p\to r$

##### Exercise3

Is an implication equivalent to its converse? Verify your answer using a truth table.

Solution
##### Exercise5

How large is the largest set of propositions generated by $p$ and $q$ with the property that no two elements are equivalent?

Solution
##### Exercise7

Explain why a contradiction implies any proposition and any proposition implies a tautology.

# Exercises3.4.1Exercises for Section 3.4

##### Exercise1

Write the following in symbolic notation and determine whether it is a tautology: “If I study then I will learn. I will not learn. Therefore, I do not study.”

##### Exercise3

Describe, in general, how duality can be applied to implications if we introduce the relation $\Leftarrow$, read “is implied by.” We define this relation by \begin{equation*} (p \Leftarrow q) \Leftrightarrow (q \Rightarrow p)\text{.} \end{equation*}

# Exercises3.5.1Exercises for Section 3.5

##### Exercise1

Prove with truth tables:

1. $p\lor q, \neg q\Rightarrow p$

2. $p \rightarrow q, \neg q \Rightarrow \neg p$

##### Exercise3

Give direct and indirect proofs of:

1. $a \rightarrow b, c \rightarrow b, d\rightarrow (a \lor c), d\Rightarrow b$.

2. $(p\to q) \land (r\to s), (q\rightarrow t) \land (s \to u), \neg (t \land u), p \rightarrow r \Rightarrow \neg p$.

3. $p\to (q\to r),\neg s\text{\backslash /}p,q\Rightarrow s\to r$.

4. $p\rightarrow q, q\rightarrow r, \neg (p \land r), p \lor r \Rightarrow r$.

5. $\neg q, p\to q, p\lor t \Rightarrow t$

##### Exercise5

Are the following arguments valid? If they are valid, construct formal proofs; if they aren't valid, explain why not.

1. If wages increase, then there will be inflation. The cost of living will not increase if there is no inflation. Wages will increase. Therefore, the cost of living will increase.

2. If the races are fixed or the casinos are crooked, then the tourist trade will decline. If the tourist trade decreases, then the police will be happy. The police force is never happy. Therefore, the races are not fixed.

##### Exercise7

Describe how $p_1,p_1\to p_2,\ldots ,p_{99}\to p_{100}\Rightarrow p_{100}$ could be proved in 199 steps.

# Exercises3.6.3Exercises for Section 3.6

##### Exercise1

If $U = \mathcal{P}( \{1, 2, 3, 4\})$, what are the truth sets of the following propositions?

1. $A \cap \{2, 4\} = \emptyset$.

2. $3 \in A$ and $1 \notin A$.

3. $A \cup \{1\} = A$.

4. $A$ is a proper subset of $\{2, 3, 4\}$.

5. $\lvert A \rvert=\lvert A^c \rvert$.

##### Exercise2

Over the universe of positive integers, define

1. What are the truth sets of these propositions?

2. Which of the three propositions implies one of the others?

Solution
##### Exercise3

If $U = \{0, 1, 2\}$, how many propositions over $U$ could you list without listing two that are equivalent?

##### Exercise5

Suppose that $s$ is a proposition over $\{1, 2,\dots, 8\}$. If $T_s = \{1, 3, 5, 7\}$, give two examples of propositions that are equivalent to $s\text{.}$

##### Exercise7

Let the universe be $\mathbb{Z}\text{,}$ the set of integers. Which of the following propositions are equivalent over $\mathbb{Z}\text{?}$

Solution

# Exercises3.7.1Exercises for Section 3.7

##### Exercise1

Prove that the sum of the first $n$ odd integers equals $n^2$ .

##### Exercise3

Prove that for $n \geq 1$: $\sum_{k=1}^n k^2= \frac{1}{6} n(n+1) (2 n+1)$.

##### Exercise5

Use mathematical induction to show that for $n\geq 1$, \begin{equation*} \frac{1}{1\cdot 2 }+ \frac{1}{2\cdot 3}+ \cdots + \frac{1}{n(n+1)}= \frac{n}{n+1}\text{.} \end{equation*}

##### Exercise7

The number of strings of $n$ zeros and ones that contain an even number of ones is $2^{n-1}$. Prove this fact by induction for $n \geq 1\text{.}$

##### Exercise9

Suppose that there are $n$ people in a room, $n \geq 1$, and that they all shake hands with one another. Prove that $\frac{n(n-1)}{2}$ handshakes will have occurred.

##### Exercise11

Generalized associativity. It is well known that if $a_1$, $a_2$, and $a_3$ are numbers, then no matter what order the sums in the expression $a_1+ a_2+a_3$ are taken in, the result is always the same. Call this fact $p(3)$ and assume it is true. Prove using course-of-values induction that if $a_1$, $a_2$, $\ldots ,$ and $a_n$ are numbers, then no matter what order the sums in the expression $a_1+ a_2+\cdots +a_n$ are taken in, the result is always the same.

Solution
##### Exercise12

Let $S$ be the set of all numbers that can be produced by applying any of the rules below in any order a finite number of times.

• Rule 1: $\frac{1}{2} \in S$
• Rule 2: $1 \in S$
• Rule 3: If $a$ and $b$ have been produced by the rules, then $a b \in S$.
• Rule 4: If $a$ and $b$ have been produced by the rules, then $\frac{a+b}{2}\in S$.

Prove that $a\in S \Rightarrow 0 \le a \leq 1$.

Hint
##### Exercise13

Proofs involving objects that are defined recursively are often inductive. A recursive definition is similar to an inductive proof. It consists of a basis, usually the simple part of the definition, and the recursion, which defines complex objects in terms of simpler ones. For example, if $x$ is a real number and $n$ is a positive integer, we can define $x^n$ as follows:

• Basis: $x^1=x$.
• Recursion: if $n \geq 2$, $x^n= x^{n-1}x$.

For example, $x^3= x^2x$ = $(x^1x)x = (x x) x$.

Prove that if $n, m \in \mathbb{P}$, $x^{m+n}= x^mx^n$. There is much more on recursion in Chapter 8.

HintSolution

# Exercises3.8.5Exercises for Section 3.8

##### Exercise1

Let $C(x)$ be “$x$ is cold-blooded,” let $F(x)$ be “$x$ is a fish,” and let $S(x)$ be “$x$ lives in the sea.”

1. Translate into a formula: Every fish is cold-blooded.

2. Translate into English: $(\exists x)(S(x) \land \neg F(x))$

3. $(\forall x)(F(x) \rightarrow S(x))$.

##### Exercise3

Over the universe of books, define the propositions $B(x)$: $x$ has a blue cover, $M(x)$: $x$ is a mathematics book, $U(x)$: $x$ is published in the United States, and $R(x, y)$ : The bibliography of $x$ includes $y\text{.}$

Translate into words:

1. $(\exists x)(\neg B(x))$.

2. $(\forall x)(M(x) \land U(x) \rightarrow B(x))$.

3. $(\exists x)(M(x) \land \neg B(x))$.

4. $(\exists y)((\forall x)(M(x)\to R(x,y)))$.

5. Express using quantifiers: Every book with a blue cover is a mathematics book.

6. Express using quantifiers: There are mathematics books that are published outside the United States.

7. Express using quantifiers: Not all books have bibliographies.

##### Exercise5

Translate into your own words and indicate whether it is true or false that $(\exists u) _{\mathbb{Z}} (4 u^2 -9 = 0)$.

##### Exercise6

Use quantifiers to say that $\sqrt{3}$ is an irrational number.

Hint
##### Exercise7

What do the following propositions say, where $U$ is the power set of $\{1,2,\dots , 9\}$? Which of these propositions are true?

1. $(\forall A)_U \lvert A \rvert \neq \lvert A^c \rvert$.

2. $(\exists A)_U(\exists B)_U (\lvert A \rvert =5, \lvert B \rvert=5, \textrm{ and } A\cap B=\emptyset )$

3. $(\forall A)_U(\forall B)_U (A-B=B^c-A^c)$

##### Exercise9

Use quantifiers to state that the sum of any two rational numbers is rational.

##### Exercise10

Over the universe of real numbers, use quantifiers to say that the equation $a + x = b$ has a solution for all values of $a$ and $b\text{.}$

Hint
##### Exercise11

Let $n$ be a positive integer. Describe using quantifiers:

1. $x \in \underset{k=1}{\overset{n}{\cup }}A_k$

2. $x \in \underset{k=1}{\overset{n}{\cap }}A_k$

# Exercises3.9.3Exercises for Section 3.9

##### Exercise1

Prove that the sum of two odd positive integers is even.

##### Exercise3

Write out a complete proof that $\sqrt{2}$ is irrational.

##### Exercise5

Prove that if $x$ and $y$ are real numbers such that $x + y \leq 1$, then either $x\leq \frac{1}{2}$ or $y\leq \frac{1}{2}$.

# Exercises4.1.5Exercises for Section 4.1

##### Exercise1

Prove the following:

1. Let $A\text{,}$ $B\text{,}$ and $C$ be sets. If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

2. Let $A$ and $B$ be sets. Then $A - B= A\cap B^c$ .

3. Let $A,B, \textrm{ and } C$ be sets. If ($A\subseteq B$ and $A\subseteq C$) then $A\subseteq B\cap C$.

4. Let $A \textrm{ and } B$ be sets. $A\subseteq B$ if and only if $B^c\subseteq A^c$ .

5. Let $A,B, \textrm{ and } C$ be sets. If $A\subseteq B$ then $A\times C \subseteq B\times C$.

##### Exercise3

Disprove the following, assuming $A, B, \textrm{ and } C$ are sets:

1. $A - B = B - A$.

2. $A\times B = B\times A$.

3. $A \cap B = A \cap C$ implies $B = C$.

4. $A \oplus (B\cap C) = (A \oplus B)\cap (A \oplus C)$

##### Exercise5

Prove by induction that if $A\text{,}$ $B_1$ $B_2$ , . . . , $B_n$ are sets, $n\geq 2$, then $A\cap ( B_1 \cup B_2\cup \dots \cup B_n) = (A \cap B_1) \cup (A \cap B_2 ) \cup \dots \cup (A\cap B_n)$.

Solution

# Exercises4.2.4Exercises for Section 4.2

##### Exercise1

1. Prove the associative law for intersection (Law $2^{\prime}$) with a Venn diagram.
2. Prove DeMorgan's Law (Law 9) with a membership table.
3. Prove the Idempotent Law (Law 6) using basic definitions.
##### Exercise3

Prove the following using the set theory laws, as well as any other theorems proved so far.

1. $A \cup (B - A) = A \cup B$
2. $A - B = B^c - A ^c$
3. $A\subseteq B, A\cap C \neq \emptyset \Rightarrow B\cap C \neq \emptyset$
4. $A\cap (B - C) = (A\cap B) - (A\cap C)$
5. $A - (B \cup C) = (A - B)\cap (A - C)$
##### Exercise5Hierarchy of Set Operations

The rules that determine the order of evaluation in a set expression that involves more than one operation are similar to the rules for logic. In the absence of parentheses, complementations are done first, intersections second, and unions third. Parentheses are used to override this order. If the same operation appears two or more consecutive times, evaluate from left to right. In what order are the following expressions performed?

1. $A \cup B^c\cap C$.
2. $A\cap B \cup C\cap B$.
3. $A \cup B \cup C^c$

# Exercises4.3.1Exercises for Section 4.3

##### Exercise1

Consider the subsets $A = \{1, 7, 8\}$, $B = \{1, 6, 9, 10\}$, and $C = \{1, 9, 10\}$, where $U = \{1,2, . . . , 10\}$.

1. List the nonempty minsets generated by $A, B, \textrm{ and } C$.

2. How many elements of the power set of $U$ can be generated by $A\text{,}$ $B\text{,}$ and $C\text{?}$ Compare this number with $\mid\mathcal{P}(U)\mid$. Give an example of one subset that cannot be generated by $A\text{,}$ $B\text{,}$ and $C\text{.}$

##### Exercise3

Partition the set of strings of 0's and 1's of length two or less, using the minsets generated by $B_1=\{s \mid s \textrm{ has length } 2\}$, and $B_2= \{s \mid s \textrm{ starts with a } 0\}$.

##### Exercise5

1. Partition $A = \{0, 1, 2, 3, 4, 5\}$ with the minsets generated by $B_1= \{0, 2, 4\}\text{ }$and $B_2= \{1, 5\}$.

2. How many different subsets of $A$ can you generate from $B_1 \textrm{ and } B_2$?

##### Exercise7

Prove Theorem 4.3.6

# Exercises4.4.1Exercises for Section 4.4

##### Exercise1

State the dual of of each of the following:

1. $A \cup (B \cap A) = A$.

2. $A \cup \left(\left(B^c \cup A\right) \cap B\right)^c = U$

3. $\left(A \cup B^c\right)^c \cap B =A^c\cap B$

##### Exercise3

Write the dual of of each of the following:

1. $p\lor \neg ((\neg q\lor p)\land q)\Leftrightarrow 1$

2. $(\neg (p \land (\neg q ))) \lor q\Leftrightarrow (\neg p \lor q)$.

##### Exercise5

Let $A = \{1,2, 3,4, 5, 6\}$ and let $B_1 = \{1, 3, 5\}$ and $B _2 = \{1,2, 3\}$.

1. Find the maxsets generated by $B_1$ and $B_2$. Note the set of maxsets does not constitute a partition of $A\text{.}$ Can you explain why?

2. Write out the definition of maxset normal form.

3. Repeat Exercise 4.3.1.4 for maxsets.

# Exercises5.1.4Exercises

##### Exercise1

Let $A=\left( \begin{array}{cc} 1 & -1 \\ 2 & 3 \\ \end{array} \right)$, $B =\left( \begin{array}{cc} 0 & 1 \\ 3 & -5 \\ \end{array} \right)$ , and $C=\left( \begin{array}{ccc} 0 & 1 & -1 \\ 3 & -2 & 2 \\ \end{array} \right)$

1. Compute $A B$ and $B A$.

2. Compute $A + B$ and $B + A$.

3. If $c = 3$, show that $c(A + B) = c A + c B$.

4. Show that $(A B)C = A(B C)$.

5. Compute $A^2 C$.

6. Compute $B + \pmb{0}$.

7. Compute $A \pmb{0}_{2\times 2}$ and $\pmb{0}_{2\times 2} A$, where $\pmb{0}_{2\times 2}$ is the $2\times 2$ zero matrix.

8. Compute $0A$, where 0 is the real number (scalar) zero.

9. Let $c = 2$ and $d = 3$. Show that $(c + d)A = c A + d A$.

##### Exercise3

Let $A =\left( \begin{array}{cc} 2 & 0 \\ 0 & 3 \\ \end{array} \right)$ . Find a matrix $B$ such that $A B = I$ and $B A = I$, where $I = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right)$.

##### Exercise5

Find $A^3$ if $A=\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \\ \end{array} \right)$ . What is $A^{15}$ equal to?

##### Exercise7

1. If $A =\left( \begin{array}{cc} 2 & 1 \\ 1 & -1 \\ \end{array} \right)$, $X =\left( \begin{array}{c} x_1 \\ x_2 \\ \end{array} \right)$, and $B =\left( \begin{array}{c} 3 \\ 1 \\ \end{array} \right)$ , show that $A X =B$ is a way of expressing the system $\begin{array}{c}2x_1 + x_2 = 3\\ x_1 - x_2= 1\\ \end{array}$ using matrices.

2. Express the following systems of equations using matrices:

1. $\begin{array}{c} 2 x_1- x_2= 4\\ x_1+ x_2= 0\\ \end{array}$

2. $\begin{array}{c} x_1+ x_2+ 2 x_3= 1\\ x_1+ 2 x_2-x_3= -1\\ x_1+ 3 x_2+x_3= 5\\ \end{array}$

3. $\begin{array}{c} x_1+x_2\quad\quad= 3\\ \quad \quad x_2\quad\quad= 5\\ x_1 \quad \quad+ 3x_3= 6\\ \end{array}$

# Exercises5.2.1Exercises

##### Exercise1

For the given matrices $A$ find $A^{-1}$ if it exists and verify that $A A^{-1}=A^{-1}A = I$. If $A^{-1}$ does not exist explain why.

1. $A = \left( \begin{array}{cc} 1 & 3 \\ 2 & 1 \\ \end{array} \right)$
2. $A=\left( \begin{array}{cc} 6 & -3 \\ 8 & -4 \\ \end{array} \right)$
3. $A = \left( \begin{array}{cc} 1 & -3 \\ 0 & 1 \\ \end{array} \right)$
4. $A = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right)$
5. Use the definition of the inverse of a matrix to find $A^{-1}$: $A=\left( \begin{array}{ccc} 3 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & 0 & -5 \\ \end{array} \right)$
##### Exercise3

1. Let $A = \left( \begin{array}{cc} 2 & 3 \\ 1 & 4 \\ \end{array} \right)$ and $B =\left( \begin{array}{cc} 3 & -3 \\ 2 & 1 \\ \end{array} \right)$. Verify that $(A B)^{-1}= B^{-1}A^{-1}$.
2. Let $A$ and $B$ be $n\times n$ invertible matrices. Prove that $(A B)^{-1}= B^{-1}A^{-1}$. Why is the right side of the above statement written “backwards”? Is this necessary? Hint: Use Theorem 5.2.6
##### Exercise5Linearity of Determinants

1. Let $A$ and $B$ be 2-by-2 matrices. Show that $\det (A B) =(\det A)(\det B)$.
2. It can be shown that the statement in part (a) is true for all $n\times n$ matrices. Let $A$ be any invertible $n\times n$ matrix. Prove that $\det \left(A^{-1}\right) =(\det A)^{-1}$. Note: The determinant of the identity matrix $I_n$ is 1 for all $n\text{.}$
3. Verify that the equation in part (b) is true for the matrix in exercise l(a) of this section.
##### Exercise7

Use the assumptions in Exercise 5.2.1.5 to prove by induction that if $n \geq 1\text{,}$ $\det \left(A^n\right) = (\det A)^n$.

##### Exercise9

1. Let $A, B, \textrm{ and } D$ be $n\times n$ matrices. Assume that $B$ is invertible. If $A = B D B^{-1}$ , prove by induction that $A^m= B D^m B^{-1}$ is true for $m \geq 1$.
2. Given that $A = \left( \begin{array}{cc} -8 & 15 \\ -6 & 11 \\ \end{array} \right) = B \left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \\ \end{array} \right) B^{-1}$ where $B=\left( \begin{array}{cc} 5 & 3 \\ 3 & 2 \\ \end{array} \right)$ what is $A^{10}$?

# Exercises5.3.1Exercises

##### Exercise1

Rewrite the above laws specifying as in Example 5.3.2 the orders of the matrices.

##### Exercise3

Let $A = \left( \begin{array}{cc} 1 & 2 \\ 0 & -1 \\ \end{array} \right)$, $B= \left( \begin{array}{ccc} 3 & 7 & 6 \\ 2 & -1 & 5 \\ \end{array} \right)$, and $C= \left( \begin{array}{ccc} 0 & -2 & 4 \\ 7 & 1 & 1 \\ \end{array} \right)$. Compute the following as efficiently as possible by using any of the Laws of Matrix Algebra:

1. $A B + A C$

2. $A^{-1}$

3. $A(B + C)$

4. $\left(A^2\right)^{-1}$

5. $(C + B)^{-1}A^{-1}$

# Exercises5.4.1Exercises

##### Exercise1

Discuss each of the “Matrix Oddities” with respect to elementary algebra.

##### Exercise3

Prove the following implications, if possible:

1. $A^2= A$ and $\det A \neq 0 \Rightarrow A =I$

2. $A^2 = I \textrm{ and } \det A \neq 0 \Rightarrow A = I \textrm{ or } A = -I$.

##### Exercise5

Write each of the following systems in the form $A X = B$, and then solve the systems using matrices.

1. $\begin{array}{c}2x_1+x_2=3\\ x_1-x_2= 1\\ \end{array}$

2. $\begin{array}{c}2x_1-x_2=4\\ x_1 -x_2= 0\\ \end{array}$

3. $\begin{array}{c}2x_1+x_2=1\\ x_1 -x_2= 1\\ \end{array}$
4. $\begin{array}{c}2x_1+x_2=1\\ x_1 -x_2= -1\\ \end{array}$

5. $\begin{array}{c}3x_1+2x_2=1 \\ 6 x_1 +4x_2= -1\\ \end{array}$

# Exercises6.1.1Exercises

##### Exercise1

For each of the following relations $r$ defined on $\mathbb{P}$, determine which of the given ordered pairs belong to $r$

1. $x r y$ iff $x|y$; (2, 3), (2, 4), (2, 8), (2, 17)

2. $x r y$ iff $x \leq y$; (2, 3), (3, 2), (2, 4), (5, 8)

3. $x r y$ iff $y =x^2$ ; (1,1), (2, 3), (2, 4), (2, 6)

##### Exercise3

Let $A = \{1,2,3,4,5\}$ and define $r$ on $A$ by $x r y$ iff $x + 1 = y$. We define $r^2 = r r$ and $r^3 = r^2 r$. Find:

1. $r$

2. $r^2$

3. $r^3$

##### Exercise5

Let $\rho$ be the relation on the power set, $\mathcal{P}(S )$, of a finite set $S$ of cardinality $n$ defined $\rho$ by $(A,B) \in \rho$ iff $A\cap B = \emptyset$.

1. Consider the specific case $n = 3$, and determine the cardinality of the set $\rho$.

2. What is the cardinality of $\rho$ for an arbitrary $n\text{?}$ Express your answer in terms of $n\text{.}$ (Hint: There are three places that each element of S can go in building an element of $\rho$.)

# Exercises6.2.1Exercises

##### Exercise1

Let $A = \{1, 2, 3, 4\}$, and let $r$ be the relation $\leq$ on $A\text{.}$ Draw a digraph for $r\text{.}$

##### Exercise3

Let $A=\{1,2,3,4,5\}$. Define $t$ on $A$ by $a t b$ if and only if $b - a$ is even. Draw a digraph for $t\text{.}$

# Exercises6.3.4Exercises

##### Exercise1

1. Let $B = \{a, b\}$ and $U = \mathcal{P}(B)$. Draw a Hasse diagram for $\subseteq$ on $U\text{.}$

2. Let $A = \{1,2, 3, 6\}$. Show that divides, $\mid \text{,}$ is a partial ordering on $A\text{.}$

3. Draw a Hasse diagram for divides on $A\text{.}$

4. Compare the graphs of parts a and c.

##### Exercise3

Consider the relations defined by the digraphs in Figure 6.3.16.

1. Determine whether the given relations are reflexive, symmetric, antisymmetric, or transitive. Try to develop procedures for determining the validity of these properties from the graphs,

2. Which of the graphs are of equivalence relations or of partial orderings?

##### Exercise5

Consider the relation on $\{1, 2, 3, 4, 5, 6\}$ defined by $r = \{(i,j): \mid i - j\mid = 2\}$.

1. Is $r$ reflexive?

2. Is $r$ symmetric?

3. Is $r$ transitive?

4. Draw a graph of $r\text{.}$

##### Exercise7Equivalence Classes

Let $A = \{0, 1, 2, 3\}$ and let $r = \{(0, 0), (1, 1), (2, 2), (3, 3), (1, 2),(2, 1), (3, 2), (2, 3), (3, 1), (1, 3)\}$

1. Verify that $r$ is an equivalence relation on $A\text{.}$

2. Let $a \in A$ and define $c(a) = \{b \in A \mid a rb\}$. $c(a)$ is called the equivalence class of $a$ under $r$. Find $c(a)$ for each element $a \in A$.

3. Show that $\{c(a) \mid a \in A\}$ forms a partition of $A$ for this set $A\text{.}$

4. Let $r$ be an equivalence relation on an arbitrary set $A\text{.}$ Prove that the set of all equivalence classes under $r$ constitutes a partition of $A\text{.}$

##### Exercise9

Consider the following relations on $\mathbb{Z}_8= \{0, 1, . . . , 7\}$. Which are equivalence relations? For the equivalence relations, list the equivalence classes.

1. $a r b$ iff the English spellings of $a$ and $b$ begin with the same letter.

2. $a s b$ iff $a - b$ is a positive integer.

3. $a t b$ iff $a-b$ is an even integer.

##### Exercise11

In this exercise, we prove that implication is a partial ordering. Let $A$ be any set of propositions.

1. Verify that $q \to q$ is a tautology, thereby showing that $\Rightarrow$ is a reflexive relation on $A\text{.}$

2. Prove that $\Rightarrow$ is antisymmetric on $A\text{.}$ Note: we do not use = when speaking of propositions, but rather equivalence, $\Leftrightarrow$.
3. Prove that $\Rightarrow$ is transitive on $A\text{.}$

4. Given that $q_i$ is the proposition $n < i$ on $\mathbb{N}$, draw the Hasse diagram for the relation $\Rightarrow$ on $\{q_1, q_2, q_3,\ldots \}$.

# Exercises6.4.1Exercises

##### Exercise1

Let $A_1 = \{1,2, 3, 4\}$, $A_2 = \{4, 5, 6\}$, and $A_3 = \{6, 7, 8\}$. Let $r_1$ be the relation from $A_1$ into $A_2$ defined by $r_1 = \{(x, y) \mid y - x = 2\}$, and let $r_2$ be the relation from $A_2$ into $A_3$ defined by $r_2 = \{(x, y) \mid y - x = 1\}$.

1. Determine the adjacency matrices of $r_1$ and $r_2$.

2. Use the definition of composition to find $r_1r_2$.

3. Verify the result in part by finding the product of the adjacency matrices of $r_1$ and $r_2$.

##### Exercise3

Suppose that the matrices in Example 6.4.3 are relations on $\{1, 2, 3, 4\}$. What relations do $R$ and $S$ describe?

##### Exercise5

How many different reflexive, symmetric relations are there on a set with three elements?

##### Exercise7

Define relations $p$ and $q$ on $\{1, 2, 3, 4\}$ by $p = \{(a, b) \mid \lvert a-b\rvert=1\}$ and $q=\{(a,b) \mid a-b \textrm{ is even}\}$.

1. Represent $p$ and $q$ as both graphs and matrices.

2. Determine $p q$, $p^2$, and $q^2$; and represent them clearly in any way.

##### Exercise9

We define $\leq$ on the set of all $n\times n$ relation matrices by the rule that if $R$ and $S$ are any two $n\times n$ relation matrices, $R \leq S$ if and only if $R_{ij} \leq S_{ij}$ for all $1 \leq i, j \leq n$.

1. Prove that $\leq$ is a partial ordering on all $n\times n$ relation matrices.

2. Prove that $R \leq S \Rightarrow R^2\leq S^2$ , but the converse is not true.

3. If $R$ and $S$ are matrices of equivalence relations and $R \leq S$, how are the equivalence classes defined by $R$ related to the equivalence classes defined by $S\text{?}$

# Exercises6.5.1Exercises

##### Exercise3

1. Draw digraphs of the relations $\mathcal{S}$, $\mathcal{S}^2$, $\mathcal{S}^3$ , and $\mathcal{S}^+$ where $\mathcal{S}$ is defined in the first exercise above.

2. Verify that in terms of the graph of $\mathcal{S}$, $a \mathcal{S}^+ b$ if and only if $b$ is reachable from $a$ along a path of any finite nonzero length.
##### Exercise5

1. Define reflexive closure and symmetric closure by imitating the definition of transitive closure.

2. Use your definitions to compute the reflexive and symmetric closures of examples in the text.

3. What are the transitive reflexive closures of these examples?

4. Convince yourself that the reflexive closure of the relation $<$ on the set of positive integers $\mathbb{P}$ is $\leq$.

##### Exercise7

1. Let $A$ be any set and $r$ a relation on $A\text{,}$ prove that $\left(r^+\right)^+=r^+$.

2. Is the transitive closure of a symmetric relation always both symmetric and reflexive? Explain.

# Exercises7.1.5Exercises for Section 7.1

##### Exercise1

Let $A = \{1, 2, 3, 4\}$ and $B = \{a, b, c, d\}$. Determine which of the following are functions. Explain.

1. $f \subseteq A \times B$, where $f = \{(1, a), (2, b), (3, c), (4, d)\}$.

2. $g\subseteq A\times B$, where $g = \{(1, a), (2, a), (3,b), (4,d)\}$.

3. $h \subseteq A \times B$, where $h = \{(1, a), (2, b), (3, c)\}$.

4. $k \subseteq A\times B$, where $k = \{(1, a), (2, b), (2, c), (3, a), (4, a)\}$.

5. $L\subseteq A\times A$, where $L = \{(1, 1), (2, 1), (3, 1), (4, 1)\}$.

##### Exercise3

Find the ranges of each of the relations that are functions in Exercise 1.

##### Exercise7

If $A$ and $B$ are finite sets, how many different functions are there from $A$ into $B\text{?}$

# Exercises7.2.1Exercises for Section 7.2

##### Exercise1

Determine which of the functions in Exercise 1 of Section 7.1 are one- to-one and which are onto.

##### Exercise3

Which of the following are one-to-one, onto, or both?

1. $f_1:\mathbb{R} \rightarrow \mathbb{R}$ defined by $f_1(x) = x^3 - x$.

2. $f_2 :\mathbb{Z} \rightarrow \mathbb{Z}$ defined by $f_2(x)= -x + 2$.

3. $f_3:\mathbb{N} \times \mathbb{N}\to \mathbb{N}$ defined by $f_3(j, k) =2^j3^k$.

4. $f_4 :\mathbb{P} \rightarrow \mathbb{P}$ defined by $f_4(n)=\lceil n/2\rceil$, where $\lceil x\rceil$ is the ceiling of $x\text{,}$ the smallest integer greater than or equal to $x\text{.}$

5. $f_5 :\mathbb{N} \rightarrow \mathbb{N}$ defined by $f_5(n)=n^2+n$.

6. $\text{ }f_6:\mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ defined by $f_6(n)= (2n, 2n+1)$.

##### Exercise5

Suppose that $m$ pairs of socks are mixed up in your sock drawer. Use the Pigeonhole Principle to explain why, if you pick $m + 1$ socks at random, at least two will make up a matching pair.

##### Exercise7

Let $A =\text{ }\{1, 2, 3, 4, 5\}$. Find functions, if they exist that have the properties specified below.

1. A function that is one-to-one and onto.

2. A function that is neither one-to-one nor onto.

3. A function that is one-to-one but not onto.

4. A function that is onto but not one-to-one.

##### Exercise9

1. Prove that the set of natural numbers is countable.

2. Prove that the set of integers is countable.

3. Prove that the set of rational numbers is countable.

##### Exercise11

Use the Pigeonhole Principle to prove that an injection cannot exist between a finite set $A$ and a finite set $B$ if the cardinality of $A$ is greater than the cardinality of $B\text{.}$

##### Exercise13

Prove that the set of all infinite sequences of 0's and 1's is not a countable set.

# Exercises7.3.4Exercises for Section 7.3

##### Exercise1

Let $A = \{1,2, 3, 4, 5\}$, $B = \{a, b, c, d, e,f\}$, and $C = \{+, -\}$. Define $f: A \to B$ by $f(k)$ equal to the $k^{th}$ letter in the alphabet, and define $g : B \rightarrow C$ by $g(\alpha ) = +$ if $\alpha$ is a vowel and $g(\alpha ) = -$ if $\alpha$ is a consonant.

1. Find $g\circ f$.

2. Does it make sense to discuss $f\circ g$? If not, why not?

3. Does $f^{-1}$ exist? Why?

4. Does $g^{-1}$ exist? Why?

##### Exercise3

Let $A = \{1, 2, 3\}$.

1. List all permutations of $A\text{.}$

2. Find the inverse and square of each of the permutations of part a.

3. Show that the composition of any two permutations of $A$ is a permutation of $A\text{.}$

4. Prove that if $A$ be any set where the $\lvert A\rvert= n$, then the number of permutations of $A$ is $n!$.

##### Exercise7

Let $f,$ $g\text{,}$ and $h$ all be functions from $\mathbb{Z}$ into $\mathbb{Z}$ defined by $f(n) = n + 5$, $g(n) = n - 2,$ and $h(n)=n^2$. Define:

1. $f\circ g$

2. $f^3$

3. $f\circ h$

##### Exercise9

Let $A$ be a nonempty set. Prove that if $f$ is a bijection on $A$ and $f \circ f=f$, then $f$ is the identity function, $i$

Hint
##### Exercise11

State and prove a theorem on inverse functions analogous to the one that says that if a matrix has an inverse, that inverse is unique.

##### Exercise12

Let $f$ and $g$ be functions whose inverses exist. Prove that $(f\circ g)^{-1}= g^{-1}\circ f^{-1}$.

Hint
##### Exercise13

Prove Theorem 7.3.6 and Theorem 7.3.7.

##### Exercise15

Prove by induction that if $n\geq 2$ and $f_1$, $f_2$ , \ldots , $f_n$ are invertible functions on some nonempty set $A$, then { }$\left( f_1\circ f_2\circ \cdots \circ f_n \right){}^{-1}= f_n^{-1}\circ \cdots \circ f_2^{-1}\circ f_1^{-1}$. The basis has been taken care of in Exercise 10.

# Exercises8.1.8Exercises for Section 8.1

##### Exercise1

By the recursive definition of binomial coefficients, $\binom{7}{2}=\binom{6}{2} +\binom{6}{1}$. Continue expanding $\binom{7}{2}$ to express it in terms of quantities defined by the basis. Check your result by applying the factorial definition of $\binom{n}{k}$.

##### Exercise3

Let $p(x) = x^5+ 3x^4 - 15x^3 + x - 10$.

1. Write $p(x)$ in telescoping form.

2. Use a calculator to compute $p(3)$ using the original form of $p(x)$.

3. Use a calculator to compute $p(3)$ using the telescoping form of $p(x)$.

4. Compare your speed in parts b and c.

##### Exercise5

What is wrong with the following definition of $f:\mathbb{R}\to \mathbb{R}$? $f(0) = 1$ and $f(x) = f(x/2)/2$ if $x\neq 0$.

# Exercises8.2.1Exercises for Section 8.2

##### Exercise1

Prove by induction that $B(k) = 3k + 2,$ $k\geq 0$, is a closed form expression for the sequence $B$ in Example 8.2.2

##### Exercise3

Given $k$ lines ($k\geq 0$) on a plane such that no two lines are parallel and no three lines meet at the same point, let $P(k)$ be the number of regions into which the lines divide the plane (including the infinite ones (see Figure 8.2.3). Describe how the recurrence relation $P(k) = P(k - 1) + k$ can be derived. Given that $P(0) = 1$, determine $P(5)$.

##### Exercise5

Let $M(n)$ be the number of multiplications needed to evaluate an $n^{th}$ degree polynomial. Use the recursive definition of a polynomial expression to define $M$ recursively.

# Exercises8.3.5Exercises for Section 8.3

##### Exercise1

$S(k) - 10S(k - 1) + 9S(k - 2) = 0$, $S(0) = 3$, $S(1) = 11$

##### Exercise3

$S(k) - 0.25S(k - 1) = 0$, $S(0) = 6$

##### Exercise5

$S(k) - 2S(k - 1) + S(k - 2) = 2 \textrm{, }S(0) = 25,\textrm{ }S(1) = 16$

##### Exercise7

$S(k) - 5S (k - 1) = 5^k,\textrm{ }S(0) = 3$

##### Exercise9

$S(k) - 4S(k - 1) + 4S(k - 2) = 3k + 2^k \textrm{, }S(0) = 1, S(1) = 1$

##### Exercise11

$S(k) - 4S(k - 1) - 11S(k- 2)+ 30S(k - 3) = 0$, $S(0) = 0$,$S(1) = -35,\textrm{ }S(2) = -85$

##### Exercise13

1. Find a closed form expression for the terms of the Fibonacci sequence (see Example 8.1.4).

2. The sequence $C$ was defined by $C_r$ = the number of strings of zeros and ones with length $r$ having no consecutive zeros (Example 8.2.1(c)). Its recurrence relation is the same as that of the Fibonacci sequence. Determine a closed form expression for $C_r$, $r \geq 1$.

##### Exercise15

Let $D(n)$ be the number of ways that the set $\{1, 2, . . . , n\}$, $n \geq 1$, can be partitioned into two nonempty subsets.

1. Find a recurrence relation for $D\text{.}$ (Hint: It will be a first-order linear relation.)

2. Solve the recurrence relation.

# Exercises8.4.5Exercises for Section 8.4

##### Exercise1

Solve the following recurrence relations. Indicate whether your solution is an improvement over iteration.

1. $n S(n) - S(n - 1) = 0$, $S(0) = 1$.

2. $T(k) + 3k T(k - 1) = 0$, $T(0) = 1$.

3. $U(k) -\frac{k-1}{k}U(k - 1) = 0$, $k \geq 2$, $U(1) = 1$.

##### Exercise3

Solve as completely as possible:

1. $T(n) = 3 + T(\lfloor n/2\rfloor )$, $T(0) = 0$.

2. $T(n) = 1 + \frac{1}{2}T(\lfloor n/2\rfloor )$, $T(0) = 2$.

3. $V(n) = 1 + V\lfloor n/8\rfloor )$, $V(0) = 0$. (Hint: Write $n$ in octal form.)

##### Exercise4

Prove by induction that if $T(n)= 1 + T (\lfloor n/2 \rfloor )$, $T(0) = 0$, and $2^{r-1}\leq n < 2^r$ , $r \geq 1$, then $T(n) = r$.

Hint
##### Exercise5

Use the substitution $S(n) = T(n + 1)/T(n)$ to solve $T(n)T(n-2)-T(n)^2=1$ for $n \geq 2$, with $T(0) = 1$, $T(1) = 6$, and $T(n) \geq 0$.

##### Exercise7

Solve as completely as possible:

1. $Q(n)=1+Q\left(\left\lfloor \sqrt{n}\right\rfloor \right)$, $n \geq 2$, $Q(1) = 0$.

2. $R(n)=n +R(\lfloor n/2\rfloor )$, $n \geq 1$, $R(0) = 0$.

# Exercises8.5.7Exercises for Section 8.5

##### Exercise1

What sequences have the following generating functions?

1. 1

2. $\frac{10}{2-z}$

3. $1 + z$

4. $\frac{3}{1+2z}+ \frac{3}{1-3z}$

##### Exercise3

Find closed form expressions for the generating functions of the following sequences:

1. $V(n) = 9^n$

2. $P$, where $P(k) - 6 P(k - 1) + 5 P(k - 2) = 0$ for $k \geq 2$, with $P(0) = 2$and $P(1) = 2$.

3. The Fibonacci sequence: $F(k + 2) = F(k + 1) + F(k)$, $k \geq 0$, with $F(0) = F(1) = 1$.

##### Exercise5

For each of the following expressions, find the partial fraction decomposition and identify the sequence having the expression as a generating function.

1. $\frac{5+2z}{1-4z^2}$

2. $\frac{32-22z}{2-3z+z^2}$

3. $\frac{6-29z}{1-11z+ 30z^2}$

##### Exercise7

Given that $S(k) = k$ and $T(k) = 10k$, what is the $k^{\text{th}}$ term of the generating function of each of the following sequences:

1. $S + T$

2. $S\uparrow * T$

3. $S * T$

4. $S\uparrow *S\uparrow$

##### Exercise9

A game is played by rolling a die five times. For the $k^{\text{th}}$ roll, one point is added to your score if you roll a number higher than $k\text{.}$ Otherwise, your score is zero for that roll. For example, the sequence of rolls $2,3,4,1,2$ gives you a total score of three; while a sequence of 1,2,3,4,5 gives you a score of zero. Of the $6^5 = 7776$ possible sequences of rolls, how many give you a score of zero?, of one? $\ldots$ of five?

# Exercises9.1.1Exercises for Section 9.1

##### Exercise1

What is the significance of the fact that there is a path connecting vertex $b$ with every other vertex in Figure 9.1.10.(a), as it applies to various situations that it models?

##### Exercise3

Draw a directed graph that models the set of strings of 0's and 1's (zero or more of each) where all of the 1's must appear consecutively.

##### Exercise5

What is the maximum number of edges in an undirected graph with eight vertices?

##### Exercise7

1. How many edges does a complete tournament graph with $n$ vertices have?

2. How many edges does a single-elimination tournament graph with $n$ vertices have?

##### Exercise9

Determine whether the following sequences are graphic. Explain your logic.

1. $(6, 5, 4, 3, 2, 1, 0)$

2. $(2,2,2,2,2,2)$

3. $(3,2,2,2,2,2)$

4. $(5,3,3,3,3,3)$

5. $(1,1,1,1,1,1)$

6. $(5,5,4,3,2,1)$

# Exercises9.2.3Exercises for Section 9.2

##### Exercise1

Estimate the number of vertices and edges in each of the following graphs. Would the graph be considered sparse, so that an adjacency matrix would be inefficient?

1. Vertices: Cities of the world that are served by at least one airline. Edges: Pairs of cities that are connected by a regular direct flight.

2. Vertices: ASCII characters. Edges: connect characters that differ in their binary code by exactly two bits.

3. Vertices: All English words. Edges: An edge connects word $x$ to word $y$ if $x$ is a prefix of $y$.

##### Exercise3

Directed graphs $G_1, \dots, G_6$ , each with vertex set $\{1,2,3,4,5\}$ are represented by the matrices below. Which graphs are isomorphic to one another?

$G_1: \left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$G_2: \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$G_3: \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} \right)$ $G_4: \left( \begin{array}{ccccc} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$\quad G_5: \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$G_6: \left( \begin{array}{ccccc} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{array} \right)$

# Exercises9.3.5Exercises for Section 9.3

##### Exercise1

Apply Algorithm 9.3.8 to find a path from 5 to 1 in Figure 9.3.11. What would be the final value of $V\text{?}$ Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order, as we assumed in Example 9.3.10.

##### Exercise3

In a simple undirected graph with no self-loops, what is the maximum number of edges you can have, keeping the graph unconnected? What is the minimum number of edges that will assure that the graph is connected?

##### Exercise5

Prove (by induction on $k$) that if the relation $r$ on vertices of a graph is defined by $v r w$ if there is an edge connecting $v$ to $w\text{,}$ then $r^k$, $k \geq 1$, is defined by $v r^kw$ if there is a path of length $k$ from $v$ to $w\text{.}$

# Exercises9.4.3Exercises for Section 9.4

##### Exercise1

Locate a map of New York City and draw a graph that represents its land masses, bridges and tunnels. Is there a Eulerian path through New York? You can do the same with any other city that has at least two land masses.

##### Exercise3

Write out the Gray Code for the 4-cube.

##### Exercise5

The Euler Construction Company has been contracted to construct an extra bridge in Koenigsberg so that a Eulerian path through the town exists. Can this be done, and if so, where should the bridge be built?

##### Exercise7

Formulate Euler's theorem for directed graphs.

##### Exercise8

Prove that the number of vertices in an undirected graph with odd degree must be even.

Hint
##### Exercise9

1. Under what conditions will a round-robin tournament graph be Eulerian?

2. Prove that every round-robin tournament graph is Hamiltonian.

# Exercises9.5.5Exercises for Section 9.5

##### Exercise1

Find the closest neighbor circuit through the six capitals of New England starting at Boston. If you start at a different city, will you get a different circuit?

##### Exercise3

Given the following sets of points in the unit square, find the shortest circuit that visits all the points and find the circuit that is obtained with the strip algorithm.

1. $\{(0.1k, 0.1k) : k = 0, 1, 2, . . . , 10\}$

2. $\{(0.1, 0.3), (0.3, 0.8), (0.5, 0.3), (0.7, 0.9), (0.9, 0.1)\}$

3. $\{(0.0, 0.5), (0.5, 0.0), (0.5, 1.0), (1.0, 0.5)\}$

4. $\{(0, 0), (0.2, 0.6), (0.4, 0.1), (0.6, 0.8), (0.7, 0.5)\}$

##### Exercise5

Consider the network whose maximum capacities are shown on the following graph.

1. A function $f$ is partially defined on the edges of this network by: $f(\text{Source}, c) =2$, $f(\text{Source}, b) =2$, $f(\text{Source}, a) = 2$, and $f(a, d) = 1$. Define $f$ on the rest of the other edges so that $f$ is a flow. What is the value of $f$ ?

2. Find a flow augmenting path with respect to $f$ for this network. What is the value of the augmented flow?

3. Is the augmented flow a maximum flow? Explain.

##### Exercise7

Find maximal flows for the following networks.

##### Exercise9

Discuss reasons that the closest neighbor algorithm is not used in the unit square version of the Traveling Salesman Problem.

# Exercises9.6.3Exercises for Section 9.6

##### Exercise1

Apply Theorem 9.6.2 to prove that once $n$ gets to a certain size, a $K_n$ is nonplanar. What is the largest complete planar graph?

##### Exercise3

What are the chromatic numbers of the following graphs?

##### Exercise5

What is $\chi \left(K_n\right)$, $n\geq 1$?

##### Exercise7

Complete the proof of Theorem 9.6.8.

##### Exercise9

Let $G = (V,E)$ with $|V|\geq 11$, and let $U$ be the set of all undirected edges between distinct vertices in $V\text{.}$ Prove that either $G$ or $G' = \left(V,E^c\right)$ is nonplanar.

##### Exercise11

Prove that a bipartite graph with an odd number of vertices greater than or equal to 3 has no Hamiltonian circuit.

##### Exercise13

Suppose you had to color the edges of an undirected graph so that for each vertex, the edges that it is connected to have different colors. How can this problem be transformed into a vertex coloring problem?

# Exercises10.1.1Exercises for Section 10.1

##### Exercise1

Given the following vertex sets, draw all possible undirected trees that connect them.

1. $V_a= \{\text{right},\text{left}\}$

2. $V_b = \{+,-,0\}$

3. $V_c = \{\text{north}, \text{south}, \text{east}, \text{west}\}$.

##### Exercise3

Prove that if $G$ is a simple undirected graph with no self-loops, then $G$ is a tree if and only if $G$ is connected and $\lvert E \rvert = \lvert V \rvert - 1$.

Hint
##### Exercise5

1. Prove that any tree with at least two vertices has at least two vertices of degree 1.

2. Prove that if a tree has $n$ vertices, $n \geq 4$, and is not a path graph, $P_n$, then it has at least three vertices of degree 1.

# Exercises10.2.1Exercises for Section 10.2

##### Exercise1

Suppose that after Atlantis University's phone system is in place, a fifth campus is established and that a transmission line can be bought to connect the new campus to any old campus. Is this larger system the most economical one possible with respect to Objective 1? Can you always satisfy Objective 2?

##### Exercise3

Show that the answer to the question posed in Example 10.2.7 is “no.”

##### Exercise5

Find a minimum diameter spanning tree for the following graphs.

# Exercises10.3.4Exercises for Section 10.3

##### Exercise1

Suppose that an undirected tree has diameter $d$ and that you would like to select a vertex of the tree as a root so that the resulting rooted tree has the smallest depth possible. How would such a root be selected and what would be the depth of the tree (in terms of $d$)?

##### Exercise3

Suppose that information on buildings is arranged in records with five fields: the name of the building, its location, its owner, its height, and its floor space. The location and owner fields are records that include all of the information that you would expect, such as street, city, and state, together with the owner's name (first, middle, last) in the owner field. Draw a rooted tree to describe this type of record

# Exercises10.4.6Exercises for Section 10.4

##### Exercise1

Draw the expression trees for the following expressions:

1. $a(b + c)$

2. $a b + c$

3. $a b + a c$

4. $b b - 4 a c$

5. $\left(\left(a_3 x + a_2\right)x +a_1\right)x + a_0$

##### Exercise3

Write out the preorder, inorder, and postorder traversals of the trees in Exercise 1 above.

##### Exercise5

1. Draw a binary tree with seven vertices and only one leaf.

2. (b) Draw a binary tree with seven vertices and as many leaves as possible.

##### Exercise7

Prove that if $T$ is a full binary tree, then the number of leaves of $T$ is one more than the number of internal vertices (non-leaves).

# Exercises11.1.4Exercises for Section 11.1

##### Exercise1

Determine the properties that the following operations have on the positive integers.

2. multiplication

3. $M$ defined by $a M b = \textrm{ larger} \textrm{ of} a \textrm{ and} b$

4. $m$ defined by $a m b = \textrm{ smaller} \textrm{ of } a \textrm{ and } b$

5. @ defined by $a @ b = a^b$

##### Exercise3

Let $*$ be an operation on a set $S$ and $A, B \subseteq S$. Prove that if $A$ and $B$ are both closed under $*$, then $A\cap B$ is also closed under $*$, but $A \cup B$ need not be.

##### Exercise5

Define $a * b$ by $\lvert a - b \rvert$, the absolute value of $a - b$. Which properties does $*$ have on the set of natural numbers, $\mathbb{N}\text{?}$

# Exercises11.2.4Exercises for Section 11.2

##### Exercise1

Discuss the analogy between the terms generic and concrete for algebraic systems and the terms generic and trade for prescription drugs.

##### Exercise3

Which of the following are groups?

1. $B^*$ with concatenation (see Subsection 11.2.1).

2. $M_{2\times 3}(\mathbb{R})$ with matrix addition.

3. $M_{2\times 3}(\mathbb{R})$ with matrix multiplication.

4. The positive real numbers, $\mathbb{R}^+,$with multiplication.

5. The nonzero real numbers, $\mathbb{R}^*$, with multiplication.

6. $\{1, -1\}$ with multiplication.

7. The positive integers with the operation $M$ defined by $a M b = \textrm{ the larger of } a \textrm{ and } b$.

##### Exercise5

The following problem supplies an example of a non-abelian group. A rook matrix is a matrix that has only 0's and 1's as entries such that each row has exactly one 1 and each column has exactly one 1. The term rook matrix is derived from the fact that each rook matrix represents the placement of $n$ rooks on an $n\times n$ chessboard such that none of the rooks can attack one another. A rook in chess can move only vertically or horizontally, but not diagonally. Let $R_n$ be the set of $n\times n$ rook matrices. There are six $3\times 3$ rook matrices: $\begin{array}{ccc} I=\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) & R_1=\left( \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{array} \right) & R_2=\left( \begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ F_1=\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{array} \right) & F_2=\left( \begin{array}{ccc} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array} \right) & F_3=\left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \\ \end{array}$

1. List the $2\times 2$ rook matrices. They form a group, $R_2,$ under matrix multiplication. Write out the multiplication table. Is the group abelian?

2. Write out the multiplication table for $R_3$ . This is another group. Is it abelian?

3. How many $4\times 4$ rook matrices are there? How many $n\times n$ rook matrices are there?

##### Exercise7

Let $V = \{e,a,b, c\}$. Let $*$ be defined (partially) by $x * x = e$ for all $x \in V$. Write a complete table for $*$ so that $[V; * ]$ is a group.

# Exercises11.3.1Exercises for Section 11.3

##### Exercise1

Let $[G; * ]$ be a group and $a$ be an element of $G\text{.}$ Define $f:G \to G$ by $f(x) = a * x$.

1. Prove that $f$ is a bijection.

2. On the basis of part a, describe a set of bijections on the set of integers.

##### Exercise3

Prove by induction on $n$ that if $a_1$, $a_2$, $\ldots$, $a_n$ are elements of a group $G\text{,}$ $n\geq 2$, then $\left(a_1*a_2*\cdots *a_n\right)^{-1}= a_n^{-1}*\cdots *a_2^{-1}*a_1^{-1}$. Interpret this result in terms of $[\mathbb{Z}; +]$ and $[\mathbb{R}^*;\cdot]$.

##### Exercise5

Prove Theorem 11.3.14.

# Exercises11.4.6Exercises for Section 11.4

##### Exercise1

Determine the greatest common divisors of the following pairs of integers without using any computational assistance.

1. $2^3 \cdot 3^2\cdot 5$ and $2^2 \cdot 3 \cdot 5^2\cdot 7$

2. $7!$ and $3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13$

3. $19^4$ and $19^5$

4. 12112 and 0

##### Exercise3

Calculate:

1. $7 +_8 3$

2. $7 \times_8 3$

3. $4\times_8 4$

4. $10+_{12} 2$

5. $6\times_8 2 +_8 6\times_8 5$

6. $6\times_8 \left(2 +_85\right)$

7. $3 \times_5 3 \times_5 3 \times_5 3 \equiv 3^4 (\textrm{ mod} 5)$

8. $2 \times_{11}7$

9. $2 \times_{14}7$

##### Exercise5

In the group $\mathbb{Z}_{11}$ , what are:

1. 3(4)?

2. 36(4)?

3. How could you efficiently compute $m(4)$, $m \in \mathbb{Z}$?

##### Exercise7

A student is asked to solve the following equations under the requirement that all arithmetic should be done in $\mathbb{Z}_2$. List all solutions.

1. $x^2 + 1 = 0$.

2. $x^2 + x + 1 = 0$.

##### Exercise10

Prove the division property, Theorem 11.4.1.

Hint

# Exercises11.5.1Exercises for Section 11.5

##### Exercise1

Which of the following subsets of the real numbers is a subgroup of $[\mathbb{R}; +]$?

1. the rational numbers

2. the positive real numbers

3. $\{k/2 \mid k \textrm{ is} \textrm{ an} \textrm{ integer}\}$

4. $\{2^k \mid k \textrm{ is an integer}\}$

5. $\{x \mid -100 \leq x \leq 100\}$

##### Exercise3

Find at least two proper subgroups of $R_3$ , the set of $3\times 3$ rook matrices (see Exercise 11.2.4.5).

##### Exercise5

1. List the cyclic subgroups of $\mathbb{Z}_6$ and draw an ordering diagram for the relation “is a subset of” on these subgroups.

2. Do the same for $\mathbb{Z}_{12}$.

3. Do the same for $\mathbb{Z}_8$.

4. On the basis of your results in parts a, b, and c, what would you expect if you did the same with $\mathbb{Z}_{24}$?

##### Exercise7

Prove that if $H,K \leq G$, and $H\cup K=G$, then $H = G$ or $K = G$.

# Exercises11.6.1Exercises for Section 11.6

##### Exercise1

Write out the group table of $\mathbb{Z}_2 \times \mathbb{Z}_3$ and find the two proper subgroups of this group.

##### Exercise3Algebraic properties of the $n$-cube

1. The four elements of $\mathbb{Z}_2^2$ can be visualized geometrically as the four corners of the 2-cube. Algebraically describe the statements:

1. Corners $a$ and $b$ are adjacent.

2. Corners $a$ and $b$ are diagonally opposite one another.

2. The eight elements of $\mathbb{Z}_2{}^3$ can be visualized as the eight corners of the 3-cube. One face contains $\mathbb{Z}_2 \times \mathbb{Z}_2\times \{0\}$ and the opposite face contains the remaining four elements so that $(a, b, 1)$ is behind $(a, b, 0)$. As in part a, describe statements i and ii algebraically.

3. If you could imagine a geometric figure similar to the square or cube in $n$ dimensions, and its comers were labeled by elements of $\mathbb{Z}_2{}^n$ as in parts a and b, how would statements i and ii be expressed algebraically?

##### Exercise5

Which of the following sets are subgroups of $\mathbb{Z} \times \mathbb{Z}$? Give a reason for any negative answers.

1. $\{0\}$

2. $\{(2j, 2k) \mid j,k\in \mathbb{Z}\}$

3. $\{(2j+ 1, 2k) \mid j,k\in \mathbb{Z}\}$

4. $\{(n, n^2 ) \mid n \in \mathbb{Z}\}$

5. $\{(j, k) \mid j + k\textrm{ is} \textrm{ even}\}$

# Exercises11.7.3Exercises for Section 11.7

##### Exercise1

State whether each pair of groups below is isomorphic. For each pair that is, give an isomorphism; for those that are not, give your reason.

1. $\mathbb{Z} \times \mathbb{R}$ and $\mathbb{R} \times \mathbb{Z}$

2. $\mathbb{Z}_2\times \mathbb{Z}$ and $\mathbb{Z} \times \mathbb{Z}$

3. $\mathbb{R}$ and $\mathbb{Q} \times \mathbb{Q}$

4. $\mathcal{P}(\{1, 2\})$ with symmetric difference and $\mathbb{Z}_2{}^2$

5. $\mathbb{Z}_2{}^2$ and $\mathbb{Z}_4$

6. $\mathbb{R}^4$ and $M_{2\times 2}(\mathbb{R})$ with matrix addition

7. $\mathbb{R}^2$ and $\mathbb{R} \times \mathbb{R}^+$

8. $\mathbb{Z}_2$ and the $2 \times 2$ rook matrices

9. $\mathbb{Z}_6$ and $\mathbb{Z}_2\times \mathbb{Z}_3$

##### Exercise3

Prove that the relation “is isomorphic to” on groups is transitive.

##### Exercise5

It can be shown that there are five non-isomorphic groups of order eight. You should be able to describe at least three of them. Do so without use of tables. Be sure to explain why they are not isomorphic.

##### Exercise7

Prove that all infinite cyclic groups are isomorphic to $\mathbb{Z}\text{.}$

# Exercises12.1.1Exercises for Section 12.1

##### Exercise1

Solve the following systems by describing the solution sets completely:

1. $\begin{array}{l} 2 x_1+x_2=3 \\ x_1-x_2=1 \\ \end{array}$

2. $\begin{array}{l} 2 x_1+x_2+3 x_3=5 \\ 4 x_1+x_2+2 x_3=-1 \\ 8 x_1+2 x_2+4 x_3=-2 \\ \end{array}$

3. $\begin{array}{l} x_1+x_2+2 x_3=1 \\ x_1+2 x_2-x_3=-1 \\ x_1+3 x_2+x_3=5 \\ \end{array}$

4. $\begin{array}{l} x_1-x_2+3 x_3=7 \\ x_1+3 x_2+x_3=4 \\ \end{array}$

##### Exercise3

Given the final augmented matrices below from the Gauss-Jordan Algorithm, identify the solutions sets. Identify the basic and free variables, and describe the solution set of the original system.

1. $\left( \begin{array}{cccc|c} 1 & 0 & -5 & 0 & 1.2 \\ 0 & 1 & 4 & 0 & 2.6 \\ 0 & 0 & 0 & 1 & 4.5 \\ \end{array} \right)$

2. $\left( \begin{array}{ccc|c} 1 & 0 & 9 & 3 \\ 0 & 1 & 0 & 4 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$

3. $\left( \begin{array}{ccc|c} 1 & 0 & 6 & 5 \\ 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)$

4. $\left( \begin{array}{cccc|c} 1 & 0 & 0 & -3 & 1 \\ 0 & 1 & 0 & 2 & 2 \\ 0 & 0 & 1 & -1 & 1 \\ \end{array} \right)$

##### Exercise5

Solve the following systems using only mod 5 arithmetic. Your solutions should be $n-\textrm{tuples}$ from $\mathbb{Z}_5$.

1. $\begin{array}{l} 2 x_1+ x_2=3 \\ x_1+4 x_2=1 \\ \end{array}$ (compare your solution to the system in 5(a))

2. $\begin{array}{l} x_1+x_2+2 x_3=1 \\ x_1+2 x_2+4 x_3=4 \\ x_1+3 x_2+3 x_3=0 \\ \end{array}$

##### Exercise7

Given a system of $n$ linear equations in $n$ unknowns in matrix form $A X = b$, prove that if $b$ is a matrix of all zeros, then the solution set of $A X = b$ is a subgroup of $\mathbb{R}^n$.

# Exercises12.2.1Exercises for Section 12.2

##### Exercise3

Use the method of this section to find the inverses of the following matrices whenever possible. If an inverse does not exist, explain why.

1. $\left( \begin{array}{cc} \frac{1}{3} & 2 \\ \frac{1}{5} & -1 \\ \end{array} \right)$

2. $\left( \begin{array}{cccc} 1 & 0 & 0 & 3 \\ 2 & -1 & 0 & 6 \\ 0 & 2 & 1 & 0 \\ 0 & -1 & 3 & 2 \\ \end{array} \right)$

3. $\left( \begin{array}{ccc} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \\ \end{array} \right)$

4. $\left( \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 2 & -1 \\ 1 & -1 & 1 \\ \end{array} \right)$

5. $\left( \begin{array}{ccc} 2 & 3 & 4 \\ 3 & 4 & 5 \\ 4 & 5 & 6 \\ \end{array} \right)$

6. $\left( \begin{array}{ccc} 1 & \frac{1}{2} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{3} & \frac{1}{4} \\ \frac{1}{3} & \frac{1}{4} & \frac{1}{5} \\ \end{array} \right)$

##### Exercise5

Express each system of equations in Exercise 12.1.1.1 in the form $A x = B$. When possible, solve each system by first finding the inverse of the matrix of coefficients.

# Exercises12.3.1Exercises for Section 12.3

##### Exercise3

1. Verify that $M_{2\times 3}\textrm{ ($$\mathbb{R}$)}$$ is a vector space over $\mathbb{R}\text{.}$ What is its dimension?

2. Is $M_{m\times n}\textrm{ ($$\mathbb{R}$)}$$ a vector space over $\mathbb{R}\text{?}$ If so, what is its dimension?

##### Exercise7

Express the vector $\left( \begin{array}{cc} 1 & 2 \\ -3 & 3 \\ \end{array} \right)\in M_{2\times 2}(\mathbb{R})$, as a linear combination of $\left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \\ \end{array} \right)$, $\left( \begin{array}{cc} -1 & 5 \\ 2 & 1 \\ \end{array} \right)$, $\left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \\ \end{array} \right)$ and $\left( \begin{array}{cc} 0 & 0 \\ 0 & 1 \\ \end{array} \right)$

##### Exercise9

1. Show that the set $\left\{\vec{x}_1,\vec{x}_2\right\}$ generates $\mathbb{R}^2$ for each of the parts in Exercise 6 of this section.

2. Show that $\left\{\vec{x}_1,\vec{x}_2,\vec{x}_3\right\}$ generates $\mathbb{R}^2$ where $\vec{x}_1= (1, 1)$, $\textrm{ }\vec{x}_2= (3,4)$, and $\vec{x}_3 = (-1, 5)$.

3. Create a set of four or more vectors that generates $\mathbb{R}^2$.

4. What is the smallest number of vectors needed to generate $\mathbb{R}^2$? $\mathbb{R}^n$?

5. Show that the set of matrices containing \begin{equation*} \begin{array}{cc} \left( \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ \end{array} \right) & \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \\ \end{array} \right) \\ \left( \begin{array}{cc} 0 & 0 \\ 1 & 0 \\ \end{array} \right) \textrm{ and}& \left( \begin{array}{cc} 0 & 0 \\ 0 & 1 \\ \end{array} \right)\\ \end{array} \end{equation*} generates $M_{2\times 2}(\mathbb{R})$

6. Show that $\left\{1,x,x^2 ,x^3\right\}$ generates $P^3$.

##### Exercise11

1. Prove that $\{(4, 1), (1, 3)\}$ is a basis for $\mathbb{R}^2$ over $\mathbb{R}\text{.}$

2. Prove that $\{(1, 0), (3, 4)\}$ is a basis for $\mathbb{R}^2$ over $\mathbb{R}\text{.}$

3. Prove that $\{(1,0, -1), (2, 1, 1), (1, -3, -1)\}$ is a basis for $\mathbb{R}^3$ over $\mathbb{R}\text{.}$

4. Prove that the sets in Exercise 9, parts e and f, form bases of the respective vector spaces.

##### Exercise13

1. Let $\vec{y}_1= (1,3, 5, 9)$, $\vec{y}_2= (5,7, 6, 3)$, and $c = 2$. Find $\vec{y}_1+\vec{y}_2$ and $c \vec{y}_1$.

2. Let $f_1(x) = 1 + 3x + 5x^2 + 9x^3$ , $f_2(x)=5 + 7x+6x^2+3x^3$ and $c = 2$. Find $f_1(x)+f_2(x)$ and $c f_1(x)$.

3. Let $A =\left( \begin{array}{cc} 1 & 3 \\ 5 & 9 \\ \end{array} \right)$, $B=\left( \begin{array}{cc} 5 & 7 \\ 6 & 3 \\ \end{array} \right)$, and $c=2$. Find $A + B$ and $c A$.

4. Are the vector spaces $\mathbb{R}^4$ , $P^3$ and $M_{2\times 2}(\mathbb{R})$ isomorphic to each other? Discuss with reference to previous parts of this exercise.

# Exercises12.4.1Exercises for Section 12.4

##### Exercise1

1. List three different eigenvectors of $A=\left( \begin{array}{cc} 2 & 1 \\ 2 & 3 \\ \end{array} \right)$, the matrix of Example 12.4.2, associated with each of the two eigenvalues 1 and 4. Verify your results.

2. Choose one of the three eigenvectors corresponding to 1 and one of the three eigenvectors corresponding to 4, and show that the two chosen vectors are linearly independent.

##### Exercise3

1. Verify that $P^{-1} A P$ is indeed equal to $\left( \begin{array}{cc} 1 & 0 \\ 0 & 4 \\ \end{array} \right)$, as indicated in Example 12.4.6

2. Choose $P^{(1)}=\left( \begin{array}{c} 1 \\ 2 \\ \end{array} \right)$ and $P^{(2)}=\left( \begin{array}{c} 1 \\ -1 \\ \end{array} \right)$ and verify that the new value of $P$ satisfies $P^{-1} A P=\left( \begin{array}{cc} 4 & 0 \\ 0 & 1 \\ \end{array} \right)$

3. Take any two linearly independent eigenvectors of the matrix $A$ of Example 12.4.6 and verify that $P^{-1} A P$ is a diagonal matrix.

##### Exercise5

Diagonalize the following, if possible:

1. $\left( \begin{array}{cc} 1 & 2 \\ 3 & 2 \\ \end{array} \right)$

2. $\left( \begin{array}{cc} -2 & 1 \\ -7 & 6 \\ \end{array} \right)$

3. $\left( \begin{array}{cc} 3 & 0 \\ 0 & 4 \\ \end{array} \right)$

4. $\left( \begin{array}{ccc} 1 & -1 & 4 \\ 3 & 2 & -1 \\ 2 & 1 & -1 \\ \end{array} \right)$

5. $\left( \begin{array}{ccc} 6 & 0 & 0 \\ 0 & 7 & -4 \\ 9 & 1 & 3 \\ \end{array} \right)$

6. $\left( \begin{array}{ccc} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \\ \end{array} \right)$

##### Exercise7

Let $A$ and $P$ be as in Example 12.4.8. Show that the columns of the matrix $A P$ can be found by computing $A P^{(1)}$, $A P^{(2)},\ldots,$ $A P^{(n)}$.

# Exercises12.5.1Exercises for Section 12.5

##### Exercise4

How many paths are there of length 6 from vertex 1 to vertex 3 in Figure 12.5.8? How many paths from vertex 2 to vertex 2 of length 6 are there?

Hint
##### Exercise5

Regarding Example 12.5.3,

1. Use matrices to determine the number of paths of length 1 that exist from vertex $a$ to each of the vertices in the given graph. Verify using the graph. Do the same for vertices $b$ and $c\text{.}$

2. Verify all the details provided in the example.

3. Use matrices to determine the number of paths of length 4 there between each pair of nodes in the graph. Verify your results using the graph.

##### Exercise7

We noted in Chapter 5 that since matrix algebra is not commutative under multiplication, certain difficulties arise. Let $A=\left( \begin{array}{cc} 1 & 1 \\ 0 & 0 \\ \end{array} \right)$ and $B=\left( \begin{array}{cc} 0 & 0 \\ 0 & 2 \\ \end{array} \right)$.

1. Compute $e^A$, $e^B$, and $e^{A+B}$. Compare $e^A e^{B}$, $e^B e^A$ and $e^{A+B}$ .

2. Show that if $\pmb{0}$ is the $2\times 2$ zero matrix, then $e^{\pmb{0}}= I$.

3. Prove that if $A$ and $B$ are two matrices that do commute, then $e^{A+B}=e^Ae^B$, thereby proving that $e^A$ and $e^B$ commute.

4. Prove that for any matrix $A\text{,}$ $\left(e^A\right)^{-1}= e^{-A}$.

# Exercises13.1.1Exercises for Section 13.1

##### Exercise1

Consider the poset $(D_{30},\mid)$, where $D_{30} = \{1,2, 3, 5, 6, 10, 15, 30\}$.

1. Find all lower bounds of 10 and 15.

2. Find the greatest lower bound of 10 and 15.

3. Find all upper bounds of 10 and 15.

4. Determine the least upper bound of 10 and 15.

5. Draw the Hasse diagram for $D_{30}$ with respect to $\div$. Compare this Hasse diagram with that of Example 13.1.10. Note that the two diagrams are structurally the same.

##### Exercise3

Figure 13.1.12 contains Hasse diagrams of posets.

1. Determine the least upper bound and greatest lower bound of all pairs of elements when they exist. Indicate those pairs that do not have a least upper bound (or a greatest lower bound ).

2. Find the least and greatest elements when they exist.

##### Exercise5

1. Prove the second part of Theorem 13.1.6, the least upper bound of two elements in a poset is unique, it one exists.

2. Prove that if a poset $L$ has a least element, then that element is unique.

# Exercises13.2.1Exercises for Section 13.2

##### Exercise5

What is a reasonable definition of the term sublattice?

# Exercises13.3.1Exercises for Section 13.3

##### Exercise1

Determine the complement of each element $B \in L$ in Example 13.3.4. Is this lattice a Boolean algebra? Why?

##### Exercise3

Determine which of the lattices of Exercise 13.1.1.3 of Section 13.1 are Boolean algebras.

##### Exercise5

It can be shown that the following statement, $S\text{,}$ holds for any Boolean algebra $[B; \lor , \land, -]$ : $(a \land b) = a$ if and only if $a \leq b$.

1. Write the dual, $S^*$, of the statement $S\text{.}$

2. Write the statement $S$ and its dual, $S^*$, in the language of sets.

3. Are the statements in part b true for all sets?

4. Write the statement $S$ and its dual, $S^*$, in the language of logic.

5. Are the statements in part d true for all propositions?

##### Exercise7

Formulate a definition for isomorphic Boolean algebras.

# Exercises13.4.1Exercises for Section 13.4

##### Exercise1

1. Show that $a = 2$ is an atom of the Boolean algebra $\left[D_{30}; \lor , \land, - \right]$.

2. Repeat part a for the elements 3 and 5 of $D_{30}$.

3. Verify Theorem Theorem 13.4.5 for the Boolean algebra $\left[D_{30}; \lor , \land, - \right]$.

##### Exercise3

Verify Theorem 13.4.6 and its corollaries for the Boolean algebras in Exercises 1 and 2 of this section.

##### Exercise5

Corollary 13.4.7 implies that there do not exist Boolean algebras of orders 3, 5, 6, 7, 9, etc. (orders different from $2^n$). Without this corollary, directly show that we cannot have a Boolean algebra of order 3.

##### Exercise7

Find a Boolean algebra with a countably infinite number of elements.

##### Exercise8

Prove that the direct product of two Boolean algebras is a Boolean algebra.

Hint

# Exercises13.5.1Exercises for Section 13.5

##### Exercise1

1. Write out the operation tables for $\left[B_2^2; \lor , \land, - \right].$

2. Draw the Hasse diagram for $\left[B_2^2; \lor , \land, - \right]$ and compare your results with Figure 9.4.6.

3. Find the atoms of this Boolean algebra.

##### Exercise3

1. List all atoms of $B_2^4$.

2. Describe the atoms of $B_2^n, n \geq 1$.

# Exercises13.6.1Exercises for Section 13.6

##### Exercise1

1. Write the 16 possible functions of Example 13.6.2.

2. Write out the tables of several of the above Boolean functions to show that they are indeed different.

3. Determine the minterm normal forms of

1. $g_1\left(x_1, x_2\right)=x_1\lor x_2,$

2. $g_2\left(x_1, x_2\right)=\overline{x_1}\lor \overline{x_2}$

3. $g_3\left(x_1, x_2\right)=\overline{x_1 \land x_2}$

4. $g_4\left(x_1, x_2\right)=1$

##### Exercise3

Let $[B; \lor , \land, - ]$ be a Boolean algebra of order 4, and let $f$ be a Boolean function of two variables on $B\text{.}$

1. How many elements are there in the domain of f?

2. How many different Boolean functions are there of two, variables? Three variables?

3. Determine the minterm normal form of $f\left(x_1, x_2\right)=x_1\lor x_2$.

4. If $B=\{0, a, b, 1\}$, define a function from $B^2$ into $B$ that is not a Boolean function.

# Exercises14.1.1Exercises for Section 14.1

##### Exercise1

For each of the subsets of the indicated monoid, determine whether the subset is a submonoid.

1. $S_1=\{0,2,4,6\}$ and $S_2=\{1,3,5,7\}$ in $[\mathbb{Z}_8;\times_8].$

2. $\{f\in \mathbb{N}^{\mathbb{N}}:f(n) \leqslant n, \forall n \in \mathbb{N}\}$ and $\left\{f\in \mathbb{N}^{\mathbb{N}}:f(1)=2\right\}$ in the monoid $[\mathbb{N}^{\mathbb{N}};\circ]$.

3. $\{A\subseteq \mathbb{Z} \mid A \textrm{ is finite}\} \textrm{ and} \left\{A\subseteq \mathbb{Z} \mid A^c\textrm{ is} \textrm{ finite}\right\}$ in $[\mathcal{P}(\mathbb{Z});\cup].$

##### Exercise3

An $n \times n$ matrix of real numbers is called stochastic if and only if each entry is nonnegative and the sum of entries in each column is 1. Prove that the set of stochastic matrices is a monoid over matrix multiplication.

##### Exercise5

Let $B$ be a Boolean algebra and $M$ the set of all Boolean functions on $B\text{.}$ Let $*$ be defined on $M$ by $(f * g)(a) = f(a) \land g(a)$. Prove that $[M,*]$ is a monoid. Construct the operation table of $[M,*]$ for the case of $B = B_2$.

# Exercises14.2.1Exercises for Section 14.2

##### Exercise1

1. If a computer is being designed to operate with a character set of 350 symbols, how many bits must be reserved for each character? Assume each character will use the same number of bits.

2. Do the same for 3,500 symbols.

##### Exercise3

What sets of strings are defined by the following grammar?

1. Terminal symbols: $\lambda$ , 0 and 1

2. Nonterminal symbols: $S$ and $E$

3. Starting symbol: $S$

4. Production rules: $S\to 0S0, S \to 1S1, S\to E, E \to \lambda, E\to 0, E\to 1$

##### Exercise5

Define the following languages over $B$ with phrase structure grammars. Which of these languages are regular?

1. The strings with an odd number of characters.

2. The strings of length 4 or less.

3. The palindromes, strings that are the same backwards as forwards.

##### Exercise7

Prove that if a language over $A$ is recursive, then its complement is also recursive.

##### Exercise9

1. Prove that if $X_1, X_2, \ldots$is a countable sequence of countable sets, the union of these sets, $\underset{i=1}{\overset{\infty }{\cup}}X_i$ is countable.

2. Using the fact that the countable union of countable sets is countable, prove that if $A$ is countable, then $A^*$ is countable.

# Exercises14.3.1Exercises for Section 14.3

##### Exercise1

Draw a transition diagram for the vending machine described in Example 14.3.1.

##### Exercise3

What is the input set for the binary adding machine in Example 14.3.9?

##### Exercise5

The Gray Code Decoder. The finite-state machine defined by the following figure has an interesting connection with the Gray Code.

Given a string $x=x_1x_2\cdots x_n\in B^n$, we may ask where $x$ appears in $G_n$. Starting in Copy state, the input string $x$ will result in an output string $z\in B^n$, which is the binary form of the position of $x$ in $G_n$. Recall that positions are numbered from 0 to $2^n-1$.

1. In what positions $(0-31)$ do 10110, 00100, and 11111 appear in $G_5$?

2. Prove that the Gray Code Decoder always works.

# Exercises14.4.1Exercises for Section 14.4

##### Exercise1

For each of the transition diagrams in Figure 14.4.4, write out tables for their associated monoids. Identify the identity in terms of a string of positive length, if possible. (Hint. : Where the output echoes the current state, the output can be ignored.)

##### Exercise3

Can two finite-state machines with nonisomorphic transition diagrams have isomorphic monoids?

# Exercises14.5.1Exercises for Section 14.5

##### Exercise1

Draw the transition diagrams for the machines of the following monoids:

1. $\left[\mathbb{Z}_4;+_4\right]$

2. The direct product of $\left[\mathbb{Z}_2;\times _2\right]$ with itself.

# Exercises15.1.1Exercises for Section 15.1

##### Exercise1

What generators besides 1 does $[\mathbb{Z}, +]$ have?

##### Exercise3

Prove that if $\lvert G \rvert >2$ and $G$ is cyclic, $G$ has at least two generators.

##### Exercise5

Which of the following groups are cyclic? Explain.

1. $[\mathbb{Q}, +]$

2. $[\mathbb{R}^+,\cdot ]$

3. $[6\mathbb{Z}, +]$ where $6\mathbb{Z} = \{6n |n \in \mathbb{Z}\}$

4. $\mathbb{Z} \times \mathbb{Z}$

5. $\mathbb{Z}_2\times \mathbb{Z}_3 \times \mathbb{Z}_{25}$

##### Exercise7

How can Theorem 15.1.13 be applied to list the generators of $\mathbb{Z}_n$? What are the generators of $\mathbb{Z}_{25}$? Of $\mathbb{Z}_{256}$?

##### Exercise9

1. Illustrate how the fast adder can be used to add the numbers 21, 5, 7, and 15 using the isomorphism between $\mathbb{Z}_{77}$ and $\mathbb{Z}_7\times \mathbb{Z}_{11}$.

2. If the same isomorphism is used to add the numbers 25, 26, and 40, what would the result be, why would it be incorrect, and how would the answer differ from the answer in part a?

# Exercises15.2.1Exercises for Section 15.2

##### Exercise1

Consider $\mathbb{Z}_{10}$ and the subsets of $\mathbb{Z}_{10}$, $\{0, 1, 2, 3, 4\}$ and $\{5, 6, 7, 8, 9\}$. Why is the operation induced on these subsets by modulo 10 addition not well defined?

##### Exercise3

For each group and subgroup, what is $G/H$ isomorphic to?

1. $G = \mathbb{Z}_4 \times \mathbb{Z}_2$ and $H = \langle (2, 0)\rangle$. Compare to Example 15.2.16.

2. $G = [\mathbb{C}, +]$ and $H = \mathbb{R}$.

3. $G$ = $\mathbb{Z}_{20}$ and $H = \langle 8\rangle$.

##### Exercise5

Prove that if $G$ is a group, $H \leq G$ and $a, b \in G$, $a*H= b*H$ if and only if $b^{-1}*a \in H$.

# Exercises15.3.5Exercises for Section 15.3

##### Exercise1

Given $f=\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{array} \right)$, $g=\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \right)$, and $h=\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \\ \end{array} \right)$, compute

1. $f\circ g$

2. $g\circ h$

3. $(f\circ g)\circ h$

4. $f\circ (g\circ h)$

5. $h^{-1}$

6. $h^{-1} g\circ h$

7. $f^{-1}$

##### Exercise3

Do the left cosets of $A_3=\left\{i,r_1,r_2\right\}$ over $S_3$ form a group under the induced operation on left cosets of $A_3$? What about the left cosets of $\left\langle f_1\right\rangle$?

##### Exercise5

1. Complete the list of elements of $D_4$ and write out a table for the group in its realization as symmetries.

2. List the subgroups of $D_4$ in a lattice diagram. Are they all cyclic? To what simpler groups are the subgroups of $D_4$ isomorphic?

##### Exercise7

Prove by induction that if $r \geq 1$ and each $t_i$, is a transposition, then $\left(t_1\circ t_2\circ \cdots \circ t_r\right){}^{-1}=t_r\circ \cdots \circ t_2\circ t_1$

##### Exercise9

Complete the proof of Theorem 15.3.9.

##### Exercise13

1. Prove that $S_3$ is isomorphic to $R_3$, the group of $3 \times 3$ rook matrices (see Section 11.2 exercises).

2. Prove that for each $n \geq 2$, $R_n$ is isomorphic to $S_n$.

# Exercises15.4.3Exercises for Section 15.4

##### Exercise1

Which of the following functions are homomorphisms? What are the kernels of those functions that are homomorphisms?

1. $\theta_1: \mathbb{R}^* \to \mathbb{R}^+$ defined by $\theta_1(a) =\left| a\right|$.

2. $\theta_2 : \mathbb{Z}_8 \rightarrow \mathbb{Z}_2$ where $\theta_2(n) =\left\{ \begin{array}{cc} 0 & \textrm{ if} n \textrm{ is} \textrm{ even} \\ 1 & \textrm{ if} n \textrm{ is} \textrm{ odd} \\ \end{array} \right.$ .

3. $\theta_3 : \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$, where $\theta_3(a, b) = a + b$.

4. $\theta_4 : S_4 \to S_4$ defined by $\theta_4(f) = f\circ f=f^2$.

##### Exercise3

Show that $D_4$ has one proper normal subgroup, but that $\langle (1,4)(2,3)\rangle$ is not normal.

##### Exercise5

Define the two functions $\alpha: \mathbb{Z}_2{}^3\rightarrow \mathbb{Z}_2{}^4$ and $\beta :\mathbb{Z}_2{}^4\to \mathbb{Z}_2$ by $\alpha\left(a_1,a_2,a_3 \right) = \left(a_1,a_2,a_3 ,a_1+_2 a_2+_2a_3\right)$, and $\beta \left(b_1,b_2,b_3,b_4\right)=b_1+b_2+b_3+b_4$ Describe the function $\beta \circ \alpha$. Is it a homomorphism?

##### Exercise7

Prove that if $G$ is an abelian group, then $q(x) = x^2$ defines a homomorphism from $G$ into $G\text{.}$ Is $q$ ever an isomorphism?

##### Exercise9

Prove that if $\theta : G \rightarrow G'$ is a homomorphism, and $H' \leq \theta(G)$, then $\theta^{-1}(H') =\{a\in G| \theta (a)\in H'\}\leq G$.

# Exercises15.5.3Exercises for Section 15.5

##### Exercise1

If the error-detecting code is being used, how would you act on the following received blocks?

1. $(1, 0, 1, 1)$

2. $(1, 1, 1, 1)$

3. $(0, 0, 0, 0)$

##### Exercise3

If the error-correcting code is being used, how would you decode the following blocks? Expect a problem with one of these. Why?

1. $(1,0,0,0,1,1)$

2. $(1,0,1,0,1,1)$

3. $(0,1,1,1,1,0)$

4. $(0,0,0,1,1,0)$

##### Exercise5

Consider the linear code defined the generator matrix\\ $G=\left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ \end{array} \right)$

1. What size blocks does this code encode and what is the length of the code words?

2. What are the code words for this code?

3. With this code, can you detect single bit errors? Can you correct all, some, or no single bit errors?

# Exercises16.1.6Exercises for Section 16.1

##### Exercise1

Review the definition of rings to show that the following are rings. The operations involved are the usual operations defined on the sets. Which of these rings are commutative? Which are rings with unity? For the rings with unity, determine the unity and all units.

1. $[\mathbb{Z};+,\cdot ]$

2. $[\mathbb{C};+,\cdot ]$

3. $[\mathbb{Q};+,\cdot ]$

4. $\left[M_{2\times 2}(\mathbb{R}),+, \cdot \right]$

5. $\left[\mathbb{Z}_2,+_2,\times_2\right]$

##### Exercise3

Show that the following pairs of rings are not isomorphic:

1. $[\mathbb{Z};+,\cdot ]$ and $\left[M_{2\times 2}(\mathbb{Z}),+,\cdot \right]$

2. $[3\mathbb{Z};+, \cdot ]$ and $[4\mathbb{Z};+, \cdot ]$.

##### Exercise5

1. Show that $3\mathbb{Z}$ is a subring of the ring $[\mathbb{Z}, +, \cdot]$

2. Find all subrings of $\mathbb{Z}_8$.

3. Find all subrings of $\mathbb{Z}_2 \times \mathbb{Z}_2$.

##### Exercise7

1. Determine all solutions of the equation $x^2 - 5x + 6 = 0$ in $\mathbb{Z}\text{.}$ Can there be any more than two solutions to this equation (or any quadratic equation) in $\mathbb{Z}\text{?}$

2. Find all solutions of the equation in part a in $\mathbb{Z}_{12}$. Why are there more than two solutions?

##### Exercise9

The relation “is isomorphic to” on rings is an equivalence relation. Explain the meaning of this statement.

##### Exercise11

1. Prove that the ring \textrm{ $\mathbb{Z}_2$} x \textrm{ $\mathbb{Z}_3$} is commutative and has unity.

2. Determine all zero divisors for the ring \textrm{ $\mathbb{Z}_2$} x \textrm{ $\mathbb{Z}_3$}.

3. Give another example illustrating the fact that the product of two integral domains may not be an integral domain. Is there an example where the product is an integral domain?

##### Exercise13

1. For any ring $[R; +, \cdot ]$, expand $(a + b)(c + d)$ for $a, b, c, d \in R$.

2. If $R$ is commutative, prove that $(a + b)^2 = a^2 + 2a b + b^2$ for all $a, b \in R$.

# Exercises16.2.1Exercises for Section 16.2

##### Exercise5

Determine all values $x$ from the given field that satisfy the given equation:

1. $x + 1 = -1$ in $\mathbb{Z}_2$ , $\mathbb{Z}_3$ and $\mathbb{Z}_5$

2. $2x + 1 = 2$ in $\mathbb{Z}_3$ and $\mathbb{Z}_5$

3. $3x + 1 = 2$ $\mathbb{Z}_5$

##### Exercise7

The following are equations over \textrm{ $\mathbb{Z}_2$} . Their coefficients come solely from \textrm{ $\mathbb{Z}_2$} . Determine all solutions over \textrm{ $\mathbb{Z}_2$}; that is, find all elements of \textrm{ $\mathbb{Z}_2$} that satisfy the equations:

1. $x^2 + x = 0$

2. $x^2 + 1 = 0$

3. $x^3 + x^2 + x + 1 = 0$

4. $x^3 + x + 1 = 0$

# Exercises16.3.1Exercises for Section 16.3

##### Exercise1

Let $f(x) = 1 + x$ and $g(x) = 1 + x + x^2$. Compute the following sums and products in the indicated rings.

1. $f(x) + g(x)$ and $f(x) \cdot g(x)$ in $\mathbb{Z}[x]$

2. $f(x) + g(x)$ and $f(x) \cdot g(x)$ in $\mathbb{Z}_2[x]$

3. $(f(x)\cdot g(x))\cdot f(x)$ in $\textrm{ $$\mathbb{Q}$[x]}$$

4. $(f(x) \cdot g(x)) \cdot f(x)$ in $\mathbb{Z}_2[x]$

5. $f(x) \cdot f(x) + f(x)\cdot g(x)$ in $\mathbb{Z}_2[x]$

##### Exercise3

Prove that:

1. The ring $\mathbb{R}$ is a subring of the ring $\mathbb{R}[x]$.

2. The ring $\mathbb{Z}[x]$ is a subring of the $\mathbb{Q}[x]$.

3. The ring $\mathbb{Q}[x]$ is a subring of the ring $\mathbb{R}[x]$.

##### Exercise5

Determine which of the following are reducible over \textrm{ $\mathbb{Z}_2$} . Explain.

1. $f(x) = x^3 + 1$

2. $g(x) = x^3 + x^2 + x$.

3. $h(x) = x^3+ x^2 + 1$.

4. $k(x) = x^4 +x^2+ 1$. (Be careful.)

##### Exercise7

Give an example of the contention made in the last paragraph of this section.

##### Exercise9

Show that $x^2 - 3$ is irreducible over $\mathbb{Q}$ but reducible over the field of real numbers.

##### Exercise11

Prove Theorem 16.3.11, the Division Property for Polynomials

# Exercises16.4.1Exercises for Section 16.4

##### Exercise1

1. Use the definition of a field to show that $\mathbb{Q}$(\textrm{ $\sqrt{2}$}) is a field.

2. Use the definition of vector space to show that $\mathbb{Q}\left(\sqrt{2}\right)$ is a vector space over $\mathbb{Q}\text{.}$

3. Prove that $\left\{1,\sqrt{2}\right\}$ is a basis for the vector space $\mathbb{Q}\left(\sqrt{2}\right)$ over $\mathbb{Q}\text{,}$ and, therefore, the dimension of $\mathbb{Q}$(\textrm{ $\sqrt{2}$}) over $\mathbb{Q}$ is 2.

##### Exercise3

Determine the splitting field of $x^4 - 5x^2 + 6$ over $\mathbb{Q}\text{.}$

##### Exercise5

1. Show that $x^3+ x + 1$ is irreducible over $\mathbb{Z}_2$.

2. Determine the splitting field of $x^3+ x + 1$ over $\mathbb{Z}_2$.

3. By Theorem 16.2.10, you have described all fields of order $2^3$.

# Exercises16.5.1Exercises for Section 16.5

##### Exercise5

1. Determine the inverse of $h(x) = \sum_{i=0}^{\infty } 2^i x^i$ in $\mathbb{Q}[[x]]$.

2. Use the procedures in Chapter 8 to find a rational generating function for $h(x)$ in part a. Find the multiplicative inverse of this function.

##### Exercise7

Write as an extended power series:

1. $\left(x^4-x^5\right)^{-1}$

2. $\left(x^2-2x^3+x^4\right)^{-1}$

# ExercisesA.1.4Exercises for Part 1 of the Algorithms Appendix

##### Exercise2

What is wrong with this algorithm?

Input: a and b, integers
Output: the value of c will be a - b
(1) c = 0
(2) While a > b:
(2.1) a := a - l
(2.2) c := c + l