Définition
Une formule exprimée comme une disjonction de conjonctions de littéraux, souvent utilisée pour l'analyse de la structure booléenne et la simplification.
Principe
Principe
La FND organise une formule comme une disjonction finie de termes, chaque terme étant une conjonction de littéraux ; c'est la duale de la FNC et elle se déduit par lois de De Morgan et distributivité, mettant souvent en évidence les implicants premiers et la construction par table de vérité.
Démonstration
Démonstration
La formule (p ∧ q) ∨ (¬p ∧ r) est en FND ; toute fonction de vérité peut s'écrire en FND en énumérant les assignations satisfaisantes et en formant les conjonctions de littéraux correspondantes.
Mauvaise application
Mauvaise application
Supposer que la FND est toujours la meilleure représentation pour les tâches de raisonnement ; convertir une formule quelconque en FND complète peut provoquer une explosion exponentielle et détruire la compacité structurelle exploitée par d'autres méthodes.
Conséquence
Conséquence
Lorsque la FND est d'une taille raisonnable, elle facilite l'énumération des modèles, la simplification par disjonction et l'identification des implicants premiers ; elle sert pour l'évaluation directe et des tâches de synthèse.
Inversion
Inversion
L'agencement opposé est la FNC, une conjonction de disjonctions ; tandis que la FNC est adaptée aux solveurs, la FND est adaptée à l'examen des modèles et les deux représentent des compromis entre concision et commodité algorithmique.
Limite
Limite
La FND exige que chaque disjonct soit une conjonction de littéraux et ne traite pas intrinsèquement les quantificateurs ou connecteurs non booléens sans transformation ; l'usage pratique est limité par la croissance combinatoire potentielle.
Tension sémantique
Tension sémantique
FND vs FND minimale vs somme-de-produits : la FND brute énumère tous les termes satisfaisants, tandis qu'une FND minimale compresse en regroupant des implicants ; la tension porte sur expressivité contre compacité.
Synthèse
Synthèse
La Forme Normale Disjonctive est l'agencement canonique disjonction-de-conjonctions qui met en évidence les assignations satisfaisantes et les implicants premiers ; utile pour le raisonnement direct sur modèles mais limitée par la croissance combinatoire.