Lo primero que tendrías que tener claro es qué significa que ese algoritmo es correcto; que el algoritmo te indica que la fórmula es satisfacible si y solamente efectivamente lo es.
En la Wikipedia
http://es.wikipedia.org/wiki/Algoritmo_de_Davis-Putnam se propone el siguiente algoritmo:
1. para cada variable en la fórmula
1.a. para cada cláusula c que contenga la variable y cada cláusula n que contenga la negación de la variable
1.a.i. resolver c y n y añadir la resolución a la fórmula
1.b. eliminar todas las cláusulas originales que contengan la variable o su negación
Este planteo presupone que sabés que la fórmula está expresada como conjunto de cláusulas, y que sabés qué es resolver dos cláusulas.
Lo que este planteo no explicita es cuándo el algoritmo indica que la fórmula es o no es satisfacible. Debes recordar que la cláusula vacía es insatisfacible.
Me parece que el argumento más simple para mostrar la corrección sería una inducción en la cantidad de variables de la fórmula.
saludos