# Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land$ {without truth table}

Problem: Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$

Source: As was noted in the original post, this problem is from Daniel J. Velleman’s book How to Prove It. The exercise may be found as problem 7 (a) on page 54 (second edition). I got a copy of this book, and I saw that some exercises have solutions in the book. The exercise directly before this one had the solution, “Either make a truth table or reason as follows: […]”. This makes me think the author had a truth table solution in mind for this exercise, as a purely direct proof by using a chain of logical equivalences has proven to be exceedingly difficult. I am very interested in obtaining a solution that uses a chain of logical equivalences similar to my answer to this problem. I have spent several hours working on this problem now, but I have not succeeded at all–I cannot seem to “pull the right-hand side out of the left-hand side”, as this seems the most natural approach. For anyone interested, I have presented a truth table without the fluff below.

Truth table solution:

$$\boxed{ \begin{array}{c|c|c|c} P & Q & R & (P\to Q)\land (Q\to R) & (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)] \\ \hline T & T & T & T & T \\ T & T & F & F & F \\ T & F & T & F & F \\ T & F & F & F & F \\ F & T & T & T & T \\ F & T & F & F & F \\ F & F & T & T & T \\ F & F & F & T & T \end{array}}$$

Chain of equivalences proof: It seems that the main issue is “coaxing” the right-hand side out of the left-hand side. For instance, by using distributivity, I can see that somehow $(P\to Q)\land(Q\to R)$ is equivalent to
$$[(P\to R)\land(P\to Q)\land(Q\to P)]\lor[(P\to R)\land(R\to Q)\land(Q\to R)].\tag{1}$$
I have tried numerous times trying to manipulate the left-hand side into the expression given in $(1)$, but I have not succeeded so far–everything is such an enormous mess. Perhaps there is some strategy involved in using equivalences (in terms of ease of manipulation); for example, should one use
$$P\leftrightarrow Q\equiv (P\land Q)\lor(\neg P\land\neg Q)$$
or
$$P\leftrightarrow Q\equiv (P\to Q)\land (Q\to P)$$

#### Solutions Collecting From Web of "Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land$ {without truth table}"

There are several algorithms to convert classical propositional sentences into normal forms. I’ll pretend to be as dumb as a computer and convert the two sentences into their disjunctive normal form in a systematic way.

\begin{align}
& {(P \to R) \wedge [(P \leftrightarrow Q) \vee (R \leftrightarrow Q)]}\\
& = (\neg P \vee R) \wedge [(P \wedge Q) \vee (\neg P \wedge \neg Q) \vee (R \wedge Q) \vee (\neg R \wedge \neg Q)] \\
& = [(\neg P \vee R) \wedge P \wedge Q] \vee [(\neg P \vee R) \wedge \neg P \wedge \neg Q] \vee \\
& \phantom{{} = {}} [(\neg P \vee R) \wedge R \wedge Q] \vee [(\neg P \vee R) \wedge \neg R \wedge \neg Q] \\
& = [P \wedge Q \wedge R] \vee [(\neg P \wedge \neg Q) \vee (\neg P \wedge \neg Q \wedge R)] \\
& \phantom{{} = {}} \vee [(\neg P \wedge Q \wedge R) \vee (Q \wedge R)] \vee
[\neg P \wedge \neg Q \wedge \neg R] \\
& = (P \wedge Q \wedge R) \vee [(\neg P \wedge \neg Q \wedge \neg R) \vee (\neg P \wedge \neg Q \wedge R)] \vee\\
& \phantom{{}={}} [(\neg P \wedge Q \wedge R) \vee (P \wedge Q \wedge R)]
\vee [\neg P \wedge \neg Q \wedge \neg R] \\
& = (P \wedge Q \wedge R) \vee (\neg P \wedge \neg Q \wedge R) \vee (\neg P \wedge \neg Q \wedge \neg R) \vee (\neg P \wedge Q \wedge R).
\end{align}
\begin{align}
& (P \to Q) \land (Q \to R) \\
& = (\lnot P \lor Q) \land (\lnot Q \lor R) \\
& = [\lnot P \land \lnot Q] \lor [\lnot P \land R] \lor [Q \land R] \\
& = [(\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R)] \lor [(\lnot P \land Q \land R) \lor (\lnot P \land \lnot Q \land R)] \lor \\
& \phantom{{}={}} [(P \land Q \land R) \lor (\lnot P \land Q \land R)] \\
& = (\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R) \lor (P \land Q \land R).
\end{align}

