How do I prove the transitivity of a set of implications?

Question

If I have a set of implications, how can I prove the transitivity? In other words: I know the transitivity law, but I need to show on paper for an assignment whether the argument is valid or not.

$$ \begin{align} P&\to Q\\ Q&\to R \\ \therefore P&\to R \end{align} $$

I recall something to do with assuming P and/or Q, since $P\to Q$ will always be true if P is false anyhow, and the same with $Q\to R$... but I don't know how to do it on paper.

Answer 1

$$(1) P\rightarrow Q\tag{Hypothesis}$$ $$(2) Q\rightarrow R\tag{Hypothesis}$$ $$\quad\quad\underline{(3)\; P\quad }\tag{Assumption}$$ $$\quad \quad\quad |(4) Q \tag{1 and 3: Modus Ponens}$$ $$\quad\quad\quad |(5) R \tag{2 and 4: Modus Ponens}$$ $$(6) P \rightarrow R \tag{3 - 5: if P, then R}$$

$$\therefore ((P\rightarrow Q)\land (Q\rightarrow R))\rightarrow (P\to R)$$
(Note: step 6 is sometimes justified by "conditional introduction": together with what you are given or have established, if by assuming P, you can derive R, then you have shown $P \rightarrow R$).

---

Note: when I first learned propositional logic, once it was established (proven), we referred to the following "syllogism": $$P\to Q\\ \underline{Q\to R}\\ \therefore P\to R\quad$$ by citing it as the "Hypothetical Syllogism", for justification in future proofs.

Answer 2

Since the logic you are using is not quantified, and there are only three variables, you can prove the argument valid with an eight row truth table covering all of the possible truth values of the three variables:

P  Q  R    Premise:  P -> Q    Premise:  Q -> R:    Conclusion:  P -> R
------------------------------------------------------------------------
0  0  0                 1                   1               1
0  0  1                 1                   1               1
0  1  0                 1                   0               1
0  1  1                 1                   1               1
1  0  0                 0                   1               0
1  0  1                 0                   1               1  
1  1  0                 1                   0               0
1  1  1                 1                   1               1

Now an argument is valid if the conclusion is true whenever all the premises are true. This means that in all the rows where both premises have a 1, we check whether the conclusion has a 1. By golly, this is the case. Therefore the argument is valid!

If we found a zero, that would be a counterexample which destroys the argument: a situation where the premises are all true, yet the conclusion is false.

In my table, the P -> Q column and its siblings are simply derived from the truth table for the conditional. P -> Q is only false when P is true, and Q is false, and true for the other three possible values of the variables.

Answer 3

Denote by $+$ the $or$ logic operator and by $\cdot$ the $and$ logic operator.

We have $(A\Rightarrow B)=\bar A+B$ and $(B\Rightarrow C) =\bar B+C$

Assume $(\bar A + B)=1=(\bar B+C)$.

Then $1=1\cdot 1=(\bar A + B)\cdot (\bar B+C) \\ = (\bar A\bar B + \bar A C + B\bar B + BC)\\ = \bar A + BC = (\bar A + B) \cdot (\bar A+C) \\ =\bar A + C $

Answer 4

I'm not sure about what notations you might use nor if you're using a natural deductive system, but this is the idea behind what you asked:

Suppose $P\to Q\\ Q\to R\\$ are true.

We want to prove that $P\to R$ is true.

To do this suppose $P$ is true.

Because $P\to Q$ is true it follows that $Q$ is true. Now because $Q$ is true, from $Q\to R$ being true follows that $R$ is true.

We assumed $P$ was true and we deduced that $R$ is also true, therefore $P\to R$ as we wanted.

Answer 5

Although it is late, I wanted to give a simple and convincing demonstration:

(1) P -> Q (Hypothesis)
(2) Q -> R (Hypothesis)
(3) ¬Q -> ¬P (Contraposition (1))
(4) (Q -> R) ∧ (¬Q -> ¬P) (Union (2) and (3))
(5) Q ∨ ¬Q (Law of excluded middle)
(6) (Q -> R) ∧ (¬Q -> ¬P) ∧ ( Q ∨ ¬Q) (Union (4) and (5) )
  ____________________________
  (R ∨ ¬P)  (Dilemma of (6), P -> R=def.(R ∨ ¬P) Definition of logical implication)

Answer 6

The answer for $6$ is indeed, true but if you had to show it with a truth table would be as follows

$$\begin{array}{cccccccc}P & Q & R & P\!\rightarrow\! Q & Q\!\rightarrow\! R & P\!\rightarrow\! R & (P\!\rightarrow\! Q)\!\wedge\!(Q\!\rightarrow\! R) & [(P\!\rightarrow\! Q)\!\wedge\!(Q\!\rightarrow\! R)]\!\rightarrow\! (P\!\rightarrow\! R)\\ T & T & T & T & T & T & T & T\\ T & T & F & T & F & F & F & T\\ T & F & T & F & T & T & F & T\\ T & F & F & F & T & F & F & T\\ F & T & T & T & T & T & T & T\\ F & T & F & T & F & T & F & T\\ F & F & T & T & T & T & T & T\\ F & F & F & T & T & T & T & T\end{array}$$

---

As you notice above the column $(P\!\rightarrow\! Q)\!\wedge\!(Q\!\rightarrow\! R)$ is the same as the column of $(P\!\rightarrow\! R).$ So with both the hypotheses $(P\!\rightarrow\! R)$ and $(Q\!\rightarrow\! R)$ we can conclude that $(P\!\rightarrow\! R).$