Forma normal disyuntiva

Forma estándar de una función booleana

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 clúster . ^[1] Como forma normal , es útil en la demostración automatizada de teoremas .

Definición

Se considera que una fórmula lógica está en DNF si es una disyunción de una o más conjunciones de uno o más literales . ^{[2] [3] [4]} Una fórmula DNF está en forma normal disyuntiva completa si cada una de sus variables aparece exactamente una vez en cada conjunción y cada conjunción aparece como máximo una vez (hasta el orden de variables). Al igual que en la forma normal conjuntiva (CNF), los únicos operadores proposicionales en DNF son y ( ), o ( ), y no ( ). El operador no solo se puede usar como parte de un literal, lo que significa que solo puede preceder a una variable proposicional . ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle \neg }$

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

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

Donde Variable es cualquier variable.

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

• ${\displaystyle (A\land \neg B\land \neg C)\lor (\neg D\land E\land F\land D\land F)}$
• ${\displaystyle (A\land B)\lor (C)}$
• ${\displaystyle (A\land B)}$
• ${\displaystyle (A)}$

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

Las siguientes fórmulas no están en DNF: ^[5]

• ${\displaystyle \neg (A\lor B)}$, ya que un OR está anidado dentro de un NOT
• ${\displaystyle \neg (A\land B)\lor C}$, ya que un AND está anidado dentro de un NOT
• ${\displaystyle A\lor (B\land (C\lor D))}$, ya que un OR está anidado dentro de un AND

Conversión a DNF

En la lógica clásica cada fórmula proposicional puede convertirse en DNF ^[6] ...

Mapa de Karnaugh de la forma normal disyuntiva (¬ A ∧¬ B ∧¬ D ) ∨ (¬ A ∧ B ∧ C ) ∨ ( A ∧ B ∧ D ) ∨ ( A ∧¬ B ∧¬ C )

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

...por medios sintácticos

La conversión implica el uso de equivalencias lógicas , como la eliminación de la doble negación , las leyes de De Morgan y la ley distributiva . Las fórmulas construidas a partir de los conectivos primitivos ^[7] se pueden convertir a DNF mediante el siguiente sistema de reescritura de términos canónicos : ^[8] ${\displaystyle \{\land ,\lor ,\lnot \}}$

${\displaystyle {\begin{array}{rcl}(\lnot \lnot x)&\rightsquigarrow &x\\(\lnot (x\lor y))&\rightsquigarrow &((\lnot x)\land (\lnot y))\\(\lnot (x\land y))&\rightsquigarrow &((\lnot x)\lor (\lnot y))\\(x\land (y\lor z))&\rightsquigarrow &((x\land y)\lor (x\land z))\\((x\lor y)\land z)&\rightsquigarrow &((x\land z)\lor (y\land z))\\\end{array}}}$

...por medios semánticos

El DNF completo de una fórmula se puede leer en su tabla de verdad . ^[9] Por ejemplo, considere la fórmula

${\displaystyle \phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))}$. ^[10]

La tabla de verdad correspondiente es

• El equivalente completo de DNF es ${\displaystyle \phi }$

${\displaystyle (p\land \lnot q\land r)\lor (\lnot p\land q\land r)\lor (\lnot p\land \lnot q\land r)\lor (\lnot p\land \lnot q\land \lnot r)}$

• El equivalente completo de DNF es ${\displaystyle \lnot \phi }$

${\displaystyle (p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)}$

Observación

Una fórmula proposicional puede representarse mediante una y solo una DNF completa. ^[12] En cambio, pueden ser posibles varias DNF simples . Por ejemplo, al aplicar la regla tres veces, la DNF completa de lo anterior puede simplificarse a . Sin embargo, también existen fórmulas DNF equivalentes que no pueden transformarse entre sí mediante esta regla; consulte las imágenes para ver un ejemplo. ${\displaystyle ((a\land b)\lor (\lnot a\land b))\rightsquigarrow b}$ ${\displaystyle \phi }$ ${\displaystyle (\lnot p\land \lnot q)\lor (\lnot p\land r)\lor (\lnot q\land r)}$

Teorema de la forma normal disyuntiva

Es un teorema que establece que todas las fórmulas consistentes en lógica proposicional pueden convertirse en forma normal disyuntiva. ^{[13] [14] [15] [16]} Esto se denomina Teorema de la Forma Normal Disyuntiva . ^{[13] [14] [15] [16]} El enunciado formal es el siguiente:

