Last Update: 5 March 2002
Note: material is highlighted |
In doing this problem, you might find the following additional rules of
inference for the natural-deduction system that I am introducing in
lecture to be useful (though note that you do not need anything that is
not in Ch. 6):
vIntro: From P From Q ----------- ----------- Infer (PvQ) Infer (PvQ) vElim: From (PvQ) From (PvQ) and -P and -Q ---------- ---------- Infer Q Infer P <=>Intro: From (P => Q) From (P => Q) and (Q => P) and (Q => P) --------------- --------------- Infer (P <=> Q) Infer (Q <=> P) <=>Elim: From (P <=> Q) From (P <=> Q) -------------- -------------- Infer (P => Q) Infer (Q => P)
Also: You can't use natural deduction (or any other syntactic proof-technique) to prove that you can't prove something. But you can prove that you can't prove something, by using semantic proof-techniques, such as truth tables or Wang's Algorithm.
For more details on the natural-deduction system introduced in lecture, see:
if P then Q else R
(a) Give a truth table for it.
(b) Define it in terms of , , and . (I.e., your definition will use some or all of those binary connectives.)
DUE AT START OF LECTURE: WED., MAR. 6 |