《離散數(shù)學(xué)及其應(yīng)用_英文版第6版_課后答案(美_Kennenth HRosen 著) 機(jī)械工業(yè)出版社》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)及其應(yīng)用_英文版第6版_課后答案(美_Kennenth HRosen 著) 機(jī)械工業(yè)出版社（39頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 P.16 1.1 4. f) If I did not buy a lottery ticket this week, then I?did not win?the million dollar jackpot on Friday. g) I did not buy a lottery ticket this week, and I did not win the million dollar jackpot on Friday. h ) Either I did not buy a lottery ticket this week, or else I did buy on

2、e and won the million dollar jackpot on Friday. ? 10. a) r ∧ ┐q b) p ∧ q∧ r c) r → p d) p ∧ ┐q ∧ r e) (p ∧ q) → r f) r? ( q ∨ p) 20. a) If I am to remember to send you the address, then you will have to send me an e-mail message.(This has been slightly reworded so that the tenses make

3、more sense.) b) If you were born in the United States, then you are a citizen of this country. c) If you keep your textbook, then it will be a useful reference in your future courses.(The word "then" is understood in English, even if omitted.) d) If their goaltender plays well, then the Red Wings

4、 will win the Stanley Cup. e) If you get the job, then you had the best credentials. f) If there is a storm, then the beach erodes. g) If you log on to the server, then you have a valid password. h) If you don’t begin your climb too late, then you will reach the summit. 33. c) p q r (p

5、→q) ∨(┐p →r?) T T T T T T F T T F T T T F F T F T T T F T F T F F T T F F F T P.26 1.2 8. a) Kwame will not take a job in industry and he will not go to graduate school. b) Yoshiko doesn’t know Java or she doesn’t know calculus. c) James is not young or he

6、is not strong. d) Rita will not move to Oregon and she will not move to Washington. 10. a) p q ┐p p∨q ┐p∧(p∨q) [┐p∧(p∨q)]→q T T F T F T T F F T F T F T T T T T F F T F F T c) p q p →q p∧(p →q) [p∧(p →q)] →q T T T T T T F F F T F T T F T F

7、F T F T 12. a) Assume the hypothesis is true. Then p is false. Since p∨q is true, we conclude that q must be true. Here is a more "algebraic" solution: ??????[┐p ∧ (p ∨ q)]→q <=> ┐[┐p∧(p ∨ q)]∨q <=> ┐┐p∨┐(p ∨ q)∨q <=> p∨┐(p ∨ q)∨q <=> (p ∨ q)∨┐(p ∨ q) <=> T c) Assume the hypothesis is tru

8、e. Then p is true, and since the second part of the hypothesis is ture, we conclude that q is also true, as desired. 24. p q r p → q p→ r (p → q) ∨(p→ r) q∨ r p →(q ∨ r) T T T T T T T T T T F T F T T T T F T F T T T T T F F F F F F F F T T T T T T T

9、 F T F T T T T T F F T T T T T T F F F T T T F T 30. p q r p ∨ q ┐p∨ r q ∨ r (p ∨ q)∧(┐p∨ r) (p ∨ q)∧(┐p∨ r) →(q ∨ r) T T T T T T T T T T F T F T F T T F T T T T T T T F F T F F F T F T T T T T T T F T F T T T T T F

10、 F T F T T F T F F F F T F F T 51. ((p ↓ p) ↓ q )↓((p ↓ p) ↓ q ) 9.7 7. The graph is planar. a d e c f b 20. The graph is not homeomorphic to K3,3, since by rerouting the edge between a and h we see that it is planar.

11、 22. Replace each vertex of degree two and its incident edges by a single edge. Then the result is K3,3 : the parts are {a,e,i} and {c,g,k}. Therefore this graph is homeomorphic to K3,3. 23. The graph is planar. 25. The graph is not planar. 9.8 3. 3 A F

12、 B C E D 8. 3 9. 2 10. 4 17. time slot 1: Math 115, Math 185; time slot 2: Math 116, CS 473; time slot 3: Math 195, CS 101; time slot 4: CS 102 time slot 5: CS 273 P.46 1.3 3. a) true b) false c) false d) false 5. a) There is a student who spen

13、ds more than 5 hours every weekday in class. b) Every student spends more than 5 hours every weekday in class. c) There is a student who does not spend more than 5 hours every weekday in class. d) No student spends more than 5 hours every weekday in class. 9. a) x(P(x)∧Q(x)) b) x(P(x)∧﹁Q(x))

