
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):
Bulletprove 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:
Bulletprove 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
