Automated theorem proving
Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a major impetus for the development of computer science.
Contents
Logical foundations
While the roots of formalised logic go back to Aristotle, the end of the 19th and early 20th centuries saw the development of modern logic and formalised mathematics. Frege's Begriffsschrift (1879) introduced both a complete propositional calculus and what is essentially modern predicate logic.^{[1]} His Foundations of Arithmetic, published 1884,^{[2]} expressed (parts of) mathematics in formal logic. This approach was continued by Russell and Whitehead in their influential Principia Mathematica, first published 1910–1913,^{[3]} and with a revised second edition in 1927.^{[4]} Russell and Whitehead thought they could derive all mathematical truth using axioms and inference rules of formal logic, in principle opening up the process to automatisation. In 1920, Thoralf Skolem simplified a previous result by Leopold Löwenheim, leading to the Löwenheim–Skolem theorem and, in 1930, to the notion of a Herbrand universe and a Herbrand interpretation that allowed (un)satisfiability of firstorder formulas (and hence the validity of a theorem) to be reduced to (potentially infinitely many) propositional satisfiability problems.^{[5]}
In 1929, Mojżesz Presburger showed that the theory of natural numbers with addition and equality (now called Presburger arithmetic in his honor) is decidable and gave an algorithm that could determine if a given sentence in the language was true or false.^{[6]}^{[7]} However, shortly after this positive result, Kurt Gödel published On Formally Undecidable Propositions of Principia Mathematica and Related Systems (1931), showing that in any sufficiently strong axiomatic system there are true statements which cannot be proved in the system. This topic was further developed in the 1930s by Alonzo Church and Alan Turing, who on the one hand gave two independent but equivalent definitions of computability, and on the other gave concrete examples for undecidable questions.
First implementations
Shortly after World War II, the first general purpose computers became available. In 1954, Martin Davis programmed Presburger's algorithm for a JOHNNIAC vacuum tube computer at the Princeton Institute for Advanced Study. According to Davis, "Its great triumph was to prove that the sum of two even numbers is even".^{[7]}^{[8]} More ambitious was the Logic Theory Machine in 1956, a deduction system for the propositional logic of the Principia Mathematica, developed by Allen Newell, Herbert A. Simon and J. C. Shaw. Also running on a JOHNNIAC, the Logic Theory Machine constructed proofs from a small set of propositional axioms and three deduction rules: modus ponens, (propositional) variable substitution, and the replacement of formulas by their definition. The system used heuristic guidance, and managed to prove 38 of the first 52 theorems of the Principia.^{[7]}
The "heuristic" approach of the Logic Theory Machine tried to emulate human mathematicians, and could not guarantee that a proof could be found for every valid theorem even in principle. In contrast, other, more systematic algorithms achieved, at least theoretically, completeness for firstorder logic. Initial approaches relied on the results of Herbrand and Skolem to convert a firstorder formula into successively larger sets of propositional formulae by instantiating variables with terms from the Herbrand universe. The propositional formulas could then be checked for unsatisfiability using a number of methods. Gilmore's program used conversion to disjunctive normal form, a form in which the satisfiability of a formula is obvious.^{[7]}^{[9]}
Decidability of the problem
This section does not cite any sources. (April 2010) (Learn how and when to remove this template message)

