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

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?

• See this and this for similar problems. Commented Mar 22, 2015 at 22:45
• I see but I can't really figure it out which relation there are to this? Commented Mar 22, 2015 at 22:56
• The last one is false because you can find interpretations for $P$ and $Q$ such that the statements aren't equivalent. Think of real life examples of this, if necessary. To prove the first one, people need to know what rules you have available or if an informal argument is enough. Commented Mar 22, 2015 at 23:10

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))$