80-211                                                                                                             Spring 2003

Assignment #5

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.

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)

Problem II:

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 jy and ├ jy to occur and try to show that one if and only if the other.

(a) jy is provable from our 10 primitives rules if and only if it is provable that ├ jy

(b)        j -||- y is provable form our 10 primitives rules if and only if it is provable that ├ jy

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

s:          Shamu

(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.