8
$\begingroup$

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?

$\endgroup$
7
  • 2
    $\begingroup$ See Hypothetical syllogism $\endgroup$ Commented May 2, 2023 at 10:53
  • 11
    $\begingroup$ You did nothing wrong. It is indeed correct -- what makes you think it can't be? $\endgroup$
    – TonyK
    Commented May 2, 2023 at 10:54
  • 1
    $\begingroup$ The "follows from" relation is tested with truth table showing that in ALL cases where the premises are True, also the conclusion is (see Logical consequence). $\endgroup$ Commented May 2, 2023 at 10:54
  • 1
    $\begingroup$ If $P\to\lnot Q$ and $\lnot Q\to R$ are true then $P\to R$ is also true, so if you have $P\to R$ you cannot infer either premise. . $\endgroup$
    – JMP
    Commented May 2, 2023 at 10:59
  • 2
    $\begingroup$ This is sometimes called vacuous truth. "False implies anything" is true. $\endgroup$ Commented May 2, 2023 at 15:55

6 Answers 6

7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ that's a counterexample right? $\endgroup$
    – eeqesri
    Commented May 2, 2023 at 11:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .