Conversion of formula to Prenex Normal Form A question about formula conversion to prenex normal form:
Does this formula convert to 1 or 2 or both of them are incorrect ?
∃x∃y∀z S(x,y,z) ∨ ∀x∃z∃y S(x,y,z)  ~


*

*∃x∃y∀z∀g∃h (S(x,y,z) ∨ S(g,y,h))

*∃x∃y∀z∀g∃h∃j (S(x,y,z) ∨ S(g,j,h))


And is this conversion correct ?
∃x∃y∀z S(x,y,z) ∨ ∀x∃y∃z S(x,y,z) ~
∃x∃y∀z∀g∃h (S(x,y,z) ∨ S(g,y,h))
 A: Some of the conversion you listed are not correct,
For $(2)$, it rewrited $x$ as $g$, $z$ as $h$ and $y$ as $j$ and didn't change the order of the quantifier, correct!
$$∃x∃y∀z S(x,y,z) ∨ \color{orange}{∀x}\color{blue}{∃z}\color{red}{∃y} S(x,y,z)\equiv∃x∃y∀z\color{orange}{∀g}\color{blue}{∃h}\color{red}{∃j} (S(x,y,z) ∨ S(g,j,h))\tag*{$\require{enclose}
\enclose{box}[mathcolor="green"]{\unicode{x2714}}$}$$
But for $(1)$ the order changed, the equivalence which will not hold.
we can put $g,h$ anywhere before $y$, but not after.
The idea is do not change the order of the quantifier, to fix $(1)$ we can write:
\begin{align}
∃x∃y∀z S(x,y,z) ∨ \color{orange}{∀x}\color{blue}{∃z}\color{red}{∃y} S(x,y,z)
&\equiv ∃x\color{orange}{∀g}\color{blue}{∃h}\color{red}{∃y}∀z(S(x,y,z) ∨  S(g,y,h))\\
\end{align}
Similar problem for the last expression, order changed,
Since we want $x$ before $y$, and $z$ after $y$, to fix it we can write:
\begin{align}
∃x∃y∀z S(x,y,z) ∨ ∃x\color{orange}{∀x}\color{red}{∃y}\color{blue}{∃z} S(x,y,z)
&\equiv∃x\color{orange}{∀g}\color{red}{∃y}\color{blue}{∃h}∀z (S(x,y,z) ∨ S(g,y,h))
\end{align}
In conclusion, $(2)$ is the only correct conversion listed above.