Now you should see how the general method works. If you want to redo it without pretending to be as dumb as a computer, some steps can be skipped. In fact, the final form doesn’t have to be expanded out in full. You can just try to make both expressions look like this:

$$(Q \land R) \vee (\lnot P \land \lnot Q).$$

It is fairly approachable if you split up according to whether $Q$ is true or false.

For conciseness, call the two formulas be $\Phi$ and $\Psi$. We can show that each of them is equivalent to $(R\land Q) \lor (\neg P\land \neg Q)$, and therefore they are equivalent to each other.

More precisely, I will show that $\Xi\land Q \equiv \neg R\land Q$ and $\Xi\land \neg Q\equiv \neg P\land \neg Q$, for $\Xi\in\{\Phi,\Psi\}$. We then have
\begin{align} \Xi \equiv{}& \Xi\land (Q\lor \neg Q) \\ \equiv{}& (\Xi\land Q) \lor (\Xi\land \neg Q) \\ \equiv{}& (R\land Q) \lor (\neg P\land \neg Q) \end{align}

Thus there are four computations to do:
\begin{align} \Phi\land Q \equiv{}& (P\to Q)\land (Q\to R)\land Q \\ \equiv{}& (P\to Q)\land Q \land R \\ \equiv{}& Q\land R \end{align}

\begin{align} \Phi\land \neg Q \equiv{}& (P\to Q)\land (Q\to R)\land \neg Q \\ \equiv{}& (P\to Q)\land (\neg Q\lor R)\land \neg Q \\ \equiv{}& (P\to Q)\land \neg Q \\ \equiv{}& (\neg Q\to \neg P)\land \neg Q\\ \equiv{}& \neg P \land \neg Q \end{align}

\begin{align} \Psi\land Q \equiv{}& (P\to R)\land (P\leftrightarrow Q \lor R\leftrightarrow Q) \land Q \\ \equiv{}& (P\to R)\land ((P\leftrightarrow Q \land Q) \lor (R\leftrightarrow Q)\land Q)) \\ \equiv{}& (P\to R)\land ((P\land Q) \lor (R\land Q)) \\ \equiv{}& (P\to R)\land (P\lor R) \land Q\\ \equiv{}& (\neg P \lor R)\land (P\lor R) \land Q \\ \equiv{}& ((\neg P \land P) \lor R) \land Q \\ \equiv{}& (\bot \lor R) \land Q \\ \equiv{}& R \land Q \end{align}

\begin{align} \Psi\land \neg Q \equiv{}& (P\to R)\land (P\leftrightarrow Q \lor R\leftrightarrow Q) \land \neg Q \\ \equiv{}& (P\to R)\land ((P\leftrightarrow Q \land \neg Q) \lor (R\leftrightarrow Q)\land \neg Q)) \\ \equiv{}& (P\to R)\land ((\neg P\land \neg Q) \lor (\neg R\land \neg Q)) \\ \equiv{}& (P\to R)\land (\neg P\lor \neg R) \land \neg Q\\ \equiv{}& (\neg P \lor R)\land (\neg P\lor \neg R) \land \neg Q \\ \equiv{}& (\neg P \lor (R \land \neg R)) \land \neg Q \\ \equiv{}& (\neg P \lor \bot) \land \neg Q \\ \equiv{}& \neg P \land \neg Q \end{align}

Here I’ve used distribution plenty of times, as well as rules such as

• $(A\to B)\land A \equiv A\land B$
• $(A\to B)\land B \equiv B$
• $(A\lor B)\land A \equiv A$
• $(A\leftrightarrow B)\land A\equiv A\land B$

