Forma normal disyuntiva

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

En lógica booleana, una forma normal disyuntiva (FND) es una estandarización (o normalización) de una fórmula lógica que es una disyunción de cláusulas conjuntivas. Como una forma normal, es útil en la demostración automática de teoremas. 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. Una negación solo se puede aplicar a un literal, lo que significa que solo 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) (la negación se aplica a una cláusula disyuntiva, no a un literal).
  • A \or (B \and (C \or D)) (una disyunción está anidada a una conjunción).

Convertir una fórmula en FND[editar]

La conversión de una fórmula para FND 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.

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.

Una variación importante utilizada en el estudio de la complejidad computacional es k-DNF. Una fórmula está en k-FND si está en FND y cada cláusula contiene en la mayoría de los literales k. A diferencia de las subclases correspondientes de forma normal conjuntiva para k> = 3, no hay algoritmo fácil de convertir una instancia arbitraria de una fórmula en FND a k-FND.

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

  1. disyunciónconjunción
  2. disyuncióndisyunciónconjunción
  3. conjunciónliteral
  4. conjunción → (conjunciónliteral)
  5. literalvariable
  6. literal → ¬variable

Donde variable es cualquier variable.

Véase también[editar]

Enlaces externos[editar]