Une normalisation syntaxique des formules du premier ordre qui déplace tous les quantificateurs en tête pour produire une formule équivalente composée d'un préfixe de quantificateurs suivi d'une matrice sans quantificateurs.

Principe

Séparer la structure de liaison (les quantificateurs) du noyau propositionnel en permutant et renommant les variables de sorte que tous les quantificateurs forment un préfixe contigu tout en préservant l'équivalence logique (ou la satisfiabilité) selon la sémantique visée.

Démonstration

À partir de ∀x (P(x) → ∃y Q(y,x)), convertir en forme prénexe en renommant et en déplaçant les quantificateurs pour obtenir ∀x ∃y (¬P(x) ∨ Q(y,x)) ou, après skolemisation pour la satisfiabilité, ∀x (¬P(x) ∨ Q(f(x),x)). Ceci illustre le déplacement en tête des quantificateurs et la matrice sans quantificateurs.

Mauvaise application

Déplacer les quantificateurs de façon automatique sans tenir compte de la capture de variables, des changements de portée, ni de la différence entre préserver l'équivalence et préserver la satisfiabilité. Par exemple, supprimer des dépendances lors de la skolemisation peut altérer la dépendance existentielle vis‑à‑vis des variables universelles.

Conséquence

Les formules en forme prénexe facilitent la comparaison, l'application de la résolution et de nombreuses procédures métathéoriques (p. ex. classification selon le préfixe de quantificateurs), au prix d'une perte d'information sur les portées locales et d'un recours possible à la skolemisation pour préserver la satisfiabilité.

Inversion

L'inverse consiste à reconstruire les portées variables originales et repousser les quantificateurs à l'intérieur de la matrice afin de refléter les dépendances locales ; la forme prénexe aplatie perd cette information locale.

Limite

S'applique à la logique classique du premier ordre et à des logiques apparentées ; ne garantit pas toujours la préservation de la vérité dans des logiques non classiques sans précautions, et la skolemisation supprime les existentials seulement pour la satisfiabilité, pas pour l'équivalence stricte dans un cadre conservatif.

Tension sémantique

Tension entre l'uniformité syntaxique (tous les quantificateurs en tête) et la localité sémantique (quantificateurs dont le sens dépend des connecteurs voisins), ainsi qu'entre la préservation de l'équivalence logique et la préservation seulement de la satisfiabilité.

Synthèse

La forme prénexe est une normalisation syntactique qui extrait la structure des quantificateurs en un préfixe pour faciliter le raisonnement mécanique et la classification, au prix d'une obscurcissement des portées locales ; son usage exige une attention aux dépendances de variables et à l'objectif de préservation (équivalence vs satisfiabilité).