CS486 Applied Logic Assignment 5 Due Thursday, Mar 8, 2001

Reading: Please read the handout on second-order propositional logic, P².

Read again the section on compactness (Smullyan, p. 30-38).

Exercises:

Consider these P² formulas:

i. "p.(p É "q.(q É p))

ii. "p.(p É q) É "r.r

iii. "p.((p É "q.q) É ~p)

iv. ("q.q) É "p.(p É p)

1. Apply the definition of free variables, FV in the handout, to the above formulas.

2. Which of the formulas is logically valid? Prove your answer.

3. Eliminate the quantifiers in each formula using the definition of Boolean value for a P² formula.

4. Solve the exercise on p. 38 of Smullyan.

5. OPTIONAL: Show where Tukey’s lemma fails if the definition of finite character is this

F(P) = if for all finite sets K, P(K), for K a subset of S then P(S).