Results 1 to 4 of 4

Math Help - natural deduction

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    4

    natural deduction

    Hello,

    I am new to logic and I could realy use some help.
    is there anyone who can prove the following examples for me in Fitch style?

    proof -(P v -(-Q v P)) without premisses.
    proof -(P & Q) v (P V Q) without premisses.
    proof -R v Q v -P v S from the premisses (-P v Q) & (-R v S).

    Any help will be much apreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: natural deduction

    The first formula is false when P is true, so it can't be proved. Concerning the third formula, either premise ~P v Q or ~R v S is enough. You can get them by conjunction elimination. The conclusion follows just by disjunction elimination (considering whether ~P or Q holds) and then disjunction introduction. The second derivation is slightly more difficult. It requires either the law of excluded middle (easier) or double-negation elimination (harder).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2011
    Posts
    4

    Re: natural deduction

    Thank you so much! You realy helped me out.
    I have found the solutions, exepts for the second exercise. How can I apply the law of excluded middle on this one?

    P.s. Excuse me for my Englisch, it is not my native language (there are no logic or mathematic forums in Holland)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: natural deduction

    You reason by cases (vE, i.e., disjunction elimination) on P v ~P. If P, then -(P & Q) v (P v Q) by applying vI two times. If ~P, then you prove ~(P & Q) as follows. Assume P & Q, derive P by /\E and get a contradiction with ~P. Having proved ~(P & Q), derive -(P & Q) v (P v Q) again by vI.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Natural Deduction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 9th 2011, 04:15 AM
  2. Could use some help with a Natural Deduction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 4th 2010, 06:58 AM
  3. natural deduction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 24th 2010, 12:47 PM
  4. Help with Logic (Natural Deduction)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 12th 2010, 03:07 PM
  5. classical logic - proofs via natural deduction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 11:27 AM

Search Tags


/mathhelpforum @mathhelpforum