Reading: Please read Smullyan Chapter I.

Tasks:
Estimated time: less then 6 hours.

1. Using library resources and possibly the Web, describe the subject of logic. That is, give two or three definitions of logic from sources other than our text books. List some of the major subfields of modern logic, either by consulting Math Reviews or finding a good Web mapping of the subject. List 10 propositional formulas that are interesting to you and are nontrivial (like Pierce's law below).
2. Give a definition of an unordered finitely generated tree according to Smullyan (p.3--4) as a data type in a high-level programming language such as Pascal, C, Scheme, etc. Relate it to Smullyan's definition, and explain why your definition is equivalent. I prefer Scheme or ML.
3. Define the notion of a formula of propositional logic as a data type in a programming language. Produce a definition equivalent to Smullyan's account on page 7 (which we call abstract syntax in computer science). I prefer Scheme or ML for this problem.
4. Write the truth tables or binary decision diagrams (BDD) for these formuals as indicated for

   (i) - use truth tables.
   (ii) Pierce's law - use decorated truth table.
   (iii) - use BDD with subformulas.
   (iv) - use BDD with subformulas.

5. Read Smullyan's exercise 1 § 2 and solve exercise 3 in § 2.

• About this document ...