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.

12. Consider the statement For all sets A and B, (A − B) ∩ B = ∅. The proof below is the beginning of a proof using the element method for proving that the set equals the empty set. Complete the proof without using any of the set properties from Theorem 6.2.2. Proof: Suppose the given statement is false. Then there exist sets A and B such that (A − B) ∩ B ̸= ∅. Thus there is an element x in (A − B) ∩ B. By deﬁnition of intersection,. . . . 13. Consider the statement For all sets A and B, (A − B) ∩ B = ∅. Complete the proof begun below in which the given statement is derived algebraically from the properties listed in Theorem 6.2.2. Be sure to give a reason for every step that exactly justiﬁes what was done in the step: Proof: Let A and B be any sets. Then the left-hand side of the equation to be shown is (A − B) ∩ B

= (A ∩ B c ) ∩ B

by the

law

by the

law

by the

law

by the

law

by the

law

which is the right-hand side of the equation to be shown. [Hence the given statement is true.] (The number of lines in the outline shown above works for one version of a proof. If you write a proof using more or fewer lines, be sure to follow the given format, supplying a reason for every step that exactly justiﬁes what was done in the step.) 14. (a) Prove the following statement using the element method for proving that a set equals the empty set: For all sets A and B, A ∩ (B − A) = ∅. (b) Use the properties in Theorem 6.2.2 to prove the statement in part (a). Be sure to give a reason for every step. 15. Derive the following result “algebraically” using the properties listed in Theorem 6.2.2. Give a reason for every step that exactly justiﬁes what was done in the step. For all sets A, B, and C, (A ∪ C) − B = (A − B) ∪ (C − B). 16. Derive the following result. You may do so either “algebraically” using the properties listed in Theorem 6.2.2, being sure to give a reason for every step, or you may use the element method for proving a set equals the empty set. For all sets B and C, (B − C) − B = ∅. 17. Use the element method for proving a set equals the empty set to prove that For all sets A and C, (A − C) ∩ (C − A) = ∅. 17

18. Prove that for all sets A and B1 , B2 , . . . Bn , A−

n ∩

Bi =

i=1

n ∪

(A − Bi ).

i=1

19. Is the following sentence a statement: This sentence is false or −22 = 4. Justify your answer.

Chapter 7 1. Let X = {a, b, c} and Y = {u, v}. Which of the following arrow diagrams deﬁne functions from X to Y ?

. b. c. a

. b. c.

.u .v .w

2. Fill in the blanks: log3 ( 19 ) =

. b. c.

.u .v .w

because

.u .v .w

3. Is log2 5 = log16 625? Why or why not? 4. Let J5 = {0, 1, 2, 3, 4} and define a function g: J5 × J5 → J5 × J5 as follows: For all (a, b) ∈ J5 × J5 , g(a, b) = ((5a − 3) mod 5, (4b + 2) mod 5). Find g(3, 4). 5. Let X = {1, 2, 3, 4, 5} and Y = {u, v, w, x, y}, and define h: X → Y as follows: h(1) = v, h(2) = x, h(3) = v, h(4) = v, h(5) = y. (a) Draw an arrow diagram for h. (b) Let A = {1, 2}, C = {x, v}, D = {w}, and E = {w, y}. Find h(A), h(X), h−1 (C), h−1 (D), h−1 (E), and h−1 (Y ). 6. Let f be a function from a set X to a set Y. Define precisely (but concisely) what it means for f to be one-to-one. 7. Let f be a function from a set X to a set Y. Define precisely (but concisely) what it means for f to be onto. 8. Let A = B = {1, 2, 3}, and consider the function f : A → B defined as follows: f (1) = 3, f (2) = 1, f (3) = 3. Is f onto? Why or why not? 9. (a) Draw an arrow diagram for a function that is onto but not one-to-one. (b) Draw an arrow diagram for a function that is one-to-one but not onto. 10. Define a function f : R−{0} −→ R by the formula f (x) = x. Prove that f is one-to-one. 18

x+3 for all nonzero real numbers x

24. A screening test for a certain disease is used in a large population of people of whom 1 in 1000 actually have the disease. Suppose that the false positive rate is 1% and the false negative rate is 0.5%. Thus a person who has the disease tests positive for it 99.5% of the time, and a person who does not have the disease tests negative for it 99% of the time. (a) What is the probability that a randomly chosen person who tests positive for the disease actually has the disease? (b) What is the probability that a randomly chosen person who tests negative for the disease actually has the disease? 25. A coin is loaded so that the probability of heads is 0.55 and the probability of tails is 0.45. Suppose the coin is tossed twice and the results of the tosses are independent. (a) What is the probability of obtaining exactly two heads? (b) What is the probability of obtaining exactly one head? (c) What is the probability of obtaining no heads? (d) What is the probability of obtaining at least one head?

