# Is my proof of $((p\implies q)\land(q\implies r))\implies(p\implies r)$ correct?

My book use truth table(brute-force) for proving. But I want to know whether my proof is correct: $$LHS\equiv((\lnot p\lor q)\land(\lnot q\lor r)),$$ let $q$ be TRUE, $\top$, we have: $$((\lnot p\lor\top)\land(\bot\lor r))\equiv r,$$ let $q$ be FALSE, $\bot$, we have: $$((\lnot p\lor\bot)\land(\top\lor r))\equiv\lnot p.$$ Since (by some axiom) $q$ is either TRUE or FALSE: $$LHS\implies r\lor\lnot p,$$ which $$\lnot p\lor r\iff (p\implies r),$$ then we have $LHS\implies(p\implies r)$.

• In which formal system do you want the proof to be conducted? It's not enough just to say "some axioms", because in some systems what you want to prove is itself an axiom! Feb 15, 2017 at 9:01
• @HenningMakholm In some case that $p$ is not true doesn't imply $p$ is false. So I add the statement but I forget the name of the axiom/assumption... Feb 15, 2017 at 9:08
• Your "proof" is actually an informal argument. A formal proof requires a defined logic. But as an argument, it is a correct argument. Feb 16, 2017 at 7:25
• @DanielV Yes, I've found that I should just use those definitions to prove. Feb 16, 2017 at 7:26

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.

• A nice proof, but the question was whether the proof in the OP was correct or not. Feb 15, 2017 at 9:35

For the formula in the question, propositional logic is sufficient to prove it. If statements are either truth or false, it's also called truth-functional propositional logic. Alternatively, this is equivalent to a Boolean algebra. The axiom you didn't remember the name is the law of excluded middle.

Regarding the formula in the question, this is called the hypothetical syllogism. But regarding the proof: It is basically correct, but you could also get there by using the inference rules from logic to show that the formula is a tautology. I don't think you need the law of excluded middle to prove it.

• So the formal proof should be the one in @user373141 's? Btw, thanks for the links. Feb 15, 2017 at 9:58
• @N1ng You don't need any kind of "assume that $P/Q/R$ is true/false" to show that it is a tautogoly. Just use the basic laws of logic.
– tylo
Feb 15, 2017 at 10:51

However this depends on that the axioms and rules used are established at the point of the proof. This means the correctness depends on the formal system, axioms and the previously proven statements.

Especially what you rely on is that from $\phi \rightarrow \chi$ and $\neg\phi\rightarrow\psi$ you can conclude $\chi\lor\psi$ or alternatively expressed $(\phi \rightarrow \chi)\land(\neg\phi\rightarrow\psi)\rightarrow(\chi\lor\psi)$. Which itself can be prooved by truth tables.

As your book seem to use truth tables for proofs. This works fine for a system, it may look overly complicated, but it has it's advantage - it's a lot easier to "bootstrap" the system if one accept truth-tables for proofs.

$$\begin{array} {l|l:l} \hdashline 1 & \quad (p\to q) \wedge (q\to r) & \mathsf{Assume } \\ 2 & \quad (p\to q) & 1, \wedge\mathsf {Elimination} \\ 3 & \quad (q\to r) & 1, \wedge\mathsf {Elimination} \\ 4 & \quad (\neg q\to \neg p) & 2,\mathsf{Contraposition} \\ 5 & \quad (q\vee\neg q) & \textsf{Law of Excluded Middle} \\ 6 & \quad r\vee \neg p & 3,4,5,\textsf{Constructive Dilemma} \\ 7 & \quad p\to r & 6,{\to}\mathsf{Equivalence} \\ \hline \therefore & ((p\to q)\wedge(q\to r))\to (p\to r) & 1,6,{\to}\mathsf{Introduction} \end{array}$$
The Constructive Dilemma states $A\vee B, A\to C, B\to D\vdash C\vee D$ .
Alternatively: $\begin{array} {l|l:l} \hline 1 & \quad (p\to q) \wedge (q\to r) & & \text{assumption } 1 \\ 2 & \quad (p\to q) & 1, \wedge\mathsf E \\ 3 & \quad (q\to r) & 1, \wedge\mathsf E \\ \hdashline 4.1 & \qquad p & & \text{assumption } 2 \\ 4.2 & \qquad q & 2,4.1, \to\mathsf E \\ 4.3 & \qquad r & 3,4.2, \to \mathsf E \\ \hline 4 & \quad p\to r & 4.1,4.3, \to\mathsf I & \text{discharge } 2 \\\hline \therefore & (p\to q) \wedge (q\to r) \to (p\to r) & 1 ,4 , \to\mathsf E & \text{discharge }1 \end{array}$