Philosophy 60                                                                  :    
Homework 1 Solution

Instructions:  Complete the following problems as directed.  Type your name.  Type your answers. Staple or paper clip multiple pages.  If you turn this in by e-mail, type the date and time you sent it on the hardcopy.   10 pts. total.

Note:  The box in the upper right hand corner is a preformatted textbox.  You can select it for copying and pasting by clicking on the perimeter.  You can expand it to whatever size you need by grabbing it on the perimeter and pulling.   It is useful for both truth trees and natural deduction.

1.  Use a truth tree to determine whether the following argument is valid.  Be sure to state the result (valid or invalid) and explain what part of the truth tree demonstrates this.  (2 pts.)

(p v q); ¬(r →p)  (¬q ↔ ¬s)

                                                                                                                                                                                                                                                    
                                       (p v q)                                                                                                                                                                                                    
                                      ¬(r →p)                                                                                                                                                                                                
                                    ¬(¬q ↔ ¬s)                                                                                                                                                                                                
                                           r                                                                                                                                                                                                          
                                         ¬p                                                                                                                                                                                               
                                                                                                                                                                                                                                                    
                                  p                 q                                                                                                                                                                                        
                                  X                                                                                                                                                                                                        
                                               ¬q        ¬¬q                                                                                                                                                                                
                                             ¬¬s          ¬s                                                                                                                                                                                       
                                               X                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                     
        One tree does not close, hence not valid.                                                                                                                                                                                                                                

                                                                                                                                                                                                                                                      

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                                      

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                          

2.  Use a truth tree to determine whether the following sentence is a tautology. Explain as above. (2 pts.)

¬(p ↔q) ↔ ((p & ¬q) v ¬(¬¬p v ¬q))

                                                                                                                                                                                                                                                    
                                		    ¬(¬(p ↔q) ↔ ((p & ¬q) v ¬(¬¬p v ¬q)))

          			¬(p ↔q)                                                             		 ¬¬(p ↔q)                                                                                                                                                                                                                                                                                                                                                                                                                  
      		¬((p & ¬q) v ¬(¬¬p v ¬q))                                           	      ((p & ¬q) v ¬(¬¬p v ¬q))                                                                                                                                                                                           
                                                                                                                                          (p  ↔ q)                                                                                                       
               p                                             ¬p                                  	                                                 	                                                                                                                            
              ¬q                                     	q                                 	                                                 	                                                                                                           
                                                                                                                     p                                                         ¬p                                                      
      ¬ (p & ¬q)                              ¬ (p & ¬q)                                              q                                                          ¬q
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
     ¬¬(¬¬p v ¬q)                         ¬¬(¬¬p v ¬q)                                                                                                                                                                           
        (¬¬p v ¬q)                              ( ¬¬p v ¬q)                      (p & ¬q)         ¬( ¬¬p  v ¬q)          (p & ¬q)          ¬(¬¬p  v ¬q)                                                                                                                               
                                                                                                                                ¬¬¬p                       p                          ¬¬¬p
                                                                                                       p                          ¬¬q                        ¬q                           ¬¬q                             
    ¬¬p               ¬q                     ¬¬p                  ¬q                        ¬q                          ¬p                         x                               x                                                                                  
                                                     x                        x                       x                   x                                                                                                                  
¬p   ¬¬q         ¬p   ¬¬q                                                                                                                                                                                                                                                  
 x       x          x         x                                                                                                                                                                                                                  

                                               Valid.  Negated formula closes on all branches.                                                                                                                                                                                                       

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                          

3.  Us a truth tree to determine whether the following is a contradiction.  Explain as above.  (2 pts.)

(p & q) → ¬(p v q)

                                      (p & q) → ¬(p v q)

                          ¬(p & q)                            ¬(pvq)                                                                                                                                                                                                               
                                                                           ¬p                                                                                                                                                                 
                                                                            ¬q                                                                                                                                                                               

                                                                                                                                                                                                                                           
      Not a contradiction.  Right branch remains open after all formulas dispatched.                                                                                                                                                                                                                                 

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                                      

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                                    

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                                     

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                                    

                                                                                                                                                                                                                                          

4.  Prove the following using natural deduction, direct proof method.  (2pts.)

p & ¬¬ q;  (r → s) & t    (¬¬t & q) &  p

                                                                                                                                                                                                                                                    
                                 1.  p & ¬¬q               	 A                                                                                                                                                                                         
                                 2. (r → s) & t			 A                                                                                                                                                                                                        
                                 3.  Show   (¬¬t & q) &  p                                                                                                                                                                                                     
                                 4.      p                              &E, 1                                                                                                                                                                                    
                                 5.      ¬¬q                          &E, 1                                                                                                                                                                        
                                 6.      q                              ¬¬,  5                                                                                                                                                                                     
                                 7.       t				 &E,  2                                                                                                                                                                                                  
                                 8.      ¬¬t                            ¬¬, 7                                                                                                                                                                            
                                 9.      (¬¬t & q)			  &I, 6,8
				10.      (¬¬t & q) &  p             &I   4,9                                                                                                                                                                                               

                                                                                                                                                                                                                                                     

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                                    

                                                                                                                                                                                                                                          

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                                      

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                                      

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                                      

                                                                                                                                                                                                                                           

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          

5.  Prove the following using natural deduction, indirect proof method.  (2pts.)

(p & s) → ¬( q & r);  (s & t) & p  ¬(r & q)    (2pts.)  

                                                                                                                                                                                                                                                    
                              	1.  (p & s) → ¬( q & r)  		A
				2.  (s & t) & p 			A
				3.    Show:   ¬(r & q)                                                                                                                                                                                                        
                                     4.        (r & q)			AIP
				5.    	  ( s & t)   			&E, 2                                                                                                                                                                                        
                                6.   	  s  				&E, 5                                                                                                                                                                                                       
                                7.  	  p    				&E, 2                                                                                                                                                                                                                 
                                8.   	  (p & s)			&I,  6,7
				9.	  r   				&E, 4                                                                                                                                                                                                   
                               10.       q 				&E, 4                                                                                                                                                                                                          
                               11.     (q & r) 			&I, 9,10                                                                                                                                                                                                          
                               12.    ¬(q & r)                     →E, 1,8