- Algoritmo de Davis-Putnam
-
El algoritmo de Davis-Putnam fue desarrollado por Martin Davis y Hilary Putnam para comprobar la satisfacibilidad de las fórmulas de la lógica proposicional en forma normal conjuntiva, es decir, en conjuntos de cláusulas. Esto es una forma de resolución en la cual las variables son elegidas iterativamente y eliminadas mediante la resolución de cada cláusula en la que que la variable aparece afirmada con una cláusula en la que la variable es negada.
El algoritmo es como sigue:
- para cada variable en la fórmula
- para cada cláusula c que contenga la variable y cada cláusula n que contenga la negación de la variable
- resolver c y n y añadir la resolución a la fórmula
- eliminar todas las cláusulas originales que contengan la variable o su negación
- para cada cláusula c que contenga la variable y cada cláusula n que contenga la negación de la variable
El nombre algoritmo Davis-Putnam o algoritmo DP a veces es empleado incorrectamente para referirse al algoritmo DPLL, el cual está relacionado pero es diferente.
Referencias
- Davis, Martin; Putnam, Hillary (1960). «A Computing Procedure for Quantification Theory». Journal of the ACM (1): pp. 201–215. http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=321034.
- Davis, Martin; Logemann, George, and Loveland, Donald (1962). «A Machine Program for Theorem Proving». Communications of the ACM 5 (7): pp. 394–397. http://portal.acm.org/citation.cfm?doid=368273.368557.
- R. Dechter and I. Rish. Directional resolution: The Davis-Putnam procedure, revisited. In Proceedings of the Fourth International Conference on the Principles of Knowledge Representation and Reasoning (KR'94), pages 134–145, 1994.
Categoría:- Algoritmos SAT
- para cada variable en la fórmula
Wikimedia foundation. 2010.