If you want a more intuitive proof of the forward direction (the more difficult one) that more displays the gist, probably the best thing is to first show the rule that $\vdash (Q \rightarrow P) \vee (R \rightarrow Q)$. This disjunction holds because

• $Q \rightarrow \bot$ entails $Q \rightarrow P$ ($Q \rightarrow \_$ considered as a function preserves entailment, and $\bot \vdash P$),
• $Q$ entails $R \rightarrow Q$,
• $\vdash (Q \rightarrow \bot) \vee Q$ (the law of excluded middle of classical logic).

Given the rule, it’s immediate that

$(P \rightarrow Q) \wedge (Q \rightarrow R) \vdash ((P \rightarrow Q) \wedge (Q \rightarrow R)) \wedge ((Q \rightarrow P) \vee (R \rightarrow Q))$.

It follows simply from distributivity that the right hand side (and thus the left hand side) of this entailment entails $(P \leftrightarrow Q) \vee (R \leftrightarrow Q)$. And it is easy to show that

$(P \rightarrow Q) \wedge (Q \rightarrow R) \vdash P \rightarrow R$.

Since a conjunction is entailed if (and only if) both conjuncts are entailed, you’re done (with the forward direction).

Here is an alternative chain-of-equivalences proof, which uses some laws of logic that may not be well-known.

\newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\equiv}{\leftrightarrow} \newcommand{\then}{\to} \newcommand{\followsfrom}{\gets} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}}Below, I will use the fact that $\;\equiv\;$ is associative; and to reduce the number of parentheses, I will just write, e.g., $\;\phi \equiv \psi \equiv \chi\;$. Also, I will use the fact that $\;\lor\;$ distributes over $\;\equiv\;$.

We start at the most complex side, and rewrite $\;(P \equiv Q) \;\lor\; (R \equiv Q)\;$ towards the left hand side, under the assumption that $\;P \then R\;$:

$$\calc (P \equiv Q) \;\lor\; (R \equiv Q) \op=\hint{\;\lor\; distributes over \;\equiv\;} P \lor (R \equiv Q) \;\equiv\; Q \lor (R \equiv Q) \op=\hint{\;\lor\; distributes over \;\equiv\;, twice} P \lor R \;\equiv\; P \lor Q \;\equiv\; Q \lor R \;\equiv\; Q \lor Q \op=\hints{assumption \;P \then R\; means \;P \lor R \equiv R\;;}\hint{simplify \;Q \lor Q\;; reorder equivalences} P \lor Q \;\equiv\; Q \;\equiv\; Q \lor R \;\equiv\; R \op=\hint{write \;\phi \lor \chi \equiv \chi\; as \;\phi \then \chi\;, twice} (P \then Q) \;\equiv\; (Q \then R) \op= \hints{write \;\phi \equiv \psi\; as \;(\phi \land \psi) \lor (\lnot\phi \land \lnot\psi)\;} \hint{– to introduce our goal \;(P \then Q) \land (Q \then R)\;} \big((P \then Q) \land (Q \then R)\big) \;\lor\; \big(\lnot (P \then Q) \land \lnot (Q \then R)\big) \op=\hint{write \;\phi \then \chi\; as \;\lnot \phi \lor \chi\;, and DeMorgan, twice} \big((P \then Q) \land (Q \then R)\big) \;\lor\; (P \land \lnot Q \land Q \land \lnot R) \op=\hint{contradiction: \;\lnot Q \land Q \;\equiv\; \false\;; simplify} (P \then Q) \;\land\; (Q \then R) \endcalc$$

Now we can wrap up the proof:

$$\calc (P \then R) \;\land\; \big((P \equiv Q) \lor (R \equiv Q)\big) \op=\hint{the above calculation} (P \then R) \;\land\; (P \then Q) \;\land\; (Q \then R) \op=\hint{\;\then\; is transitive} (P \then Q) \;\land\; (Q \then R) \endcalc$$