14、 c) x(P(x)∨Q(x)) d) x﹁(P(x)∨Q(x)) 16. a) true b) false c) true d) false 24. Let C(x) be the propositional function “x is in your class.” a) x P(x) and x(C(x) →P(x)), where P(x) is “x has a cellular phone.” b) x F(x) and x(C(x)∧F(x)), where F(x) is “x has seen a foreign movie.” c) x ﹁S(x)

15、 and x(C(x)∧﹁S(x)), where S(x) is “x can swim.” d) x E(x) and x(C(x) →E(x)), where E(x) is “x can solve quadratic equations.” e) x ﹁R(x) and x(C(x)∧﹁R(x)), where R(x) is “x wants to be rich.” 62. a) x (P(x)→﹁S(x)) b) x(R(x)→S(x)) c) x (Q(x)→P(x)) d) x(Q(x)→﹁R(x)) e) Yes. If x is one of

16、my poultry, then he is a duck (by part(c)), hence not willing to waltz (part (a)). Since officers are always willing to waltz (part (b)), x is not an officer. P.59 1.4 12. d) x ┐C(x, Bob) h) x y (I(x) ∧((x ≠ y) →┐ I(y))) k) x y( I(x) ∧┐C(x, y)) n) x y z ((x ≠ y) ∧┐ (C(x, z) ∧ C(y, z)))

17、 14. a) x H(x), where H(x) is “x can speak Hindi” and the universe of the discourse consists of all students in this class. b) x y P(x, y), where P(x, y) is “x plays y.” and the universe of the discourse for x consists of all students in this class, and the universe of the discourse for y consis

18、ts of all sports. c) x A(x) ∧┐H(x) , where A(x) is “x has visited Alaska.” , H(x) is “x has visited Hawaii” and the universe of the discourse for x consists of all students in this class. d) x y L(x, y), where L(x, y) is “x has learned programming language y” and the universe of the discourse for

19、x consists of all students in this class, and the universe of the discourse for y consists of all programming languages. e) x z y (Q(y, z) → P(x, y)), where P(x, y) is“ x has taken course y.”, Q(y, z) is “course y is offered by department z.”, and the universe of the discourse for x consists of all

20、 students in this class, the universe of the discourse for y consists of all courses in this school, and the universe of the discourse for z consists of all departments in this school. f) x y z ( (x ≠ y) ∧ P(x, y)∧ ((x ≠ y ≠ z) → ┐P(x, z))), where P(x, y) is “ x and y grew up in the same town.” an

21、d the universe of the discourse for x, y, z consists of all students in this class. g) x y z C(x, y) ∧ G(y, z), where C(x, y) is “x has chatted with y”, G(y, z) is “y is in chat group z”, the universe of the discourse for x, y consists of all students in this class, and the universe of the discours

22、e for z consists of all chat group in this class. 24. a) There is an additive identity for the real numbers. d) The product of two nonzero numbers is nonzero for the real numbers. 38. b) There are no students in this class who have never seen a computer. d) There are no students in th

23、is class who have taken been in at least one room of every building on campus. 1.5 (1) (┐r∧(q→p))→(p→(q∨r)) <=> ┐(┐r∧(┐q∨p))∨(┐p∨(q∨r)) <=> (q∧┐p)∨(┐p∨q∨r) <=> (┐p∨q∨r∨q)∧(┐p∨q∨r∨┐p) <=> (┐p∨q∨r) <=> ∏3 <=> ∑0,1,2,4,5,6,7 (2) P.72 6. Let r be the proposition "It rains", let f be the propositi

24、on "It is foggy", let s be the proposition "The sailing race will be held", let l be the proposition "The lifesaving demonstration will go on", and let t be the proposition "The trophy will be awarded". We are given premises (┐r∨┐f)→(s∧l), s→t, and ┐t. We want to conclude r. We set up the proof in t

25、wo columns, with reasons. Note that it is valid to replace subexpressions by other expressions logically equivalent to them. ?Step????????????????????????????????Reason ????? 1.?? ┐t???????????????????????????????Hypothesis ????? 2.?? s→t???????????????????????????????Hypothesis ????? 3.?? ┐s???

26、????????????????????Modus tollens using Steps 1 and 2 ????? 4.?? (┐r∨┐f)→(s∧l)????????????????????? Hypothesis ????? 5.???(┐(s∧l))→┐(┐r∨┐f)?????????? Contrapositive of step 4 ????? 6.???(┐s∨┐l)→(r∧f)??????De Morgan's law and double negative ????? 7.???┐s∨┐l???????????????????????????Addition, us

