Shantila's Inside Logic #21+

Answers to some more Practice exercises

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

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

119 PvQ } ~(~P&~Q)

The proof of 119 also is similar to the proof of 114.

120 ~PvQ } P>Q

  1 1. ~PvQ A      
  2 2. P A (for CP)      
  2 3. ~~P 2 DN
  1,2 4. Q 1,3 DS
  1 5. P>Q 2,4 CP      
 

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

The proof of 121 also is similar to the proof of 114.

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

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

Answers to some Extra Credit exercises

123 ~(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      
               

124 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!!          

125 ~P>Q } PvQ

Note: The proof for sequent 125 is similar to that for 124.

126 ~(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 126. 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.

126 ~(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        
 

127 P, ~P } Q

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

128 ~(~P&~Q) } PvQ

Note: The proof for sequent 128 is similar to that for 126.

129 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        

130 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 130 would be to assume ~R for RA on line 4 and go from there.

131 (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        
                 

132 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      
 

133 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        
                 

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

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