Question

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

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

Answer 1

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

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

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

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

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

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

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

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

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

  A (¬A ¬B) V [(T) (T)]   {We know that P V ¬ P = T}

(A ¬A) ¬B V [ (T) ] {We know that T T = T}

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

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

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

T

Tautology