Issuu

SOLUTIONS MANUAL Discrete Mathematics, 8th Edition by Richard Johnsonbaugh Solutions to Selected Exercises Section 1.1 2. {2, 4} 8. A

3. {7, 10} 9. ∅

15. {2, 3, 4, 5, 6, 7, 8, 9, 10}

5. {2, 3, 5, 6, 8, 9} 11. B

12. {1, 4} 18. {n ∈ Z+ | n ≥ 6}

21. {n ∈ Z+ | n ≤ 5 or n = 2m, m ≥ 3} 25. {n ∈ Z+ | n ≤ 5 or n = 2m + 1, m ≥ 3} 29. 1

6. {1, 3, 5, 7, 9, 10} 14. {1} 19. {2n − 1 | n ∈ Z+ }

22. {2n | n ≥ 3}

24. {1, 3, 5}

27. {n ∈ Z+ | n ≥ 6 or n = 2 or n = 4}

30. 3

33. We find that B = {2, 3}. Since A and B have the same elements, they are equal. 34. Let x ∈ A. Then x = 1, 2, 3. If x = 1, since 1 ∈ Z+ and 12 < 10, then x ∈ B. If x = 2, since 2 ∈ Z+ and 22 < 10, then x ∈ B. If x = 3, since 3 ∈ Z+ and 32 < 10, then x ∈ B. Thus if x ∈ A, then x ∈ B.

Now suppose that x ∈ B. Then x ∈ Z+ and x2 < 10. If x ≥ 4, then x2 > 10 and, for these values of x, x∈ / B. Therefore x = 1, 2, 3. For each of these values, x2 < 10 and x is indeed in B. Also, for each of the values x = 1, 2, 3, x ∈ A. Thus if x ∈ B, then x ∈ A. Therefore A = B.

37. Since (−1)3 − 2(−1)2 − (−1) + 2 = 0, −1 ∈ B. Since −1 ∈ / A, A 6= B. 38. Since 32 − 1 > 3, 3 ∈ / B. Since 3 ∈ A, A 6= B.

41. Equal

42. Not equal

45. Let x ∈ A. Then x = 1, 2. If x = 1, x3 − 6x2 + 11x = 13 − 6 · 12 + 11 · 1 = 6. Thus x ∈ B. If x = 2,

x3 − 6x2 + 11x = 23 − 6 · 22 + 11 · 2 = 6.

Again x ∈ B. Therefore A ⊆ B. 46. Let x ∈ A. Then x = (1, 1) or x = (1, 2). In either case, x ∈ B. Therefore A ⊆ B. 49. Since (−1)3 − 2(−1)2 − (−1) + 2 = 0, −1 ∈ A. However, −1 ∈ / B. Therefore A is not a subset of B. 50. Consider 4, which is in A. If 4 ∈ B, then 4 ∈ A and 4 + m = 8 for some m ∈ C. However, the only value of m for which 4 + m = 8 is m = 4 and 4 ∈ / C. Therefore 4 ∈ / B. Since 4 ∈ A and 4 ∈ / B, A is not a subset of B. Copyright c 2018 Pearson Education, Inc.

SOLUTIONS 53. U A

54. U A

56. A

57.

U A B C

59. A

62. 32

63. 105

65. 51

67. Suppose that n students are taking both a mathematics course and a computer science course. Then 4n students are taking a mathematics course, but not a computer science course, and 7n students are taking a computer science course, but not a mathematics course. The following Venn diagram depicts the situation: Copyright c 2018 Pearson Education, Inc.

SOLUTIONS '$ '$ CompSci

Math

&% &%

Thus, the total number of students is 4n + n + 7n = 12n. The proportion taking a mathematics course is 5 5n = , 12n 12 which is greater than one-third. 69. {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)} 70. {(1, 1), (1, 2), (2, 1), (2, 2)}

73. {(1, a, a), (2, a, a)}

74. {(1, 1, 1), (1, 2, 1), (2, 1, 1), (2, 2, 1), (1, 1, 2), (1, 2, 2), (2, 1, 2), (2, 2, 2)} 77. Vertical lines (parallel) spaced one unit apart extending infinitely to the left and right. 79. Consider all points on a horizontal line one unit apart. Now copy these points by moving the horizontal line n units straight up and straight down for all integers n > 0. The set of all points obtained in this way is the set Z × Z. 80. Ordinary 3-space 82. Take the lines described in the instructions for this set of exercises and copy them by moving n units out and back for all n > 0. The set of all points obtained in this way is the set R × Z × Z. 84. {1, 2} {1}, {2} 85. {a, b, c} {a, b}, {c} {a, c}, {b} {b, c}, {a} {a}, {b}, {c} 88. False

89. True

91. False

92. True

94. ∅, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}. All except {a, b, c, d} are proper subsets. 95. 210 = 1024; 210 − 1 = 1023

98. B ⊆ A

99. A = U

102. The symmetric difference of two sets consists of the elements in one or the other but not both. 103. A 4 A = ∅, A 4 A = U , U 4 A = A, ∅ 4 A = A 105. The set of primes Copyright c 2018 Pearson Education, Inc.

SOLUTIONS

Section 1.2 2. Is a proposition. Negation: 6 + 9 6= 15. 3. Not a proposition 4. Is a proposition. Negation: π 6= 3.14. 6. Is a proposition. Negation: For every positive integer n, 19340 6= n · 17. 7. Is a proposition. Negation: Audrey Meadows was not the original “Alice” in the “Honeymooners.” 9. Is a proposition. Negation: The line “Play it again, Sam” does not occur in the movie Casablanca. 10. Is a proposition. Some even integer greater than 4 is not the sum of two primes. 12. Not a proposition. The statement is neither true nor false. 13. No heads were obtained. 19. True 24.

25.

27.

21. False

p T T F F

q T F T F

(¬p ∨ ¬q) ∨ p T T T T

p T T F F

q T F T F

(p ∨ q) ∧ ¬p F F T F

p T T F F

q T F T F

(p ∧ q) ∨ (¬p ∨ q) T F T T

p T T T T F F F F

q T T F F T T F F

r T F T F T F T F

15. No heads or no tails were obtained. 22. False

28. ¬(p ∧ q) ∨ (r ∧ ¬p) F F T T T T T T Copyright c 2018 Pearson Education, Inc.

18. True

SOLUTIONS 30. p T T T T F F F F

q T T F F T T F F

r T F T F T F T F

¬(p ∧ q) ∨ (¬q ∨ r) T F T T T T T T

32. ¬(p ∧ q). True.

33. p ∨ ¬(q ∧ r). True.

35. Lee takes computer science and mathematics. 36. Lee takes computer science or mathematics. 38. Lee takes computer science but not mathematics. 39. Lee takes neither computer science nor mathematics. 41. You do not miss the midterm exam and you pass the course. 42. You play football or you miss the midterm exam or you pass the course. 44. Either you play football and you miss the midterm exam or you do not miss the midterm exam and you pass the course. 46. It is not Monday and either it is raining or it is hot. 47. It is not the case that today is Monday or it is raining, and it is hot. 50. Today is Monday and either it is raining or it is hot, and it is hot or either it is raining or today is Monday. 51. p ∧ q

