Issuu

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

. .

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

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 satisﬁes 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. 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 ﬁrst, then Al is innocent. (d) −5 ≤ x < 2 (where x is a particular real number) 4. Are the following statement forms logically equivalent: p ∨ q → p and p ∨ (∼ p ∧ q)? Include a truth table and a few words explaining how the truth table supports your answer. 5. State precisely (but concisely) what it means for two statement forms to be logically equivalent. 6. Write the following two statements in symbolic form and determine whether they are logically equivalent. Include a truth table and a few words explaining how the truth table supports your answer. If Sam bought it at Crown Books, then Sam didn’t pay full price. Sam bought it at Crown Books or Sam paid full price. 7. Write the following two statements in symbolic form and determine whether they are logically equivalent. Include a truth table and a few words explaining how the truth table supports your answer. If Sam is out of Schlitz, then Sam is out of beer. Sam is not out of beer or Sam is not out of Schlitz. 8. Write the converse, inverse, and contrapositive of “If Ann is Jan’s mother, then Jose is Jan’s cousin.” 9. Write the converse, inverse, and contrapositive of “If Ed is Sue’s father, then Liu is Sue’s cousin.” 10. Write the converse, inverse, and contrapositive of “If Al is Tom’s cousin, then Jim is Tom’s grandfather.” 11. Rewrite the following statement in if-then form without using the word “necessary”: Getting an answer of 10 for problem 16 is a necessary condition for solving problem 16 correctly. 12. State precisely (but concisely) what it means for a form of argument to be valid. 3

13. Consider the argument form:

p →∼ q q →∼ p ∴ p∨q Use the truth table below to determine whether this form of argument is valid or invalid. Annotate the table (as appropriate) and include a few words explaining how the truth table supports your answer. p T T F F

∼p F F T T

q T F T F

∼q F T F T

p →∼ q F T T T

q →∼ p F T T T

p∨q T T T F

14. Consider the argument form:

Therefore

p∧∼q→r p∨q q→p r.

Use the truth table below to determine whether this argument form is valid or invalid. Annotate the table (as appropriate) and include a few words explaining how the truth table supports your answer. 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

r T F T F T F T F

15. Determine whether the following argument is valid or invalid. Include a truth table and a few words explaining why the truth table shows validity or invalidity. If Hugo is a physics major or if Hugo is a math major, then he needs to take calculus. Hugo needs to take calculus or Hugo is a math major. Therefore, Hugo is a physics major or Hugo is a math major. 16. Determine whether the following argument is valid or invalid. Include a truth table and a few words explaining why the truth table shows validity or invalidity. If 12 divides 709,438 then 3 divides 709,438. If the sum of the digits of 709,438 is divisible by 9 then 3 divides 709,438. The sum of the digits of 709,438 is not divisible by 9. Therefore, 12 does not divide 709,438. 17. Write the form of the following argument. Is the argument valid or invalid? Justify your answer. If 54,587 is a prime number, then 17 is not a divisor of 54,587. 17 is a divisor of 54,587. Therefore, 54,587 is not a prime number. 4

18. Write the form of the following argument. Is the argument valid or invalid? Justify your answer. If Ann has the ﬂu, then Ann has a fever. Ann has a fever. Therefore, Ann has the ﬂu. 19. On the island of knights and knaves, you meet three natives, A, B, and C, who address you as follows: A: At least one of us is a knave. B: At most two of us are knaves. What are A, B, and C? 20. Consider the following circuit. AND

NOT

AND

(a) Find the output of the circuit corresponding to the input P = 1, Q = 0, and R = 1. (b) Write the Boolean expression corresponding to the circuit. 21. Write 1101012 in decimal form. 22. Write 75 in binary notation. 23. Draw the circuit that corresponds to the following Boolean expression: (P ∧ Q) ∨ (∼ P ∧ ∼ Q).(Note for students who have studied some circuit design: Do not simplify the circuit; just draw the one that exactly corresponds to the expression.) 24. Find a circuit with the following input/output table. P 1 1 1 1 0 0 0 0

Q 1 1 0 0 1 1 0 0

R 1 0 1 0 1 0 1 0

S 0 0 1 0 1 0 0 0

25. Find 101112 + 10112 . 26. Write 1001102 in decimal form. 27. Write the 8-bit two’s complement for 49.

Chapter 3 1. Rewrite the following statement in the form ∀ x, if the second two blanks are sentences involving the variable x)

then

(where each of

Every valid argument with true premises has a true conclusion. 2. Consider the statement “The square of any odd integer is odd.” (a) Rewrite the statement in the form ∀ “then.”)

. (Do not use the words “if” or

(b) Rewrite the statement in the form ∀ n, if then the variable n when you ﬁll in each of the second two blanks.)

