Section 1.2 Problem 12 b

Prove that [(p -> q) ^ (q -> r)] -> (p -> r) is a tautology.

1 = ~[(~p v q) ^ (~q v r)] v (~p v r) by OULE - (p => q) = ~p v q
2 = [~(~p v q) v ~(~q v r)] v (~p v r) by DeMorgans
3 = [(p ^ ~q) v (q ^ ~r)] v (~p v r) by deMorgans and Double Negation
4 = [((p ^ ~q) v q) ^ ((p ^ ~q) v ~r)] v (~p v r) by commutative and distributive
5 = [((q v p) ^ (q v ~q)) ^ ((p ^ ~q) v ~r)] v (~p v r) by Negation and Identity
6 = [(q v p) ^ ((p ^ ~q) v ~r)] v (~p v r) by commutative and distributive
7 = ((~p v r) v (q v p)) ^ ((~p v r) v ((p ^ ~q) v ~r)) by commutative and associative
8 = (p v ~p) v (q v r) ^ ((r v ~r) v (~p v (p ^ ~q))) by Negation
9 = (T v (q v r)) ^ (T v (~p v (p ^ ~q))) by commutative and domination
10 = T ^ T = T

(taken from another student in class)