Forma normal disyuntiva

La forma normal disyuntiva ( DNF ) en lógica booleana es una forma normal en la que una fórmula booleana tiene la forma de una disyunción de conjunciones de literales . Cualquier fórmula booleana se puede convertir a un DNF. [1] Para hacer esto, puede usar la ley de doble negación , la ley de Morgan , la ley de distributividad . La forma normal disyuntiva es conveniente para la demostración automática de teoremas .

Ejemplos

Fórmulas en DNF :

A \ o B

(A\land B)\lor {\overline {A}}

(A\land B\land {\overline {C)))\lor ({\overline {D))\land E\land F)\lor (C\land D)\lor B

Fórmulas que no están en DNF :

{\overline {(A\lor B)))

A\lor (B\land (C\lor D))

Pero las dos últimas fórmulas son equivalentes a las siguientes fórmulas en DNF:

{\overline {A}}\land {\overline {B}}

A\lor (B\land C)\lor (B\land D).

Construyendo un DNF

Algoritmo para construir un DNF

1) Deshágase de todas las operaciones lógicas contenidas en la fórmula, reemplazándolas por las principales: conjunción, disyunción, negación. Esto se puede hacer usando fórmulas equivalentes:

A\rightarrow B=\neg A\vee B

A\leftrightarrow B=(A\cuña B)\vee (\neg A\cuña \neg B)

2) Reemplazar el signo de negación, referido a la expresión completa, por signos de negación, referidos a enunciados de variables individuales, con base en las fórmulas:

\neg (A\vee B)=\neg A\cuña \neg B

\neg (A\cuña B)=\neg A\vee \neg B

3) Deshazte de los signos negativos dobles.

4) Aplicar, en su caso, a las operaciones de conjunción y disyunción las propiedades de distributividad y fórmulas de absorción.

Un ejemplo de construcción de un DNF

Reduzcamos la fórmula a DNF $F=\neg ((X\rightarrow Y)\vee \neg (Y\rightarrow Z))$

Expresamos la operación lógica → a través de $\vee \cuña \neg$

F=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))

En la fórmula resultante, trasladamos la negación a las variables y reducimos las dobles negaciones:

F=(\neg \neg X\cuña \neg Y)\cuña (\neg Y\vee Z)=(X\cuña \neg Y)\cuña (\neg Y\vee Z)

Usando la ley de distributividad , obtenemos:

F=(X\cuña \neg Y\cuña \neg Y)\vee (X\cuña \neg Y\cuña Z)

Usando la idempotencia de la conjunción, obtenemos un DNF:

F=(X\cuña \neg Y)\vee (X\cuña \neg Y\cuña Z)

k -forma normal disyuntiva

Una forma normal disyuntiva k es una forma normal disyuntiva en la que cada conjunción contiene exactamente k literales .

Por ejemplo, la siguiente fórmula está escrita en 2-DNF:

(A\land B)\lor (\neg B\land C)\lor (B\land \neg C)

Transición de DNF a SDNF

Si falta una variable, por ejemplo, Z, en alguna conjunción simple, insertamos la expresión en ella

Z\vee\neg Z=1

después de lo cual abrimos los paréntesis (al mismo tiempo, no escribimos los términos disjuntos repetidos, ya que de acuerdo con la ley de idempotencia ). Por ejemplo: $Z\vee Z=Z$

X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=

XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z=

=XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z

Así, de DNF obtuvimos SDNF .

Gramática formal que describe DNF

La siguiente gramática formal describe todas las fórmulas reducidas a DNF:

donde <término> denota una variable booleana arbitraria.

Características de la notación

Cabe señalar que, para facilitar la percepción, los símbolos de la multiplicación y la suma aritmética se utilizan a menudo como designación de la conjunción y la disyunción, mientras que el símbolo de la multiplicación suele omitirse. En este caso, las fórmulas del álgebra booleana parecen polinomios algebraicos, lo que resulta más familiar a la vista, pero a veces puede dar lugar a malentendidos.

Por ejemplo, las siguientes entradas son equivalentes:

(A\land B\land {\overline {C)))\lor ({\overline {D))\land E\land F)\lor (C\land D)\lor B;

(A\cdot B\cdot {\overline {C)))\lor ({\overline {D))\cdot E\cdot F)\lor (C\cdot D)\lor B;

AB{\overline {C}}\lor {\overline {D}}EF\lor CD\lor B;

AB{\overline {C}}+{\overline {D}}EF+CD+B.

Por esta razón, DNF en la literatura en idioma ruso a veces se denomina "suma de productos", que es un papel de calco del término inglés "suma de productos".

Véase también

Notas

↑ Pozdnyakov S. N., Rybin S. V. Matemáticas discretas. - art. 303.

Literatura

Yu.I. Galushkina, A. N. Maryamov: Apuntes de clase sobre matemáticas discretas - 2ª ed., rev. - M.: Iris-prensa, 2008. - 176 p. - (Educación más alta).