离散数学及其应用（英文版）答案

PI: 1 ANS Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 Answers to oddNumbered Exercises S3 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→pdq→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 Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 S4 Answers to oddNumbered Exercise qpvqp→(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^qp→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)pqp→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, (pq)is true, then p>q is false, so p is true and q is hu(P→y)→(q→s) will be true.35. a)Pvq 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 Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 Answers to oddNumbered 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)丑xB(x)ind3x(C(x)∧B(x), where B(x)is th (Pivp2v..vPn). 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)xL(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)AH(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)AS(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)Al(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)yQ0.0,1)dQ(0,0,1) P(3)P(4)動(P(0)入P(1)AP(2)AP(3)AP(4)) o(1.0,1)v2(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)VP(3) calculus, and let the domain be rabbits. Original is =x C(x) PI: 1 ANS Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 S6 Answers to oddNumbered 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 lefthand side is always true be birds or in this case. By similar reasoning the righthand 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 Ictthand side is an, respectively. and lct the domain bc people in this class ac LIuusly true 'The same reasoning shows that the righthan 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 lcfthand sidc is falsc.The ghthand 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 lefthand 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 righthand 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 lefthand side is false (there is no x making the conditional "The student wrote a thesis."and statement true). the righthand 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 lcfthand sidc is clcarly falsc Furthcrmorc, for cvcry x, P(x)A A is false, so the righthand 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 lefthand 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 Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 Answers to oddNumbered Exercises S7 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)→(xy∷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(xx=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)=xl(lydia, x) loscd under the opcration of addition. 27. a) Truc b)Tr n彐xyL(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)3xVy3z7 vy(F(y)A(y≠x)→A(x,y)h三x(S(x) (x,y,z)b)彐xvyP(x,y)∧彐xyQ(x,y)c)三xy V(F(y) A(y. x))) 13. a)=M(Chuu, Koko) P(r,v)vV2R(r, v, z ))d)arvy (P(x y )AQ(, y)) ara 33.a)丑xyP(x,y)b)彐yxP(x.y)c3y3x(P(x, rah, Jose)d)VxM(. Ken)e)Vrf(x, Nina)f)Vx(Tx, Avi) M(x,Avi))g彐vy(y≠A→M(x,y)h)彐xvy(y≠ y)A2(r, y)) d)(vxvy P(x, y)) ray=o(. y)) e)arVvEzP(,v.)vVEyP(, 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))<VxEyP(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 Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 S8 Answers to oddNumbered 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 highpaying 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 wordprucessiny 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)As(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, wd, anddnj 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 Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 Answers to oddNumbered Exercises S9 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 mis 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+212n= @(a). We want to show P(a). Supposc, to the contrary 2(5+tn). 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+1k2=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 x1 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.彐xP(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 pvr 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 lefthand 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 lefthand side is odd even even which is again the last two clauses enables us to conclude gvg: in other dd. Similarly, if a is cven and b is odd, then the lcfthand PI: 1 ANS Rosen231 IT MHIADI7Rosenv5cIs May 13. 201 1 101: 29 S10 Answers to OddNumbered 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 nor1.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 lxy=lyxl, 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(xy))/2=(x+yx+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+(ry))/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 v0. Then x+ly=x+(y For the first of these, suppose that 3x+ 2 is rational, namely, Ifx= y, thenx+y=x+y But because y<0.y>y yual to P/ q for some integers P and q with q#0. Then we 0x+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)2x+(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=2vis 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 laCI=bc is eyuiv alent by show ing that (i)implies (ii).(ii implies(iii).(iii) alent to the disjunction of two cquations: ac=bcor plies(iv), and (iv)implies(i). First, assuine that n is even aC=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
 75.21MB
离散数学及其应用 第八版 奇数编号练习答案.pdf
20210123离散数学及其应用 第八版本科教学版答案，有需要其他版本到的还可以去华章图书官网下载 地址：http://www.hzbook.com/
 22.7MB
离散数学及其应用奇数习题答案
20150131离散数学及其应用奇数习题答案，是完整版，不是本科教学班，偶数习题没有
 222.97MB
离散数学及其应用（第8版）奇数题答案
20201010离散数学及其应用第8版答案，但是没有偶数题答案。第8版和前面几版的答案有所不同，CSDN上基本上都是前几版的答案，第8版答案网络上基本上很难找到，因此上传以满足学习需要
 190.36MB
