0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Henning Makholm Feb 15 '17 at 9:01
  • $\begingroup$ @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... $\endgroup$ – Ning Wang Feb 15 '17 at 9:08
  • 1
    $\begingroup$ Your "proof" is actually an informal argument. A formal proof requires a defined logic. But as an argument, it is a correct argument. $\endgroup$ – DanielV Feb 16 '17 at 7:25
  • $\begingroup$ @DanielV Yes, I've found that I should just use those definitions to prove. $\endgroup$ – Ning Wang Feb 16 '17 at 7:26
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So the formal proof should be the one in @user373141 's? Btw, thanks for the links. $\endgroup$ – Ning Wang Feb 15 '17 at 9:58
  • $\begingroup$ @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. $\endgroup$ – tylo Feb 15 '17 at 10:51
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A nice proof, but the question was whether the proof in the OP was correct or not. $\endgroup$ – skyking Feb 15 '17 at 9:35
1
$\begingroup$

Your proof is basically correct.

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.

$\endgroup$
1
$\begingroup$

Your proof in a nutshell.

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

It is quite valid to use, though one could argue that this is not more fundamental than the Hyperthetical Syllogism which you are trying to prove.   You should be careful about that if you wish to avoid circularity.   [IE: Is CD itself provable without invoking HS?]


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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.