Page 86 - Discrete Mathematics and Its Applications

1.5 Nested Quantifiers 65

given at your school. Express each of these statements by h) Thereisexactlyonepersonwhom everybody canfool.
a simple English sentence. i) No one can fool himself or herself.
a) C(Randy Goldberg, CS 252) j) There is someone who can fool exactly one person
b) ∃xC(x, Math 695) besides himself or herself.
c) ∃yC(Carol Sitea, y) 11. Let S(x) be the predicate “x is a student,” F(x) the pred-
d) ∃x(C(x, Math 222) ∧ C(x, CS 252)) icate “x is a faculty member,” and A(x, y) the predicate
e) ∃x∃y∀z((x = y) ∧ (C(x, z) → C(y, z))) “x has asked y a question,” where the domain consists of
f) ∃x∃y∀z((x = y) ∧ (C(x, z) ↔ C(y, z)))
all people associated with your school. Use quantifiers to
7. Let T (x, y) mean that student x likes cuisine y, where the express each of these statements.
domain for x consists of all students at your school and a) Lois has asked Professor Michaels a question.
the domain for y consists of all cuisines. Express each of
these statements by a simple English sentence. b) Every student has asked Professor Gross a question.
c) Every faculty member has either asked Professor
a) ¬T (Abdallah Hussein, Japanese) Miller a question or been asked a question by Pro-
b) ∃xT (x, Korean) ∧∀xT (x, Mexican)
fessor Miller.
c) ∃y(T (Monique Arsenault, y) ∨
d) Some student has not asked any faculty member a
T (Jay Johnson, y))
d) ∀x∀z∃y((x = z) →¬(T (x, y) ∧ T (z, y))) question.
e) ∃x∃z∀y(T (x, y) ↔ T(z, y)) e) There is a faculty member who has never been asked
f) ∀x∀z∃y(T (x, y) ↔ T(z, y)) a question by a student.
8. Let Q(x, y) be the statement “student x has been a con- f) Some student has asked every faculty member a ques-
testant on quiz show y.” Express each of these sentences tion.
in terms of Q(x, y), quantifiers, and logical connectives, g) There is a faculty member who has asked every other
where the domain for x consists of all students at your faculty member a question.
school and for y consists of all quiz shows on television. h) Some student has never been asked a question by a
a) There is a student at your school who has been a con- faculty member.
testant on a television quiz show. 12. Let I(x) be the statement “x has an Internet connection”
b) No student at your school has ever been a contestant and C(x, y) be the statement “x and y have chatted over
on a television quiz show. the Internet,” where the domain for the variables x and y
c) There is a student at your school who has been a con- consists of all students in your class. Use quantifiers to
testant on Jeopardy and on Wheel of Fortune. express each of these statements.
d) Every television quiz show has had a student from a) Jerry does not have an Internet connection.
your school as a contestant.
e) At least two students from your school have been con- b) Rachel has not chatted over the Internet with Chelsea.
c) Jan and Sharon have never chatted over the Internet.
testants on Jeopardy.
d) No one in the class has chatted with Bob.
9. Let L(x, y) be the statement “x loves y,” where the do-
e) Sanjay has chatted with everyone except Joseph.
main for both x and y consists of all people in the world.
Use quantifiers to express each of these statements. f) Someone in your class does not have an Internet con-
nection.
a) Everybody loves Jerry.
b) Everybody loves somebody. g) Not everyone in your class has an Internet connec-
c) There is somebody whom everybody loves. tion.
d) Nobody loves everybody. h) Exactly one student in your class has an Internet con-
e) There is somebody whom Lydia does not love. nection.
f) There is somebody whom no one loves. i) Everyone except one student in your class has an In-
g) There is exactly one person whom everybody loves. ternet connection.
h) There are exactly two people whom Lynn loves. j) Everyone in your class with an Internet connection
i) Everyone loves himself or herself. has chatted over the Internet with at least one other
j) There is someone who loves no one besides himself student in your class.
or herself.
k) Someone in your class has an Internet connection but
10. Let F(x, y) be the statement “x can fool y,” where the has not chatted with anyone else in your class.
domain consists of all people in the world. Use quantifiers l) There are two students in your class who have not
to express each of these statements.
chatted with each other over the Internet.
a) Everybody can fool Fred. m) There is a student in your class who has chatted with
b) Evelyn can fool everybody. everyone in your class over the Internet.
c) Everybody can fool somebody.
d) There is no one who can fool everybody. n) There are at least two students in your class who have
e) Everyone can be fooled by somebody. not chatted with the same person in your class.
f) No one can fool both Fred and Jerry. o) There are two students in the class who between them
g) Nancy can fool exactly two people. have chatted with everyone else in the class.