Teorema de la forma normal disyuntiva: Supongamos que es una oración en un lenguaje proposicional con letras de oración, que denotaremos por . Si no es una contradicción, entonces es equivalente en función de la verdad a una disyunción de conjunciones de la forma , donde , y . ^[14] ${\displaystyle X}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle n}$ ${\displaystyle A_{1},...,A_{n}}$ ${\displaystyle X}$ ${\displaystyle \pm A_{1}\land ...\land \pm A_{n}}$ ${\displaystyle +A_{i}=A_{i}}$ ${\displaystyle -A_{i}=\neg A_{i}}$

La prueba se desprende del procedimiento indicado anteriormente para generar DNF a partir de tablas de verdad . Formalmente, la prueba es la siguiente:

Supongamos que es una oración en un lenguaje proposicional cuyas letras de oración son . Para cada fila de la tabla de verdad de , escriba una conjunción correspondiente , donde se define como si toma el valor en esa fila, y es si toma el valor en esa fila; de manera similar para , , etc. (el orden alfabético de en las conjunciones es bastante arbitrario; se podría elegir cualquier otro en su lugar). Ahora forme la disyunción de todas estas conjunciones que corresponden a filas de la tabla de verdad de . Esta disyunción es una oración en , ^[17] que por el razonamiento anterior es veritativamente-funcionalmente equivalente a . Esta construcción obviamente presupone que toma el valor en al menos una fila de su tabla de verdad; si no lo hace, es decir, si es una contradicción , entonces es equivalente a , que es, por supuesto, también una oración en . ^[14] ${\displaystyle X}$ ${\displaystyle A,B,C,\ldots }$ ${\displaystyle X}$ ${\displaystyle \pm A\land \pm B\land \pm C\land \ldots }$ ${\displaystyle \pm A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle \neg A}$ ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle \pm B}$ ${\displaystyle \pm C}$ ${\displaystyle A,B,C,\ldots }$ ${\displaystyle T}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {L}}[A,B,C,\ldots ;\land ,\lor ,\neg ]}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle A\land \neg A}$ ${\displaystyle {\mathcal {L}}[A,B,C,\ldots ;\land ,\lor ,\neg ]}$

Este teorema es una forma conveniente de derivar muchos resultados metalógicos útiles en lógica proposicional, como, trivialmente , el resultado de que el conjunto de conectivos es funcionalmente completo . ^[14] ${\displaystyle \{\land ,\lor ,\neg \}}$

Número máximo de conjunciones

Toda fórmula proposicional se construye a partir de variables, donde . ${\displaystyle n}$ ${\displaystyle n\geq 1}$

Hay posibles literales: . ${\displaystyle 2n}$ ${\displaystyle L=\{p_{1},\lnot p_{1},p_{2},\lnot p_{2},\ldots ,p_{n},\lnot p_{n}\}}$

${\displaystyle L}$tiene subconjuntos no vacíos. ^[18] ${\displaystyle (2^{2n}-1)}$

Este es el número máximo de conjunciones que puede tener un DNF. ^[12]

Un DNF completo puede tener hasta conjunciones, una para cada fila de la tabla de verdad. ${\displaystyle 2^{n}}$

Ejemplo 1

Consideremos una fórmula con dos variables y . ${\displaystyle p}$ ${\displaystyle q}$

El DNF más largo posible tiene conjunciones: ^[12] ${\displaystyle 2^{(2\times 2)}-1=15}$

${\displaystyle {\begin{array}{lcl}(\lnot p)\lor (p)\lor (\lnot q)\lor (q)\lor \\(\lnot p\land p)\lor {\underline {(\lnot p\land \lnot q)}}\lor {\underline {(\lnot p\land q)}}\lor {\underline {(p\land \lnot q)}}\lor {\underline {(p\land q)}}\lor (\lnot q\land q)\lor \\(\lnot p\land p\land \lnot q)\lor (\lnot p\land p\land q)\lor (\lnot p\land \lnot q\land q)\lor (p\land \lnot q\land q)\lor \\(\lnot p\land p\land \lnot q\land q)\end{array}}}$

El DNF completo más largo posible tiene 4 conjunciones: están subrayadas.

Esta fórmula es una tautología .

Ejemplo 2

