Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Existential and universal quantifiers

  1. Jun 24, 2012 #1
    If anyone in the dorm has the measles, then everyone who has a friend
    in the dorm will have to be quarantined

    I'm supposed to convert this sentence into a logical form. I'm having trouble breaking this sentence apart because im not sure what to look for. I need help with this thanks?
     
  2. jcsd
  3. Jun 24, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Can you see statements similar to as "for all" and "there exists" in the sentence?
     
  4. Jun 24, 2012 #3
    so you mean like this.
    where it says if anyone in the dorm has measles is similar to there exists
    and where it say where "everyone who has a friend..." is similar to for all

    but what about the if and the then? I tried breaking it apart like that and the answer I got was way off the original answer.
     
  5. Jun 24, 2012 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    OK, so you can already write it like this:

    [itex]\exists[/itex] person in dorm who has measles, then [itex]\forall[/itex] person who has a friend will be quarantined.

    You're still missing an existential quantifier though. Maybe you can try to write the previous sentence in even more formal notation?
     
  6. Jun 24, 2012 #5
    well my original answer goes like this

    ∃ x(D(x,y)^M(x)) → ∀y((F(y,x)^Q(y))

    where D(x,y) is where x is anyone who lives in the dorm y
    M(x) is where x has measles
    followed by
    F(y,x) where y is the friend of x who has measles
    Q(y)- y the friend has to get quarantened
     
  7. Jun 24, 2012 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    This can be improved. You have only two variables right now x and y. But you need much more. First, you use x for the person who live in the dorm and the friend who lives in the dorm (who are not necessarily the same person), you need to use seperate variables.
    You use y for the person who has the friend and for the dorm. These require seperate variables (logically, you don't need an extra variable, but increases readability a lot). Furthermore, I'm not sure if you need a variable for the dorm.
     
  8. Jun 24, 2012 #7
    ∃ x(F(x,y)^D(x,z)^E(y,z)^M(x)) → ∀y((F(y,x)^Q(y))


    where F(x,y) is where x is friend of y
    D(x,z) is where x friend lives in dorm z
    E(y,z)- is where y lives in a dorm as well z
    M(y)- is where y has measles
    F(y,x) where y is the friend of x who has measles
    Q(y)- y the friend has to get quarantined

    Am i doing this right now?
     
  9. Jun 24, 2012 #8
    Yeah I'm not able to figure this one out. I tried to break apart like this

    ∃ x(If Someone has measles then their friends will all be quarantined)
    ∀ z(If z is a friend of x and lives in the dorm then z would have to be quarantined)


    is there something free online that would help me figure this out?
     
  10. Jun 24, 2012 #9

    Stephen Tashi

    User Avatar
    Science Advisor

    No, it isn't correct yet. If you are writing a statement (as opposed to a statement-expressions) every variable should be in the "scope" of some quantifier. If you examine what you have written, the variable "z"is not in the scope of any quantifier. So you haven't written a statement.

    To express "if anyone in the dorm has measles", think of it as "if there exists a person who is both in the dorm and has measles". You only need one variable to express this.

    D(x) : x lives in the dorm
    M(x): x has measles

    To express "Everyone who has a friend in the dorm will have to be quarantined", I think you only need two variables.

    F(x,y) : y is a friend of x
    As above, D(y): y lives in the dorm
    Q(x): x must be quarantined

    Think of it as saying: For each person x, if there is some y who is a friend of x and who lives in the dorm then x must be quarantined.

    The statement does not say that y must have measles.
     
  11. Jun 25, 2012 #10
    do these statements have to look exactly the same as the ones in the book? Mine are coming out pretty similar but a little bit off. I may add an extra variable like q(x) to it for example. Should I worry about that or as long im getting the concepts thats fine? and thanks alot for your guys help!!!
     
  12. Jun 25, 2012 #11

    Stephen Tashi

    User Avatar
    Science Advisor

    That's a question only your instructor can answer.
    g(x) isn't a variable. 'x' is a variable. What do your text materials call expressions like "g(x)"?
    You have to get the concepts to the extent that your answers are correct. Can you give a correct answer to this problem?
     
  13. Jun 25, 2012 #12
    Why not use piecewise functions:

    H(x)=0 if noone has measles, or H(x)=1 if at least one person does.
    F(y)=1 if person y has a friend in the dorm, or 0 if they don't.
    Q(y)=1 if person y must be quarantined, or 0 if they don't.

    Therefore, if [itex]\exists y_0:H(x)F(y_0)=1 => Q(y_0)=1[/itex]
     
  14. Jun 25, 2012 #13

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    This is not valid predicate logic and totally not the point of the exercise.
     
    Last edited: Jun 25, 2012
  15. Jun 25, 2012 #14
     
  16. Jun 25, 2012 #15

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Two remarks. You have something of the form [itex]A\rightarrow B\rightarrow C[/itex] right now. It would be better to add some brackets here. So I think you mean:

    ∃x (D(x)^M(x))→(∀y(F(y,x)^D(y))→q(y))

    Anyway. You say F(y,x), which means that y is a friend of x. But this x does not need to be the same x that has measles!!!! The statement here is:

    If anyone in the dorm has the measles, then everyone who has a friend in the dorm will have to be quarantined.

    So let's say John has measles and let's say Robert lives in the same dorm. Then any friend of Robert needs to be quarantined. This is how I interpret the sentence.
    What you wrote is that only the friends of John need to be quarantined.

    So you can not use F(y,x). You need to introduce a new variable z somehow and write F(y,z).
     
  17. Jun 25, 2012 #16

    Stephen Tashi

    User Avatar
    Science Advisor

    You have to pay attention to the "scope" of the quantifiers. How to define "scope" formally may be in the materials you are studying or it may only be treated informally. I can only explain it informally!

    We already know that on a page in a math book, that a variable like 'x' may mean one thing in one paragraph and something different in the next. For example, in problem 1, 'x' may stand for one thing and in problem 23, 'x' may mean something different. This similar to the "scope" of variable in computer programming. The value of 'x' in the code for one function doesn't determine the value of 'x' in the code for another function, unless 'x' is variable whose "scope" includes both functions (such as a "global" variable).

    When you use a quantifer "there exists" on the variable 'x' in an exression that contains lot's of x's, the "there exists" may only apply to a few of them. The way to be unambiguous about this is to use parentheses or brackets to show what a quantifier applies to.

    For example:

    "There is person in class who is smart and everyone in class is has limited abilities".

    S(x): x is smart
    L(x) : x has limited abilities
    C(x): x is in class

    [tex] \exists x \{ C(x) \wedge S(x) \} \wedge \forall x \{ C(x) \rightarrow L(x) \} [/tex]

    It is clearer to most human minds to write the above as:

    [tex] \exists x \{ C(x) \wedge S(x) \} \wedge \forall y \{ C(y) \rightarrow L(y) \} [/tex]

    but it is not necesary to introduce the symbol 'y'. The symbol 'x' can be re-used by putting it in the scope of different quantifiers.

    Someone reading your answer would have to interpret all the x's as being in the scope of the "there exists" and your answer, as I read it, claims: "There is a person with the property that if that person lives in the dormitory and has measels then all friends of that person who live in the dormitory must be quarantined."

    You need to introduce another quantifier on the right hand side of the [itex] \rightarrow [/itex]. The idea you need to express is that "for each y { if ( there is some x who lives in the dormitory and y is a friend of x) then (y must be quarantined)}.
     
  18. Jun 25, 2012 #17
    ∃x (D(x)^M(x))→ ∃y((∀z F(y,z))^D(y))→q(y)

    I think now it reads right ."For someone x if x lives in a dorm and has the measles then everyone z who has a friend y and lives in the dorm has to get quarantined."
     
    Last edited: Jun 25, 2012
  19. Jun 25, 2012 #18

    Stephen Tashi

    User Avatar
    Science Advisor

    That says "If there is some x who lives in the dorm and has measles then there is some y such that if y is a friend of everything and y lives in the dorm then y must be quarantined"

    You need to change the order of the [itex] \exists y [/itex] and [itex] \forall z [/itex] and get z quarantined instead of y.

    [itex] \exists x \{ D(x) \wedge M(x)\} \rightarrow \forall z \{ \exists y\{ .... [/itex] etc.
     
  20. Jun 25, 2012 #19
    ∃x (D(x)^M(x))→ ∀z((∃y F(y,z))^D(z))→q(z)

    so every y who has a friend z where z lives in the dorm? Is this right?
     
    Last edited: Jun 25, 2012
  21. Jun 26, 2012 #20

    Stephen Tashi

    User Avatar
    Science Advisor

    The last part of what you wrote needs a minor fix. Put y in the dorm, not z. The last part should apply to every z who has a friend y with the property that y lives in the dorm.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Existential and universal quantifiers
  1. Quantifier help? (Replies: 1)

  2. Universal Quantifier (Replies: 4)

Loading...