Logical Reasoning and Theorem Proving

Logical reasoning and theorem proving concern the use of formal logic to represent knowledge and the automation of deduction, deriving conclusions that necessarily follow from a set of premises.

Definition

Theorem proving is the automated derivation of whether a logical formula follows from a set of axioms, typically by manipulating the formulas with sound inference rules until the goal is derived or a contradiction is reached.

Scope

This topic covers reasoning in propositional and first-order logic and the algorithms that automate it: truth-table and DPLL-based satisfiability checking for propositional logic, unification and the resolution principle for first-order logic, forward and backward chaining, and the foundations of logic programming. It addresses soundness, completeness, and decidability of inference procedures. Reasoning that tolerates uncertainty or defaults is treated in the related topics on reasoning under uncertainty and nonmonotonic reasoning.

Core questions

• What does it mean for a conclusion to be entailed by a set of premises, and how is entailment checked mechanically?
• How does the resolution principle, with unification, give a single complete inference rule for first-order logic?
• How do forward and backward chaining differ as inference strategies?
• What are the limits of automated reasoning, given that first-order validity is only semi-decidable?

Key concepts

• propositional and first-order logic
• entailment and validity
• unification
• resolution and refutation
• DPLL and SAT solving
• forward and backward chaining
• Horn clauses and logic programming
• soundness and completeness

Key theories

Resolution principle

Robinson's resolution is a single inference rule on clauses that, combined with unification, is refutation-complete for first-order logic: any unsatisfiable set of clauses can be shown unsatisfiable by deriving the empty clause.

DPLL and propositional satisfiability

The Davis-Putnam procedure and its DPLL refinement decide propositional satisfiability by systematic case splitting with unit propagation and pure-literal elimination, forming the basis of modern SAT solvers.

Logic programming and backward chaining

Restricting first-order logic to Horn clauses and resolving goals backward yields logic programming, in which computation is proof search, providing both a reasoning method and a programming paradigm.

Clinical relevance

Automated theorem proving and SAT/SMT solving are used in hardware and software verification, program analysis, planning, and mathematics, while logic programming languages such as Prolog apply backward-chaining inference to databases, parsing, and rule-based systems.

History

Early proof procedures by Gilmore, Davis and Putnam (1960) automated propositional and quantificational reasoning, and Robinson's resolution principle (1965) unified first-order inference into one rule. The 1970s saw resolution refined into logic programming and Prolog; SAT and SMT solving later grew into a major practical technology.

Key figures

• John Alan Robinson
• Martin Davis
• Hilary Putnam
• Robert Kowalski
• Alan Robinson

Seminal works

• robinson1965
• davis1960
• kowalski1979

Frequently asked questions

What is the resolution principle?

Resolution is a single inference rule that takes two clauses containing complementary literals and produces a new clause combining the rest. Applied repeatedly with unification, it can show that a set of first-order clauses is unsatisfiable, which is the basis for proving theorems by refutation.

Is automated theorem proving guaranteed to terminate?

For propositional logic, validity is decidable, so procedures terminate. For full first-order logic, validity is only semi-decidable: a complete prover will eventually confirm any valid formula, but may run forever on an invalid one, so termination is not guaranteed in general.