# Prove a proposition using natural deduction

1. Aug 28, 2014

### gaobo9109

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. Aug 29, 2014

### Fredrik

Staff Emeritus
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$?

3. Aug 29, 2014

### andrewkirk

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