1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove a proposition using natural deduction

  1. Aug 28, 2014 #1
    1. The problem statement, all variables and given/known data

    p⇒¬q,q∨r⊢p⇒r, prove this using rule of natural deducton

    2. Relevant equations

    3. The attempt at a solution

    My approach is this.

    1.Prove that qvr⊢¬q⇒r.
    2.Assume p
    3.By modus ponen, p⇒r

    But the problem I face is how to prove step 1.
  2. jcsd
  3. Aug 29, 2014 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't even know what natural deduction is, so this may not be helpful. I had a quick glance at the Wikipedia page on natural deduction, and it gave me the impression that it's not about following the rules of some proof theory (i.e. definition of what a proof is). So can't you just use that ##p\Rightarrow\lnot q## is equivalent to ##q\Rightarrow\lnot p##, and then conclude that this result and ##q\lor r## together imply that ##\lnot p\lor r##?
  4. Aug 29, 2014 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I suggest you start by opening a Conditional Proof with hypothesis p.
    Then you immediately get ¬q by Modus Ponens. Now if you can prove r, you can close the Conditional Proof and get the desired conclusion.

    In my set of Natural Deduction rules, I'd use Disjunctive Syllogism (DS) inside the Conditional Proof to get the result in your line 1, and then apply Modus Ponens to prove r.

    But you may be using a different set of rules. There is no ISO listing of Natural Deduction rules. You need to use the rules your text allows, and if asking a question about a problem under those rules, you need to list the rules.

    Here is the set I like: http://www.philosophy.ed.ac.uk/undergraduate/documents/Natural_deduction_rules_propositional.pdf

    Alternatively, if you use the following set, you have your line 1 ready-made as a Replacement Rule ('Material Implication'): http://www.mathpath.org/proof/proof.inference.htm
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted