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$$