Définition - Que signifie la forme normale disjonctive (DNF)?
La forme normale disjonctive (DNF) est la normalisation d'une formule logique en mathématiques booléennes. En d'autres termes, une formule logique est dite sous forme normale disjonctive s'il s'agit d'une disjonction de conjonctions avec chaque variable et que sa négation est présente une fois dans chaque conjonction. Toutes les formes normales disjonctives ne sont pas uniques, car toutes les formes normales disjonctives pour la même proposition sont mutuellement équivalentes.
La forme normale disjonctive est largement utilisée dans des domaines tels que la démonstration automatisée de théorèmes.
Definir Tech explique la forme normale disjonctive (DNF)
Une formule logique est sous forme normale disjonctive si et seulement s'il existe une alternance d'une ou plusieurs conjonctions d'un ou plusieurs littéraux. Une formule est considérée comme sous forme normale disjonctive complète si toutes les variables impliquées ne sont représentées qu'une seule fois dans chaque clause. Semblables à la forme normale conjonctive, les opérateurs propositionnels dans la forme normale disjonctive sont les mêmes: AND, OR et NOT.
Toutes les formules logiques peuvent être converties en une forme normale disjonctive équivalente. Cependant, dans certains cas, une explosion exponentielle de la fonction logique est possible en raison de la conversion en forme normale disjonctive. Un autre point saillant est que toute fonction booléenne unique peut être représentée par une seule et unique forme normale disjonctive complète. À l'aide de techniques telles que la méthode de la table de vérité, des arbres de vérité ou une table d'équivalences logiques, une forme normale disjonctive pour des formules logiques peut être générée. K-DNF, une variante de forme normale disjonctive, est largement utilisé et populaire dans l'étude de la complexité de calcul.