离散数学及其应用第七版中文版加全部习题答案
20180810离散数学及其应用第七版 中文版pdf 加全部习题答案 原作者：（美）Kenneth H.Rosen 离散数学是计算机专业必学的基础课程，无论是数据结构、算法还是编译原理等都需要用到里面的知识。但大部分人往往连第一章——逻辑 ，也很难参透，其实这和书本的选择有关，拿到一本通熟易懂的书就会越看越有成就感，拿到一本写的不好的书，就永远在看第一章。本书讲解由浅入深，能把大部分人在阅读的过程中可能产生的疑问一一解析清楚，值得阅读。
 23.38MB
离散数学及其应用第七版习题答案（完全版）
20180401《计算机科学丛书：离散数学及其应用（原书第7版）》是介绍离散数学理论和方法的经典教材，已经成为采用率最高的离散数学教材，被美国众多名校用作教材，获得了极大的成功。该资源为本书全部课后习题答案。
 156.6MB
离散数学及其应用（原书第7版）教辅及答案
20180625离散数学及其应用（原书第7版）教辅及答案。。。。。。
 5.61MB
离散数学及其应用课后答案（中文版）
20180916本科教学版，离散数学及其应用课后答案（中文版），包括奇数偶数页答案全
 606KB
离散数学及其应用 答案
20130726十分有用 十分清晰便于查阅 答案十分准确
 20.96MB
离散数学及其应用答案（奇数题+偶数题）.zip
20190713计算机科学 离散数学及应用 课后题 答案
 16.69MB
离散数学及其应用第七版(本科教学版)中文版答案
20190102离散数学及其应用第七版(本科教学版)中文版答案.pdf 离散数学及其应用（原书第7版）》可作为1至2个学期的离散数学课入门教材，适用于数学、计算机科学、计算机工程、信息技术等专业的学生。
 4.24MB
离散数学及其应用（Rosen第7版）偶数题答案
20170709国外经典离散数学教材《离散数学及其应用》（Discrete Mathematics and its Applications）（第7版）偶数习题英文参考答案
 456KB
离散数学及其应用第八版偶数题答案
20210321离散数学及其应用第八版偶数题答案（英文
 10.9MB
离散数学及其应用原书第7版奇数题课后答案.pdf
20190720离散数学第七版奇数编号练习答案，高清完整版，有需要的就下载版，哈哈哈哈哈哈哈
 1.93MB
离散数学及其应用答案
20101104离散数学及其应用 傅彦 顾小丰 王庆先 刘启和 答案 高等教育出版社
 4.24MB
《离散数学及其应用》偶数题答案
20190411《离散数学及其应用》偶数题答案，此为第七版完整偶数题答案
 1.88MB
傅 彦：离散数学及其应用习题解析
20130905傅 彦：离散数学及其应用习题解析。选傅彦老师的孩纸们快下载吧。哈哈。
 6.76MB
离散数学及其应用 第七版 英语完整答案
20180831离散数学及其应用 第七版 网上的答案大多只能找到奇数的答案。这里收集了奇数与偶数的所有答案
 17.99MB
离散数学及其应用奇数题答案
20121029离散数学及其应用第六版奇数题答案，基本上与原书都对得上，还算不错，对学习离散数学的同学有帮助

下载
eoffice 9.0 微信企业号使用
eoffice 9.0 微信企业号使用

下载
炫酷的图片扇形展开特效.rar
炫酷的图片扇形展开特效.rar

下载
基于web的购物网站商城的设计与实现
基于web的购物网站商城的设计与实现

下载
标准件 零件图 轴.dwg
标准件 零件图 轴.dwg

下载
APSK调制仿真_256 apsk信号 matlab,apsk matlab
APSK调制仿真_256 apsk信号 matlab,apsk matlab

下载
邮箱探测器_smtp探测器,经典smtp探测邮箱密码批量深探助手
邮箱探测器_smtp探测器,经典smtp探测邮箱密码批量深探助手

下载
极路由 HC6361 0.9.008官方稳定固件
极路由 HC6361 0.9.008官方稳定固件

下载
csdn上传我的世界.zip
csdn上传我的世界.zip

下载
mLogcat_1_2_4_0.7z
mLogcat_1_2_4_0.7z

下载
各国创新指数数据集科研党使用.csv
各国创新指数数据集科研党使用.csv