Exercise 1863Logic, sets and proofs › Quantifiers and negationL1Added 3 Nov 2026

Prenex normal form

#prenex form#quantifiers#normal form

Statement

Put $\neg(\forall x,\ \exists y,\ P(x,y))$ into prenex normal form.

Hint

Apply the negation rules.

Show solutionHide solution

Negation. $\neg(\forall x,\ \exists y,\ P(x,y))\equiv\exists x,\ \neg(\exists y,\ P(x,y))\equiv\exists x,\ \forall y,\ \neg P(x,y)$ .

Conclusion. The prenex form is $\exists x,\ \forall y,\ \neg P(x,y)$ .

General. Every first-order formula is equivalent to one in prenex form (all quantifiers at the front).