Prenex normal form of $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$

Question

I have the statement $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$ and I have to write it in prenex normal form.

First I use the second De Morgan law

$\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big) \equiv \neg \forall x \ P(x) \wedge \neg \forall x \ Q(x)$

Then I use the second De Morgan law for quantifiers

$\neg \forall x \ P(x) \wedge \neg \forall x \ Q(x) \equiv \exists x \ \neg P(x) \wedge \exists x \ \neg Q(x)$

Now I can write it in prenex normal form but I made it in two different ways

$\exists x \ \neg P(x) \wedge \exists x \ \neg Q(x) \equiv \exists x \exists y \big( \neg P(x) \wedge \neg Q(y) \big)$

and

$\exists x \ \neg P(x) \wedge \exists x \ \neg Q(x) \equiv \exists x \big( \neg P(x) \wedge \neg Q(x) \big)$

Which one is correct/wrong and why?

Answer 1

The former formula is the correct statement.

$\exists X \,(\lnot P(X)) \land \exists X \, (\lnot Q(X))$

$\lnot P(x) \land \exists X \, (\lnot Q(X))$ by existential instantation

$\exists X \, \left[\lnot P(X) \land \exists X \, (\lnot Q(X))\right]$ by existential generalization

note that we cannot apply existential generalization to the wff $\lnot P(X) \land \exists X \, (\lnot Q(X))$ because $X$ appears free.

However if we rename:

$\exists X \, \left[\lnot P(X) \land \exists Y \, (\lnot Q(Y))\right]$

we no longer have the above mentioned problem. So from here it is not hard to show that we have

$\exists X \, \exists Y\,(\lnot P(X) \land \lnot Q(Y))$