Forma normal conjuntiva

La forma normal conjuntiva ( CNF ) en lógica booleana es una forma normal en la que una fórmula booleana tiene la forma de una conjunción de disyunciones de literales . La forma normal conjuntiva es conveniente para la demostración automática de teoremas . Cualquier fórmula booleana se puede convertir a CNF. [1] Para esto puedes usar: la ley de la doble negación , la ley de Morgan , la distributividad .

Ejemplos y contraejemplos

Fórmulas en CNF :

\neg A\cuña (B\vee C),

(A\vee B)\cuña (\neg B\vee C\vee \neg D)\cuña (D\vee \neg E),

A \ cuña B.

Fórmulas que no están en CNF :

\neg (B\vee C),

(A\cuña B)\vee C,

A\cuña (B\vee (D\cuña E)).

Pero estas 3 fórmulas no son equivalentes en CNF a las siguientes fórmulas en CNF:

\neg B\cuña \neg C,

(A\vee C)\cuña (B\vee C),

A\cuña (B\vee D)\cuña (B\vee E).

Construcción de CNF

Algoritmo para construir CNF

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=(\neg A\vee B)\wedge (A\vee \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 CNF

Reduzcamos la fórmula a CNF

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

Transformemos la fórmula en una fórmula que no contenga : $F$ $\flecha correcta$

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

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

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

De acuerdo con la ley de distributividad , obtenemos CNF:

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

k -forma normal conjuntiva

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

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

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

Transición de KNF a SKNF

Si falta alguna variable en una disyunción simple (por ejemplo, z), entonces le agregamos la expresión: (esto no cambia la disyunción en sí), después de lo cual abrimos los paréntesis usando la ley de distribución : $Z\cuña \neg Z=0$

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

Por lo tanto, SKNF se obtiene de CNF.

Gramática formal que describe CNF

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

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

El problema de satisfacibilidad de una fórmula en CNF

En la teoría de la complejidad computacional, el problema de la satisfacibilidad de las fórmulas booleanas en forma normal conjuntiva juega un papel importante . Según el teorema de Cooke , este problema es NP-completo , y se reduce al problema de satisfacibilidad para fórmulas en 3-CNF, que se reduce, y al que se reducen a su vez otros problemas NP-completos .

El problema de satisfacibilidad para fórmulas 2-CNF se puede resolver en tiempo lineal.

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\vee B)\cuña (\neg B\vee C\vee \neg D)\cuña (D\vee \neg E);

(A\vee B)\cuña ({\overline {B}}\vee C\vee {\overline {D}})\cuña (D\vee {\overline {E}});

(A\vee B)\cdot ({\overline {B}}\vee C\vee {\overline {D}})\cdot (D\vee {\overline {E}});

(A\vee B)({\overline {B}}\vee C\vee {\overline {D}})(D\vee {\overline {E}});

(A+B)({\overline {B}}+C+{\overline {D}})(D+{\overline {E}}).

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

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)

Enlaces

Formas normales disyuntivas y conjuntivas