Depending on the underlying logic, the problem of deciding the validity of a formula varies from trivial to impossible. For the frequent case of propositional logic, the problem is decidable but coNPcomplete, and hence only exponentialtime algorithms are believed to exist for general proof tasks. For a first order predicate calculus, Gödel's completeness theorem states that the theorems (provable statements) are exactly the logically valid wellformed formulas, so identifying valid formulas is recursively enumerable: given unbounded resources, any valid formula can eventually be proven. However, invalid formulas (those that are not entailed by a given theory), cannot always be recognized.
The above applies to first order theories, such as Peano arithmetic. However, for a specific model that may be described by a first order theory, some statements may be true but undecidable in the theory used to describe the model. For example, by Gödel's incompleteness theorem, we know that any theory whose proper axioms are true for the natural numbers cannot prove all first order statements true for the natural numbers, even if the list of proper axioms is allowed to be infinite enumerable. It follows that an automated theorem prover will fail to terminate while searching for a proof precisely when the statement being investigated is undecidable in the theory being used, even if it is true in the model of interest. Despite this theoretical limit, in practice, theorem provers can solve many hard problems, even in models that are not fully described by any first order theory (such as the integers).
Related problems
A simpler, but related, problem is proof verification, where an existing proof for a theorem is certified valid. For this, it is generally required that each individual proof step can be verified by a primitive recursive function or program, and hence the problem is always decidable.
Since the proofs generated by automated theorem provers are typically very large, the problem of proof compression is crucial and various techniques aiming at making the prover's output smaller, and consequently more easily understandable and checkable, have been developed.
Proof assistants require a human user to give hints to the system. Depending on the degree of automation, the prover can essentially be reduced to a proof checker, with the user providing the proof in a formal way, or significant proof tasks can be performed automatically. Interactive provers are used for a variety of tasks, but even fully automatic systems have proved a number of interesting and hard theorems, including at least one that has eluded human mathematicians for a long time, namely the Robbins conjecture.^{[10]}^{[11]} However, these successes are sporadic, and work on hard problems usually requires a proficient user.
Another distinction is sometimes drawn between theorem proving and other techniques, where a process is considered to be theorem proving if it consists of a traditional proof, starting with axioms and producing new inference steps using rules of inference. Other techniques would include model checking, which, in the simplest case, involves bruteforce enumeration of many possible states (although the actual implementation of model checkers requires much cleverness, and does not simply reduce to brute force).
There are hybrid theorem proving systems which use model checking as an inference rule. There are also programs which were written to prove a particular theorem, with a (usually informal) proof that if the program finishes with a certain result, then the theorem is true. A good example of this was the machineaided proof of the four color theorem, which was very controversial as the first claimed mathematical proof which was essentially impossible to verify by humans due to the enormous size of the program's calculation (such proofs are called nonsurveyable proofs). Another example of a programassisted proof is the one that shows that the game of Connect Four can always be won by first player.
Industrial uses
Commercial use of automated theorem proving is mostly concentrated in integrated circuit design and verification. Since the Pentium FDIV bug, the complicated floating point units of modern microprocessors have been designed with extra scrutiny. AMD, Intel and others use automated theorem proving to verify that division and other operations are correctly implemented in their processors.
Firstorder theorem proving
In the late 1960s agencies funding research in automated deduction began to emphasize the need for practical applications. One of the first fruitful areas was that of program verification whereby firstorder theorem provers were applied to the problem of verifying the correctness of computer programs in languages such as Pascal, Ada, Java etc. Notable among early program verification systems was the Stanford Pascal Verifier developed by David Luckham at Stanford University. This was based on the Stanford Resolution Prover also developed at Stanford using J.A. Robinson's resolution Principle. This was the first automated deduction system to demonstrate an ability to solve mathematical problems that were announced in the Notices of the American Mathematical Society before solutions were formally published.
Firstorder theorem proving is one of the most mature subfields of automated theorem proving. The logic is expressive enough to allow the specification of arbitrary problems, often in a reasonably natural and intuitive way. On the other hand, it is still semidecidable, and a number of sound and complete calculi have been developed, enabling fully automated systems. More expressive logics, such as higher order logics, allow the convenient expression of a wider range of problems than first order logic, but theorem proving for these logics is less well developed.
Benchmarks, Competitions, and Sources
The quality of implemented systems has benefited from the existence of a large library of standard benchmark examples — the Thousands of Problems for Theorem Provers (TPTP) Problem Library^{[12]} — as well as from the CADE ATP System Competition (CASC), a yearly competition of firstorder systems for many important classes of firstorder problems.
Some important systems (all have won at least one CASC competition division) are listed below.
 E is a highperformance prover for full firstorder logic, but built on a purely equational calculus, originally developed in the automated reasoning group of Technical University of Munich, and now at BadenWürttemberg Cooperative State University in Stuttgart.
 Otter, developed at the Argonne National Laboratory, is based on firstorder resolution and paramodulation. Otter has since been replaced by Prover9, which is paired with Mace4.
 SETHEO is a highperformance system based on the goaldirected model elimination calculus. It is developed in the automated reasoning group of Technical University of Munich. E and SETHEO have been combined (with other systems) in the composite theorem prover ESETHEO.
 Vampire is developed and implemented at Manchester University by Andrei Voronkov and Krystof Hoder, formerly also by Alexandre Riazanov. It has won the CADE ATP System Competition in the most prestigious CNF (MIX) division for eleven years (1999, 2001–2010).
 Waldmeister is a specialized system for unitequational firstorder logic developed by Arnim Buch and Thomas Hillenbrand. It won the CASC UEQ division for fourteen consecutive years (1997–2010).
 SPASS is a first order logic theorem prover with equality. This is developed by the research group Automation of Logic, Max Planck Institute for Computer Science.
