Assignment 1

This is due on the table at the front of class,
between 6:50 and 7:00 p.m., Tuesday, 22 January.

It is easiest for me to type the text's "triple bar" in a plain
text file like this one as a long symbol: == .  (Triple bar may in
fact not appear in this file.  I may use  ==  throughout the course, 
when I type in a plain text editor like this -- just train yourself 
to read  ==  as  triple-bar),

And to type the text's "arrow" this way:  --> .

"Conjunction"  ("anding")  I will type as  /\ ,  

and "disjunction"  ("oring")  as  \/ .

When I am feeling energetic, negation is   ¬  ; when I am
lazy with typing, it becomes   \not  (backslash not), or even just "not".

The above remarks about notation will probably apply to most or all
of my Web postings about MATH 1090 for section M.  In handwritten
work on assignments, tests or exams, you must use  ¬  always --
not some other symbol from some other course you once took.

In the following problems, give all relevant detail. Convince the
grader, by what you write, that you know what all the words in the
problem mean, and that you have noticed what you should have noticed.
Don't just answer -- show what you had to do to arrive at your answer.
Make sure also that you answer all flaming questions, with 
civilized answers like "Yes" or "No".

To do problems 2-4 below, you will need the definition of 
"tautologically implies" from the preparation file posted on 
this course page for this assignment, and the definition of "is 
tautologically equivalent to", below.

(I won't bother making  t, f  boldface any more (or at least
sometimes I won't bother), but I always MEAN boldface.)


Terminology:

     Let  P  and  Q  be wffs.  P  is tautologically equivalent to  Q, 
     provided that,
     on every line of the "joint truth table" for  P  and  Q,     
     either   P  and  Q  are both t    
     or       P  and  Q  are both f.


Convince yourself that this is the case iff  ( P |= Q  and  Q |= P ) 
-- GT gives this definition in problem 16 on p. 50), and also 
that it is the case iff  |= (P == Q).

Given wffs  P  and  Q, we know how to write down
the truth table for each of them separately.  The joint
truth table for  P  and  Q  is obtained by looking at all boolean
variables appearing in either  P  or  Q, listing them in 
our preferred order (as indicated in class:  p, q, r if there are only
three, say), in the upper left from left to right, and then regarding  
P  and  Q  as expressions in  ALL  of the variables appearing in 
either  P  or  Q.

For instance, the  JOINT  truth table for  ¬p /\ q  and  q \/ r
would begin with columns labelled  p, q, r  at the upper left,
and would therefore have eight rows (each starting with a triple
of f's and t's, in lexicographic order from top to bottom):  


p q r    ¬p   /\ q       q \/ r
_________________________________

f f f    t     f            f    (line 1)

...          ...         ...     (six lines omitted here...)

t t t    f     f            t    (line 8)    


(Handwritten truth tables must have vertical lines as
separators in certain places, such as after the three far-
left columns of truth values here, but I omit them here 
because they involve too much finicky typing.  You will 
want horizontal lines also, separating the rows of a truth table
from one another, or will want to leave enough space between rows 
so that you don't make an eyeballing error, and a grader can easily
read your table.)


On all assignments, tests and exam in this course, it is
UNDERSTOOD that you must give a proof or a GOOD explanation
of your answer to any problem, UNLESS the problem explicitly
tells you NOT to.


As I said in class on 15 Jan., our lexicographic order for
boolean variables is  

p, q, r, p', q', r', p  , p  , p  , ....  And the grader will
                      1    2    3

be instructed to make heavy mark deductions in cases where the
student fails to list the variables involved in lexicographic 
order in the columns in the far left of a truth table.  And 
similar deductions if the student does not follow lexicographic
order in the lines of the truth table, where f comes BEFORE t
in the lexicography.  Thus, in the far left columns of an 8-line
truth table, fff comes in line 1, ftf in line 3, and tft in line 6.


In problem 4 below, I want the entire joint truth table
(32 truth values), together with enough English annotation of 
it to justify your answer.

In problems 1-3, you have a choice:  

(1)  Give FULL TRUTH TABLES, with a clear indication 
of WHAT COLUMN of the truth table is "important", and why.  Here,
"FULL TRUTH TABLE for a given wff or wffs" means a truth table
with t or f appearing in EVERY line *directly under* EVERY
connective of the wff or wffs.  I did an example in class
Tuesday.

OR

(2)  Give CLEAR, COMPLETE English explanations for your
answers.  

If your English is not great, or you are not sure what 
qualifies as a "complete" explanation, you'll probably
want to choose method (1) above.



1. Is   p   -->   ¬q \/ (p --> q)   a tautology? 

(Note that I left the "overcoat" off of the above wff.  Note 
also that I left an enormous amount of space on both sides of
the first arrow above.  This means that I intend the wff

( p   -->   ( (¬q) \/ (p --> q) ) )     above.

(Here I put the overcoat on, and brackets around the stuff that
I put far to the right of the first arrow.  I also put cute little
(  )s  around  ¬q.  Technically they should be there, but the 
"negation" connective is such a strong magnet, especially where 
only a variable is being negated, that one often omits the brackets.
Similarly,

               3    x    2 - 7

clearly means, at least I hope it is clear,   ( 3(2 - 7) ), 

and NOT   ( (3(2)) - 7 ).  I.e., it means -15, not -1.)



2. Does  p --> q  tautologically imply  (p /\ q) \/ ¬p ?


3. Are   (p \/ q) \/ r   and   p \/ (q \/ r)
          tautologically equivalent? 

          [In other words, do the parentheses "make
          a difference"? But don't answer this second question,
          in these here [  ]s! Just think about it.]

 
4. Are   (p --> q) --> r   and    p --> (q --> r)
          tautologically equivalent? 

          [In other words, do the parentheses
          "make a difference"? Again, don't answer this question
          in [  ]'s; just think about it.  And of course the purpose 
          of problems 3, 4 is that you think about them in light 
          of each other.]


5. (English reading skills required for this one....)

I claim that there is an infinite sequence of wffs


  P  ,  P  ,  P   ,  ... , P   , ... , P  , P    , ... ,
   1     2     3            17          n    n+1


that are all tautologies,
                                                 
in which     

         the only symbols which appear are: the boolean 
         variable  q  and  (  and  )  and  the connective --> ,

and such that 

         the complexity of  P     is strictly greater than
                             n+1
         the complexity of  P  , for all positive integers n.
                             n

Show that my claim is correct, by writing down an inductive definition
of such a sequence of wffs satisfying all of the above conditions.

(So you will have to write down who  P  is, and what  P     is
                                      1                n+1   

in terms of  P  .  Or, at least, that is what Ganong requires you to do
              n                               for full marks here.)

In this fifth problem, I want absolute precision
in the writing of wffs. Put in ALL required pairs ( )
of brackets.

(And, of course, no ( )s where ( )s should not be!)