Existential and universal quantifiers

  • Thread starter bonfire09
  • Start date
  • #1
248
0

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
22,097
3,282
Can you see statements similar to as "for all" and "there exists" in the sentence?
 
  • #3
248
0
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.
 
  • #4
22,097
3,282
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?
 
  • #5
248
0
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
 
  • #6
22,097
3,282
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
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.
 
  • #7
248
0
∃ 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?
 
  • #8
248
0
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?
 
  • #9
Stephen Tashi
Science Advisor
7,162
1,314
∃ 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?
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.
 
  • #10
248
0
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!!!
 
  • #11
Stephen Tashi
Science Advisor
7,162
1,314
do these statements have to look exactly the same as the ones in the book?
That's a question only your instructor can answer.
Mine are coming out pretty similar but a little bit off. I may add an extra variable like q(x) to it for example.
g(x) isn't a variable. 'x' is a variable. What do your text materials call expressions like "g(x)"?
Should I worry about that or as long im getting the concepts thats fine?
You have to get the concepts to the extent that your answers are correct. Can you give a correct answer to this problem?
 
  • #12
281
2
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]
 
  • #13
22,097
3,282
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]
This is not valid predicate logic and totally not the point of the exercise.
 
Last edited:
  • #14
248
0
That's a question only your instructor can answer.

I'm actually trying to learn this stuff on my own right now. P(x) represents a statement. Yeah I can try to give the correct answer now.


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

D(x)- x lives in a dorm
M(x)- x has the measles
F(y,x)-y is a friend of x
D(y)-y lives in a dorm
q(y)- y needs to quarantined
 
  • #15
22,097
3,282
I'm actually trying to learn this stuff on my own right now. P(x) represents a statement. Yeah I can try to give the correct answer now.


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

D(x)- x lives in a dorm
M(x)- x has the measles
F(y,x)-y is a friend of x
D(y)-y lives in a dorm
q(y)- y needs to quarantined
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).
 
  • #16
Stephen Tashi
Science Advisor
7,162
1,314
∃x (D(x)^M(x))→∀y(F(y,x)^D(y))→q(y)
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)}.
 
  • #17
248
0
∃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:
  • #18
Stephen Tashi
Science Advisor
7,162
1,314
∃x (D(x)^M(x))→ ∃y((∀z F(y,z))^D(y))→q(y)
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.
 
  • #19
248
0
∃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:
  • #20
Stephen Tashi
Science Advisor
7,162
1,314
∃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?
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.
 
  • #21
281
2
This is not valid predicate logic and totally not the point of the exercise.
Oooops, sorry! The engineer inside me is to blame :biggrin:
 

Related Threads on Existential and universal quantifiers

Replies
10
Views
6K
Replies
6
Views
781
  • Last Post
Replies
4
Views
1K
Replies
9
Views
4K
Replies
2
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
564
Top