52. p ∧ ¬q

54. p ∨ q

58. (p ∨ r) ∧ q

60. (q ∨ ¬p) ∧ ¬r

65. ¬p ∧ ¬q ∧ r

66. ¬(p ∨ q ∨ ¬r)

67.

p T T F F

q T F T F

55. (p ∨ q) ∧ ¬p 62. p ∧ ¬r

57. p ∧ r ∧ q

63. p ∧ q ∧ r

p exor q F T T F

69. Inclusive-or

70. Inclusive-or

72. Exclusive-or

77. ”lung disease” -cancer 78. ”minor league” baseball team illinois -”midwest league” Copyright c 2018 Pearson Education, Inc.

73. Exclusive-or

SOLUTIONS

Section 1.3 2. If Rosa has 160 quarter-hours of credits, then she may graduate. 3. If Fernando buys a computer, then he obtains $2000. 5. If a person gets that job, then that person knows someone who knows the boss. 6. If you go to the Super Bowl, then you can afford the ticket. 8. If a better car is built, then Buick will build it. 9. If the chairperson gives the lecture, then the audience will go to sleep. 11. If the switch is not turned properly, then the light will not be on. 13. Contrapositive of Exercise 2: If Rosa does not graduate, then she does not have 160 quarter-hours of credits. 15. False

16. False

18. False

24. Unknown

25. Unknown

31. Unknown

34. True

40. True

41. False

48. (¬p ∨ ¬r) → ¬q

19. True

27. True 35. True 44. (p ∧ r) → q

49. r → q

21. True

28. Unknown 37. True

22. True 30. Unknown

38. False

45. ¬((r ∧ ¬q) → r)

51. q → (p ∨ r)

52. (q ∧ p) → ¬r

54. If it is not raining, then it is hot and today is Monday. 55. If today is not Monday, then either it is raining or it is hot. 57. If today is Monday and either it is raining or it is hot, then either it is hot, it is raining, or today is Monday. 58. If today is Monday or (it is not Monday and it is not the case that (it is raining or it is hot)), then either today is Monday or it is not the case that (it is hot or it is raining). 60. Let p: 4 > 6 and q: 9 > 12. Given statement: p → q; true. Converse: q → p; if 9 > 12, then 4 > 6; true. Contrapositive: ¬q → ¬p; if 9 ≤ 12, then 4 ≤ 6; true. 61. Let p: |1| < 3 and q: −3 < 1 < 3. Given statement: q → p; true. Converse: p → q; if |1| < 3, then −3 < 1 < 3; true. Contrapositive: ¬p → ¬q; if |1| ≥ 3, then either −3 ≥ 1 or 1 ≥ 3; true. 64. P 6≡ Q

65. P ≡ Q

67. P 6≡ Q

68. P ≡ Q

71. P 6≡ Q

74. Either Dale is not smart or not funny.

70. P 6≡ Q

75. Shirley will not take the bus and not catch a ride to school. 78. (a) If p and q are both false, (p imp2 q) ∧ (q imp2 p) is false, but p ↔ q is true. (b) Making the suggested change does not alter the last line of the imp2 table.

79.

p T T F F

q T F T F

¬(p ∧ q) F T T T

¬p ∨ ¬q F T T T Copyright c 2018 Pearson Education, Inc.

SOLUTIONS

Section 1.4 2. Invalid p→q ¬r → ¬q ... r 3. Valid p↔r r ... p 5. Valid p → (q ∨ r) ¬q ∧ ¬r ... ¬p 7. Valid (p ∨ q) → (r ∨ s) p ∧ ¬r ... s 8. Invalid p→r q→s ¬(q ∧ p) ¬p ... s 11. If 4 megabytes of memory is better than no memory at all, then either we will buy a new computer or we will buy more memory. If we will buy a new computer, then we will not buy more memory. Therefore if 4 megabytes of memory is better than no memory at all, then we will buy a new computer. Invalid. 12. If 4 megabytes of memory is better than no memory at all, then we will buy a new computer. If we will buy a new computer, then we will buy more memory. Therefore, we will buy more memory. Invalid. 14. If 4 megabytes of memory is better than no memory at all, then we will buy a new computer. If we will buy a new computer, then we will buy more memory. 4 megabytes of memory is better than no memory at all. Therefore we will buy more memory. Valid. 16. If the hardware is unreliable or the output is correct, then the while loop is not faulty. If the output is correct, then the while loop is faulty. Either the for loop is faulty or the output is correct. Therefore the hardware is unreliable. Invalid. 17. If, if the for loop is faulty, then the hardware is unreliable, then the while loop is faulty. If, if the while loop is faulty, then the output is correct, then the for loop is faulty. The hardware is unreliable and the output is correct. Either the for loop is faulty or the while loop is faulty. Therefore the for loop is faulty and the while loop is faulty. Invalid. 19. If the for loop is faulty, then the while loop is faulty or the hardware is unreliable. If the while loop is faulty, then the for loop is faulty or the output is correct. Either the for loop is faulty or the while loop is not faulty. The output is not correct. Therefore the for loop is faulty or the hardware is unreliable. Invalid. Copyright c 2018 Pearson Education, Inc.

SOLUTIONS 21. Valid

22. Valid

24. Valid

25. Suppose that p1 , p2 , . . . , pn are all true. Since the argument p1 , p2 / ... p is valid, p is true. Since p, p3, . . . , pn are all true and the argument p, p3 , . . . , pn / ... c is valid, c is true. Therefore the argument p1 , p2 , . . . , pn / ... c is valid. 28. Modus ponens

29. Disjunctive syllogism

31. Let p denote the proposition “there is gas in the car,” let q denote the proposition “I go to the store,” let r denote the proposition “I get a soda,” and let s denote the proposition “the car transmission is defective.” Then the hypotheses are: p → q, q → r, ¬r. From p → q and q → r, we may use the hypothetical syllogism to conclude p → r. From p → r and ¬r, we may use modus tollens to conclude ¬p. From ¬p, we may use addition to conclude ¬p ∨ s. Since ¬p ∨ s represents the proposition “there is not gas in the car or the car transmission is defective,” we conclude that the conclusion does follow from the hypotheses. 32. Let p denote the proposition “Jill can sing,” let q denote the proposition “Dweezle can play,” let r denote the proposition “I’ll buy the compact disk,” and let s denote the proposition “I’ll buy the compact disk player.” Then the hypotheses are: (p ∨ q) → r, p, s. From p, we may use addition to conclude p ∨ q. From p ∨ q and (p ∨ q) → r, we may use modus ponens to conclude r. From r and s, we may use conjunction to conclude r ∧ s. Since r ∧ s represents the proposition “I’ll buy the compact disk and the compact disk player,” we conclude that the conclusion does follow from the hypotheses. 34. The truth table p T T F F

