INSTRUCTOR SOLUTIONS MANUAL for Discrete Mathematics with Applications, 5th Edition by Susanna Epp
Instructor’s Manual Section 1.1 1
Chapter 1: Speaking Mathematically
Many college and university students have difficulty using and interpreting language involving if-then statements and quantification. Section 1.1 is a gentle introduction to the relation between informal and formal ways of expressing such statements. The exercises are intended to start the process of helping students improve their ability to interpret mathematical statements and evaluate their truth or falsity. Sections 1.2 - 1.4 are a brief introduction to the language of sets, relations, functions, and graphs. Including Sections 1.2 and 1.3 at the beginning of the course can help students relate discrete mathematics to the pre-calculus or calculus they have studied previously while enlarging their perspective to include a greater proportion of discrete examples. Section 1.4 is designed to broaden students’ understanding of the way the word graph is used in mathematics and to show them how graph models can be used to solve some significant problems.
Proofs of set properties, such as the distributive laws, and proofs of properties of relations and functions, such as transitivity and surjectivity, are considerably more complex than those used in Chapter 4 to give students their first practice in constructing mathematical proofs. For this reason set theory as a theory is left to Chapter 6, properties of functions to Chapter 7, and properties of relations to Chapter 8. By making slight changes about exercise choices, instructors could cover Section 1.2 just before starting Chapter 6 and Section 1.3 just before starting Chapter 7.
The material in Section 1.4 lays the groundwork for the discussion of the handshake theorem and its applications in Section 4.9. Instructors who wish to offer a self-contained treatment of graph theory can combine both sections with the material in Chapter 10.
College and university mathematics instructors may be surprised by the way students understand the meaning of the term “real number.” When asked to evaluate the truth or falsity of a statement about real numbers, it is not unusual for students to think only of integers. Thus an informal description of the relationship between real numbers and points on a number line is given in Section 1.2 to illustrate that there are many real numbers between any pair of consecutive integers, Examples 3.3.5 and 3.3.6 show that while there is a smallest positive integer there is no smallest positive real number, and the discussion in Chapter 7, which precedes the proof of the uncountability of the real numbers between 0 and 1, describes a procedure for approximating the (possibly infinite) decimal expansion for an arbitrarily chosen point on a number line.
Section 1.1
1. a. x2 = 1 (Or : the square of x is 1) b a real number x
2. a. a remainder of 2 when it is divided by 5 and a remainder of 3 when it is divided by 6 b. an integer n; n is divided by 6 the remainder is 3
3. a. between a and b b distinct real numbers a and b; there is a real number c
4. a. a real number; greater than r b. real number r; there is a real number s
5. a. r is positive
b. positive; the reciprocal of r is positive (Or : positive; 1/r is positive) c. is positive; 1/r is positive (Or : is positive; the reciprocal of r is positive)
6. a. s is negative b. negative; the cube root of s is negative (Or : c. is negative; √ 3 s is negative (Or: the cube root of s is negative) √ 3 s is negative)
Instructor’s Manual: Chapter 1
7. a. There are real numbers whose sum is less than their difference. True. For example, 1 + ( 1) = 0, 1 ( 1) = 1 + 1 = 2, and 0 < 2.
b. There is a real number whose square is less than itself. True. For example, (1/2)2 = 1/4 < 1/2
c. The square of each positive integer is greater than or equal to the integer.
True. If n is any positive integer, then n ≥ 1. Multiplying both sides by the positive number n does not change the direction of the inequality (see Appendix A, T20), and so n2 ≥ n.
d. The absolute value of the sum of any two numbers is less than or equal to the sum of their absolute values.
True. This is known as the triangle inequality. It is discussed in Section 4.4.
8. a. have four sides b. has four sides c. has four sides d. is a square; has four sides e. J has four sides
9. a. have at most two real solutions b. has at most two real solutions c. has at most two real solutions d. is a quadratic equation; has at most two real solutions e. E has at most two real solutions
10. a. have reciprocals b. a reciprocal c. s is a reciprocal for r
11. a. have positive square roots b. a positive square root c. r is a square root for e
12. a. real number; product with every number leaves the number unchanged b. a positive square root c. rs = s
13. a. real number; product with every real number equals zero b. with every number leaves the number unchanged c. ab = 0
1.2
1. A = C and B = D
2. a. The set of all positive real numbers x such that 0 is less than x and x is less than 1
b. The set of all real numbers x such that x is less than or equal to zero or x is greater than or equal to 1
c. The set of all integers n such that n is a factor of 6
d. The set of all positive integers n such that n is a factor of 6
3. a. No, 4 is a set with one element, namely 4, whereas 4 is just a symbol that represents the number 4
b. Three: the elements of the set are 3, 4, and 5.
c. Three: the elements are the symbol 1, the set {1}, and the set {1, {1}}
4. a. Yes: 2 is the set whose only element is 2. b. One: 2 is the only element in this set c. Two: The two elements are 0 and 0 d. Yes: 0 is one of the elements listed in the set.
e. No: The only elements listed in the set are 0 and 1 , and 0 is not equal to either of these.
Section
5. The only sets that are equal to each other are A and D.
A contains the integers 0, 1, and 2 and nothing else.
B contains all the real numbers that are greater than or equal to 1 and less than 3.
C contains all the real numbers that are greater than 1 and less than 3. Thus 1 is in B but not in C
D contains all the integers greater than 1 and less than 3. Thus D contains the integers 0, 1, and 2 and nothing else, and so D = {0, 1, 2} = A
E contains all the positive integers greater than 1 and less than 3. Hence E contains the integers 1 and 2 and nothing else, that is, E = {1, 2}
6. T2 and T−3 each have two elements, and T0 and T1 each have one element.
JustiFIcation: T2 = {2, 22} = {2, 4}, T−3 = {−3, ( 3)2} = {−3, 9}, T1 = {1, 12} = {
and
7. a. {1, 1}
b. T = {m ∈ Z | m = 1+( 1)k for some integer k} = {0, 2} Exercises in Chapter 4 explore the fact that ( 1)k = 1 when k is odd and ( 1)k = 1 when k is even. So 1+( 1)k = 1+( 1) = 0 when k is odd, and 1 + ( 1)k = 1 + 1 = 2 when k is even.
c. the set has no elements
d. Z (every integer is in the set)
e. There are no elements in W because there are no integers that are both greater than 1 and less than 3
f. X = Z because every integer u satisfies at least one of the conditions u ≤ 4 or u ≥ 1
8. a. No, B ¢ A because j ∈ B and j ∈ / A
b. Yes, because every element in C is in A. c. Yes, because every element in C is in C.
c.. Yes, because it is true that every element in C is in C.
d. Yes, C is a proper subset of A. Both elements of C are in A, but A contains elements (namely c and f ) that are not in C.
9. a. Yes
b. No, the number 1 is not a set and so it cannot be a subset.
c. No: The only elements in {1, 2} are 1 and 2, and {2} is not equal to either of these.
d. Yes: {3} is one of the elements listed in {1, {2}, {3}}.
e. Yes: {1} is the set whose only element is 1.
f. No, the only element in {2} is the number 2 and the number 2 is not one of the three elements in {1, {2}, {3}}.
g. Yes: The only element in {1} is 1, and 1 is an element in {1, 2}.
h. No: The only elements in {{1}, 2} are {1} and 2, and 1 is not equal to either of these.
i. Yes, the only element in {1} is the number 1, which is an element in {1, {2}}
j. Yes: The only element in {1} is 1, which is is an element in {1}. So every element in {1} is in {1}.
10. a. No. Observe that ( 2)2 = ( 2)( 2) = 4, whereas 22 = (22) = 4. So (( 2)2 , 22) = (4, 4), whereas ( 22 , ( 2)2) = ( 4, 4). And (4, 4) = ( 4, 4) because 4 = 4.
b. No: For two ordered pairs to be equal, the elements in each pair must occur in the same order. In this case the first element of the first pair is 5, whereas the first element of the second
Instructor’s Manual: Chapter 1
pair is 5, and the second element of the first pair is 5 whereas the second element of the second pair is 5.
c. Yes. Note that 8 9 = 1 and √ 3 1 = 1, and so (8 9, √ 3 1) = ( 1, 1).
d. Yes The first elements of both pairs equal 1 , and the second elements of both pairs equal 8.
11. a. {(w, a), (w, b), (x, a), (x, b), (y, a), (y, b), (z, a), (z, b)} A × B has 4 · 2 = 8 elements.
b. {(a, w), (b, w), (a, x), (b, x), (a, y), (b, y), (a, z), (b, z)} B × A has 4 · 2 = 8 elements.
c. {(w, w), (w, x), (w, y), (w, z), (x, w), (x, x), (x, y), (x, z), (y, w), (y, x), (y, y), (y, z), (z, w), (z, x), (z, y), (z, z)} A × A has 4 · 4 = 16 elements.
d. {(a, a), (a, b), (b, a), (b, b)} B × B has 2 2 = 4 elements.
12. All four sets have nine elements.
a. S × T = {(2, 1), (2, 3), (2, 5), (4, 1), (4, 3), (4, 5), (6, 1), (6, 3), (6, 5)}
b. T × S = {(1, 2), (3, 2), (5, 2), (1, 4), (3, 4), (5, 4), (1, 6), (3, 6), (5, 6)}
c. S × S = {(2, 2), (2, 4), (2, 6), (4, 2), (4, 4), (4, 6), (6, 2), (6, 4), (6, 6)}
d. T × T = {(1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)}
13. a. A × (B × C) = {(1, (u, m)), (1, (u, n)), (2, (u, m)), (2, (u, n)), (3, (u, m)), (3, (u, n))}
b. (A × B) × C = {((1, u), m), ((1, u), n), ((2, u), m), ((2, u), n), ((3, u), m), ((3, u), n)}
c. A × B × C = {(1, u, m), (1, u, n), (2, u, m), (2, u, n), (3, u, m), (3, u, n)}
14. a.R × (S × T ) = {(a, (x, p)), (a, (x, q)), (a, (x, r)), (a, (y, p)), (a, (y, q)), (a, (y, r))}
b. (R × S) × T = {((a, x), p), ((a, x), q), ((a, x), r), ((a, y), p), ((a, y), q), ((a, y), r)}
c. R × S × T = {(a, x, p), (a, x, q), (a, x, r), (a, y, p), (a, y, q), (a, y, r)}
15. 0000, 0001, 0010, 0100, 1000
16. yxxxx, xyxxx, xxyxx, xxxyx, xxxxy
Section 1.3
1. a. No. Yes. No. Yes.
b. R = {(2, 6), (2, 8), (2, 10), (3, 6), (4, 8)}
c. Domain of R = A = {2, 3, 4}, co-domain of R = B = {6, 8, 10}
d.
2. a. 2 S 2 because 1 1 = 0, which is an integer. 2 2 1 1 1 S 1 because −1 −1 = 0, which is an integer.
3 S 3 because 1 1 = 0, which is an integer.
3 3
3 S/ 3 because 1 1 = 2 , which is not an integer. 3 −3 3
b. S = {( 3, 3), ( 2, 2), ( 1, 1), (1, 1), (2, 2), (3, 3), (1, 1), ( 1, 1), (2, 2), ( 2, 2)}
c. The domain and co-domain of S are both {−3, 2, 1, 1, 2, 3}
d. S
D
3. a. 3 T 0 because 3−0 = 3 = 1, which is an integer. 3 3
1 T ( 1) because 1 ( 1) = 2 , which is not an integer.
(2, 1) ∈ T because 2−(−1) = 3 = 1, which is an integer.
(3, 2) ∈ / T because 3 ( 2) = 5 , which is not an integer. 3 3
b. T = {(1, 2), (2, 1), (3, 0)}
c. Domain of T = E = {1, 2, 3}, co-domain of T = F = {−2, 1, 0}
d. T 1 –2 2 –1 3 0
4. a. 2 V 6 because 2−6 = −4 = 1, which is an integer.
1 V ( 1) because ( 2) 8 = 6 , which is not an integer. ( 2) V 8 because ( 2) 8 = 6 , which is not an integer.
0 V 6 because 0 6 = 6 , which is not an integer.
2 V 4 because 2 4 = 2 , which is not an integer.
b. V = {( 2, 6), (0, 4), (0, 8), (2, 6)}
c. Domain of V = {−2, 0, 2}, co-domain of V = {4, 6, 8}
d. S G H
5. a. (2, 1) ∈ S because 2 ≥ 1. (2, 2) ∈ S because 2 ≥ 2. 2 S 3 because 2 § 3. ( 1)S( 2) because 1 ≥ 2.
Instructor’s Manual: Chapter 1
x $ y in shaded region
6. a. (2, 4) ∈ R because 4 = 22
(4, 2) ∈ / R because 2 = 42
( 3, 9) ∈ R because 9 = ( 3)2
(9, 3) ∈ / R because 3 = 92 b.
of S
7. a.
b. R is not a function because it satisfies neither property (1) nor property (2) of the definition. It fails property (1) because (4, y) / R, for any y in B. It fails property (2) because (6, 5) R and (6, 6) R and 5 = 6.
S is not a function because (5, 5) S and (5, 7) S and 5 = 7. So S does not satisfy property (2) of the definition of function.
T is not a function both because (5, x) ∈ / T for any x in B and because (6, 5) ∈ T and (6, 7) T and 5 = 7. So T does not satisfy either property (1) or property (2) of the definition of function.
graph