Prove that $(p \to q) \land (q \to r)$ is equivalent to $p \to r$

Question

$(P\implies Q)\land(Q\implies R)$ is equivalent to $P\implies R$. Is this true? How to prove this directly, not using truth tables?

Answer 1

If $P$ and $R$ are true, then $P \implies R$ is true no matter what $Q$ is. So just choose a $Q$ to make one of the statements $P \implies Q$ and $Q \implies R$ become false, then the two sides don't agree. In this case choosing $Q$ to be false works.

Answer 2

They aren’t equivalent. You mentioned wanting a proof without truth tables, but here is one, anyway. $\newcommand{\tru}{{\color{#0c0}T}}$ $\newcommand{\fal}{{\color{#c00}F}}$ \begin{array}{|c|c|c|c|c|} \hline P & Q & R & (P \Rightarrow Q) \wedge (Q \Rightarrow R) & P \Rightarrow R \\ \hline \fal & \fal & \fal & \tru & \tru \\ \fal & \fal & \tru & \tru & \tru \\ \fal & \tru & \fal & \fal & \tru \\ \fal & \tru & \tru & \tru & \tru \\ \tru & \fal & \fal & \fal & \fal \\ \tru & \fal & \tru & \fal & \tru \\ \tru & \tru & \fal & \fal & \fal \\ \tru & \tru & \tru & \tru & \tru \\ \hline \end{array}

It is true, however, that

$$(P \Rightarrow Q) \wedge (Q \Rightarrow R) \text{ implies } P \Rightarrow R.$$

Answer 3

$\begin{align} & \underline{\begin{align} & P\to Q\Leftrightarrow \,\sim P\vee Q \\ & Q\to R\Leftrightarrow \,\sim Q\vee R \\ \end{align}} \\ & (P\to Q)\wedge (Q\to R)\Leftrightarrow (\sim P\vee Q)\wedge (\sim Q\vee R) \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Leftrightarrow [(\sim P\vee Q)\wedge \sim Q]\vee [(\sim P\vee Q)\wedge R] \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Leftrightarrow [(\sim P\wedge \sim Q)\vee \underbrace{(Q\,\wedge \sim Q)}_{F}]\vee [(\sim P\wedge R)\vee (Q\,\wedge R)] \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Leftrightarrow (\sim P\wedge \sim Q)\vee (\sim P\wedge R)\vee (Q\,\wedge R) \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Leftrightarrow \,\,\sim P\wedge (\sim Q\vee R)\vee (Q\,\wedge R) \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Leftrightarrow \,\,\sim P\wedge [(\sim Q\vee R)\vee (Q\,\wedge R)] \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Leftrightarrow \,\,\sim P\wedge [(\sim Q\vee R)\vee (Q\,\wedge R)] \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Leftrightarrow \,\,\sim P\wedge (\,\underbrace{[(\sim Q\vee R)\vee Q\,]}_{R}\wedge \underbrace{[(\sim Q\vee R)\vee R}_{\sim Q\vee R}\,]) \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\ \to \,\,\sim P\wedge R \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\ \to \,\,P\to R \\ \end{align}$

Answer 4

$(p \to q) \land (q \to r) \implies (p \to r)$

$(p \to r)$ means that everytime $p$ is true, then $r$ is also true.

From the left side $\left(p \to q\right)$, we have that when $p$ is true, then $q$ is true. From the left side $\left(q \to r\right)$, we have that when $q$ is true then so is $r$. Then $(p \to r)$, like the right side says. So the left side implies the right side.

To check that the converse is not true (the right side DOES NOT implies the left side), check @coffeemath answer. So the expressions are not equivalent.

Answer 5

These two statements are clearly not equivalent:

• If $p$ is divisible by 4, then it's even.
• If $p$ is divisible by 4, then pigs can fly. Furthermore, if pigs can fly, then $p$ is even.

So the equivalence can't hold in general.