In English, this formula says, "someone ($x$) is everybody's friend and nobody's foe". (Or, "someone is everybody's friend and has no foes", depending on how $Foe(a,b)$ is to read, and assuming is-a-foe-of is not symmetric – the question doesn't say. See comments below with @bof.) Note that you can rename the rightmost bound variable from $y$ to for example $z$, which may make it easier to figure out the meaning when you're first learning how to convert between ordinary language and first order formulas.
Converting it to prenex normal form is fairly straightforward. First, make sure that the bound variables are distinct, then move them across connectives. When a quantifier crosses a negation it changes from universal to existential and vice versa, as seen in step (2). Thus:
$$
\begin{align}
\exists x(\forall y Friend(x,y) \;\&\; \lnot (\exists y Foe(y,x))) &\iff \exists x(\forall y \,Friend(x,y) \;\&\; (\forall y \,\lnot Foe(y,x))) \tag{1}\\
&\iff \exists x(\forall y \,Friend(x,y) \;\&\; \forall y \,\lnot Foe(y,x)) \tag{2}\\
&\iff \exists x\forall y \,(Friend(x,y) \;\&\; \lnot Foe(y,x)) \tag{3}\\
\end{align}
$$
What each step does:
- $\lnot \exists y$ becomes $\forall y \,\lnot$
- Drop unneeded parentheses around right subformula
Coalesce universal quantifiers in conjoined subformulas into one universal quantifier around the entire conjunction: $$(\forall y\, p) \,\&\, (\forall y\, q) \iff \forall y\, (p \,\&\, q)$$
In fact the following is valid:
$$(\forall y\, p) \,\&\, (\forall z\, q) \iff \forall y\, (p \,\&\, q[z/y])$$
where $q[z/y]$ is the result of substituting $y$ for $z$ in $q$.
Two problems:
First, as Graham points out, going from
$$(\exists x \forall y \ r_1(x,g(y)) \lor \exists x \ \neg r_2(x,u))$$
to
$$\exists x \ ( \forall y \ r_1(x,g(y)) \lor \neg r_2(x,u))$$
is not an application of the Prenex laws
However, as it so happens, the existential does distribute over the disjunction, so you're lucky, and in fact this is a correct equivalence. But you'll have to justify it by 'Distribution of $\exists$ over $\lor$' rather than reference to Prenex laws. Or, as Graham suggests, first replace variables, and then use the Prenex Laws.
Second, going from
$$\exists x \ ( \forall y \ r_1(x,g(y)) \lor \neg r_2(x,u))$$
to
$$\forall y \exists x \ ( r_1(x,g(y)) \lor \neg r_2(x,u))$$
is a mistake. By the Prenex laws, the formula
$$\forall y \ r_1(x,g(y)) \lor \neg r_2(x,u)$$
is equivalent to:
$$\forall y ( r_1(x,g(y)) \lor \neg r_2(x,u))$$
and so, substituting that back, you get that:
$$\exists x \ ( \forall y \ r_1(x,g(y)) \lor \neg r_2(x,u))$$
is equivalent to
$$\exists x \ \forall y ( r_1(x,g(y)) \lor \neg r_2(x,u))$$
Best Answer
Yes, that is correct, though I would break that step into two: first replace the variable, and then bring out the quantifier. So:
$(\forall u) ((\exists x) S(x,y) \rightarrow (R(x) \rightarrow \neg S(x,u))) \overset{\text{Replace variables}}\Leftrightarrow$
$(\forall u) ((\exists w) S(w,y) \rightarrow (R(x) \rightarrow \neg S(x,y)))\overset{\text{Prenex Law}}\Leftrightarrow$
$(\forall u) (\forall w) (S(w,y) \rightarrow (R(x) \rightarrow \neg S(x,y)))$