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.