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 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

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 7 (1): 201-215. 

• Davis, Martin; Logemann; Loveland, Donald (1962). «A Machine Program for Theorem Proving». Communications of the ACM 5 (7): 394-397. 

• 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.

• Datos: Q1177898