27、ing Step 3 ????? 8.?? r∧f??????????????????????? Modus ponens using Step 6 and 7 ????? 9.?? r???????????????????????????? Simplification using Step 8 12. First, using the conclusion of Exercise 11, we should show that?the argument form with premises (p ∧ t) → (r ∨s),?q→ (u ∧ t), u→ p, ┐s, q, and

28、 conclusion r is valid. Then, we use rules of inference from Table 1. ?Step??????????????????????????? ????? Reason ????? 1.?? q???????????????????????????? Premise ????? 2.?? q→ (u ∧ t)????????????????????????????? Premise ????? 3.?? u ∧ t???????????????????? Modus ponens using Steps 1 an

29、d 2 ????? 4.?? u???????????????????? Simplification using Step 3 ????? 5.???u→ p????????? Premise ????? 6.???p ????? Modus ponens using Steps 3 and 4 ????? 7.???t?????????????????????????? Simplification using Step 3 ????? 8.?? p ∧ t?????????????????????? Conjunction using S

30、teps 6 and 7 ????? 9.?? (p ∧ t) → (r ∨s)????????????????????Premise ????? 10.???r ∨s????????? Modus ponens using Steps 8 and 9 ????? 11.???┐s ????? Premise ????? 12.???r????????????????????????? Disjunctive syllogism using Steps 10 and 11 14． b) Let R(x) be “x is one of the fi

31、ve roommates,” D(x) be “x has taken a course in discrete mathematics,” and A(x) be “x can take a course in algorithms.” The premises are x (R(x) → D(x)), x (D(x) → A(x)) and R(Melissa). Using the first premise and Universal Instantiation, R(Melissa) → D(Melissa) follows. Using the third premise and

32、Modus Ponens, D(Melissa) follows. Using the second premise and Universal Instantiation, A(Melissa) follows. So do the other roommates. d) Let C(x) be “x is in the class,” F(x) be “x has been to France,” and L(x) be “x has visited Louvre.” The premises are x(C(x) ∧F(x)) and x (F(x) → L(x)). From the

33、 first premise and Existential Instantiation imply that C(y) ∧F(y) for a particular person y. Using Simplification, F(y) follows. Using the second premise and Universal Instantiation F(y) → L(y) follows. Using Modus Ponens, L(y) follows. Using Existential Generalization, x(C(x) ∧L(x)) follows. 24

34、. The errors occur in steps (3), (5) and (7).For steps (3) and (5), we cannot assume, as is being done here, that the c that makes P(x) true is the same as the c that makes Q(x) true at the same time. For step (7), it is not a conjunction and there is no such disjunction rule. 29. ?Step???????

35、?????????????????????????Reason ????? 1.??x ┐P(x)?????????????????????????????Premise ????? 2.?? ┐P(c)?????????????????????????????? Existential instantiation from (1) ????? 3.?? x (P(x) ∨Q(x))???????????????Premise ????? 4.?? P(c) ∨Q(c)??????????????????? Universal instantiation from (3) ?????

36、 5.?? Q(c)??????????? Disjunctive syllogism from (2) and (4) ????? 6.???x (┐Q(x) ∨S(x))???????? Premise ????? 7.???┐Q (c) ∨S(c)??????????????????? Universal instantiation from (6) ????? 8.?? S(c)??????????? Disjunctive syllogism from (5) and (7) ????? 9.?? x (R(x) →?┐S(x))????????????Pre

37、mise??? ????? 10.??R(c) →?┐S(c)??????????? Universal instantiation from (9)??? ????? 11.??┐R(c)???????????? Modus tollens from (8) and (10) ????? 12.??x ┐R(x)?????????? Existential generalization from (11) P.86 1.6 37. Suppose that P1→P4→P2→P5→P3→P1. To prove that one of these proposition

38、s implies any of the others, just use hypothetical syllogism repeatedly. P.103 1.7 13. a) This statement asserts the existence of x with a certain property. If we let y=x, then we see that P(x) is true. If y is anything other than x, then P(x) is not true. Thus, x is the unique element that

39、makes P true. b) The first clause here says that there is an element that makes P true. The second clause says that whenever two elements both make P true, they are in fact the same element. Together these say that P is satisfied by exactly one element. c) This statement asserts the existence of a

40、n x that makes P true and has the further property that whenever we find an element that makes P true, that element is x. In other words, x is the unique element that makes P true. P.120 2.1 9.? T?? T?? F?? T?? T? F 16. Since the empty set is a subset of every set, we just need to take a set B

