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 5-step 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 3-step 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 non-theorem! 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 8-12 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.