View source for Automated theorem proving

{{short description|Subfield of automated reasoning and mathematical logic}}
'''Automated theorem proving''' (also known as '''ATP''' or '''automated deduction''') is a subfield of [[automated reasoning]] and [[mathematical logic]] dealing with proving [[mathematical theorem]]s by [[computer program]]s. Automated reasoning over [[mathematical proof]] was a major motivating factor for the development of [[computer science]].

== Logical foundations ==
While the roots of formalized [[Logicism|logic]] go back to [[Aristotelian logic|Aristotle]], the end of the 19th and early 20th centuries saw the development of modern logic and formalized mathematics. [[Gottlob Frege|Frege]]'s ''[[Begriffsschrift]]'' (1879) introduced both a complete [[propositional logic|propositional calculus]] and what is essentially modern [[predicate logic]].<ref>{{cite book|last=Frege|first=Gottlob|title=Begriffsschrift|year=1879|publisher=Verlag Louis Neuert|url=https://gallica.bnf.fr/ark:/12148/bpt6k65658c}}</ref> His ''[[The Foundations of Arithmetic|Foundations of Arithmetic]]'', published in 1884,<ref>{{cite book|last=Frege|first=Gottlob|title=Die Grundlagen der Arithmetik|year=1884|publisher=Wilhelm Kobner|location=Breslau|url=http://www.ac-nancy-metz.fr/enseign/philo/textesph/Frege.pdf|access-date=2012-09-02|archive-url=https://web.archive.org/web/20070926172317/http://www.ac-nancy-metz.fr/enseign/philo/textesph/Frege.pdf|archive-date=2007-09-26|url-status=dead}}</ref> expressed (parts of) mathematics in formal logic. This approach was continued by [[Bertrand Russell|Russell]] and [[Alfred North Whitehead|Whitehead]] in their influential ''[[Principia Mathematica]]'', first published 1910–1913,<ref>{{cite book |author=Russell |first1=Bertrand |url=https://archive.org/details/cu31924001575244 |title=Principia Mathematica |last2=Whitehead |first2=Alfred North |publisher=Cambridge University Press |year=1910–1913 |edition=1st}}</ref> and with a revised second edition in 1927.<ref>{{cite book |author=Russell |first1=Bertrand |url=https://archive.org/details/in.ernet.dli.2015.221192 |title=Principia Mathematica |last2=Whitehead |first2=Alfred North |publisher=Cambridge University Press |year=1927 |edition=2nd |language=en}}</ref> Russell and Whitehead thought they could derive all mathematical truth using [[axiom]]s and [[inference rule]]s of formal logic, in principle opening up the process to automation. 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 [[satisfiability|(un)satisfiability]] of first-order formulas (and hence the [[Validity (logic)|validity]] of a theorem) to be reduced to (potentially infinitely many) propositional satisfiability problems.<ref>{{cite thesis |first=J. |last=Herbrand |title=Recherches sur la théorie de la démonstration |date=1930 |type=PhD |publisher=University of Paris |url=https://eudml.org/doc/192791 |language=fr}}</ref>

In 1929, [[Mojżesz Presburger]] showed that the [[first-order theory]] of the [[natural numbers]] with addition and equality (now called [[Presburger arithmetic]] in his honor) is [[Decidability (logic)|decidable]] and gave an algorithm that could determine if a given [[sentence (logic)|sentence]] in the [[language (logic)|language]] was true or false.<ref>{{cite journal|last=Presburger|first=Mojżesz|title=Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt|journal=Comptes Rendus du I Congrès de Mathématiciens des Pays Slaves|year=1929|pages=92–101|location=Warszawa}}</ref><ref name=Davis2001>{{Cite book
| last = Davis
| first = Martin
| author-link = Martin Davis (mathematician)
| chapter = The Early History of Automated Deduction
| year = 2001
| chapter-url = http://cs.nyu.edu/cs/faculty/davism/early.ps
| title = {{harvnb|Robinson|Voronkov|2001}}
| access-date = 2012-09-08
| archive-date = 2012-07-28
| archive-url = https://web.archive.org/web/20120728092819/http://www.cs.nyu.edu/cs/faculty/davism/early.ps
| url-status = dead
}}</ref>

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 that 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 of [[Undecidable problem|undecidable question]]s.

== First implementations ==

