Can you help me understand this logic proof?

**rowe** · February 23rd 2010, 05:07 AM

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

**clic-clac** · February 23rd 2010, 06:34 AM

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

**Nyrox** · February 23rd 2010, 06:42 AM

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.

**Plato** · February 23rd 2010, 06:50 AM

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

**xalk** · February 23rd 2010, 08:17 AM

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

**rowe** · February 23rd 2010, 10:15 AM

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?

**clic-clac** · February 23rd 2010, 11:02 AM

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

About something you wrote earlier, if you had assumed (for CP)

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

**xalk** · February 24th 2010, 01:08 AM

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

**rowe** · February 24th 2010, 05:51 AM

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.

Thread: Can you help me understand this logic proof?

LinkBack

Thread Tools

Display

Can you help me understand this logic proof?

Similar Math Help Forum Discussions

Struggling to understand logic tables and proposition

Do not quite understand this simple proof

Don't understand the proof of a simple theorem

i cant visualize/understand this convergence proof

Can't understand proof.

Search Tags