CSCE 222 Chapter 1.4

« previous | Sunday, February 20, 2011 | next »

Nested Quantifiers

Think of nested quantifiers as loops:

$\mathrm{\forall }x\mathrm{\forall }yP(x,y)$

for x in Domain do
  for y in Domain do
    p(x,y)
  end
end

Order Matters

$\mathrm{\forall }x\mathrm{\exists }y(x+y=0)\equiv ̸\mathrm{\exists }y\mathrm{\forall }x(x+y=0)$

Left side: For all real numbers $x$, there is a real number $y$ such that $x+y=0$. (Namely, $y=-x$)

Right side: There is a real number $y$ such that for all real numbers $x$, $x+y=0$. (can never be true)

Negating Nested Quantifiers

Follow rules of negating quantifiers and De Morgan's Laws, just cascade down the line.

$\begin{array}{rl}\mathrm{\forall }w\mathrm{\neg }\mathrm{\forall }a\mathrm{\exists }f(P(w,f)\wedge Q(f,a))& \equiv \mathrm{\forall }w\mathrm{\exists }a\mathrm{\neg }\mathrm{\exists }f(P(w,f)\wedge Q(f,a))\\ & \equiv \mathrm{\forall }w\mathrm{\exists }a\mathrm{\forall }f\mathrm{\neg }(P(w,f)\wedge Q(f,a))\\ & \equiv \mathrm{\forall }w\mathrm{\exists }a\mathrm{\forall }f(\mathrm{\neg }P(w,f)\vee \mathrm{\neg }Q(f,a))\end{array}$