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

AppendixBHints and Solutions to Selected Exercises

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

Answer
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 \}\)

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

Answer

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

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

Answer
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\}\)

Answer
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

  2. undergraduate mathematics majors

  3. non-math graduate students

  4. non-math undergraduate students

Answer

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

Answer
Exercise3

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

Answer
Exercise5

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

Answer
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?

Answer
Exercise9

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

Answer

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

Answer
Exercise3

What positive integers have the following binary representations?

  1. 10010

  2. 10011

  3. 101010

  4. 10011110000

Answer
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}\)

Answer
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?

Answer

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

Answer
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}\)

Answer
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{.}\)

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

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

Answer

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?

Answer
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?

Answer
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?

Answer
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?

Answer
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?

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

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

Answer
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?

Answer
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?

Answer
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?

Answer

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?

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

Answer
Exercise5

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

Answer
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?

Answer
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?

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

Answer

Exercises2.3.1Exercises for Section 2.3

Exercise1

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

Answer
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?

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

Answer
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?

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

Answer

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 ?

Answer
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?

Answer
Exercise5

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

Answer
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?

Answer
Exercise9

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

Answer
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?

Answer
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?

Answer
Exercise15

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

Answer
Exercise17

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

HintAnswer

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.

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

Answer
Exercise5

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

Answer

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

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

Answer
Exercise5

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

Answer

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

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

Answer

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

Answer
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*}

Answer

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

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

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

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

Answer

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

Answer
Exercise2

Over the universe of positive integers, define

\(p(n)\): \(n\) is prime and \(n < 32\).
\(q(n)\): \(n\) is a power of 3.
\(r(n)\): \(n\) is a divisor of 27.

  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?

Answer
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{.}\)

Answer
Exercise7

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

\(a\text{:}\) \(0 < n^2 < 9\)
\(b\text{:}\) \(0 < n^3 < 27\)
\(c\text{:}\) \(0 < n < 3\)
Solution

Exercises3.7.1Exercises for Section 3.7

Exercise1

Prove that the sum of the first \(n\) odd integers equals \(n^2\) .

Answer
Exercise3

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

Answer
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*}

Answer
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{.}\)

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

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

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

Answer
Exercise5

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

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

Answer
Exercise9

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

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

Answer

Exercises3.9.3Exercises for Section 3.9

Exercise1

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

Answer
Exercise3

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

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

Answer

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

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

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

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

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

Answer
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\)?

Answer
Exercise7

Prove Theorem 4.3.6

Answer

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

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

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

Answer

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

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

Answer
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?

Answer
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} \)

Answer

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

Answer
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}\)?
Answer

Exercises5.3.1Exercises

Exercise1

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

Answer
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}\)

Answer

Exercises5.4.1Exercises

Exercise1

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

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

Answer
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}\)

Answer

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)

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

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

Answer

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

Answer
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{.}\)

Answer

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.

Answer
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?

Some digraphs of relations for exercise 3 of section 6.3
Figure6.3.16Some digraphs of relations
Answer
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{.}\)

Answer
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{.}\)

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

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

Answer

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

Answer
Exercise3

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

Answer
Exercise5

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

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

Answer
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{?}\)

Answer

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

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

Answer

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

Answer
Exercise3

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

Answer
Exercise7

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

Answer

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.

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

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

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

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

Answer
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{.}\)

Answer
Exercise13

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

Answer

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?

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

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

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

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

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

Answer

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

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

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

Answer

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

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

A general configuration of three lines
Figure8.2.3A general configuration of three lines
Answer
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.

Answer

Exercises8.3.5Exercises for Section 8.3

Exercise1

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

Answer
Exercise3

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

Answer
Exercise5

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

Answer
Exercise7

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

Answer
Exercise9

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

Answer
Exercise11

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

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

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

Answer

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

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

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

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

Answer

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

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

Answer
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}\)

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

Answer
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?

Answer

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?

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

Answer
Exercise5

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

Answer
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?

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

Answer

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

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

Answer

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.

Answer
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?

Answer
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{.}\)

Answer

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.

Answer
Exercise3

