Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

start of proof

That's what I have so far... It seems like a bad approach. I've tried others and end up in the same spot.

share|cite|improve this question
@Danikar: using a truth-table is not the method that the OP needs to use to prove the equivalence. – amWhy Jan 16 '13 at 23:02
I don't mean to be a bother, but what textbook is this particular problem from? – Mack Feb 13 '13 at 22:16
@Eli it's this one – papercuts Feb 14 '13 at 1:46
up vote 9 down vote accepted

What you've done in the first few steps is all correct. I'll start where you left off. We need to use a lot of distribution. And it gets messier before it gets clearer!

To prove $$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$ $$\vdots$$ $$\vdots$$

$$\equiv (p\land \lnot q) \lor (q \land \lnot r) \lor (\lnot p \lor r)\tag{picking up...}$$ $$\equiv [[(p\land \lnot q) \lor q] \land [(p \land \lnot q) \lor \lnot r]] \lor (\lnot p \lor r)\quad \tag{distributivity x 2}$$

$$\equiv [[(p\lor q) \land (\lnot q \lor q)] \land [(p\lor \lnot r)\land (\lnot q \lor \lnot r)]] \lor(\lnot p \lor r)\quad \quad\quad \quad\tag{distributivity x 2}$$

$$\equiv [(p \lor q) \land T \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \tag{$\lnot q \lor q \equiv T$}$$

$$\equiv [(p \lor q) \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \quad \quad \quad \tag{$(p \lor q) \land T \equiv (p \lor q)$} $$

Can you see how distribution (as discussed in an answer to your earlier question) helps here? We've eliminated one expression ($\lnot q \lor q \equiv T$), and if you proceed with expanding out, using distribution, on the expression to the left (in brackets), you will be able to eliminate other terms...ending with a final evaluation of $T$.

Why don't you work on it a bit to see what you arrive at, and post a follow up question in a comment below, or as an edit to this question if you run into problems.

Edit: continued from where we left off...

To prove:

$$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$ $$\vdots$$ $$\vdots$$

$$\equiv [(p \lor q) \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \quad \quad \quad \tag{$(p \lor q) \land T \equiv (p \lor q)$} $$ $$\equiv [(p \lor q) \land (\lnot q \lor \lnot r) \land (p\lor \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{Commutative property}$$

$$\equiv[[(p \lor q) \land \lnot q] \lor [(p \lor q) \land \lnot r] \land (p \lor \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{distributivity x 2}$$

$$\equiv[[(p\land \lnot q) \lor (q \land \lnot q) \lor (p \land \lnot r) \lor (q \land \lnot r)] \land (p \land \lnot r)] \lor (\lnot p \lor r) \quad\quad\quad\quad\quad \tag{distributivity}$$

$$\equiv [[(p \land \lnot q) \lor F \lor (p\land \lnot r) \lor (q \land \lnot r)] \land (p \land \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad\quad\quad\tag{$q \land \lnot q \equiv F$}$$

$$\equiv [[(p \land \lnot q) \lor \color{red}{\bf{(p\land \lnot r)}}\lor (q \land \lnot r)] \land \color{red}{\bf{(p \land \lnot r)}}] \lor (\lnot p \lor r) \quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad \tag{$(p \land \lnot r) \lor F \equiv p \land \lnot r)$}$$

$$\equiv \color{red}{\bf{(p \land \lnot r)}} \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{?}$$

$$\equiv (\lnot \lnot p \land \lnot r) \lor (\lnot p \lor r)\quad\quad\quad\quad\tag{Double negation}$$

$$\equiv \lnot( \lnot p \lor r) \lor (\lnot p \lor r) \quad\quad\quad \tag{DeMorgan's Law}$$

$$\quad \equiv T \quad\quad\quad\quad \tag{$\lnot a \lor a \equiv T$}$$

Hence, $$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$

Task: What remains is for you to justify/understand why the step followed by "$\,(?)\,$" holds.

share|cite|improve this answer It's just getting worse... – papercuts Jan 16 '13 at 4:08
I'll take a look at it...I got to a F (false) "or" term, and dropped it as well...but I'm going to need to get a little sleep. I'll look at it more carefully when I wake up. I think we can trim back a little on the work...but I'm proud of your effort! I'll get back to you! – amWhy Jan 16 '13 at 4:23
Thanks, you're awesome. Applying the distributive across 4 terms helped me with a different problem as well so double thanks ! – papercuts Jan 16 '13 at 4:38
@amWhy, your proof strategy is crazy! The formula $[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r)$ is true in a positive implicational calculus --- you do not have to introduce these negations, conjunctions and use the law of excluded middle. In fact the formula corresponds to the modus ponens rule, or to internal "composition": – Michal R. Przybylek Jan 17 '13 at 14:30
@amWhy - I don't agree. Papercuts proposed an approach and wrote "It seems like a bad approach". The correct answer to his question is "yes, it is a bad approach. Here is a (possible) right one.". What you have proposed is CRAZY! – Michal R. Przybylek Jan 17 '13 at 18:03

Let's assume that (1)$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$ is false for some assignment of $p$, $q$, and $r$. From the truth table for implication, this means that (2)$(p \rightarrow q) \land (q \rightarrow r)$ must be true while (3)$p \rightarrow r$ is false. From (2) we see that (4)$p \rightarrow q$ and (5)$(q \rightarrow r)$ must be true and from (3) we have (6)$p$ must be true while (7)$r$ is false. So from (4) and (6), $q$ must be true. But now we have a contradiction with (5) and (7). Therefore no assigment of $p$, $q$, and $r$ which will make the original statement false.

share|cite|improve this answer

Here is yet another proof: \begin{align} & ((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r) \\ \equiv & \;\;\;\;\;\text{"expand all occurrences of $\;\rightarrow\;$"} \\ & \lnot((\lnot p \lor q) \land (\lnot q \lor r)) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"in the first disjunct we may assume the negation of the others ($\;\lnot p\;$ and $\;r\;$)"} \\ & \lnot((\text{false} \lor q) \land (\lnot q \lor \text{false})) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \lnot(q \land \lnot q) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"excluded middle"} \\ & \lnot \text{false} \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \text{true} \\ \end{align}

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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