In 1954, [[Martin Davis (mathematician)|Martin Davis]] programmed Presburger's algorithm for a [[JOHNNIAC]] [[vacuum-tube computer]] at the [[Institute for Advanced Study]] in Princeton, New Jersey. According to Davis, "Its great triumph was to prove that the sum of two even numbers is even".<ref name=Davis2001/><ref name=Bibel2007>{{cite journal|last=Bibel|first=Wolfgang|title=Early History and Perspectives of Automated Deduction|journal=Ki 2007|year=2007|series=LNAI|issue=4667|pages=2–18|url=http://www.intellektik.de/resources/OsnabrueckBuchfassung.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.intellektik.de/resources/OsnabrueckBuchfassung.pdf |archive-date=2022-10-09 |url-status=live|access-date=2 September 2012|publisher=Springer}}</ref> More ambitious was the [[Logic Theorist]] in 1956, a deduction system for the [[propositional logic]] of the ''Principia Mathematica'', developed by [[Allen Newell]], [[Herbert A. Simon]] and [[Cliff Shaw|J. C. Shaw]]. Also running on a JOHNNIAC, the Logic Theorist constructed proofs from a small set of propositional axioms and three deduction rules: [[modus ponens]], (propositional) [[Substitution_(logic)|variable substitution]], and the replacement of formulas by their definition. The system used [[Heuristic (computer science)|heuristic]] guidance, and managed to prove 38 of the first 52 theorems of the ''Principia''.<ref name=Davis2001/>

The "heuristic" approach of the Logic Theorist 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 (logic)|completeness]] for first-order logic. Initial approaches relied on the results of [[Jacques Herbrand|Herbrand]] and [[Thoralf Skolem|Skolem]] to convert a first-order formula into successively larger sets of [[propositional formula]]e by instantiating variables with [[term (logic)|term]]s 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.<ref name=Davis2001/><ref>{{cite journal|last=Gilmore|first=Paul|title=A proof procedure for quantification theory: its justification and realisation|journal=IBM Journal of Research and Development|year=1960|volume=4|pages=28–35|doi=10.1147/rd.41.0028}}</ref>

