
Preparation file for Test 1:
Test 1, 77: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 "wellformed
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 highschoolish. (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 valuevalued 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 Gammatheorems 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 superimportant.

Of course understand the recursive definition of "theorem" and of
"Gammatheorem". 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 threehour 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. 8687. 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 triplebar. 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 triplebar, 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 lowercase.
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
"letterplopping".
Suddenly, from nowhere, comes this "v", and we
are supposed to know who/what "v" is. PLOP.
This will lose you marks bigtime.
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
bigtime.
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. 4243, 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 Gammatheorem 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.
