80-211 Spring 2003

Assignment #5

Due on Friday,
February, 21^{th} .

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