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!

Direct proof unclear

  1. Oct 23, 2009 #1
    "A direct proof is a proof in which the truth of the premises of a theorem are shown to directly imply the truth of the theorem's conclusion."

    Here are the premises:
    (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q)

    and the conclusion:

    (S v R) ^ (~P)

    Now what I do not understand why we are using expressions that are implications are not equivalency?

    Let me start the prrof.

    (1) ~P premise
    (2) P v Q premise
    (3) From discjunctive simplification we got:
    (P v Q) ^ (~P) -> Q
    (4) (Q->S) premise
    (5) From detachment i.e (Q->S) ^ Q -> S
    (6) P -> R premise
    (7) from (6) ~P v R

    And I didn't come up with the conclusion? What is the problem with this direct proof?

    Shouldn't I use equivalent expressions and not implications?


    Please help
  2. jcsd
  3. Oct 23, 2009 #2
    Which proof system are you using?
  4. Oct 24, 2009 #3
    Its called direct proof in propositional calculus.

    But the real problem is not every time implication works as same as equivalency.

    For ex.

    The first proof.

    (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (S v R) ^ (~P) (tautology)

    When substituting (P v Q) ^ (~P) -> Q


    (P -> R) ^ (Q -> S) ^ Q-> (S v R) ^ (~P) is not tautology

    Practically the direct proof is substituting implication in the expression, which I believe is not valid.
  5. Oct 24, 2009 #4
    But from S, you should be able to prove S v X for any proposition X.
  6. Oct 24, 2009 #5
    I do not understand. Please explain how.
  7. Oct 24, 2009 #6
    I don't know how in your particular system, but there's often an axiom of disjunction introduction, similar to the conjunction elimination you've been doing so far:

    (conj. elim.) (A ^ B) => A
    (disj. intro.) A => (A v B)
  8. Oct 25, 2009 #7
    Ok, my question is:

    (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (S v R) ^ (~P)

    Would be correct to substitute

    (~P) ^ (P v Q ) -> Q as it is equivalent expression to Q as follows (because of disjunctive simplification):

    (P -> R) ^ (Q -> S) ^ Q -> (S v R) ^ (~P)

    ?? Is this valid?

    It is not. So why the proof says:

    (1) A proof must end in a finite number of steps.

    (2) Each step must be either a premise or a proposition that is implied from previous steps using any valid equivalence or implication.

    (3) For a direct proof, the last step must be the conclusion of the theorem.

    The (2) says that.
  9. Oct 25, 2009 #8
    Any help, please? Could somebody possibly explain my why the direct proof is valid?

    Thank you.
  10. Oct 25, 2009 #9
    (~P) ^ (P v Q) implies Q, but it is not equivalent to Q (since Q says nothing about whether or not P holds). Thus, you cannot simply substitute it for (~P) ^ (P v Q) in an expression.

    The steps don't need to involve substituting the things into the original formula, but just noting what other statements follow from the premises.
  11. Oct 25, 2009 #10
    Yes, the steps does not involve substituting, but it is same like substituting things.

    I didn't manage to prove the expression above, because it is something wrong with this direct proof. Just look at my first post and see where I am stuck.
  12. Oct 25, 2009 #11
    You were fine up to and including step 5.

    (1) ~P premise
    (2) P v Q premise
    (3) From disjunctive simplification we got:
    (P v Q) ^ (~P) -> Q
    (4) (Q->S) premise
    (5) From detachment i.e (Q->S) ^ Q -> S

    Then here your next steps should be something like

    (6) S -> (S v R) by disjunction introduction
    (7) (S v R) ^ (~P) from (6) and (1)

    And (7) is what you wanted to prove.
  13. Oct 25, 2009 #12

    But you used premise ~P already in step (3).

    Is it valid to use it again?
  14. Oct 25, 2009 #13
    Of course. You can use a premise as often as you want. It remains true throughout the entire proof.
  15. Oct 26, 2009 #14
    And does p,q,s have any truth value, for example. true or false through the process?

    Do we suppose from the start that the premises are true?
  16. Oct 26, 2009 #15
    Yes, in a direct proof one assumes the premises are true, and derives statements from that.
  17. Oct 26, 2009 #16
    Thank you.

    And can we prove it like this:

    (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q)

    t(P->R) = T



    t(P v Q)=T

    Since the premises are true.


    From t(F v Q) =T, t(Q)=T

    From t(T->S)=T, t(S)=T

    From t(F->R) = T t(R)=T or t(R)=F

    Substituting in the conclusion:

    (T v R) ^ (T) <=> T ^ T <=> T

    Is this valid?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook