1. Not finding help here? Sign up for a free 30min 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!

Set Theory

  1. Jul 28, 2006 #1
    I want to know if there is a way to prove this without using a truth table.... i have begun it but unsure if this is correct....any suggestions would be great


    Given that (P v Q ) -> R , R <-> S , (NOT)S are all TRUE. Show that (NOT)P is true.


    I have started with (NOT)((P v Q ) V R) which is the same as (P v Q ) -> R but dont see what i can do after this


    any suggestions???? cheers
     
  2. jcsd
  3. Jul 28, 2006 #2

    loseyourname

    User Avatar
    Staff Emeritus
    Gold Member

    What are the axioms/theorems/inference rules you are allowed to use?
     
  4. Jul 28, 2006 #3
    i can use any rules
     
  5. Jul 28, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    Well, you have to use rules to prove anything. Not knowing what yours are, in general your proof would probably start by showing that R is false. Then you show that (P v Q) is false, and then you show that P is false.

    You are incorrect in saying (NOT)((P v Q ) V R) is equivalent to (P v Q) --> R.
     
  6. Jul 28, 2006 #5

    loseyourname

    User Avatar
    Staff Emeritus
    Gold Member

    Never mind.
     
    Last edited: Jul 28, 2006
  7. Jul 28, 2006 #6
    Sorry that was typo.... it should read

    ((NOT)(P v Q ) V R) is equivalent to (P v Q) --> R.

    But i dont understand why you wold have to prove that R is false first. What about the other 2 conditions which are also true?
     
  8. Jul 28, 2006 #7
    thanks for your help hint..... i got it now....
     
  9. Jul 28, 2006 #8

    loseyourname

    User Avatar
    Staff Emeritus
    Gold Member

    Present your answer if you got it!!

    By the way, the reason I asked what rules you could use is that, if you are allowed to use Modus Tollens, you can do it in six steps. If not, but you are allowed to use that equivalency you used (is there a name for that??), then it should take one additional step.
     
  10. Jul 28, 2006 #9
    Note: using * for (NOT)
    using @ for AND

    Given that (P v Q ) -> R , R <-> S , *S are all TRUE. Show that *P is true.

    R <-> S is the same as (R->S) @ (S->R)
    for this to be true, S if false and hence R is False

    If R is false, therefore (P V Q) is False for (P v Q ) -> R to be true
    therefore *(*P @ *Q) is False
    therefore (*P @ *Q) is true and hence *P and *Q have to be true
     
  11. Jul 28, 2006 #10
    i would have started out with teh statement Not(S) and then brought in S<->R or simply Not(S)&S<->R->not(R)
     
  12. Jul 29, 2006 #11

    loseyourname

    User Avatar
    Staff Emeritus
    Gold Member

    While all of that is true, it's not the way a derivation is usually written. The proper form is:

    1. Premise
    2. Premise
    C. Conclusion
    3. Premise (derived from other premise using axiom or theorem)
    4. Premise (derived from other premise using axiom or theorem)
    and so on until you derive the conclusion

    If your professor will accept that, though, go for it.
     
  13. Jul 29, 2006 #12
    i see what you mean.....thank you for that.....the form is easier to follow and conclude...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Set Theory
  1. Set theory (Replies: 2)

  2. Set theory (Replies: 4)

  3. No. of elements (Replies: 5)

  4. Set theory proof (Replies: 7)

Loading...