
Test 2: Solutions, comments, etc.
Problem 1:
4 free marks. Just state the Deduction Theorem. I promised to
ask folks to do this. I gave 0.8 bonus if people put all the
English in that I put in, in class.
Problem 2 (8 marks):
Easiest proof: Marks:
(1) A > C < hyp > 1
(2) B > C < ass > 1
(3) (A > C) /\ (B > C) < (1), (2), merging > 1.5
(4) blah blah < 2.4.24 > 1
(5) (A \/ B) > C < (3), (4), Eqn > .3, .2, 1
So {A > C}  {B > C} > ((A \/ B) > C),
by the D.T. 1
So the wff given in this problem is a theorem,
by the D.T. 1
The saddest sort of error here, and I saw MANY people
making it, was starting with too many assumptions.
LOTS of people assumed ... A! And/or assumed ... B!
This immediately destroys the proof. There is no way
to recover from this kind of error except to go back
and cross it out and start over.
One or two of you even like to start a Hilbert proof
by ASSUMING the wff you must prove. The "proof" is
over as soon as it starts, then.
Problem 3 (substitutions  2 marks for each one):
(a) This substn. is undefined.
(b) Just replace the "last" x in the wff by a z.
(c) Just the given wff.
Problem 4 (9 marks):
4.(a) Give a bullet proof that  A > (A \/ B).
The commonest, most natural, easiest, shortest proof:
given wff Marks:
<==> < 2.4.11 > .4
¬A \/ A \/ B
<==> <  ax. 9!  2.1.15! > 1.0
top \/ B  2.4.7! .4
Lots of folks still omit the turnstiles when using
this powerful metatheorem.
(b) Easiest, most natural proof was this Hilbert proof:
(1) (forall x) A < ass >
(2) A < (1), Spec spec >
(3) A > (A \/ B) < part (a), above >
(4) A \/ B < (2), (3), M.P. >
(5) (forall x) (A \/ B) < (4), 6.1.1, since
x dnof in wff in (1) >
Some people gave a shorter proof using 6.1.9. I gave that
proof a maximum of about 5 marks. My excuse for doing that
is that we had not mentioned 6.1.9 at all when the test was
given. We mentioned it and proved it only after the test. So
I did not regard it, at the time of Test 2, as a "metatheorem
from the course". My *motivation* for giving only 5 out of 7.2
is that the proof is too easy then. I wanted a 5step proof as
above. People who quoted 6.1.9 are the sort, probably, who
madly scan a handout for something that looks like what they
must prove, and pick even something not covered in the course
yet, rather than thinking about how to prove the given theorem
using what has been done in the course.
I will not type out the marking scheme the TA and I jointly
came up with. I don't have the time for that now.
Problem 5 (6 marks):
Easy, for people who understood the VERY similar example done
in class. (Here we said "exactly three". In class we said
"exactly two".)
Lots of people messed this up. The commonest error was not
putting EVERYTHING after the initial quantifiers into the scope
of those quantifiers. Another error consisted of putting a
universal quantifier BEFORE the existentials rather than after.
It makes a huge difference.
Maybe ten people began with (forall x)(forall y) and another
universal quantifier, and then first in the scope came
¬(x = y) as part of a conjunction.
Already this wff interprets as "false" always. It is NEVER
the case that for all elements a,b of a nonempty set,
a is different from b. a is not different from a.
Problem 6 (5 marks for each part):
(a) Easiest proof:
(1) top < 2.1.15 > 1.5
(2) (forall x) top < (1) and 6.1.1  x dnof in any
wff of the empty set > 3.5
One could also use Ax 4 and M.P., for a 3step proof.
(b) Just mimic the totally similar proof from class.
5 marks.
Problem 7 (5 marks):
The given wff P is not a theorem.
Simplest: Let D = {17, 43}. Let A be (x = y)
and B be (x = z). Interpret the free y as 17
and the free z as 43. This already gets 5 marks.
But further explanation: Then
(forall x)(A \/ B) interprets as the statement that
everyone in D is 17 or 43, which is true. And
(forall x) A \/ (forall x) B interprets as
"everyone in D is 17 or everyone in D is 43". Which
is false. So the given conditional interprets as "false".
Another solution, just as good: Instead of using variables
y and z as above, use constant symbols a and b.
LOTS of people proved the nontheorem! They all got 0.
Lots of people ignored the instruction to use a D having
exactly two elements. They got part marks (I forget what; the
marking scheme is in an email I sent to the grader) if their
example was good apart from having too many elements.
Lots of people used symbols like "0" or "1" or "≥", which
are not part of our alphabet of predicate logic, in their
wffs A and B. I think they got 3.4 out of 5.
Scroll down 60 lines or so for some "statistics" on the test
results, if you want.
Around 812 people out of 50 got unfiddled marks in the high
30s (37 to 39.9). Roughly the same number of people got
below 12 out of 50. The other 1/2 to 2/3 of people got
scores mostly between 20 and 34. I have not
entered the marks and found the average, yet. I will
probably raise marks on average by 2 or 3 marks. Not sure.
I would guess that the average mark was about 26 out of 50.
I think it was fairly easy to get 37 out of 50 for anyone who
had been attending class, working, and doing the assignments
conscientiously, and who took the test preparation file
seriously. I was a little surprised that some people did not
get unfiddled marks around 45 on this test. I welcome explanation
of that fact, in emails.
