Results 1 to 9 of 9

Math Help - Can you help me understand this logic proof?

  1. #1
    Member rowe's Avatar
    Joined
    Jul 2009
    Posts
    89

    Thumbs down 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    From
    Lisbon
    Posts
    51
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,649
    Thanks
    1597
    Awards
    1
    Quote Originally Posted by rowe View Post
    P \to (Q \to R) \vdash Q \to (P \to R).
    \begin{gathered}<br />
  P \to \left( {Q \to R} \right) \hfill \\<br />
  \neg P \vee \left( {\neg Q \vee R} \right) \hfill \\<br />
  \left( {\neg P \vee \neg Q} \right) \vee R \hfill \\<br />
  \left( {\neg Q \vee \neg P} \right) \vee R \hfill \\<br />
  \neg Q \vee \left( {\neg P \vee R} \right) \hfill \\<br />
  Q \to \left( {P \to R} \right) \hfill \\ <br />
\end{gathered}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by rowe View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member rowe's Avatar
    Joined
    Jul 2009
    Posts
    89
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by rowe View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member rowe's Avatar
    Joined
    Jul 2009
    Posts
    89
    Quote Originally Posted by xalk View Post

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Struggling to understand logic tables and proposition
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 24th 2011, 01:06 AM
  2. Do not quite understand this simple proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: August 5th 2010, 04:34 AM
  3. Don't understand the proof of a simple theorem
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 15th 2009, 12:55 PM
  4. Replies: 1
    Last Post: December 13th 2008, 03:27 AM
  5. Can't understand proof.
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 7th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum