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!

[Discrete Math] <=> related question.

  1. Jan 29, 2006 #1
    Ok so I have two propositions;

    for ALL x: (P(x) or Q(x))
    and I have...
    (for ALL x: P(x)) or (for ALL x: Q(x))

    I need to show if these are logically equivalent. My original assumption was that these are <=>; but that turned out to be wrong. I'm clueless as to what to do... Some hints or guides would be nice.
     
  2. jcsd
  3. Jan 29, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    Are you familiar with the finite universe method? Consider a universe with 2 elements and see if you can assign values for P(x) and Q(x) so that one statement is true and not the other.

    And intuitively, think about what the two statements mean. You should be able to see that they are different.
     
    Last edited: Jan 29, 2006
  4. Jan 29, 2006 #3
    This book doesn't cover the finite universe method. Though I'm googleing it to figure out what it is.
     
  5. Jan 29, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    Well, what does the book cover? The finite universe method is the only way I know to show that a statement in predicate logic doesn't follow. Maybe they just want you to explain, intuitively, why the two are not the same.
     
  6. Jan 29, 2006 #5
    It's not a book problem it's a professor problem, and IMHO my professor isn't right in the head.

    Anyways, here's how I think it works... For the first proposition to be true (for all X) either P(x) or Q(x) must be true. While in the second proposition all values of P(X) must be true or all values of Q(x) must be true.

    I'm not sure if I'm just restating the problem, but that's what I got...
     
  7. Jan 29, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Surely considering propositions P and Q which are jointly always true but occasionally false will do it.

    I'm sure your professor thinks highly of you too.
     
  8. Jan 29, 2006 #7
    I don't follow.
     
  9. Jan 29, 2006 #8

    honestrosewater

    User Avatar
    Gold Member

    What if your domain is the set of natural numbers and P and Q are evenness and oddness? Does that give you an idea for a counterexample?

    [tex](\forall x (Px \vee Qx)) \rightarrow ((\forall x (Px)) \vee (\forall x (Qx)))[/tex]

    doesn't hold. You need to construct a counterexample -- an interpretation where [itex](\forall x (Px \vee Qx))[/itex] is True and [itex]((\forall x (Px)) \vee (\forall x (Qx)))[/itex] is False.
    Let your domain D = {a, b}, a be in P, and b be in Q. Does that work?
     
    Last edited: Jan 29, 2006
  10. Jan 29, 2006 #9
    *whoosh* Straight over my head. I'll sleep on it, maybe I just need to digest this a bit more.
     
  11. Jan 29, 2006 #10

    honestrosewater

    User Avatar
    Gold Member

    That's okay. If you don't understand, just ask. :smile: What words or parts don't you understand?
     
  12. Jan 29, 2006 #11
    Ok I'll try to explain where I'm having issues. It's not really understanding what your asking, it's more like finding the answers is the problem.

    Doesn't turn on any light bulbs.

    Well... Let P(a) = true, and P(b) = false. So [itex](Pa \vee Qb)[/itex] is true... Then [itex](Pa) \vee (Qb)[/itex] would be true as well... So from what I see it works.

    PS: Thanks for the help so far, I'm not one to pick things up fast... Logic is not my strong side.
     
  13. Jan 29, 2006 #12

    honestrosewater

    User Avatar
    Gold Member

    1) [tex](\forall x (Px \vee Qx))[/tex]

    says that you can plug in every member d of your domain for x and

    (Pd v Qd)

    will be true. If your domain has one member, d1, it means that

    (Pd1 v Qd1)

    is true. If your domain has two members, it means that

    (Pd1 v Qd1) & (Pd2 v Qd2)

    is true. If your domain has n members, it means that

    (Pd1 v Qd1) & (Pd2 v Qd2) & ... & (Pdn v Qdn)

    is true. If your domain has r members, it means that

    (Pdr v Qdr)

    is true for every r. Does that makes sense?

    2) [tex](\forall x (Px))[/tex]

    says what? That you can plug in every member d of your domain for x and

    (Pd)

    will be true. So

    3) [tex](\forall x (Px)) \vee (\forall y (Qy))[/tex]

    (with different variables for clarity) says what? That you can plug in every member d of your domain for x and

    (Pd)

    will be true or you can plug in every member d of your domain for y and

    (Qd)

    will be true. That is, (3) says that every member of your domain has the property P or every member of your domain has the property Q; (1) says that every member of your domain has the property P or the property Q. For natural numbers and evenness and oddness, (1) says that every natural number is even or odd (which is true). (3) says that every natural number is even (which is false) or every natural number is odd (which is also false).

    If you don't understand why I used two variables for (3), look in your book for the discussion of quantifer scope.

    Do you understand why and how to go about the next step, constructing a (general) counterexample?
     
    Last edited: Jan 30, 2006
  14. Jan 30, 2006 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Let's think about it in set theory terms. Given a set S and P a proposition about elements in S, then there are two subsets of S, those for which P is true and those for which it is false. Conversely given any partition of S into two subsets then there is a proposition whose truth set is one part of the partition and the other is the false set.


    Got it?

    Now, what you're saying is that you cannot think of a two subsets U and V such that UuV is all of S but neither of which is S?

    Come on I'm sure you can.

    And if you can't do that, then surely you can at least understand the case of 'what if P is not(Q)?

    Of course if you don't see honestrosewater's explicit example from the odd and even hint then no hints will give you the answer since that is practically a counterexample explicitly, indeed I'd practically give a student full marks if the handed in the statement: consider the integers, and the odd and even members thereof.
     
  15. Jan 30, 2006 #14
    Ok so it's false because in the case of ALL x: (P(x) or Q(x)); for this to be true either P(x) or Q(x) has to be true. While in (for ALL x: P(x)) or (for ALL x: Q(x)), it's either all of P(x) is true, or all Q(x) is true.

    Am I following correctly?
     
  16. Jan 30, 2006 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that is the entire point of the exercise.
     
  17. Jan 30, 2006 #16

    honestrosewater

    User Avatar
    Gold Member

    If your teacher wants you to give a general counterexample, you only need two individuals in your domain. You just need to name them D = {a, b} and assign Pa, Pb, Qa, and Qb the truth-values that make (1) = T and (3) = F.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: [Discrete Math] <=> related question.
  1. Discrete Math Question (Replies: 9)

  2. Discrete Math Question (Replies: 9)

Loading...