Answer to Question #285550 in Discrete Mathematics for dami

Question

Given The Following 2 Premises,

1. 𝑝→(𝑞∨𝑟)

2. 𝑞→𝑠

Prove 𝑝→(𝑟∨𝑠) Is Valid Using The Proof By Contradiction Method.

[Hint: Use A Combination Of Equivalence Laws And Rules Of Inference To Solve This Question]

Answer 1

Proof by Contradiction Method:

1. $p\rightarrow (q\lor r)$ Premise
2. $q\rightarrow s$ Premise
3. $\neg (p\rightarrow (r\lor s))$ Premise, proof by contradiction
4. $\neg (\neg p\lor (r\lor s))$ 3, Definition of $\rightarrow$
5. $p\land \neg (r\lor s)$ 4, DeMorgan’s law
6. $p$ 5, Specialization
7. $\neg (r\lor s)$ 5, Specialization
8. $\neg r\land \neg s$ 7, DeMorgan’s law
9. $\neg r$ 8, Specialization
10. $\neg s$ 8, Specialization
11. $\neg q$ 2, 10, Modus Tollens
12. $\neg q\land \neg r$ 9, 11
13. $\neg (q\lor r)$ 12, DeMorgan’s law
14. $\neg p$ 1, 13, Modus Tollens
15. False 6, 14, proof by contradiction

Premise $\neg (p\rightarrow (r\lor s))$ was false, so $p\rightarrow (r\lor s)$ must be true.