Forma normal disyuntiva

En lógica booleana, una forma normal disyuntiva (DNF) es una forma normal canónica de una fórmula lógica que consiste en una disyunción de conjunciones; también se puede describir como un OR de AND, una suma de productos o (en lógica filosófica) un concepto de grupo. Como forma normal, es útil en la demostración automática de teoremas.

Definición

Una fórmula lógica se considera en DNF si es una disyunción de una o más conjunciones de uno o más literales. Una fórmula DNF está en forma normal disyuntiva completa si cada una de sus variables aparece exactamente una vez en cada conjunción. Como en la forma normal conjuntiva (CNF), los únicos operadores proposiciónles en DNF son y (${displaystyle wedge }$), o (${displaystyle vee }$), y no (${displaystyle neg }$). El no El operador sólo puede ser utilizado como parte de un literal, lo que significa que sólo puede preceder a una variable proposición.

La siguiente es una gramática libre de contexto para DNF:

1. DNF →Conjunción) ${displaystyle vee }$ DNF
2. DNF →Conjunción)
3. Conjunción → Literal ${displaystyle wedge }$ Conjunción
4. Conjunción → Literal
5. Literal → ${displaystyle neg }$Variable
6. Literal → Variable

Donde Variable es cualquier variable.

Por ejemplo, todas las fórmulas siguientes están en DNF:

• ${displaystyle (Aland neg Bland neg C)lor (neg Dland Eland F)}$
• ${displaystyle (Aland B)lor (C)}$
• ${displaystyle (Aland B)}$
• ${displaystyle (A)}$

Sin embargo, las siguientes fórmulas no están en DNF:

• ${displaystyle neg (Alor B)}$, ya que un OR está anidado dentro de un NO
• ${displaystyle neg (Aland B)lor C}$, ya que un Y está anidado dentro de un NO
• ${displaystyle Alor (Bland (Clor D)}$, ya que un OR está anidado dentro de un

La fórmula ${displaystyle Alor B}$ está en DNF, pero no en el DNF completo; una versión DNF equivalente es ${displaystyle (Aland B)lor (Aland lnot B)lor (lnot Aland B)}$.

Conversión a DNF

Karnaugh mapa de la forma normal disyuntiva (ADejaBDejaD) Alternativa (A∧B∧C) Alternativa ()A∧B∧D) Alternativa ()ADejaBDejaC)

Karnaugh mapa de la forma normal disyuntiva (A∧CDejaD) Alternativa ()B∧C∧D) Alternativa ()ADejaC∧D) Alternativa (BDejaCDejaD). A pesar de la agrupación diferente, los mismos campos contienen un "1" como en el mapa anterior.

La conversión de una fórmula a DNF implica el uso de equivalencias lógicas, como la eliminación de doble negación, las leyes de De Morgan y la ley distributiva.

Todas las fórmulas lógicas se pueden convertir en una forma normal disyuntiva equivalente. Sin embargo, en algunos casos la conversión a DNF puede conducir a una explosión exponencial de la fórmula. Por ejemplo, la conversión de la fórmula ${displaystyle (X_{1}lor Y_{1})land (X_{2}lor Y_{2})land dots land (X_{n}lor Y_{n}}}$ DNF produce una fórmula con 2ⁿ términos.

Cada función booleana particular puede ser representada por una y sólo una forma normal disyuntiva completa, una de las formas canónicas. Por el contrario, dos formas normales disyuntivas simples diferentes pueden denotar la misma función booleana; ver las ilustraciones.

Complejidad computacional

El problema de satisfacibilidad booleano en fórmulas de forma normal conjuntiva es NP-difícil; por el principio de dualidad, también lo es el problema de falsabilidad en las fórmulas DNF. Por lo tanto, es co-NP-difícil decidir si una fórmula DNF es una tautología.

Por el contrario, una fórmula DNF es satisfactoria si, y solo si, una de sus conjunciones es satisfactoria; esto se puede decidir en tiempo polinomial.

Variantes

Una variación importante utilizada en el estudio de la complejidad computacional es k-DNF. Una fórmula está en k-DNF si está en DNF y cada conjunción contiene como máximo k literales.