• Support PF! Buy your school textbooks, materials and every day products Here!

How do I prove this propositional logic

  • Thread starter millani
  • Start date
  • #1
3
0
How do I prove this? (propositional logic)

Homework Statement


How to prove this
[itex](p \rightarrow (q \vee p)) \rightarrow r \vdash \neg p \vee (q \vee r)[/itex]
using only the natural deduction rules in propositional logic?

Homework Equations


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

The Attempt at a Solution


[itex]1: (p \rightarrow (q \vee p)) \rightarrow r[/itex] premise
<start of hypothesis 0> ; I tried to make a box here but failed miserably
[itex]2: \neg (\neg p \vee (q \vee r))[/itex] hypothesis
<start of hypothesis 1>
[itex]3: \neg p[/itex] hypothesis
[itex]4: \neg p \vee (q \vee r)[/itex] conjunction introduction 3
[itex]5: \bot[/itex] negation introduction 2,4
<end of hypothesis 1>
[itex]6: \neg \neg p[/itex] negation introduction 3-5
[itex]7: p[/itex] double negative elimination 6
[itex]8: ?[/itex]
<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:

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
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
MathematicalPhysicist
Gold Member
4,220
172
let's try conditional proof:
1.(p->(qvp))->r premise
2. p hypothesis
3. qvp 2addition
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
3
0
Thanks for the help, loop quantum gravity!

1. [itex](p \rightarrow (q \vee p)) \rightarrow r[/itex] premise
2. [itex]p[/itex] hypothesis
3. [itex]q \vee p[/itex] 2addition
4. [itex]p \rightarrow (q \vee p)[/itex] 2-3conditional proof
5. [itex]r[/itex] 1,4 modes ponens
6. [itex]q \vee r[/itex] disjunction introduction 5
7. [itex]\neg p \vee (q \vee r)[/itex] disjunction introduction 6
 
  • #5
MathematicalPhysicist
Gold Member
4,220
172
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..(-:
 

Related Threads on How do I prove this propositional logic

  • Last Post
Replies
19
Views
7K
  • Last Post
Replies
9
Views
6K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
3K
Replies
4
Views
800
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
1
Views
805
Replies
11
Views
8K
Top