41、 that contains Φ as an element. Thus we can let A = Φ and B = {Φ} as the simplest example. 20 .The union of the sets in the power set of a set X must be exactly X. In other words, we can recover X from its power set, uniquely. Therefore the answer is yes. 22. a) The power set of every set include

42、s at least the empty set, so the power set cannot be empty. Thus?Φ is not the power set of any set. b) This is the power set of {a} c) This set has three elements. Since 3 is not a power of 2, this set cannot be the power set of any set. d) This is the power set of {a,b}. 28. a) {(a,x,0), (a,x,

43、1), (a,y,0), (a,y,1), (b,x,0), (b,x,1), (b,y,0), (b,y,1), (c,x,0), (c,x,1), (c,y,0), (c,y,1)} c) {(0,a,x), (0,a,y), (0,b,x), (0,b,y), (0,c,x), (0,c,y), (1,a,x), (1,a,y), (1,b,x), (1,b,y), (1,c,x), (1,c,y)} P.130 2.2 14. Since A = (A - B)∪(A∩B), we conclude that A = {1,5,7,8}∪{3,6,9} = {1,3,5,6

44、,7,8,9}. Similarly B = (B - A)∪(A ∩ B) = {2,10}∪{3,6,9} = {2,3,6,9,10}. 24. First suppose x is in the left-hand side. Then x must be in A but in neither B nor C. Thus x∈A - C, but xB - C, so x is in the right-hand side. Next suppose that x is in the right-hand side. Thus x must be in A - C and not

45、in B - C. The first of these implies that x∈A and xC. But now it must also be the case that xB, since otherwise we would have x∈B - C. Thus we have shown that x is in A but in neither B nor C, which implies that x is in the left-hand side. 40. This is an identity; each side consists of those things

46、 that are in an odd number of the sets A,B,and C. P147. 2.3 35 a) This really has two parts. First suppose that b is in f(S∪T). Thus b=f(a) for some a∈S∪T. Either a ∈S, in which case b∈f(S), or a∈T, in which case b∈f(T). Thus in either case b∈ f(S) ∪f(T). This shows that f(S∪T) f(S) ∪f(T), Con

47、versely, suppose b∈f(S) ∪f(T). Then either b∈f(S) or b∈f(T). This means either that b=f(a) for some a∈S or that b=f(a) for some a ∈T. In either case, b=f(a) for some a∈S∪T, so b∈f(S∪T). This shows that f(S) ∪f(T) f(S∪T), and our proof is complete. b) Suppose b∈f(S∩T). Then b=f(a) for some a∈S∩T. T

48、his implies that a∈S and a∈T , so we have b∈f(S) and b∈f(T). Therefore b∈f(S)∩f(T), as desired. 52 In some sense this question is its own answer—the number of integers between a and b, inclusive, is the number of integers between a and b, inclusive. Presumably we seek an express involving a, b, an

49、d the floor and/or ceiling function to answer this question. If we round a up and round b down to integers, then we will be looking at the smallest and largest integers just inside the range of the integers we want to count, respectively. These values are of course and , respectively. Then the answ

50、er is +1 (just think of counting all the integers between these two values, including both ends—if a row of fenceposts one foot apart extends for k feet, then there are k +1 fenceposts). Note that this even works when, for example, a=0.3 and b=0.7 . P162 2.4 34. a) This is countable. The in

51、tegers in the set are ±1,±2,±4,±5,±7,andso on. We can list these numbers in the order 1, -1 , 2, -2, 4, -4,…, thereby establishing the desired correspondence. In other words, the correspondence is given by 11，2-1， 3 2，4 -2，5 4， and so on. b) This is similar to part(a);we can simply list the element

52、s of the set in order of increasing absolute value, listing each positive term before its corresponding negative:5,-5,10,-10,15,-15,20,-20,30,-30,40,-40,45,-45,50,-50,…… c) This is countable but a little tricky. We can arrange the numbers in a 2-dimensional table as follows: .1 0.11 0.111 0

53、.1111 0.11111 …… 1 1.1 1.11 1.111 1.1111 …… 11 11.1 11.11 11.111 11.1111 …… 111 111 111.1 111.11 111.111 111.1111 …… …… …… …… …… …… …… d) This set is not countable. We can prove it by the same diagonalization argument as was used to prove that the set of all reals