q T F T F

p∨q T T T F

shows that whenever p is true, p ∨ q is also true. Therefore addition is a valid argument. 35. The truth table p T T F F

q T F T F

p∧q T F F F

shows that whenever p ∧ q is true, p is also true. Therefore simplification is a valid argument. Copyright c 2018 Pearson Education, Inc.

SOLUTIONS 37. The truth table p T T T T F F F F

q T T F F T T F F

r T F T F T F T F

p→q T T F F T T T T

q→r T F T T T F T T

p→r T F T F T T T T

shows that whenever p → q and q → r are true, p → r is also true. Therefore hypothetical syllogism is a valid argument. 38. The truth table p T T F F

q T F T F

p∨q T T T F

¬p F F T T

shows that whenever p ∨ q and ¬p are true, q is also true. Therefore disjunctive syllogism is a valid argument.

Section 1.5 2. The statement is a command, not a propositional function. 3. The statement is a command, not a propositional function. 5. The statement is not a propositional function since it has no variables. 6. The statement is a propositional function. The domain of discourse is the set of real numbers. 8. 1 divides 77. True.

9. 3 divides 77. False.

11. For some n, n divides 77. True.

12. For every n, n does not divide 77. False. 14. It is false that for every n, n divides 77. True. 15. It is false that for some n, n divides 77. False. 17. False

18. True

20. True

21. True

23. False

26. ¬P (1) ∧ ¬P (2) ∧ ¬P (3) ∧ ¬P (4)

27. ¬(P (1) ∧ P (2) ∧ P (3) ∧ P (4))

29. ¬P (1) ∨ ¬P (2) ∨ ¬P (3) ∨ ¬P (4)

30. ¬(P (1) ∨ P (2) ∨ P (3) ∨ P (4))

33. Some student is taking a math course. 34. Every student is not taking a math course. 36. It is not the case that every student is taking a math course. Copyright c 2018 Pearson Education, Inc.

24. True

SOLUTIONS

37. It is not the case that some student is taking a math course. 40. There is some person such that if the person is a professional athlete, then the person plays soccer. True. 41. Every soccer player is a professional athlete. False. 43. Every person is either a professional athlete or a soccer player. False. 44. Someone is either a professional athlete or a soccer player. True. 46. Someone is a professional athlete and a soccer player. True. 49. ∃x(P (x) ∧ Q(x)) 50. ∀x(Q(x) → P (x)) 54. True

55. True

57. False

58. True

60. No. The suggested replacement returns false if ¬P (d1) is true, and true if ¬P (d1) is false. 62. Literal meaning: Every old thing does not covet a twenty-something. Intended meaning: Some old thing does not covet a twenty-something. Let P (x) denote the statement “x is an old thing” and Q(x) denote the statement “x covets a twenty-something.” The intended statement is ∃x(P (x) ∧ ¬Q(x)). 63. Literal meaning: Every hospital did not report every month. (Domain of discourse: the 74 hospitals.) Intended meaning (most likely): Some hospital did not report every month. Let P (x) denote the statement “x is a hospital” and Q(x) denote the statement “x reports every month.” The intended statement is ∃x(P (x) ∧ ¬Q(x)). 65. Literal meaning: Everyone does not have a degree. (Domain of discourse: People in Door County.) Intended meaning: Someone does not have a degree. Let P (x) denote the statement “x has a degree.” The intended statement is ∃x¬P (x). 66. Literal meaning: No lampshade can be cleaned. Intended meaning: Some lampshade cannot be cleaned. Let P (x) denote the statement “x is a lampshade” and Q(x) denote the statement “x can be cleaned.” The intended statement is ∃x(P (x) ∧ ¬Q(x)). 68. Literal meaning: No person can afford a home. Intended meaning: Some person cannot afford a home. Let P (x) denote the statement “x is a person” and Q(x) denote the statement “x can afford a home.” The intended statement is ∃x(P (x) ∧ ¬Q(x)). 69. The literal meaning is as Mr. Bush spoke. He probably meant: Someone in this country doesn’t agree with the decisions I’ve made. Let P (x) denote the statement “x agrees with the decisions I’ve made.” Symbolically, the clarified statement is ∃x ¬P (x). 71. Literal meaning: Every move does not work out. Intended meaning: Some move does not work out. Let P (x) denote the statement “x is a move” and Q(x) denote the statement “x works out .” The intended statement is ∃x(P (x) ∧ ¬Q(x)). 74. Let p(x) : x is good. q(x) : x is too long. r(x) : x is short enough. The domain of discourse is the set of movies. The assertions are Copyright c 2018 Pearson Education, Inc.

SOLUTIONS ∀x(p(x) → ¬q(x)) ∀x(¬p(x) → ¬r(x)) p(Love Actually) q(Love Actually). By universal instantiation, p(Love Actually) → ¬q(Love Actually).

Since p(Love Actually) is true, then ¬q(Love Actually) is also true. But this contradicts, q(Love Actually). 77. Let P (x) denote the propositional function “x is a member of the Titans,” let Q(x) denote the propositional function “x can hit the ball a long way,” and let R(x) denote the propositional function “x can make a lot of money.” The hypotheses are P (Ken), Q(Ken), ∀x Q(x) → R(x). By universal instantiation, we have Q(Ken) → R(Ken). From Q(Ken) and Q(Ken) → R(Ken), we may use modus ponens to conclude R(Ken). From P (Ken) and R(Ken), we may use conjunction to conclude P (Ken) ∧ R(Ken). By existential generalization, we have ∃x P (x) ∧ R(x) or, in words, someone is a member of the Titans and can make a lot of money. We conclude that the conclusion does follow from the hypotheses. 78. Let P (x) denote the propositional function “x is in the discrete mathematics class,” let Q(x) denote the propositional function “x loves proofs,” and let R(x) denote the propositional function “x has taken calculus.” The hypotheses are ∀x P (x) → Q(x), ∃x P (x) ∧ ¬R(x). By existential instantiation, we have P (d) ∧ ¬R(d) for some d in the domain of discourse. From P (d) ∧ ¬R(d), we may use simplification to conclude P (d) and ¬R(d). By universal instantiation, we have P (d) → Q(d). From P (d) → Q(d) and P (d), we may use modus ponens to conclude Q(d). From Q(d) and ¬R(d), we may use conjunction to conclude Q(d) ∧ ¬R(d). By existential generalization, we have ∃ Q(x) ∧ ¬R(x) or, in words, someone who loves proofs has never taken calculus. We conclude that the conclusion does follow from the hypotheses. 80. By definition, the proposition ∃x ∈ D P (x) is true when P (x) is true for some x in the domain of discourse. Taking x equal to a d ∈ D for which P (d) is true, we find that P (d) is true for some d ∈ D. 81. By definition, the proposition ∃x ∈ D P (x) is true when P (x) is true for some x in the domain of discourse. Since P (d) is true for some d ∈ D, ∃x ∈ D P (x) is true.

