|
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.
|