# $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I believe is the closest:

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

$(\lnot p \lor q) \wedge (\lnot q \lor r) \implies (p \implies r)$

$((\lnot p \lor q) \land \lnot q) \lor ((\lnot p \lor q) \land r) \implies(p \implies r)$

$((\lnot p \land \lnot q) \lor (q \lor \lnot q)) \lor ((\lnot p \land r) \lor (q \land r)) \implies (p \implies r)$

$(\lnot p \land \lnot q) \lor ((\lnot p \land r) \lor (q\land r)) \implies (p \implies r)$

and at this point, everything else I try seems to lead back to the same place.

EDIT: Besides the truth tables, I have:

$1.)$ $p \implies q$
$2.)$ $q \implies r$
$3.)$ $p$
$4.)$ If 1,3: $q$
$5.)$ If 2,4: $r$
$6.)$ By 1,2: $p \implies r$

• What rules are you allowed to use? – Hunan Rostomyan Apr 17 '14 at 18:07
• I suppose any/all. I have the truth tables and a proof of the hypothetical syllogism which I'm editing into the question here, but I believe he wants a manipulation. – user65384 Apr 17 '14 at 18:11
• Keep going that way: replace all $\Rightarrow$-signs by their corresponding disjunctions. By doing some manipulations similar to those you already made, you will eventually obtain a tautology. – punctured dusk Apr 17 '14 at 18:23
• Have you tried using truth tables? – Pubbie Apr 17 '14 at 18:43
• One rule that you may find useful that I didn't have when I had to do this same proof is that (p or q)=(q or p). The same with (p and q)=(q and p). – TheBluegrassMathematician Apr 17 '14 at 19:18

Here's one way of proceeding. Used the definition of →, as well as distribution and de morgan laws.

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

By the definition of →, the outermost conditional is turned into a disjunction:

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

The outermost negation is pushed in using a de Morgan law:

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

Remaining conditionals are also turned into a disjunctive form:

$$[((\lnot p \lor q) \land (\lnot q \lor r)) \land \lnot (\lnot p \lor r)].$$

The last conjunct is de Morgan'd to get this:

$$[((\lnot p \lor q) \land (\lnot q \lor r)) \land (p \land \lnot r)].$$

By the associativity of conjunction, we get to regroup things to get:

$$[(\lnot p \lor q) \land p] \land [(\lnot q \lor r) \land \lnot r].$$

Simultaneously distributing $p$ and $r$ in both conjuncts we get this:

$$[(\lnot p \land p) \lor (p \land q) ] \land [(\lnot q \land \lnot r) \lor (\lnot r \land r)].$$

Canceling the contradictory disjunctions there we obtain:

$$(p \land q) \land (\lnot q \land \lnot r).$$

Again, by associativity we can regroup that to this:

$$p \land (q \land \lnot q) \land \lnot r.$$

Which gives us this:

$$p \land \bot \land \lnot r.$$

Which reduces to:

$$\bot.$$

Therefore, the supposition was false, so we conclude that $[((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r)]$.

The usual direct proof would be considerably shorter. Here's an example.

Given $((p \rightarrow q) \land (q \rightarrow r))$, assume $p$, obtain $q$ from that assumption and the first conjunct by modus ponens. From $q$ with the second conjunct obtain $r$ by modus ponens again. Since from $p$ we've derived $r$, we have $(p \rightarrow r)$ by →-introduction. Since from $((p \rightarrow q) \land (q \rightarrow r))$ we've derived $(p \rightarrow r)$, again by →-introduction we conclude that $((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r)$.

• What is the significance of the negation in line 2? Does that distribute all the way to the right side? – user65384 Apr 17 '14 at 18:28
• Which one? The outermost? – Hunan Rostomyan Apr 17 '14 at 18:29
• not(not(p implies q).....or (p implies r) from line 2, which turns into (p implies q).......and not(p implies r) – user65384 Apr 17 '14 at 18:33
• @user65384 I wrote things a little more explicitly. Does it make sense now? – Hunan Rostomyan Apr 17 '14 at 18:47
• Now I understand, thank you. – user65384 Apr 17 '14 at 19:19