54、 is uncountable in Example 21.All we need to do is choose di=1 when dii=9 and choose di=9 when dii=1 or dii is blank(if the decimal expansion is finite) 46. We know from Example 21 that the set of real numbers between 0 and 1 is uncountable. Let us associate to each real number in this range(inclu

55、ding 0 but excluding 1) a function from the set of positive integers to the set {0,1,2,3,4,5,6,7,8,9} as follows: If x is a real number whose decimal representation is 0.d1d2d3…(with ambiguity resolved by forbidding the decimal to end with an infinite string of 9's),then we associate to x the functi

56、on whose rule is given by f(n)=dn. clearly this is a one-to-one function from the set of real numbers between 0 and 1 and a subset of the set of all functions from the set of positive integers the set {0,1,2,3,4,5,6,7,8,9}.Two different real numbers must have different decimal representations, so th

57、e corresponding functions are different.(A few functions are left out, because of forbidding representations such as 0.239999…)Since the set of real numbers between 0 and 1 is uncountable, the subset of functions we have associated with them must be uncountable. But the set of all such functions has

58、 at least this cardinality, so it, too, must be uncountable. P191 3.2 1. The choices of C and k are not unique. a) Yes????? C = 1, k = 10 b) Yes????C = 4, k = 7 c) No?????? d) Yes????? C = 5, k = 1 e) Yes?????C = 1, k = 0 f) Yes??????C = 1, k = 2 9. x2+4x+17 ≤ 3x3 for all x＞17, so x2+4x+17

59、is O(x3), with witnesses C = 3, k=17. However, if x3 were O(x2+4x+17), then x3 ≤ C(x2+4x+17) ≤ 3Cx2 for some C, for all sufficiently large x, which implies that x ≤ 3C, for all sufficiently large x, which is impossible. P209 3.4 19. a) no??????b)?no?????c) yes????? d) no ? 31. a) GR???QRW

60、? SDVV? JR b) QB?? ABG? CNFF? TB c) QX?? UXM? AHJJ? ZX P218 3.5 13. a) Yes????? b) No??????c) Yes??????d) Yes 17 a) 2????? b) 4??????c) 12?????? P280 4.1 22. A little computation convinces us that the answer is that n2 ≤ n! for n = 0, 1, and all n ≥ 4. (clearly the inequality doe

61、sn’t hold for n=2 or n=3) We will prove by mathematical induction that the inequality holds for all n ≥ 4. The base case is clear, since 16 ≤ 24. Now suppose that n2 ≤ n! for a given n ≥ 4. We must show that (n+1)2 ≤ (n+1)!. Expanding the left-hand side, applying the inductive hypothesis, and then i

62、nvoking some valid bounds shows this: n2 + 2n + 1 ≤ n! + 2n + 1 ≤ n! + 2n + 1 = n! + 3n ≤ n! + n·n ≤ n! + n·n! ≤ (n+1)n! = (n+1)! P293 4.2 31. Assume that the well-ordering property holds. Suppose that P(1) is true and that the conditional statement [P(1)∧P(2) ∧···∧P(n)] →P(n+1) is t

63、rue for every positive integer n. Let S be the set of positive integers n for which P(n) is false. We will show S=?. Assume that S≠?, then by the well-ordering property there is a least integer m in S. We know that m cannot be 1 because P(1) is true. Because n=m is the least integer such that P(n) i

64、s false, P(1), P(2),…,P(m-1) are true, and m-1 ≥1. Because [P(1)∧P(2) ∧···∧P(m-1)] →P(m) is true, it follows that P(m) must also be true, which is a contradiction. Hence, S= ?. P308 4.3 10. The base case is that Sm(0)=m. The recursive part is that Sm(n+1) is the successor of Sm(n)(i.e., Sm(n)+

65、1) 12. The base case n=1 is clear, since f12=f1f2=1. Assume the inductive hypothesis. Then f12+f22+…+fn2+fn+12 = fn+12+fnfn+1= fn+1(fn+1+fn) = fn+1fn+2, as desired. 31. If x is a set or variable representing set, then x is well-formed formula. if x and y are all well-formed formulas, then?,

66、(x∪y), (x∩y) and (x-y) are all well-formed formulas. 50. Let P(n) be “A(1, n) = 2n .” BASIC STEP: P(1) is true, because P(1) = A(1, 1) = 2 = 21. INDCUTIVE STEP: Assume that P(m) is true, that is A(1, m) = 2m and m≥1. Then P(m+1) = A(1, m+1) = A(0, A(1, m))= A(0, 2m)=2·2m=2m+1. So A(1, n) = 2n whenever n≥1 59. b) Not well defined. F(2) is not defined since F(0) isn’t. Also, F(2) is ambiguous. d) Not well defined. The definition is ambiguous about n=1. P344 5.1 3. a) b) 12.