Shantila's Inside Logic #21

Answers to some Practice exercises

*

Remember that there can be more than one way successfully to prove that a sequent is valid. Your proof may be fine even if it differs from those listed here -- the question, of course, is: have you use the rules correctly on each line? (Please check with one of the instructors if you have questions about one of your proofs.)

Please do not try to memorize the following proofs. That will not help very much. But it may help to see how they can be done (if you get stuck) -- and then go back and DO THEM and re-do them ON YOUR OWN.

Answers to some Practice exercises

Note: Remember that there may be other perfectly good derivations than these that are presented (different paths to the same conclusion, given the premises).

109 } (P&Q) > ~(P>~Q)

  1 1. P&Q A (for CP)      
  2 2. P>~Q A (for RA)      
  1 3. P 1 &E      
  1,2 4. ~Q 2,3 MP
  1 5. Q 1 &E      
  1,2 6. Q&~Q 4,5 &I      
  1 7. ~(P>~Q) 2,6 RA      
  --- 8. (P&Q) > ~(P>~Q) 1,7 CP      
               

110 } ~(P&Q) > (P>~Q)

  1 1. ~(P&Q) A (for CP)      
  2 2. P A (for CP)      
  3 3. Q A (for RA)
  2,3 4. P&Q 2,3 &I
  1,2,3 5. (P&Q) & ~(P&Q) 1,4 &I      
  1,2 6. ~Q 3,5 RA      
  1 7. P>~Q 2, 6 CP      
  --- 8. ~(P&Q) > (P>~Q) 1,7 CP        
               

111 } ~(P&~Q) > (P>Q)

The proof of 111 is similar to the proof of 110.

112 } P > ~(~P&Q)

  1 1. P A (for CP)      
  2 2. ~P&Q A (for RA)      
  2 3. ~P 2, &E      
  1,2 4. P&~P 1,3 &I
  1 5. ~(~P&Q) 2,4 RA      
  --- 6. P > ~(~P&Q) 1,5 CP      
               

113 } ~(PvQ) > ~P

  1 1. ~(PvQ) A (for CP)      
  2 2. P A (for RA)      
  2 3. PvQ 2, vI      
  1,2 4. (PvQ) & ~(PvQ) 1,3 &I
  1 5. ~P 2,4 RA      
  --- 6. ~(PvQ) > ~P 1,5 CP      
               

114 ~P&~Q } ~(PvQ)

  1 1. ~P&~Q A      
  2 2. PvQ A (for RA)      
  1 3. ~P 1 &E      
  1,2 4. Q 2,3 DS
  1 5. ~Q 1 &E      
  1,2 6. Q&~Q 4,5 &I      
  1 7. ~(PvQ) 2,6 RA      
 

115 ~(PvQ) } ~P&~Q

  1 1. ~(PvQ) A      
  2 2. P A (for RA)      
  2 3. PvQ 2, vI      
  1,2 4. (PvQ) & ~(PvQ) 1,3 &I
  1 5. ~P 2,4 RA      
  6 6. Q A (for RA)      
  6 7. PvQ 6, vI      
  1,6 8. (PvQ) & ~(PvQ) 1,7 &I      
  1 9. ~Q 6,8 RA      
  1 10. ~P&~Q 5,9 &I      
               

116 } ~(PvQ) <> (~P&~Q)

  1 1. ~(PvQ) A (for CP)      
  2 2. P A (for RA)      
  2 3. PvQ 2, vI      
  1,2 4. (PvQ) & ~(PvQ) 1,3 &I
  1 5. ~P 2,4 RA      
  6 6. Q A (for RA)      
  6 7. PvQ 6, vI      
  1,6 8. (PvQ) & ~(PvQ) 1,7 &I      
  1 9. ~Q 6,8 RA      
  1 10. ~P&~Q 5,9 &I      
  -- 11. ~(PvQ) > (~P&~Q) 1, 10 CP      
  12 12. (~P&~Q) A (for CP)      
  13 13. PvQ A (for RA)      
  12 14. ~P 12 &E      
  12,13 15. Q 13,14 DS      
  12 16. ~Q 12 &E      
  12,13 17. Q&~Q 15,16 &I      
  12 18. ~(PvQ) 13,17 RA      
  -- 19. (~P&~Q) > ~(PvQ) 12,18 CP      
  -- 20. ~(PvQ) <> (~P&~Q) 11,19 <>I      
               
      ***