Le processus de transformation qui réduit une formule logique à une forme syntaxiquement plus simple et sémantiquement équivalente en éliminant les redondances et en appliquant des identités logiques.

Principe

Appliquer des règles de réécriture sûres (associativité, distributivité, lois de De Morgan, élimination des doubles négations, idempotence, absorption, etc.) pour obtenir une expression avec des constructions syntaxiques moins nombreuses ou plus claires tout en préservant l'équivalence logique.

Démonstration

Simplifier la formule propositionnelle (p ∧ vrai) ∨ (p ∧ faux) en appliquant les lois d'identité et de domination pour obtenir la formule équivalente et plus simple p.

Mauvaise application

Remplacer une formule par une autre qui est seulement équisatisfaisable (et non équivalente) quand l'équivalence est exigée, ou appliquer des transformations algébriques qui supposent des propriétés absentes de la logique (par exemple traiter l'implication comme une égalité).

Conséquence

La simplification qui préserve la sémantique réduit le coût d'évaluation, facilite le raisonnement automatisé et peut faire apparaître une structure exploitable pour des transformations ultérieures telles que la canonicalisation ou l'optimisation.

Inversion

L'expansion ou la distribution qui augmente la taille syntaxique (par exemple une expansion CNF naïve) peut exposer la structure en clauses mais inverse l'objectif de simplification en rendant les formules plus volumineuses.

Limite

Visée pour des transformations qui maintiennent l'équivalence logique ; certains algorithmes produisent volontairement des formes équisatisfaisables mais non équivalentes (prénexation, skolemisation) et sortent donc du cadre strict de la simplification de formule.

Tension sémantique

La simplification est en tension avec la normalisation et la minimisation : la simplification cherche la lisibilité et une complexité syntaxique réduite, la normalisation vise une forme standard et la minimisation vise l'usage minimal de ressources, buts qui peuvent entrer en conflit.

Synthèse

La simplification de formule est une suite d'étapes de réécriture préservant la sémantique qui supprime les redondances et clarifie la structure, produisant une formule équivalente mieux adaptée au raisonnement et au calcul.