Mathematical Foundation of Computer Science

DHARM

PROPOSITIONAL LOGIC 121

Example 5.15. Show conclusion E follows logically from given premises:
A → B, B → C, C → D, ~ D and A ∨ E.
Sol. Given premises are,

1. A → B


2. B → C


3. C → D


4. ~ D


5. A ∨ E/∴ E
   (Apply rules of inference and obtain new
   premises until we reach to conclusion)


6. A → C 1 & 2, HS


7. A → D 6 & 3, HS


8. ~ A 7 & 4, MT


9. E 5 & 8, DS
   Thus we reach to conclusion; hence conclusion logically follows from given premises.
   In fact, there are possibly several different deductions (derivation sequences) to reach
   the conclusion. For this particular example, there is another possible deduction shown below.
   We have 1 – 5 premises, (Apply rules of inference and obtain new
   premises until we reach to conclusion)


10. ~ C 3 & 4, MT


11. ~ B 2 & 6, MT


12. ~ A 1 & 7, MT


13. E 5 & 8, DS
    Example 5.16. Show premises A → B, C → D, ~ B → ~ D, ~ ~ A, and (E ∧ F) → C will derive the
    conclusion ~ (E ∧ F).
    Sol. List the premises,


14. A → B


15. C → D


16. ~ B → ~ D


17. ~ ~ A


18. (E ∧ F) → C/∴ ~ (E ∧ F)
    (Apply rules of inference and obtain new
    premises until we reach to conclusion)


19. (A → B) ∧ (C → D)1 & 2, Conj


20. ~ A ∨ ~ C 6 & 3, DD


21. ~ C 7 & 4, DS


22. ~ (E ∧ F) 5 & 8, MT
    Since, we get the conclusion hence deduction process stop. Therefore conclusion is valid.
    Example 5.17. Show
    1.A ∧ B/∴ B
    Sol. Deduction using rules of inference could not solve this problem. (From the list of rules of
    inference no rule will applicable here). In other words the 9 rules of inference are not sufficient