kenneth rosen

Question

S1:for each x in domain:
    if P(x) is false:
        return FALSE
   return TRUE

S2:for each x in domain:
    if P(x) is true:
        return TRUE
return FALSE

Which of the following is correct?

(A) S1 represents $\exists x\,P(x)$, S2 represents $\forall x\,P(x)$  

(B) S1 represents $\forall x\,P(x)$, S2 represents $\exists x\,P(x)$  

(C) Both represent $\forall x\,P(x)$  

(D) Both represent $\exists x\,P(x)$

Comments

hint:kenneth rosen chapter1 page 54 8e edition

Connections Between Quantification and Looping

It is sometimes helpful to think in terms of looping and searching when determining the truth value of a quantification. Suppose that there are $n$ objects in the domain for the variable $x$. To determine whether $\forall x\, P(x)$ is true, we can loop through all values of $x$ to see whether $P(x)$ is always true. If we encounter a value $x$ for which $P(x)$ is false, then we have shown that $\forall x\, P(x)$ is false. Otherwise, $\forall x\, P(x)$ is true.

To see whether $\exists x\, P(x)$ is true, we loop through the $n$ values of $x$ searching for a value for which $P(x)$ is true. If we find one, then $\exists x\, P(x)$ is true. If we never find such an $x$, then we have determined that $\exists x\, P(x)$ is false. (Note that this searching procedure does not apply if there are infinitely many values in the domain. However, it is still a useful way of thinking about the truth values of quantifications.)