Baixe Chapter 1. Formal Logic e outras Exercícios em PDF para Informática, somente na Docsity! Gersting Mathematical Structures for Computer Science Page 3 CHAPTER 1: Formal Logic Chapter 1 is an introduction to formal logic and some of its implications for computer science. Formal logic is nothing more than a systematization of much of what we do daily when we communicate in natural language and when we draw conclusions using informal reasoning. It is certainly the basis for scientific thinking and reasoning. Because ofits formalization, many students seem to find logic a difficult topic. You can point out to the students, however, that this very formality actually relieves them of the burden of undirected creative thinking! There are certain patterns and rules that must be followed in constructing formal proofs, which serve to channel and limit the possible steps to be taken at any time. Students face similar constraints in following the rules of syntax of a programming language; in fact, they are so much more constrained in formal logic that their task is even simpler than in programming. Pointing this out to the students (who have usually experienced some success in programming tasks by this time) can serve as a morale-builder. Or you can also note the similarities to standard high school geometry, but you are on less firm ground here because some students hated their bigh school geometry class! At any rate, they need some reassurance that symbolism itself is not all that formidable and, by its constraining nature, is actually helpful. T usuaily point out that one of the purposes of symbolism is to strip away meaning in order to concentrate on form alone, and thus help ensure that we are “pure in heart" in our thinking processes. Students find this a bemusing idea, but they generally see the point. Of course, natural language statements must first be translated into symbolic form, and it is this part of the chapter that is most fun to teach. It points up how sloppy we tend to be in our natural language statements. (See "John loves only Mary," “John only loves Mary," and "Only John loves Mary" in Section 1.3.) One would think that students for whom English is a second language would have more difficulties than native English speakers with this type of translation exercise, but that doesn't seem to be the case - they all have to work at this, but they also enjoy it. Students often come back later and tell me that after this course, they never take words and sentences at face value again! Propositional logic is covered is Sections 1.1 and 1.2, while predicate logic is discussed in Sections 1.3 and 1.4. Sections 1.5 and 1.6 give some direct applications of formal systems to computer science; Section 1.5 is a brief introduction to logic programming and Section 1.6 introduces proof of correctness. The discrete structures course is too often seen as a collection of disjointed topics, so it behooves us as instructors to emphasize the connecting threads whenever possible. The notations of formal logic will be used throughout the book to clarify definitions. Logical reasoning, although not always formal, is the basis for much of the rest of the work in this course and will also stand the students in good stead in many other computer science courses. Page 4 Mathematical Structures for Computer Science Gersting Answers that are starred also appear at the back of the textbook. EXERCISES 1.1 *L (a, (0) (O O 2. a. 3. a. *4 a TbT eceTdF TbF cFdFeTfFgThT antecedent: sufficient water consequent: healthy plant growth antecedent: further technological advances consequent: increased availability of information antecedent: errors will be introduced consequent: there is a modification of the program antecedent: fuel savings conseguent: good insulation or storm windows throughout land3 b2 c4 - The food is good but the service is poor. The food is poor and so is the service. Either the food is poor or the service is poor, but the price is low. Either the food is good or the service is excellent. The price is high but either the food is poor or the service is poor. Either the processor is slow or the printer is fast. The processor is slow and the printer is fast. The processor is fast but so is the printer. Either the processor is slow or the printer is fast, but the file is not damaged. The file is not damaged, the processor is fast, and the printer is not stow. The printer is slow and the file is not damaged. AnB ANn(BvC) B>(ANC) AS(B'vC) ANO 5 (B'vC)] BAD AND D5(BvcC) B'AAÃ D5€ Page 7 Mathematical Structures for Computer Science Gersting h. ALB|IB|IAvB|AABI(AABJYI(AVBjA(AABY nRmE mhHHm E Em HERE mem eme FGRmEm BICIAvBICI(AVB)AC| AJA vVCIMAvB)AC]->AvC Run HHE Fim EmA EE REM RRARRREm Emmett RERmEERm AHHRHHHHR RARA FARA RAR- Em eae E Rx fm Ea fa E E Eu Page ARE RE Rm Es a a E e e e RARHHEE mm HERE E E pu E fu E pu E fu Eneas ER E Em EEE E i BRR EE iu 2a. AIBICIAVBI(AvVB)vCIBvVCIAvV(BvCI(AVB)vCe Av(BvC) EEE A pa Em bs a 2b. ABICIAABI(AABJACIBAC|AA(BAC)(ANAB)ACO AN(BAC) EE E ia pu Em Gersting Av(BAC) O BICIBAC|Av(BAC)AvBIAvVC(AvBJA(AvC)] (AVBJA(AVC) Mathematical Structures for Computer Science Page 8 3a. RRRRRHRE RRREREEE ANnBvC) & RARE AR RR RE Eu RARE E E ps ES pa Es Ea a fm RRRREHEA REmmE me 3b. ALBICIBVCIAN(BvC)]) AAB|AACI(ANB)v(ANC)(AAB)V(AAC) o RR E mm Renernmemo < = ten < o <| 2 BEER Pre aE FRrRhahhHba GS < <| Em 2Hm d Erhtrtaem Erbabata o < - RERRERo HhnaHheme Satã Suh FRHEEmE E PRrrRbreanao de <dhHy q & 5b. Ay 42 A T T m a 4 > HER JanHh € ? . < «| Ser am Dr a demente > < < dum graca greE-m dtem dhrmm SEHmm = Ê q E Gersting Mathematical Structures for Computer Science Page 9 e AIB AvBI(AvBJHAI|B|AABI(AvBy 6 A'AB! T|IT T F F|F F T T|F T F FiT| F T FIT T F TI|F F T F|/F F T T|T T T £ A|BIAABI(ANBJUHAIBIA vBI(ANBJS O A! vB'! T|IT| T F F|F F T T|F| F T F|T T T F|T| F T T|F T T F|F| F T TT] T T p- o > < - ed B. A v «e TIT T T F F T 18.a (ANB)ACO ANBAC SO AN(CABSO(ANC)AB' b(AvBA(AVB) SO AvVBAB SG AvOS A cAv(BAA OS (AVBA(AVA)O(AvVBAILO AvB d(ANBYvBe(AvBNvBO (AvBvB OA v(BvB) SO A'vB ec AnN(ANBY GS AN(A vB) S AN(A vB) OS (ANA)v(ANB) SOv(ANBS(ANB)vVOS ANB *19. dogs AND NOT retrievers 20. “oil paintings” AND (VanGogh OR REMBRANDT) AND NOT Vermeer 21. (novels OR plays) AND AIDS 22.1.0,2.4,72,53 23. For example: (A OR B) AND NOT (A AND B) AND NOT C 24. The conditional expression has the form (A v BJ v (A'A B). (Av Bv (A ABS (A AB) v (A A B) (De Morgan's Laws) e AA (B'v B) (tautology 3b) SA A (Bv B) (tautology la) o An (tautology Sa) o A (tautology 4b) Therefore the statement form can be written as if not(Value! < Value?) then statement] else statement? end if Page 12 Mathematical Structures for Computer Science Gersting b. AA Bis equivalentto (A > B' ALBIAABBIA >B'I(A >BY|AA BO(A > BY TIT| TIF| F T T TIF| FiT) T F T FIT] FI|T| T F T F|F| FI|T| T F T v B is equivalentto A'>B AvB/AA>SBIAVBO A SB F T nmanspo> mom rs ty mad “3 F T T T T F 31. (AA B) has the value F when A and B have the valuês T. However, any statement using only — and v will have the value T when A and B are both T. *32.A AB is equivalent to (A|B)(AI|B) ALBIAAB| AÍB| (AIBJ(A|B) | AA B <> (ABJ(AIB) TIT| T F T T T/F| F T F T F|T| F T F T FIF| F T F T A'is equivalent to AJA ALA] AAJA e> AJA T|F F T Flirt TI T 33.44 Bis equivalentto (AV A)Ú(B LB) AIBIA ABJAJAIBYBI(AVA) L(BLB)] ANABO(ALAS(BYB) TT T/F | F T T T|F F F T F T FIT| F TI|F F T FI|F F T T F T A'is equivalent to A ) A ALA ALAJA O ALA T|F F T FIT T T 34. a. In order for A À B to be true, we would want to know that both parts are true; if one part has an unknown truth value then it is unknown whether this is the case. In order for A v B to be true, we would want at least one part to be true; if one part is false and the other part has an unknown truth value, then it is unknown whether this is the case. Finally, if the truth value of A is unknown, then the truth value of A! is also unknown. Gersting Mathematical Structures for Computer Science Page 13 b. EJAN=TAN=N c. NAF=F d (N'v(FJ=NvT=T 35. a. HA hasa truth valucofx O <x<, then A'is the "opposite condition" and will have the truth valve that represents everything A is not, namely 1 -x. For A AB, both conditions must hold, which means the lower of the two truth values is all that can be achieved. For A v B, either condition can hold, so the higher of the two truth values can be achieved. b. 1-0,12=0.88 *c. min(0.12, 093) = 0.12 d. max(0.12, 1 - 0.84) = max(0.12, 0.16) = 0.16 36. Machine D is either clean or infected. In either case, by statements 3 and 1, respectively, C is infected. Because C is infected, then A is infected by statement 2. By statement 4, B is infected (since C is not clean). By statement 3, because B is infected, D is not clean. The conclusion is that all four machines are infected. *37. HW Percival is a liar, then his statement is false. Therefore it is false that there is at least one liar, and both Percival and Llewellyn must be truth-teilers. But this is impossible since we assumed Percival is a liar. Therefore Percival is a truth-teller, and his statement is true. Because he said, "At least one of us is a liar," Llewellyn must be a liar. Therefore Percival is a truth-teller and Llewellyn is a liar. 38. Merlyn's statement is of the form A -> B, where A stands for "E am a truth-teller" and B stands for "Meredith is a truth-teller.” If Merlyn is a liar then statement A is false; therefore statement A — B is true, but Merlyn, as a liar, would not have said a true statement. Therefore Merlyn must be a truth-teller. Then the statement he makes, A > B, must be true, and statement A is true as well. Therefore statement B must be true, and Meredith is a truth-teller. So both Merlyn and Meredith are truth-tellers. 39. Rothwold's statement is of the form A v B, where A stands for “I am a liar" and B stands for "Grymlin is a truth-teller." If Rothwold is a liar, then his statement A v B is faise, and the statement (A v BJ must be true. By De Morgan's laws, A' and B' must both be true. But Á' is the statement that Rothwold is a truth-teller, which is not true. Therefore Rothwold must be a truth-teller, and his statement A v Bistrue. Statement A, however, is false because it says that Rothwold is a liar. So statement B must be true, and Grymlin is a truth-teiler. Both are truth-tellers. EXERCISES 1.2 1. MSBAFSM «mt 2. (B>A)JABSA -mp 3. SALSL -sim 4. (SS5RBARSDB)S(S->B)-hs Page 14 Mathematical Structures for Computer Science Gersting 5. 6. *7. *10. 1. 12. *13, The hypotheses have the form (C — P) A P'. By mt, the conclusion is C', the car was not involved in the hit-and-run. The hypotheses have the form (W v L) A (W > F). No conclusion can be made (note that W v L does not mean that you have W). The hypotheses have the form (B > P) AP. Only P, you will be paid tomorrow, can be concluded, using simplification. (B cannot be concluded.) The hypotheses have the form GA TA (G >R). By mp, the conclusion is R, we need to rake the leaves. 1 A hyp 2. B5C€C hyp 3. B hyp (deduction method) 4. € 2,3, mp 5. ANAC 1,4, con 1 As(BvC) hyp 2. B' hyp 3 € hyp 4. BAC 2,3, con 5. (BvC)y 4, De Morgan 6 A 1,5, mt 1 A hyp 2. B hyp 3. B5(AvC) hyp 4. AvC 2,3,mp 5. (A) vc 4, dn 6. A'-5C 5, imp 7. € 1,6, mp ANBS5ASB' 1 A hyp 2. B5A hyp. 3. B 1,2, mt ASBATAS(BS0]5(A>0) 1 ASB hyp 2 AS(BS50) hyp 3. À hyp 4. B 1,3, mp 5 B5C 2,3, mp 6. € 4,5, mp Gersting 427. PAP S5Q 1. P hyp 2 P hyp 3. PvQ 1, add 4 QvP 3, comm 5. (Q)vP 4, dn 6 Q>5P 5, imp 7. (Q9 2,6, mt 8. Q 7, dn 28. PA(QVR)S(PAQ)v (PAR) 29. Rewriting the conclusion, the argument is PA(QVR) S(PAQV PAR) or PA(QVRSIPAQS PAR] 1 P hyp 2. QvR hyp 3. (PAQ) hyp 4 PvQ 3, De Morgan 5. QvP 4, comm 6. 95P 5, imp 7. PY 1, dn 8 q 6,7, mt 9. RvQ 2, comm 10. (R)'vQ 9, dn ILR'SQ 10, imp 12. (R) 8, 1, mt 13.R 12, dn 14.PAR 1, 13, con Pv(QAR)5 (PvOAn(PvR) Prove Pv(OAR)S>(PvQ) Rewriting the conclusion, the argument is Pv(QAR)5((P)vQ) bydn or Pv(OQAR) 5 (PS Q) by imp 1 Pv(QAR) hyp 2. P hyp 3. (PYv(QAR)L dn 4. PS(QAR) 3, imp 5. QAR 2,4, mp 6. Q 5, sim Mathematical Structures for Computer Science by dn by imp The prooffor PV(QAR)S (Pv R) is similar. Page 17 Page 18 Mathematical Structures for Computer Science 30. 32. 33. 34. 35. AS (A SB) LA hyp 2. A hyp 3. B 1,2, inc *31, POE P>Q hyp z P5Q hyp 3. Q5SP 1, cont 4 050 2,3,hs 5. (0) vQ imp 6. 0vQ 5, dn 7. Q 6, self (ASB)A(AS CO) 5(B5€) 1 ASB hyp 2. A3C hyp 3. B hyp 4 B5A. 1, cont 5. c 2,4,hs (ASBABSCA(CSDS(A SD) 1 ASB hyp 2 B5C€C hyp 3. C5D hyp 4 ASC 12,hs 5. ASD 3,4,hs (AVBA(ASCABS5C)5C 1 AvB hyp 2. ASC hyp 3. BoC hyp 4. (AyYvB 1, dn 5 ASB 4, imp 6. A'-4€ 3,5,hs T (ASON(A 50) 2,5, con 8. € Exercise 31 VoDAXS NDA SRS WIAVSDSV SW) 1. YoZ hyp 2 Y52Z hyp 3. Y hyp 4 2 1,3,mp 5. Z 2,3,mp 6 wW 4,5, inc Sersting Gersting 136. (ANBYA(CAAJA(CAB) 5 A! 37. 38. 1. (ANBY (CAAy (CABY AvB' B'vA B5 A (Cv A CSA 9, C'v(BY 10. (B)'v €C' NB SC 12.B' 5 A SA mm Ao. 13. B5AA BS A) 14, A! Mathematical Structures for Computer Science hyp hyp hyp 1, De Morgan 4, comm 5, imp 2, De Morgan 7, imp 3, De Morgan 1, comm 10, imp 8,11,hs 6, 12, con Exercise 31 POA RAE TS) Pv(QAR) R'vS Ss5T T mM) g SvR' (S) vR' SR 10.R' ILR'IVQ 12. Q'vR' 13. (QAR) 14. (QAR)vP 15.P sannA tp o) hyp hyp hyp hyp 4, dn 3,5, mt 2, comm 7, dn 8. imp 6,9, mp 10, add 11, comm 12, De Morgan 1, comm 13, 14, ds The argument is (E > Q)A (EvB)AQ'5B A proof sequence is: 1 E50Q EvB q QS5E E (E9' vB ESB B LAMA A hyp hyp hyp cont 3,4, mp 2, dn 6, imp 5,7,mp Page 19 Page 22 46. Let Mathematical Structures for Computer Science I=my client is innocent K = the knife was in the drawer J = Jason Pritchard saw the knife O = the knife was there on October 10 H= the hammer was in the ban Then the argument is ESKAKVDAOSNDAOS KAB)AH]SI A proof sequence is: 1. 15X 2 KvJ 3 057 4. 05(KAH sH 6. HvkK 7 (AX) 8 KAH) 9 4. K5 07 15.1) 16.1 EXERCISES 1.3 laTbrFcFdoT 2.*a. true (picky=0) *b. true (picky=0) *c. true (picky=-x) hyp hyp hyp hyp hyp 5, add 6, De Morgan 7, comm 4, cont 8,9, mp 3, 10, mp 2, comm n,12, ds 1, cont 13,14, mp 15, dn *d. false (no one y works for all x's) . false (may have x=y) true (pick y =-x) e f g. true (pickx=2,y=4) h. false (may havex=0) 3. aF bT cT dF eT 4.%a. true: domain is the integers, A(x) is "x is even", B(x) is "x is odd” false: domain is the positive integers, A(x) is "x > 0", BO) is "x 21" Gersting Sersting Mathematical Structures for Computer Science Page 23 b. c. pocos true: domain is the collection of lines in the plane, P(x, y) is "x is paralleito y" false: domain is the integers, P(x, y) is "x <y" true: domain is the integers, P(x) is "x is even", Q(x, y) is “y)x" (y divides x) false: domain is the collection of all people, P(x) is "x is male", Q(x, y) is "y is a brother of x" true: domain is the nonnegative integers, A(x) is "x is even", B(x, y)is "x <y” false: domain is the positive integers, A(x) is "x is even", B(x, y)is "x <y” true: domain is the integers, A(x) is 'x > 0", B(x) is "x > 0" false: domain is the integers, A(x) is "x > 0", B(x) is "x is even" scope of (Vx) is P(x) > Q(y); y is a free variable scope of (Ix) is A(x) A (Vy)BG); scope of (Vy) is B(y); no free variables scope of (x) is (Vy)P(x, y) A Q(x, y); scope of (Vy) is P(x, y); y is a free variable scope of (3x) is (Iy)[A(x, y) A B(y, 2) —> A(a, z)]; scope of (dy) is A(x, y) A B(y, z) > A(a, z); Z is a free variable Some parts of Exercises 6-9 have muitiple equivalent answers. 6.*a. *b. te. a ="2mmo FrwWmns acc» so se o 9. a. *b. x 8 WADE) > S69) GDE) A RO] or [VADE > R69)T (CDE) A SG) > (RG9)T (O) IDGO A Sh) A R(g)] (Mo)LD() > (S(x) A RG) or (VOID) A S6Gx) A RGD] (CODE) A Sh) > DECO A R69] CDE) — (SG9))] SM) > (Va(DO) > SE) R(M) A R(T) GDE) A RED) > (Vo)(DO) —> SG) CABE) —> R6)) [C(BE) > SC or BE) A [SCOM (SG) > RED) (BE) A RO] GBE) A RG) A (VASO) > [RG] VaXBCO) A RG) — S(x)) (VxXB(x) A RQ) — S(x)) - this is the same statement as (f) CASCO) > RED) —> (BO) > Ré) COPE) A (VT) > Fx, y)) CP) —> (EyXTG) A Fls, y)) [OCIXKPG) A TO) > Fx, 9) or G)CIVAPE) A TO) A (Ft, 93) or (Va (PE) > (VyTO) > Fls, y)I GW E) A LE) À CO) COLWE) — (LO) À CG] - COLE) A (VIXAG, 9) > HT or CV ILES) À (AG, 9) > T(9)] Page 24 d. 1. 12. f 14.*a. Mathematical Structures for Computer Science Gersting CO) > (VyXAG, 3) > IO) or MIO) > (AG, 9) —> TI) or VIC) A As, y) > T(9)] CENTO) A AG, 9) — TO] (VLW) À LO] > Gy) A AG, y)D or COGYAWOS) 2 LOM] > [Hy) A AGs, y)) COWE) n (YyILG) — (AC, 9))D or GWE) A (VT AG, 3) —> (Ly) or GW PWE n IL) > (AG, 9))D CO(CE A Fls) (GHPGSO) A (VyXSOS, 7) —> FG] or CY yIPG) A (SG, y) > FG) Cy XIP() A SEs, 9)] > Cl) CO LEGO) —> EyXC() A S(x, 99) or (VaANIFOS) — (C() n SG, 9)] or, if there is some one Corvette, ()[C(x) A (VI XE) > S(y, x)] EPE) A (IL) > (SE, y))D or EN VIXPE) À LEG) — (S(x, TD GENTE) A FO) A Sax, 9) > (VaVINCO) A Fly) — St, y)) (IBC) > (Vy)FO) —> Les, 9] or (XV ITBG) A FG) > Les, 9)] GIBC) A (VIPO) > LG, 9) CTBC) —> (yXEG) A Le, y))] COBG) —> (VIXCLE, 9) > F())] CLEO) > WLE, y) > BE] or (VyVOE() A LE, y)) > BO] (o BE) —> (VyXLOs, y) —> F(y))] ISIIBE) A (VILLE, y) > FOI or (VIBE) > ELE, 9) 4 (FO)I GIBG) A GyXEG) À LX, 9)] or IBC) A F(y) A Le, 9)] CO IBES) A (Vy)(LG, 3) —> F(y)] CoIBCO) > Gy(FO) AíLE, y))] COBC) —> (VyXFO) > (Le, 9)))] or (Va Y PIB) A E) —> (Lex, y))] [GB A VE > Le, 9) or VIBE) > (yXFG) A LE, 9))] Co) (SC) —> Lt) CGho(ME) A ISGIT) (COLO) > MG) Gxo(SC) À MG) CaVY) (SO) A M(y) — Blx, 7) G(MES À (VYXS6) > Bés, 9)) COC9M) À Bs, y) —> SEM) . John is handsome and Kathy loves John all men are handsome all women love only handsome men a handsome man loves Kathy some pretty woman loves only handsome men John loves all pretty women 2 b3 c3 di Gersting Mathematical Structures for Computer Science Page 27 b. To getto step 2, ei was performed on two different existential quantifiers, neither of which was in front with the whole rest of the wff as its scope. Also, both existential quantifiers were removed at once, with the same constant a substituted for the variable in each case; this should be done in two steps, and the second would then have to introduce a new constant not previously used in the proof. And at step 3, the existential quantifier was not inserted at the front of the wff. a. domain is the integers, Ox, y)is "x <y"; for every y thereis an x withx<y but there is no single integer x that is less than every integer y. b. The use of universal generalization at step 4 is illegal because step 3 was deduced by ei from (3x)Q(x, y) in which y is a free variable. *10. (Vo) PG) > (VOTP() v QI] q. 12. 13. 14. 1. (VoP6) hyp 2. P(x) ) ui 3. P(x) v Q(x) 2, add 4. (Wa(P(x)v Q(x) 3,ug (note that P(x) v Q(x) was deduced from (Vx)P(x) in which x is not free (onto) A EQC) > EoIPÇO) A QE] (a)PGo) hyp 2 EO) hyp 3. Q(a) 2, ei 4. P(a) 1, ui 5. P(a)A (a) 3,4, con 6 OPCAO) Seg GEP, 9) > ENE, y) 1 GOEPk, y) hyp 2. (Gy)P(a, y) 1, ei 3. P(a,b) 2ei 4. (Ox)P(x b) 3,eg 5 GEP) Seg CPO, 9) > (CRE, 9) 1 Voy) hyp 2. (VyO(x, y) 1, ui 3. Q(x,y) 2, ui 4. (VOO, y) 3, ug (x not free in (Vx)(Vy)Q(x, y)) 5. (WyXVMOCY) | 4, ug (y not free in (Vx(V9)QK, 7) (PQ À (Ix)[POI] —> (x)QK) 1 (VOPG) hyp 2 Goo] hyp 3. [P( 2 é 4. P(a) Lui 5. Q(a) 3,4, inc 6. (O)0K) 5,eg Page 28 Mathematical Structures for Computer Science Gersting *15. (0) AG) A BG9)] > (IAGO) A (Ex)B(x) 16. 17. 18. +19. 20. 21. - GxXAC) A BO) A(a) A B(a) A(a) B(a) GI) A(x) (GOB) Dm dan mo a hyp lei 2, sim 2, sim 3,eg 4,eg (DoA(x) A (Gx)BG) 5,6, con Using an equivalence to rewrite the conclusion, we want to prove GRC) v SO) > GARE) ) > GS] 1 (GRC) v 869) R(a) v S(a) (GRC) (ARO) Re) S(a) Gas) Am A w mr hyp 1,ei hyp 3, neg 4, ut 2,5, ds 6,eg COPO) > Q6)] + HP6) > (VOQCI] 1 (IPG) > QCO] 2. (Vx)P(x) 3. P(x) > Q(x) 4. P(x) 5. Mx) 6. (OG) byp hyp 1, ui 2,ui 3,4, mp 5, ug [PE) > (WO)QC)] > (VoPG) — QCI] Domain is the integers, P(x) is "x < 3" and Q(x) is "x < 2." (The left side is true because (Vx)P(x) is false, but the right side is false.) ENE, 9) > (Vi, y) 1 GWV9OE, y) (Yy)Q(a, y) Qa, y) 4. WA, y) 5. Cy, y) +» hyp 1,ei 2, ui 3,eg 4, ug CPG) v E)O6) > (VolP(s) v Q(] Domain is the integers, P(x) is "x < 5" and Q(x) is “x is even." (CV aLAGO) > BO] > [E)AGo) > (9)BC)] 1. AG) > BC) hyp 2. ()AG) hyp 3. A(a) 2,ei 4. A(a) > B(a) 1, ui 5. B(a) 3,4, mp 6. (GwB(x) 5,eg Gersting Mathematical Structures for Computer Science Page 29 22. (Vy QE, 3) > PC] —> [ENOE, 3) > PED] 1 (VyXQE, y) > PO) hyp 2. Ey)Ok, y) byp 3. O(x,a) 2, ei 4. 06x a) > P6x) 1, uí 5. P(x) 3,4, mp +23. (P(x) > y)K, 9)) > Cy PG) —> Q(x, y)] - PG) > 906) byp ta 2. P(x) temporary hyp 3. GyQk,y) 1,2,mp 4. Q(x, a) 3, ei 5. Px) > Q(x, à) temporary hyp discharged 6. EyPC) > QE, y)) 5, eg 24. Go) [PG —> QE A (VITQO) > R6)] A (OPG) —> Gy)RGO) 1 GPS 6] by 2. VOO) > R(y] hyp 3. (VoPlo) hyp 4. P(a)> Q(a) 1,ei 5. P(a) 3, uí 6. (a) 4,5, mp 7. Ya) > R(a) 2, ui 8. R(a) 6,7, mp 2. ORG) 8,eg 25. a (VxXM6) > PODA (Va(S6) > MG) > (Vo(SC) > Ps) A proof sequence is: + (AME) > PO) byp 2. (VS) > MG) byp 3. M(x) 5 P(x) 1, ui 4. SG) > MG) 2, ui 5. S(x) > Px) 3,4hs 6. (VxXS(x) —> P(x)) 5, ug db. COME > POD A VaXSG) > MG) > (VASCO) — [PG 1. (Vo)(MGO => [PGOT) hyp 2 (Vx(S(x) > MG) hyp 3. M(x) > [P(o)]' 1, ui 4. 809) > MG) 2, ui 5. S(x) > [PGO] 3,4,hs 6. (VxXSCO > [PO] 5, ug Page 32 Mathematical Structures for Computer Science Gersting 30. The argument is: CGhMES) A CR, 9) A (Va) lVIARE, 7) > Tx, 9) > (EMO A (Yy)TGs, 9)) 31. 32. A proof sequence is: 1 GxX(ME) A (Vy)RG, y) hyp 2. M(a) A (Vy)R(a, y) lei 3. M(a) . 2, sim 4. (CHAVIXREE, y) > T(x, y)) hyp 5. (Vy(R(a, y) > T(g, y)) 4, uí 6. (R(a, y) > T(a, y)) 5, uí 7. (VyR(a y) 2, sim 8. R(a,y) 7, ui 9. T(a, y) 6,8, mp 10. (Vy)T(a, y) 8, ug 11, M(a) A (Vy)T(a, y) 3,9, con 12. GM) A (VyTE, 9) — 10,eg The argument is: CCO) > Ey)W O, 9) A (VW, 3) > Sl, y)) A Cm) > (y)Sm. y) A proof sequence is: 0. CCO) > Gy)Ws, y) - hyp Cm) 5 (Oy)W(m, y) 1, ui C(m) : byp GEy)W(m, y) 2,3,mp CX VINAWE, y) > S(x, y)) hyp CyXWím, y) > S(m,y) 5, ui Wím, a) 4,ei Wí(m, a) > S(m, a) 6, ui S(m, a) 7,8, mp (y)S(m, y) 9, eg The argument is: COL VIUAÇ) À Sex, 9) > DO) A CEYNACO A SCx, y)) — (DG) A proof sequence is: 1. ao ma sw VAXVIAÇO) A SC, 9) > D(y)) hyp GOEXAÇO) A SG, y)) hyp (GyXA(a) A S(a, y)) 2,ei A(a) A S(a, b) 3,ei (VyXCA(a) À S(a, y)) > D(y)) 1, ui (A(a) AS(a, b)) > D(b) 5, uí D(b) 4,6, mp (3x)D(x) 7,eg Gersting Mathematical Structures for Computer Science 33. [GP é (VolPÇ) [EIPETT & (VOPC) [PO O (EP)! neg, using [P(x)]' for A(x) dn cont (each direction) [CPO] ++ EPPGT dn 34 a 3 b 5 c 2(anevenprimenumber) d 2 ((1)2=1) e. 11 (211. 1=2047=23*89) EXERCISES 1.5 1. no 2. yes *3. fish 4. rabbit 5. fox deer 6. fish little-fish fish raccoon fox deer deer *7. herbivore(x) H eax, y) and planty) 8. little-fish rabbit deer 9. a Anita b. Mike Kim e. Judith Sam Mike Kim Joan Hamal Enrique Jefferson 10. For example, capitolnorth-dakota, bismark) capitol(california, sacramento) capitol(hawaii, honolulu) capitoKpennsylvania, harrisburg) Page 33 Page 34 Mathematical Structures for Computer Science *11. 12. 33. capitoKflorida, tallahassee) capitoKnew-york, albany) big(sacramento) big(honolulu) big(albany) smalibismark) smali(harrisburg) smali(tallahassee) eastern(pennsylvania) eastern(florida) eastern(new-york) western(north-dakota) western(california) western(hawaii) a. which(x: smailx)) b. which(x: capitoi(x, y) and smaii(y)) c. which(x: eastern(x) and capitoi(x, y) and big(y)) d. cosmopolitan(x) if big(x) and capitoKy, x) and western(y) e. which(x: cosmopolitan(x)) . is(author-of(mark-twain, hound-of-the-baskervilles)) . which(x: author-offaulkner, x)) nonfiction-author(x) if author-oflx, y) and not(fiction(y)) . which(x: nonfiction-author(x)) asca Jfather-ofx, y) if parent-ofx, y) and male(x) . daughter-oflx, y) if parent-ofly, x) and female(x) es *c. ancestor-oflx, y) if parent-oflx, y) ancestor-ofx, y) if parent-ofx, z) and ancestor-oflz, y) a. which(x: smalkx) and part-ofx, y)) b. which(y: small(x) and part-oflx, y) and big(y)) c. component-ofx, y) if part-ofx, y) component-ofx, y) if part-ofx, z) and component-ofz, y) EXERCISES 1.6 * x+tl=y-lorx=y-2 2. 2x>y,orx>y/2 Gersting