Chapter 10 1. If a graph has vertices of degrees 1, 1, 2, 3, and 3, how many edges does it have? Why? 2. For each of (a)–(c) below, either draw a graph with the speciﬁed properties or else explain why no such graph exists. (a) Graph with six vertices of degrees 1, 1, 2, 2, 2, and 3. (b) Graph with four vertices of degrees 1, 2, 2, and 5. (c) Simple graph with four vertices of degrees 1, 1, 1, and 5. 3. Determine whether each of the following graphs has an Euler circuit. If it does have an Euler circuit, ﬁnd such a circuit. If it does not have an Euler circuit, explain why you can be 100% sure that it does not. c

d e

4. Determine whether each of the following graphs has a Hamiltonian circuit. If it does have an Hamiltonian circuit, ﬁnd such a circuit. If it does not have an Hamiltonian circuit, explain why you can be 100% sure that it does not. c

d e

G1 25

5. Draw a directed graph with the following adjacency matrix: v  1 v1 1 v2  0 v3  2 v4 0

v2 2 0 2 1

v3 0 0 1 0

v4  0 1  0 0

3 4

0 2

6. Find the following matrix product: 

 2 0 [  0 1  1 2 3 2

]

7. Consider the adjacency matrix for a graph that is shown below. Answer the following questions by examining the matrix and its powers only, not by drawing the graph. Show your work in a way that makes your reasoning clear. v  1 v1 0 v2  1 v3  0 v4 1

v2 1 0 2 0

v3 0 2 0 0

v4  1 0  0 0

(a) How many walks of length 2 are there from v1 to v2 ? (b) How many walks of length 2 are there from v1 to v3 ? (c) How many walks of length 2 are there from v2 to v2 ?

8. Determine whether any two of G1 , G2 , and G3 are isomorphic. If they are, give vertex and edge functions that deﬁne the isomorphism. If they are not, give an isomorphic invariant that they do not share.

u2 e1

f1 u3

g3 g2 w 2

G3 26

12. Explain why the following statement is true. (You may use the theorem on polynomial orders.) 3 + 6 + 9 + · · · + 3n is O(n2 ). 13. (a) Find the total number of additions and multiplications that must be performed when the following algorithm is executed. Show your work carefully. for i := 1 to n for j = i to n a := 2 · (5 · i + j + 1) next j next i (b) Find an order for the algorithm segment of part (a) from among the following: log2 n, n, n · log2 n, n2 , n3 , and n4 . Give a reason for your answer. 14. (a) Consider the following algorithm segment: for i := 1 to n for j := 1 to i x := 5 · i + 8 · j next j next i How many additions and multiplications are performed when the inner loop of this algorithm segment is executed? How many additions and multiplications are performed when the entire algorithm segment is executed? (b) Find an order for this algorithm segment from among the following: log2 n, n, n · log2 n, n2 , n3 , and n4 . Give a reason for your answer. 15. Describe the operation of the sequential search algorithm. 16. Describe the operation of the insertion sort algorithm. 17. Sketch the graph of y = log3 x. 18. Deﬁne a function F : R+ −→ R by the formula F (x) = log2 (x) for all positive real numbers x. (a) Graph F, marking units carefully on your axes. (b) What is F ( 81 )? Why? (c) Write the equation 220 = 1, 048, 576 in logarithmic form. 19. If n and k are positive integers and 2k ≤ n < 2k+1 , what is ⌊log2 (n)⌋? Be sure to justify each step of your answer. 20. Use O-notation to express the following statement: | 5x + x log2 x |≤ 6 | x log2 x | for all x > 2. 21. Describe the operation of the binary search algorithm. 22. Describe the operation of the merge sort algorithm. 29

Chapter 12 1. Let Σ = {0, 1}, and let L be the language over Σ consisting of all strings of 0’s and 1’s of length 4 with an equal number of 0’s and 1’s. List the elements of L. 2. Let L be the language defined by the regular expression 0(0 | 1)∗ 1(0 | 1)∗ . (a) Write 3 strings that belong to L (b) Use words to describe L. 3. Let L be the language defined by the regular expression (x | y)∗ x(x | y). (a) Write 3 strings that belong to L (b) Use words to describe L. 4. Consider the language that consists of all strings of a’s and b’s in which the second character from the beginning is a b. Find a regular expression that defines this language. 5. Consider the language that consists of all strings of 0’s and 1’s in which the number of 1’s is evenly divisible by 4. Find a regular expression that defines this language. 6. Consider the finite-state automaton given by the following transition diagram: a s2 a a

s0 b

(a) What is N (s2 , a)? (b) To what state does the automaton go if the string babaa is input to it? (c) Indicate which of the following strings are accepted by the automaton: abab

bbab

abbbaa

(d) Describe the language accepted by this automaton. (e) Find a regular expression that deﬁnes the same language. 7. Consider the ﬁnite-state automaton given by the following transition diagram: 0 s0

0,1

(a) To what state does the automaton go if the string 10010010 is input to it? Is this string accepted by the automaton? (b) Indicate which of the following strings are accepted by the automaton: 000101

0100010 30

000100

110001