Conflict Resolution: A First-Order Resolution Calculus with Decision Literals and Conflict-Driven Clause Learning

Abstract

This paper defines the (first-order) conflict resolution calculus: an extension of the resolution calculus inspired by techniques used in modern Satsolvers. The resolution inference rule is restricted to (first-order) unit propagation and the calculus is extended with a mechanism for assuming decision literals and with a new inference rule for clause learning, which is a first-order generalization of the propositional conflict-driven clause learning procedure. The calculus is sound (because it can be simulated by natural deduction) and refutationally complete (because it can simulate resolution), and these facts are proven in detail here Show more