Results 1 to 2 of 2

Math Help - classical logic - proofs via natural deduction

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    classical logic - proofs via natural deduction

    Hi,

    I've recently started working through an introduction to logic work book and I am having a lot of trouble generating proofs using natural deduction. I understand the rules, but have difficulty figuring out when to apply them and how to properly discharge assumptions.

    Here are a couple of problems that are spinning my head at the moment:

    1. I would like to prove the following theorem:

    (p => r) => ((q => p) => (q => r))

    It seems to me that this proof will rely heavily on the conditional proof (CP) rule. Beyond that, I'm not sure how to proceed. Should I start by assuming the antecedent of the entire string (p => r), or do I need to attack the bracketed section first?

    2. I would like to translate the following argument and then prove that it is valid.

    Mice are not welcome if and only if mice and rats are not welcome. If Tanya is a reliable witness, then rats are welcome. If it's not true that if Tanya is not a reliable witness mice are welcome, then mice are welcome. Therefore, mice are welcome.

    This is what I've tried so far as a translation:

    (p) Mice are not welcome
    (q) Rats are not welcome
    (r) Tanya is a reliable witness

    1) p <=> (p ^ r)
    2) r => !q
    3) !(!r => !p) => !p
    C) !p

    I'm very uncertain of my reading of premise 3. I'm not 100% confident on my translations of the other premises either. However, even taking this into account, I'm not really sure how to proceed with the proof. I would start by assuming the premises:

    1 1 p <=> (p ^ r) A
    2 2 r => !q A
    3 3 !(!r => !p) => !p A

    But once the real work begins, I'm drawing a blank. I understand from my reading that I should target the conclusion and try and use valid rules to reach it. As the conclusion is !p, it seems that proving the antecedent of premise 3 is probably the best way to get there. I'm really unsure though.

    If someone was willing to help me not only solve the problems, but understand the process taken to do so, it would be hugely appreciated. I'm determined to figure it out, but if I go it alone I fear I'll still be sitting here tearing my hair out two weeks from now!

    Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2007
    From
    Moldova
    Posts
    15
    Quote Originally Posted by sanktum View Post
    Hi,

    I've recently started working through an introduction to logic work book and I am having a lot of trouble generating proofs using natural deduction. I understand the rules, but have difficulty figuring out when to apply them and how to properly discharge assumptions.

    Here are a couple of problems that are spinning my head at the moment:

    1. I would like to prove the following theorem:

    (p => r) => ((q => p) => (q => r))

    It seems to me that this proof will rely heavily on the conditional proof (CP) rule. Beyond that, I'm not sure how to proceed. Should I start by assuming the antecedent of the entire string (p => r), or do I need to attack the bracketed section first?

    2. I would like to translate the following argument and then prove that it is valid.

    Mice are not welcome if and only if mice and rats are not welcome. If Tanya is a reliable witness, then rats are welcome. If it's not true that if Tanya is not a reliable witness mice are welcome, then mice are welcome. Therefore, mice are welcome.

    This is what I've tried so far as a translation:

    (p) Mice are not welcome
    (q) Rats are not welcome
    (r) Tanya is a reliable witness

    1) p <=> (p ^ r)
    2) r => !q
    3) !(!r => !p) => !p
    C) !p

    I'm very uncertain of my reading of premise 3. I'm not 100% confident on my translations of the other premises either. However, even taking this into account, I'm not really sure how to proceed with the proof. I would start by assuming the premises:

    1 1 p <=> (p ^ r) A
    2 2 r => !q A
    3 3 !(!r => !p) => !p A

    But once the real work begins, I'm drawing a blank. I understand from my reading that I should target the conclusion and try and use valid rules to reach it. As the conclusion is !p, it seems that proving the antecedent of premise 3 is probably the best way to get there. I'm really unsure though.

    If someone was willing to help me not only solve the problems, but understand the process taken to do so, it would be hugely appreciated. I'm determined to figure it out, but if I go it alone I fear I'll still be sitting here tearing my hair out two weeks from now!

    Thank you in advance.
    (Would you tell me first what book you are working through?) Natural deduction is the kind that does not make use of axioms. Only make asuumptions and use figures (schemes ?). In first exercise we start with three consecutive assumtions p\to r, q\to p, q. Then by using some "schemes" we get r. Then by using other we get the whole formula.

    You don't say Suppose p\to r is true. You just say suppose p\to r and use schemes. if you cannot then make next assumption and so on.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. natural deduction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 12th 2011, 08:31 AM
  2. Natural Deduction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 9th 2011, 03:15 AM
  3. Could use some help with a Natural Deduction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 4th 2010, 05:58 AM
  4. natural deduction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 24th 2010, 11:47 AM
  5. Help with Logic (Natural Deduction)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 12th 2010, 02:07 PM

Search Tags


/mathhelpforum @mathhelpforum