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.