# Need help with tautology proof without truth tables.

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.

~ = 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}$$

• You can remove the [] and the () around ~pVr because V is associative. Commented Sep 9, 2018 at 7:23
• after that, would I be able to do p & (~q V q) & r ? Commented Sep 9, 2018 at 7:26
• No, because V and & do not work together that nicely. Commented Sep 9, 2018 at 7:27
• yeah... that's what I thought. Would've been nice if I could. Yeah... I have no idea how to simplify this down more so it could easily be seen that this would only evaluate to true. Commented Sep 9, 2018 at 7:30

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.

• Thanks. This worked out. I should hopefully have no trouble solving the rest of the proofs I have to do. Also, the first rule I believe is called the "Negation Law" and the second is called the "Identity Law" Commented Sep 9, 2018 at 8:08

• $(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.
• Distribute the disjunction of $\lnot p$ over the nearest conjunction. $\neg p\lor (p\;\& \neg q) \equiv (\neg p\lor p)\;\&(\neg p\lor\neg q)$ . Likewise distribute the disjunction of $r$ over the nearest conjunction. Commented Sep 9, 2018 at 8:08