Preparation file for Test 2:


Test 2, 7-7:55 p.m., Tuesday, 26 March,
IN TWO DIFFERENT ROOMS.

(Possibly, anyway -- I have reserved Curtis J as the extra room -- we may need it or may not -- check back here later. People whose last names start with a letter toward the end of the alphabet will go to Curtis J if we use it.) What will appear in this file will surely not be a complete list of what you should know for Tuesday's test. Test preparation files never mention EVERYTHING. You may NOT assume that if I don't mention something here then it will not appear on our test. ----------------------------- READ instructions carefully and follow them, on the test. At the test, you will have our two pages of lists of axiom schemes and theorem schemes, etc., of Boolean and Predicate Logic. (I might print only the things from predicate logic which we have talked about already in class, from the predicate logic page.) Again: You will have all the axioms from pp. 42-43, numbered in the usual way, and many theorems we will have discussed in class, with their usual numbers, printed on a handout I will give out at the test (but don't bring any such list yourself; I will have copies printed out for everyone that day). You will NOT have the basic inference rules printed out -- you are supposed to have used those, and other derived ones (such as "Trans" and "other Equanimity" and M.P. and maybe others), and certain metatheorems (like D.T., which you should be able to state fully and precisely if asked to), so many times that you know them in your sleep. You should basically know metatheorems and derived inference rules discussed in class on your own -- they will not be given on a handout at the test. Also: You are NOT allowed to use Completeness to prove that wffs are theorems on our test Tuesday. If I ask you to do this, I definitely expect a syntactic proof that the wff is a theorem.

Where to go on test day

I will post more a little later this week about our test, in particular, WHAT ROOM you should go to for the test. Everyone should come to Curtis K after the tests are collected by the invigilators; we will have class as usual, for about 95 minutes. Know what splitting and merging are and how to use them in, say, a Hilbert proof. (These are basically 2.5.1, parts (1) and (4).) Regard them as derived inference rules or as metatheorems, whichever. Know what the derived inference rule Modus Ponens (M.P., 2.5.3) is and how to use it. Know precisely what The Deduction Theorem (2.6.1) says and how to use it to prove conditionals. I might ask you to state it precisely. It works in predicate logic as well as boolean (as does M.P.) -- as do all of the inference rules we had before predicate logic. Just replace, in all of them, "wff of boolean logic" by "wff of pred. logic". If you write out what M.P. and D.T. each say, you will see that M.P. is basically the converse of D.T. (Reverse the "if" and "then" parts of the English sentence which is the statement of the D.T. to get a new "if, then" English sentence; convince yourself that it is true iff M.P. is true. :-) (I won't ask about any of this; I just thought I'd mention it here.) Be an expert at proofs of conditionals via the D.T., like the ones done in class and the ones on Assignment 4. Know what a ping-pong proof is, and how to write them out. The advantage of such proofs is that they allow one to bring to bear the power of M.P. and D.T. on the proving of biconditionals. Know the alphabet of predicate logic (PL) (not absolutely perfectly, maybe, but well enough to know the difference between the two kinds of variable and the letters used for them, well enough that you know a term from a wff (terms and wffs are totally different things -- look at the early part of the chapter beginning predicate logic if you want examples of terms). I am too lazy to type the x's below as bold x's. Pretend they are bold (i.e., metaobject variables). Know that if A is a wff then ((\exists x) A) is just an abbreviation for &neg; ((\forall x) (&neg; A)) Know that, in the above, the wff A is the "scope" of (\exists x) A. Understand thoroughly what free and bound occurrences of an object variable in a wff are. I might well give you one or more fairly complicated wffs and ask you which occurrences of this or that variable in this or that subformula of the given formulas are free and which are bound, and, in the case of the bound ones, which (\forall x) binds each of them. Have something of an understanding of the semantics of PL. Know in particular that an interpretation always requires the choice of a nonempty set called the "domain" or "universe of discourse". One of you asked me after class why it is called the universe of discourse (UD). "Discourse" is "discussion", "conversation". The term may come from philosophy. Philosophers use formal logic, and their nonempty set was the set D, or domain, "about which they were talking". Understand the examples done in class involving 2-place predicate letters φ (for instance) and their interpretation as directed graphs. By the way, a ONE-place predicate letter essentially interprets as a subset of the universe of discourse. For instance, if &phi& is a 1-place predicate letter, then it interprets as ... a predicate! I.e., as a statement about elements of the UD, which takes truth value "true" or "false" depending on which element is fed into it. It interprets, that is, as a function from the UD to {t, f}. Example: Let the UD be D = {1, 2, 4, 5, 7, 11, 14}, and consider the function (the predicate) (call it Joe) whose value at an element of this set is t iff the integer is even. Then one could, for instance, interpret a 1-place predicate letter φ as that function, or, more briefly, as the subset of the UD where it takes the value t, i.e., as the subset {2, 4, 14}. (The predicate letter interprets here as the statement "n is even", which is true iff ... n is even!) Joe: D --> {t, f}, and such a function is completely determined by giving its "truth set", i.e., the set of elements of its domain D, at which it takes the value t. We gave one or two examples involving "(universally) valid formulas" of predicate logic, also known as "absolute truths". Tourlakis uses both terms. x = x is a universally valid formula. So are, indeed, all the theorems of PL. The word "tautology" is no longer used in PL. It is replaced by "valid formula". We spent quite a bit of time talking about substitution of terms for object variables in wffs. Understand all of that. Know what capture is and that a substitution is defined iff capture would not result, from its being carried out. Know 4.1.33 and 4.1.34 (not by number, of course). Understand the proof in class that |-- (t = t) for any term t. It involved a partial generalization and Ax 2 and M.P. This last part finally added Sunday afternoon: I said I would finish this up Thur. or Fri. That did not happen. But I am just going through my notes and recording stuff here, and that was almost done last Wednesday. We did a proof or two or three using the very important metatheorem Gen, also known as 6.1.1. Understand those proofs and be ready to execute others like them. 6.1.1, for instance, gave us 6.1.3 in the text. (We remarked that this does NOT come from "partial generalization" and that it does not come from Ax 4 and M.P. either, because a theorem A might very well have a free occurrence of x in it.) We proved metatheorem 6.1.5 (Spec) easily from Ax 2, and 6.1.6 (Spec spec) is the special case where the term t is x. Look up all of these proofs in our text, by the way, if you like. We gave a ping-pong proof of 6.1.7. Understand that proof and be able to carry out similar proofs. Both the ping and the pong involve Spec spec and Gen (and D.T.). An easy proof of 6.1.8 involves ping-pong, with pong looking just like ping, and ping requiring two Spec specs and two Gens and D.T. OK, that's about it. I don't know if Test 2 will feature any bullet proofs. I sort of think that we moved on from bullet proofs after Test 1; I only put some on Assignment 4 to give more practice (maybe for the exam?) and a short one for some easy grading and assignment marks. Centre stage has been sort of taken over by Hilbert and D.T. and M.P. at this point. But we don't "forget" anything. OK, here is the last thing I will post on this course page before Tuesday's test:

Where you should go for Tuesday's test:

People whose LAST names start with any of the letters V, W, X, Y, Z must write the test in Curtis J. Everyone else must write in our usual room, Curtis K. And we will have class starting within ten minutes of the end of the test, in the usual room. I wish everyone what she/he would want to be wished, for test night, and I hope to see you Tuesday night. Ciao.