Mathematical Foundation of Computer Science

DHARM

120 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Rule 3. Hypothetical Syllogism (HP) Rule 4. Disjunctive Syllogism (DS)

(i)P → Q(i)P ∨ Q

(ii)Q → R(ii)~ P

∴ P → R ∴ Q

Rule 5. Constructive Dilemma (CD) Rule 6. Destructive Dilemma (DD)

(i) (P → Q) ∧ (R → S) (i) (P → Q) ∧ (R → S)

(ii)P ∨ R(ii)~ Q ∨ ~ S

∴ Q ∨ R ∴ ~ P ∨ ~ R

Rule 7. Simplification (Simp) Rule 8. Conjunction (Conj)

(i)P ∧ Q(i)P

∴ P (ii)Q

∴ P ∧ Q

Rule 9. Addition (Add)

(i)P

∴ P ∨ Q

Fig. 5.24
While derivation the rule will be acknowledge by its abbreviated name that was shown
in brackets.
Note. Reader must note that by applying rules of inference we extend the list of premises and
further all these premises including the new premises are equally participated in derivation process.
Example 5.14. Show that B → E is a valid conclusion drawn from the premises
A ∨ (B → D), ~ C → (D → E), A → C and ~ C.
Sol. First, we list the premises,

1. A ∨ (B → D)


2. ~ C → (D → E)


3. A → C


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


5. D → E 2 & 4, MP


6. ~ A 3 & 4, MT


7. B → D 1 & 6, DS


8. B → E 7 & 5, HS
   Since we reach to conclusion therefore, derivation process stops. Hence, premises 1-4
   derive the valid conclusion.