1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Hint :

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.