CSE 321 -- HANDOUT ON PRACTICING NESTED QUANTIFERS.
WINTER 2010
For problems 1-5, assume that the following predicates are defined:
Student(x) means that x is a student
Advisor(x, y) means that x is an advisor of y
Translate the following sentences into predicate logic using quantifiers when appropriate assuming that the domain is the set of all students and faculty at the University of Washington and assuming that a person is an advisor if and only if they advise someone.
1. Every student has an advisor
forall x . (Student(x) -> (exists y . Advisor (y,x)))
2. Everyone with an an advisor is a student
forall x. ((exists y. Advisor(y,x)) -> Student(x))
3. Everyone is either a student or an advisor or both.
forall x. ((Student(x)) or (exists y. Advisor(x,y)))
4. Every student has exactly one advisor
forall x. (Student(x) -> (exists y. (Advisor(y,x) -> exists
z. (Advisor(z,x) -> y=z))))
5. Only students have advisors
forall x. ((exists y. Advisor(y,x)) -> Student(x))
For problems 6-10, assume that the following predicates are defined:
Cool(x) means that x is cool
Proof(x) means that x is a proof
Wears(x, y) means that x wears y
Translate the following sentences into predicate logic using quantifiers when appropriate.
6. All the stuff worn by cool people is cool.
forall x. (exists y. (Cool(y) and Wears(y,x)) -> Cool(x))
7. You can wear all cool stuff and still not be cool.
forall x. (not (forall y . (Wears(x,y) -> Cool(y)) -> Cool(x)))
8. Proofs are cool.
forall x. (Proof(x) -> Cool(x))
9. You will not be cool if you wear a proof.
forall x. ((exists y . Proof(y) and Wears(x,y)) -> not Cool(x))
10. Translate the following logical expression into English:
exists x.(Cool(x) and forall y. Wears(y, x))
There is a cool item that everyone wears.
For problems 11-15, assume that the following predicates are defined:
Rich(x) means that x is rich
RockStar(x) means that x is a rock star
Fan(x, y) means that x is a fan of y
Translate the following sentences into predicate logic using quantifiers when appropriate.
11. Every rock star has fans.
forall x. (RockStar(x) -> exists y. Fan (y,x))
12. No rock star has everyone as a fan.
forall x. (RockStar(x) -> exists y. (not Fan(y,x)))
13. You can't be a rock star if you're not rich.
forall x. (RockStar(x) -> Rich(x))
14. Some rich people aren't rock stars.
exists x. (Rich(x) and (not RockStar(x)))
15. Translate the following logical expression into English:
not exists x. forall y (RockStar(y) --> Fan(x, y))
No one is a fan of all rock stars.
For problesm 16-20, assume that the following predicates are defined:
Likes(drinker, beer)
Frequents(drinker, bar)
Serves(bar, beer)
Express the following sentences in First Order Logic using
quantifiers:
16. Every drinker likes 'Bud'
forall x. Likes(x,'Bud')
17. Some drinker likes only 'Bud'
exists x. forall y . (Likes(x,y) <=> y = 'Bud'))
18. Every drinker frequents some bar that serves 'Bud'
forall x. exists y . (Frequents(x,y) and Serves(y,'Bud'))
19. Every drinker frequents some bar that serves some beer that they
don't like
forall x. exists y. (Frequents(x,y) and exists z. (Serves(y,z) and not
Likes(x,z)))
20. Some drinker frequents only bars that seve only beer that that
they don't like
exists x. forall y. (Frequents(x,y) -> forall z. (Serves(y,z) -> not Likes(x,z)))