Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Hint :

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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