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: Discrete Math, Intro Proof

  1. Sep 14, 2013 #1
    1. The problem statement, all variables and given/known data

    Using the rules of inference, prove that if ∀x(P(x) ∨ Q(x)) and ∀x((¬P(x) ∧ Q(x)) → R(x)) are true, then ∀x(¬R(x) → P(x)) is true as well.

    2. Relevant equations

    3. The attempt at a solution


    The problem arises step 5. I feel this is correct but the instructor has stated that assuming in a proof:

    "you are not allowed to assume any more information that what is given. Otherwise, you are solving a different problem."

    I felt since my assumption is a bit like a scenario in a truth table that it was OK, because it does not contradict any of the premises.

    I have no idea how to approach this problem other than this.
  2. jcsd
  3. Sep 14, 2013 #2
    Anytime you are asked to prove an implicated statement, in this case, "(Not R) imples P", you may assume the first part to prove the second part. In this case, your professor has added additional stipulations that you must assume as well, so I'd argue that 5 is not only valid, but entirely necessary for proving what you're asked.
  4. Sep 14, 2013 #3


    User Avatar
    Science Advisor

    A->B is equivalent to it "contrapositive", -B->A. Since R is the conclusion of the statement to be proved, -R is the hypothesis of its contrapositive.
  5. Sep 14, 2013 #4
    The problem is not to prove ∀x(¬R(x) → P(x)) but rather to show that it follows from ∀x(P(x) ∨ Q(x)) and ∀x((¬P(x) ∧ Q(x)) → R(x)). Assuming ¬R(x) to be true is not necessary and not valid in the kind of proof that is being asked for.
  6. Sep 15, 2013 #5
    One person said it's OK. Another said it's not. And one just gave just a general definition. If I cannot assume -R(a) is true then I need a push in the right direction on how to solve this without using this assumption, or at least a hint on how I can proof -R(a) is true using rules.
  7. Sep 15, 2013 #6
    You're not supposed to assume or prove that ¬R(a) is true, you're suppose to show ¬R(x) → P(x) is true for all x whenever ∀x(P(x) ∨ Q(x)) and ∀x((¬P(x) ∧ Q(x)) → R(x)) are true. I don't know what rules of inference you are permitted to use, so I can't tell you exactly how you should proceed, but I think HallsofIvy's hint, that you should try proving the contrapositive, might be the way to go.

    Edit: If you have an axiom that says something along the lines of ((A→B)∧¬B)→¬A, you may be able to salvage your proof.
    Last edited: Sep 15, 2013
  8. Sep 17, 2013 #7
    I would argue that taking the first two conditions along with not R is perfectly valid in this problem, as the question is ultimately "given these two conditions, prove this implication" and how you prove an implication is to assume the premise. However I do admit it's less formal and more a tool for someone who really knows what they're doing. Since discrete structures aims to teach basic understandings of proof structures, with a great emphasis on formality and distinctive rules, what the professor is probably aiming for is using the contrapositive of [3] and combining it with [6] through [9].
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted