Problem Set 2

NEW PROBLEM DUE DATE: Tues, Feb 11

Reading

Please read Smullyan, Chapter II:

Problems

  1. Solve the exercise on p. 24, items 1, 4, 5, and 8.

  2. Recall that a tableau $\cal T$ is complete if all its branches are either closed or complete, where a branch $\theta$ of a tableau $\cal T$ is complete if for every $\alpha$ on $\theta$ both $\alpha$\(_{_1}\!\) and $\alpha$\(_{_2}\!\) occur on $\theta$ and if for every $\beta$ on $\theta$ at least one of $\beta$\(_{_1}\!\), $\beta$\(_{_2}\!\) occur on $\theta$.

    Prove that the tableaux method terminates, i.e. that it takes finitely many direct extension steps until a tableau for a formula $X$ becomes complete.

  3. Show that any downward closed set $S$ (Smullyan page 23) satisfying the condition

    for all signed formulas $X$, $X\in S$ iff $\bar{X} \not\in S$

    is a truth set.

  4. Extra credit. Give a recursive definition for the data type of an analytic tableau.

    Data types for concepts defined in chapter I do not have to be defined but should be declared before you use them. Where possible, use the notation of notes for lecture 3.


Juanita Heyerman 2003-02-03