El algoritmo de Davis-Putnam fue desarrollado por Martin Davis y Hilary Putnam para la comprobación de la validez de una lógica de primer orden fórmula utilizando una resolución procedimiento de toma poblacionales para la lógica de proposiciones . Dado que el conjunto de fórmulas de primer orden válidas es recursivamente numerable pero no recursivo , no existe ningún algoritmo general para resolver este problema. Por lo tanto, el algoritmo de Davis-Putnam solamente termina en fórmulas válidas. Hoy en día, el término "algoritmo de Davis-Putnam" se utiliza a menudo como sinónimo del procedimiento de toma de proposiciones basadas en la resolución que en realidad es sólo una de las etapas del algoritmo original.
Descripción general
El procedimiento se basa en el teorema de Herbrand , lo que implica que un unsatisfiable fórmula tiene un unsatisfiable ejemplo tierra , y en el hecho de que una fórmula es válida si y sólo si su negación es unsatisfiable. Tomados en conjunto, estos hechos implican que para probar la validez de φ es suficiente para probar que una instancia de base de ¬φ es insaciable. Si φ no es válida, entonces la búsqueda de una instancia de tierra unsatisfiable no va a terminar.
El procedimiento consiste más o menos de estas tres partes:
- poner la fórmula en prenex forma y eliminar cuantificadores
- Generar todas las instancias base proposicionales, una por una.
- comprobar si cada caso es satisfiable
La última parte es probablemente la más innovadora, y funciona de la siguiente (véase la imagen):
- para cada variable en la fórmula
- para cada cláusula que contiene la variable y cada cláusula que contiene la negación de la variable
- determinación c y n y agregar la resolvente a la fórmula
- eliminar todas las cláusulas originales que contienen la variable o su negación
- para cada cláusula que contiene la variable y cada cláusula que contiene la negación de la variable
En cada paso, la fórmula intermedio generado es equisatisfiable , pero posiblemente no equivalente , a la fórmula original. La resolución de paso conduce a una peor de los casos exponencial golpe en marcha en el tamaño de la fórmula.
El algoritmo de Davis-Putnam-Logemann-Loveland es un refinamiento 1962 de la etapa de satisfacibilidad proposicional del procedimiento de Davis-Putnam que requiere sólo una cantidad lineal de la memoria en el peor caso. Todavía constituye la base de la actual (a partir de 2015) más completos eficientes solucionadores SAT .
Ver también
Referencias
- Davis, Martin; Putnam, Hilary (1960). "Procedimiento Computing A para Cuantificación Theory" . Revista de la ACM . 7 (3): 201-215. doi : 10.1145 / 321,033.321034 .
- Davis, Martin; Logemann, George; Loveland, Donald (1962). "Un programa de máquina para la demostración de teoremas" . Comunicaciones de la ACM . 5 (7): 394-397. doi : 10.1145 / 368,273.368557 . HDL : 2027 / mdp.39015095248095 .
- R. Dechter; Irlandesa. "Resolución direccional: el procedimiento de Davis-Putnam, Revisited". En J. Doyle y E. Sandewall y P. Torasso (ed.). Principios de representación del conocimiento y razonamiento: Proc. de la Cuarta Conferencia Internacional (KR'94) . Kaufmann. págs. 134-145.
- John Harrison (2009). Handbook of lógica práctica y razonamiento automatizado . Prensa de la Universidad de Cambridge. pp. 79 -90. ISBN 978-0-521-89957-4.