# Statements in prenex normal form.

Put these statements in prenex normal form.

a) $\exists x \ P(x) \vee \exists x \ Q(x) \vee A$, $\textit{where A is a proposition not involving any quantifiers.}$

b) $\neg (\forall x \ P(x) \vee \forall x \ Q(x))$

c) $\exists x \ P(x) \rightarrow \exists x \ Q(x)$

I just need a hint.

• en.m.wikipedia.org/wiki/Rules_of_passage_%28logic%29 – symplectomorphic Mar 22 '15 at 14:54
• (b) is the same as $neg(\forall x\,P(x)\vee\forall y\,Q(y))$. (The latter form is called an "alphabetic variant" of the former.) Sometimes viewing it that way is useful. ${}\qquad{}$ – Michael Hardy Mar 22 '15 at 14:58
• Okay this is hard I need more help to do this assignment – Alim Teacher Mar 22 '15 at 20:50

a)

$$\exists x ( P(x) \lor Q(x) \lor A)$$

b) Distribute the NOT Operation $$\exists x \lnot P(x) \land \exists x \lnot Q(x)$$

$\exists$ quantifier is not distributed over AND operation, thus we rename

$$\exists x \lnot P(x) \land \exists y \lnot Q(y)$$

$$\exists x \exists y (\lnot P(x) \land \lnot Q(y))$$

c) Simplify the formula

$$\lnot(\exists x P(x)) \lor (\exists x Q(x))$$ $$( \forall x \lnot P(x) ) \lor (\exists x Q(x))$$

Rename one of the variable

$$( \forall x \lnot P(x) ) \lor (\exists z Q(z))$$

$$\forall x \exists z (\lnot P(x) \lor Q(z))$$