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.