Asserting that when (P→Q) and (Q→R) are true, then so is (P→R)

Question

I am going through Velleman's "how to prove it", and am stuck on Problem 16 in section 3.2, which requires me to show, with the help of truth tables, that if $P\rightarrow Q$ and $Q\rightarrow R$ are true, then $P\rightarrow R$ is true.

I did the truth table; it shows that when $P\rightarrow Q$ and $Q\rightarrow R$ are true, then so is $P\rightarrow R$. But there are also instances where $P\rightarrow R$ is true and $P\rightarrow Q$ and $Q\rightarrow R$ are false. Is this indeed correct or did I do something wrong with the truth table?

Answer 1

The exercise requires me to show, with the help of truth tables, that if $P\rightarrow Q$ and $Q\rightarrow R$ are true, then $P\rightarrow R$ is true

Since we are reasoning completely abstractly, the exercise is essentially asking you to show that $$\Big((P\rightarrow Q)\land(Q\rightarrow R)\Big)\boldsymbol\to (P\rightarrow R)\tag1$$ is a tautology. Our previous discussion has established that this corresponds to its truth table having entirely T under its main connective.

\begin{array}{ccc|c@{}c@{}c@{}ccc@{}ccc@{}ccc@{}c@{}ccc@{}ccc@{}c@{}c} P&Q&R&(&P&\rightarrow&Q&)&\land&(&Q&\rightarrow&R&)&\rightarrow&(&P&\rightarrow&R&)\\\hline 1&1&1&&1&1&1&&1&&1&1&1&&\mathbf{1}&&1&1&1&\\ 1&1&0&&1&1&1&&0&&1&0&0&&\mathbf{1}&&1&0&0&\\ 1&0&1&&1&0&0&&0&&0&1&1&&\mathbf{1}&&1&1&1&\\ 1&0&0&&1&0&0&&0&&0&1&0&&\mathbf{1}&&1&0&0&\\ 0&1&1&&0&1&1&&1&&1&1&1&&\mathbf{1}&&0&1&1&\\ 0&1&0&&0&1&1&&0&&1&0&0&&\mathbf{1}&&0&1&0&\\ 0&0&1&&0&1&0&&1&&0&1&1&&\mathbf{1}&&0&1&1&\\ 0&0&0&&0&1&0&&1&&0&1&0&&\mathbf{1}&&0&1&0& \end{array}

But there are also instances where $P\rightarrow R$ is true, and $P\rightarrow Q$ and $Q\rightarrow R$ are false.

Sure: in these rows, sentence $(1)$ is indeed T.

If A is false and B true, then can "if A, then B" be true?

Yes: in this row (in fact, in every row where hypothesis A is false), we say that the implication "if A, then B" is vacuously true.

In the same row (A is false and B true), the bi-implication "A is equivalent to B", on the other hand, is certainly false.

Answer 2

You ask:

But there are also instances where $P\rightarrow R$ is true and $P\rightarrow Q$ and $Q\rightarrow R$ is false. Is this indeed correct or did I do something wrong with the truth table?

I think what you are thinking here is: 'Wait! If you can't go from $P$ to $Q$, and from $Q$ to $R$, then how can you go from $P$ to $R$?!'

Well, maybe you can get from $P$ to $S$, and from $S$ to $R$

Answer 3

Consider $(P \implies Q) \equiv (\neg P \vee Q)$. And $(Q \implies R) \equiv (\neg Q \vee R)$. Then combine the two assumptions, we get $(\neg P \vee Q) \land (\neg Q \vee R)$.

Case 1. If $\neg P$, we are done since the antecedent is false.

Case 2. If $(P \land Q)$, then $R$. This implies $(\neg P \vee R)$ which is $\equiv (P \implies R)$ as desired.

The above two cases exhausted all possibilities, hence we are done.

Answer 4

$S1: p\implies q \equiv q \lor !p$

$S2: q\implies r \equiv r \lor !q$

If $q$ is true then so is $S1$. We can only have $S2$ be true if $r$ is true. If $q$ is false, then S2 is true. We can only have $S1$ if $!p$. So $S1\land S2$ requires either $!p$ or $r$.

$S1 \land S2 \implies !p \lor r \equiv p \implies r$

Answer 5

I did the truth table; it shows that when $P→Q$ and $Q→R$ are true, then so is $P→R$. But there are also instances where $P→R$ is true and $P→Q$ and $Q→R$ are false. Is this indeed correct or did I do something wrong with the truth table?

It is correct.

Semantic entailment occurs exactly when: all interpretations of the variables that value the premises as true must also value the conclusion as true.

You do not need to consider what happens to the conclusion when one or more of the premises are false.

Answer 6

Fix a natural number n.

Take P := 4 | n

Q := n is odd

R := 2 | n

P $\to$ R is true. Neither P $\to$ Q nor Q $\to$ R are true.