Assignment 4

(I will post another file with 2-3 more problems for Assignment 4, within hours of posting this one. At least with this one you can get started.) This is due in class between 6:50 and 7 p.m. on 19 March. Same rules as for Assignment 2 (look at the Asst. 2 file linked on the course page to remind yourself of those rules.) There are other instructions below. People lost lots of marks on earlier assignments and on Test 1 by ignoring instructions. It's easy enough to lose marks without doing it this way. In bullet proofs on this assignment, you may use any theorems on the axiom/theorem sheet we have been using in class for a long time now (theorems up through 2.4.26). Problem 1: Give a Hilbert proof that |- P --> (Q --> R) --> (P --> Q) --> (P --> R). To get any credit for this problem, you must use the Deduction Theorem exactly three times. The Hilbert proof I have in mind has exactly six lines. Then you'll need, I believe, three English sentences at the end of your proof. (Write up the proof neatly and carefully enough to convince the grader that you understand the D.T. perfectly.) Problem 2: Bullet-prove that |- (P /\ Q) --> (P \/ Q). You may NOT use the Deduction Theorem in your proof. This is a ridiculously short proof. 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". (I give such detailed instructions for a few reasons -- to force people to do well on the assignment; to produce, ideally, only one solution, so that the grader does not have to work with five different marking schemes for as many different proofs; to speed up the assignment for you since time is short till it is due.) Problem 4: Bullet-prove that |- (P == Q) == ( (P /\ Q) \/ (¬P /\ ¬Q) ). (This is also very short and easy.) Problem 5: 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.