# Discrete Math - Logic - Implication Problem

I am taking a discrete mathematics course, and I am currently studying the logic chapters of the textbook. The problem I am trying to solve at the moment says "Use truth tables to verify the following" which makes me assume that it expects the two compound statements being compared to be logically equivalent. Anyways this is the problem: $$(P\implies Q)\land(Q\implies R)\equiv (P\implies R).$$ When I set up the truth table for this problem, I am getting the answer that thee two statements are not logically equivalent. Perhaps this is right, but this problem has 4 other subproblems (a,b,c,d,....etc.), each of which had statements that were logically equivalent. Maybe I am over-thinking this, but any help, hint, or explanation is appreciated.

• They are not equivalent, as if $P,R$ are true and $Q$ is false, the left side is false and the right is true. It is true as an implication. – Ross Millikan Sep 10 '13 at 20:00

## 3 Answers

You are correct that $$(P \rightarrow Q) \land (Q \rightarrow R) \not\equiv P\rightarrow R$$

It is true that $$\Big((P\rightarrow Q) \land (Q\rightarrow R)\Big) \rightarrow (P \rightarrow R)$$ (You can confirm that this is a tautology by consulting its truth-table.)

But if $Q$ is false, and P is true, and R is true, the left hand side is false, but the righthand side is true, so the implication is not bidirectional.

• Clean write up (missing a closing parens in "(You .... +1 – Amzoti Sep 11 '13 at 1:33

I think you're meant to be proving $$\big((P \implies Q) \wedge (Q \implies R)\big) \implies (P \implies R)$$ is a tautology. This is true, as per the following truth table: $$\begin{array}{|ccc|ccc|c|c|} \hline P & Q & R & P \implies Q & Q \implies R & (P \implies Q) \wedge (Q \implies R) & P \implies R & \text{above} \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array}$$ Comparing the last two columns, we see the identity holds.

The statement above is true, because the implication is false only if the premise is true and the conclusion is false.

• Don't write in uppercase, it looks like you are yelling – Alan Simonin Mar 15 '15 at 11:08