Answer to Question #289726 in Discrete Mathematics for Netu

Question

Given the following 2 premises, 1. 𝑝 → (𝑞 ∨ 𝑟) 2. 𝑞 → 𝑠 Prove 𝑝 → (𝑟 ∨ 𝑠) is valid using the Proof by Contradiction method. 

Answer 1

Solution:

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.