Section 1.6 2. Everyone is taller than someone. 3. Someone is taller than everyone. The solutions for 7–20 are for Exercise 2. 7. False

8. False

10. False

11. False

16. False

17. True

19. True

20. False

13. False

14. False

SOLUTIONS

23. Everyone is taller than or the same height as someone. 24. Someone is taller than or the same height as everyone. 29. For every person, there is a person such that if the persons are distinct, the first is taller than the second. 30. There is a person such that, for every person, if the persons are distinct, the first is taller than the second. 35. ∀x∀yL(x, y). False.

36. ∃x∃yL(x, y). True.

41. ∀x∃yE(x) → A(x, y)

44. True

40. ∀x ¬A(x, Profesor Sandwich)

45. False

52. False

53. False

55. False

56. False

61. True

62. False

64. True

65. True

49. True

50. False

58. True

59. True

67. for i = 1 to n if (forall dj (i)) return true return false forall dj (i) { for j = 1 to n if (¬P (di , dj )) return false return true } 68. for i = 1 to n for j = 1 to n if (P (di , dj )) return true return false 70. Since the first two quantifiers are universal and the last quantifier is existential, Farley chooses x and y, after which, you choose z. If Farley chooses values that make x ≥ y, say x = y = 0, whatever value you choose for z, (z > x) ∧ (z < y) is false. Since Farley can always win the game, the quantified propositional function is false. 71. Since the first two quantifiers are universal and the last quantifier is existential, Farley chooses x and y, after which, you choose z. Whatever values Farley chooses, you can choose z to be one less than the minimum of x and y; thus making (z < x) ∧ (z < y) true. Since you can always win the game, the quantified propositional function is true. 73. Since the first two quantifiers are universal and the last quantifier is existential, Farley chooses x and y, after which, you choose z. If Farley chooses values such that x ≥ y, the proposition (x < y) → ((z > x) ∧ (z < y)) is true by default (i.e., it is true regardless of what value you choose for z). If Farley chooses values such that x < y, you can choose z = (x + y)/2 and again the proposition (x < y) → ((z > x) ∧ (z < y)) is true. Since you can always win the game, the quantified propositional function is true. Copyright c 2018 Pearson Education, Inc.

SOLUTIONS

75. The proposition must be true. P (x, y) is true for all x and y; therefore, no matter which value for x we choose, the proposition ∀yP (x, y) is true. 76. The proposition must be true. Since P (x, y) is true for all x and y, we may choose any values for x and y to make P (x, y) true. 78. The proposition can be false. Let N denote the set of persons James James, Terry James, and Lee James; let the domain of discourse be N × N ; and let P (x, y) be the statement “x’s first name is the same as y’s last name.” Then ∃x∀yP (x, y) is true, but ∀x∃yP (x, y) is false. 79. The proposition must be true. Since ∃x∀yP (x, y) is true, there is some value for x for which ∀yP (x, y) is true. Choosing any value for y whatsoever makes P (x, y) true. Therefore ∃x∃yP (x, y) is true. 81. The proposition can be false. Let P (x, y) be the statement x > y and let the domain of discourse be Z+ × Z+ . Then ∃x∃yP (x, y) is true, but ∀x∃yP (x, y) is false. 82. The proposition can be false. Let P (x, y) be the statement x > y and let the domain of discourse be Z+ × Z+ . Then ∃x∃yP (x, y) is true, but ∃x∀yP (x, y) is false. 84. The proposition can be true. Let P (x, y) be the statement x ≤ y and let the domain of discourse be Z+ × Z+ . Then ∀x∀yP (x, y) is false, but ∃x∀yP (x, y) is true. 85. The proposition can be true. Let P (x, y) be the statement x ≤ y and let the domain of discourse be Z+ × Z+ . Then ∀x∀yP (x, y) is false, but ∃x∃yP (x, y) is true. 87. The proposition can be true. Let N denote the set of persons James James, Terry James, and Lee James; let the domain of discourse be N × N ; and let P (x, y) be the statement “x’s first name is different from y’s last name.” Then ∀x∃yP (x, y) is false, but ∃x∀yP (x, y) is true. 88. The proposition can be true. Let P (x, y) be the statement x > y and let the domain of discourse be Z+ × Z+ . Then ∀x∃yP (x, y) is false, but ∃x∃yP (x, y) is true. 90. The proposition can be true. Let P (x, y) be the statement x < y and let the domain of discourse be Z+ × Z+ . Then ∃x∀yP (x, y) is false, but ∀x∃yP (x, y) is true. 91. The proposition can be true. Let P (x, y) be the statement x ≤ y and let the domain of discourse be Z × Z. Then ∃x∀yP (x, y) is false, but ∃x∃yP (x, y) is true. 93. ∀x ∃y P (x, y) must be false. Since ∃x ∃y P (x, y) is false, for every x and for every y, P (x, y) is false. Choose x = x0 in the domain of discourse. For this choice of x, P (x, y) is false for every y. Therefore ∀x ∃y P (x, y) is false. 94. ∃x ∀y P (x, y) must be false. Since ∃x ∃y P (x, y) is false, for every x and for every y, P (x, y) is false. Choose y = y0 in the domain of discourse. Now, for any choice of x, P (x, y) is false for y = y0 . Therefore ∃x ∀y P (x, y) is false. 96. Not equivalent. Let P (x, y) be the statement x > y and let the domain of discourse be Z+ × Z+ . Then ¬(∀x∃yP (x, y)) is true, but ∀x¬(∃yP (x, y)) is false. 97. Equivalent by De Morgan’s law 100. ∃ε > 0 ∀δ > 0 ∃x ((0 < |x − a| < δ) ∧ (|f(x) − L| ≥ ε)) 101. ∀L ∃ε > 0 ∀δ > 0 ∃x ((0 < |x − a| < δ) ∧ (|f(x) − L| ≥ ε)) 102. Literal meaning: No school may be right for every child. Intended meaning: Some school may not be right for some child. Let P (x, y) denote the statement “school x is right for child y.” The intended statement is ∃x∃y¬P (x, y). Copyright c 2018 Pearson Education, Inc.

SOLUTIONS

Problem-Solving Corner: Quantifiers 1. The statement of Example 1.6.6 is ∀x∃y(x + y = 0). As was pointed out in Example 1.6.6, this statement is true. Now ∀x∀y(x + y = 0) is false; a counterexample is x = y = 1. Also ∃x∀y(x + y = 0) is false since, given any x, if y = 1 − x, then x + y 6= 0. 2. Yes; the statement ∀m∃n(m < n) with domain of discourse Z × Z of Example 1.6.1 also solves problems (a) and (b).

