Proof Analogy in Interactive Theorem Proving: A Method to Express and Use It Via Second Order Pattern Matching

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Automated Reasoning

A method is presented to express and use syntactic analogies between proofs in interactive theorem proving and proof checking. Up to now, very few papers have addressed instances of this problem. The paradigm of "proposition as types" is adopted and proofs are represented as terms. The proposed method is to transform a known proof of a theorem into what might become a proof of an "analogous" -according to the user-proposition, namely the one to be proved. This transformation is expressed by means of second order pattern matching (this may be seen as a generalisation of rewriting rules), thus allowing the use of variable function symbols. For the moment, it is up to the user to discover the transformation rule, and the paper deals only with the problem of managing it. We explain the proposed analogy treatment with a fully developed running example.