How would I put the following statement into prenex normal form?
$∀x P(x) ∨ ∀x Q(x)$
Initially I thought you can use subsumption to do it as follows:
$∀x( P(x) ∨ Q(x))$ but I'm under the impression this is "illegal" because x is not free from the forall quantifier..
$\forall x P(x) \vee \forall x Q(x)$ is not equivalent with $\forall x(P(x)\vee Q(x))$. To see this just think of the case $P(x)$ = "x is even" and $Q(x)$ = "x is odd". then certainly (among positive integers) $\forall x(P(x)\vee Q(x))$ hold but $\forall x P(x) \vee \forall x Q(x)$ do not hold.
Instead rewrite $\forall x P(x) \vee \forall x Q(x)$ as $\forall x P(x) \vee \forall y Q(y)$, and then pull out the quantifier one at a time. Thus: $\forall x P(x) \vee \forall y Q(y)$ is equivalent with $\forall x (P(x) \vee \forall y Q(y))$ which is equivalent with $\forall x\forall y( P(x) \vee Q(y))$ which is in prenex normal form.