Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4663060 | Journal of Applied Logic | 2009 | 15 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Tjark Weber, Hasan Amjad,