80-211 Spring 2003

Assignment #2

Due on Friday,
January 31^{st}.

**1.
**Prove the following sequents using only the 10 basic inference rules (see page
39-40)

(a) P ├ Q → (P &Q)

(b) (P→Q) & (P→R) ├ P→ (Q &R)

(c) P & Q ├ P v Q

(d) P→Q, R→S ├ (P v R) → (Q v S)

(e) ~P→P ├ P

**2**.
Prove the following sequents using only the 10 basic
inference rules and the definition of the biconditional.

(a) P↔Q ├ ~P ↔ ~Q

(b) (P ↔ ~Q), (Q ↔ ~R) ├ P↔R

**3. **(a) Prove the following sequent:

P, ~P ├ Q

(b) What
does this sequent suggest about what follows from a contradiction?

**4.
**Define @ by the following, A@B = ~(A & B). Using df-@
in a way parallel Df. ↔, find a proof for the
following sequent.

** **(a) P @ P ├ ~P