== Decidability of the problem ==
{{Unreferenced section|date=April 2010}}
Depending on the underlying logic, the problem of deciding the validity of a formula varies from trivial to impossible. For the common case of [[propositional logic]], the problem is decidable but [[co-NP-complete]], and hence only [[exponential time|exponential-time]] algorithms are believed to exist for general proof tasks. For a [[first-order logic|first-order predicate calculus]], [[Gödel's completeness theorem]] states that the theorems (provable statements) are exactly the semantically valid [[well-formed formula]]s, so the valid formulas are [[computably 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 axioms|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 consistent theory whose axioms are true for the natural numbers cannot prove all first-order statements true for the natural numbers, even if the list of 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 [[integer]]s).

== 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 assistant]]s 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]].<ref>{{cite journal |last=McCune |first=W. W. |year=1997 |title=Solution of the Robbins Problem |journal=[[Journal of Automated Reasoning]] |volume=19 |issue=3 |pages=263–276 |doi=10.1023/A:1005843212881 |s2cid=30847540}}</ref><ref>{{cite news |author=Kolata |first=Gina |date=December 10, 1996 |title=Computer Math Proof Shows Reasoning Power |newspaper=The New York Times |url=https://www.nytimes.com/library/cyber/week/1210math.html |access-date=2008-10-11}}</ref> 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 brute-force 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 that use model checking as an inference rule. There are also programs that 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 machine-aided proof of the [[four color theorem]], which was very controversial as the first claimed mathematical proof that was essentially impossible to verify by humans due to the enormous size of the program's calculation (such proofs are called [[non-surveyable proofs]]). Another example of a program-assisted proof is the one that shows that the game of [[Connect Four]] can always be won by the first player.

== Applications ==
Commercial use of automated theorem proving is mostly concentrated in [[integrated circuit design]] and verification. Since the [[Pentium FDIV bug]], the complicated [[floating point unit]]s 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.<ref>{{Citation |last=Goel |first=Shilpi |title=Microprocessor Assurance and the Role of Theorem Proving |date=2022 |work=Handbook of Computer Architecture |pages=1–43 |editor-last=Chattopadhyay |editor-first=Anupam |url=https://link.springer.com/10.1007/978-981-15-6401-7_38-1 |access-date=2024-02-10 |place=Singapore |publisher=Springer Nature Singapore |language=en |doi=10.1007/978-981-15-6401-7_38-1 |isbn=978-981-15-6401-7 |last2=Ray |first2=Sandip|url-access=subscription }}</ref>

Other uses of theorem provers include [[program synthesis]], constructing programs that satisfy a [[formal specification]].<ref>{{cite book |last1=Basin |first1=D. |title=Program Development in Computational Logic |last2=Deville |first2=Y. |last3=Flener |first3=P. |last4=Hamfelt |first4=A. |last5=Fischer Nilsson |first5=J. |publisher=Springer |year=2004 |editor=M. Bruynooghe and K.-K. Lau |series=LNCS |volume=3049 |pages=30&ndash;65 |chapter=Synthesis of programs in computational logic |citeseerx=10.1.1.62.4976}}</ref> Automated theorem provers have been integrated with [[Proof assistant|proof assistants]], including [[Isabelle (proof assistant)|Isabelle/HOL]].<ref>{{Cite journal |last1=Meng |first1=Jia |last2=Paulson |first2=Lawrence C. |date=2008-01-01 |title=Translating Higher-Order Clauses to First-Order Clauses |url=https://doi.org/10.1007/s10817-007-9085-y |journal=Journal of Automated Reasoning |language=en |volume=40 |issue=1 |pages=35–60 |doi=10.1007/s10817-007-9085-y |issn=1573-0670 |s2cid=7716709|url-access=subscription }}</ref>

Applications of theorem provers are also found in [[natural language processing]] and [[formal semantics (natural language)|formal semantics]], where they are used to analyze [[Discourse representation theory|discourse representations]].<ref>Bos, Johan. [https://aclanthology.org/W08-2222.pdf "Wide-coverage semantic analysis with boxer."] Semantics in text processing. step 2008 conference proceedings. 2008.</ref><ref>Muskens, Reinhard. [https://philarchive.org/archive/MUSCMS "Combining Montague semantics and discourse representation."] Linguistics and philosophy (1996): 143-186.</ref>

==First-order theorem proving==
In the late 1960s agencies funding research in automated deduction began to emphasize the need for practical applications.{{citation needed|date=December 2023}} One of the first fruitful areas was that of [[program verification]] whereby first-order theorem provers were applied to the problem of verifying the correctness of computer programs in languages such as [[Pascal (programming language)|Pascal]], [[Ada (programming language)|Ada]], etc. Notable among early program verification systems was the Stanford Pascal Verifier developed by [[David Luckham]] at [[Stanford University]].<ref>{{cite report |url=https://apps.dtic.mil/sti/citations/ADA027455 |title=Automatic Program Verification V: Verification-Oriented Proof Rules for Arrays, Records, and Pointers |author=Luckham |first1=David C. |last2=Suzuki |first2=Norihisa |date=Mar 1976 |archive-url=https://web.archive.org/web/20210812180903/https://apps.dtic.mil/sti/citations/ADA027455 |archive-date=August 12, 2021 |url-status=live |institution=[[Defense Technical Information Center]] |type=Technical Report AD-A027 455}}</ref><ref>{{cite journal | doi=10.1145/357073.357078 | first1=David C. |last1=Luckham |first2=Norihisa |last2=Suzuki | title=Verification of Array, Record, and Pointer Operations in Pascal | journal=[[ACM Transactions on Programming Languages and Systems]] | volume=1 | number=2 | pages=226–244 | date=Oct 1979 | s2cid=10088183 | doi-access=free }}</ref><ref>{{cite tech report | url=https://exhibits.stanford.edu/stanford-pubs/catalog/nh154bt5645 |first1=D. |last1=Luckham |first2=S. |last2=German |first3=F. |last3=von Henke |first4=R. |last4=Karp |first5=P. |last5=Milne |first6=D. |last6=Oppen |first7=W. |last7=Polak |first8=W. |last8=Scherlis | title=Stanford Pascal verifier user manual | institution=Stanford University | id=CS-TR-79-731 | year=1979 }}</ref> This was based on the Stanford Resolution Prover also developed at Stanford using [[John Alan Robinson]]'s [[Resolution (logic)|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.{{citation needed|date=September 2020}}

[[First-order logic|First-order]] 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 semi-decidable, and a number of sound and complete calculi have been developed, enabling ''fully'' automated systems.<ref>{{Cite book |last=Loveland |first=D. W. |title=Proceedings of the ACM SIGART international symposium on Methodologies for intelligent systems |date=1986 |publisher=ACM Press |isbn=978-0-89791-206-8 |location=Knoxville, Tennessee, United States |page=224 |language=en |chapter=Automated theorem proving: Mapping logic into AI |doi=10.1145/12808.12833 |doi-access=free |s2cid=14361631}}</ref> More expressive logics, such as [[higher-order logic]]s, allow the convenient expression of a wider range of problems than first-order logic, but theorem proving for these logics is less well developed.<ref>Kerber, Manfred. "[https://kluedo.ub.uni-kl.de/files/364/seki_4.pdf How to prove higher order theorems in first order logic]." (1999).</ref><ref>Benzmüller, Christoph, et al. "[https://page.mi.fu-berlin.de/cbenzmueller/papers/C26.pdf LEO-II-a cooperative automatic theorem prover for classical higher-order logic (system description)]." International Joint Conference on Automated Reasoning. Berlin, Germany and Heidelberg: Springer, 2008.</ref>

===Relationship with SMT===

There is substantial overlap between first-order automated theorem provers and [[satisfiability modulo theories|SMT solver]]s. Generally, automated theorem provers focus on supporting full first-order logic with quantifiers, whereas SMT solvers focus more on supporting various theories (interpreted predicate symbols). ATPs excel at problems with lots of quantifiers, whereas SMT solvers do well on large problems without quantifiers.<ref>{{Cite journal |last1=Blanchette |first1=Jasmin Christian |last2=Böhme |first2=Sascha |last3=Paulson |first3=Lawrence C. |date=2013-06-01 |title=Extending Sledgehammer with SMT Solvers |url=https://doi.org/10.1007/s10817-013-9278-5 |journal=Journal of Automated Reasoning |language=en |volume=51 |issue=1 |pages=109–128 |doi=10.1007/s10817-013-9278-5 |s2cid=5389933 |issn=1573-0670|quote=ATPs and SMT solvers have complementary strengths. The former handle quantifiers more elegantly, whereas the latter excel on large, mostly ground problems.|url-access=subscription }}</ref> The line is blurry enough that some ATPs participate in SMT-COMP, while some SMT solvers participate in [[CADE ATP System Competition|CASC]].<ref>{{Cite journal |last1=Weber |first1=Tjark |last2=Conchon |first2=Sylvain |last3=Déharbe |first3=David |last4=Heizmann |first4=Matthias |last5=Niemetz |first5=Aina |last6=Reger |first6=Giles |date=2019-01-01 |title=The SMT Competition 2015–2018 |journal=Journal on Satisfiability, Boolean Modeling and Computation |language=en |volume=11 |issue=1 |pages=221–259 |doi=10.3233/SAT190123|quote=In recent years, we have seen a blurring of lines between SMT-COMP and CASC with SMT solvers competing in CASC and ATPs competing in SMT-COMP.|doi-access=free }}</ref>

==Benchmarks, competitions, and sources ==
The quality of implemented systems has benefited from the existence of a large library of standard [[Benchmark (computing)|benchmark]] examples—the [[Thousands of Problems for Theorem Provers]] (TPTP) Problem Library<ref>{{cite web|last=Sutcliffe|first=Geoff|title=The TPTP Problem Library for Automated Theorem Proving|url=http://www.tptp.org/|access-date=15 July 2019}}</ref>—as well as from the [[CADE ATP System Competition]] (CASC), a yearly competition of first-order systems for many important classes of first-order problems.

Some important systems (all have won at least one CASC competition division) are listed below.
* [[E theorem prover|E]] is a high-performance prover for full first-order logic, but built on a [[superposition calculus|purely equational calculus]], originally developed in the automated reasoning group of [[Technical University of Munich]] under the direction of [[Wolfgang Bibel]], and now at [[Baden-Württemberg Cooperative State University]] in [[Stuttgart]].
* [[Otter (theorem prover)|Otter]], developed at the [[Argonne National Laboratory]], is based on [[first-order resolution]] and [[paramodulation]]. Otter has since been replaced by [[Prover9]], which is paired with [[Mace4]].
* [[SETHEO]] is a high-performance system based on the goal-directed [[model elimination]] calculus, originally developed by a team under direction of [[Wolfgang Bibel]]. E and SETHEO have been combined (with other systems) in the composite theorem prover E-SETHEO.
* [[Vampire theorem prover|Vampire]] was originally developed and implemented at [[University of Manchester|Manchester University]] by [[Andrei Voronkov]] and Kryštof Hoder. It is now developed by a growing international team. It has won the FOF division (among other divisions) at the CADE ATP System Competition regularly since 2001.<ref>{{cite web |title=History |url=https://vprover.github.io/history.html |website=vprover.github.io}}</ref>
* Waldmeister is a specialized system for unit-equational first-order 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<ref>{{cite web|url=https://theoremprover-museum.github.io |title=The Theorem Prover Museum |access-date=2022-11-20 |publisher=[[Michael Kohlhase]]}}</ref> is an initiative to conserve the sources of theorem prover systems for future analysis, since they are important cultural/scientific artefacts. It has the sources of many of the systems mentioned above.

== Popular techniques ==

{{Prose|date=December 2023}}

*[[First-order resolution]] with [[unification (computing)|unification]]
*[[Model elimination]]
*[[Method of analytic tableaux]]
*[[Superposition calculus|Superposition]] and term [[rewriting]]
*[[Model checking]]
*[[Mathematical induction]]<ref>{{cite tech report |first=Alan |last=Bundy |title=The automation of proof by mathematical induction |date=1999 |publisher=Division of Informatics, University of Edinburgh|url=https://www.era.lib.ed.ac.uk/bitstream/handle/1842/3394/0002.pdf?sequence=1 |hdl=1842/3394  |series=Informatics Research Report |volume=2}}</ref>
*[[Binary decision diagram]]s
*[[DPLL algorithm|DPLL]]
*[[Unification (computing)#Higher-order unification|Higher-order unification]]
*[[Quantifier elimination]]<ref>Gabbay, Dov M., and Hans Jürgen Ohlbach. [https://pure.mpg.de/rest/items/item_1834831/component/file_2172339/content "Quantifier elimination in second-order predicate logic."] (1992).</ref>

== Software systems{{anchor|Comparison}} ==
{{See also|Proof assistant#Comparison|Category:Theorem proving software systems}}
{| class="wikitable sortable mw-collapsible mw-collapsed"
|+ Comparison
|-
! Name !! License type !! Web service !! Library !! Standalone !! Last update {{small|([[strftime|YYYY-mm-dd format]])}} 
|-
| [[ACL2]] || [[BSD Licenses|3-clause BSD]] || {{No}} || {{No}} || {{Yes}} || {{dts|2019-05}}
|-
| [[Prover9|Prover9/Otter]] || Public Domain || {{Yes|Via [[System on TPTP]]}} || {{Yes}} || {{No}} || {{dts|2009}} 
|-
| [[Jape (software)|Jape]] || [[GPL | GPLv2]] ||  {{Yes}} || {{Yes}} || {{No}} || {{dts|2015-05-15}} 
|-
| [[Prototype Verification System|PVS]] || [[GPL | GPLv2]] || {{No}} || {{Yes}} || {{No}} || {{dts|2013-01-14}} 
|-
| [[Equational prover|EQP]] || {{dunno}} ||  {{No}} || {{Yes}} || {{No}} || {{dts|2009-05}} 
|-
| [[PhoX]] || {{dunno}} ||  {{No}} || {{Yes}} ||{{No}} || {{dts|2017-09-28}} 
|-
| [[E theorem prover|E]] || [[GPL]] || {{Yes|Via [[System on TPTP]]}} ||{{No}} || {{Yes}}  || {{dts|2017-07-04}}
|-
| [[SNARK theorem prover|SNARK]] || [[Mozilla Public License | Mozilla Public License 1.1]] || {{No}} || {{Yes}} || {{No}} || {{dts|2012}} 
|-
| [[Vampire theorem prover|Vampire]] ||Vampire License ||  {{Yes|Via [[System on TPTP]]}} || {{Yes}} || {{Yes}} || {{dts|2017-12-14}} 
|-
| [[Theorem Proving System]] (TPS) || TPS Distribution Agreement || {{No}} || {{Yes}} || {{No}} || {{dts|2012-02-04}} 
|-
| [[SPASS]] || [[FreeBSD license]] ||  {{Yes}}|| {{Yes}} ||  {{Yes}} || {{dts|2005-11}} 
|-
| [[IsaPlanner]] || [[GPL]] ||  {{No}} || {{Yes}} ||  {{Yes}} || {{dts|2007}} 
|-
| [[KeY]] || [[GPL]] || {{Yes}}||  {{Yes}} || {{Yes}} || {{dts|2017-10-11}} 
|-
| [[Z3 Theorem Prover]] || [[MIT License]] || {{Yes}} || {{Yes}} || {{Yes}} || {{dts|2019|11|19}}
|-
|}

=== Free software ===
* [[Alt-Ergo]]
* [[Automath]]
* [[CVC (theorem prover)|CVC]]
* [[E theorem prover|E]]
* [[IsaPlanner]]
* [[LCF (theorem prover)|LCF]]
* [[Mizar system|Mizar]]
* [[NuPRL]]
* [[Paradox (theorem prover)|Paradox]]
* [[Prover9]]
* [[Prototype Verification System|PVS]]
* [[SPARK (programming language)]]
* [[Twelf]]
* [[Z3 Theorem Prover]]

=== Proprietary software ===
* [[CARINE]]
* [[Wolfram Mathematica]]
* [[ResearchCyc]]

== See also ==
{{Div col}}
* [[Curry–Howard correspondence]]
* [[Symbolic computation]]
* [[Ramanujan machine]]
* [[Computer-aided proof]]
* [[Formal verification]]
* [[Logic programming]]
* [[Proof checking]]
* [[Model checking]]
* [[Proof complexity]]
* [[Computer algebra system]]
* [[Program analysis (computer science)]]
* [[General Problem Solver]]
* [[Metamath]] language for formalized mathematics
* [[De Bruijn factor]]{{colend}}

== Notes ==
{{Reflist}}

== References ==
{{refbegin}}
* {{cite book | title = Symbolic Logic and Mechanical Theorem Proving
| first1 = Chin-Liang |last1=Chang
|first2=Richard Char-Tung |last2=Lee
| publisher = Elsevier
| isbn=9780080917283 |date=2014 |url={{GBurl|oGriBQAAQBAJ|pg=PR7}}
| orig-year = 1973
}}
* {{cite book
| last = Loveland
| first = Donald W. |author-link=Donald W. Loveland
| title = Automated Theorem Proving: A Logical Basis
| series= Fundamental Studies in Computer Science |volume=6
| publisher = Elsevier
| isbn= 9781483296777 |date=2016 |url={{GBurl|lsvSBQAAQBAJ|pg=PP11}}
| orig-year = 1978
}}
*{{cite book
| last = Luckham
| first = David |author-link=David Luckham
| title = Programming with Specifications: An Introduction to Anna, A Language for Specifying Ada Programs
| publisher = Springer
| year = 1990
| isbn = 978-1461396871
}}
* {{cite book
| last = Gallier
| first = Jean H. | author-link = Jean Gallier
| title = Logic for Computer Science: Foundations of Automatic Theorem Proving
| publisher = Dover |edition=2nd
| orig-year = 1986 |date=2015 |isbn=978-0-486-78082-5 |quote=This material may be reproduced for any educational purpose, ...
| url = http://www.cis.upenn.edu/~jean/gbooks/logic.html
}}
* {{cite book
| last = Duffy
| first = David A.
| title = Principles of Automated Theorem Proving
| year = 1991
| publisher = Wiley |isbn=9780471927846
}}
* {{cite book
| last = Wos
| first = Larry |author-link=Larry Wos
|author2= Overbeek, Ross|author3= Lusk, Ewing|author4= Boyle, Jim
| title = Automated Reasoning: Introduction and Applications
| edition = 2nd
| publisher = [[McGraw–Hill]] | isbn=9780079112514
| year = 1992
}}
* {{cite book
| title = Handbook of Automated Reasoning |volume=I
| title-link = Handbook of Automated Reasoning
| editor1-first = Alan |editor1-last=Robinson 
| editor1-link = John Alan Robinson
| editor2-first= Andrei | editor2-last=Voronkov
| editor2-link = Andrei Voronkov (scientist)
| publisher = [[Elsevier]], [[MIT Press]]
| year = 2001
| isbn=9780080532790
}} II {{ISBN|9780262182232}}.
* {{cite book
| last = Fitting
| first = Melvin |author-link=Melvin Fitting
| title = First-Order Logic and Automated Theorem Proving
| edition = 2nd
| publisher = Springer 
| orig-year = 1996 |date=2012 |isbn=9781461223603 
| url = {{GBurl|133kBwAAQBAJ}}
}}
{{refend}}

==External links==
* [https://github.com/johnyf/tool_lists/blob/master/verification_synthesis.md#theorem-provers A list of theorem proving tools]

{{Mathematical logic}}
{{Authority control}}

{{DEFAULTSORT:Automated Theorem Proving}}
[[Category:Automated theorem proving| ]]
[[Category:Formal methods]]