80-211 Spring 2003
Due on Friday, January 31st.
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