Mathematical Foundation of Computer Science

DHARM

PROPOSITIONAL LOGIC 117

Now construct the truth table for X, we observe that formula X is not a tautology. There-
fore, argument is invalid. (Fig. 5.20)

RCR → C (R → C) ∧ C ((R → C) ∧ C) → R : X

FF T F T

FT T T F

TF F F T

TT T T T

Fig. 5.20 Truth table for X.

You will also see that argument is invalid for,

(i)R → C: T

(ii)C : T

∴ R: F

Example 5.11. Demonstrate that following argument is invalid.
(i) ((A → B) ∧ C) → D
(ii) A ∨ C
(iii) (B ∨ D) → (E ∧ F)
(iv) (E ∧ F) → G
(v) (G ∧ A) → H
∴ H

Sol. An argument is invalid if and only if, true (T) truth values of all premises must derive the
false (F) conclusion.
We assume that H is false (F),
· if H is F then (G ∧ A) must be F⇒ either G is F or A is F : from premise (v)
· if G is F then (E ∧ F) must be F⇒ either E is F or F is F : from premise (iv)
· if E is F then (B ∨ D) must be F⇒ B is F and D must be F : from premise (iii)
· Since D is F, so antecedent part of premise (i) must be F ⇒ either C is F or A is F
(since B is F and (A → B) is F so A is F).
Above discussed situation will be seen in Fig. 5.21.

B

D

→

→

false

false

Ao→→false rCfalse

H→false

GA∧→false

G→false or A→false

E→false or F→false

Fig. 5.21