SAT-based Finite Model Generation for Higher-Order Logic

Tjark Weber. PhD thesis, Institut für Informatik, Technische Universität München, Germany, April 2008.

Abstract

This thesis presents two extensions to the theorem prover Isabelle/HOL, a logical framework based on higher-order logic.

The main contribution is a model generator for higher-order logic that proceeds by translating the input formula to propositional logic, so that a standard SAT solver can be employed for the actual model search. The translation is proved correct. The model generator has been integrated with the Isabelle system, extended to support some of the definitional mechanisms provided by Isabelle/HOL, and applied to various case studies.

Moreover, SAT solvers have been integrated with Isabelle in a proof-producing fashion: propositional tautologies can be proved by a SAT solver, and the resolution proof found by the solver is verified by Isabelle. An adequate representation of the problem allows to verify proofs with millions of resolution steps.

Download

BibTeX

@phdthesis{weber08satbased,
  author  = {Tjark Weber},
  title   = {{SAT}-based Finite Model Generation for Higher-Order Logic},
  school  = {Institut f{\"u}r Informatik, Technische Universit{\"a}t M{\"u}nchen},
  address = {Germany},
  month   = apr,
  year    = {2008},
  url     = {http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20081018-676608-1-8}
}

Errata

  1. Page 15: replace "Even satisfiability in finite models is not semi-decidable." with "Moreover, satisfiability in finite models is not decidable [160].".

Last modified: 2011-12-09