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

            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.