# Logic - how to prove $\;[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r) \equiv T\;$?

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

-
@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 amazon.com/gp/aw/d/0073383090 – papercuts Feb 14 '13 at 1:46

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.

-
i.imgur.com/8exCR.png 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.

-

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}

-