Need help with tautology proof without truth tables.

Question

I am trying to prove

$$[(p\to q)~\&~(q\to r)]\to (p\to r) $$

is a tautology using only logical laws. I have gotten part-way there but I got stuck and am not sure how to proceed.

Please state any laws that you use in your answers so that I can reference them.

~ = NOT
& = AND
V = OR
-> = IMPLIES

The Proof:

$$\begin{array}{ll} [(p\to q)~\&~(q\to r)]\to (p\to r); & \text{Given} \\ \sim[(\sim p\vee q)~\&~({\sim} q\vee r)]~\vee~({\sim} p\vee r); & \text{Material Implication} \\ [{\sim}({\sim} p~\vee~ q)\vee{\sim}({\sim} q\vee r)]\vee({\sim} p\vee r); & \text{DeMorgan's Law} \\ [(p~\&\,{\sim} q)\vee(q~\&\,{\sim} r)]\vee({\sim} p\vee r); & \text{DeMorgan's Law} \end{array}$$

Answer 1

First remove redundant brackets because V is associative:

(p&~q)V(q&~r)V~pVr

Then rearrange a little since V is commutative:

 ~pV(p&~q)VrV(q&~r)

Then we distribute the first two terms, and we distribute the last two:

[(~pVp)&(~pV~q)]V[(rVq)&(rV~r)]

We can cancel (~pVp) and (rV~r) because they're both tautologies (I don't know what you call that law) and because &-ing with a tautology doesn't change anything (I don't know what you call that law). Then again remove redundant brackets to get

~pV~qVrVq

and you should be able to see why this is a tautology.

Answer 2

Your next two steps:

• $(p\&\lnot q)\lor(q\&\lnot r)\lor\lnot p\lor r$ by association.

• $\lnot p\lor (p\&\lnot q)\lor(q\&\lnot r)\lor r$ by commutation.