Verified QBF Solving

Axel Bergström 📧 and Tjark Weber 📧

March 6, 2024


A Quantified Boolean Formula (QBF) extends propositional logic with quantification over Boolean variables. We formalise two simple QBF solvers and prove their correctness. One solver is based on naive quantifier expansion, while the other utilises a search-based algorithm. Additionally, we formalise a parser for the QDIMACS input format and use Isabelle's code generation feature to obtain executable versions of both solvers.


BSD License


Session QBF_Solver_Verification