# 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! – Henning Makholm Feb 15 '17 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... – Ning Wang Feb 15 '17 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. – DanielV Feb 16 '17 at 7:25
• @DanielV Yes, I've found that I should just use those definitions to prove. – Ning Wang Feb 16 '17 at 7:26

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. – Ning Wang Feb 15 '17 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 '17 at 10:51

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. – skyking Feb 15 '17 at 9:35

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