Computer Laboratory

Technical reports

Natural deduction proof as higher-order resolution

Lawrence C. Paulson

December 1985, 25 pages

Abstract

An interactive theorem prover, Isabelle, is under development. In LCF, each inference rule is represented by one function for forwards proof and another (a tactic) for backwards proof. In Isabelle, each inference rule is represented by a Horn clause. Resolution gives both forwards and backwards proof, supporting a large class of logics. Isabelle has been used to prove theorems in Martin-Löf’s Constructive Type Theory.

Quantifiers pose several difficulties: substitution, bound variables, Skolemization. Isabelle’s representation of logical syntax is the typed lambda-calculus, requiring higher-order unification. It may have potential for logic programming. Depth-first search using inference rules constitutes a higher-order Prolog.

Full text

PDF (0.2 MB)
DVI (0.0 MB)

BibTeX record

@TechReport{UCAM-CL-TR-82,
  author =	 {Paulson, Lawrence C.},
  title = 	 {{Natural deduction proof as higher-order resolution}},
  year = 	 1985,
  month = 	 dec,
  url = 	 {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-82.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-82}
}