Shantila's Inside Logic #20+

Answers to some Extra Credit exercises

*

Remember that there can be more than one way successfully to prove that a sequent is valid. For example, see below for two different ways of proving 107.

**

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

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

105 P>Q } ~PvQ

  1 1. P>Q A      
  2 2. ~(~PvQ) A (for RA)      
  3 3. P A (for RA)      
  1,3 4. Q 1,3 MP
  1,3 5. ~PvQ 4, vI      
  1,2,3 6. (~PvQ) & ~(~PvQ) 2,5 &I      
  1,2 7. ~P 3,6 RA      
  1,2 8. ~PvQ 7 vI      
  1,2 9. (~PvQ) & ~(~PvQ) 2,8 &I      
  1 10. ~~(~PvQ) 2,9 RA      
  1 11. ~PvQ 10 DN        
                 
      wow! what a beautiful proof!!          

106 ~P>Q } PvQ

Note: The proof for sequent 106 is similar to that for 105.

107 ~(P&Q) } ~Pv~Q

  1 1. ~(P&Q) A      
  2 2. ~(~Pv~Q) A (for RA)      
  3 3. ~P A (for RA)      
  3 4. ~Pv~Q 3 vI
  2,3 5. (~Pv~Q) & ~(~Pv~Q) 2,4 &I      
  2 6. ~~P 3,5 RA      
  2 7. P 6, DN      
  8 8. ~Q A (for RA)      
  8 9. ~Pv~Q 8 vI      
  2,8 10. (~Pv~Q) & ~(~Pv~Q) 2,9 &I      
  2 11. ~~Q 8,10 RA      
  2 12. Q 11 DN        
  2 13. P&Q 7,12 &I        
  1,2 14. (P&Q) & ~(P&Q) 1,13 &I        
  1 15. ~~(~Pv~Q) 2,14 RA        
  1 16. ~Pv~Q 15 DN        
                 

Here is another way to prove 107. Each is equally good (because we have used the Rules correctly at each line in both proofs). The following one is two steps shorter, so it is slightly more efficient, but each is a fine proof for 107.

107 ~(P&Q) } ~Pv~Q (alternative proof)

  1 1. ~(P&Q) A      
  2 2. ~(~Pv~Q) A      
  3 3. P A      
  4 4. Q A      
  3,4 5. P&Q 3,4 &I
  1,3,4 6. (P&Q) & ~(P&Q) 1,5 &I      
  1,3 7. ~Q 4,6 RA      
  1,3 8. ~Pv~Q 7 vI      
  1,2,3 9. (~Pv~Q) & ~(~Pv~Q) 2,8 &I      
  1,2 10. ~P 3,9 RA      
  1,2 11. ~Pv~Q 10 vI      
  1,2 12. (~Pv~Q) & ~(~Pv~Q) 2,11 &I      
  1 13. ~~(~Pv~Q) 2,12 RA      
  1 14. ~Pv~Q 13 DN        
 

108 P, ~P } Q

  1 1. P A      
  2 2. ~P A      
  1 3. PvQ 1 vI
  1,2 4. Q 2,3 DS      
 

109 ~(~P&~Q) } PvQ

Note: The proof for sequent 109 is similar to that for 107.

110 P&(QvR) } (P&Q)v(P&R)

  1 1. P&(QvR) A      
  2 2. ~((P&Q)v(P&R)) A (for RA)      
  1 3. P 1 &E      
  1 4. QvR 1 &E
  5 5. ~Q A (for RA)      
  1,5 6. R 4,5 DS      
  1,5 7. P&R 3,6 &I      
  1,5 8. (P&Q)v(P&R) 7 vI      
  1,2,5 9. ((P&Q)v(P&R)) & ~((P&Q)v(P&R)) 2,8 &I      
  1,2 10. ~~Q 5,9 RA      
  1,2 11. Q 10 DN      
  1,2 12. P&Q 3,11 &I        
  1,2 13. (P&Q)v(P&R) 12 vI        
  1,2 14. ((P&Q)v(P&R)) & ~((P&Q)v(P&R)) 2,13 &I        
  1 15. ~~((P&Q)v(P&R)) 2,14 RA        
  1 16. (P&Q)v(P&R) 15, DN        

111 P>R } (PvQ)>(QvR)

  1 1. P>R A      
  2 2. PvQ A (for CP)      
  3 3. ~(QvR) A (for RA)      
  4 4. ~Q A (for RA)
  2,4 5. P 2,4 DS      
  1,2,4 6. R 1,5 MP      
  1,2,4 7. QvR 6 vI      
  1,2,3,4 8. (QvR) & ~(QvR) 3,7 &I      
  1,2,3 9. ~~Q 4,8 RA      
  1,2,3 10. Q 9 DN      
  1,2,3 11. QvR 10 vI      
  1,2,3 12. (QvR) & ~(QvR) 3,11 &I        
  1,2 13. ~~(QvR) 3,12 RA        
  1,2 14. QvR 13 DN        
  1 15. (PvQ)>(QvR) 1,14 CP        
                 

Another way to do 111 would be to assume ~R for RA on line 4 and go from there.

112 (PvQ)vR, P>R, Q>R, R>S } S

  1 1. (PvQ)vR A      
  2 2. P>R A      
  3 3. Q>R A      
  4 4. R>S A
  5 5. ~S A (for RA)      
  4,5 6. ~R 4,5 MT      
  1,4,5 7. PvQ 1,6 DS      
  3,4,5 8. ~Q 3,6 MT      
  1,3,4,5 9. P 7,8 DS      
  1,2,3,4,5 10. R 2,9 MP      
  1,2,3,4,5 11. R&~R 6,10 &I      
  1,2,3,4 12. ~~S 5, 11 RA        
  1,2,3,4 13. S 12 DN        
                 

113 QvR } RvQ

  1 1. QvR A      
  2 2. ~(RvQ) A (for RA)      
  3 3. R A (for RA))      
  3 4. RvQ 3 vI
  2,3 5. (RvQ) & ~(RvQ) 2,4 &I      
  2 6. ~R 3,5 RA      
  1,2 7. Q 1,6 DS      
  1,2 8. RvQ 7 vI      
  1,2 9. (RvQ) & ~(RvQ) 2,8 &I      
  1 10. ~~(RvQ) 2,9 RA      
  1 11. RvQ 10 DN      
 

114 PvQ, P>R, Q>S } RvS

  1 1. PvQ A      
  2 2. P>R A      
  3 3. Q>S A      
  4 4. ~(RvS) A (for RA)
  5 5. P A (for RA)      
  2,5 6. R 2,5 MP      
  2,5 7. RvS 6 vI      
  2,4,5 8. (RvS) & ~(RvS) 4,7 &I      
  2,4 9. ~P 5,8 RA      
  1,2,4 10. Q 1,9 DS      
  1,2,3,4 11. S 3,10 MP      
  1,2,3,4 12. RvS 11 vI        
  1,2,3,4 13. (RvS) & ~(RvS) 4,12 &I        
  1,2,3 14. ~~(RvS) 4,13 RA        
  1,2,3 15. RvS 14 DN        
                 

115 (P>R)&(Q>R) } (PvQ)>(RvS)

The proof of 115 is similar to the proof of 114.