Section 2.1 2. For all x, for all y, x + y = y + x. 3. An isosceles trapezoid is a trapezoid with equal legs. 5. The medians of any triangle intersect at a single point. 6. If 0 < x < 1 and ε > 0, there exists a positive integer n satisfying xn < ε. 8. Let m and n be odd integers. Then there exist k1 and k2 such that m = 2k1 + 1 and n = 2k2 + 1. Now m + n = (2k1 + 1) + (2k2 + 1) = 2(k1 + k2 + 1). Therefore, m + n is even. 9. Let m and n be even integers. Then there exist k1 and k2 such that m = 2k1 and n = 2k2 . Now mn = (2k1 )(2k2 ) = 2(2k1 k2 ). Therefore, mn is even. 11. Let m be an odd integer and n be an even integer. Then there exist k1 and k2 such that m = 2k1 + 1 and n = 2k2. Now mn = (2k1 + 1)(2k2 ) = 2(2k1 k2 + k2 ). Therefore, mn is even. 12. Let m and n be integers such that m and m + n are even. Then there exist k1 and k2 such that m = 2k1 and m + n = 2k2 . Now n = (m + n) − m = 2k2 − 2k1 = 2(k2 − k1 ). Therefore, n is even. 14. Let x and y be rational numbers. Then there exist integers m1 , n1 , m2 , n2 such that x = m1 /n1 and y = m2 /n2 . Now xy = (m1 m2 )/(n1 n2 ). Therefore xy is rational. 15. Let x be a nonzero rational number. Then there exist integers m 6= 0 and n 6= 0 such that x = m/n. Now 1/x = n/m. Therefore 1/x is rational. Copyright c 2018 Pearson Education, Inc.

SOLUTIONS 17. Let m = 3k1 + 2 and n = 3k2 + 2 be integers of the prescribed from. Then mn = 9k1 k2 + 6k1 + 6k2 + 4 = 3(3k1 k2 + 2k1 + 2k2 + 1) + 1 is of the form 3k3 + 1, where k3 = 3k1 k2 + 2k1 + 2k2 + 1. 19. x · 0 + 0 = x · 0 because b + 0 = b for all real numbers b = x · (0 + 0) because b + 0 = b for all real numbers b = x · 0 + x · 0 because a(b + c) = ab + ac for all real numbers a, b, c

Taking a = c = x · 0 and b = 0, the preceding equation becomes a + b = a + c; therefore, 0 = b = c = x · 0. 20. We must have X = Y . To prove this, suppose that x ∈ X. Since Y is nonempty, choose y ∈ Y . Then (x, y) ∈ X × Y . Since X × Y = Y × X, (x, y) ∈ Y × X. Therefore x ∈ Y . Similarly, if x ∈ Y , then x ∈ X. Thus X = Y . 22. Let x ∈ X. Then x ∈ X ∪ Y . Therefore X ⊆ X ∪ Y . 23. Let x ∈ X ∪ Z. Then x ∈ X or x ∈ Z. If x ∈ X, since X ⊆ Y , x ∈ Y . Therefore x ∈ Y ∪ Z. If x ∈ Z, then x ∈ Y ∪ Z. In either case, x ∈ Y ∪ Z. Therefore X ∪ Z ⊆ Y ∪ Z. 25. Let x ∈ Z − Y . Then x ∈ Z and x ∈ / Y . Now x cannot be in X, for if x ∈ X, since X ⊆ Y , then x ∈ Y , which is not the case. Since x ∈ Z and x ∈ / X, x ∈ Z − X. Therefore Z − Y ⊆ Z − X. 26. Let x ∈ Y − (Y − X). Then x ∈ Y and x ∈ / Y − X. Since x ∈ Y , we must have x ∈ X (if x ∈ / X, we would have x ∈ Y − X). Therefore Y − (Y − X) ⊆ X. Now let x ∈ X. Then x ∈ / Y − X. Since X ⊆ Y , x ∈ Y . Thus x ∈ Y − (Y − X). Therefore X ⊆ Y − (Y − X). We have shown that Y − (Y − X) = X. 28. Let Z ∈ P(X) ∪ P(Y ). Then Z ∈ P(X) or Z ∈ P(Y ). If Z ∈ P(X), then Z is a subset of X and, thus, Z is also a subset of X ∪ Y . Therefore Z ∈ P(X ∪ Y ). Similarly, if Z ∈ P(Y ), Z ∈ P(X ∪ Y ). In either case, Z ∈ P(X ∪ Y ). Therefore P(X) ∪ P(Y ) ⊆ P(X ∪ Y ). 29. Let Z ∈ P(X ∩ Y ). Then Z is a subset of X ∩ Y . Therefore Z is a subset of X and a subset of Y . Thus Z ∈ P(X) ∩ P(Y ). We have proved that P(X ∩ Y ) ⊆ P(X) ∩ P(Y ). Let Z ∈ P(X) ∩ P(Y ). Then Z ∈ P(X) and Z ∈ P(Y ). Since Z ∈ P(X), Z is a subset of X. Since Z ∈ P(Y ), Z is a subset of Y . Since Z is a subset of X and Y , Z is a subset of X ∩Y . Thus Z ∈ P(X ∩Y ). Therefore P(X) ∩ P(Y ) ⊆ P(X ∩ Y ). It follows that P(X ∩ Y ) = P(X) ∩ P(Y ). 31. Let X = {a} and Y = {b}. Then P(X) = {∅, {a}},

P(Y ) = {∅, {b}},

so P(X) ∪ P(Y ) = {∅, {a}, {b}}. Since X ∪ Y = {a, b},

P(X ∪ Y ) = {∅, {a}, {b}, {a, b}}.

Now {a, b} ∈ P(X ∪ Y ), but {a, b} ∈ / P(X) ∪ P(Y ). Therefore P(X ∪ Y ) ⊆ P(X) ∪ P(Y ) is false in general. Copyright c 2018 Pearson Education, Inc.

16 32.

SOLUTIONS (X ∩ Y ) − (X ∩ Z)

= =

(X ∩ Y ) ∩ (X ∩ Z) (X ∩ Y ) ∩ (X ∪ Z)

((X ∩ Y ) ∩ X) ∪ ((X ∩ Y ) ∩ Z)

((Y ∩ X) ∩ X) ∪ ((X ∩ Y ) ∩ Z)

(Y ∩ (X ∩ X)) ∪ (X ∩ (Y ∩ Z))

(Y ∩ ∅) ∪ (X ∩ (Y ∩ Z))

∅ ∪ (X ∩ (Y ∩ Z))

(X ∩ (Y ∩ Z)) ∪ ∅

X ∩ (Y ∩ Z)

X ∩ (Y − Z)

[A − B = A ∩ B] [De Morgan’s law; Theorem 1.1.21, part (k)] [Distributive law; Theorem 1.1.21, part (c)] [Commutative law; Theorem 1.1.21, part (b)] [Associative law; Theorem 1.1.21, part (a)] [Complement law; Theorem 1.1.21, part (e)] [Bound law; Theorem 1.1.21, part (g)] [Commutative law; Theorem 1.1.21, part (b)] [Identity law; Theorem 1.1.21, part (d)] [A − B = A ∩ B]

34. False. Let X = {a} and Y = Z = {b}. Then X ∪ (Y − Z) = {a},

(X ∪ Y ) − (X ∪ Z) = ∅.

