Automated Theorem Proving: Fundamentals and Applications

By Fouad Sabry

What Is Automated Theorem Proving

The process of proving mathematical theorems by the use of computer programs is referred to as automated theorem proving. This subfield of automated reasoning and mathematical logic was developed in the 1980s. A significant driving force behind the development of computer science was the application of automated reasoning to mathematical proof.

How You Will Benefit

(I) Insights, and validations about the following topics:

Chapter 1: Automated theorem proving

Chapter 2: Curry-Howard correspondence

Chapter 3: Logic programming

Chapter 4: Proof complexity

Chapter 5: Metamath

Chapter 6: Model checking

Chapter 7: Formal verification

Chapter 8: Program analysis

Chapter 9: Ramanujan machine

Chapter 10: General Problem Solver

(II) Answering the public top questions about automated theorem proving.

(III) Real world examples for the usage of automated theorem proving in many fields.

Who This Book Is For

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of automated theorem proving.

What is Artificial Intelligence Series

The artificial intelligence book series provides comprehensive coverage in over 200 topics. Each ebook covers a specific Artificial Intelligence topic in depth, written by experts in the field. The series aims to give readers a thorough understanding of the concepts, techniques, history and applications of artificial intelligence. Topics covered include machine learning, deep learning, neural networks, computer vision, natural language processing, robotics, ethics and more. The ebooks are written for professionals, students, and anyone interested in learning about the latest developments in this rapidly advancing field.
The artificial intelligence book series provides an in-depth yet accessible exploration, from the fundamental concepts to the state-of-the-art research. With over 200 volumes, readers gain a thorough grounding in all aspects of Artificial Intelligence. The ebooks are designed to build knowledge systematically, with later volumes building on the foundations laid by earlier ones. This comprehensive series is an indispensable resource for anyone seeking to develop expertise in artificial intelligence.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jul 6, 2023

Book preview

Chapter 1: Automated theorem proving

Automated theorem proving, sometimes referred to as ATP or automated deduction, is an area of automated reasoning and mathematical logic that deals with proving mathematical theorems by computer programs. Other names for this topic include automated deduction and automated reasoning. A significant driving force behind the development of computer science was the application of computerized logic to the verification of mathematical theorems.

While Aristotle is often credited as being the father of formal logic,, In the latter half of the 19th century and the early part of the 20th century, modern logic and formalized mathematics were developed.

Frege's Begriffsschrift (1879) was the first publication that included both a comprehensive propositional calculus as well as what is basically contemporary predicate logic.

However, immediately after obtaining this encouraging outcome, Kurt Gödel published On Formally Undecidable Propositions of Principia Mathematica and Related Systems (1931), demonstrating that every axiomatic framework that is sufficiently robust contains true propositions that cannot be proven using the framework itself.

In the 1930s, Alonzo Church and Alan Turing made significant contributions to the discussion of this subject, who, on the one hand, provided two different definitions of computability that were identical to one another, and, on the other hand, provided tangible instances for issues that could not be answered.

The first computers designed for civilian use were commercially accessible not long after the end of World War II. At the Institute for Advanced Study in Princeton, New Jersey, in the year 1954, Martin Davis was the one who first coded Presburger's algorithm onto a JOHNNIAC vacuum tube computer. Davis claims that the organization's most significant achievement was demonstrating that the sum of any two even integers is also even.

Depending on the reasoning that lies underneath it, Determining the correctness of a formula may range from being an easy task to an insurmountable obstacle.

Regarding the most common instance of propositional logic, The challenge can be solved, however it is co-NP-complete, Consequently, it is assumed that only algorithms with exponentially increasing runtimes exist for generic proving jobs.

For a first order predicate calculus, Gödel's completeness theorem states that the theorems (provable statements) are exactly the logically valid well-formed formulas, Therefore, it is possible to enumerate valid formulae in a recursive fashion: given an unlimited supply of resources, Any correct formula may be shown to exist at some point.

However, invalid formulae (those that are not entailed by a given theory), may not usually allow for recognition.

All of the above applies to theories of the first order, include things like Peano arithmetic.

However, with reference to a particular model that may be explained using a first order theory, In the theory that is being used to define the model, there may be certain claims that are true but cannot be decided.

For example, by Gödel's incompleteness theorem, We are aware that any theory for which the relevant axioms hold for the natural numbers cannot prove all first order propositions to hold for the natural numbers if those axioms hold, Even if the list of correct axioms is permitted to be infinitely enumerable, this won't change anything.

Therefore, an automated theorem prover will not be able to conclude its search for a proof when the statement that is being studied is undecidable in the theory that is being employed, regardless of whether or not it holds true in the model of interest.

Despite the fact that this restriction is theoretical, in practice, Theorem provers have the ability to tackle a variety of challenging situations, even in models that cannot be completely characterized by any first order theory (such as the integers).

Proof verification is a less complicated but similar topic, in which an existing proof for a theorem is checked to ensure that it is valid. In order to do this, it is often essential that each individual proof step be verifiable by a simple recursive function or program; hence, the issue is always capable of being solved.

The subject of proof compression is critical because the proofs that are created by automated theorem provers are often rather extensive. Various strategies have been developed in an effort to make the prover's output smaller and, as a result, more readily comprehensible and checkable.

Proof helpers need the participation of a human user in order to receive and process tips. The prover may be simply reduced to a proof checker, with the user giving the evidence in a formal manner, depending on the degree of automation; alternatively, substantial proof duties may be completed automatically. Even fully automatic systems have proven a number of interesting and difficult theorems, including at least one that has eluded human mathematicians for a considerable amount of time, which is the Robbins conjecture. Interactive provers are used for a variety of tasks, but even fully automatic systems have proven a number of interesting and difficult theorems. However, these accomplishments are not consistent, and working on challenging issues often calls for a user who is skilled.

Another distinction that is sometimes drawn between theorem proving and other techniques is that a process is considered to be theorem proving if it consists of a traditional proof, beginning with axioms and producing new inference steps using rules of inference. This distinction is sometimes drawn because theorem proving is considered to be more rigorous than other techniques. Other methods might include model verification, which, in its simplest form, is the laborious and time-consuming process of enumerating a large number of distinct 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 out there, and one of its functions is to employ model verification as an inference rule. There are other programs that were developed specifically to prove a given theorem. These programs include a (often informal) proof that states that if the program completes with a certain outcome, then the theorem must be correct. The first claimed mathematical proof that was essentially impossible to verify by humans due to the enormous size of the program's calculation was the machine-aided proof of the four color theorem, which caused a lot of controversy when it was presented. A good example of this is the machine-aided proof of the four color theorem (such proofs are called non-surveyable proofs). One such example of a computer-assisted proof is the one that demonstrates the fact that the first player in a game of Connect Four will always emerge victorious.

The integration of automated theorem proving into commercial applications is particularly prevalent in the verification and design of integrated circuits. Since the discovery of the Pentium FDIV problem, contemporary microprocessors' sophisticated floating point units have been subjected to a greater level of scrutiny throughout the design process. Automated theorem proving is used by AMD, Intel, and other companies, amongst others, in order to ensure that division and other operations are accurately implemented in their CPUs.

In the late 1960s, organizations that funded research in automated deduction started placing a greater emphasis on the need of finding practical applications for their findings. The use of first-order theorem provers to the challenge of verifying the correctness of computer programs written in languages such as Pascal, Ada, and so on was one of the first areas that proved to be productive. This was the case in the field of program verification. Among the first program verification systems, the Stanford Pascal Verifier created by David Luckham at Stanford University stands out as particularly innovative.

The existence