Notices
Results 1 to 15 of 15

Thread: direct proof unclear

  1. #1 direct proof unclear 
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    "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


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    If the problem statement uses implications, then you should use implications. I think what's throwing you off here is the ~P, since it looks like you don't really need it beyond having it show back up in the conclusion.


    Reply With Quote  
     

  4. #3  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Quote Originally Posted by MagiMaster
    If the problem statement uses implications, then you should use implications. I think what's throwing you off here is the ~P, since it looks like you don't really need it beyond having it show back up in the conclusion.
    What really trows me off is substituting implications as they were equivalences. For example. the following proof needs to be done:

    (p -> r) ^ (q -> s) ^ (p v q ) => (s v r)

    The proof goes like (1)-(5) steps doing this:

    (p->r) ^ (~p->q) ^ (q->s) => (s v r) (this is valid because (p v q) <=> ~p -> q)

    Now they do:

    (p->r)^(~p->s) => (s v r) (substituting (~p->q) ^ (q->s) -> (~p ->s) which is not equivalency)

    Now

    (p->r) ^ (~s -> p) => (s v r) (using ~p -> s <=> ~s -> p)

    (~s -> r) => (~s ->r)



    How is the second and third steps valid?
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Can you be more specific? They look fine ot me. You can still have transitivity without having commutitivity. ((p -> q) ^ (q -> r)) -> (p -> r) still works without equivalence. Anyway, if the implications are throwing you off, you showed a transformation to get rid of them.
    Reply With Quote  
     

  6. #5  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Quote Originally Posted by MagiMaster
    Can you be more specific? They look fine ot me. You can still have transitivity without having commutitivity. ((p -> q) ^ (q -> r)) -> (p -> r) still works without equivalence. Anyway, if the implications are throwing you off, you showed a transformation to get rid of them.
    I don't know how to explain you.

    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

    like

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

    That's the problem.
    Reply With Quote  
     

  7. #6  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I guess I'm still not understanding the problem exactly, but maybe it's due to having transitivity but not commutativity, so you might have (a->b)^(a->c)^(b->d)^(c->e), so (a->d) and (a->e), but it doesn't say anything about how d and e relate to each other.
    Reply With Quote  
     

  8. #7  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Quote Originally Posted by MagiMaster
    I guess I'm still not understanding the problem exactly, but maybe it's due to having transitivity but not commutativity, so you might have (a->b)^(a->c)^(b->d)^(c->e), so (a->d) and (a->e), but it doesn't say anything about how d and e relate to each other.
    Lets say the expression we need to prove is:

    (~p v q) ^ (s v p) ^ (~q) -> s

    using a direct proof.

    (~p v q), (s v p), (~q) - premises

    s - conclusion

    Ok. Here is how to direct proof goes like:

    (1) ~p v q Premise
    (2) ~q Premise
    (3) ~p Disjunctive simplification, (1),(2)
    (4) s v p Premise
    (5) s Disjunctive simplification (3),(4) #

    Disjunctive simplification is: (p v q) ^ (~q) -> p

    The expression is:

    (~p v q) ^ (s v p) ^ (~q) -> s

    Now, analog to the steps of the direct proof:

    (~p v q) ^ (~q) ^ (s v p) -> s

    (3) Disjunctive simplification of (~p v q) ^ (~q) -> (~p)

    (~p) ^ (s v p) -> s

    (4) Disjunctive simplification of (~p) ^ (s v p) -> s

    s -> s #

    Do you understand now what I am talking about??
    Reply With Quote  
     

  9. #8  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Well, I follow both of those, but I still don't see the problem.
    Reply With Quote  
     

  10. #9  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Quote Originally Posted by MagiMaster
    Well, I follow both of those, but I still don't see the problem.
    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?
    Reply With Quote  
     

  11. #10  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I think I see the problem. I think you need to substitute (~p)^(q) for (p v q)^(~p). While (p v q)^(~p) implies (q), it's not equivalent, so you can't plug it in to the left side of some other implication and expect the implication to remain unchanged. At least, that's my understanding.
    Reply With Quote  
     

  12. #11  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Quote Originally Posted by MagiMaster
    I think I see the problem. I think you need to substitute (~p)^(q) for (p v q)^(~p). While (p v q)^(~p) implies (q), it's not equivalent, so you can't plug it in to the left side of some other implication and expect the implication to remain unchanged. At least, that's my understanding.
    Exactly. Sometimes it works, but not necessarily works...

    That's what direct proof does.

    But still can't understand. In my text book 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.
    Reply With Quote  
     

  13. #12  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Any help please?

    Anyone to try to prove:

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

    with direct proof ?
    Reply With Quote  
     

  14. #13  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    No, that's not what 2 says. It says you need a chain of implications, but you can't just make a substitution like that in the middle of such a chain. You could make a different chain that includes that substitution though.
    Reply With Quote  
     

  15. #14  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Quote Originally Posted by MagiMaster
    No, that's not what 2 says. It says you need a chain of implications, but you can't just make a substitution like that in the middle of such a chain. You could make a different chain that includes that substitution though.
    Could you please give me an example?

    Thank you.
    Reply With Quote  
     

  16. #15  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    You have:
    - (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (S v R) ^ (~P)
    And:
    - (~P) ^ (P v Q) -> (Q)
    So:
    - (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (P -> R) ^ (Q -> S) ^ (Q)
    But not:
    - (P -> R) ^ (Q -> S) ^ (Q) -> (S v R) ^ (~P)

    On the other hand:
    - (~P) ^ (P v Q) <=> (~P) ^ (Q)
    So:
    - (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) <=> (P -> R) ^ (Q -> S) ^ (~P) ^ (Q)
    And this works now:
    - (P -> R) ^ (Q -> S) ^ (~P) ^ (Q) -> (S v R) ^ (~P)

    Or sticking with just implications:
    - (P -> R) ^ (Q -> S) ^ (~P) ^ (P v Q) -> (P -> R) ^ (Q -> S) ^ (Q)
    And:
    - (P -> R) ^ (Q -> S) ^ (Q) -> (P -> R) ^ (Q) ^ (S)
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •