This little file is meant to ensure that you know enough to do 
Assignment 1 properly.  It's also meant to save some class time.  

We defined states in class.  At first, we said that their 
domains are the set of all atomic Boolean wffs, i.e., the infinite
set consisting of the Boolean constants "top" and "bottom" and the
(infinitely many) Boolean variables.  

Then we indicated how one extends, inductively, any given state  v  
to a function defined on the entire set WFF.

Time expired then, but next I would have noted, as GT does, 
that only finitely many Bool. variables appear in any 
given wff  A, and would have said that a "finite state 
appropriate to A" is just a function whose codomain is 
the set  {f, t}  and whose domain is the set 
of variables appearing in  A  together with top and bottom, and whose 
value at top is t and whose value at bottom is f.  (And
of course one extends such a "finite state" to a function with a
bigger domain, namely, the set of all wffs which contain no Boolean
variables other than the ones with appear in  A.  (That domain
includes A!  :-) )  The truth table for  A  with which 
everyone should be familiar from a previous course (MATH
1019 or MATH 1190, e.g.) then has  2^n  (2 to the power n) lines,
where  n  is the number of Boolean variables appearing in  A.  

I gave an example in class.  Another example is the upper diagram on
page 33 of our text, except that I would write this wff as
(p --> (q --> p)), i.e., with brackets.  When you give truth tables on
this assignment, you may use the symbols  f, t  without making them
bold and without underlining them.  Just lower-case, as above, is ok.
Upper-case (as in the text by Rosen) is not recommended, for at least 
two reasons:  One, T looks dangerously like the symbol for "top" 
("verum") in our alphabet V.  Two, we said in the first class that
upper-case Latin letters from A through Z would stand for wffs, and 
if we now use F, T  for truth values then we are saying that truth
values are wffs, which is ridiculous (the former are semantic 
creatures; the latter are syntactic; "truth values" are not gotten
inductively (as all wffs are!) from atomic wffs, as discussed in 
our first Tuesday meeting).

Note again, also, that for us lexicographic order is f first,
then t.  (For Rosen it is the reverse.)  Thus the values of
p, q, r  in a truth table featuring only those variables are
f f f, t t t, t f f  in lines 1, 8, 5, respectively.  The grader
should not have to spend oceans of time deciding whether a truth
table is correctly filled out, if the person who wrote it down
did not have the basic consideration for his reader to list the
n-tuples of fs and ts lexicographically; I will instruct the 
grader to grade such tables as harshly as he wants.

We gave an official definition in class of "tautology".  On test or
exam, you must give that definition if asked to define "tautology".
But for this assignment you may use this fact (without even mentioning
that you are using it):

A  is a tautology  iff  it has value  t  on every line of its
truth table.  (I.e., iff its value under every finite state 
appropriate to it is  t.  This is made visible by there being 2^n
ts in the column under the main connective of A (if A is not atomic).

We began defining terminology like "satisfies" and "satisfiable" 
and "tautologically implies" at the end of our time Tuesday, and 
ran out of time.  Here are some definitions, which I'll give here 
to save time next week (and also so that you can do this assignment).

Given two or more wffs  A, B, ..., their "joint truth table" has
2^n  lines, where  n  is the number of variables which appear in
one or more of the wffs.  E.g., 

if  A  is  p /\ (q == p)   and   B  is  (q --> r) \/ q

(I left off the outer overcoat in each of  A  and  B  here),

then the joint truth table of  A  and  B  looks like this:

 p  q  r    A    B        There should be a vertical line to
                          separate the  r  column  from the part
 f  f  f                  of the table to the right of it, and
                          horizontal lines separating rows from
 ..............           one another, as in the top table on 
                          p. 33 of our text.  Note that in the
 t  t  t                  joint truth table we regard both of 
                          A  and  B  as involving all three 
                          variables  p, q, r, or at least we 
treat them as if they do (even though they don't).

Following our text, we will use certain upper-case Greek letters to 
denote sets of wffs:  Our favourites (with pronunciations in brackets) 
will be Γ ("gamma"), Δ ("delta"), Σ ("sigma"), Θ ("theta"), 
listed in that order on line 4 of page 34 of GT.  Often Γ is enough.

Here are some official definitions (compare these with 1.3.11 on 
page 34 -- the term being defined is in bold face below):

Let  A  be a wff, and let  Γ  be a set of wffs. 

(0)  A state  v  "satisfies  Γ"  


     for all wffs  B  in  Γ,  v(B) = t.
     (There is no special notation for this, just the English.)

     Γ "is satisfiable" iff some state satisfies Γ.

     ("Some" in mathematics always means "at least one".)

     Γ "is unsatisfiable" iff  it is not satisfiable,
     i.e., iff  every state  v  fails to satisfy at least one wff
     in Γ.

(1)  A  is satisfiable  iff there is some state  v
     such that  v(A) = t.  And one expresses this last
     equation in mathglish by saying that  "v satisfies A".

(1') A  is  unsatisfiable, or a  contradiction,  iff  
     for ALL states  v,  v(A) = f.

(2)  Γ  tautologically implies  A   iff

     for each state  v  satisfying  Γ,  v  satisfies  A.

     We then write  Γ |=    A,  or (my preference)  Γ |= A.

Unravelling this from earlier definitions, one easily sees that

Γ |= A    iff    EVERY state  v  which satisfies all of the
                       wffs in  Γ  also satisfies  A.

I may get tired of all the verbiage and just say "Γ
entails A"  in this case.

   [end of that list of definitions/terminology]

Convince yourself of these facts (all are easy):

Let  A  be any wff.  Then:
   |= A   iff   {  |  } |= A.  (A is a tautology iff the set {top}
                                entails  A.)

Given the question of whether
a set  Γ  of wffs does or does not tautologically imply a given
wff  D, we call  Γ  the set of hypotheses, or premises,
and  D  the conclusion, and we ask whether the hypotheses entail
the conclusion.

I suggest using notation I don't think is in GT, namely:

Let's write  v |= A,  to mean that the state  v  satisfies  A.  Then

this double turnstile is pronounced "satisfies", whereas in

Γ |= E,  it is pronounced "tautologically implies", or "entails".

Notice also that (as I said in class), if a double turnstile 
appears in a phrase like  |= C, i.e., with nothing to the 
left of it, then it is pronounced "is a tautology", and the 
wff to the right of it is pronounced first ("C  is a tautology").

Finally, note (right after 1.3.11 in our text) that in the
case of a finite set  Γ, we may at times drop the set braces
when the set is given by listing its elements, even though it
is not proper to do so (we pretend that the set braces are still

In your answers to problems 1-4 in Assignment 1, you must write enough
correct, clear English to convince the grader that you KNOW why your
answer is correct.  (This can include circling appropriate columns
or parts of a truth table, with accompanying English.)

OK, enough!