##  [Canonicalisation de Formule](/fr/node/60845) 

 Définition

La procédure de conversion de formules ou termes en une forme représentante canonique unique à équivalence logique près, utilisée pour la comparaison, l'indexation et les tests d'égalité.

 

 

 

 

 

 





## Principe

Principe

Définir une fonction de normalisation déterministe et une relation d'équivalence choisie ; appliquer des réécritures ordonnées, le renommage des variables liées, l'élimination des ambiguïtés syntaxiques et un ordre standard des opérandes pour produire un représentant unique par classe d'équivalence.

 

 

 

 

 





## Démonstration

Démonstration

Convertir des formules propositionnelles en CNF canonique en distribuant, en supprimant les tautologies, en triant littéraux et clauses lexicographiquement, et en renommant les variables de façon cohérente pour que des formules logiquement équivalentes donnent la même représentation chaîne pour l'indexation.

 

 

 

 

## Mauvaise application

Mauvaise application

Supposer que la canonicalisation est gratuite ou toujours possible ; appliquer une « normalisation » heuristique non déterministe ou dépendant de noms de symboles arbitraires qui ne garantit pas l'unicité entre formules équivalentes.

 

 

 

 

 





## Conséquence

Conséquence

Les formes canoniques permettent des tests d'égalité syntaxique efficaces pour l'équivalence sémantique, soutiennent la mise en cache, l'indexation et l'élimination des doublons dans les systèmes de raisonnement automatique.

 

 

 

 

## Inversion

Inversion

Utiliser plusieurs formes normales également valides ou laisser les formules sous des formes simplifiées non contraintes produit des représentations non déterministes qui entravent les tests d'équivalence directs.

 

 

 

 

 





## Limite

Limite

Dépend de la logique et de l'équivalence choisie (équivalence sémantique, congruence structurelle, alpha-équivalence) ; certaines logiques ne disposent pas d'une canonicalisation complète calculable ou la rendent prohibitivement coûteuse.

 

 

 

 

 





## Tension sémantique

Tension sémantique

La canonicalisation est proche mais distincte de la simplification et de la minimisation : elle privilégie l'unicité et la reproductibilité de la représentation, éventuellement au détriment de la taille syntaxique minimale ou de la lisibilité humaine.

 

 

 

 

 





## Synthèse

Synthèse

La canonicalisation est la transformation déterministe d'équivalents en un unique représentant choisi via des réécritures ordonnées et des conventions standards, de sorte que les questions d'équivalence se réduisent à l'égalité syntaxique.