Forme normale disjonctive

Forme normale disjonctive
Article principal : Calcul des propositions.

En logique booléenne ou en Calcul des propositions, une forme normale disjonctive (FND) est une normalisation d'une expression logique qui est une disjonction de clauses conjonctives. Elle est utilisée dans la démonstration automatique de théorèmes. Une expression logique est en FND si et seulement si elle est une disjonction d'une ou plusieurs conjonctions d'un ou plusieurs littéraux. Tout comme dans une forme normale conjonctive (FNC), les seuls opérateurs dans une FND sont le et logique, le ou logique et la négation. L'opérateur non ne peut être utilisé que dans un littéral, c'est-à-dire qu'il ne peut que précéder une variable. Par exemple, toutes les expressions suivantes sont en FND:

A \or B
A\!
(A \and B) \or C
(A \and \neg B \and \neg C) \or (\neg D \and E \and F)

Cependant, les expressions suivantes ne sont pas en FND:

\neg(A \or B) — la négation s'applique à toute la parenthèse plutôt que directement à une variable
A \or (B \and (C \or D)) — un ou est imbriqué dans un et

Convertir une expression vers une FND requiert l'utilisation d'équivalences logiques, comme l'élimination de double négations, les lois de De Morgan, et la loi de distributivité. Toutes les expressions booléennes peuvent être converties en FND. Cependant, dans quelques cas la conversion à la FND peut mener à un allongement exponentiel de l'expression. Par exemple, la FND d'une expression de la forme suivante a 2n termes :

(X_1 \or Y_1) \and (X_2 \or Y_2) \and \dots \and (X_n \or Y_n)

Ce qui suit est une grammaire formelle pour la FND :

  1. <ou> → ∨
  2. <et> → ∧
  3. <non> → ¬
  4. <disjonction> → <conjonction>
  5. <disjonction> → <disjonction> <ou> <conjonction>
  6. <conjonction> → <littéral>
  7. <conjonction> → (<conjonction> <et> <littéral>)
  8. <littéral> → <terme>
  9. <littéral> → <non><terme>

où <terme> est une variable quelconque.

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Forme normale disjonctive de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Forme normale conjonctive — Article principal : Calcul des propositions. En logique booléenne et en calcul des propositions, une forme normale conjonctive (FNC) est une normalisation d une expression logique qui est une conjonction de clauses, autrement dit une… …   Wikipédia en Français

  • FORME — L’histoire du concept de forme et des théories de la forme est des plus singulières. Nous vivons dans un monde constitué de formes naturelles. Celles ci sont omniprésentes dans notre environnement et dans les représentations que nous nous en… …   Encyclopédie Universelle

  • forme disjonctive normale — norminė disjunkcinė forma statusas T sritis automatika atitikmenys: angl. disjunctive normal form; DNF vok. disjungtive Normalform, f rus. дизъюнктивная нормальная форма, f pranc. forme disjonctive normale, f …   Automatikos terminų žodynas

  • FND — Forme normale disjonctive Article principal : Calcul des propositions. En logique booléenne ou en Calcul des propositions, une forme normale disjonctive (FND) est une normalisation d une expression logique qui est une disjonction de clauses… …   Wikipédia en Français

  • Antilogie — Calcul des propositions Pour les articles homonymes, voir Déduction. Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C est la version moderne de la logique stoïcienne. C… …   Wikipédia en Français

  • Calcul Des Propositions — Pour les articles homonymes, voir Déduction. Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C est la version moderne de la logique stoïcienne. C est aussi la première… …   Wikipédia en Français

  • Calcul propositionnel — Calcul des propositions Pour les articles homonymes, voir Déduction. Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C est la version moderne de la logique stoïcienne. C… …   Wikipédia en Français

  • Expression booléenne — Calcul des propositions Pour les articles homonymes, voir Déduction. Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C est la version moderne de la logique stoïcienne. C… …   Wikipédia en Français

  • Logique des propositions — Calcul des propositions Pour les articles homonymes, voir Déduction. Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C est la version moderne de la logique stoïcienne. C… …   Wikipédia en Français

  • Logique propositionnelle — Calcul des propositions Pour les articles homonymes, voir Déduction. Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C est la version moderne de la logique stoïcienne. C… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”