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.