Forme normale disjonctive - Disjunctive normal form

En logique booléenne , une forme normale disjonctive ( DNF ) est une forme normale canonique d'une formule logique consistant en une disjonction de conjonctions ; il peut également être décrit comme un OU de ET , une somme de produits ou (en logique philosophique ) un concept de cluster . En tant que forme normale , il est utile dans la démonstration automatisée de théorèmes .

Définition

Une formule logique est considérée comme en DNF si elle est une disjonction d'une ou plusieurs conjonctions d'un ou plusieurs littéraux . Une formule DNF est sous forme normale disjonctive complète si chacune de ses variables apparaît exactement une fois dans chaque conjonction. Comme dans la forme normale conjonctive (CNF), les seuls opérateurs propositionnels dans DNF sont et ( ), ou ( ), et non ( ). L' opérateur not ne peut être utilisé que dans le cadre d'un littéral, ce qui signifie qu'il ne peut précéder qu'une variable propositionnelle . ${\displaystyle \wedge }$${\style d'affichage \vee }$${\style d'affichage \neg }$

Ce qui suit est une grammaire sans contexte pour DNF :

1. DNF → ( Conjonction ) DNF${\style d'affichage \vee }$
2. DNF → ( Conjonction )
3. Conjonction → Conjonction littérale ${\displaystyle \wedge }$
4. Conjonction → Littéral
5. Littéral → Variable${\style d'affichage \neg }$
6. Littéral → Variable

Où Variable est n'importe quelle variable.

Par exemple, toutes les formules suivantes sont en DNF :

• ${\displaystyle (A\land \neg B\land \neg C)\lor (\neg D\land E\land F)}$
• ${\style d'affichage (A\land B)\lor (C)}$
• ${\style d'affichage (A\land B)}$
• ${\style d'affichage (A)}$

Cependant, les formules suivantes ne sont pas en DNF :

• ${\style d'affichage \neg (A\ou B)}$, puisqu'un OR est imbriqué dans un NOT
• ${\displaystyle \neg (A\land B)\lor C}$, puisqu'un AND est imbriqué dans un NOT
• ${\displaystyle A\lor (B\land (C\lor D))}$, puisqu'un OU est imbriqué dans un ET

La formule est en DNF, mais pas en DNF complet ; une version complète DNF équivalente est . ${\style d'affichage A\ou B}$${\displaystyle (A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)}$

Conversion en DNF

Carte de Karnaugh de la forme normale disjonctive (¬ A ∧¬ B ∧¬ D ) ∨ (¬ A ∧ B ∧ C ) ∨ ( A ∧ B ∧ D ) ∨ ( A ∧¬ B ∧¬ C )

Table de Karnaugh de la forme normale disjonctive (¬ A ∧ C ∧ ¬ D ) ∨ ( B ∧ C ∧ D ) ∨ ( A ∧ ¬ C ∧ D ) ∨ (¬ B ∧ ¬ C ∧ ¬ D ) . Malgré le regroupement différent, les mêmes champs contiennent un "1" comme dans la carte précédente.

La conversion d'une formule en DNF implique l'utilisation d' équivalences logiques , telles que l' élimination de la double négation , les lois de De Morgan et la loi de distribution .

Toutes les formules logiques peuvent être converties en une forme normale disjonctive équivalente. Cependant, dans certains cas, la conversion en DNF peut conduire à une explosion exponentielle de la formule. Par exemple, la conversion de la formule en DNF donne une formule avec 2 ⁿ termes. ${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$

Chaque fonction booléenne particulière peut être représentée par une et une seule forme normale disjonctive complète , l'une des formes canoniques . En revanche, deux formes normales disjonctives simples différentes peuvent désigner la même fonction booléenne, voir les images.

Complexité de calcul

Le problème de satisfiabilité booléenne sur les formules conjonctives de forme normale est NP-difficile ; par le principe de dualité , il en est de même du problème de falsifiabilité sur les formules DNF. Par conséquent, il est co-NP-difficile de décider si une formule DNF est une tautologie .

Variantes

Une variation importante utilisée dans l'étude de la complexité de calcul est k-DNF . Une formule est en k-DNF si elle est en DNF et que chaque conjonction contient au plus k littéraux.

Voir également

• Forme normale algébrique — autres formes normales pour les formules logiques
• Forme canonique de Blake - un cas particulier de DNF
• Logique propositionnelle
• Algorithme Quine-McCluskey - obtient un DNF minimal pour une fonction booléenne donnée
• Table de vérité

Remarques

Les références

• David Hilbert ; Wilhelm Ackermann (1999). Principes de logique mathématique . Société mathématique américaine. ISBN 978-0-8218-2024-7.
• J. Eldon Whitesitt (24 mai 2012). L'algèbre booléenne et ses applications . Société de messagerie. ISBN 978-0-486-15816-7.
• Colin Howson (11 octobre 2005). Logique avec des arbres : une introduction à la logique symbolique . Routledge. ISBN 978-1-134-78550-6.
• David Gries ; Fred B. Schneider (22 octobre 1993). Une approche logique des mathématiques discrètes . Springer Science & Business Media. p. 67–. ISBN 978-0-387-94115-8.

Liens externes

• " Forme normale disjonctive " , Encyclopédie des mathématiques , EMS Press , 2001 [1994]