资源描述
P.161.14.f) If I did not buy a lottery ticket this week, then Idid not winthe 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 one and won the million dollar jackpot on Friday.10.a) r qb) p q rc) r pd) 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 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 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 dont begin your climb too late, then you will reach the summit.33.c) pqr(p q) (p r) TTTTTTFTTFTTTFFTFTTTFTFTFFTTFFFTP.261.28.a) Kwame will not take a job in industry and he will not go to graduate school.b) Yoshiko doesnt know Java or she doesnt know calculus.c) James is not young or he is not strong.d) Rita will not move to Oregon and she will not move to Washington.10.a) pqppqp(pq)p(pq)qTTFTFTTFFTFTFTTTTTFFTFFTc)pqp qp(p q)p(p q) qTTTTTTFFFTFTTFTFFTFT12.a) Assume the hypothesis is true. Then p is false. Since pq 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) Tc) Assume the hypothesis is true. Then p is true, and since the second part of the hypothesis is ture, we conclude that q is also true, as desired.24.pqrp qp r(p q) (p r)q rp (q r)TTTTTTTTTTFTFTTTTFTFTTTTTFFFFFFFFTTTTTTTFTFTTTTTFFTTTTTTFFFTTTFT30.pqrp qp rq r(p q)(p r)(p q)(p r) (q r)TTTTTTTTTTFTFTFTTFTTTTTTTFFTFFFTFTTTTTTTFTFTTTTTFFTFTTFTFFFFTFFT51.(p p) q )(p p) q )9.77. The graph is planar.a d e cf b20. The graph is not homeomorphic to K3,3, since by rerouting the edge between a and h we see that it is planar.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.83. 3 A F BC ED8. 39. 210. 417.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 102time slot 5: CS 273P.46 1.33. a) true b) false c) false d) false 5. a) There is a student who spends 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)c) x(P(x)Q(x)d) x(P(x)Q(x)16. a) true b) false c) true d) false24. 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) 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 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.591.412. 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)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 consists 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 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 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.” and 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 discourse 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 this class who have taken been in at least one room of every building on campus.1.5(1) (r(qp)(p(qr) (r(qp)(p(qr) (qp)(pqr) (pqrq)(pqrp) (pqr) 3 0,1,2,4,5,6,7(2)P.726. Let r be the proposition It rains, let f be the proposition 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 (rf)(sl), st, and t. We want to conclude r. We set up the proof in two columns, with reasons. Note that it is valid to replace subexpressions by other expressions logically equivalent to them.StepReason 1. tHypothesis 2. stHypothesis 3. sModus tollens using Steps 1 and 2 4. (rf)(sl) Hypothesis 5.(sl)(rf) Contrapositive of step 4 6.(sl)(rf)De Morgans law and double negative 7.slAddition, using Step 3 8. rf Modus ponens using Step 6 and 7 9. r Simplification using Step 812.First, using the conclusion of Exercise 11, we should show thatthe argument form with premises (p t) (r s),q (u t), u p, s, q, and conclusion r is valid.Then, we use rules of inference from Table 1.StepReason 1. qPremise 2. q (u t)Premise 3. u tModus ponens using Steps 1 and 2 4. u Simplification using Step 3 5.u p Premise 6.pModus ponens using Steps 3 and 4 7.tSimplification using Step 3 8. p t Conjunction using Steps 6 and 7 9. (p t) (r s)Premise 10.r s Modus ponens using Steps 8 and 9 11.sPremise 12.rDisjunctive syllogism using Steps 10 and 1114b) Let R(x) be “x is one of the five 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 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 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. 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.StepReason 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) 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)Premise 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.861.637. Suppose that P1P4P2P5P3P1. To prove that one of these propositions implies any of the others, just use hypothetical syllogism repeatedly.P.1031.713. 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 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 an 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.1202.19. T T F T T F16. Since the empty set is a subset of every set, we just need to take a set B 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 includes 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 ac) 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,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.1302.214. Since A = (A - B)(AB), we conclude that A = 1,5,7,83,6,9 = 1,3,5,6,7,8,9. Similarly B = (B - A)(A B) = 2,103,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 xA - 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 in B - C. The first of these implies that xA and xC. But now it must also be the case that xB, since otherwise we would have xB - 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 that are in an odd number of the sets A,B,and C.P147.2.335a) This really has two parts. First suppose that b is in f(ST). Thus b=f(a) for some aST. Either a S, in which case bf(S), or aT, in which case bf(T). Thus in either case b f(S) f(T). This shows that f(ST) f(S) f(T), Conversely, suppose bf(S) f(T). Then either bf(S) or bf(T). This means either that b=f(a) for some aS or that b=f(a) for some a T. In either case, b=f(a) for some aST, so bf(ST). This shows that f(S) f(T) f(ST), and our proof is complete.b) Suppose bf(ST). Then b=f(a) for some aST. This implies that aS and aT , so we have bf(S) and bf(T). Therefore bf(S)f(T), as desired.52In some sense this question is its own answerthe 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, and 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 answer is +1 (just think of counting all the integers between these two values, including both endsif 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 . P1622.434. a) This is countable. The integers 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 elements 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: .10.110.1110.11110.1111111.11.111.1111.11111111.111.1111.11111.1111111111111.1111.11111.111111.1111d) 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 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(including 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 9s),then we associate to x the function 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 the 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 at least this cardinality, so it, too, must be uncountable.P1913.21. The choices of C and k are not unique.a) Yes C = 1, k = 10b) YesC = 4, k = 7c) Nod) Yes C = 5, k = 1e) YesC = 1, k = 0f) YesC = 1, k = 29. x2+4x+17 3x3 for all x17, so x2+4x+17 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.P2093.419.a) nob)noc) yes d) no31.a) GRQRW SDVV JRb) QB ABG CNFF TBc) QX UXM AHJJ ZXP2183.513.a) Yes b) Noc) Yesd) Yes17a) 2 b) 4c) 12P280 4.122. A little computation convinces us that the answer is that n2 n! for n = 0, 1, and all n 4. (clearly the inequality doesnt 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 invoking some valid bounds shows this:n2 + 2n + 1 n! + 2n + 1 n! + 2n + 1 = n! + 3n n! + nn n! + nn! (n+1)n! = (n+1)!P293 4.231. 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 true 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) is 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= .P3084.310. 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)+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, (xy), (xy) 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 m1. Then P(m+1) = A(1, m+1) = A(0, A(1, m)= A(0, 2m)=22m=2m+1.So A(1, n) = 2n whenever n159.b) Not well defined. F(2) is not defined since F(0) isnt. Also, F(2) is ambiguous. d) Not well defined. The definition is ambiguous about n=1. P3445.1 3.a) b) 12.
展开阅读全文