Nested Qualifiers

Tom Kelliher, MA 190

Feb. 6, 2008

Modeling Nested Qualifiers as Nested Loops

  1. $\forall x \forall y \: P(x, y)$

    Example: For every pair of real numbers, their sum is a real number.

    proved := true;
    for x := each element in its domain
       confirmed := true;
       for y := each element in its domain
          if P(x, y) == false
             confirmed := false;
             break;
    
       if confirmed == false
          proved := false;
          break;
    
    return proved;
    

  2. $\forall x \exists y \: P(x, y)$

    Example: For every integer, $i$, there is an integer, $j$, such that $i + j
= 0$.

    proved := true;
    for x := each element in its domain
       confirmed := false;
       for y := each element in its domain
          if P(x, y) == true;
             confirmed := true
             break;
    
       if confirmed == false
          proved := false;
          break;
    
    return proved;
    

  3. $\exists x \forall y \: P(x, y)$

    Example: There is a real number that when multiplied by any real number, $x$, results in a product of $x$.

    proved := false;
    for x := each element in its domain
       confirmed := true;
       for y := each element in its domain
          if P(x, y) == false
             confirmed := false;
             break;
    
       if confirmed == true
          proved := true;
          break;
    
    return proved;
    

  4. $\exists x \exists y \: P(x, y)$

    Example: There are two integers whose product is 12.

    proved := false;
    for x := each element in its domain
       confirmed := false;
       for y := each element in its domain
          if P(x, y) == true
             confirmed := true;
             break;
    
       if confirmed == true
          proved := true;
          break;
    
    return proved;
    

Exercises

  1. (1 a, b, c) Translate these statements into English. The domain is all real numbers.
    1. $\forall x \exists y \: (x < y)$

    2. $\forall x \forall y \: (((x \geq 0) \wedge (y \geq 0))
\rightarrow (xy \geq 0))$

    3. $\forall x \forall y \exists z \: (xy = z)$

  2. (5 e) Translate this statement into English. $W(x, y)$ means that student $x$ has visited web site $y$. The domain for $x$ is all Goucher students and the domain for $y$ is all web sites.

    \begin{displaymath}
\exists y \forall z \: (y \neq ({\rm David~Belcher}) \wedge (W({\rm
David~Belcher}, z) \rightarrow W(y, z)))
\end{displaymath}

  3. (9 b, c, d, h) Let $L(x, y)$ be the statement ``$x$ loves $y$,'' where the domain for both $x$ and $y$ consists of all people. Use quantifiers to express these statements.
    1. Everybody loves somebody.

    2. There is somebody whom everybody loves.

    3. Nobody loves everybody.

    4. There are exactly two people whom Lynn loves.

  4. (37 b, c) Express each of these statements using quantifiers. Then, form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English.
    1. Someone has visited every country in the world except Libya.

    2. Every movie actor has either been in a movie with Kevin Bacon or has been in a movie with someone who has been in a movie with Kevin Bacon.



Thomas P. Kelliher 2008-02-02
Tom Kelliher