Homework 2 Solutions

1. Find proofs for the following sequents:
   1. (2 points)

      P -> (P -> Q), P |- Q
           1 (1) P -> (P -> Q)   A
           2 (2) P               A
         1,2 (3) P -> Q          1,2 MPP
         1,2 (4) Q               2,3 MPP

   2. (2 points)

      -P -> -Q, Q |- P
           1 (1) -P -> -Q   A
           2 (2) Q          A
           2 (3) --Q        2 DN
         1,2 (4) --P        1,3 MTT
         1,2 (5) P          4 DN

   3. (2 points)

      P |- (P -> Q) -> Q
           1 (1) P               A
           2 (2) P -> Q          A
         1,2 (3) Q               1,2 MPP
           1 (4) (P -> Q) -> Q   2,3 CP

   4. (2 points)

      P & (Q & R) |- Q & (P & R)
         1 (1) P & (Q & R)   A
         1 (2) P             1 &E
         1 (3) Q & R         1 &E
         1 (4) Q             3 &E
         1 (5) R             3 &E
         1 (6) P & R         2,5 &I
         1 (7) Q & (P & R)   4,6 &I

   5. (2 points)

      P & Q |- P v Q
         1 (1) P & Q   A
         1 (2) P       1 &E
         1 (3) P v Q   2 vI

   6. extra credit: (2 points)

      -(-P v -Q) |- P & Q
           1 (1)  -(-P v -Q)               A
           2 (2)  -P                       A
           2 (3)  -P v -Q                  2  vI
         1,2 (4)  (-P v -Q) & -(-P v -Q)   1,3 &I
           1 (5)  --P                      2,4 RAA
           1 (6)  P                        5 DN
           7 (7)  -Q                       A
           7 (8)  -P v -Q                  7  vI
         1,7 (9)  (-P v -Q) & -(-P v -Q)   1,8 &I
           1 (10) --Q                      7,9 RAA
           1 (11) Q                        10 DN
           1 (12) P & Q                    6,11 &I

2. Show that the sequent P v Q |- P & Q is unsound, by finding actual propositions for P and Q such that the assumption is true and the conclusion false.

   (2 points) Let P be the statement ``1+1=2'' and let Q be the statement ``1+1=3''; then the assumption P v Q is true, but the conclusion P & Q is false.