Results 1 to 12 of 12
Like Tree3Thanks
  • 1 Post By phys251
  • 1 Post By phys251
  • 1 Post By Plato

Thread: Help with conditional proof (natural deduction)

  1. #1
    Newbie
    Joined
    Nov 2015
    From
    Michigan
    Posts
    10
    Thanks
    1

    Question Help with conditional proof (natural deduction)

    Hey guys, I've been banging my head against the wall trying to figure this one out. It's the first problem in my problem set (so it should be one of the easier ones), but I have taken many dead end routes trying to figure this out. The problem is as follows:

    1. (\sim U \rightarrow Z) \rightarrow (Y \wedge \sim B)

    2. \sim U \rightarrow (H \vee Z)

    3. H \rightarrow Z

    / \sim B

    So far I've been trying to use a conditional to prove \sim U \rightarrow Z so that I can use MP to get Y \wedge \sim B, and by simplification \sim B , but everything I've tried thus far is a dead end. Any and all help would be greatly appreciated! Thanks!
    Last edited by nateneal; Oct 30th 2016 at 01:51 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2012
    From
    Georgia
    Posts
    220
    Thanks
    55

    Re: Help with conditional proof (natural deduction)

    Are these three separate statements that you are supposed to combine to prove $\sim B$?
    Thanks from nateneal
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2015
    From
    Michigan
    Posts
    10
    Thanks
    1

    Re: Help with conditional proof (natural deduction)

    Quote Originally Posted by phys251 View Post
    Are these three separate statements that you are supposed to combine to prove $\sim B$?
    Yes, using the 18 rules of natural deduction
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2015
    From
    Michigan
    Posts
    10
    Thanks
    1

    Re: Help with conditional proof (natural deduction)

    I feel like I'm getting a bit closer. When assuming \sim U , I'm able to create the statement \sim H \rightarrow Z, giving me both \sim H \rightarrow Z and H \rightarrow Z. Abstractly, I can see how this would lead to being able to prove \sim U \rightarrow Z, since H and \sim H both imply Z, but I'm unable to put it down concretely in terms of the rules of natural deduction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2012
    From
    Georgia
    Posts
    220
    Thanks
    55

    Re: Help with conditional proof (natural deduction)

    If you are completely lost, you could try a truth table. Note, however, that since you have five variables, you would have to have $2^5 = 32$ entry rows in your table.

    Alternatively, don't forget properties such as contrapositives.
    Thanks from nateneal
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2015
    From
    Michigan
    Posts
    10
    Thanks
    1

    Re: Help with conditional proof (natural deduction)

    Quote Originally Posted by phys251 View Post
    If you are completely lost, you could try a truth table. Note, however, that since you have five variables, you would have to have $2^5 = 32$ entry rows in your table.

    Alternatively, don't forget properties such as contrapositives.
    Unfortunately, I don't think a truth table will do much here. The nature of this proof is that it is a tautology, since regardless of the input truth values, we will always be able to deduce \sim B.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2015
    From
    Michigan
    Posts
    10
    Thanks
    1

    Re: Help with conditional proof (natural deduction)

    Ok guys, I decided to scrap this one and do another problem of similar form. It seems like I wasn't creating a construction dilemma. For anyone wondering, this was the proof: (note that the symbols used for implication and conjunction are different. I don't know why, but they are)

    Help with conditional proof (natural deduction)-5c9b83510d1fd359eb6beadce7f56f5e.png
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,873
    Thanks
    2513
    Awards
    1

    Re: Help with conditional proof (natural deduction)

    Quote Originally Posted by nateneal View Post
    Ok guys, I decided to scrap this one and do another problem of similar form. It seems like I wasn't creating a construction dilemma. For anyone wondering, this was the proof: (note that the symbols used for implication and conjunction are different. I don't know why, but they are)

    Click image for larger version. 

Name:	5c9b83510d1fd359eb6beadce7f56f5e.png 
Views:	8 
Size:	15.3 KB 
ID:	36515
    There is a long tradition in logic of people find new and more reasonable ways to teach the subject. Natural Deduction is just one more example. In fact, it is one of the more obscure efforts. Thus you will be lucky to find someone here willing to take this up, not I.
    Thanks from nateneal
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Nov 2015
    From
    Michigan
    Posts
    10
    Thanks
    1

    Re: Help with conditional proof (natural deduction)

    Quote Originally Posted by Plato View Post
    There is a long tradition in logic of people find new and more reasonable ways to teach the subject. Natural Deduction is just one more example. In fact, it is one of the more obscure efforts. Thus you will be lucky to find someone here willing to take this up, not I.
    I've actually taken discrete math courses before and I agree. I'm taking this class as more of an easy A and the emphasis on ND was definitely a surprise. I've never taken a class so picky when it comes to these kinds of proofs
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    20,873
    Thanks
    2513
    Awards
    1

    Re: Help with conditional proof (natural deduction)

    Quote Originally Posted by nateneal View Post
    I've never taken a class so picky when it comes to these kinds of proofs
    I have been out of active research for c10 years. But before that, your complaint about being 'picky' was the most frequent that I heard. Some traditional things just always work. But the need to publish drives the need to find the new.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jul 2011
    Posts
    216
    Thanks
    2

    Re: Help with conditional proof (natural deduction)

    Here is a way to create the conditional : \sim U \rightarrow Z


    1. (\sim U \rightarrow Z) \rightarrow (Y \wedge \sim B)

    2. \sim U \rightarrow (H \vee Z)

    3. H \rightarrow Z

    4. \sim U .................................................. .................................................. ...ACP

    5. \sim Z.................................................. ........................................Assumption for contradiction

    6. \sim Z\rightarrow\sim H.................................................. .......................3 CONTRAPOSITIVE

    7. \sim H.................................................. .................................................5 6 MP

    8. \sim H\wedge \sim Z.................................................. ................................5 7 Conjunction

    9. \sim(H\vee Z).................................................. ..........................................8 D.Morgan

    10.. (H\vee Z).................................................. ..........................................2 4 MP

    11. \sim(H\vee Z)\wedge(H\vee Z).................................................. .......................9 10 Conjunction

    12. Z.................................................. .................................................. ..........5 TO 11 CONTRADICTION

    13. \sim U \rightarrow Z.................................................. .................................4 to 12 Conditional proof
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jul 2011
    Posts
    216
    Thanks
    2

    Re: Help with conditional proof (natural deduction)

    Quote Originally Posted by nateneal View Post
    Ok guys, I decided to scrap this one and do another problem of similar form. It seems like I wasn't creating a construction dilemma. For anyone wondering, this was the proof: (note that the symbols used for implication and conjunction are different. I don't know why, but they are)

    Click image for larger version. 

Name:	5c9b83510d1fd359eb6beadce7f56f5e.png 
Views:	8 
Size:	15.3 KB 
ID:	36515
    Step 11 is totally wrong
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of Predicate Logic by natural deduction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 29th 2015, 09:52 PM
  2. Natural deduction, need help.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Jan 16th 2015, 10:11 AM
  3. Natural Deduction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: Jun 9th 2011, 03:15 AM
  4. 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
  5. natural deduction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Apr 24th 2010, 11:47 AM

/mathhelpforum @mathhelpforum