Forma normal disyuntiva - Disjunctive normal form

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 agrupación . Como forma normal , es útil en la demostración automática 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 . 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 proposicionales en DNF son y ( ), o ( ), y no ( ). El operador not 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 fórmulas siguientes están en DNF:

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

Sin embargo, 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

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

Conversión a DNF

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.

Convertir una fórmula a DNF 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 .

Todas las fórmulas lógicas se pueden convertir a 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, convertir la fórmula a DNF produce una fórmula con 2 ⁿ términos. ${\ Displaystyle (X_ {1} \ lor Y_ {1}) \ land (X_ {2} \ lor Y_ {2}) \ land \ dots \ land (X_ {n} \ lor Y_ {n})}$

Cada función booleana particular puede ser representada por una y solo una forma normal disyuntiva completa , una de las formas canónicas . En contraste, dos formas normales disyuntivas simples diferentes pueden denotar la misma función booleana, ver imágenes.

Complejidad computacional

El problema de satisfacibilidad booleana en fórmulas conjuntivas de forma normal 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 .

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.

Ver también

• Forma normal algebraica : otras formas normales de fórmulas lógicas
• Forma canónica de Blake : un caso especial de DNF
• Lógica proposicional
• Algoritmo de Quine-McCluskey : obtiene un DNF mínimo para una función booleana determinada
• Mesa de la verdad

Notas

Referencias

• David Hilbert; Wilhelm Ackermann (1999). Principios de lógica matemática . American Mathematical Soc. ISBN 978-0-8218-2024-7.
• J. Eldon Whitesitt (24 de mayo de 2012). Álgebra booleana y sus aplicaciones . Corporación de mensajería. ISBN 978-0-486-15816-7.
• Colin Howson (11 de octubre de 2005). Lógica con árboles: una introducción a la lógica simbólica . Routledge. ISBN 978-1-134-78550-6.
• David Gries; Fred B. Schneider (22 de octubre de 1993). Un enfoque lógico para las matemáticas discretas . Springer Science & Business Media. págs. 67–. ISBN 978-0-387-94115-8.

enlaces externos

• "Forma normal disyuntiva" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]