Technical reports

The integration of higher order interactive proof with first order automatic theorem proving

Jia Meng

July 2015, 144 pages

This technical report is based on a dissertation submitted April 2005 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Churchill College.

DOI: 10.48456/tr-872

Abstract

Interactive and automatic theorem proving are the two most widely used computer-assisted theorem proving methods. Interactive proof tools such as HOL, Isabelle and PVS have been highly successful. They support expressive formalisms and have been used for verifying hardware, software, protocols, and so forth. Unfortunately interactive proof requires much effort from a skilled user. Many other tools are completely automatic, such as Vampire, SPASS and Otter. However, they cannot be used to verify large systems because their logic is inexpressive. This dissertation focuses on how to combine these two types of theorem proving to obtain the advantages of each of them. This research is carried out by investigating the integration of Isabelle with Vampire and SPASS.

Isabelle is an interactive theorem prover and it supports a multiplicity of logics, such as ZF and HOL. Vampire and SPASS are first order untyped resolution provers. The objective of this research is to design an effective method to support higher order interactive proof with any first order resolution prover. This integration can simplify the formal verification procedure by reducing the user interaction required during interactive proofs: many goals will be proved by automatic provers.

For such an integration to be effective, we must bridge the many differences between a typical interactive theorem prover and a resolution theorem prover. Examples of the differences are higher order versus first order; typed versus untyped.

Through experiments, we have designed and implemented a practical method to convert Isabelle’s formalisms (ZF and HOL) into untyped first-order clauses. Isabelle/ZF’s formulae that are not first-order need to be reformulated to first-order formulae before clause normal form transformation. For Isabelle/HOL, a sound modelling of its type system is designed first before translating its formulae into first-order clauses with its type information encoded. This method of formalization makes it possible to have Isabelle integrated with resolutions.

A large set of axioms is usually required to support interactive proofs but can easily overwhelm an automatic prover. We have experimented with various methods to solve this problem, including using different settings of an automatic prover and automatically eliminating irrelevant axioms.

The invocation of background automatic provers should be invisible to users, hence we have also designed and implemented an automatic calling procedure, which extracts all necessary information and sends it to an automatic prover at an appropriate point during an Isabelle proof.

Finally, the results and knowledge gained from this research are generally applicable and can be applied to future integration of any other interactive and automatic theorem provers.

Full text

PDF (1.0 MB)

BibTeX record

@TechReport{UCAM-CL-TR-872,
  author =	 {Meng, Jia},
  title = 	 {{The integration of higher order interactive proof with
         	   first order automatic theorem proving}},
  year = 	 2015,
  month = 	 jul,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-872.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-872},
  number = 	 {UCAM-CL-TR-872}
}