Question

Give a formal proof for the following tautology by using the IP rule.

(C →A) ^ (¬ C →B) →(A v B)

Answer 1

Given (C A) (¬ C B) (A V B)

(¬C V A) ¬(¬C B) V (A V B)  { Law of Implies (PQ) = ¬PVQ }

(¬C V A) ¬[¬(¬C) V B] V (A V B) { Law of Implies (PQ) = ¬PVQ }

(¬C V A) ¬[C V B] V (A V B)   {By De Morgan's law ¬ (¬ P) = P }

(¬C V A) [¬C ¬B] V (A V B) {By De Morgan's law ¬ (PVQ) = ¬P ¬Q}

(¬C V A)   (A V B) V [¬C ¬B]  { Commutative law P V Q = Q V P }

(¬C V A)   (A V B) V [¬B ¬C]  { Commutative law P Q = Q P }

¬C V (A A) V (B​​​​​​​ V ¬B) ¬C {Associative law (A B) C = A (B C)}

¬C V (A) V (T) ¬C {We know that P P = P}

¬C V (A V T) ¬C

¬C V (T) ¬C {We know that P V T = T}

(T) V ¬C ¬C

(T) V (¬C ¬C)

T V (¬C)  {We know that ¬P ¬P = ¬P}

T

Tautology