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.

  • $\begingroup$ en.m.wikipedia.org/wiki/Rules_of_passage_%28logic%29 $\endgroup$ – symplectomorphic Mar 22 '15 at 14:54
  • $\begingroup$ (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{}$ $\endgroup$ – Michael Hardy Mar 22 '15 at 14:58
  • $\begingroup$ Okay this is hard I need more help to do this assignment $\endgroup$ – Alim Teacher Mar 22 '15 at 20:50


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.