The slide on "Order of quantifiers matters" changed...

[Subbarao Kambhampati <rao@asu.edu>]

Folks:
 The example I used to make the point that the order of quantifiers 
matters is sort of confusing.
I changed that slide now and show from first principles how just shifting 
the quantifier order
(ie. forall x therexists y  changes to there exists y forall x ) changes 
meaning.

Rao

ps: Here is a small trick question--do you think quantifiers can be 
distributed over all connectives?
In particular, check which of these are valid:

forall x P(x) & Q(x) == forall x P(x) & forall x Q(x)

forall x P(x) V Q(x)  == forall x P(x) V forall x Q(x)

exists x P(x) V Q(x)  == exists x P(x) V exists x Q(x)

exists x P(x) & Q(x)   == exists x P(x) & exists x Q(x)


[Hint: each quantifier can be distributed only one one of the two 
conjunctives without changing the meaning]