Forma estándar de función booleana
En lógica booleana , una fórmula está en forma normal conjuntiva ( CNF ) o en forma normal clausal si es una conjunción de una o más cláusulas , donde una cláusula es una disyunción de literales ; Dicho de otra manera, es un producto de sumas o un AND de OR . Como forma normal canónica , es útil en la demostración automatizada de teoremas y en la teoría de circuitos .
En la demostración automatizada de teoremas, la noción de " forma normal clausal " se utiliza a menudo en un sentido más estricto, es decir, una representación particular de una fórmula CNF como un conjunto de conjuntos de literales.
Definición
Una fórmula lógica se considera en CNF si es una conjunción de una o más disyunciones de uno o más literales . Como en la forma normal disyuntiva (DNF), los únicos operadores proposicionales en CNF son o ( ), y ( ), y no ( ). 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 CNF:
- CNF → ( Disyunción ) CNF
- CNF → ( Disyunción )
- Disyunción → Disyunción literal
- Disyunción → Literal
- Literales → Variables
- Literales → Variables
Donde Variable es cualquier variable.
Todas las siguientes fórmulas en las variables y están en forma normal conjuntiva:
Las siguientes fórmulas no están en forma normal conjuntiva:
- , ya que un AND está anidado dentro de un NOT
- , ya que un OR está anidado dentro de un NOT
- , ya que un AND está anidado dentro de un OR
Conversión a CNF
En lógica clásica cada fórmula proposicional se puede convertir en una fórmula equivalente que está en CNF. Esta transformación se basa en reglas sobre equivalencias lógicas : eliminación de la doble negación , leyes de De Morgan y la ley distributiva .
Algoritmo básico
El algoritmo para calcular un equivalente CNF de una fórmula proposicional dada se basa en la forma normal disyuntiva (DNF) : paso 1. [2]
Luego se convierte intercambiando AND con OR y viceversa mientras se niegan todos los literales. Eliminar todo .
Conversión por medios sintácticos
Convertir a CNF la fórmula proposicional .
Paso 1 : convierte su negación a forma normal disyuntiva. [2]
, [a]
donde cada uno es una conjunción de literales . [b]
Paso 2 : Negar . Luego, cambie hacia adentro aplicando las equivalencias (generalizadas) de De Morgan hasta que ya no sea posible.
dónde
Paso 3 : Elimina todas las dobles negaciones.
Ejemplo
Convertir a CNF la fórmula proposicional . [C]
El equivalente (completo) DNF de su negación es [2]
Conversión por medios semánticos
Se puede derivar un equivalente CNF de una fórmula a partir de su tabla de verdad . De nuevo, considere la fórmula . [C]
La tabla de verdad correspondiente es
Un equivalente de CNF es
Cada disyunción refleja una asignación de variables cuya evaluación es F(alse).
Si en tal asignación una variable
- es T(rue), entonces el literal se establece en la disyunción,
- es F(alse), entonces el literal se establece en en la disyunción.
Otros enfoques
Dado que todas las fórmulas proposicionales se pueden convertir en una fórmula equivalente en forma normal conjuntiva, las pruebas a menudo se basan en el supuesto de que todas las fórmulas son CNF. Sin embargo, en algunos casos esta conversión a CNF puede provocar una explosión exponencial de la fórmula. Por ejemplo, traducir la fórmula no CNF
en CNF produce una fórmula con cláusulas:
Cada cláusula contiene o para cada uno .
Existen transformaciones en CNF que evitan un aumento exponencial de tamaño al preservar la satisfacibilidad en lugar de la equivalencia . Se garantiza que estas transformaciones solo aumentarán linealmente el tamaño de la fórmula, pero introducirán nuevas variables. Por ejemplo, la fórmula anterior se puede transformar en CNF agregando variables de la siguiente manera:
Una interpretación satisface esta fórmula sólo si al menos una de las nuevas variables es verdadera. Si esta variable es , entonces ambos y también son verdaderos. Esto significa que cada modelo que satisface esta fórmula también satisface la original. Por otro lado, sólo algunos de los modelos de la fórmula original satisfacen éste: dado que no se mencionan en la fórmula original, sus valores son irrelevantes para su satisfacción, lo que no ocurre en la última fórmula. Esto significa que la fórmula original y el resultado de la traducción son equisatisfacibles pero no equivalentes .
Una traducción alternativa, la transformación de Tseitin , incluye también las cláusulas . Con estas cláusulas, la fórmula implica ; A menudo se considera que esta fórmula "define" como un nombre para .
Número máximo de disyunciones
Considere una fórmula proposicional con variables, .
Hay posibles literales: .
tiene subconjuntos no vacíos. [d]
Este es el número máximo de disyunciones que puede tener un CNF. [mi]
Todas las combinaciones de funciones de verdad se pueden expresar con disyunciones, una para cada fila de la tabla de verdad. En el siguiente ejemplo están subrayados.
Ejemplo
Considere una fórmula con dos variables y .
El CNF más largo posible tiene disyunciones: [e]
Esta fórmula es una contradicción .
Complejidad computacional
Un conjunto importante de problemas de complejidad computacional implica encontrar asignaciones a las variables de una fórmula booleana expresada en forma normal conjuntiva, de modo que la fórmula sea verdadera. El problema k -SAT es el problema de encontrar una asignación satisfactoria a una fórmula booleana expresada en CNF en la que cada disyunción contiene como máximo k variables. 3-SAT es NP-completo (como cualquier otro problema de k -SAT con k >2), mientras que se sabe que 2-SAT tiene soluciones en tiempo polinomial . Como consecuencia, [f] la tarea de convertir una fórmula en un DNF , preservando la satisfacibilidad, es NP-difícil ; dualmente , convertir a CNF, preservar la validez , también es NP-duro; por lo tanto, la conversión que preserva la equivalencia a DNF o CNF es nuevamente NP-duro.
Los problemas típicos en este caso involucran fórmulas en "3CNF": forma normal conjuntiva con no más de tres variables por conjunción. Los ejemplos de este tipo de fórmulas que se encuentran en la práctica pueden ser muy grandes, por ejemplo con 100.000 variables y 1.000.000 de conjunciones.
Una fórmula en CNF se puede convertir en una fórmula equisatisfactible en " k CNF" (para k ≥3) reemplazando cada conjunción con más de k variables por dos conjunciones y con Z una nueva variable, y repitiendo tantas veces como sea necesario.
Lógica de primer orden
En la lógica de primer orden, la forma normal conjuntiva se puede llevar más allá para producir la forma normal clausal de una fórmula lógica, que luego se puede utilizar para realizar una resolución de primer orden . En la demostración automatizada de teoremas basada en resolución, una fórmula CNF
Vea a continuación un ejemplo.
Conversión de lógica de primer orden
Para convertir lógica de primer orden a CNF:
- Convertir a forma normal de negación .
- Eliminar implicaciones y equivalencias: reemplazar repetidamente con ; reemplazar con . Con el tiempo, esto eliminará todas las apariciones de y .
- Mueva los NOT hacia adentro aplicando repetidamente la ley de De Morgan . Específicamente, reemplácelo con ; reemplazar con ; y reemplazar con ; reemplazar con ; con . Después de eso, a puede aparecer sólo inmediatamente antes de un símbolo de predicado.
- Estandarizar variables
- Para oraciones como las que usan el mismo nombre de variable dos veces, cambie el nombre de una de las variables. Esto evita confusiones posteriores al eliminar cuantificadores. Por ejemplo, se le cambia el nombre a .
- Skolemizar la declaración
- Mueva los cuantificadores hacia afuera: reemplácelos repetidamente con ; reemplazar con ; reemplazar con ; reemplazar con . Estos reemplazos preservan la equivalencia, ya que el paso anterior de estandarización de variables aseguró que eso no ocurriera en . Después de estos reemplazos, un cuantificador puede aparecer solo en el prefijo inicial de la fórmula, pero nunca dentro de , o .
- Reemplace repetidamente con , donde hay un nuevo símbolo de función -aria, la llamada " función Skolem ". Este es el único paso que preserva sólo la satisfacibilidad y no la equivalencia. Elimina todos los cuantificadores existenciales.
- Elimina todos los cuantificadores universales.
- Distribuya los OR hacia adentro sobre los AND: reemplácelos repetidamente con .
Ejemplo
Como ejemplo, la fórmula que dice "Cualquiera que ama a todos los animales, es a su vez amado por alguien" se convierte en CNF (y posteriormente en forma de cláusula en la última línea) de la siguiente manera (resaltando las reglas de reemplazo redex en ):
Informalmente, se puede considerar que la función Skolem produce la persona que es amada, mientras que produce el animal (si lo hay) que no ama. La tercera y última línea desde abajo dice " no ama al animal , o es amado por " .
La penúltima línea desde arriba, es el CNF.
Ver también
Notas
- ^ número máximo de conjunciones para
- ^ número máximo de literales para
- ^ ab = (( NO (p Y q)) IFF (( NO r) NAND (p XOR q)))
- ^
- ^ ab Se supone que las repeticiones y variaciones (como ) basadas en la conmutatividad y asociatividad de y no ocurren.
- ^ dado que una forma de verificar la satisfacibilidad de un CNF es convertirlo en un DNF , cuya satisfacibilidad se puede verificar en tiempo lineal
- ^ número máximo de disyunciones número máximo de literales
Referencias
- Andrews, Peter B. (2013). Introducción a la lógica matemática y la teoría de tipos: hacia la verdad a través de la prueba . ISBN 9401599343.
- Howson, Colin (11 de octubre de 2005) [1997]. Lógica con árboles: una introducción a la lógica simbólica. Rutledge. ISBN 978-1-134-78550-6.
- Jackson, Pablo; Sheridan, Daniel (10 de mayo de 2004). "Conversiones de formularios de cláusulas para circuitos booleanos" (PDF) . En Hoos, Holger H.; Mitchell, David G. (eds.). Teoría y aplicaciones de las pruebas de satisfacción . VII Congreso Internacional sobre Teoría y Aplicaciones de las Pruebas de Satisfabilidad, SAT. Artículos seleccionados revisados. Apuntes de conferencias sobre informática. vol. 3542. Vancouver, BC, Canadá: Springer 2005. págs. doi :10.1007/11527695_15. ISBN 978-3-540-31580-3.
- Kleine Büning, Hans; Lettmann, Theodor (28 de agosto de 1999). Lógica proposicional: deducción y algoritmos. Prensa de la Universidad de Cambridge . ISBN 978-0-521-63017-7.
- Russell, Estuardo ; Norvig, Peter , eds. (2010) [1995]. Inteligencia artificial: un enfoque moderno (PDF) (3ª ed.). Upper Saddle River, Nueva Jersey: Prentice Hall. ISBN 978-0-13-604259-4. Archivado (PDF) desde el original el 31 de agosto de 2017.
- Tseitin, Grigori S. (1968). "Sobre la complejidad de la derivación en cálculo proposicional" (PDF) . En Slisenko, AO (ed.). Estructuras en Matemática Constructiva y Lógica Matemática, Parte II, Seminarios de Matemáticas (traducido del ruso) . Instituto de Matemáticas Steklov. págs. 115-125.
- Whitesitt, J. Eldon (24 de mayo de 2012) [1961]. Álgebra booleana y sus aplicaciones. Corporación de mensajería. ISBN 978-0-486-15816-7.
enlaces externos
- "Herramienta Java para convertir una tabla de verdad en CNF y DNF". Universidad de Marburgo . Consultado el 31 de diciembre de 2023 .