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

Question

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

Answer 1

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.

---

Answer 2

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.

Answer 3

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}