Predicate logic - What is the point of changing a variable name?

Question

I recently learned a bit about predicate logic, and now I am facing an exercice which is turning my mind upside down. I am not sure how I can achieve one of these, and I don't understand why someone would change a variable name all of the sudden?

Here's the original logical equation:

¬∀x(   ¬(∃y ¬P(x,y))   ∨    (¬∀y ¬Q(x,y))   )

Here are the four possible answer:

∃x∃y∃z(¬P(x,y)∨ Q(x,z))

∃x∃y∃z(¬P(x,y)∧ Q(x,z))

∃x∃y∃z(P(x,y)∨¬Q(x,z))

∃x∃y∃z (P(x,y)∧¬Q(x,z))

Here's my logic:

¬∀x(   ¬(∃y ¬P(x,y))   ∨    (¬∀y ¬Q(x,y))   ) // Original logic in the question

∃x¬(   ¬(∃y ¬P(x,y))   ∨    (¬∀y ¬Q(x,y))   ) // De Morgan

∃x (   (∃y ¬P(x,y))    ∧   ¬(¬∀y ¬Q(x,y))   ) // De Morgan

∃x (   (∃y ¬P(x,y))    ∧   ¬(∀y Q(x,y))     ) // Double negation

∃x (   (∃y ¬P(x,y))    ∧   (∃y ¬Q(x,y))     ) // Double negation + De Morgan

∃z ¬Q(x,z) = ∃y ¬Q(x,y)
∃x (   (∃y ¬P(x,y))    ∧   (∃z ¬Q(x,z))     ) // Variable change

∃x (   ∃y ¬P(x,y)      ∧     ∃z ¬Q(x,z)     ) // Parentesis removal by priority

∃x (   ∃y∃z: ¬P(x,y)   ∧      ¬Q(x,z)       ) // Organisation

∃x∃y∃z: (   ¬P(x,y)    ∧      ¬Q(x,z)       ) // Organisation

EDIT 1:

Thank you very much @Graham Kemp and everybody in the comments. Here's what I did, at last. Could someone validate if the logic is right? I achieved one of the answer, however, I want to make sure I understood correctly. Thank you!

¬∀x(   ¬(∃y ¬P(x,y))   ∨   (¬∀y ¬Q(x,y))   ) // Original

¬∀x(   ¬(∃y ¬P(x,y))   ∨   (¬∀z ¬Q(x,z))   ) // Variable Change

¬∀x(   ¬(¬∀y P(x,y))   ∨   (¬∀z ¬Q(x,z))   ) // Morgan

¬∀x(   ¬(∃y ¬P(x,y))   ∨   (¬∀z ¬Q(x,z))   ) // Morgan

¬∀x(    (∀y P(x,y))    ∨   (¬∀z ¬Q(x,z))   ) // Morgan

¬∀x(    ∀y¬∀z (P(x,y)  ∨       ¬Q(x,z) )   ) // Simplification

¬∀x(   ¬∃y¬∃z¬(P(x,y)  ∨       ¬Q(x,z) )   ) // Morgan

¬∀x(   ¬∃y¬∃z (¬P(x,y) ∧       Q(x,z)  )   ) // Morgan

¬∀x(   (¬∃y ¬P(x,y))   ∧   (¬∃z Q(x,z))    ) // Organisation

∃x¬(   (¬∃y ¬P(x,y))   ∧   (¬∃z Q(x,z))    ) // Morgan

∃x (   ¬(¬∃y ¬P(x,y))  ∨   ¬(¬∃z Q(x,z))   ) // Morgan

∃x (   ¬(¬∃y ¬P(x,y))  ∨   ¬(∀z¬Q(x,z))    ) // Morgan

∃x (   ¬(¬∃y ¬P(x,y))  ∨    (∃z Q(x,z))    ) // Morgan

∃x (   (¬∀y P(x,y))    ∨    (∃z Q(x,z))    ) // Morgan

∃x (   (∃y ¬P(x,y))    ∨    (∃z Q(x,z))    ) // Morgan

∃x (   ∃y∃z (¬P(x,y)   ∨       Q(x,z))     ) // Simplification

∃x∃y∃z (¬P(x,y)        ∨       Q(x,z)      ) // Simplification

Answer 1

and I don't understand why someone would change a variable name all of the sudden?

When distributing, you are overlapping the scopes of the quantifiers and need to be clear on which variable is bound to which quantifier.   For this purpose, we use substitution (sometimes called alpha-substitution) to ensure each quantifier is bound to a distinct term.   It is always best to choose a 'new', or 'fresh', variable - one which does not occur elsewhere in the statement.

Now, when $z$ does not occur free in $Q(x,y)$, then $\forall y~Q(x,y)$ is equivalent to $\forall z~Q(x,z)$.  

Thus $\lnot\forall x~(\lnot(\exists y~\lnot P(x,y))\lor(\lnot\forall y~\lnot Q(x,y)))$ equates to $\lnot\forall x~(\lnot(\exists y~\lnot P(x,y))\lor(\lnot\forall z~\lnot Q(x,z)))$ and you may now safely distribute to prenex form (well, okay, after carefully using negation duality rules).

$${\lnot\forall x~(\lnot(\exists y~\lnot P(x,y))\lor(\lnot\forall y~\lnot Q(x,y)))\\\lnot\forall x~(\lnot(\exists y~\lnot P(x,y))\lor(\lnot\forall z~\lnot Q(x,z)))\\\exists x~\lnot(\lnot(\exists y~\lnot P(x,y))\lor(\lnot\forall z~\lnot Q(x,z)))\\\exists x~(\lnot\lnot(\exists y~\lnot P(x,y))\land\lnot(\lnot\forall z~\lnot Q(x,z)))\\\vdots\\\exists x~\exists y~\forall z~(\neg P(x,y)\wedge\neg Q(x,z))}$$

Also, no, your original statement is not equivalent to any of the four suggested answers. There would seem to be a typo somewhere.

Answer 2

I mistyped the answer in the comment (on the question) above. Here is my derivation:

I used Lemma 2.29 in Mendelson, Intro. to Math. Log. \begin{array}{rc} &\neg\forall x\quad[ \neg(\exists y\neg P(x,y)) \quad\vee\quad (\neg\forall y\neg Q(x,y))] \\ \text{In the last disjunct $y \rightarrow z$}&\neg\forall x\quad[ \neg(\exists y\neg P(x,y)) \quad\vee\quad (\neg\forall z\neg Q(x,z))] \\ (\neg A\vee B) \iff (A\Rightarrow B)&\neg\forall x\quad[(\exists y\neg P(x,y)) \quad\Rightarrow\quad (\neg\forall z\neg Q(x,z))] \\ \text{part $b$) on the "$y$"}&\neg\forall x\quad[\forall y(\neg P(x,y) \quad\Rightarrow\quad \exists z Q(x,z))] \\ \text{part $d$) on the "$z$"}&\neg\forall x\quad[\forall y\ \exists z\ (\neg P(x,y) \quad\Rightarrow\quad Q(x,z))] \\ (A\Rightarrow B) \iff (\neg A\vee B)&\neg\forall x\quad[\forall y\ \exists z\ ( P(x,y) \quad\vee\quad Q(x,z))] \\ \text{$f$) and $e$) on the "$x$","$y$","$z$"}&\exists x\ \exists y\ \forall z\ \neg(P(x,y) \quad\vee\quad Q(x,z)) \\ \end{array}