80-211 Spring 2003
Due on Friday, February, 21th .
1 (4 pts). Do either problem I or problem II below (but not both). Problem II is more challenging than problem I, but should be shorter. I suggest you at least think about problem II even if you decide to do Problem I.
(a) P→Q ├ (P↔Q) v Q
(b) P & Q ├ ~(P→ ~Q)
(c) P→Q, ~(~P & ~S), ~Q v S ├ T v S
(d) P→(Q v R) ├ (P→Q) v (P→R)
For (a) and (b) let j and y stand for arbitrary formulas of propositional logic. Also, note that the goal of the problem is not to give a proof as we have been doing, rather you must give a “meta-proof”. The variables j and y are meta-variables for arbitrary formulas in propositional logic. Thus, think about what it means for j ├ y and ├ j→y to occur and try to show that one if and only if the other.
(a) j ├ y is provable from our 10 primitives rules if and only if it is provable that ├ j→ y
(b) j -||- y is provable form our 10 primitives rules if and only if it is provable that ├ j↔y
2. (2 pts) Show that the following sequents are valid or invalid. If it’s invalid its not necessary to write out the whole table, rather just a single case (namely one that shows its invalid).
(a) P→(Q v R) ├ P→Q
(b) P→(Q→R), Q, ~R ├ P
3. (4 pts) Symbolize sentences (a)-(d) with the interpretations given below.
Tx: x is a trick
Wx: x is a whale
Sx: Shamu can do x
Cx: x can do a trick
(a) Shamu can do every trick
(b) Shamu cannot do every trick
(c) Shamu cannot do any trick.
(d) If any whale can do a trick, Shamu can.