Homework Help: Set Theory

1. Jul 28, 2006

supasupa

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. Jul 28, 2006

loseyourname

Staff Emeritus
What are the axioms/theorems/inference rules you are allowed to use?

3. Jul 28, 2006

supasupa

i can use any rules

4. Jul 28, 2006

0rthodontist

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.

5. Jul 28, 2006

loseyourname

Staff Emeritus
Never mind.

Last edited: Jul 28, 2006
6. Jul 28, 2006

supasupa

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?

7. Jul 28, 2006

supasupa

thanks for your help hint..... i got it now....

8. Jul 28, 2006

loseyourname

Staff Emeritus

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.

9. Jul 28, 2006

supasupa

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

10. Jul 28, 2006

neurocomp2003

i would have started out with teh statement Not(S) and then brought in S<->R or simply Not(S)&S<->R->not(R)

11. Jul 29, 2006

loseyourname

Staff Emeritus
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.

12. Jul 29, 2006

supasupa

i see what you mean.....thank you for that.....the form is easier to follow and conclude...