CS486 ����������� Applied Logic��� ����������� Assignment 4� ����������� Due� Thursday, Mar 1, 2001

����������������������� ����������������������� ����������������������� ����������������������� ����������������������� �����������������������

Reading:�������� Please study Smullyan, p. 36-40 again;

also read Chapter XI, p. 101-108

Exercises:

1. Give block tableau proofs or falsifications of these formulas:

(i)�� ((p � q) � p) � p

(ii)� ((p � r) � (q � r)) � (~p � q) � r

(iii) (p �(q � r)) � ((q & ~r) � ~p)

2. Give three examples of properties of sets which are not of finite character and prove that they are not (see p. 32).

3. Write a precise symbolic definition of what it means for a set S of formulas to be satisfiable.

4. Is it true that the set of all tautologies is the intersection of all saturated sets?� Prove your answer.