CS486 Applied Logic Assignment 2 Due Tuesday, Feb 13, 2001

Reading: Please read Smullyan, Chapter II:

p. 15-24 by Thursday, Feb 8

p. 25-30 by Tuesday Feb 13

p. 30-40 by Thurs Feb 15

Exercises:

1. Recall that B are the Booleans, {t,f} and Value was defined in Lecture 3 (see Lecture Notes). Prove this valuation theorem in detail by induction on Form.

"X:Form. " v₀:Var_X®B. $y: B. Value(X,v₀,y).

2. Solve the Exercise on p. 24, items 2, 3, 6, and 7.

3. What is the maximum number of nodes that can appear in an analytic tableau (considered as a tree) for a formula of degree n? Explain your answer.

4. Prove that truth tables considered as a proof system are consistent and complete (see Smullyan for definitions, p. 25).

5. Extra credit. Write a recursive definition for the type of an analytic tableau (see p. 24).