Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {without truth table}

Question

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

Answer 1

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

Answer 2

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$

Answer 3

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).

Answer 4

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