CS486 Applied Logic Assignment 3 Due Thursday, Feb 22, 2001

Reading: Please read Smullyan, Chapter III:

p. 1-36 by Tuesday, Feb 20

p. 36-40 by Thursday Feb 22

Exercises:

1. Produce a completely systematic tableau proof of these formulas and for (i) show that the tableau is an example of a Labeled Tableau Tree satisfying the conditions to be a tableau proof.

(i)((p É q) É p) É p (Pierce’s Law)

(ii)((p Ú q) É r) É (p É r)

2. Write a programming language data type for an analytic tableau according to our in-class translation of Smullyan’s definition on p. 24.

3. Show that any finished tableau (all lines used) must be complete (according to Smullyan p. 26).

4. Solve Smullyan exercise 3, p. 30.

5. Optional. Prove the theorem at the top of p. 29 about finite sets S of formulas being unsatisfiable.