. (Make sure you use

(c) Write a negation for the statement. 3. Rewrite the following statement formally. Use variables and include both quantiﬁers ∀ and ∃ in your answer. Every rational number can be written as a ratio of some two integers. 4. Rewrite the following statement formally. Use variables and include both quantiﬁers ∀ and ∃ in your answer. Every even integer greater than 2 can be written as a sum of two prime numbers. 5. Which of the following is a negation for “Given any real numbers a and b, if a and b are rational then a/b is rational.” (a) There exist real numbers a and b such that a and b are not rational and a/b is not rational. (b) Given any real numbers a and b, if a and b are not rational then a/b is not rational. (c) There exist real numbers a and b such that a and b are not rational and a/b is rational. (d) Given any real numbers a and b, if a and b are rational then a/b is not rational. (e) There exist real numbers a and b such that a and b are rational and a/b is not rational. (f) Given any real numbers a and b, if a and b are not rational then a/b is rational. 6. Which of the following is a negation for “For all real numbers r, there exists a number s such that rs > 10.” (a) There exists a real number r such that for all real numbers s, rs ̸> 10. (b) For all real numbers r, there does not exist a number s such that rs > 10. (c) There exists real numbers r and s such that rs ̸> 10. (d) For all real numbers r and s, rs ̸> 10. (e) There exists a real number r and there does not exist a real number s such that rs ̸> 10. (f) For all real numbers r, there exists a number s such that rs ̸> 10. (g) There exists a real number r such that there does not exist a real number s with rs ̸= 10. 6

7. Which of the following is a negation for “There exists a real number x such that for all real numbers y, xy > y.” (a) There exists a real number x such that for all real numbers y, xy ≤ y. (b) There exists a real number y such that for all real numbers x, xy ≤ y. (c) There exist real numbers x and y such that xy ≤ y. (d) For all real numbers x there exists a real number y such that xy ≤ y. (e) For all real numbers y there exists a real number x such that xy ≤ y. (f) For all real numbers x and y, xy ≤ y. 8. Which of the following is a negation for “For any integer n, if n is composite, then n is even or n > 2.” (a) For any integer n, if n is composite, then n is not even or n ≤ 2. (b) For any integer n, if n is not composite, then n is not even or n ≤ 2. (c) For any integer n, if n is not composite, then n is not even and n ≤ 2. (d) For any integer n, if n is not composite, then n is even and n ≤ 2. (e) For any integer n, if n is not composite, then n is not even and n ≤ 2. (f) There exists an integer n such that if n is composite, then n is not even and n ≤ 2. (g) There exists an integer n such that n is composite and n is not even and n ≤ 2. (h) There exists an integer n such that if n is not composite, then n is not even and n ≤ 2. (i) There exists an integer n such that n is composite and n is even and n ≤ 2. (j) There exists an integer n such that if n is not composite, then n is not even or n ≤ 2. 9. Write negations for each of the following statements: (a) For all integers n, if n is prime then n is odd. 1 (b) ∀ real numbers x, if x < 1 then > 1. x (c) For all integers a and b, if a2 divides b2 then a divides b. (d) ∀ real numbers x, if x(x − 2) > 0 then x > 2 or x < 0. (e) ∀ real numbers x, if x(x − 2) ≤ 0 then 0 ≤ x ≤ 2. (f) For all real numbers x and y with x < y, there exists an integer n such that x ≤ n ≤ y. 10. Let T be the statement ∀ real numbers x, if − 1 < x ≤ 0 then x + 1 > 0. (a) Write the converse of T. (b) Write the contrapositive of T. 11. Rewrite the following statement in if-then form without using the word “only”: A graph with n vertices is a tree only if it has n − 1 edges. 12. Are the following two statements logically equivalent? Justify your answer. (a) A real number is less than 1 only if its reciprocal is greater than 1. (b) Having a reciprocal greater than 1 is a suﬃcient condition for a real number to be less than 1. 7

13. For each of the following statements, (1) write the statement informally without using variables or the symbols ∀ or ∃, and (2) indicate whether the statement is true or false and brieﬂy justify your answer. (a) ∀ integers a, ∃ an integer b such that a + b = 0. (b) ∃ an integer a such that ∀ integers b, a + b = 0. 14. For each of the following statements, (1) write the statement informally without using variables or the symbols ∀ or ∃, and (2) indicate whether the statement is true or false and brieﬂy justify your answer. (a) ∀ real numbers x, ∃ a real number y such that x < y. (b) ∃ a real number y such that ∀ real numbers x, x < y. 15. Is the following argument valid or invalid? Justify your answer.

Therefore,

All real numbers have nonnegative squares. The number i has a negative square. the number i is not a real number.

16. Is the following argument valid or invalid? Justify your answer.

Therefore,

All prime numbers greater than 2 are odd. The number a is not prime. the number a is not odd.

Chapter 4 1. State precisely (but concisely) what it means for an integer n to be odd. 2. Find a counterexample to show that the following statement is false: For all nonzero real numbers a, b, c and d,

a c a+c + = . b d b+d

3. Consider the following statement: Statement A: ∀ integers m and n, if 2m + n is odd then m and n are both odd. (a) Write a negation for Statement A. (b) Disprove Statement A. That is, show that Statement A is false. 4. If m and n are integers, is 6m2 + 34n − 18 an even integer? Justify your answer. 5. Show that the following statement is false: The product of any two irrational numbers is irrational. 6. State precisely (but concisely) what it means for a number r to be rational. 7. Is 605.83 a rational number? Justify your answer. 8. Is 56.745 a rational number? Justify your answer. 9. State precisely (but concisely) what it means for an integer n to be divisible by an integer d. 8

10. Is 0 divisible by 3? Justify your answer. 11. Does 12 divide 72? Justify your answer. 12. Outline a proof of the following statement by writing the “starting point” and the “conclusion to be shown” in a proof of the statement. ∀ real numbers r and s, if r and s are rational then r − s is rational. That is, complete the sentences below. Proof: Suppose We must show that

. .

13. Prove the following statement directly from the deﬁnitions of the terms. Do not use any other facts previously proved in class or in the text or in the exercises. For all rational numbers r, and s, if s ̸= 0, then

2r is a rational number. 5s

14. Prove the following statement directly from the definitions of the terms. Do not use any other facts previously proved in class or in the text or in the exercises. For all integers a, b, and c, if a | b and a | c, then a | (5b + 3c). 15. Prove the following statement directly from the definition of divisibility. Do not use any other facts previously proved in class or in the text or in the exercises.For all integers a, and b, if a divides b then a3 divides b3 . 16. Prove the statement below directly from the definitions of the terms. Do not use any other facts previously proved in class or in the text or in the exercises. For all integers n, n2 + n + 1 is odd. 17. Prove the following statement: The sum of any two consecutive integers can be written in the form 4n + 1 for some integer n. 18. Prove the following statement: For all real numbers x, ⌊x − 2⌋ = ⌊x⌋ − 2. 19. Prove the following statement: There is no smallest positive rational number. 20. Prove the following statement by contradiction: For all real numbers r and s, if r is rational and s is irrational, then r + 2s is irrational. 21. Consider the following statement: For all integers n, if n3 is even then n is even. (a) Prove the statement either by contradiction or by contraposition. Clearly indicate which method you are using. (b) If you used proof by contradiction in part (a), write what you would “suppose” and what you would “show” to prove the statement by contraposition. If you used proof by contraposition. in part (a), write what you would “suppose” and what you would “show” to prove the statement by contradiction. 9

22. Consider the following statement: For all real numbers r, if r3 is irrational then r is irrational. (a) Prove the statement either by contradiction or by contraposition. Clearly indicate which method you are using. (b) If you used proof by contradiction in part (a), write what you would “suppose” and what you would “show” to prove the statement by contraposition. If you used proof by contraposition in part (a), write what you would “suppose” and what you would “show” to prove the statement by contradiction. 23. Consider the following statement: For all integers n, if n3 is odd then n is odd. (a) Prove the statement either by contradiction or by contraposition. Clearly indicate which method you are using. (b) If you used proof by contradiction in part (a), write what you would “suppose” and what you would “show” to prove the statement by contraposition. If you used proof by contraposition in part (a), write what you would “suppose” and what you would “show” to prove the statement by contradiction. 24. True or false? For any irrational number r, r2 is irrational. Justify your answer. √ 25. Fill in the blanks of the following proof by contradiction that 7 + 4 2 is an irrational number. √ (You may use the fact that 2 is irrational.) √ √ Proof: Suppose not. That is, suppose that 7 + 4 2 is (i) . By deﬁnition of rational, 7 + 4 2 = a , where (ii) . Multiplying both sides by b gives b √ 7b + 4b 2 = a, so if we subtract 7b from both sides we have √ 4b 2 = (iii) . Dividing both sides by 4b gives

√ 2 = (iv) .

√ But then 2 would be a rational number because (v) . This contradicts our knowledge that √ 2 is irrational. Hence (vi) . √ √ 26. Prove by contradiction that 4 + 3 2 is an irrational number. (You may use the fact that 2 is irrational.) 27. Use the Euclidean algorithm to ﬁnd the greatest common divisor of 284 and 168. Show your work. 28. Use the Euclidean algorithm to calculate the greatest common divisor of 10,673 and 11,284. Show your work.

Chapter 5 1. Compute 2. Compute

∑3 k=0

∑4

1 . 2k

2 k=1 k .

3. Use summation notation to rewrite the following: 13 − 23 + 33 − 43 + 53 . 4. Use a summation symbol to rewrite the following: 1 − 10

1 1 1 1 1 + − + − 2 3 4 5 6