Write out the Gray Code for the 4-cube.

Answer
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?

Answer
Exercise7

Formulate Euler's theorem for directed graphs.

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

Answer

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?

Answer
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)\}\)

Answer
Exercise5

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

Figure for Exercise 9-5-5

  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.

Answer
Exercise7

Find maximal flows for the following networks.

Figure for Exercise 9-5-7a
Figure for Exercise 9-5-7b
Figure for Exercise 9-5-7c
Answer
Exercise9

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

HintAnswer

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?

Answer
Exercise3

What are the chromatic numbers of the following graphs?

What are the chromatic numbers?
Figure9.6.20What are the chromatic numbers?
Answer
Exercise5

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

Answer
Exercise7

Complete the proof of Theorem 9.6.8.

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

Answer
Exercise11

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

Answer
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?

Answer

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

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

Answer

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?

Answer
Exercise3

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

Answer
Exercise5

Find a minimum diameter spanning tree for the following graphs.

Figure for exercise-10-2-5a
Figure for exercise-10-2-5b
Answer

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

Answer
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

Answer

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

Answer
Exercise3

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

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

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

Answer

Exercises11.1.4Exercises for Section 11.1

Exercise1

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

  1. addition

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

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

Answer
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{?}\)

Answer

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.

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

Answer
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?

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

Answer

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.

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

Answer
Exercise5

Prove Theorem 11.3.14.

Answer

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

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

Answer
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}\)?

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

Answer
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\}\)

Answer
Exercise3

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

Answer
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}\)?

Answer
Exercise7

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

HintAnswer

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.

Answer
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?

Answer
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}\}\)

Answer

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

Answer
Exercise3

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

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

Answer
Exercise7

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

Answer

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

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

Answer
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}\)

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

Answer

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

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

Answer

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?

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

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

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

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

Answer

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.

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

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

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

Answer

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?

Graph for exercise 4
Figure12.5.8Graph for exercise 4
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.

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

Answer

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.

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

Section 13.1, Exercise 3
Figure13.1.12Figure for Exercise 3
Answer
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.

Answer

Exercises13.2.1Exercises for Section 13.2

Exercise5

What is a reasonable definition of the term sublattice?

Answer

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?

Answer
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?

Answer
Exercise7

Formulate a definition for isomorphic Boolean algebras.

Answer

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

Answer
Exercise3

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

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

HintAnswer
Exercise7

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

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

Answer
Exercise3

  1. List all atoms of \(B_2^4\).

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

Answer

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

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

Answer

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

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

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

Answer

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.

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

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

Answer
Exercise7

Prove that if a language over \(A\) is recursive, then its complement is also recursive.

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

Answer

Exercises14.3.1Exercises for Section 14.3

Exercise1

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

Answer
Exercise3

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

Answer
Exercise5

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

Gray Code Decoder
Figure14.3.12Gray Code Decoder

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.

Answer

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

Exercise 1 of section 14.4
Figure14.4.4Exercise 1
Answer
Exercise3

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

Answer

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.

Answer

Exercises15.1.1Exercises for Section 15.1

Exercise1

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

Answer
Exercise3

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

Answer
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}\)

Answer
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}\)?

Answer
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?

Answer

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?

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

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

Answer

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

Answer
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\)?

Answer
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?

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

Answer
Exercise9

Complete the proof of Theorem 15.3.9.

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

Answer

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

Answer
Exercise3

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

Answer
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?

Answer
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?

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

Answer

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

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

Answer
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?

Answer

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

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

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

Answer
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?

Answer
Exercise9

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

Answer
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?

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

Answer

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

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

Answer

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

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

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

Answer
Exercise7

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

Answer
Exercise9

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

Answer
Exercise11

Prove Theorem 16.3.11, the Division Property for Polynomials

Answer

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.

Answer
Exercise3

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

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

Answer

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.

Answer
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}\)

Answer

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
Answer

ExercisesA.2.1Exercises for Part 2 of the Algorithms Appendix

Exercise2

Verify the correctness of the following algorithm to compute the greatest common divisor of two integers that are not both zero.

Hint