How do I prove this propositional logic

1. Apr 7, 2007

millani

How do I prove this? (propositional logic)

1. The problem statement, all variables and given/known data
How to prove this
$(p \rightarrow (q \vee p)) \rightarrow r \vdash \neg p \vee (q \vee r)$
using only the natural deduction rules in propositional logic?

2. Relevant equations
http://en.wikipedia.org/wiki/Propositional_logic
(natural deduction rules only)

3. The attempt at a solution
$1: (p \rightarrow (q \vee p)) \rightarrow r$ premise
<start of hypothesis 0> ; I tried to make a box here but failed miserably
$2: \neg (\neg p \vee (q \vee r))$ hypothesis
<start of hypothesis 1>
$3: \neg p$ hypothesis
$4: \neg p \vee (q \vee r)$ conjunction introduction 3
$5: \bot$ negation introduction 2,4
<end of hypothesis 1>
$6: \neg \neg p$ negation introduction 3-5
$7: p$ double negative elimination 6
$8: ?$
<end of hypothesis 0>

As you can see, I don't exactly know how to use TeX.

PS: How do I put a box around the hypothesis in TeX?

Last edited: Apr 7, 2007
2. Apr 7, 2007

matt grime

There are many many latex guides easily googlable. However, it is not guaranteed that the code will work in the forum. Still. Searching is you r best bet if you really want to put a box round something. (Though I'd say there was no need to do that at all.)

3. Apr 7, 2007

MathematicalPhysicist

let's try conditional proof:
1.(p->(qvp))->r premise
2. p hypothesis
4. p->(qvp) 2-3conditional proof
5. r 1,4 modes ponens
6.?
7.?
now i leave you to fill 6 and 7. (hint: look at 3).

4. Apr 7, 2007

millani

Thanks for the help, loop quantum gravity!

1. $(p \rightarrow (q \vee p)) \rightarrow r$ premise
2. $p$ hypothesis
3. $q \vee p$ 2addition
4. $p \rightarrow (q \vee p)$ 2-3conditional proof
5. $r$ 1,4 modes ponens
6. $q \vee r$ disjunction introduction 5
7. $\neg p \vee (q \vee r)$ disjunction introduction 6

5. Apr 8, 2007

MathematicalPhysicist

another method which doesnt employ having an extra hypothesis is:
use material conditional on the premise as far as you get to ~qvr, and afterwards use addition or disjunctive intro, to get ~qvrvq which is r and then the same as in the first approach.
the differnece is that we trully have (p->(qvp))->r |- ~pvqvr
while in the first approach we have (p->(qvp))->r,p|- ~pvqvr
which by the deudction theorem is the sam as: (p->(qvp))->|-p->(~pvqvr) but by the mc it's again the same result.
so here you have both methods to prove this.
and even more..(-: