Efficiently checking propositional refutations in HOL theorem provers. Weber, T. & Amjad, H. Journal of Applied Logic, 7(1):26--40, 2009.
doi  abstract   bibtex   
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. ?? 2007 Elsevier Inc. All rights reserved.
@article{Weber2009,
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. ?? 2007 Elsevier Inc. All rights reserved.},
author = {Weber, Tjark and Amjad, Hasan},
doi = {10.1016/j.jal.2007.07.003},
file = {:Users/jonaprieto/Mendeley/Weber, Amjad - 2009 - Efficiently checking propositional refutations in HOL theorem provers.pdf:pdf},
issn = {15708683},
journal = {Journal of Applied Logic},
keywords = {Interactive theorem proving,LCF-style proof checking,Propositional resolution},
number = {1},
pages = {26--40},
title = {{Efficiently checking propositional refutations in HOL theorem provers}},
volume = {7},
year = {2009}
}

Downloads: 0