Results 1 to 3 of 3

Math Help - Could use some help with a Natural Deduction proof

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    1

    Could use some help with a Natural Deduction proof

    I've been working on a proof for my symbolic logic class, but I cannot seem to solve it. Even after hours and hours of work I am pretty stuck. Anyone want to take a crack at it? It's probably easy for experts. Our class has been working with Hurley's 18 rules

    I'm not sure what convention everyone is used to around here, so i'll post a key.

    > = If then,
    * = Conjuction,
    ~ = Negation
    v= Or
    C: will precede the conclusion/goal of the proof

    Okay, here is the proof:

    C: I
    1. (I>E)>C
    2. C > ~C


    I can't seem to solve it.

    There are a few obvious lines (and about a hundred others) I've found are useful right off the bat.

    3. ~C v ~C 2, Material Implication
    4. ~C 3, Tautology

    Can anyone help me solve this? I've tried a million things. It's truly my "white whale" of our logic problem set.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    1. (I>E)>C
    2. C > ~C
    From the intuitive standpoint, C is a contradiction because, supposing otherwise, truth cannot imply falsehood. Therefore, (I -> E) -> C is equivalent to ~ (I -> E), and this in turn implies I.

    More formally, Natural Deduction, is, in fact, natural, so here is an explanation in the natural language .

    The proof can be broken into two parts. The first proves ~ (I -> E), and the second deduces I from that.

    For the first part, assume I -> E. Then you get C with 1. Also, you get ~ C with 2. Obtaining C as before once more, you get a contradiction from C and ~ C. Therefore, the assumption I -> E was false and we have ~ (I -> E).

    The second part is just a bit trickier because it uses the law of double negation. Assume ~ I and (separately) I. This, of course, gives a contradiction. Since everything follows from contradiction by ex falso quodlibet, we deduce E. Closing the assumption I, we get I -> E. (We still have ~ I open.) But, in the first step we deduced ~ (I -> E), so we get a contradiction again. Now, closing the the assumption ~ I we get ~~ I, from which by Double Negation we get I.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by Cermak View Post
    I've been working on a proof for my symbolic logic class, but I cannot seem to solve it. Even after hours and hours of work I am pretty stuck. Anyone want to take a crack at it? It's probably easy for experts. Our class has been working with Hurley's 18 rules

    I'm not sure what convention everyone is used to around here, so i'll post a key.

    > = If then,
    * = Conjuction,
    ~ = Negation
    v= Or
    C: will precede the conclusion/goal of the proof

    Okay, here is the proof:

    C: I
    1. (I>E)>C
    2. C > ~C


    I can't seem to solve it.

    There are a few obvious lines (and about a hundred others) I've found are useful right off the bat.

    3. ~C v ~C 2, Material Implication
    4. ~C 3, Tautology

    Can anyone help me solve this? I've tried a million things. It's truly my "white whale" of our logic problem set.
    If I'm not mistaken, ten of those 18 rules are rules of replacement. And, DM, DN and Impl are among those ten.
    With those three in hand, you can work the subformulas to your advantage.
    Add to those three the three rules HS, MT and Simp (that are among the other eight rules -- the rules of inference),
    and you have everything you need to write out a derivation that'll take no more than six lines (modulo the premisses).
    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. natural deduction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 24th 2010, 11:47 AM
  4. Help with Logic (Natural Deduction)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 12th 2010, 02:07 PM
  5. classical logic - proofs via natural deduction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 10:27 AM

Search Tags


/mathhelpforum @mathhelpforum