Mathematical Foundation of Computer Science

DHARM

PROPOSITIONAL LOGIC 125

Since we find the conclusion; therefore conclusion is valid at stage 3. Thus, conclusion is
valid at stage 2 at hence old conclusion must be valid.
IV. Rule of Indirect Proof

Example 5.21. Show that

1. A /∴ B ∨ ~ B
   Sol. In order to show that a conclusion follows logically from the premise/s, we assume that
   the conclusion is false. Take negation of the conclusion as the additional premise and start
   deduction. If we obtain a contradiction (s.t. R ∧ ~ R where, R is any formula) then, the negation
   of conclusion is true doesn’t hold simultaneously with the premises being true. Thus negation
   of conclusion is false. Therefore, conclusion is true whenever premises are true. Hence conclu-
   sion follows logically from the premises. Such procedure of deduction is known as Rule of
   Indirect Proof (IP) or Method of Contradiction or Reductio Ad Absurdum.
   Therefore,


2. A/∴ B ∨ ~ B


3. ~ (B ∨ ~ B) IP


4. ~ B ∧ ~ ~ B 2, Dem
   Since, we get a contradiction, so deduction process stops. Therefore, the assumption
   negation of conclusion is wrong. Hence, conclusion must be true.

Example 5.22. Show ~ (H ∨ J) follows logically from (H → I) ∧ (J → K), (I ∨ K) → L and ~ L.
Sol.

1. (H → I) ∧ (J → K)


2. (I ∨ K) → L


3. ~ L /∴ ~ (H ∨ J)


4. ~ (I ∨ K) 2 & 3, MT


5. ~ I ∧ ~ K 4, Dem


6. ~ I 5, Simp


7. ~ K ∧ ~ I 5, Comm


8. ~ K 7, Simp


9. H → I 1, Simp


10. ~ H 9 & 6, MT


11. (J → K) ∧ (H → I) 1, Comm


12. J → K 11, Simp


13. ~ J 12 & 8, MT


14. ~ H ∧ ~ J 13 & 10, Conj


15. ~ (H ∨ J) 14, DeM
    There is alternate method to reach the conclusion using Indirect Proof
    Since we have 1 – 3 premises; so


16. ~ ~ ((H ∨ J) Indirect Proof (IP)


17. H ∨ J 4, DeM


18. I ∨ K 1 & 5, CD


19. L 2 & 6, MP


20. L ∧ ~ L 7 & 3, Conj