- Show that $\forall x P(x) \wedge \exists x Q(x)$ is logically equivalent to $\forall x \exists y (P(x) \wedge Q(y))$, where all quantifiers have the same nonempty domain.
- Show that $\forall x P(x) \vee \exists x Q(x)$ is equivalent to $\forall x \exists y (P(x) \vee Q(y))$, where all quantifiers have the same nonempty domain.
A statement is in prenex normal form (PNF) if and only if it is of the form
$Q_1x_1 Q_2x_2...Q_kx_kP(x_1,x_2,…..,x_k),$
where each $Q_i,i=1,2,...,k,$ is either the existential quantifier or the universal quantifier, and $P(x_1,...,x_k)$ is a predicate involving no quantifiers. For example $\exists x \forall y(P(x,y) \wedge Q(y))$ is in prenex normal form, whereas $\exists x P(x) \vee \forall x Q(x)$ is not (because the quantifiers do not all occur first).Every statement formed from propositional variables,predicates,T, and F using logical connectives and quantifiers is equivalent to a statement in prenex normal form.
