Skip to content
Textbook Guides

Solution Manual For Discrete Mathematics With Applications, 5th Edition

Solution Manual For Discrete Mathematics With Applications, 5th Edition gives you all the tools you need to solve your textbook problems effectively.

Preview 16 of 732 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    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. x 2 = − 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 : 3 √ s is negative) c. is negative; 3 √ s is negative ( Or : the cube root of s is negative)

  2. Page 2
  3. Page 3
    Read page 3 as text

    2 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 n 2 ≥ 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 Section 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.

  4. Page 4
    Read page 4 as text

    Manual Section 1.2 3 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. T 2 and T − 3 each have two elements, and T 0 and T 1 each have one element. Justification : T 2 = { 2 , 2 2 } = { 2 , 4 } , T − 3 = {− 3 , ( − 3) 2 } = {− 3 , 9 } , T 1 = { 1 , 1 2 } = { 1 , 1 } = { 1 } , and T 0 = { 0 , 0 2 } = { 0 , 0 } = { 0 } . 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 − 2 2 = − (2 2 ) = − 4. So (( − 2) 2 , − 2 2 ) = (4 , − 4), whereas ( − 2 2 , ( − 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

  5. Page 5
    Read page 5 as text

    4 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 2 , 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. R 6 8 10 2 3 4 2. a. 2 S 2 because 1 2 − 1 2 = 0, which is an integer. − 1 S − 1 because 1 − 1 − 1 − 1 = 0, which is an integer. 3 S 3 because 1 3 − 1 3 = 0, which is an integer. 3 / S − 3 because 1 3 − 1 − 3 = 2 3 , which is not an integer.

  6. Page 6
    Read page 6 as text

    Manual Section 1.3 5 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 –3 –2 –1 1 2 3 –3 –2 –1 1 2 3 C D 3. a. 3 T 0 because 3 − 0 3 = 3 3 = 1, which is an integer. 1 ̸ T ( − 1) because 1 − ( − 1) 3 = 2 3 , which is not an integer. (2 , − 1) ∈ T because 2 − ( − 1) 3 = 3 3 = 1, which is an integer. (3 , − 2) / ∈ T because 3 − ( − 2) 3 = 5 3 , which is not an integer. 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 –2 –1 0 1 2 3 4. a. 2 V 6 because 2 − 6 4 = − 4 4 = − 1, which is an integer. 1 ̸ V ( − 1) because ( − 2) − 8 4 = − 6 4 , which is not an integer. ( − 2) ̸ V 8 because ( − 2) − 8 4 = − 6 4 , which is not an integer. 0 ̸ V 6 because 0 − 6 4 = − 6 4 , which is not an integer. 2 ̸ V 4 because 2 − 4 4 = − 2 4 , 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 –2 0 2 4 6 8 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.

  7. Page 7
    Read page 7 as text

    6 Manual: Chapter 1 b. x 1 x $ y in shaded region graph of S 6. a. (2 , 4) ∈ R because 4 = 2 2 . (4 , 2) / ∈ R because 2 ̸ = 4 2 . ( − 3 , 9) ∈ R because 9 = ( − 3) 2 . (9 , − 3) / ∈ R because − 3 ̸ = 9 2 . b. 1 2 3 4 5 6 -6 -5 -4 -3 -2 -1 6 5 4 3 2 1 -1 -2 7 8 9 y y = x 2 x 7. a. R 5 6 7 4 5 6 A B 4 5 6 5 6 7 S T A B 4 5 6 5 6 7 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.

  8. Page 8
    Read page 8 as text

    Manual Section 1.3 7 8. a. U 2 4 1 3 5 A B V 1 3 5 A B W 1 3 5 A B 2 4 2 4 b. None of U , V , or W are functions. U is not a function because (4 , y ) is not in U for any y in B , and so U does not satisfy property (1) of the definition of function. V is not a function because (2 , y ) is not in V for any y in B , and so V does not satisfy property (1) of the definition of function. W is not a function because both (2 , 3) and (2 , 5) are in W and 3 ̸ = 5, and so W does not satisfy property (2) of the definition of function. 9. a. There is only one: { (0 , 1) , (1 , 1) } b. { (0 , 1) } , { (1 , 1) } 10. The following sets are relations from { a, b } to { x, y } that are not functions: { ( a, x ) } , { ( a, y ) } , { ( b, x ) } , { ( b, y ) } , { ( a, x ) , ( a, y ) } , { ( b, x ) , ( b, y ) } , { ( a, x ) , ( a, y ) , ( b, x ) } , { ( a, x ) , ( a, y ) , ( b, y ) } , { ( b, x ) , ( b, y ) , ( a, x ) } , { ( b, x ) , ( b, y ) , ( a, y ) } , { ( a, x ) , ( a, y ) , ( b, x ) , ( b, y ) } . 11. L (0201) = 4 , L (12) = 2 12. C ( x ) = yx, C ( yyxyx ) = yyyxyx 13. a. Domain = A = {− 1 , 0 , 1 } , co-domain = B = { t, u, v, w } b. F ( − 1) = u, F (0) = w, F (1) = u 14. a. Domain of G = { 1 , 2 , 3 , 4 } , co-domain of G = { a, b, c, d } b. G (1) = G (2) = G (3) = G (4) = c 15. a. This diagram does not determine a function because 2 is related to both 2 and 6. b. This diagram does not determine a function because 5 is in the domain but it is not related to any element in the co-domain. c. This diagram does not determine a function because 4 is related to both 1 and 2, which violates property (2) of the definition of function. d. This diagram defines a function; both properties (1) and (2) are satisfied. e. This diagram does not determine a function because 2 is in the domain but it is not related to any element in the co-domain. 16. f ( − 1) = ( − 1) 2 = 1 , f (0) = 0 2 = 0 , f ( 1 2 ) = ( 1 2 ) 2 = 1 4 . 17. g ( − 1000) = − 999, g (0) = 1, g (999) = 1000 18. h ( − 12 5 ) = h ( 0 1 ) = h ( 9 17 ) = 2 19. For each x ∈ R , g ( x ) = 2 x 3 + 2 x x 2 + 1 = 2 x ( x 2 + 1) x 2 + 1 = 2 x = f ( x ) . Therefore, by definition of equality of functions, f = g .

  9. Page 9
    Read page 9 as text

    8 Manual: Chapter 1 20. For all x ∈ R , K ( x ) = ( x − 1)( x − 3) + 1 = ( x 2 − 4 x + 3) + 1 = x 2 + 4 x + 4 = ( x − 2) 2 = H ( x ). Therefore, by definition of equality of functions, H = K . Section 1.4 1. V ( G ) = { v 1 , v 2 , v 3 , v 4 } , E ( G ) = { e 1 , e 2 , e 3 } Edge-endpoint function: Edge Endpoints e 1 { v 1 , v 2 } e 2 { v 1 , v 3 } e 3 { v 3 } 2. V ( G ) = { v 1 , v 2 , v 3 , v 4 } , E ( G ) = { e 1 , e 2 , e 3 , e 4 , e 5 } Edge-endpoint function: Edge Endpoints e 1 { v 1 , v 2 } e 2 { v 2 , v 3 } e 3 { v 2 , v 3 } e 4 { v 2 , v 4 } e 5 { v 4 } 3. 1 e 1 e 2 2 4 5 3 e 3 e 4 4. 1 v 4 v 3 v 2 v 1 v 5 e e e e 4 2 3 5. Imagine that the edges are strings and the vertices are knots. You can pick up the left-hand figure and lay it down again to form the right-hand figure as shown below. 5 2 6 1 3 4 e 6 e 5 e 7 e 4 e 3 e 2 e 1

  10. Page 10
    Read page 10 as text

    Manual Section 1.4 9 6. v 4 v 3 v 2 v 1 e 3 e 4 e 2 1 e 7. or 1 2 3 4 5 6 7 8 9 v 4 v 3 v 2 v 1 v 5 v 6 v 7 e e e e e e e e e 1 2 3 4 5 6 7 8 9 v 4 v 3 v 2 v 1 v 5 v 6 v 7 e e e e e e e e e 8. (i) e 1 , e 2 , e 7 are incident on v 1 . (ii) v 1 , v 2 , and v 3 are adjacent to v 3 . (iii) e 2 , e 8 , e 9 , and e 3 are adjacent to e 1 . (iv) Loops are e 6 and e 7 . (v) e 8 and e 9 are parallel; e 4 and e 5 are parallel. (vi) v 6 is an isolated vertex. (vii) degree of v 3 = 5 9. (i) e 1 , e 2 , e 7 are incident on v 1 . (ii) v 1 and v 2 are adjacent to v 3 . (iii) e 2 and e 7 are adjacent to e 1 . (iv) e 1 and e 3 are loops. (v) e 4 and e 5 are parallel. (vi) v 4 is an isolated vertex. (vii) degree of v 3 = 2 10. a. Yes. According to the graph, Sports Illustrated is an instance of a sports magazine, a sports magazine is a periodical, and a periodical contains printed writing. b. Yes. According to the graph, Poetry Magazine is an instance of a Literary journal which is a Scholarly journal and, therefore, contains Long words. 11. ( vvccB/ ) → ( vc/Bvc ) → ( vvcB/c ) → ( c/Bvvc ) → ( vcB/vc ) → ( /Bvvcc ) ( vvccB/ ) → ( vv/Bcc ) → ( vvcB/c ) → ( c/Bvvc ) → ( vcB/vc ) → ( /Bvvcc ) ( vvccB/ ) → ( vv/Bcc ) → ( vvcB/c ) → ( c/Bvvc ) → ( ccB/vv ) → ( /Bvvcc )

  11. Page 11
    Read page 11 as text

    10 Manual: Chapter 1 12. To solve this puzzle using a graph, introduce a notation in which, for example, wc / fg means that the wolf and the cabbage are on the left bank of the river and the ferryman and the goat are on the right bank. Then draw those arrangements of wolf, cabbage, goat, and ferryman that can be reached from the initial arrangement ( wgcf /) and that are not arrangements to be avoided (such as ( wg / fc )). At each stage ask yourself, “Where can I go from here?” and draw lines or arrows pointing to those arrangements. This method gives the graph shown below. Examining the diagram reveals the solutions ( wgcf /) → ( wc / gf ) → ( wcf / g ) → ( w / gcf ) → ( wgf / c ) → ( g / wcf ) → ( gf / wc ) → (/ wgcf ) and ( wgcf /) → ( wc / gf ) → ( wcf / g ) → ( c / wgf ) → ( gcf / w ) → ( g / wcf ) → ( gf / wc ) → (/ wgcf ) 13. vvvcccB/ vvvc/Bcc vvcc/Bvc vvvcc/Bc vvvccB/c vvv/Bccc vvvcB/cc vc/Bvvcc vvccB/vc cccB/vvv c/Bvvvcc vcB/vvcc /Bvvvccc ccB/vvvc ccB/vvvc The diagram shows several solutions. Among them is ( vvvcccB/ ) → ( vvcc/Bvc ) → ( vvvccB/c ) → ( vvv/Bccc ) → ( vvvcB/cc ) → ( vc/Bvvcc ) → ( vvccB/vc ) → ( cc/Bvvvc ) → ( cccB/vvv ) → ( c/Bvvvcc ) → ( vcB/vvcc ) → ( /Bvvvccc ), or one can end with ( c/Bvvvcc ) → ( ccB/vvvc ) → ( /Bvvvccc ), or one can start with ( vvvcccB/ ) → ( vvvc/Bcc ) → ( vvvccB/c ) . 14. Represent possible amounts of water in jugs A and B by ordered pairs with, say, the ordered pair (1,3) indicating that there is one quart of water in jug A and three quarts in jug B . Starting with (0,0), draw an edge from one ordered pair to another if it is possible to go from the situation represented by the one pair to that represented by the other and back by either

  12. Page 12
    Read page 12 as text

    Manual Section 1.4 11 filling a jug from the tap, emptying a jug into the drain, or transferring water from one jug to another. Except for (0,0), only draw edges from states that have edges incident on them (since these are the only states that can be reached). The resulting graph is shown as follows: (0,3) (1,3) (2,3) (3,3) (0,2) (1,2) (2,2) (3,2) (0,1) (1,1) (2,1) (3,1) (0,0) (1,0) (2,0) (3,0) (0,5) (1,5) (2,5) (3,5) (0,4) (1,4) (2,4) (3,4) It is clear from the graph that one solution is (0 , 0) → (3 , 0) → (0 , 3) → (3 , 3) → (1 , 5) → (1 , 0) and another solution is (0 , 0) → (0 , 5) → (3 , 2) → (0 , 2) → (2 , 0) → (2 , 5) → (3 , 4) → (0 , 4) → (3 , 1) → (0 , 1) . Note that it would be possible to add arrows to the above graph from each reachable state to each other state that could be obtained from it either by filling one of the jugs to the top or by emptying the entire contents of one of the jugs. For instance, one could draw an arrow from (0,3) to (0,5) or from (0,3) to (0,0). Because the graph is connected, all such arrows would point to states already reachable by other means, so that it is not necessary to add such additional arrows to find solutions to the problem (and it makes the diagram look more complicated). However, if the problem were to find all possible solutions, the arrows would have to be added. 15. b c e d g f a 1 3 2 3 2 3 1 Vertex e has maximal degree, so color it with color #1. Vertex a does not share an edge with e , and so color #1 may also be used for it. From the remaining uncolored vertices, all of d, g , and f have maximal degree. Choose any one of them—say, d —and use color #2 for it. Observe that vertices c and f do not share an edge with d , but they do share an edge with each other, which means that color #2 may be used for one but not the other. Choose to color f with color #2 because the degree of f is greater than the degree of c . The remaining uncolored vertices, b, c, and g , are unconnected, and so color #3 may be used for all three.

  13. Page 13
    Read page 13 as text

    12 Manual: Chapter 1 16. Represent each committee name by a vertex, labeled with the first letter of the name of the committee, and join vertices if, and only if, the corresponding committees have a member in common. Figure (a) shows one way to color the graphs. Vertex H has maximum degree, so use color #1 for it. Vertex L does not share an edge with H , and so color #1 may also be used for it. From the remaining uncolored vertices, each of P , U , and G is adjacent to three other vertices. Choose any one of them, say P , and use color #2 for it. Vertices U and C do not share an edge with P or with each other, and so color #2 may also be used for them. Color #3 can then be used for the remaining vertex, G , at which point all vertices will be colored. Note that the same result is obtained if U is chosen instead of P in step 2. However, if G is chosen instead of P in step 2, the result is the coloring indicated in Figure (b). U G H P L C 2 2 1 1 3 2 (b) (a) U G H P L C 3 3 1 1 2 2 To use the results of Figure (a) to schedule the meetings, let color n correspond to meeting time n . Then Time 1: hiring, library Time 2: personnel, undergraduate education, colloquium Time 3: graduate education Using the results of Figure (b) to schedule the meetings produces this result: Time 1: hiring, library Time 2: graduate education, colloquium Time 3: personnel, undergraduate education 17. In the following graph each course number is represented as a vertex. Vertices are joined if, and only if, the corresponding courses have a student in common. 110 120 130 135 100 1 2 4 2 4 3 3 102 101 Vertex 135 has maximum degree, so use color #1 for it. All vertices share edges with vertex 135, and so color #1 cannot be used on any other vertex. From the remaining uncolored vertices, only vertex 120 has maximum degree. So use color #2 for it. Because vertex 100 does not share an edge with vertex 120, color #2 may also be used for it. From the remaining uncolored vertices, all of 101, 102, 110, and 130 have maximum degree. Choose any one of them, say vertex 101, and use color #3 for it. Neither vertex 102 nor

  14. Page 14
    Read page 14 as text

    Manual Section 1.4 13 vertex 110 shares an edge with vertex 101, but they do share an edge with each other. So color #3 may be used for only one of them. If color #3 is used for vertex 110, then, since the remaining vertices 130 and 102 are connected, two additional colors would be needed for them to have different colors. On the other hand, if color #3 is used for vertex 102, then, since the remaining vertices, 110 and 130, are not connected to each other, color 4 may be used for both. Therefore, to minimize the number of colors, color #3 should be used for vertex 102 and color #4 for vertices 110 and 130. The result is indicated in the annotations on the graph. To use the results for scheduling exams, let color n correspond to exam time n . Then Time 1: MCS135 Time 2: MCS 100 and MCS120 Time 3: MCS101 and MCS102 Time 4: MCS110 and MCS130 Note that because, for example, MSC135, MSC102, MSC110, and MSC 120 are all connected to each other, they must all be given different colors, and so the schedule for the seven exams must use at least four time periods.

  15. Page 15
    Read page 15 as text

    Manual: Chapter 2 1 Chapter 2: The Logic of Compound Statements The ability to reason using the principles of logic is essential for solving problems in abstract math- ematics and computer science and for understanding the reasoning used in mathematical proof and disproof. Because a significant number of students who come to college have had limited opportu- nity to develop this ability, a primary aim of Chapters 2 and 3 is to help students develop an inner voice that speaks with logical precision. Consequently, the various rules used in logical reasoning are developed both symbolically and in the context of their somewhat limited but very important use in everyday language. Exercise sets for Sections 2.1–2.3 and 3.1–3.4 contain sentences for students to negate, write the contrapositive for, and so forth. Virtually all students benefit from doing these exercises. Another aim of Chapters 2 and 3 is to teach students the rudiments of symbolic logic as a foundation for a variety of upper-division courses. Symbolic logic is used in, among others, the study of digital logic circuits, relational databases, artificial intelligence, and program verification. Suggestions 1. In Section 2.1 a surprising number of students apply De Morgan’s law to write the negation of, for example, “1 < x ≤ 3” as “1 ≥ x > 3.” You may find that it takes some effort to teach them to avoid making this mistake. 2. In Sections 2.1 and 2.4, students have more difficulty than you might expect simplifying statement forms and circuits. Only through trial and error can you learn the extent to which this is the case at your institution. If it is, you might either assign only the easier exercises or build in extra time to teach students how to do the more complicated ones. Discussion of simplification techniques occurs again in Chapter 6 in the context of set theory. At this later point in the course most students are able to deal with it successfully. 3. In ordinary English, the phrase “only if” is often used as a synonym for “if and only if.” But it is possible to find informal sentences for which the intuitive interpretation is the same as the logical definition. It is helpful to give examples of such statements when you introduce the logical definition. For instance, it is not hard to get students to agree that “The team will win the championship only if it wins the semifinal game” means the same as “If the team does not win the semifinal game then it will not win the championship.” Once students see this, you can suggest that they remember this example when they encounter more abstract “only if”statements. Through guided discussion, students also come to agree that the statement “Winning the semi- final game is a necessary condition for winning the championship” translates to “If the team does not win the semifinal game then it will not win the championship.” They can be encouraged to use this (or a similar statement) as a reference to help develop intuition for general statements of the form “ A is a necessary condition for B .” With students who have weaker backgrounds, you may find yourself tying up excessive amounts of class time discussing “only if” and “necessary and sufficient conditions.” You might just assign the easier exercises, or you might assign exercises on these topics to be done for extra credit (putting corresponding extra credit problems on exams) and use the results to help distinguish A from B students. It is probably best not to omit these topics altogether, though, because the language of “only if” and “necessary and sufficient conditions” is a standard part of the technical vocabulary of textbooks used in upper-division courses, as well as occurring regularly in non-mathematical writing. 4. In Section 2.3, many students mistakenly conclude that an argument is valid if, when they compute the truth table, they find a single row in which both the premises and the conclusion are true. The source of students’ difficulty appears to be their tendency to ignore quantification and to misinterpret if-then statements as “and” statements. Since the definition of validity includes both a universal quantifier and if-then, it is helpful to go back over the definition and the procedures for testing for validity and invalidity after discussing the general topic of universal conditional statements

  16. Page 16
    Read page 16 as text

    2 Solutions for Exercises: The Logic of Compound Statements in Section 3.1. As a practical measure to help students assess validity and invalidity correctly, the first example in Section 2.3 is of an invalid argument whose truth table has eight rows, several of which have true premises and a true conclusion. To further focus students’ attention on the situations where all the premises are true, the truth values for the conclusions of arguments are omitted when at least one premise is false. 5. In Section 2.3, you might suggest that students just familiarize themselves with, but not memorize, the various forms of valid arguments covered in Section 2.3. It is wise, however, to have them learn the terms modus ponens and modus tollens (because these are used in some upper-division computer science courses) and converse and inverse errors (because these errors are so common). Section 2.1 1. Common form: If p then q . p Therefore, q ( a + 2 b )( a 2 − b ) can be written in prefix notation. All algebraic expressions can be written in prefix notation. 2. Common form: If p then q . ∼ q Therefore, ∼ p All prime numbers are odd. 2 is odd 3. Common form: p ∨ q ∼ p Therefore, q My mind is shot. Logic is confusing. 4. Common form: If p then q . If q then r . Therefore, If p then r . Has 4 vertices and 6 edges. Is complete; Any two of its vertices can be joined by a path 5. a. It is a statement because it is a true sentence. 1,024 is a perfect square because 1 , 024 = 32 2 , and the next smaller perfect square is 31 2 = 961, which has fewer than four digits. b. The truth or falsity of this sentence depends on the reference for the pronoun “she.” Considered on its own, the sentence cannot be said to be either true or false, and so it is not a statement. c. This sentence is false; hence it is a statement. d. This is not a statement because its truth or falsity depends on the value of x. 6. a. s ∧ i b . ∼ s ∧ ∼ i 7. m ∧ ∼ c 8. a. ( h ∧ w ) ∧ ∼ s b. ∼ w ∧ ( h ∧ s ) c. ∼ w ∧ ∼ h ∧ ∼ s d. ( ∼ w ∧ ∼ s ) ∧ h e. w ∧ ∼ ( h ∧ s ) ( w ∧ ( ∼ h ∨ ∼ s ) is also acceptable) 9. a. p ∨ q b. r ∧ p c. r ∧ ( p ∨ q ) 10. a. p ∧ q ∧ r b . p ∧ ∼ q c. p ∧ ( ∼ q ∨ ∼ r ) d. ( ∼ p ∧ q ) ∧ ∼ r e. ∼ p ∨ ( q ∧ r )

716 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.