Preparation file for Test 1:


Test 1, 7-7:55 p.m., Tuesday, 26 February,
IN TWO DIFFERENT ROOMS (see below)

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. I spent somewhat too long at the start of this course on technicalities about wffs, etc. You should certainly, going into our test on 26 February, have a good feel for the "alphabet" of boolean logic (variables, the two boolean constants, parentheses, five connectives, recursive definition of wff), but that is all just necessary background to doing other things. I will not promise that I will or will not ask anything on Test 1 about the alphabet, or about the recursive definition of "well-formed formula", but you must know all this anyway. Be ready to be absolutely precise in writing down a wff (including ALL required parentheses, and NO brackets which should NOT be present), to be able to notice even the smallest flaw in a string, preventing it from being a wff. I will not, though, ask on our test for induction proofs of statements about strings, of the sort done in class. ----------------------------- I regard truth table stuff as high-schoolish. (It is also supposed to be stuff mastered before MATH 1090 in other courses.) Having expertise with truth tables, knowing the truth table definitions of F , F , etc. ¬ /\ ( the actual functions defined from {f, t} to B := {f, t} or B x B to B ), and being able to work with truth tables, counts for probably much less than 10% of the grade in this course. But, of course, to understand any semantics at all, one must know how those five truth value-valued functions are defined. Notice that they are not definitions of the boolean connectives themselves; they are interpretations of those connectives which come up only when one does SEMANTICS of boolean (and, later, predicate) logic, NOT when one does SYNTAX of logic -- PROOFS. When one proves things, the connectives are just meaningless symbols appearing in meaningless axioms (hence in meaningless theorems) -- semantics later breathes life into all that meaninglessness. (And reveals why we chose the 11 axiom schemes we did, and the two primary inference rules -- at least somewhat reveals that.) -----------------------------

Induction

I talked about induction but then did not do very much with it. Again: Don't worry about induction proofs for Test 1. I may give a Bonus Problem later in the term for people to do if they want to do an induction proof, but Bonus Problems will not be due until near the end of the term. ------------------

Substitution

Know what substitution is and the notation for it: Q[p:=A] sort of thing. I won't ask for the recursive definition of substitution which we gave in class. The purpose of doing that was just to be totally honest about claiming that we had defined it (for that, one must use induction/recursion). Of course, our main, if not only, use of substitution so far is in uses of the primary inference rule called Leibniz. I could ask you folks to STATE the Leibniz inference rule for me precisely on our test, in full generality. This should be regarded as an easy problem, since we have used Leibniz so many times in so many specific instances. (I could also ask you to STATE precisely for me our one other basic inference rule, Equanimity. We have done everything we have done in the course, on the syntactic side of logic, starting with only 11 axiom schemes and two inference rules, Leib and Eqn.) Note that each inference rule applies not only to inputs that are theorems, but to inputs that are merely Gamma-theorems for some set Gamma of wffs. Substitution will become much more complicated in predicate logic, later in the course, where the distinction between "free" occurrences and "bound" occurrences of a variable in a wff will arise, and will be super-important. ------------------------------------------ Of course understand the recursive definition of "theorem" and of "Gamma-theorem". I will not ask you folks to state those definitions, but if you don't understand them you can't give (annotated) Hilbert proofs of given wffs, or at any rate will not understand what is happening in a proof, and then later on bullet proofs and equational proofs generally will perhaps also not quite make sense to you. Do as many bullet proofs as you can before the test. Actually, you should have started with this AT LEAST two weeks ago, when I said to. We did several bullet proofs in the last two three-hour classes, and at the end of one class I said "Nothing prevents you from doing MANY MORE bullet proofs before our test as practice" (or something very close to that). To be prepared for the test on Tuesday, 26 February, you need lots of practice with bullet proofs. Understand well all bullet proofs done in class. Look again at everything I have said or typed about practice proofs. The general rule is that one may use, in a proof, ALL axioms, and any theorems with number SMALLER than the number on the list of the theorem whose proof is asked for (i.e., any theorems which appear HIGHER UP in the list, i.e., earlier). But I could also ask youo to prove a theorem we have never seen before, also. Or I could tell you that you are NOT allowed to use a certain theorem in a bullet proof of a certain other theorem you have been given to prove. So: READ instructions carefully and follow them, on the test. I noticed just now that Tourlakis does not use parentheses or spacing as I insist that we do in this course, on pp. 86-87. So here is some clarification, if you want it, of the wffs he is talking about on those pages: (I'll just list the problem numbers and type the wff involved in each case; I won't type out the wording of the whole problem. And, by the way, let's treat all of these as bullet proofs, not annotated Hilbert proofs.) 1. A \/ B == A \/ ¬B == A 2. A /\ (A \/ B) == A 3. A \/ (A /\ B) == A 4. (A /\ B) \/ (A /\ ¬B) == A 5. A == B == (A /\ B) \/ (¬A /\ ¬B) 6. Just put a lot more space around the triple-bar. It is the "main connective" in this wff. Alternatively, put an overcoat around the wffs to the left and to the right of the ==. 9. I'd type this as Prove that A --> B |-- (C \/ A) --> (C \/ B). 16. Put a lot more space around the triple-bar, or overcoats on the wffs to its left and its right. 17. A --> (¬B --> (¬(A --> B))) 18. A --> B --> (¬A --> B) --> B (Or, put overcoats around the wffs to the left and the right of the arrow I put sooooooooooooo much space around, above -- technically, they aren't even wffs without those overcoats, and we need a final overcoat around the whole thing, but we have agreed to relax the formalities (unless someone tells us NOT to on a test, say) as long as we clearly indicate what wff we intend.) 20. (A --> C) --> ((B --> C) --> ((A \/ B) --> C)) --------------------- We have spent most of our time so far on syntax -- proofs etc. But earlier in the course we defined the double turnstile symbol and used it to denote the phrase "is a tautology" and, more generally, the phrase "tautologically implies", in connection with arbitrary sets Gamma of wffs. You should be able to use, and read and write, such stuff perfectly; you should be able to give me perfect definitions (in perfect English) of phrases like the ones in 1.3.11 in the text, but the versions from class, of course, NOT the versions in the textbook. (My English is often better than Tourlakis'.) So you will need accurate copies of notes of what was done in class. The phrases include these: state "satisfies" set, wff is "satisfiable", set is "satisfiable", set is "unsatisfiable", wff A is a tautology ( |= A ), set Γ tautologically implies wff A. (Example: This may not be the definition from class; I don't have the notes in front of me now, but it is a good way to state this definition: Let Γ be a set of wffs and let H be a wff. "Γ "tautologically implies" H, iff for each state v such that v(B) = t for all wffs B in Γ, (long pause here if you are SAYING this rather than typing it :-)) v(H) = t.) By the way, I don't insist that you make f, t boldface. But they must be lower-case. For some reason, MANY students in my courses do not BELIEVE me when I warn them in advance that they will have to know definitions of things and be willing and able to WRITE THEM DOWN for me perfectly on tests. (Go to perfectly taken notes and -- if your English is not perfect -- memorize perfectly whatever definition or theorem (or whatever) I have told you I might ask of you.) I don't know why this is. If you don't believe me, then, during and after the test, you will wish that you HAD believed me. I WILL ask you to do these things. So I strongly suggest that you write out ALL definitions mentioned in this test preparation file, on index cards if necessary, and practice alone or with a friend writing them out perfectly, in perfect Mathglish (i.e., English sentences, punctuated properly, possibly with technical symbols used correctly in them). Practice ten times writing out each definition, if necessary. You won't have time on the test to fool around; you'll want to know those definitions in your sleep. There is no rule that tells you what wording changes you can make in a definition without hurting it. Sometimes what looks like a big wording change will still get full marks according to my marking scheme. Sometimes what looks like a small change will lose lots of marks. If your English is weak, you probably want to stick with wordings from class (or wordings posted in files on our course page). A nontrivial amount of marks may end up being dependent upon being able to give correct definitions in correct English. I strongly believe that people who cannot SAY exactly what is meant by the words and symbols they use don't KNOW what those words and symbols mean. ("I know what I mean; I just can't say it." is, to me, a statement without any validity in my universe -- part of what I MEAN by "know" and "mean" is being able to SAY precisely what this or that means.) Many students THINK they know certain definitions, and find out on tests, or when the tests are graded, that they did NOT know. You must actually GO BACK to the class notes and SEE what is there and MEMORIZE the thing if that is the only way to remember an accurate phrasing of it. Here's an example from my class notes: Γ is unsatisfiable iff for EACH state v, v(B) = f for at least one B in Γ. I could test whether you know this definition, in various ways. I could ask you to complete the following in perfect English: "Gamma is unsatisfiable iff" , in which case your job would be to find a grammatical way to FINISH the sentence so as to give a precise phrasing of the definition. Or I could say, "Give the definition from class of what it means to say that a set Gamma of wffs is unsatisfiable." Then your job is to write a complete English sentence that does the job. Suppose I do the first. Then you start with Gamma is unsatisfiable iff .... Suppose you then write "v(B) = f for some B in Gamma." Well, the "some" is fine, because in mathematics "some" MEANS "at least one". But, out will come my red pen and I will write something like WHO IS v?? Because the above is an instance of

"letter-plopping".

Suddenly, from nowhere, comes this "v", and we are supposed to know who/what "v" is. PLOP. This will lose you marks big-time. It's like saying "Mary in Indiana is clever." My reaction to this is "Huh?? WHO is MARY?" I am supposed to know without being told, who "Mary" is??????? If instead you say, "

There is

someone named Mary in Indiana who is clever.", then I nod to myself and say, "Yes, there probably is." Or if you say "Everyone named Mary in Indiana is clever.", then I probably think to myself, "No, I doubt that." You can't just PLOP "Mary" down without any OTHER WORDS. I must be told whether you are speaking of ONE Mary, or TWO Marys, or ALL Marys, BEFORE I can make any sense of what you are saying. By leaving out the "for each state v,", you are making two errors: First, you neglect to say that v is a STATE. Second, you omit the CRUCIAL words "FOR EACH" ("for all states v" is just as good as "for each state v"). If you write "for state v" or "for a state v", you still lose marks big-time. The definition stipulates that something must be true for ALL states v, not "a" state v. Here is a way to complete Gamma is unsatisfiable iff ... that would get FULL marks, even though it looks quite different from the definition given in class: "... for each state v, it is not the case that v(D) = t for all D in Gamma." This, on the other hand, would get close to ZERO marks: "... it is not the case that for each state v, v(D) = t for all D in Gamma." This last says: "It is not the case that Gamma consists just of tautologies." I.e., there is at least one wff in Gamma that is not a tautology. This is very different from saying that Gamma is unsatisfiable. There are lots of sets which contain wffs that are not tautologies, but which are satisfiable (i.e., which are not unsatisfiable). HOW YOU USE English, the order in which you write the words down, what words you use or don't use, have enormous consequences for the meaning of what you write. Anyways... I hope this little discussion is enough warning about such matters on Ganong tests. ----------------------------------------- I say elsewhere in this file that you will have lists of axiom schemes and theorem schemes, on a printed sheet during Tuesday's test. 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 two basic inference rules printed out -- you are supposed to have used those, and other derived ones (such as "Trans" and "other Equanimity" and maybe others), and certain metatheorems, 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, basically. There was, for instance, the metatheorem to the effect that if |- A and |- B then |- A == B. I.e., that any two theorems are syntactically equivalent. We have used this metatheorem a few times already, and I remarked when we first stated and proved it that it was important. ----------------------- I will expect you to know and be able to state precisely, and know the names of, two gigantic metatheorems of Boolean Logic. They express the connection between semantics and syntax of BL. Here they are (note that they are called "theorems" but they are really "metatheorems" -- they are ENGLISH statements ABOUT Boolean Logic): The Soundness Theorem (or, just "Soundness" of BL) I won't state this here; if you were in class you know what it says. The Completeness Theorem (or, just "Completeness" of BL) Same comment. More briefly: Soundness says: If a wff A is provable from a set Gamma of wffs, then Gamma tautologically implies A. In other words, our logic ONLY allows us to prove "good" things. We cannot prove a Gamma-theorem that is not entailed by Gamma. If we can (Gamma-) prove a wff, then it is (Gamma-) "good". But don't give me any of these wordings; these are just for your benefit, in this file. Completeness says: If a set Gamma tautologically implies a certain wff A, then A is provable from Gamma. In other words, if a wff out there in the woods is (Gamma-) good, then our proof weapons in BL do enable us to track it down. (more below) ------------------------
Here is a list of theorems that will appear, numbered, along with the axioms, on a handout at Tuesday's test: 2.1.12, 2.1.15, 2.1.21, 2.4.1, 2.4.4, 2.4.5, 2.4.7, 2.4.10, 2.4.11, 2.4.12, 2.4.13, (Ganong's) 2.4.17' and 2.4.18', 2.4.19, 2.4.20, 2.4.21. (There might also be others on the list; I don't know.) I could very well ask you to do something like "Prove 2.4.12 using only theorems BEFORE 2.4.10 on the list given out at this test (and, of course, axioms)", or "Prove W (where W is some theorem you maybe never saw before) using only axioms, and theorems appearing before 2.4.17 on this list." I am thinking also that I might ask you to justify only one or two steps of a Hilbert proof -- i.e., to provide the detailed annotation to justify one or two steps. Typically, that will involve a Leibniz step. In such situations, remember from things I have posted here that saying a variable is "fresh" is not explicit enough for me. One must say explicitly in what wff or wffs it does not occur. Also: You are NOT allowed to use Soundness to prove that wffs are tautologies, on our test Tuesday, and not allowed to use Completeness to prove that wffs are theorems on our test Tuesday either. If I ask you to do the former, I expect some work either with a truth table or with English discussion of truth values. If I ask the latter, I definitely expect a syntactic proof that the wff is a theorem (and NOT a discussion of truth values).

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: About 45 of you will write the test in our usual room, Curtis K, from 7 to 7:55 p.m. on Tuesday, 26 February. The rest of you are to write the test in Curtis 110. I will post here a clear indication of which people in the class are supposed to go to Curtis 110, and which people are supposed to go to Curtis K. Right now I must run to an appointment. I may post more here tonight. If you show up in the wrong room and an invigilator sees that you did, you will be told to go to the right room and will lose valuable time for the test doing that. We may deduct marks for this, too. So make sure you know the room to go to, and tie a string on your finger reminding yourself where to go for the test, or so. Everyone should come to Curtis K after the tests are collected by the invigilators; we will have class as usual, for about 95 minutes.