Homework 10Problem 23Give formal proofs corresponding to the valid steps discussedn Problem 16, page 1031. Modus Tollens: From A B and B infer A1. A B2. B / A3. A4. B Elim 1, 35. B B Intro 4, 26. A Intro 3-52. Strengthening the Antecedent: From B C infer (A B) C1. B C / (A B) C2. A B3. B Elim 24. C Elim 1, 35. (A B) C Intro 2-43. Weakening the Consequent: From A B infer A (B C)1. A B2. A3. B Elim 1, 24. B C Intro 35. A (B C) Intro 2-44. Constructive Dilemma: From A B, A C, and B D infer C D1. A B2. A C3. B D4. A5. C Elim 2, 46. C D Intro 57. B8. D Elim 3, 79. C D Intro 810. C D Elim 1, 4-6, 7-95. Transitivity of the biconditional: From A B and B C infer A C1. A B2. B C3. A4. B Elim 1, 35. C Elim 2, 46. A C Intro 3-57. C8. B Elim 2, 79. A Elim 1, 810. C A Intro 7-911. A C Intro 3-6, 7-10Problem 24Give formal proofs of the following1. A (B A) from no premises1. A2. B3. A Reit 14. B A Intro 2-35. A (B A) Intro 1-4To prove something with no premises means that we must start off with an assumption. We work this problem by noticing that the main connective is a . Given that, we know that we can use a Intro to prove the main connective and therefore introduce the antecedent as our assumption. The second step of the proof is done by noticing that the other connective is a and can be solved in the same way. Having assumed B (the antecedent in the inside ), all we have to do is restate A to show that A follows from B. having shown that A follows from B, we have shown B A. Because we were able to get this only by assuming A, we have shown that A (B A).2. (A (B C)) ((A B) C) from no premises1. (A (B C))2. A B3. A Elim 24. B C Elim 1, 35. B Elim 26. C Elim 4, 57. (A B) C Intro 2-68. (A (B C)) ((A B) C) Intro 1-79. (A B) C10. A11. B12. A B Intro 10, 1113 C Elim 9, 1214. B C Intro 11-1315. A (B C) Intro 10-1416. ((A B) C) (A (B C)) Intro 9-1517. (A (B C)) ((A B) C) Intro 1-8, 9-16The major connective here is a biconditional, so we know that we need to use a Intro. The way a Intro works is by proving first that the left side implies the right side (by using a Intro, assuming the left side, and proving the right side) and then by proving that the right side implies the left side (by using a Intro, assuming the right side, and proving the left side). From here, it’s a pretty straightforward proof that it similar to the last one.3. C D from premises A (B C), E, (A B) (D E), and A1. A (B C)2. E3. (A B) (D E)4. A5. A6. (B C)7. A A Intro 5, 48. B C Intro 6-79. B C10. B C Reit 911. B C Elim 1, 5-8, 9-1012. C Elim 1113. B Elim 1114. A B Intro 1315. D E Elim 3, 1416. D17. D E Intro 16, 218. (D E) DeM 1719. (D E) (D E) Intro 15, 1820. D Intro 16-1921. C D Intro 12, 20There are a couple of ways of doing this proof. What I have done here is to use a Elim to prove that B C follows from A (B C). [This is because A is a premise, so we know that B C must be true.] So, line 5 is the left side of the from line 1 and I use a Elim to prove that B C follows from it (lines 6-7), and line 9 is the right side of the from line 1. Now that we’ve shown that B C (line 11), we know that C follows ( Elim). This is half of what we want in our conclusion. Now all we need to do is to get D, which I have done by using a Intro (lines 16-19). Finally, now that we have gotten C by itself (line 12) and D by itself (line 20), we know that C D (by Intro).Problem 25The book wants you to prove two equivalences, which you will be able to cite in later homework using our method of citing previous theorms. Once you know them, you can then use them in Elim (in system F and F’) and in Gen Sub (in system F’).1. Prove (P Q) (P Q)1. P Q2. ( P Q)3. P Q DeM 24. P Elim 35. Q Elim 36. Q Elim 1, 47. Q Q Intro 5, 68. P Q Intro 2-79. (P Q) (P Q) Intro 1-810. P Q11. P12. Q13. P Q Intro 11, 1214. (P Q) DeM 1315. (P Q) (P Q) Intro 10, 1416. Q Intro 12-1517. P Q Intro 11-1618. (P Q) (P Q) Intro 10-1719. (P Q) (P Q) Intro 1-9, 10-18 This is a biconditional introduction so we will need two conditional introductions, one in which we prove that the right follows from the assumption of the left and another in which we prove that the left follows from the assumption of the right. The first half is taken care of by means of a Intro. I assume the opposite of what I want to prove (P Q), prove a contradiction (Q Q), and therefore conclude P Q.The second half involves proving a conditional (P Q), so I use a conditional introduction, which involves assuming the antecedent (P) and proving the consequent (Q). I …
View Full Document
Unlocking...