35. True. Y − X = Y ∩ X = Y ∪ X = Y ∪ X = X ∪ Y . 36. False. Let X = {a} and Y = Z = {b}. Then X − (Y ∪ Z) = {a},

(X − Y ) ∪ Z = {a, b}.

38. False. Let X = {a}, Y = {b}, and U = {a, b}. Then X − Y = {b},

Y − X = {a}.

40. True. Let x ∈ (X ∩ Y ) ∪ (Y − X). Now either x ∈ X ∩ Y or x ∈ Y − X. In either case, x ∈ Y . Therefore (X ∩ Y ) ∪ (Y − X) ⊆ Y .

Now suppose that x ∈ Y . Either x ∈ X or x ∈ / X. If x ∈ X, then x ∈ X ∩Y . Thus x ∈ (X ∩Y )∪(Y −X). If x ∈ / X, then x ∈ Y − X. Again x ∈ (X ∩ Y ) ∪ (Y − X). Thus Y ⊆ (X ∩ Y ) ∪ (Y − X). Therefore (X ∩ Y ) ∪ (Y − X) = Y .

41. True. Let a ∈ X × (Y ∪ Z). Then a = (x, y) where x ∈ X and y ∈ Y ∪ Z. Now y ∈ Y or y ∈ Z. If y ∈ Y , then a = (x, y) ∈ X × Y . Thus a ∈ (X × Y ) ∪ (X × Z). If y ∈ Z, then a = (x, y) ∈ X × Z. Again a ∈ (X × Y ) ∪ (X × Z). Therefore X × (Y ∪ Z) ⊆ (X × Y ) ∪ (X × Z). Now suppose that a ∈ (X × Y ) ∪ (X × Z). Then either a ∈ X × Y or a ∈ X × Z. If a ∈ X × Y , then a = (x, y) where x ∈ X and y ∈ Y . In particular, y ∈ Y ∪ Z. Thus a = (x, y) ∈ X ×(Y ∪ Z). If a ∈ X ×Z, then a = (x, z) where x ∈ X and z ∈ Z. In particular, z ∈ Y ∪ Z. Thus a = (x, z) ∈ X × (Y ∪ Z). Therefore (X × Y ) ∪ (X × Z) ⊆ X × (Y ∪ Z). We have proved that X × (Y ∪ Z) = (X × Y ) ∪ (X × Z).

43. True. Let a ∈ X × (Y − Z). Then a = (x, y), where x ∈ X and y ∈ Y − Z. Thus y ∈ Y and y ∈ / Z and, so, (x, y) ∈ X × Y and (x, y) ∈ / X × Z. Therefore a = (x, y) ∈ (X × Y ) − (X × Z). We have shown that X × (Y − Z) ⊆ (X × Y ) − (X × Z). Now suppose that a ∈ (X × Y ) − (X × Z). Then a ∈ X × Y and a ∈ / X × Z. Thus a = (x, y), where x ∈ X, y ∈ Y , and y ∈ / Z. Therefore a = (x, y) ∈ X × (Y − Z). We have shown that (X × Y ) − (X × Z) ⊆ X × (Y − Z). It follows that X × (Y − Z) = (X × Y ) − (X × Z). Copyright c 2018 Pearson Education, Inc.

SOLUTIONS 44. False. Take X = {1, 2}, Y = {1}, Z = {2}. Then Y × Z = {(1, 2)},

X − Y = {2},

X − Z = {1}.

Thus X − (Y × Z) = {1, 2} and (X − Y ) × (X − Z) = {(2, 1)}. 47–56. Argue as in the proof given in the book of the first associative law [Theorem 1.1.21, part (a)]. 58. By definition (A 4 B) 4 A = [(A 4 B) ∪ A] − [(A 4 B) ∩ A]. Show that (A 4 B) ∪ A = A ∪ B

and

(A 4 B) ∩ A = A ∩ B.

The statement then follows easily. 59. The statement is true. We first prove that A ⊆ B. Let x ∈ A.

We divide the proof into two cases. First, we consider the case that x ∈ C. Then x 6∈ A 4 C. Therefore x 6∈ B 4 C. Thus x ∈ B (since if x 6∈ B, then x ∈ B 4 C). Next, we consider the case that x 6∈ C. Then x ∈ A 4 C. Therefore x ∈ B 4 C. Thus x ∈ B. In either case, x ∈ B, and so A ⊆ B. Similarly, B ⊆ A, and so A = B.

61. The statement is false. Let A = {1, 2}, Since B ∩ C = {3},

B = {2, 3},

C = {1, 3}.

A 4 (B ∩ C) = {1, 2, 3}.

Now A 4 B = {1, 3} and A 4 C = {2, 3}, thus (A 4 B) ∩ (A 4 C) = {3}. 62. The statement is false. Let A = {1, 2}, Since B 4 C = {1, 2},

B = {2, 3},

C = {1, 3}.

A ∪ (B 4 C) = {1, 2}.

Since A ∪ B = A ∪ C = {1, 2, 3},

(A ∪ B) 4 (A ∪ C) = ∅.

64. Yes, 4 is commutative: A 4 B = (A ∪ B) − (A ∩ B) = (B ∪ A) − (B ∩ A) = B 4 A. 65. Yes, 4 is associative. We first prove that (A 4 B) 4 C = (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C). [For the motivation of this formula, draw the Venn diagram of (A 4 B) 4 C.] By Exercise 57, (A 4 B) 4 C = [(A 4 B) − C] ∪ [C − (A 4 B)]. Again using Exercise 57 and the fact that X − Y = X ∩ Y , we have (A 4 B) − C = [(A − B) ∪ (B − A)] − C = [(A ∩ B) ∪ (B ∩ A)] ∩ C. Copyright c 2018 Pearson Education, Inc.

(1)

SOLUTIONS Using the definition of 4, the fact that X − Y = X ∩ Y , and De Morgan’s laws, we have A 4 B = (A ∪ B) − (A ∩ B) = (A ∪ B) ∩ (A ∩ B) = (A ∪ B) ∪ (A ∩ B) = (A ∩ B) ∪ (A ∩ B). Thus C − (A 4 B) = C ∩ (A 4 B) = C ∩ [(A ∩ B) ∪ (A ∩ B)].

Combining the preceding equations and using Theorem 1.1.21, we obtain equation (1) (A 4 B) 4 C

= = =

[(A 4 B) − C] ∪ [C − (A 4 B)] {[(A ∩ B) ∪ (B ∩ A)] ∩ C} ∪ {C ∩ [(A ∩ B) ∪ (A ∩ B)]}

(A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C).

By Exercise 64, 4 is commutative. Thus A 4 (B 4 C) = (B 4 C) 4 A. We can obtain a formula for (B 4 C) 4 A using equation (1) with A replaced by B, B replaced by C, and C replaced by A. However, noting that the right-hand side of equation (1) is symmetric in A, B, and C, we see that the two expressions (A 4 B) 4 C

and A 4 (B 4 C)

are equal. Therefore, 4 is associative.

