Problem Set 1

due Tues, Jan 28, 2003

Reading

Please read Smullyan:

• p. 1-14 for Thurs, Jan 23
• p. 15-24 for Thurs, Jan 30

NOTE: Recall lecture discussion about reading assignments.

Note on integrity

You may discuss problems with fellow students, but all written work must be entirely your own, and should not be from any other course, present or past. If you use a solution from another source you must cite it, including from other people who help you.

Problems

1. Give another definition of tree (from CS280 or readings) and show informally that it is equivalent to Smullyan's.
2. Show that this recursive definition includes only finite binary trees in Smullyan's sense:
   
   $$\mbox{If }t \mbox{ is an element of }S, \mbox{ then }t \mbox{ is a tree.}$$
   
   
   
   
   $$\mbox{If }t_1,t_2 \mbox{ are trees, then so is }<t_1,t_2>.$$
   
   

3. Show that a finitely generated tree can be infinite by constructing an example that fits Smullyan's definition precisely.
4. Solve Exercise 5, p. 14 for $\downarrow$ the denial operator.
5. 1. Give a precise definition of formula for the logic with only $\downarrow$ as a connective.
   2. Give a precise definition of formula for the logic with $t$ and $f$ as constants (Exercise 2, p. 13).
6. Solve Exercise 1, p. 13 for the three equivalences in the left column.