Question

Do the following proofs deductively. Justify each step in your proof with a law or inference rule.

a) If P ⇒ Q, ¬R ⇒¬Q, and P then prove R.

b) If P ⇒ (Q ∧ R) and ¬R ∧ Q then prove ¬P.

Answer 1

a) (P Q) ( ¬R ¬Q) P

(¬P V Q) ( ¬(¬R) V ¬Q) P  { Law of Implies (AB) = ¬AVB }

(¬P V Q) ( R V ¬Q) P { By Demorgan's law ¬( ¬A) = A }

.(¬P V Q) ( ¬Q V R) P { Commutative law A V B = B V A }

.¬P V (Q ¬Q) V R P { Associative law (A V B) V C  = A V ( B V C ) }

.¬P V (F) V R P  { We know that A   ¬A = F }

.¬P V P (F) V R { Commutative law A V B = B V A }

​​​​​​​.(¬P V P) (F) V R  { Associative law (A V B) V C  = A V ( B V C ) }

​​​​​​​​​​​​​​.(T) (F) V R { We know that A V ¬A = T }

​​​​​​​​​​​​​​.(T F) V R

​​​​​​​​​​​​​​.( F) V R { We know that T F = F }

R  { We know that F V A = A }

Hence Proved

b) P (Q R) (¬R ∧ Q)

P Q (R ¬R) ∧ Q  { Associative law (A V B) V C  = A V ( B V C ) }

P Q (F) ​​​​​​​Q { We know that A   ¬A = F }

P Q Q (F)   { Commutative law A V B = B V A }

P ( Q​​​​​​​ Q ) (F)

P ( Q​​​​​​​) (F)  { We know that A A = A }

¬P V ( Q​​​​​​​) (F)   { Law of Implies (AB) = ¬AVB }

¬P V ( Q​​​​​​​ F)  

¬P V ( F)  { We know that A F = F }

(¬P V F)

¬P   { We know that F V ¬A = ¬A }

​​​​​​​Hence Proved