CS486 ����������� Applied
Logic��� ����������� Assignment
5� ����������� Due� Thursday, Mar 8, 2001
����������������������� ����������������������� ����������������������� ����������������������� ����������������������� �����������������������
Reading:�������� Please read the handout on second-order
propositional logic, P2.
Read again the section on compactness (Smullyan, p.
30-38).
Exercises:
Consider these P2 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 P2
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).