Mathematical Foundation of Computer Science

DHARM

122 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

to solve the problem. Hence, we have another 10 rules. These rules are called rules of replace-
ment that are listed in Fig. 5.25.

II. Rules of Replacement

Rule 1. De Morgan’s (DeM) Rule 2. Commutation (Comm)

(i) ~ (P ∨ Q) ⇔ ~P ∧ ~ Q, (i) (P ∨ Q) ⇔ Q ∨ P

(ii) ~ (P ∧ Q) ⇔ ~P ∨ ~ Q (ii) (P ∧ Q) ⇔ Q ∧ P

Rule 3. Association (Assoc) Rule 4. Distribution (Dist)

(i) (P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) (i)P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)

(ii)(P∧ Q) ∧ R ⇔ P ∧ (Q ∧ R) (ii)P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)

Rule 5. Double Negation (DN) Rule 6. Transportation (Trans)

~ ~ P ⇔ PP → Q ⇔ ~ Q → ~ P

Rule 7. Material Implication (Imp) Rule 8. Explanation (Exp)

P → Q ⇔ ~ P ∨ Q (P ∧ Q) → R ⇔ P → (Q → R)

Rule 9. Tautology (Taut) Rule 10. Equivalence (Equiv)
(i)P ⇔ P ∧ P (P → Q) ∧ (Q → P) ⇔ (P ∧ Q) ∨ (~P ∧ ~ Q)
(ii)P ⇔ P ∨ P
Fig. 5.25
The major difference between rules of inference and the rules of replacement is that, rules
are inference applies over full line but rules of replacement apply on part of line also.
Now attempt the problem of example 5.17 and solve.

1. A ∧ B/∴ B
   (Apply rules of inference and rules of
   replacement whenever required and obtain
   new premises until we reach to conclusion)


2. B ∧ A 1, Comm


3. B 2, Simp
   Thus, we obtain the required conclusion, hence deduction stop.

Example 5.18. Verify the argument

1. (A ∨ B) → (C ∧ D)


2. ~ C / ∴ ~ B
   (Apply rules of inference and rules of replacement
   whenever required and obtain new premises until
   we reach to conclusion)


3. ~ C ∨ ~ D 2, Add


4. ~ (C ∧ D) 3, DeM


5. ~ (A ∨ B) 1 & 4, MT


6. ~ A ∧ ~ B 5, DeM


7. ~B ∧ ~ A 6, Comm


8. ~ B 7, Simp