# Thread: Can you help me understand this logic proof?

1. ## Can you help me understand this logic proof?

$P \to (Q \to R) \vdash Q \to (P \to R)$.

First line of the proof is obv.,

$1. P \to (Q \to R)$ (A)
$2. Q$ (A)
$3. P$ (A)
$4. Q \to R$ (1,3 MP)
$5. R$ (2,4 MP)
$6. P \to R$ (3,5 CP)
$7. Q \to (P \to R)$ (2,6 CP)

I don't understand why it's just assuming lines 2 and 3. Couldn't I just assume R to be true as well and be done with the proof?

How do I know which variables to assume as true?

2. Hi

The idea is, to prove $A\rightarrow B,$ you assume $A$ and deduce $B.$

In your case, you have to repeat this, to prove $Q\rightarrow(P\rightarrow R)),$ you assume $Q$ and prove $P\rightarrow R,$ i.e. you assume $P$ and prove $R.$

3. I really don't see how that proof can be correct. The statement itself, however, is true. Indeed, consider the two Hilbert calculus axioms:

1. $\phi \Rightarrow (\psi \Rightarrow \phi)$
2. $((\phi \Rightarrow (\psi \Rightarrow \delta))\Rightarrow ((\phi \Rightarrow\psi)\Rightarrow(\phi \Rightarrow \delta))$

We then have

1. $P\Rightarrow (Q\Rightarrow R)$ (Hip)
2. $(P\Rightarrow (Q\Rightarrow R))\Rightarrow ((P\Rightarrow Q)\Rightarrow (P\Rightarrow R))$ (Ax 2)
3. $(P\Rightarrow Q)\Rightarrow (P\Rightarrow R)$ (MP 1,2)
4. $((P\Rightarrow Q)\Rightarrow (P\Rightarrow R))\Rightarrow (Q\Rightarrow ((P\Rightarrow Q)\Rightarrow (P\Rightarrow R))$ (Ax 1)
5. $Q\Rightarrow ((P\Rightarrow Q)\Rightarrow (P\Rightarrow R))$ (MP 3,4)
6. $(Q\Rightarrow ((P\Rightarrow Q)\Rightarrow (P\Rightarrow R)))\Rightarrow ((Q\Rightarrow (P\Rightarrow Q))\Rightarrow (Q\Rightarrow (P\Rightarrow R)))$ (Ax 2)
7. $(Q\Rightarrow (P\Rightarrow Q))\Rightarrow (Q\Rightarrow (P\Rightarrow R))$ (MP 5,6)
8. $Q\Rightarrow (P\Rightarrow Q)$ (Ax 1)
9. $Q\Rightarrow (P\Rightarrow R)$ (MP 7,8)

Given I'm extremely rusty with Hilbert calculi, there may be a shorter proof.

4. Originally Posted by rowe
$P \to (Q \to R) \vdash Q \to (P \to R)$.
$\begin{gathered}
P \to \left( {Q \to R} \right) \hfill \\
\neg P \vee \left( {\neg Q \vee R} \right) \hfill \\
\left( {\neg P \vee \neg Q} \right) \vee R \hfill \\
\left( {\neg Q \vee \neg P} \right) \vee R \hfill \\
\neg Q \vee \left( {\neg P \vee R} \right) \hfill \\
Q \to \left( {P \to R} \right) \hfill \\
\end{gathered}$

5. Originally Posted by rowe
$P \to (Q \to R) \vdash Q \to (P \to R)$.

First line of the proof is obv.,

$1. P \to (Q \to R)$ (A)
$2. Q$ (A)
$3. P$ (A)
$4. Q \to R$ (1,3 MP)
$5. R$ (2,4 MP)
$6. P \to R$ (3,5 CP)
$7. Q \to (P \to R)$ (2,6 CP)

I don't understand why it's just assuming lines 2 and 3. Couldn't I just assume R to be true as well and be done with the proof?

How do I know which variables to assume as true?
C P is for conditional proof .Somewhere in your book of propositional calculus that very important rule is explained in details .Make sure you understand completely the rule .Without it you cannot have any proofs in logic and mathematics.

The above proof is 100% correct.

In an axiomatic development of the propositional calculus conditional proof is mentioned as deduction theorem and is categorized as the most important meta-theorem

6. I understand the conditional proof part - after all, if P and R are true, then P -> R is going to be true.

I was more concerned about why we made the extra assumptions of Q and P. What if we assume Q and P, and we still arrive at that conclusion, when really ¬Q is true?

Or is it that, if I select the wrong assumptions, then I will be unable to prove what I want to prove?

And in this case, how do I make the right assumptions? Guesswork? Where are the clues to help me make the right assumptions?

7. What if we assume Q and P, and we still arrive at that conclusion, when really ¬Q is true?
Nothing For $A\rightarrow B$ to be true just asks that if $A$ is true, so is $B.$ That is exactly what CP means, you make an assumption $A,$ and if you can deduce $B$ from it, all you can conclude is $A\rightarrow B.$

$(2)Q$ (CPA)
$(3)P$ (CPA)
$(4)R$ (CPA)

then you would have gotten nothing better than:

$(5)R$ (A) (from the CPA (4))
$(6)R\rightarrow R$ (CP, 4,5)
$(7)P\rightarrow(R\rightarrow R)$ (CP, 3,6)
$(8)Q\rightarrow(P\rightarrow(R\rightarrow R)))$ (CP, 2,7)

Note that this last formula doesn't need any supplementary axiom, you can check it is a tautology (6,7,8 are), i.e. assuming R did not bring anything.

Or is it that, if I select the wrong assumptions, then I will be unable to prove what I want to prove?

And in this case, how do I make the right assumptions? Guesswork? Where are the clues to help me make the right assumptions?
Therefore yes, making "wrong" assumptions just won't help you. I guess it comes with practicing, you can guess what can be helpful from the form of the sentence you want to prove.
I only worked with different formal systems, so I don't know what are the rules you are allowed to use, but I think an important thing to do is to study these rules, particulary their conclusion, and then you'll be able to choose the good rule to apply. In a sense, start from the conclusion to see what can have been used to get it.

8. Originally Posted by rowe
I understand the conditional proof part - after all, if P and R are true, then P -> R is going to be true.

I was more concerned about why we made the extra assumptions of Q and P. What if we assume Q and P, and we still arrive at that conclusion, when really ¬Q is true?

Or is it that, if I select the wrong assumptions, then I will be unable to prove what I want to prove?

And in this case, how do I make the right assumptions? Guesswork? Where are the clues to help me make the right assumptions?

First of all in propositional calculus there are two kinds of proofs .

1)The Syntactical proof where the proof is purely mechanical and is done by using the laws of logic without any reference to the true or false value of the statements involved,and

2) The semantical proof where the true or false value of the statements involved are taken into consideration .In this kind of proof we may use the true tables ,or in general the rules concerning semantical proofs.

But is of no help at all if you start ask any questions ,without having spent enough time ,on reading and exercising in the book of the propositional calculus that you are advised to read.

The above proof is purely syntactical and the laws of logic involved in proving the desired result are:

The law of conditional proof (C.P) twice and the law of M.Ponens (M.P )twice as well.

And since the proof is syntactical it is of no use at all asking questions about the value of the statements ( true,false).

In this kind of proof you simple can ask whether the laws of logic involved are applied correctly on not

9. Originally Posted by xalk

But is of no help at all if you start ask any questions ,without having spent enough time ,on reading and exercising in the book of the propositional calculus that you are advised to read.
Wrong - I came here to get clarification on something I didn't understand in the book. You cannot just expect people to read and re-read something until they understand it as a valid pedagogical tool.