Journal
JOURNAL OF APPLIED LOGIC
Volume 7, Issue 1, Pages 26-40Publisher
ELSEVIER
DOI: 10.1016/j.jal.2007.07.003
Keywords
Interactive theorem proving; Propositional resolution; LCF-style proof checking
Categories
Funding
- Engineering and Physical Sciences Research Council [GR/T06315/01] Funding Source: researchfish
Ask authors/readers for more resources
This paper describes the integration of zChaff and MiniSat, currently two leading SAT solvers, with Higher Order Logic (HOL) theorem provers. Both SAT solvers generate resolution-style proofs for (instances of) propositional tautologies. These proofs are verified by the theorem provers. The presented approach significantly improves the provers' performance on propositional problems, and exhibits counterexamples for unprovable conjectures. It is also shown that LCF-style theorem provers can serve as viable proof checkers even for large SAT problems. An efficient representation of the propositional problem in the theorem prover turns out to be crucial; several possible solutions are discussed. (C) 2007 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available