Finding minimal form — Velleman exercise 1.5.7a

Question

I am self-studying out of Velleman's "How to Prove It", and am trying to solve exercise 7, part a from section 1.5. The problem is to show that

$$ (P \to Q) \land (Q \to R) = (P \to R) \land ((P \leftrightarrow Q) \lor (R \leftrightarrow Q)) $$

By converting the right-hand side to the equivalent AND/OR statements I was able to simplify the expression to

$$(\lnot P \lor Q) \land (\lnot Q \lor R) \land (\lnot P \lor R)$$

which is equivalent to the left-hand side (confirmed through truth tables, Venn diagrams, and Wolfram Alpha), but I am having trouble showing it analytically. Clearly, the first part of this statement is identical to the left-hand side. But I cannot figure out the analytical steps to show that $\lnot P \lor R$ cancels out of the statement. I've tried distributing the statements into each other completely, but I keeping ending up back at the above expression.

By converting back to conditional statements, the fact that $\lnot P \lor R$ is dispensable becomes intuitive to me. That is, it makes sense that $P \to Q$ and $Q \to R$ already implies that $P \to R$. However, I want to be able to show it analytically based on the Boolean laws and I've hit a wall there. I'm sure I'm missing something simple, but it's driving me crazy. Any hints?

Answer 1

To expand slightly on pedja's hint: The crux of the matter is to first show $$\left((\lnot P \lor Q) \land (\lnot Q \lor R)\right) \rightarrow (\lnot P \lor R)$$ and then that $$\left((A\land B)\land (A\rightarrow B)\right) \rightarrow A.$$

Addendum: One could also note that $A\land(A\rightarrow B) = A\land B$. Thus, if $A\rightarrow B$, $A = A\land B$.

Answer 2

Here is a full calculational solution, where we will use several times that $\;p \lor q \leftrightarrow q\;$ is an alternative way of writing $\;p \rightarrow q\;$. We will also use the fact that $\;\leftrightarrow\;$ is associative, so that we need not write parentheses in, for example, the 'golden rule': $$ p \;\leftrightarrow\; q \;\leftrightarrow\; p \land q \;\leftrightarrow\; p \lor q $$

Starting at the most complex side, we calculate \begin{align} & (P \to R) \;\land\; \big((P \leftrightarrow Q) \lor (R \leftrightarrow Q)\big) \\ = & \;\;\;\;\;\text{"$\;\lor\;$ distributes over $\;\leftrightarrow\;$, three times"} \\ & (P \to R) \;\land\; (P \lor R \;\leftrightarrow\; P \lor Q \;\leftrightarrow\; Q \lor R \;\leftrightarrow\; Q \lor Q) \\ = & \;\;\;\;\;\text{"use $\;P \rightarrow R\;$ rewritten as $\;P \lor R \leftrightarrow R\;$ in second part; simplify $\;Q \lor Q\;$"} \\ & (P \to R) \;\land\; (R \;\leftrightarrow\; P \lor Q \;\leftrightarrow\; Q \lor R \;\leftrightarrow\; Q) \\ = & \;\;\;\;\;\text{"reorder equivalents by symmetry of $\;\leftrightarrow\;$ -- this lets us introduce $\;\rightarrow\;$"} \\ & (P \to R) \;\land\; \big((P \lor Q \;\leftrightarrow\; Q) \;\leftrightarrow\; (Q \lor R \;\leftrightarrow\; R)\big) \\ = & \;\;\;\;\;\text{"rewrite $\;p \lor q \leftrightarrow q\;$ to $\;p \rightarrow q\;$, twice"} \\ & (P \to R) \;\land\; \big((P \rightarrow Q) \;\leftrightarrow\; (Q \rightarrow R)\big) \\ = & \;\;\;\;\;\text{"the golden rule -- to introduce our goal $\;(P \rightarrow Q) \land (Q \rightarrow R)\;$"} \\ & (P \to R) \;\land\; \big((P \rightarrow Q) \land (Q \rightarrow R) \;\leftrightarrow\; (P \rightarrow Q) \lor (Q \rightarrow R)\big) \\ = & \;\;\;\;\;\text{"$\;(P \rightarrow Q) \lor (Q \rightarrow R)\;$ is a tautology, see below"} \\ & (P \to R) \;\land\; (P \rightarrow Q) \;\land\; (Q \rightarrow R) \\ = & \;\;\;\;\;\text{"the leftmost conjunct is implied by the rest, by transitivity of $\;\rightarrow\;$"} \\ & (P \rightarrow Q) \;\land\; (Q \rightarrow R) \\ \end{align}

Above we used \begin{align} & (P \rightarrow Q) \lor (Q \rightarrow R) \\ = & \;\;\;\;\;\text{"write $\;p \rightarrow q\;$ as $\;\lnot p \lor q \;$, twice"} \\ & \lnot P \lor Q \lor \lnot Q \lor R \\ = & \;\;\;\;\;\text{"excluded middle"} \\ & \lnot P \lor \text{true} \lor R \\ = & \;\;\;\;\;\text{"excluded middle; simplify"} \\ & \text{true} \\ \end{align}

This completes the proof.

Answer 3

Hint :

$(P \rightarrow Q) \land (Q \rightarrow R) \rightarrow (P \rightarrow R)$