Section 2.2 2. False; x =

√ 2 is a counterexample.

3. We prove the contrapositive: If x is rational, then x3 is rational. Suppose that x is rational. Then there exist integers p and q such that x = p/q. Now x3 = p3 /q 3 . Thus x3 is rational. 5. Suppose, by way of contradiction, that x < 1 and y < 1 and z < 1. Adding these inequalities gives x + y + z < 3, which is a contradiction. √ √ 6. Suppose, by way of contradiction, that x > 2 and y > 2. Multiplying these inequalities gives xy > 2, which is a contradiction. 8. Suppose, by way of contradiction, that x + y is rational. Since x and x + y are rational, there exist integers p1 , p2 , q1, q2 such that x = p1 /q1 and x + y = p2 /q2. Now y = (x + y) − x =

p2 p1 p2 q 1 − p1 q 2 − = . q2 q1 q1 q2

Therefore y is rational, which is a contradiction. √ 9. False; a counterexample is x = 0, y = 2. √ 11. √ Since the integers increase without bound, there exists n ∈ Z such that 2/(b − a) < n. Therefore √ 2/n < b −√a. Choose m ∈ Z as large as possible satisfying m 2/n ≤ a. Then, by the choice of m, a < (m + 1) 2/n. Also √ √ √ (m + 1) 2 m 2 2 = + < a + (b − a) = b. n n n √ √ Therefore x √ = (m + 1) 2/n is an irrational number satisfying √ a < x < b. (If (m + 1) 2/n is rational, say (m + 1) 2/n = p/q where p and q are integers, then 2 = np/[(m + 1)q] is rational, which is not the case.) Copyright c 2018 Pearson Education, Inc.

SOLUTIONS

√ √2 √ 2 is rational, then we have found irrational numbers a and b (namely a = b = √ 2) such that ab is √ √ √ 2 √ 2 √ √ 2 √ √ rational. Suppose that 2 is irrational. Let a = 2 and b = 2. Now ab = ( 2 ) 2 = ( 2)2 = 2 is rational. We have found irrational numbers a and b such that ab is rational. √ This proof is nonconstructive since it does not show whether the desired pair is a = b = 2 or a = √ √ 2 √ 2 , b = 2. √ 14. Let a = 2 and b = 1/2. Then a and b are rational. Now ab = 21/2 = 2 is irrational. This proof is a constructive existence proof. 12. If

15. Suppose, by way of contradiction, that x > y. Let ε = (x − y)/2. Then y +ε = y+

x−y x+y x+x = < = x, 2 2 2

which is a contradiction. 17. First prove that if b is a rational number, then bn is rational for every positive integer n. To this end, let b = p/q, where p and q are integers. Then bn = pn /q n . Since b is the quotient of integers, b is rational. Now suppose, but way of contradiction, that ar is rational for some positive rational number r = p/q, where p and q are positive integers. Because ar is rational, (ar )q is rational by the result of the first paragraph. Since (ar )q = ap , ap is rational. This contradicts the hypothesis that an is irrational for every positive integer n. 18. We show that Abby, Cary, Dale, and Edie went to the concert, but not Bosco. Suppose that Bosco went. Then Cary and Dale also went. Since Cary went, Edie went; and since Dale went, Abby went. But this contradicts the hypothesis that exactly four went to the concert. Therefore, Bosco did not go. This means Abby, Cary, Dale, and Edie went to the concert. 20. Suppose, by way of contradiction, that X × ∅ is not empty. Then there exists (x, y) ∈ X × ∅. Now y ∈ ∅, which is a contradiction. 21. Suppose that every box contains less than 12 balls. Then each box contains at most 11 balls and the maximum number of balls contained by the nine boxes is 9 · 11 = 99. Contradiction. 23. Suppose, by way of contradiction, that each of the other three suits contains at most six cards. Then these three suits together contain at most 3 · 6 = 18 cards. Together with the other suit, which contains exactly seven cards, we can account for at most 25 cards. Since S contains 26 cards, we have a contradiction. Therefore there is another suit in which S has at least seven cards. 24. Since there is a suit in which S1 has at least nine cards, S2 has at most four cards in this suit. Now suppose, by way of contradiction, that S2 has at most seven cards in the other three suits. These three suits contain at most 3 · 7 = 21 cards. Together with at most four cards in the other suit, we can account for at most 25 cards in S2 . Since S2 contains 26 cards, we have a contradiction. Therefore there is a suit in which S2 has at least eight cards. 26. For n = 3, we have n2 > 2n . 28. The statement is false. Let s1 = s2 = 3. Then A = 3. For no i do we have si > A. The proof is by counterexample. 29. The statement is true and we prove it using proof by contradiction. Suppose that for every j, sj ≤ A. Since sj ≤ A for all j and si < A, s1 + · · · + si + · · · + sn < A + · · · + A + · · · + A = nA. Copyright c 2018 Pearson Education, Inc.

SOLUTIONS Dividing by n, we obtain

s1 + · · · + sn < A, n

which is a contradiction. 31. Since si 6= sj , either si 6= A or sj 6= A. By changing the notation, if necessary, we may assume that si 6= A. Either si < A or si > A. If si > A, the proof is complete; so assume that si < A. We show that there exists k such that sk > A. Suppose, by way of contradiction, that sm ≤ A for all m, that is, s1 s2 sn

≤ ≤ .. . ≤

A A

Adding these inequalities yields s1 + s2 + · · · + si + · · · + sn < nA since si < A. Dividing by n gives

s1 + s2 + · · · + sn < A, n which is a contradiction. Therefore there exists k such that sk > A.

33. If m and n are positive integers and m > 3, then m3 + 2n2 > 36. If m and n are positive integers and n > 4, then m3 + 2n2 > 36. Thus it suffices to consider the cases 1 ≤ m ≤ 3 and 1 ≤ n ≤ 4. The following table, which shows the values of m3 + 2n2 , shows that there is no solution to m3 + 2n2 = 36:

1 2 3 4

1 3 9 19 33

m 2 10 16 26 40

3 29 35 45 59

34. Notice that 2m2 + 4n2 − 1 is odd and 2(m + n) is even. Therefore 2m2 + 4n2 − 1 6= 2(m + n) for all positive integers m and n. 36. We consider two cases: n is even, n is odd. First suppose that n is even. By Exercise 9, Section 2.1, the product of even integers is even. Therefore n2 = n · n is even. Again by Exercise 9, Section 2.1, n3 = n2 · n is even. By Exercise 7, Section 2.1, the sum of even integers is even. Therefore n3 + n is even. Now suppose that n is odd. By Exercise 10, Section 2.1, the product of odd integers is odd. Therefore n2 = n · n is odd. Again by Exercise 10, Section 2.1, n3 = n2 · n is odd. By Exercise 8, Section 2.1, the sum of odd integers is even. Therefore n3 + n is even. In either case, n3 + n is even.

38. First, note that from Exercise 37, for all x, |−x| = |(−1)x| = |−1||x| = |x|. Example 2.2.7 states that for all x, x ≤ |x|. Using these results, we consider two cases: x + y ≥ 0 and x + y < 0. If x + y ≥ 0, we have |x + y| = x + y ≤ |x| + |y|. If x + y < 0, we have

|x + y| = −(x + y) = −x + −y ≤ |−x| + |−y| = |x| + |y|. Copyright c 2018 Pearson Education, Inc.

SOLUTIONS 40. Suppose that xy > 0. Then either x > 0 and y > 0 or x < 0 and y < 0. If x > 0 and y > 0, sgn(xy) = 1 = 1 · 1 = sgn(x)sgn(y). If x < 0 and y < 0, sgn(xy) = 1 = −1 · −1 = sgn(x)sgn(y).

Next, suppose that xy = 0. Then either x = 0 or y = 0. Thus either sgn(x) = 0 or sgn(y) = 0. In either case, sgn(x)sgn(y) = 0. Therefore sgn(xy) = 0 = sgn(x)sgn(y). Finally, suppose that xy < 0. Then either x > 0 and y < 0 or x < 0 and y > 0. If x > 0 and y < 0, sgn(xy) = −1 = 1 · −1 = sgn(x)sgn(y). If x < 0 and y > 0, sgn(xy) = −1 = −1 · 1 = sgn(x)sgn(y). 41. |xy| = sgn(xy)xy = sgn(x)sgn(y)xy = [sgn(x)x][sgn(y)y] = |x||y| 43. Suppose that x ≥ y. Then max{x, y} = x Thus max{x, y} = x =

and

|x − y| = x − y.

2x x+y+x−y x + y + |x − y| = = . 2 2 2

The other case is x < y. Then max{x, y} = y Thus max{x, y} = y =

and

|x − y| = y − x.

x+y+y−x x + y + |x − y| 2y = = . 2 2 2

44. Suppose that x ≥ y. Then min{x, y} = y Thus min{x, y} = y =

and

|x − y| = x − y.

2y x + y − (x − y) x + y − |x − y| = = . 2 2 2

The other case is x < y. Then min{x, y} = x Thus min{x, y} = x =

and

|x − y| = y − x.

2x x + y − (y − x) x + y − |x − y| = = . 2 2 2

x + y + |x − y| x + y − |x − y| + 2 2 x + y + |x − y| + x + y − |x − y| = 2 2x + 2y = = x + y. 2

45. max{x, y} + min{x, y} =

SOLUTIONS

47. Suppose that n is odd. Then n = 2k + 1. Now n + 2 = (2k + 1) + 2 = 2(k + 1) + 1 is odd. Now suppose that n + 2 is odd. Then n + 2 = 2k + 1. Now n = (2k + 1) − 2 = 2(k − 1) + 1 is odd.

Therefore n is odd if and only if n + 2 is odd.

49. Suppose that A ⊆ C and B ⊆ C. Let x ∈ A ∪ B. Then either x ∈ A or x ∈ B. If x ∈ A, since A ⊆ C, x ∈ C. If x ∈ B, since B ⊆ C, x ∈ C. In either case, x ∈ C. Therefore A ∪ B ⊆ C. Now suppose that A ∪ B ⊆ C. Let x ∈ A. Then x ∈ A ∪ B. Since A ∪ B ⊆ C, x ∈ C. Therefore A ⊆ C. Let x ∈ B. Then x ∈ A ∪ B. Since A ∪ B ⊆ C, x ∈ C. Therefore B ⊆ C. We conclude that A ⊆ C and B ⊆ C. It follows that A ⊆ C and B ⊆ C if and only if A ∪ B ⊆ C.

50. Suppose that C ⊆ A and C ⊆ B. Let x ∈ C. Since C ⊆ A, x ∈ A. Since C ⊆ B, x ∈ B. Since x ∈ A and x ∈ B, x ∈ A ∩ B. Therefore C ⊆ A ∩ B.

Now suppose that C ⊆ A ∩ B. Let x ∈ C. Then x ∈ A ∩ B. In particular, x ∈ A. Therefore C ⊆ A. Again let x ∈ C. Then x ∈ A ∩ B. In particular, x ∈ B. Therefore C ⊆ B. Thus C ⊆ A and C ⊆ B. It follows that C ⊆ A and C ⊆ B if and only if C ⊆ A ∩ B.

53. [(a) → (b)] We assume that A ∩ B = ∅ and prove that B ⊆ A. Let x ∈ B. If x ∈ A, we obtain the contradiction A ∩ B 6= ∅. Thus x ∈ / A. Hence x ∈ A. Therefore B ⊆ A. [(b) → (c)] We assume that B ⊆ A and prove that A 4 B = A ∪ B.

Let x ∈ A 4 B. By definition, A 4 B = (A ∪ B) − (A ∩ B), thus x ∈ A ∪ B. Therefore A 4 B ⊆ A ∪ B.

Let x ∈ A ∪ B. We first prove that x ∈ / A ∩ B. Suppose, by way of contradiction, that x ∈ A ∩ B. Then x ∈ A and x ∈ B. Since B ⊆ A, x ∈ A, which implies that x ∈ / A. We have the desired contradiction. Therefore x ∈ / A ∩ B. Now x ∈ (A ∪ B) − (A ∩ B) = A 4 B. Therefore A ∪ B ⊆ A 4 B. It follows that A 4 B = A ∪ B.

[(c) → (a)] We assume that A 4 B = A ∪ B and prove that A ∩ B = ∅. Suppose, by way of contradiction, that A ∩ B is not empty. Then there exists x ∈ A ∩ B. Then x ∈ A ∪ B. This implies that x ∈ / A 4 B. Since x ∈ A ∪ B, A 4 B 6= A ∪ B, which is a contradiction. Therefore A ∩ B = ∅. 54. [(a) → (b)] We assume that A ∪ B = U and prove that A ∩ B = ∅. Taking the complement of both sides of the equation A ∪ B = U and using De Morgan’s law and the 0/1 law (Theorem 1.1.22), we obtain A ∩ B = A ∪ B = U = ∅. [(b) → (c)] We assume that A ∩ B = ∅ and prove that A ⊆ B. Replace A by B and B by A in Exercise 53(a) to obtain B ∩ A = ∅. Since Exercise 53(a) is equivalent to Exercise 53(b), we obtain A ⊆ B or A ⊆ B.

[(c) → (a)] We assume that A ⊆ B and prove that A∪B = U . Since U is a universal set, we automatically have A ∪ B ⊆ U . Let x ∈ U . If x ∈ A, then x ∈ A ∪ B. If x ∈ / A, then x ∈ A. Since A ⊆ B, x ∈ B. Again x ∈ A ∪ B. Therefore U ⊆ A ∪ B. It follows that A ∪ B = U .

Problem-Solving Corner: Proofs 1. The least upper bound of a nonempty finite set of real numbers is the maximum number in the set. 2. Call the given set X. We prove that the least upper bound of X is 1. Since 1−

1 <1 n