CS486 Applied Logic Assignment 1 Due Thursday, Feb 1, 2001

Reading: Please read Smullyan, Chapter 1, by Tuesday Jan 29, and Chapter 2, Section 1, by Thursday, Feb 1

Quiz: Expect an in-class multiple choice quiz on Thursday, Feb 1 on Chapter 1 and on first 3 pages of Chapter 2.

Exercises:

1. Write a data type for the class of finite unordered trees (Chapter 1, Section 0) and propositional formulas, Smullyan’s definition (Chapter 1, Section 1, p.5). You can use Lisp, Scheme, Java, ML or any other programming language because we want a careful explanation of the data types and an argument that they are equivalent to Smullyan’s inductive definitions (pages 1 and 5).

2. Solve Smullyan exercise 2 of Chapter 1.

3. Solve exercise 3 of Chapter 1.

4. Solve exercise 4 of Chapter 1.

Note: You may discuss these problems with fellow students, but all written work must be entirely your own. If you use a solution from other sources, you must cite them, including from other people who help you.