Forma normal disyuntiva

En lógica booleana , una forma normal disyuntiva ( FND ) es una forma normal de una fórmula lógica que consiste en una disyunción de conjunciones; también puede describirse como una OR de AND , una suma de productos o, en lógica filosófica , un concepto de clúster . ^{[ 1 ]} La forma normal disyuntiva y su contraparte, la forma normal conjuntiva , son las formas estandarizadas más comunes de representar expresiones booleanas . Se utilizan ampliamente en diversas aplicaciones, como el diseño de circuitos o la demostración automática de teoremas .

Una fórmula lógica se considera en forma normal disyuntiva (FND) si es una disyunción de una o más conjunciones de uno o más literales . ^{[ 2 ] [ 3 ] [ 4 ]} Una fórmula FND 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 las variables). Al igual que en la forma normal conjuntiva (FNC), los únicos operadores proposicionales en FND son y (${\displaystyle \wedge }$), o (${\displaystyle \vee }$), y no (${\displaystyle \neg }$). El operador not solo puede usarse como parte de un literal, lo que significa que solo puede preceder a una variable proposicional .

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

No finalizó la temporada${\displaystyle \,\to \,}$( Disyunto )${\displaystyle \,\mid \,}$( Disyunto )${\displaystyle \,\lor \,}$No finalizó la temporada

Desunido${\displaystyle \,\to \,}$Literal${\displaystyle \,\mid \,}$Literal${\displaystyle \,\land \,}$Desunido

Literal${\displaystyle \,\to \,}$Variable${\displaystyle \,\mid \,}$${\displaystyle \,\neg \,}$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${\displaystyle A\lor B}$está en DNF, pero no en DNF completo; una versión equivalente de DNF completo es${\displaystyle (A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)}$.

Las siguientes fórmulas no están en DNF:

• ${\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 ^{[ 5 ]}

En lógica clásica, cada fórmula proposicional puede convertirse a DNF ^{[ 6 ]} ...

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

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

La demostración se deduce del procedimiento descrito anteriormente para generar DNF a partir de tablas de verdad . Formalmente, la demostración es la siguiente:

Suponer${\displaystyle X}$es una oración en un lenguaje proposicional cuyas letras de oración son${\displaystyle A,B,C,\ldots }$. Para cada fila de${\displaystyle X}$Tabla de verdad de , escribe una conjunción correspondiente${\displaystyle \pm A\land \pm B\land \pm C\land \ldots }$, dónde${\displaystyle \pm A}$se define como${\displaystyle A}$si${\displaystyle A}$toma el valor${\displaystyle T}$en esa fila, y es${\displaystyle \neg A}$si${\displaystyle A}$toma el valor${\displaystyle F}$en esa fila; de manera similar para${\displaystyle \pm B}$,${\displaystyle \pm C}$, etc. (el orden alfabético de${\displaystyle A,B,C,\ldots }$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${\displaystyle T}$filas de${\displaystyle X}$tabla de verdad de. Esta disyunción es una oración en${\displaystyle {\mathcal {L}}[A,B,C,\ldots$ ;\land ,\lor ,\neg ]} , ^{[ 18 ]} que por el razonamiento anterior es veritativamente equivalente a${\displaystyle X}$Esta construcción obviamente presupone que${\displaystyle X}$toma el valor${\displaystyle T}$en al menos una fila de su tabla de verdad; si${\displaystyle X}$no lo hace, es decir, si${\displaystyle X}$es una contradicción , entonces${\displaystyle X}$es equivalente a${\displaystyle A\land \neg A}$, que, por supuesto, también es una oración en${\displaystyle {\mathcal {L}}[A,B,C,\ldots$ ;\land ,\lor ,\neg ]} . ^{[ 15 ]}

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${\displaystyle \{\land ,\lor ,\neg \}}$es funcionalmente completo . ^{[ 15 ]}

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

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

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

Este es el número máximo de conjunciones que puede tener una DNF. ^{[ 13 ]}

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

Ejemplo 1

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

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

${\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}}}$

La DNF completa más larga posible tiene 4 conjunciones: están subrayadas.

Esta fórmula es una tautología . Se puede simplificar a${\displaystyle (\neg p\lor p)}$o para${\displaystyle (\neg q\lor q)}$, que también son tautologías, así como DNF válidos.

Ejemplo 2

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

El problema de satisfacibilidad booleana 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 determinar en tiempo polinomial simplemente comprobando que al menos una conjunción no contiene literales conflictivos.

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. ^{[ 20 ]}

• Forma normal algebraica : una operación XOR de cláusulas AND.
• Forma canónica de Blake – No terminado, incluyendo todos los implicantes principales.
  • Algoritmo de Quine-McCluskey : algoritmo para calcular implicantes primos.
• Dualidad conjunción/disyunción
• Lógica proposicional
• Tabla de verdad

• Arora, Sanjeev ; Barak, Boaz (20 de abril de 2009). 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 las redes y el orden . Libros de texto matemáticos de Cambridge. Cambridge University Press.
• Dershowitz, Nachum ; Jouannaud, Jean-Pierre (1990). «Sistemas de reescritura». En Van Leeuwen, Jan (ed.). Modelos formales y semántica . Manual de informática teórica. Vol.  B. Elsevier . pp. 243–320 . ISBN  0-444-88074-7.
• Gries, David; Schneider, Fred B. (22 de octubre de 1993). Un enfoque lógico de 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 . 
• Smullyan, Raymond M. (1968). Lógica de primer orden . Ergebnisse der Mathematik und ihrer Grenzgebiete. vol.  43 (primera edición, segunda impresión,  edición de 1971). Nueva York Heidelberg Berlín: Springer-Verlag . pag.  160.doi : 10.1007 /978-3-642-86718-7 . ISBN 978-3-642-86718-7.
• Sobolev, SK (2020) [1994], "Forma normal disyuntiva" , Enciclopedia de Matemáticas , EMS Press
• Whitesitt, J. Eldon (24 de mayo de 2012) [1961]. Álgebra booleana y sus aplicaciones . Courier Corporation. ISBN 978-0-486-15816-7.