Superposition: Types and Induction

Abstract

Proof assistants are becoming widespread for formalization of theories both in computer science and mathematics. They provide rich logics with powerful type systems and machine-checked proofs which increase the confidence in the correctness in complicated and detailed proofs. However, they incur a significant overhead compared to pen-and-paper proofs. This thesis describes work on bridging the gap between high-order proof assistants and first-order automated theorem provers by extending the capabilities of the automated theorem provers to provide features usually found in proof assistants. My first contribution is the development and implementation of a first-order superposition calculus with a polymorphic type system that supports type classes and the accompanying refutational completeness proof for that calculus. The inclusion of the type system into the superposition calculus and solvers completely removes the type encoding overhead when encoding problems from many proof assistants. My second contribution is the development of SupInd, an extension of the typed superposition calculus that supports data types and structural induction over those data types. It includes heuristics that guide the induction and conjecture strengthening techniques, which can be applied independently of the underlying calculus. I have implemented the contributions in a tool called Pirate. The evaluations of both contributions show promising results.

Beweisassistenten werden zunehmend in der Formalisierung von Theorien, sowohl in der Informatik als auch in der Mathematik, genutzt. Ihre vielseitigen Logiken mit ausdrucksstarken Typsystemen ermöglichen Maschinenkontrollierte Beweise. Dies erhöht die Vertrauenswürdigkeit von komplizierten und detaillierten Beweisen. Im Gegensatz zu Papierbeweisen ist ihr Gebrauch jedoch aufwendiger. Diese Dissertation beschreibt Fortschritte darin, den Abstand zwischen Beweisassistenten höherer Stufe und automatischen Beweissystemen erster Stufe zu schließen, indem automatische Beweissysteme so erweitert werden, dass sie die Möglichkeiten die Beweisassistenten bieten auch bereit stellen. Der erste Beitrag ist die Erweiterung des Superpositionskalküls erster Stufe um ein polymorphes Typsystem, das Typklassen unterstützt. Die Erweiterung beinhaltet einen Beweis der Widerlegungsvollständigkeit. Das Typsystem als Teil des Superpositionskalkül ermöglicht die Übertragung von Problemen aus Beweisassistenten ohne den sonst üblichen Mehraufwand durch Typenenkodierung. Der zweite Beitrag ist die Entwicklung von SupInd, einer Erweiterung von Superposition, die Datentypen und strukturelle Induktion über diese Datentypen ermöglicht. SupInd beinhaltet Heuristiken, die die Induktion lenken und Annahmenverstärkungstechniken, die auch unabhängig des Kalküls benutzt werden können. Die Beiträge wurden im Tool Pirate umgesetzt, die Evaluationen zeigen vielversprechende Ergebnisse.