The Theorem Prover Museum is an initiative to conserve the sources of theorem prover systems for future analysis, since they are imporant cultural/scientific artefacts. It has the sources of many of the systems mentioned above.
Popular techniques
 Firstorder resolution with unification
 Model elimination
 Method of analytic tableaux
 Superposition and term rewriting
 Model checking
 Mathematical induction^{[13]}
 Binary decision diagrams
 DPLL
 Higherorder unification
Comparison
Name  License type  Web service  Library  Standalone  Last update (YYYYmmdd format) 

ACL2  3clause BSD  No  No  Yes  March 2017 
Prover9/Otter  Public Domain  Via System on TPTP  Yes  No  2009 
Metis  MIT License  No  Yes  No  March 1, 2018 
MetiTarski  MIT  Via System on TPTP  Yes  Yes  October 21, 2014 
Jape  GPLv2  Yes  Yes  No  May 15, 2015 
PVS  GPLv2  No  Yes  No  January 14, 2013 
Leo II  BSD License  Via System on TPTP  Yes  Yes  2013 
EQP  ?  No  Yes  No  May 2009 
SAD  GPLv3  Yes  Yes  No  August 27, 2008 
PhoX  ?  No  Yes  No  September 28, 2017 
KeYmaera  GPL  Via Java Webstart  Yes  Yes  March 11, 2015 
Gandalf  ?  No  Yes  No  2009 
E  GPL  Via System on TPTP  No  Yes  July 4, 2017 
SNARK  Mozilla Public License 1.1  No  Yes  No  2012 
Vampire  Vampire License  Via System on TPTP  Yes  Yes  December 14, 2017 
Theorem Proving System (TPS)  TPS Distribution Agreement  No  Yes  No  February 4, 2012 
SPASS  FreeBSD license  Yes  Yes  Yes  November 2005 
IsaPlanner  GPL  No  Yes  Yes  2007 
KeY  GPL  Yes  Yes  Yes  October 11, 2017 
Princess  lgpl v2.1  Via Java Webstart and System on TPTP  Yes  Yes  January 27, 2018 
iProver  GPL  Via System on TPTP  No  Yes  2018 
Meta Theorem  Freeware  No  No  Yes  2018 
Free software
 AltErgo
 Automath
 CVC
 E ([1])
 Gödel machine
 iProver
 IsaPlanner
 KED theorem prover
 leanCoP
 Leo II ([2])
 LCF
 LoTREC
 MetaPRL
 Mizar
 NuPRL
 Paradox
 Simplify (GPL'ed since 5/2011)
 Twelf
 SPARK (programming language)
Proprietary software
 Acumen RuleManager (commercial product)
 ALLIGATOR (CC BYNCSA 2.0 UK)
 CARINE
 KIV (freely available as a plugin for Eclipse)
 Prover PlugIn (commercial proof engine product)
 ProverBox
 ResearchCyc
 Spear modular arithmetic theorem prover
Notable people
 Leo Bachmair, codeveloper of the superposition calculus.
 Woody Bledsoe, artificial intelligence pioneer.
 Robert S. Boyer, coauthor of the BoyerMoore theorem prover, corecipient of the Herbrand Award 1999.
 Alan Bundy, University of Edinburgh, metalevel reasoning for guiding inductive proof, proof planning and recipient of 2007 IJCAI Award for Research Excellence, Herbrand Award, and 2003 Donald E. Walker Distinguished Service Award.
 William McCune Argonne National Laboratory, author of Otter, the first highperformance theorem prover. Many important papers, recipient of the Herbrand Award 2000.
 Hubert Comon, CNRS and now ENS Cachan. Many important papers.
 Robert Lee Constable, Cornell University. Important contributions to type theory, NuPRL.
 Martin Davis, author of the "Handbook of Artificial Reasoning", coinventor of the DPLL algorithm, recipient of the Herbrand Award 2005.
 Branden Fitelson University of California at Berkeley. Work in automated discovery of shortest axiomatic bases for logic systems.
 Harald Ganzinger, codeveloper of the superposition calculus, head of the MPI Saarbrücken, recipient of the Herbrand Award 2004 (posthumous).
 Michael Genesereth, Stanford University professor of Computer Science.
 Melvin Fitting, author of several books and several hundred articles in ATP, software researcher in tableau proof systems.
 Keith Goolsbey chief developer of the Cyc inference engine.
 Michael J. C. Gordon led the development of the HOL theorem prover.
 Gérard Huet Term rewriting, HOL logics, Herbrand Award 1998.
 Robert Kowalski developed the connection graph theoremprover and SLD resolution, the inference engine that executes logic programs.
 Donald W. Loveland Duke University. Author, codeveloper of the DPLLprocedure, developer of model elimination, recipient of the Herbrand Award 2001.
 David Luckham Stanford University, Developed the Stanford Resolution Theorem Prover 1968, the first automated deduction system used to solve problems announced in the Notices of the AMS, and subsequently developed the Stanford Pascal Verifier, the first program verification system for Pascal, and a widely distributed program verification system, 1968–75
 Norman Megill, developer of Metamath, and maintainer of its site at metamath.org, an online database of automatically verified proofs.
 J Strother Moore, coauthor of the Boyer–Moore theorem prover, corecipient of the Herbrand Award 1999.
 Robert Nieuwenhuis University of Barcelona. Codeveloper of the superposition calculus.
 Tobias Nipkow of the Technical University of Munich, contributions to (higherorder) rewriting, codeveloper of the Isabelle proof assistant
 Ross Overbeek Argonne National Laboratory. Founder of The Fellowship for Interpretation of Genomes
 Lawrence C. Paulson of the University of Cambridge, work on higherorder logic system, codeveloper of the Isabelle Theorem Prover
 David Plaisted University of North Carolina at Chapel Hill. Complexity results, contributions to rewriting and completion, instancebased theorem proving.
 John Rushby Program Director – SRI International^{[14]}
 J. Alan Robinson Syracuse University. Developed original resolution and unification based first order theorem proving, coeditor of the "Handbook of Automated Reasoning", recipient of the Herbrand Award 1996
 Jürgen Schmidhuber, work on Gödel Machines: SelfReferential Universal Problem Solvers Making Provably Optimal SelfImprovements
 Stephan Schulz, E theorem Prover.
 Natarajan Shankar SRI International, work on decision procedures, little engines of proof, codeveloper of PVS.
 Mark Stickel SRI International. Recipient of the Herbrand Award 2002.
 Geoff Sutcliffe University of Miami. Maintainer of the TPTP collection, an organizer of the CADE annual contest.
 Dolph Ulrich Purdue, Work on automated discovery of shortest axiomatic bases for systems.
 Robert Veroff University of New Mexico. Many important papers.
 Andrei Voronkov Developer of Vampire and CoEditor of the "Handbook of Automated Reasoning"
 Larry Wos Argonne National Laboratory. (Otter) Many important papers. Very first Herbrand Award winner (1992)
 WenTsun Wu Work in geometric theorem proving: Wu's method, Herbrand Award 1997
 Christoph Weidenbach, author of SPASS, automated theorem prover.
See also
Notes
 ^ Frege, Gottlob (1879). Begriffsschrift. Verlag Louis Neuert.
 ^ Frege, Gottlob (1884). Die Grundlagen der Arithmetik (PDF). Breslau: Wilhelm Kobner.
 ^ Bertrand Russell; Alfred North Whitehead (1910–1913). Principia Mathematica (1st ed.). Cambridge University Press.
 ^ Bertrand Russell; Alfred North Whitehead (1927). Principia Mathematica (2nd ed.). Cambridge University Press.
 ^ Herbrand, Jaques (1930). Recherches sur la théorie de la démonstration.
 ^ Presburger, Mojżesz (1929). "Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt". Comptes Rendus du I congrès de Mathématiciens des Pays Slaves. Warszawa: 92–101.
 ^ ^{a} ^{b} ^{c} ^{d} Davis, Martin (2001), "The Early History of Automated Deduction", in Robinson, Alan; Voronkov, Andrei, Handbook of Automated Reasoning, 1, Elsevier)
 ^ Bibel, Wolfgang (2007). "Early History and Perspectives of Automated Deduction" (PDF). KI 2007. LNAI. Springer (4667): 2–18. Retrieved 2 September 2012.
 ^ Gilmore, Paul (1960). "A proof procedure for quantification theory: its justification and realisation". IBM Journal of Research and Development. 4: 28–35. doi:10.1147/rd.41.0028.
 ^ W.W. McCune (1997). "Solution of the Robbins Problem". Journal of Automated Reasoning. 19 (3).
 ^ Gina Kolata (December 10, 1996). "Computer Math Proof Shows Reasoning Power". The New York Times. Retrieved 20081011.
 ^ Sutcliffe, Geoff. "The TPTP Problem Library for Automated Theorem Proving". Retrieved 8 September 2012.
 ^ Bundy, Alan. The automation of proof by mathematical induction. 1999.
 ^ "SRI International Computer Science Laboratory – John Rushby". SRI International. Retrieved 22 September 2012.
References
 ChinLiang Chang; Richard CharTung Lee (1973). Symbolic Logic and Mechanical Theorem Proving. Academic Press.
 Loveland, Donald W. (1978). Automated Theorem Proving: A Logical Basis. Fundamental Studies in Computer Science Volume 6. NorthHolland Publishing.
 Luckham, David (1990). Programming with Specifications: An Introduction to Anna, A Language for Specifying Ada Programs. SpringerVerlag Texts and Monographs in Computer Science, 421 pp.
 Gallier, Jean H. (1986). Logic for Computer Science: Foundations of Automatic Theorem Proving. Harper & Row Publishers (Available for free download).
 Duffy, David A. (1991). Principles of Automated Theorem Proving. John Wiley & Sons.
 Wos, Larry; Overbeek, Ross; Lusk, Ewing; Boyle, Jim (1992). Automated Reasoning: Introduction and Applications (2nd ed.). McGraw–Hill.
 Alan Robinson; Andrei Voronkov, eds. (2001). Handbook of Automated Reasoning Volume I & II. Elsevier and MIT Press.
 Fitting, Melvin (1996). FirstOrder Logic and Automated Theorem Proving (2nd ed.). Springer.
External links
 A list of theorem proving tools