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!

Homework Help: How do I prove this propositional logic

  1. Apr 7, 2007 #1
    How do I prove this? (propositional logic)

    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations
    (natural deduction rules only)

    3. 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: Apr 7, 2007
  2. jcsd
  3. Apr 7, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.)
  4. Apr 7, 2007 #3


    User Avatar
    Gold Member

    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
    now i leave you to fill 6 and 7. (hint: look at 3).
  5. Apr 7, 2007 #4
    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
  6. Apr 8, 2007 #5


    User Avatar
    Gold Member

    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..(-:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook