Test Bank For Discrete Mathematics With Applications, 5th Edition

Discrete Mathematics with Applications, 5th Edition by Susanna S. Epp Test Bank Questions Chapter 1 1. Fill in the blanks to rewrite the following statement with variables: Is there an integer with a remainder of 1 when it is divided by 4 and a remainder of 3 when it is divided by 7? (a) Is there an integer n such that n has (b) Does there exist ? such that if n is divided by 4 the remainder is 1 and if ? 2. Fill in the blanks to rewrite the following statement with variables: Given any positive real number, there is a positive real number that is smaller. (a) Given any positive real number r, there is (b) For any , s such that s is . such that s < r. 3. Rewrite the following statement less formally, without using variables: There is an integer n such that 1/n is also an integer. 4. Fill in the blanks to rewrite the following statement: For all objects T , if T is a triangle then T has three sides. . (a) All triangles (b) Every triangle . . (c) If an object is a triangle, then it (d) If T , then T . (e) For all triangles T , . 5. Fill in the blanks to rewrite the following statement: Every real number has an additive inverse. (a) All real numbers . (b) For any real number x, there is for x. (c) For all real numbers x, there is real number y such that . 6. Fill in the blanks to rewrite the following statement: There is a positive integer that is less than or equal to every positive integer. (a) There is a positive integer m such that m is (b) There is a such that . every positive integer. (c) There is a positive integer m which satisfies the property that given any positive integer n, m is . 7. (a) Write in words how to read the following out loud {n ∈ Z | n is a factor of 9}. (b) Use the set-roster notation to indicate the elements in the set. 8. (a) Is {5} ∈ {1, 3, 5}? (b) Is {5} ⊆ {1, 3, 5}? (c) Is {5} ∈ {{1}, {3}, {5}}? (d) Is {5} ⊆ {{1}, {3}, {5}}? 9. Let A = {a, b, c} and B = {u, v}. Write a. A × B and b. B × A. 10. Let A = {3, 5, 7} and B = {15, 16, 17, 18}, and define a relation R from A to B as follows: For all (x, y) ∈ A × B, y (x, y) ∈ R ⇔ is an integer. x (a) Is 3 R 15? Is 3 R 16? Is (7, 17) ∈ R? Is (3, 18) ∈ R? (b) Write R as a set of ordered pairs. (c) Write the domain and co-domain of R. (d) Draw an arrow diagram for R. (e) Is R a function from A to B? Explain. 11. Define a relation R from R to R as follows: For all (x, y) ∈ R × R, (x, y) ∈ R if, and only if, x = y 2 + 1. (a) Is (2, 5) ∈ R? Is (5, 2) ∈ R? Is (−3) R 10? Is 10 R (−3)? (b) Draw the graph of R in the Cartesian plane. (c) Is R a function from R to R? Explain. 12. Let A = {1, 2, 3, 4} and B = {a, b, c}. Define a function G: A → B as follows: G = {(1, b), (2, c), (3, b), (4, c)}. (a) Find G(2). (b) Draw an arrow diagram for G. 13. Define functions F and G from R to R by the following formulas: F (x) = (x + 1)(x − 3) and G(x) = (x − 2)2 − 7. Does F = G? Explain. Chapter 2 1. Which of the following is a negation for “Jim is inside and Jan is at the pool.” (a) Jim is inside or Jan is not at the pool. (b) Jim is inside or Jan is at the pool. (c) Jim is not inside or Jan is at the pool. (d) Jim is not inside and Jan is not at the pool. (e) Jim is not inside or Jan is not at the pool. 2 2. Which of the following is a negation for “Jim has grown or Joan has shrunk.” (a) Jim has grown or Joan has shrunk. (b) Jim has grown or Joan has not shrunk. (c) Jim has not grown or Joan has not shrunk. (d) Jim has grown and Joan has shrunk. (e) Jim has not grown and Joan has not shrunk. (f) Jim has grown and Joan has not shrunk. 3. Write a negation for each of the following statements: (a) The variable S is undeclared and the data are out of order. (b) The variable S is undeclared or the data are out of order. (c) If Al was with Bob on the first, then Al is innocent. (d) −5 ≤ x x or x ≥ 2 4. The statement forms are not logically equivalent. Truth table: p T T F F q T F T F ∼p F F T T p∨q T T T F ∼p∧ q F F T F p∨q →p T T F T p ∨ (∼ p ∧ q) T T T F Explanation: The truth table shows that p ∨ q → p and p ∨ (∼ p ∧ q) have different truth values in rows 3 and 4, i.e, when p is false. Therefore p ∨ q → p and p ∨ (∼ p ∧ q) are not logically equivalent. 5. Sample answers: Two statement forms are logically equivalent if, and only if, they always have the same truth values. Or: Two statement forms are logically equivalent if, and only if, no matter what statements are substituted in a consistent way for their statement variables the resulting statements have the same truth value. 6. Solution 1: The given statements are not logically equivalent. Let p be “Sam bought it at Crown Books,” and q be “Sam didn’t pay full price.” Then the two statements have the following form: p → q and p∨ ∼ q. The truth tables for these statement forms are p T T F F q T F T F ∼q F T F T p→q T F T T 2 p∨ ∼ q T T F T Rows 2 and 3 of the table show that p → q and p∨ ∼ q do not always have the same truth values, and so p → q ̸≡ p∨ ∼ q. Solution 2 : The given statements are not logically equivalent. Let p be “Sam bought it at Crown Books,” and q be “Sam paid full price.” Then the two statements have the following form: p →∼ q and p ∨ q. The truth tables for these statement forms are p T T F F q T F T F ∼q F T F T p →∼ q F T T T p∨q T T T F Rows 1 and 4 of the table show that p →∼ q and p ∨ q do not always have the same truth values, and so p →∼ q ̸≡ p ∨ q. 7. The given statements are not logically equivalent. Let p be “Sam is out of Schlitz,” and q be “Sam is out of beer.” Then the two statements have the following form: p → q and ∼ q∨ ∼ p. The truth tables for these statement forms are p T T F F q T F T F ∼p F F T T ∼q F T F T p→q T F T T ∼ p∨ ∼ q F T T T The table shows that p → q and ∼ p ∨ ∼ q sometimes have opposite truth values (shown in rows 1 and 2), and so p → q ̸≡ ∼ p ∨ ∼ q. 8. Converse: If Jose is Jan’s cousin, then Ann is Jan’s mother Inverse: If Ann is not Jan’s mother, then Jose is not Jan’s cousin. Contrapositive: If Jose is not Jan’s cousin, then Ann is not Jan’s mother. 9. Converse: If Liu is Sue’s cousin, then Ed is Sue’s father. Inverse: If Ed is not Sue’s father, then Liu is not Sue’s cousin Contrapositive: If Liu is not Sue’s cousin, then Ed is not Sue’s father. 10. Converse: If Jim is Tom’s grandfather, then then Al is Tom’s cousin. Inverse: If Al is not Tom’s cousin, then Jim is not Tom’s grandfather Contrapositive: If Jim is not Tom’s grandfather, then then Al is not Tom’s cousin. 11. If someone does not get an answer of 10 for problem 16, then the person will not have solved problem 16 correctly. Or: If someone solves problem 16 correctly, then the person got an answer of 10. 12. Sample answers: For a form of argument to be valid means that no matter what statements are substituted for its statement variables, if the resulting premises are all true, then the conclusion is also true. Or: For a form of argument to be valid means that no matter what statements are substituted for its statement variables, it is impossible for all the premises to be true at the same time that the conclusion is false. Or: For a form of argument to be valid means that no matter what statements are substituted for its statement variables, it is impossible for conclusion to be false if all the premises are true. 3 13. The given form of argument is invalid. premises z p T T F F q T F T F ∼p F F T T ∼q F T F T }| p →∼ q F T T T { q →∼ p F T T T conclusion z }| { p∨q T T T F Row 4 of the truth table shows that it is possible for an argument of this form to have true premises and a false conclusion. 14. The given form of argument is invalid. premises z 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 ∼q F F T T F F T T p∧∼q F F T T F F F F }| p∧∼q→r T T T F T T T T { p∨q T T T T T T F F q→p T T T T F F T T conclusion z }|{ r T F T F T F T F Row 2 of the truth table shows that it is possible for an argument of this form to have true premises and a false conclusion. 15. Let p be “Hugo is a physics major,” q be “Hugo is a math major,” and r be “Hugo needs to take calculus.” Then the given argument has the following form: Therefore Truth table: premises z 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 F F T T T T F F p∨q →r r∨q p ∨ q. }| p∨q →r T F T F T F T T r∨q T T T F T T T F { conclusion z }|{ p∨q T T T T T T F F Row 7 of the truth table shows that it is possible for an argument of this form to have true premises and a false conclusion. Therefore, the given argument is invalid. 16. Let p be “12 divides 709,438,” q be “3 divides 709,438,” and r be “The sum of the digits of 709,438 is divisible by 9.” Then the given argument has the following form: Therefore 4 p→q r→q ∼r ∼ p. 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 ∼q F F T T F F T T p∧∼q F F T T F F F F z premises p→q T T F F T T T T r→q T T F T T T F T }| { ∼r F T F T F T F T conclusion z }|{ ∼p F F F F T T T T Row 2 of the truth table shows that it is possible for an argument of this form to have true premises and a false conclusion. Therefore, the given argument is invalid. 17. The argument has the form Therefore p→q ∼q ∼ p, which is valid by modus tollens (and the fact that the negation of “17 is not a divisor of 54,587” is “17 is a divisor of 54,587”). 18. The argument has the form Therefore p→q q p, which is invalid; it exhibits the converse error. 19. A and B are knights, and C is a knave. Reasoning: A cannot be a knave because if A were a knave his statement would be true, which is impossible for a knave. Hence A is a knight, and at least one of the three is a knave. That implies that at most two of the three are knaves, which means that B’s statement is true. Hence B is a knight. Since at least one of the three is a knave and both A and B are knights, it follows that C is a knave. 20. a. S = 1 b. ∼ (P ∧ Q)∧ (Q ∧ R) 21. 1101012 = 1 · 25 + 1 · 24 + 1 · 22 + 1 · 20 = 32 + 16 + 4 + 1 = 5310 22. 7510 = 64 + 8 + 2 + 1 = 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20 = 10010112 . 23. The following circuit corresponds to the given Boolean expression: P Q AND OR NOT AND NOT 5 R 24. One circuit (among many) having the given input/output table is the following: P Q NOT OR AND S R NOT AND 25. + 101112 10112 1000102 26. 1001102 = 1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20 = 32 + 4 + 2 = 3810 27. 4910 = (32 + 16 + 1)10 = 001100012 −→ 11001110 −→ 11001111. So the two’s complement is 11001111. Check: 28 − 49 = 256 − 49 = 207 and 110011112 = = = 1 · 27 + 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 1 · 21 + 1 · 20 128 + 64 + 8 + 4 + 2 + 1 207, which agrees. Chapter 3 1. ∀ valid argument x, if x has true premises, then x has a true conclusion. 2. a. ∀ odd integer n, n2 is odd. b. ∀ integer n, if n is odd then n2 is odd. c. ∃ an odd integer n such that n2 is not odd. Or: ∃ an integer n such that n is odd and n2 is not odd. 3. ∀ rational number r, ∃ integers u and v such that r is the ratio of u to v. Or: ∀ rational number r, ∃ integers u and v such that r = u/v. 4. ∀ even integer n that is greater than 2, ∃ prime numbers p and q such that n = p + q. Or: ∀ even integer n, if n > 2 then ∃ prime numbers p and q such that n = p + q. 5. e 6. a 7. d 8. g 6