Une formule exprimée comme une conjonction de disjonctions de littéraux, couramment utilisée dans la résolution de satisfiabilité et la normalisation logique.

Principe

La FNC organise une formule en une conjonction finie de clauses, chaque clause étant une disjonction de littéraux ; des équivalences logiques (De Morgan, distributivité) et des manipulations de quantificateurs servent à convertir des formules en FNC en préservant la satisfaisabilité ou l'équivalence selon les transformations appliquées.

Démonstration

La formule (p ∨ q) ∧ (¬p ∨ r) est en FNC ; pour convertir (p ∧ q) ∨ r en FNC, appliquer la distributivité pour obtenir (p ∨ r) ∧ (q ∨ r). En raisonnement automatique les clauses FNC sont souvent traitées comme des ensembles de littéraux.

Mauvaise application

Supposer que la conversion en FNC préserve toujours l'équivalence logique de la formule d'origine ; certaines procédures introduisent des symboles frais ou des fonctions de Skolem et produisent seulement une FNC équipossible, pas équivalente, ce qui conduit à des affirmations incorrectes sur la préservation des modèles.

Conséquence

Mettre en FNC permet l'utilisation directe des solveurs SAT et des prouveurs basés sur la résolution, facilite l'indexation des clauses et la propagation d'unités, et standardise l'entrée pour de nombreuses procédures de décision.

Inversion

La perspective duale est la Forme Normale Disjonctive (FND), où la formule est une disjonction de conjonctions de littéraux ; passer de la FNC à la FND peut révéler des implicants premiers mais provoque souvent une explosion exponentielle de taille.

Limite

La FNC exige que les clauses soient des disjonctions de littéraux ; elle ne prescrit pas le placement des quantificateurs et ne prend pas en charge des connecteurs plus riches sans transformation, et une conversion naïve peut entraîner une augmentation exponentielle de la taille.

Tension sémantique

FNC vs ensemble de clauses vs théorie normalisée : la FNC comme forme syntaxique est liée à l'ensemble abstrait de clauses utilisé par les solveurs, mais cette correspondance peut être brouillée lorsque des symboles frais ou la skolemisation altèrent l'équivalence.

Synthèse

La Forme Normale Conjonctive est la mise en forme canonique organisant une formule en une conjonction de clauses disjonctives de littéraux ; elle est centrale pour les algorithmes de satisfiabilité et de normalisation, tout en nécessitant de la prudence quant à l'équivalence vs l'équipossibilité.