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.