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)))