离散数学及其应用(英文版)答案

所需积分/C币:44 2017-01-18 20:39:11 4.82MB PDF
462
收藏 收藏
举报


PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 Answers to odd-Numbered Exercises S-3 dctcrminc that the butler and cook arc lying but p 4 P艹qrs Ur + s mine whether the gardener is lelling the Lruth or whether the handyman is telling the truth. 37. The Japanese min owns TT F TT F T F 49 corrupt41.a)→(pA(q→)b)(p)A(-q))v(PAr) T FF T TFT T T FTF F F T F F F F TFFTFTTFFTTFT FFT H F Section 1.3 41. The first clause is true if and only if at lest one uf p, 4, and 1. Thc cquivalcnccs follow by showing that the appropriate ris true. ' The second clause is true if and only if at least one of pairs of columns of this table agree the three variables is false. Therefore the entire statement is truc if and only if there is at least onc t and onc f among the ruth vialues of the variables, in other words that they don'tall PPATLPVFIPAFIPVTIPVPPAP a Bitwise or is llI: T T bitwise ANDis OO0O000; bitwise XONis 11l1lll. b) bitwise F F F T OR is 1111 1010: bitwise ANDis 1010 0000 bitwise XOR is 0101 1010. e) Birwisc OR is 10 11 1001: bitwise AND is 3.a)p qpq gvp b)p qpAq9Ap 0001000000: bitwise XOR is 100011 1001. d) Bitwise OR T T is 1111111111: bitwise 4ND is 00 0000 0000: bitwise XOk T F isl1111l1111.45.0.2,0.647.0.8.0.649a)The TTTF T FFF F 99th statement is true and the rest are false. b)statements through 50 are all true and statements 51 through 100 are all talse. c) This cannot happen: it is a paradox, showing that thesc cannot be statements p 9 rqyrPA(gvr)pAq PAr(pA Section 1.2 TTTT TFTT l.e→a3.g→(A(-m)A(-b)5.e→(aA(b TFFF p)AF)7.a)q→Pb)A=pc)q→pd-q→P FTTIT 9 Lt 11, Consistent 13, NEW AND JER SEY AND BEACHES, (JERSEY AND BEACHES)NOT F FTT TTTFFFFF F TFTFFFFF T NEw 15. If I were to ask you whether the right branch F lcads to the ruins. would you answer yes? 17 If the first professor did not want coffee, then he wuuld know that the an swer to the hostess's question was"nn. Therefore the hoste 7. a) Jan is not rich, or Jan is not happy. b)Carlos will not and the remaining professors know that the irst professor did bicycle tomorrow, and Carlos will not run tomorrow. c)Mei want coffee. Similarly, the second professor must want coffee does not walk to class and mei does not take the bus to class When the third professor said"no, the hostess knows that the d ibrahim is not snarL or ibrahim is not hard worl third professor docs not want coffce. 19. A is a knight and B is a knave. 21. A is a knight and B is a knight. 23. A is a knave and B is a knight. 25. A is the knight, B is the spy, C 9.a) PAq(pA)- is the knave. 27. A is the knight, B is the spy, C is the knave T 29. Any nf the three can be the knight, any can be the spy, any TFF T can be the knave, 31. No solutions 33. In order of de- creasing salary: Frcd Maggic, Janice 35. The detective can F H F PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 S-4 Answers to odd-Numbered Exercise qpvq|p→(pvq) q 1s truc wh nd g have TT les, which means that p and g have different truth values T TTTF TTTT Similarly, p<> -g is true in exactly the same cases. 'There- fore, these two expressions are logically equivalent. 21.The FF proposition→(p分q) is true when p分 q is false, which mcans that p and c have diffcrent truth valucs. Bccause this is P→q-→(P→q) precisely when -p <> g is true, the two expressions are logi- cally cquivalent.23.For(p→r)∧(q→r) to bc falsc,onc TT F T T FF of the two conditional statements must be false, which hap- T pens exactly when r is false and at least one of Is true But these are precisely the cases in which pvy is truc andris Pqp^q|p→q(pAq)→(p→q) the two propositions are falsc in cxactly the same situations, they are logically equivalent.25.上or(p→r)y(q→r) TTT T to be false. hoth of the two conditional statements must he T FF false, which happens exactly when r is fal sc and both p and truc and r is falsc, which is prcciscly when (pA g) is false. Because the two propositions are false in exactly the e)pq|p→q-(n→q)-(p→q)→p same situations, they are logically equivalent. 27. This fact was observed in Section 1 when the biconditional was first TFF defined. Each of these is true precisely when p and g have the samc truth valucs, 29. The last column is all ts -(p→q)-g|-(P→q) 卩qrp→qq→r(q→r)|p T F F T FTT FTFF T F TTFT F F TFT F 11. In each case we will show that if the hypothesis is true, F TI T then the conclusion is also a) If the hypothesis p q is truc, FT FT F F TFTFTTTT T T then by the dcfinition of conjunction. the conclusion p must also be true. b) If the hypothesis p is true, by the delinition of disjunction, the conclusion pv g is also truc. c)If th hypothesis -p is true, thal is, if p is false, then the conclusion le. d) If the hypothesis p q is true, then both 31. These are not logically equivalent because when p, q, and p and g are true, so the conclusion p->g is also true. e)If r arc all falsc,(p→q)→ ris falsc,butp→(q→r)is true. 33. Many answers are possible. If we let r be true and the conclusion p is truc(and 4 is falsc). f) If the hypothesis P,q, and s he false,then(p→q)→(r→s) will he false, (p-q)is true, then p->q is false, so p is true and q is hu(P→y)→(q→s) will be true.35. a)Pv-q V false. Hence, the conclusion -y is truc. 13. That the fourth b)(pvqvr)As c)(pAT)v(gAF) 37. If we take duals column of the truth table shown is identical to the first column twice, cvcry v changes to an A and then back to an v, cvcry roves part (a), and that the sixth column is identical to the changes Lo an y and then back to an A every T changes first column provcs part(b) an f and then back to a t every f changes to a t and then back Lo an F. Hence, (3") 39. Let p and g be eyuiv P PAY PV(PAD)PV! PA(P Vy nd -. and T and F Notc that -p and -g arc also cquiv r I alent Use De Murgan's laws as many times as necessary Lo T FF push negations in as far as possible within these compound d F ng Ts to Fs, and vice versa. This shows that -p and -c are the same as p"and q cxcept that cach atomic proposition 15. It is a autol 17. Fach ot these is true pi pr within them is replaced by its negation. From this we can p and g havc opposite truth valucs. 19. The oncludc that pand q arc cquivalent bccausc -p and -q PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 Answers to odd-Numbered Exercises $.5 r.41.(P入qA一r)∨(pA一q∧r)Y(→p入q入r)-P(4)√-P(5)21. Many answers arc possiblc.a) 43. Given a compound proposition P, form its truTh table tudents in your discrete mathematics class: all students in and then write down a proposition q in disjunctive nor the world b)All United States senators; all college footbal mal form that is logically cquivalent to p. Because q in players c) Gcorge w. Bush and Ich Bush; all politicians wolves only -,A, and v, this shows that these thrcc op in the United States d) Bill Clinton and gcorgc w. bush erators form i functionally complete seL. 45. By Exercise all politicians in the United States 23 Lel C(x) be the 43, given a compound proposition p, we can write down propositional function"x is in your class. "a)3x H(x)and proposition g that is logically cquivalent to p and involves only -,A, and v By De Morgan's law we can eliminate all b)x F(x)and V r(C(x)-> F(x)),where F(x)is "x is thc^ s by replacing cach occurrence of p∧p2A……∧pn friendly”c)丑x-B(x)ind3x(C(x)∧-B(x), where B(x)is th -(-Piv-p2v..v-Pn). 47 -(p A g)is k was born in california”d)丑xM(x)and彐x(C(x)AM(x) when either p or 4, or hoth, are false, and is false where M(r)is x has bccn in a movic e)x-L(r)and when both p and g arc truc. Recause this was the dcti vx(C(x)->=L(x)), where L(x)is"x has liken a course nition of p 4, the two compound propositions are logi- in logic programming" 25. Let P(x) be"x is perfect cally equivalent. 49. (p v q) is true when both p and let F(x) be "x is your riend; and let the domain be all q are false, and is false otherwise. Because this was cople. a)Vx P(x)b)ve P(x)c)Vx(F(x)-P()) the definition of p+ g. the two are logically cquivalent. d Ex(F(x)A P(x))e)vx(F(x)A P(x))or(x F(x)) s1.(P↓p)↓q)↓(p↓p)↓q)53. his follows im- x P(x)) n(Vx F(x))y(x=P(x)) 27. Let Y(r)be mediately from the truth table or delinition of p iq the propositional function that x is school ur class. as I 6 57. If the databasc is op appropriate. a) If we let v(x)be"x has lived in Victnat tcm is in its initial state or the monitor is put in a closcd then we have 3x v(r) if the domain is just your schoolmates, state. 59. All nine 61. a) Satisfiable b) Not satisfiable or Ex(r(x)A v(x)) il the domain is all people. Ir we e)Not satisfiable 63. Use the salme propositions as were D(x, y) mean that person x has lived in country y, then we given in the text for a 99 Sudoku puzzle, with the vari- an rewrite this last one as =x(Y(x)A D(x, vietnam)). b)If ed from i to 4, instcad of from i to 9, and e let H(x) be sp with a similar change for the propositions for the 2 x 2 if the domain is just your schoolmates, or x(r(x)A-H(r)) blocks:=0∧=0∧m=1V=1V2=1P(2+t,25+j,n if the domain is all people. If we let S(r, v) mean that per 65.V,p(i, j, n)asserts that column j contains the number son x can speak language y, then wc can rewrite this last ne as 3x(y(x)A-S(r, Hindi)). c)If we lel J(x), P(x). 9 numbers: thercforc∧∧n=1V1p(,,n) asserts that and C(x)be the propositional functions asserting x's knowl- every column contains every number. edgc of Java, P nd C++, r'espectively, then we hav Ex((x)A P(x)AC(x)) if the domain is just your school )∧P(x)∧C(x) Section 1.4 is all people. If we let K(x. y) mean that person x knows programming language y, then we can rewrite this last one as (F(x)∧K(x,Java)AK(x olog)AK(x C+ -)).d) is a student who spends more than 5 hours every weekday wc lct T(x)bc"x enjoys Thai food "then we havc Vx T(x) ycckday in class. c) Thcre is a student who docs no if the domain is all people. If we let E(x, y)mean tha spend morc than 5 hours cvcry wcckday in class. d)No person r enjoys food of type y, then we can rewrite this stuident spends more than 5 hours every weekday in clias last one as vx(y(x)-> E(x, Thai)). e)If we let H(r) 7. a)Every comedian is funny. b)Every person is a funny be"x plays hockey, "then we have 3x H(x) if the do comedian. c) Thcrc exists a person such that if she or he is main is just your classmates, or Ix (Y(x)A H(r))if median, then she or he is funny. d)Some comedians che domain is all pcoplc If we lct P(x, v)mcan that pcr are funny. 9. a)Ex(l(x)A@()) b)3x(r(x)A((r)) on x plays game v, then we can rewrite this last one a c)Vx(P(x)vo())dVx-(P(x)vo(r)) I1.a)T b)T Ex(Y(x)A-l(x, hockey )) 29Let r(x)mean that x is a c)F df e)t ff 13. a)t bit ct dIt 15.a)T tautology and c(x)mcan that x is a contradiction. al 3.x T(r) b)Fc)Td)上17.a)P(0)P(1)VP(2)P(3)P(4)b)x(C(x)→>f(→x)e)彐x=y(-(x)A=C(x)∧=T(y)A h)P(0)AP(1)AP(2)AP(3)AP(4)c)-P(0=P(1) C(r)AT(x vy)) d)yry((T(x)Al())->T(rAy)) P(2) P(3)-P(4)d)-P(0)A=P(1)八 31.a)Q(0,0,0)AQ(0,1,0)b)Q(0,1.1)vQ(1、1,1 2)A=P(3)A=P(4)e)-(P(0)YP(1)vP(2) Q(2,1.)c)-Q(0,0.0)y-Q0.0,1)d-Q(0,0,1) P(3)P(4)動-(P(0)入P(1)AP(2)AP(3)AP(4)) o(1.0,1)v-2(2.0, 1) 33. a)Lct T(x) bc the predicate 19.a)P(1)vP(2)vP(3)vP(4)vP(5)bP(1)AP(2) at x Can learn new Tricks, and let the domain be old dogs P(3)AP(4)AP(5)c)一(P(1)vP(2)vP(3)VP(4)VP(5) riginal is lx T'(r). Negation is Vx7(x): No old dogs can d)-(P(1)AP(2)∧P(3)∧P(4)AP(5)e)(P(1)八 carn new tricks. h)Ict. C(x) be the predicate that x knows P(2)∧P(4)∧P(5)(P(1)y一P(2)V-P(3) calculus, and let the domain be rabbits. Original is -=x C(x) PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 S-6 Answers to odd-Numbered exercise Negation is 3.x C(x): Therc is a rabbit that knows calculus other side is truc. a)Supposc that A is truc. Then for cach r c)Let F(x) be the predicate that x can fly, and let the domain P(r)-> A is true; therefore the left-hand side is always true be birds or in this case. By similar reasoning the right-hand side is always a bird who cannot ly. "d)Let T'(x)be the predicate that x can true in this case. Therefore, the two propositions arc logically talk, and let the domain be dogs. Original is -ax T(x). Nega uivalent when A is cruc. On the othcr hand, supposc that A tion is ax T(x): Thcrc is a dog that talks. e)Lct F(x)and is false. There are two subcases. If P(x)is false for every R() be the predicates that x knows French and knows Rus then P(x)-A is vacuously truc. so thc Ictt-hand side is an, respectively. and lct the domain bc people in this class ac LIuusly true 'The same reasoning shows that the right-han side is also true, because in this subcase =x P(x)is false. For There is someone in this class who knows frcnch and rus- sccond subcase, suppose that P(r)is truc for some r. Then sian. 35. a)There is no counterexample. b)x=0c).x=2 for that x P(x)- A is false, so thc lcft-hand sidc is falsc.The ght-hand side is also false, because in this subcase 3x/(x) is"Person x qualifies as an elite flyer in a given year F(x is true hut A is false. Thus in all cases, the two propositions is"Pcrson x flics more than y miles in a gi cn ycar. al have the same truth valuc. b)If A is truc, then both sides S(r, y)is"Person x takes more than y flights in a given year are trivially lrue. because the conditional statements have b)Vx(((M(x)AT(r, 3))v(M(x)A T(x, 3.5)))->Q(x)) true conclusions. If A is false. then there are lwo subcases. If where Q(r)is"Person x qualifies for the marathon P(x)is false for some x, then P(x)-Ais vacuously true M(r) is"Person x is a man, and T(r, v) is" x for that x, so the left-hand side is true. The same reasoning has run the marathon in less than y hours H(60)(H(45)T∧↓yG(B.y), whcrc a is the nows that thc right-hand sidc is truc, bccausc in this subcasc xP(x)is false. For the second subcase, suppose that P(r)is oposition"The student received a masters degree, " H()is The student took at least. x coursc hours, T is the proposition ryx. Then for cvcry x. P(x)- A is falsc. so thc left-hand side is false (there is no x making the conditional "The student wrote a thesis."and statement true). the right-hand side is also false, because it is grade or higher in course y "d)x((T(x, 21)AG(x, 4.0)), a conditional statement with a truc hypothesis and a false con where T(. y)is"Person x took more than y credit hours and G(r, p) is"Person x earned grade point average p clusion. Thus in all cases. the two propositions have the salm (we assume that we are talking about onc given semester) truth value. 51. To show these are not logically cquivalent, P(x)bc the statement"x is positive, "and let Q 39. a)If there is a printer that is both out of service and busy, then some joh has bccn lost. b)If cvcry printer is the stalement"x is negaLive "with domain the set of integers busy, then there is a job in the qucuc. c)If there is a job Then 3x P(x)A 3x Q(x)is true, but 3x (P(x)AQ())is that is both queued and lost, then some printer is out of ser- lse. 53. a) Truc b) false, unless the domain consists of vice. d) If cvcry printer is busy and cvcry job is qucucd just one elernent c)True 55. a)Yes b) No c)juana, kiko then some job is lust. 41. a)(x F(x, 10))-> 3.x S(x), d)math273, cs301 e)juina, kiko 57. sibling(x,Y where F(x. y)is"Disk x has morc than y kilobytes of nother(M, X), mother(M, Y), Eather(F, X) free space, "aund s(x)is"Mail message x can be saved father(F, Y) 59. a)vx(P(r) e(x)) (xA(x)→x(Q(x)→Y(x), where a(x)is" Alert x b)Vx(Q(x)-> R(x))e)vx(P(r) nR(x) d)The is active, @(r)is"Message x is queued, and T(x)is""Mes- conclusion does not follow. There may be vain profes- e x is transmitted”e)x((x≠ main console)→T(x) sors, because the premises do not rule out the possibil where t(x)is " The diagnostic monitor tracks the status of ity that thcre arc othcr vain pcople bcsidcs ignorant onc system x"d)vx(L(x)- B(x)), where L(x)is"The host 61.a)vx(P(x)→>-Q(x)b)vx(R(x)→S(x)) of the conference call put participant x on a list and c)Vx(→Q(x)→5(x))d)vx(P(x)→→R(x))e)The B(x)is""Participant x was billed 43. They are not equiva conclusion follows. Supposc x is a baby. Then by the first lent. Ict P()be any propositional function that is sometimes premise,x is illogical, su by the third premise, x is despised. true and somelimes false, and let ((x) be any Propos The secund premise says thiat if x could manage a crocodile, function that is always falsc. Then Vx(P(x)-o(x))is falsc then r would not he despised. Therefore, x cannot manage a but x P(x)- Vxe()is truc. 45. Both statements arc truc precisely when at Icast. one of P(x)and @() is truc f at least onc valuc of x in the domain 47 al It a is truc then both sides are ally equivalent to Vx. r(x). If A falsc. the lcft-hand sidc is clcarly falsc Furthcrmorc, for cvcry x, P(x)A A is false, so the right-hand side is false. Hence, Section 1. 5 the two sides arc logically cquivalent. b)If A both sides are logically equivalent (o 3x P(x). If A is false. a)For cvcry rcal number r thcre exists a rcal number yy the left-hand side is clearly false. Furthermore, for cv such that r is less than y. b)For every real number x and real P A is fals (P(x)∧A) is false.He egative, thei sides are logically cquivalent. 49. We can cstablish these is nonnegative. c)For every real number x and real number equivalences by arguing that one sidc is truc if and only if the 3, there exists a rcal numbcr z such that xy=z. 3. a)There PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 Answers to odd-Numbered Exercises S-7 In Tho has sent y”andQ(x,z)is“ r has bcen in some student in your class. b) There is some student in your sists of all students in the class, the domain for y consists class who has sent a message to every student of all buildings on campus, and the domain of z consists of )Every student in your class has sent a message Lo at lea all rooms. g)xyz(P(=v)A o(. 2)), with same cn- inc student in your class. d) There is a student in your clas in part. (f) 17. a)VuEnt(A(w m)A Vn(e= student in n->A(u, n))), where A(u, nm)means that user u has e)Every student in your class has been sent a message fre acccss to mailbox n t)彐pve(H(e)∧S(p, running) at Icast onc student in your class. f) Every student in the clas S(kernel. working correctly ) where H(e mcans that has sent a message to cvcry student in the class. 5. a) Sarah ror condition e is in elfect and S(x, y)means that the Smithhasvisitedwww.att.com.b)atleastoncpersonhasstatusofxisyc)vus(E(s,.cdu)a(u,s)),whcre visitedwww.imdb.org.closeOrezhasvisitedatleastone website. d There is a website that both Ashok Puri and E(sx) mcans that website s has extension x and A(u. s) means that user u can access website s d)3xdy(x Cindy Yoon have visited. e) There is a person besides David Belcher who has visited all the websites that david belcher y'A Vz( 9s M(z,s)) has visited. D)There are two different people who have visited whcrc M(a b)mcans that systcm a monitors remote server b exactly the same websites. 7. a) Abdallah Hussein does not 19.a)vxvy((x<0)A(y<0)→(x+y<0)b)→vxy like Japanese cuisine. b )Some student at your school like (x≥0)A(y≥0)→(x-y∷0)c)wxy(x2+y Korean cuisine, and everyone at your school likes Mexican (a+y))d)Vrvy(lxy= ally 21. v. r3a3bacad ((r cuisine. c) Thcrc is some cuisine that cithcr monique 0)->x=a'+b2++d2). where the domain consists of all integers 23. a)Vray((x<0)A(<0)-(ry> students at your school. there is somc cuisine that at least onc 0))b)v(x-x=o) e)9x3a=b(a f bA ic(c-=x+ them does not like. e) There are twn students at your school (c=aVC=b)d)Yx(x<0)→→3y(x=y2) who like exactly thc same sct of cuisines. f)For cvcry pair 25. a)There is a multiplicative identity for the real numbers of students al your school. there is some cuisine about which b) The product of two negative rcal numbers is always a po they have the same opinion (cithcr thcy both like it or they itive real number. c) There exist real numbers x and y such both do not like it). 9. a)VxL(x, Jerry) b)vx3yL(x. y) d) 把are c)yVxl(r, y) d)vx=/(x, y) e)=x-l(lydia, x) loscd under the opcration of addition. 27. a) Truc b)Tr n彐xy-L(y.x)g)丑x(yL(y:x)∧v(wL(w,x)→ c) True d) True e) True f) false g) False h) True i) False C= x))hr=y(r =y.(ynn, r)A1(Lynn. y) 29.a)P(1,1)AP(1,2)AP(1,3)AP(2,1AP(2,2) Vz(L(Lynn,)→(x=xvz=y))i)vxL(x,x)j彐rvy P(2,3)AP(3,1)∧P(3.2)∧P(3,3)b)P(l,1) (L(x, y)++x=y) I1. a)A(Lois, Professor Michaels) P(,2)∨P(1,3)∨P(2,1)P(2,2)P(2,3)∨P(3.Dv b)v x(s(x)-A(x, Professor Gross))c)x(F(x)-(A(r P(3 P(3,3)c)(P(,D)^P(1,2)AP(1,3) Professor Miller)v A(Professor Miller, x)))d)Ex(S(x)A (P(2, 1)A P(2, 2)A P(2, 3))v(P(3. 1)A P(3, 2)A P(3. 3)) vy(F(y)→-A(x,y)e)彐x(F(x)∧y(S(y)一 d(P(1,)ˇP(2,1)∨P(3,))∧(P(1,2)VP(2,2)v A(y,x)Dvy(f(y)→x(S(x)A(x,y))g三x(F(x) P(3,2)A(P(1,3)P(2,3)P(3,3))31.a)3xVy3z-7 vy(F(y)A(y≠x)→A(x,y)h三x(S(x) (x,y,z)b)彐xvy-P(x,y)∧彐xy-Q(x,y)c)三xy V(F(y) -A(y. x))) 13. a)=M(Chuu, Koko) -P(r,v)vV2-R(r, v, z ))d)arvy (P(x y )A-Q(, y)) ara 33.a)丑xy-P(x,y)b)彐yx-P(x.y)c3y3x(P(x, rah, Jose)d)VxM(. Ken)e)Vr-f(x, Nina)f)Vx(T-x, Avi) M(x,Avi))g彐vy(y≠A→M(x,y)h)彐xvy(y≠ y)A-2(r, y)) d)(vxvy P(x, y)) ray=o(. y)) e)arVvEz-P(,v.)vVEy-P(, y, 2)) 35. Any di T(x, y)))i)3xy(x+yAM(x,y)A M(,x)j彐xM(x,x)k)xvy(x≠y→(→M(x,y)A lain with four or more memhers makes the statement truc 1(y,x))Dwx(y{x≠yA(M(y.x)√r(y,x) any domain with threc or tower members makes the stat nent false. 37. a)There is this class such m)3y(x≠yAM(x,y)A7(,x)n)3x3y(x≠yA vz((3≠x∧≠y)→(M(x,3)M(y,)√I(x,z)Y that for every two ditferent math courses, these are not T(, 2)))) 15. a)VxP(r), where P(r)is*x needs a course the two and only two math courses this person has taken in discrete mathematics"and the domain consists of all com- b) Every person has either visited Libya or has not visited puter science students b)ix P(x), where P(r)is"* owns a country other than Libya. c) So a personal computer" and the domain consists of all students ry mountain in the Himalay as. d)There is someone who in this class c)Wxy P(x y), where P(, y)is x has taken has neither been in i l movie with kevin bacon nor has beel y the dormain for x consists of all students in this class in a movic with someone who has been in a movie with and the domain for y consists of all computcr scicnce classc Kevin Bacon. 39.a)x=2,I .2 b)x d) c) 1 41.x yy yz((x y) in part(c) e)VAV P(x ,), where P(x, y)is"I has becn 43.vmvb(m≠0→彐x(mx+b=0Aww(m+b in y: the dumain for x consists of all students in this class 0- W= x)))45.a) Truc b)Falsc c)Truc and the domain for y consists of all buildings on campus 47 -(ErvyP(x, y))<>Vx(-vyP(x, y))<VxEy-P(x, y) f)彐x3yz(P(z Q(.z)). where P(z ))is"z is in 49.aSupposc that wx P(x)A3. o(x)is PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 S-8 Answers to odd-Numbered exercise truc for all x and there is an clcmcnt y for which Q(y)is true will not gct thc job, follows. 7. Universal instantiation is Bccausc P(x)Ao(y)is truc for all x and thcrc is a y for which sed Lo conclude thal"If Socrates is i man, then Socrates e(y)is true. Vx3y(P(x)A Q())is true. Conversely, sup- mortal. "Modus ponens is then used Lo conclude that Socrates pose that the second proposition is true. Iet x he an element is mortal. 9. a) valid conclusions are "" I did not take tues- the domain. There is a y such that O(y)is true. So 3 .Q(x) day off,"I took Thursday off. "It rained on Thursday. b)I is true Because rl(r)is ilso true, il follows that the first. did did not eat spicy foods and il did nut thunder"is a valid con proposition is truc. b)Supposc that vx P(x)v Er@(x) is clusion. c)"T am clever"is a valid conclusion. d)"Ralpl ruc. Then cithcr P(r)is truc for all *, or thcrc exists a y for not a CS major" is a valid conclusion. e) you buy hich ((y) is true. In the former case. /(x)v@(y)is true lots of stull is good for the U.S. and is good for you "is a for all x, su Vxy(P(r)v g(y))is true. In the latter case, alid conclusion. f)Mice gnaw their food"andRabbils e(v)is true for a particular y, so P()ve(v)is true for all are not rodents"are valid conclusions. I 1. Suppose th r and consequently Wy(P(x)ve())is truc. Conversely. Pu arc truc. Wc want to cstablish that g- suppose that lhe second proposition is true. If P(x)is true lu is Lrue. If q is Talse, then we are dune, vacuouSly. Otherwise all x thcn the hirst proposition is true. If not. P()is talc for 4 is true, so by the validity of the given argument form(that some, and for this x there must be a y such that P(x)vo(y whenever p1,p2,.,P,,g arc true. then r must be true), is truc. Hence, @(v)must he truc, so yo(y)is true. It tol- know that r is truc. 13. a) Lct c(x)bc"x is in this class, lows that the first proposition must. hok. 51. We will show j(x)bex knows how to write programs in JAVA, " and h( how an expression can be put into prencx normal form(PNF) e"x can get a high-paying job. The premises are c(Doug) if subexpressions in it can be put into PNF. Then working Doug),vx(j(r)-h(r)). Using universal instantiation from the inside ouL, any expression can be put in PNF.(lo and the last premise, j(Doug )-> h(Doug)follows. Applying formalize the argument, it is necessary to use the method of modus ponens tu this conclusion and the second premise, structural inducTion that will be discussed in Section 5.3.)By h(Doug)follows. Using conjunction and the first pre Exercise 45 of Section 1.4, we can assume that the proposition c(Doug)A h(Doug) follows. Finally, using existential gener uses only v and - as logical connectives. Now note that any alization, the desired conclusion, 3.(c(x)A h(r))follows proposition with no quantifiers is already in PNf. (This is the b)Let c(x)be"x is in this class, "w(r)be"t enjoys whale basis case of the argument. )Now suppose that the proposition watching, and p(x) he r cares about occan pollution of the form gx P(r), where Q is a quantifier. Bccausc P(r The premises are 3x(c(x)A w(x)) and x(w(x)- p(r)) is a shorter expression than the original proposition, we can put it into PNE. Then gx followcd by this PF is again in P.F son y. Using simplification, w(v) follows. Using the sec- that the proposition is of thc form -P If P is adv in pn ond premise and universal instantiation. w(y)- p(y) we slide the negation sign past all the quantifiers using the follows. Using modus ponens, p(y)follows, and by cun equivalences in'Table 2 in Section 1. 4. Finally, assume thal junction,c( )A p(y)follows. Finilly, by existential gen cralization, the desired conclusion. xr(c()A p(r)), fol proposition is ot the form Pv 2, where cach of P and Q is PNF. If only one of / and Q has quantifiers, then we can use lows. c)Let c(x)be"x is in this class, P(x) be"x owns Excrcise 46 in Scction 1. 4 to bring the quantifier in front of a PC, "and w(r) be"r can use a word-prucessiny pro- gram. The premises are c(Zeke), Vx(c(r)- p(r), and both.If both P and g have quantifiers, we can usc Excrcisc Vx(p()+w(x)). Using the sccond premise and universal 45 in Section 1.4, Exercise 48, or part(b)of Exercise 49 Lo write PvQ with two quantifiers preceding the disjur instantiation, c(Zeke)-> P(Zeke )follows. Lsing the first sInise of a proposition of the form R S, and then put R V S inlo p(Zeke)follows. Using the third PNH premise and universal instantiation, p(Zeke)w(Zeke) follows. Finally using modus poncns w (Zckc) the desired d) Let j(x) x) be"r lives within 50 miles of the ocean "and s(r) be r has seen the nccan. The premises arc Vx(/(r)>/(r) lial instantiation imply that j (y)A "s(y)for a particular universal instantiation and the first premise, j(y)+/(y) I. Modus ponens, valid; the conclusion is truc, because and by modus ponens, f()follows By simplification, -s(y) the hypotheses arc truc. 3. a)Addition b)Simplification follows frun j(y)A-s(y). So f(y)As(y)follows by con c)Modus ponens d) Modus tollens e) Hypothetical sylla junction. Finally, the desired conclusion, ar(/(r)As(x gism5. Let w he‘ Randy works hard” let d be“ Randy is a llows by existential generalization. 15. a)Correct. using dull hoy, and lct i be "Randy will get the joh. The hypoth universal instantiation and Modus ponens b) Invalid; allacy es are w, w-d, andd-nj Using modus ponens and the of affirming the conclusion c)Invalid fallacy of denying first two hypotheses, d follows Using modus ponens and the the hypothesis d) Correct, using universal instantiation and last hypothesis, j. which is the desired conclusion. "Rand modus tollens 17. we know that somme x exists that make PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 Answers to odd-Numbered Exercises S-9 H(x)truc, but nclude that lola is onc such x words, we know that -g has to bc truc. This is a contradiction 19. a) Fallacy uf affirming the conclusion b)Fallacy of beg Su this proposition is not satisfiable. 35. valid ing the qucstion c)Valid argument using modus tollens d)Fallacy of denying the hypothesis 21. By the second Section 1.7 premise, there is some lion that does not drink coffee. Let L eo he such a creature. By simplification we know that Ien is a lion. By modus ponens we know from the first premise that Leo is fierce. Hence, Len is fierce and does not drink gcrs. Then n+m=2(+1+) is cven. 3. Supposc that coffee. By the definition of the existential quantifier, there 2k)2=4k=2(2k2). Bccausc wc have written n2 exist fierce creatures that do not drink coffce. that is. some as 2 times an integer. we conclude that m-is even. 5. DirecL fierce creatures do not drink coffee 23. The error occurs in 5. bccausc wc cannot assume, as is proof: Suppose that m+n andin+pare even Then m+F2=2s donc herc for some integer s and n +p= 2/ for some intcger I If we at the c that makes P truc is the same as the c that makes g add these, we get m p+2n= 25+ 2r. Subtracting 2n frum le. 25. we are given the premises Vx(P(x)->2(x))and oth sides and factoring, we have m+p=2s+21-2n= @(a). We want to show -P(a). Supposc, to the contrary 2(5+t-n). Becausc wc have written I p as 2 times that -P(a)is not true. 'Then P(a) is true. 'Therefore by uni an integer, we conclude that. m p is even. 7. Because n versal modus punens, we have @(a). But this contradicts the is odd. we can write n= 2k +1 for some integer k. Thet given premise ((a). Therefore our supposition must have (k+1)2 k2+2k+1-k2=2k+1=n.9.Su been wrong. and so -P(a)is true, as desired hat r is rational and i is irrational and s=P+i is rational hen by Example, s+(r)=iis rational, which is a contr 27. Step Rease /2=2is rationalandv2 (r)AR(x) P tional, the product of two irrational numbers is not 2.P(a)∧R(t) Universal instantiation from(1) irrational. 13. Proof by contraposition: If 1/x wcrc rationaL. P Si then by definition I 4.Vx(P(x)→ qf0 Bccausc 1/ x cannot be 0(if it wcrc, then wed hay Q(x)∧S(x) 5.Q(a)∧S(a Universal modus poncns from(3) the contradiction 1=r O by multiplying both sides by x),we and (4) know that p40 Nowx=1/ (1/ x)=1/(p/ q)=g/ p by the rules of algebra and arithmetic. He be 7.R(a) Simplification from as the quotient of lwo integers with the denominator nonzero. 8.R(a)∧S(a) Conjunction from(7)and (6) Thus hy definition, x is rational. 15. Assume that it is not 9.Vx(R(x)A S(x)) Universal generalization from (5) truc that x> l or y= 1. Thcn x-1 and y<1.Adding thcsc two inequalities, we obtain x +y 2, which is the negation 中p Reas 2. 17. a)Assumc that n is odd. so n= 2K+l for 1.彐x-P(x) Premise me integer k. 'Then n+5=2(4k+6k+3k +3). Because 2.-P{C) Existential instantiation from(I) 73+5 is two Limes some integer, it is even. h) Suppose thalt 3. x(P(xr)vo(r)) Premise 22+5 is odd and n is odd. Because n is odd and the prod ()Q( Universal instantiation from CL U Q(c) sm then ' is odd.Bu to be cven bccausc it is the diffcrence of two odd numbers 6. x(o(r)v 5(x)) Premise Therefore, the supposition that n+5 and n were both odd is Universal instantiation from (6) wrong. 19. The proposition is vacuously truc bccausc 0 is 8.S D syllogism from (5) not a positive integer. Vacuous prouf. 21. P(1)is true be 9. x(R(r)--S(r) Premise cause(a +b)=a+b=a+b=a+b Direct proof 10. R(c)--S(c) Universal instantiation from(9) 23. If we chose 9 or fewer days on each day of the week. this 11.→R(c) Modus tollens from (8)and(10) would account for at most 9. 7= 63 days. But we chose (14 Existential generalization fro days. This contradiction shows that at least 10 of the days we rom chose must be on the same day of the weck. 25. Supposc hy way of contradiction that a b is a rational root, where a and b 31.Lct p be "It is raining; let g be"Yvette has her umbrella care integers and this fraction is in lowest terms (that is, a and let r be"Yvette gets wet " Assumptions at b havc no common divisor grcatcr than 1). Plug this proposcd and pv -r Resolution on the first two gives -pv-r Res root into the equation to obtain a/b1 a/ b +1=0.Mul- lution on this and the third assumption gives -r. as desired tiply through by b 'to obtain a+ab+b'=0. If a and h 33. Assume that this proposition is satisfiable. Using rcsolu- arc both odd. then the left-hand side is the sum of three odd tion on the first two clauses cnablcs us to conclude q vg: in numbers and therefore must be odd. If a is odd and h is even other words, we knuw that g has Lo be true. Using resolution on then the left-hand side is odd even even which is again the last two clauses enables us to conclude -gv-g: in other dd. Similarly, if a is cven and b is odd, then the lcft-hand PI: 1 ANS Rosen-231 IT MHIADI7-Rosen-v5cIs May 13. 201 1 101: 29 S-10 Answers to Odd-Numbered exercises sidc is cvcn +cvcn +odd. which is again odd. Bccausc the 7s that 3n+l is odd, showing that (it)implies (iii ) Next fraction a/ h is in simplest terms, it cannot happen that hoth se that 3n+ l is odd so 37+ 1= 2k+ l for some n. Thus in all and therefore cannot equal 0. 'This contradiction shows that This shows that (iii)implies(iv). Finally, suppose that n is no such root exists. 27. First. assume that n is odd. so that nut even. Then n is odd, so n= 2k+ 1 for sume integer k. n=2k+ I for somc integer k. Then 5/+6=5(2K+1)+6= Then 3n=3(2k+I)=6k+3=2(3k+1)+l, so 3n is odd 10k+11= 2(5k+5)+l. Hence, 5n+6 is od. Iu prove This completes a proof by contraposition that(iv)implies (i) the converse, suppose that n is even, so that n= 2k for some integer k Then 5n+6= 10k+6=2(5k+3), so 5n+6 is even. Hence, n is ocd if and only if 57+ 6 is odd. 29. This proposiTion is true. Suppose that m is neither l nor-1.Then nLn has a factor m larger than I. On the other hand, mn=I and 1 has no such factor. hence in first case n= 1. and in the secund case n7 Section 1. 8 n=1/ m. 31. we prove that all these are equivalent to being even If x is even, then x=2k for sorme integer k. There- 22+1=5≥4=2;32+1= fore 3 x+2=3. 2k+2=6k+2=2(3k+1), which is even 1028=23;42+1=17216=243.Ifx because it has been wrilten in the form 2t, where t=3k+1 then max(x, y)+ min(x, y)=y+r=x+y If x es, Similarly,x+5=2+5=2k+4+1=2(k+2)+l then max(x, y)+ min(x, y)= x+ y Because these are s is ocd: and 12 he only two cases, the equality always holds. 5. Because is even. For the converses, we will use a proof by contra- lx-y=ly-xl, the valucs of x and y arc interchange position. So assume that x is not even: thus x is odd and able. Therefore, without loss uf generality, we can assume that we can write x some Integer r> y Thcn(+y-(x-y))/2=(x+y-x+r)/2= 3x+2=3(2k+1)+2=6k+5=2(3k+2)+1, which is odo 2y/2=y=min(x, y). Similarly, (x +y+(r-y))/2= c. not cven), bccausc it has been writtcn in the form 2/+I max(x, y) where t= 3k+2. Similarly, x +5=2k+1+5=2(k+3), 7. There arc tour cases. Case 7: x 0 and v :0. Then so x t 5 is even (ic,, not odd). That x- is odd was already F r+ lyl= x+y=lr+ yl Case 2: x <0 and y <0 proved in Example 1. 33. We give proofs by contrapositio Then r|+ly==x+(y)=-(+v)=Ir+yI because of(i)→(i),(→(),()→(in),and(i)→(i) +)<0. Case 3. x >0 and v-0. Then x+ly=x+(-y For the first of these, suppose that 3x+ 2 is rational, namely, Ifx= -y, then|x+y=x+y But because y<0.-y>y yual to P/ q for some integers P and q with q#0. Then we 0|x|+|y=x+(-y)≥x+y=x+川Hfx≤-y,then can write x =((P/ q)-2)/3=(p- 24)/(34). wher x+y=-(x+y)=-x+(-y). Bul because x≥0.x≥-x 3q=o. This shows that x is rational. For the sccond condi- soIrl-+lyl=x+(-y)2-x+(-y)=lx+yl Case 4:x< 0 vo Identical to casc 3 with the roles of r and p/ q for somc integers p and q with q+O. Then we can write rsed.9. 10,001. 10.002...., 10, 100 arc all nonsquare 3. x+2=(3p+2q)/ q, where q+0. This shows that 3. x+2 is because 1004= 10.000 and 1012=10.201: constructive rational. For the third conditional statement, supposc that x/ 2 11.8=2 and 9=32 13. Let x=2 and y= v2.It is rational, namely, equal to p q for some integers p and q xv=2v-is irrational. we are done. Ifnot. then letx= 2v= ano with q#o. Then we can write 2p/g where 40. This y=√2/4. Then x=(22)2/=22(2)/4=2l2=√2 ment, suppose that r is rational, namely, cqual to pig for some property. If we let y=l,<s the existence of r with a certain shows that x is rational, and for the fourth conditional state- 15. a)This statenent asserts n we see that P(x)is true. If y integers p and g with g=0Then wecan write x/2=P/ (29) is anything other than x. then P(x) is not truc. Thus, is the where 24 0. This shows that x 2 is rational. 35. No unique element thal makes P true. b)The first clause her 37. Supposc that p1→p4→p→p5→p;→p1. To says that there is an clement that makes P truc. The second prove that one of thesc propositions implies any of the others clause says that whenever lwo elements buth make p true just usc hypothetical syllogism repcatcdly. 39. Wc will give they are in fact the same elemenL. Together these say that I a proof by contradiction. Suppose that a1, (2,.... (n are all is satisfied by exactly onc clement. c)This statement asserts less than A, where A is thc avcrage of thcsc numbers. Then the existence of an x that makes p' true and has the further a1+a2+…+2≤nA. Dividing hoth sides hy nt shows property that whenever we find an element that makes P true, that A=(a+a2+.+an)/'nA, which is a contradic- that clcmcnt is x. In other words. t is the unique clement that lion. 41. We will show that the four statements atre etui makes p true. 17. the ion la-CI=b-c is eyuiv alent by show ing that (i)implies (ii).(ii implies(iii).(iii) alent to the disjunction of two cquations: a-c=b-cor plies(iv), and (iv)implies(i). First, assuine that n is even a-C=-b+c. The first of these is equivilent to a= b, Then n= 2h for some intcger k Then n+ I =2k.+ I, so which contradicts the assumptions made in this problem, so 7+ 1 is odd. This shows that (i)implies (ii ). Next, suppose nt to a +c By that n+ I is odd, so it +I 2k I for some integer k. adding b+c to both sides and dividing by 2, wc scc that this Then 3n 1 2n+(n + 1)= 2(n +k)+ 1. which cquation is cquivalent to c=(a +b)/2. Thus, there is

...展开详情
试读 97P 离散数学及其应用(英文版)答案
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
离散数学及其应用(英文版)答案 44积分/C币 立即下载
1/97
离散数学及其应用(英文版)答案第1页
离散数学及其应用(英文版)答案第2页
离散数学及其应用(英文版)答案第3页
离散数学及其应用(英文版)答案第4页
离散数学及其应用(英文版)答案第5页
离散数学及其应用(英文版)答案第6页
离散数学及其应用(英文版)答案第7页
离散数学及其应用(英文版)答案第8页
离散数学及其应用(英文版)答案第9页
离散数学及其应用(英文版)答案第10页
离散数学及其应用(英文版)答案第11页
离散数学及其应用(英文版)答案第12页
离散数学及其应用(英文版)答案第13页
离散数学及其应用(英文版)答案第14页
离散数学及其应用(英文版)答案第15页
离散数学及其应用(英文版)答案第16页
离散数学及其应用(英文版)答案第17页
离散数学及其应用(英文版)答案第18页
离散数学及其应用(英文版)答案第19页
离散数学及其应用(英文版)答案第20页

试读结束, 可继续阅读

44积分/C币 立即下载