Convert to Prenex Normal Form

Question

How can I convert the following to Prenex Normal Form. $$ \exists x (P(x) \land (\exists y (Q(y) \land R \left(x,y\right)))) $$

Thanks.

Answer 1

Here the only thing that you have to argue about is if the quantifier attached to the $y$ variable can be "pulled out" into the front of the expression, i.e. if $$\exists x (P(x) \land (\exists y (Q(y) \land R \left(x,y\right)))) \tag{$\star$}$$ and $$\exists x \exists y(P(x) \land ((Q(y) \land R \left(x,y\right)))) \tag{$\star\star$}$$ are logically equivalent expressions. If so, then the latter is by definition in prenex normal form. As you comment in Graham's answer, the expressions $\exists x ( P(x) \land Q(x))$ and $\exists x P(x) \land \exists x Q(x) \ $ are not logically equivalent; the reason for this is that the first one expresses that there is some element satisfying both $P$ and $Q$, while the second says that there is some element satisfying $P$ and some other one satisfying $Q$, and these two might not be the same element.

In our case however we don't encounter this issue because $x$ and $y$ are different variables; in particular, expressing that there is some $y$ satisfying $Q$ and $R$ as in $(\star)$ is equivalent to expressing that there is some $y$ satisfying $P, Q$ and $R$ as in $(\star\star)$, since $P$ does not involve the variable $y$.

Answer 2

A prenex form is a quantified statement where all the quantifiers are occur in the string before the predicates.

You have one quantifier that does not. May you move(/distribute) it? If so, do that.