Solutions to, comments on, and
a marking scheme for, Assignment 4

Problem 1 (11 marks): |- P --> (Q --> R) --> (P --> Q) --> (P --> R). Proof: Marks (1) P --> (Q --> R) (Call this wff A.) < ass > 1 (2) P --> Q (Call this wff B.) < hyp > 1 (3) P < ass > 1 .5, .5, (4) Q --> R < (3), (1), M.P. > 1 (5) Q < (3), (2), M.P. > .5, .5 (6) R < (5), (4), M.P. > .5, .5 So, {A, B} U {P} |-- R, 1 so, by the D.T., {A} U {B} = {A, B} |-- P --> R. 1 So, by the D.T., {A} |-- B --> (P --> R). 1 So, by the D.T., |-- A --> (B --> (P --> R)). // 1 Grader: I warned the students against saying "By the D.T., blah blah" at the BEGINNING of the proof. The place to say that is at the END, when one has done the necessary provings. I guess it's possible also to put sentences instead at the BEGINNING with phrases like "It's enough to show that blah blah, by the D.T." But the instructions call for exactly three sentences at the END of the proof. Decide on mark deductios to make, for people who ignore the instructions. "ass(umption}" and "hyp(othesis)" are both fine as the annotation for each of the first three lines. The assumptions can be made in any order in lines 1 through 3. Lines 4 and 5 can be reversed. Whichever one the student writes first, give .5 each for mentioning each of the two line numbers and 1 for mentioning M.P. Later, in lines 5 and 6, give .5 for the line numbers total and .5 for M.P., i.e., 1 mark for line 5 and 1 mark for line 6. Then 4 marks for the English sentences at the end. According to the instructions in the problem, there must be exactly three English sentences; I would think that each one contains one invocation of the D.T. But maybe give 2 marks for the first of those three sentences. Decide yourself how to allot these 4 marks, and write down a marking scheme for me to accompany the group lists. Maybe the part of the first of the three sentences above which comes before the second "so" can be omitted. But still give 2 marks for the resulting shorter first sentence. Problem 2 (7 marks total): Bullet-prove that |- (P /\ Q) --> (P \/ Q). You may NOT use the Deduction Theorem in your proof. This is a ridiculously short proof. P /\ Q --> P \/ Q Marks <==> < 2.4.11 > 1 ¬(P /\ Q) \/ (P \/ Q) <==> < 2.4.18' > 1 ¬P \/ ¬Q \/ P \/ Q 4 altogether: 1 each for turnstiles <==> < |-- ax. 9! |-- top! > 1 for ax. 9, 1 for "top" (huge "T" in handwriting) or "2.1.12" (¬P \/ P) \/ top -- 2.4.7! 1 Problem 3: Now prove again the same theorem as in Problem 2, but this time you must use the Deduction Theorem. Begin with a sentence of the form "Assume _____________" (where you fill in the blank with the appropriate wff). Then give a bullet proof of P \/ Q (exactly one of your steps should use the symbol <===> (talked about in Γ a file posted on the course page a long time ago, and mentioned in class as well), where Γ is the set consisting of the wff you filled in the blank with above -- be sure to say explicitly what the set Γ is, in your proof). In addition to all the theorems on our usual class list, you may use in this problem, as annotation for a step in your bullet proof, any metatheorems proven in class up through the end of class on 5 March. That includes what we called "merging" and "splitting". Assume P /\ Q. Let Γ = {P /\ Q}. Then (Proof number 1) P \/ Q <==> < Γ |-- Q by splitting, and Γ Γ |-- top > P \/ top -- 2.4.7! But this last wff is a real theorem, hence a Γ-theorem, so by Equanimity Γ |-- P \/ Q. So |-- (P /\ Q) --> (P \/ Q), by the D.T. // (Proof number 2 -- a bit less smart) P \/ Q <==> < ax. 10 -- the rule that is golden > P /\ Q == P == Q <==> < Γ |-- P /\ Q! $Gamma; |-- top! > Γ top == P == Q <==> < 2.1.21 > P == Q. But Γ |-- P and Γ |-- Q, by splitting, twice. So Γ |-- P == Q (any two Γ-theorems are Γ-equivalent). So (by Equanimity and Trans), Γ |-- P \/ Q. So |-- (P /\ Q) --> (P \/ Q), by the D.T. // Problem 4: Bullet-prove that |- (P == Q) == ( (P /\ Q) \/ (¬P /\ ¬Q) ). I am not sure which way is easiest here. Here is one way: (P /\ Q) \/ (¬P /\ ¬Q) <==> < 2.4.23(i) > (P /\ Q) \/ ¬P /\ (P /\ Q) \/ ¬Q <==> < 2.4.23(i) twice more > (P \/ ¬P) /\ (Q \/ ¬P) /\ (P \/ ¬Q) /\ (Q \/ ¬Q) <==> < |-- ax. 9! (twice); |-- top! (twice) > top /\ (Q \/ ¬P) /\ (P \/ ¬Q) /\ top <==> < 2.4.20 twice > (Q \/ ¬P) /\ (P \/ ¬Q) <==> < 2.4.11 twice, then 2.4.26 > P == Q. // Problem 5 (10 marks): Do Exercise 20 on page 87 of our text. Note that the wff there is really (A --> C) --> ((B-->C) --> ((A \/ B) --> C)). For credit on this problem you must give a Hilbert proof. I think it should have exactly five lines in it, and I suggest using theorem scheme 2.4.24 somewhere in it. The proof I have in mind also has an English sentence or two at its end. (1) A --> C < ass > 1 (2) B --> C < ass > 1 (3) (A -> C) /\ (B -> C) < (1), (2), 1 merging > 1 Call the above wff D. (4) D == (A \/ B) --> C < 2.4.24 > 1 (5) (A \/ B) --> C < (3), (4), 1 Eqn > 1 (or, "Equanimity", in that last annotation) So {wff (1)} U {wff (2)} |-- wff (5), 1 so (1) |-- (2) --> (5), by the D.T. 1 So |-- (1) --> ((2) --> (5)), by the D.T. 1