Forma normal disyuntiva

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 2ⁿ:

${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor 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ón → conjunción
2. disyunción → disyunción ∨ conjunción
3. conjunción → literal
4. conjunción → (conjunción ∧ literal)
5. literal → variable
6. literal → ¬variable

Donde variable es cualquier variable.

• Forma normal algébrica
• Álgebra booleana
• Función de Valor Booleano
• Forma Normal Conjuntiva
• Cláusula de Horn
• Diagrama de Pierce
• Algoritmo Quine-McCluskey
• Tabla de verdad

• Hazewinkel, Michiel, ed. (2001), «Forma normal disyuntiva», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 .
• Applet de Java para convertir expresiones lógicas booleanas a FNC y FND, mostrando las leyes utilizadas
• Esta obra contiene una traducción derivada de «Disjunctive normal form» de Wikipedia en inglés, concretamente de esta versión, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.