# Using Rule of Inference, How to derive following conclusion from given premises?

Question is from the book: Discrete Mathematical Structures with Applications to CS by Tremblay and Manohar. It is an exercise problem. But, unfortunately, there is no help available on answers, or solutions of this book. I have tried to solve this problem but couldn't get the desired conclusion.

Premise 1: $$P \rightarrow Q$$,

Premise 2: $$(\neg Q \lor R) \wedge \neg R$$

Premise 3: $$\neg (\neg P \wedge S)$$

Conclusion: $$\neg S$$

Solution:

1. $$(\neg Q \lor R)$$ $$\wedge$$ $$-R$$..............[Introducing Premise 2]

2. $$(\neg Q \lor R)$$.........................[Tautologically Implies, 1, Simplification]

3. $$Q \rightarrow R$$.............................[Tautologically Implies, 2, Converting Disjuction To Implication]

4. $$P \rightarrow Q$$.............................[Introducing Premise 1]

5. $$P \rightarrow R$$.............................[Tautologically Implies, 4, 3, Transitivity Law]

6. $$\neg (\neg P \wedge S)$$.......................[Introducing Premise 3]

7. $$P \lor \neg S$$............................[Tautologically Implies, 6, DeMorgan's Law]

8. $$\neg S \lor P$$............................[Tautologically Implies, 7, Commutative Law]

9. $$S \rightarrow P$$............................[Tautologically Implies, 8, Converting Disjuction to Implication]

10. $$S \rightarrow R$$............................[Tautologically Implies, 9, 5, Transitivity]

11. $$\neg S \lor R$$............................[Tautologically Implies, 10, Converting Implication to Disjuction]

What wrong I did? I am getting $$\neg S \lor R$$ instead of $$\neg S$$

• You didn't take much benefit from premisse $2$. That's why you didn't get the desired conclusion. But your reasonning is Correct. – hamam_Abdallah Jul 2 '20 at 21:19

hint

From premisse $$2$$, use distributivity to get $$\lnot Q \wedge \lnot R$$ because $$R\wedge \lnot R$$ is false.

by simplification, you have $$\lnot Q$$.

by contrapositive of premmisse $$1$$, you get $$\lnot P.$$

Finally, using premisse $$3$$, De Morgan's law and disjunctive syllogism, you have the conclusion $$\lnot S$$.

• There it is... I really missed that one out. – Ubi hatt Jul 2 '20 at 21:23
• How do we get $\neg Q$ from $\neg Q\land\neg R$? – Invisible Jul 3 '20 at 11:42
• @Croissant by simplification . – hamam_Abdallah Jul 3 '20 at 13:53