Forma normal disyuntiva

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En lógica booleana, una forma normal disyuntiva (DNF) es una estandarización (o normalización) de una fórmula lógica que es una disyunción de cláusulas conjuntivas, en otro caso pone, si este es un OR de AND's, también se conoce como suma de productos. Como una forma normal, es útil en la demostración automática de teoremas. Una fórmula lógica se considera que está en FND si y solo si es una disyunción de una o más conjunciones de uno o más literales. Una fórmula FND está en forma normal disyuntiva completa si cada una de sus variables aparece exactamente una vez en cada cláusula. Al igual que en forma normal conjuntiva (FNC), los únicos operadores proposicionales en FND son la conjunción, disyunción y negación. El operador not solo se puede utilizar como parte de un literal, lo que significa que sólo puede preceder a una variable proposicional. Por ejemplo, todas las siguientes fórmulas están en FND:

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

Sin embargo, las siguientes fórmulas NO están en FND:

\neg(A \or B) — El operador NOT es el más extremo
A \or (B \and (C \or D)) — Un OR está anidado con una AND

La conversión de una fórmula para DNF implica el uso de equivalencias lógicas como la eliminación de la doble negación, las leyes de De Morgan, y uso de la distributividad. Nótese que todas las fórmulas lógicas se pueden convertir en forma normal disyuntiva. Sin embargo, en algunos casos, la conversión a FND puede conducir a una explosión exponencial de la fórmula. Por ejemplo, en FND, las fórmulas lógicas de las siguientes formas tienen términos 2n:

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

Cualquier función booleana en particular puede ser representada por una y solo una forma normal disyuntiva completa, una de las dos formas canónicas.

La siguiente fórmula es una gramática formal para FND:

  1. <or> → ∨
  2. <and> → ∧
  3. <not> → ¬
  4. <disyunción> → <conjunción>
  5. <disyunción> → <disyunción> <or> <conjunción>
  6. <conjunción> → <literal>
  7. <conjunción> → (<conjunción> <and> <literal>)
  8. <literal> → <término>
  9. <literal> → <not><término>

Donde <término> es cualquier variable.

Véase también[editar]

Enlaces externos[editar]