Cada DNF de la fórmula eg tiene conjunciones. ${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$ ${\displaystyle 2^{n}}$

Complejidad computacional

El problema de satisfacibilidad booleano en fórmulas de forma normal conjuntiva es NP-completo . Por el principio de dualidad , también lo es el problema de falsabilidad en 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 satisfacible si, y solo si, una de sus conjunciones es satisfacible. Esto se puede decidir en tiempo polinómico simplemente comprobando que al menos una conjunción no contenga literales conflictivos.

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. ^[19]

Véase también

• Forma normal algebraica : una operación XOR de cláusulas AND
• Forma canónica de Blake : DNF que incluye todos los implicantes primos
  • Algoritmo de Quine-McCluskey : algoritmo para calcular implicantes primos
• Dualidad conjunción/disyunción
• Lógica proposicional
• Tabla de verdad

Notas

1. Después de 1921.
2. Davey y Priestley 1990, pág. 153.
3. Gries y Schneider 1993, pág. 67.
4. Whitesitt 2012, págs. 33–37.
5. Sin embargo, están en forma normal de negación .
6. Davey y Priestley 1990, págs. 152-153.
7. Las fórmulas con otros conectivos se pueden llevar primero a la forma normal de negación .
8. Dershowitz y Jouannaud 1990, pág. 270, sección 5.1.
9. Sóbolev 2020.
10. = (( NO (p Y q)) SI Y FALSO (( NO r) N Y (p XOR q))) ${\displaystyle \phi }$
11. me gusta ${\displaystyle (a\land b)\lor (b\land a)\lor (a\land b\land b)}$
12. Se supone que no ocurren repeticiones y variaciones ^[11] basadas en la conmutatividad y asociatividad de y . ${\displaystyle \lor }$ ${\displaystyle \land }$
13. Halbeisen, Lorenz; Kraph, Regula (2020). Los teoremas de Gödel y los axiomas de Zermelo: una base sólida para las matemáticas . Cham: Birkhäuser. p. 27. ISBN 978-3-030-52279-7.
14. Howson, Colin (1997). Lógica con árboles: una introducción a la lógica simbólica . Londres; Nueva York: Routledge. p. 41. ISBN 978-0-415-13342-5.
15. Cenzer, Douglas; Larson, Jean; Porter, Christopher; Zapletal, Jindřich (2020). Teoría de conjuntos y fundamentos de las matemáticas: una introducción a la lógica matemática . Nueva Jersey: World Scientific. págs. 19–21. ISBN 978-981-12-0192-9.
16. Halvorson, Hans (2020). Cómo funciona la lógica: una guía del usuario . Princeton Oxford: Princeton University Press. pág. 195. ISBN 978-0-691-18222-3.
17. Es decir, el lenguaje con las variables proposicionales y los conectivos . ${\displaystyle A,B,C,\ldots }$ ${\displaystyle \{\land ,\lor ,\neg \}}$
18. ${\displaystyle \left|{\mathcal {P}}(L)\right|=2^{2n}}$
19. Arora y Barak 2009.

Referencias

• Arora, Sanjeev; Barak, Boaz (20 de abril de 2009). Computational Complexity: A Modern Approach (Complejidad computacional: un enfoque moderno ). Cambridge University Press . pág. 579. doi :10.1017/CBO9780511804090. ISBN . 9780521424264.
• Davey, BA; Priestley, HA (1990). Introducción a los retículos y al orden . Cambridge Mathematical Textbooks. Cambridge University Press.
• Dershowitz, Nachum ; Jouannaud, Jean-Pierre (1990). "Rewrite Systems". En Van Leeuwen, Jan (ed.). Modelos formales y semántica . Manual de informática teórica. Vol. B. Elsevier . págs. 243–320. ISBN 0-444-88074-7.
• Gries, David; Schneider, Fred B. (22 de octubre de 1993). Un enfoque lógico para las matemáticas discretas. Springer Science & Business Media. ISBN 978-0-387-94115-8.
• Hilbert, David ; Ackermann, Wilhelm (1999). Principios de lógica matemática. American Mathematical Soc. ISBN 978-0-8218-2024-7.
• Howson, Colin (11 de octubre de 2005) [1997]. Lógica con árboles: una introducción a la lógica simbólica. Routledge. ISBN 978-1-134-78550-6.
• Post, Emil (julio de 1921). "Introducción a una teoría general de proposiciones elementales". American Journal of Mathematics . 43 (3): 163–185. doi :10.2307/2370324. JSTOR  2370324.
• Sobolev, SK (2020) [1994], "Forma normal disyuntiva", Enciclopedia de matemáticas , EMS Press
• Whitesitt, J. Eldon (24 de mayo de 2012) [1961]. Álgebra de Boole y sus aplicaciones. Courier Corporation. ISBN 978-0-486-15816-7.