Course contentsShow
← Computer Science
Lesson 57 of 2,8722. Discrete Mathematics for CSFree lesson

Prenex Normal Form

Learn to transform predicate logic formulas by moving all quantifiers to the front.

Prenex Normal Form

What You'll Learn

You'll learn how to reorganize predicate logic formulas so that all quantifiers (∀ and ∃) appear at the very beginning, making them easier to analyze and work with.

The Core Idea

Imagine organizing a messy closet: instead of having shoes, shirts, and pants scattered randomly, you group all shirts together, all pants together, and so on. Prenex Normal Form (PNF) does something similar with logical formulas—it pulls all quantifiers to the front in one neat bundle.

In predicate logic, quantifiers can appear anywhere within a formula. For example:

(∀x P(x)) → (∃y Q(y))

Prenex Normal Form transforms this by moving all quantifiers to the front:

∀x ∃y (P(x) → Q(y))

The quantifiers now form a "prefix" (hence "prenex"), followed by a quantifier-free formula.

Why Does This Matter?

Having all quantifiers at the front makes formulas:

  • Easier to analyze for logical equivalence
  • Simpler to process in automated reasoning systems
  • Clearer to understand at a glance

The Transformation Process

To convert a formula to PNF:

  1. Eliminate implications using logical equivalences (A → B becomes ¬A ∨ B)
  2. Push negations inward using De Morgan's Laws and quantifier negation rules
  3. Rename variables if needed to avoid conflicts when quantifiers are moved
  4. Pull quantifiers outward one by one until they're all at the front

The order of quantifiers matters! ∀x ∃y P(x,y) means something different from ∃y ∀x P(x,y).

Key Takeaway: Prenex Normal Form standardizes predicate logic formulas by relocating all quantifiers to the beginning, creating a clear prefix-body structure that simplifies logical analysis.