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

Hint :

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