# Need to prove that a conditional statement is a tautology

The conditional statement is

$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$

Here are the steps I took in an attempt to prove the above statement a tautology, but I can't seem to understand what kind of reasoning I have to use to complete this problem.

LINK TO A TABLE OF LOGICAL EQUIVALENCES FOR YOUR CONVENIENCE : http://en.wikipedia.org/wiki/Logical_equivalence

$\lnot[(p \rightarrow q) \land (q \rightarrow r)] \lor (p \rightarrow r)$ (Because $p \rightarrow q = \lnot p \lor q$ )

$\lnot (p \rightarrow q) \lor \lnot ( q \rightarrow r) \lor (p \rightarrow r)$ (Because $\lnot(p \land q) = \lnot p \lor \lnot q$ )

At this point I just isolate and focus on the portion of the above that is:

$\lnot ( q \rightarrow r) \lor (p \rightarrow r)$

Then that can become:

$(p \rightarrow r)\lor \lnot ( q \rightarrow r)$ (Because of the commutative law)

$(p \rightarrow r) \lor q \land \lnot r$ (Because $\lnot(p \rightarrow q) = p \land \lnot q$)

$(p \rightarrow r) \lor \lnot r \land q$ (Because of the commutative law)

$(\lnot p \lor r) \lor \lnot r \land q$ (Because $p \rightarrow q = \lnot p \lor q$)

$\lnot p \lor ( r \lor \lnot r) \land q$ (Because of the associative law)

$\lnot p \lor T \land q$ (Because of negation)

$T \land q$ (Because $\lnot p \lor T$ is true no matter what)

I don't know how to get from this point to "and this is why the original conditional statement is true no matter what".

$(p \rightarrow r) \lor (q \land \lnot r)$ is not equivalent to $((p \rightarrow r) \lor \lnot r) \land q$.

$\lnot ( q \rightarrow r) \lor (p \rightarrow r)=\text{(...as you did...)}=(p \rightarrow r) \lor (q \land \lnot r)$

• $=(\lnot p \lor r) \lor (q \land \lnot r)$
• $=(\lnot p \lor (r \lor (q \land \lnot r))$
• $=(\lnot p \lor ((r \lor q) \land (r \lor \lnot r)))$
• $=(\lnot p \lor (r \lor q))$

So $\lnot (p \rightarrow q) \lor \lnot ( q \rightarrow r) \lor (p \rightarrow r)$

• $=\lnot (p \rightarrow q) \lor (\lnot p \lor (r \lor q))$
• $=(p \land \lnot q) \lor \lnot p \lor r \lor q$
• $=((p \lor \lnot p) \land (\lnot q \lor \lnot p)) \lor r \lor q$
• $=\lnot q \lor \lnot p \lor r \lor q$
• $=(\lnot q \lor q) \lor \lnot p \lor r$
• $=T$

I used the distributive law $p \lor (q \land r)=(p \lor q) \land (p \lor r)$ but the fact we needed is actually $p \lor (\lnot p \land q)=p \lor q$, which I believe is the absorption law.

• I didn't... it starts a new statement, the one you left off when you said to focus on the right two terms. – user1537366 Jan 25 '15 at 7:29
• I'm sorry I just don't see how (-p v (r v q)) is equivalent to -(q -> r) v ( p -> r) – user11892 Jan 25 '15 at 9:29
• @RogerVillanueva I proved it in the previous lines. You focused on those terms so I just did the same! – user1537366 Jan 25 '15 at 9:30