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?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Direct proof unclear
  1. A proof. (Replies: 2)

  2. Vector Direction (Replies: 5)