4
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ What rules are you allowed to use? $\endgroup$ – Hunan Rostomyan Apr 17 '14 at 18:07
  • $\begingroup$ 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. $\endgroup$ – user65384 Apr 17 '14 at 18:11
  • $\begingroup$ 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. $\endgroup$ – punctured dusk Apr 17 '14 at 18:23
  • $\begingroup$ Have you tried using truth tables? $\endgroup$ – Pubbie Apr 17 '14 at 18:43
  • $\begingroup$ 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). $\endgroup$ – TheBluegrassMathematician Apr 17 '14 at 19:18
8
$\begingroup$

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

Suppose, for contradiction, that:

$$\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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.