AI Notes

Theorem Proving - Automated Reasoning

Learn theorem proving. Proof strategies, SAT. AI 2024.

What is Automated Theorem Proving?

Automated theorem proving (ATP) is the use of computer programs to establish whether a mathematical or logical statement is true given a set of axioms and inference rules. An automated theorem prover takes a knowledge base (premises) and a conjecture (goal) and attempts to construct a formal proof—a sequence of valid inference steps that logically derives the conjecture from the premises.

ATP is foundational to AI: it enables expert systems to reason, verifies software correctness, validates hardware circuits, and proves mathematical theorems. Understanding ATP gives insight into the computational nature of reasoning itself—what can be mechanically proved, what cannot, and how efficiently proofs can be found.

Proof Systems

Natural Deduction

Mirrors human-style reasoning with introduction and elimination rules:

AND-Introduction	AND-Elimination:
IMPLIES-Introduction	IMPLIES-Elimination (Modus Ponens):
[Assume P] P	Q
P	Q

Proof Example: Natural Deduction

Prove: From P	Q and Q→R, derive P→R
1. P	Q (premise)
2. Q	R (premise)
3. \| P (assumption — for	-introduction)
6. P	R (→-introduction, discharging assumption 3)
QED: P	R (hypothetical syllogism)

Sequent Calculus

Uses sequents Γ ⊢ Δ (from assumptions Γ, conclude Δ):

Example

Axiom: P ⊢ P Left rules (analyze assumptions): Γ, A, B ⊢ Δ ─────────────── (∧-Left) Γ, A ∧ B ⊢ Δ Right rules (prove conclusions): Γ ⊢ A Γ ⊢ B ───────────────── (∧-Right) Γ ⊢ A ∧ B

Resolution-Based Theorem Proving

The most common ATP method for first-order logic:

Example

Algorithm: 1. Negate the theorem to prove 2. Convert KB + ¬theorem to CNF (Conjunctive Normal Form) 3. Apply resolution rule repeatedly 4. If empty clause (□) derived → theorem proved 5. If saturated (no new clauses) → theorem not provable from KB

Complete First-Order Example

Axioms

∀x (Philosopher(x) → Thinker(x)) "All philosophers are thinkers"

∀x (Thinker(x) → Curious(x)) "All thinkers are curious"

Philosopher(socrates) "Socrates is a philosopher"

Theorem: Curious(socrates)

Step 1: Negate theorem → ¬Curious(socrates)

Step 2: CNF clauses:

C1: {¬Philosopher(x), Thinker(x)}

C2: {¬Thinker(x), Curious(x)}

C3: {Philosopher(socrates)}

C4: {¬Curious(socrates)} ← negated theorem

Step 3: Resolution

Resolve C2 + C4 (unify x=socrates):

C5: {¬Thinker(socrates)}

Resolve C1 + C5 (unify x=socrates):

C6: {¬Philosopher(socrates)}

Resolve C3 + C6

C7: □ (empty clause!)

Step 4: Contradiction! → Theorem PROVED ✓

Proof Search Strategies

Forward Chaining (Bottom-Up)

Philosopher(socrates) + Rule1	Thinker(socrates)
Thinker(socrates) + Rule2	Curious(socrates) ✓
Pros	Systematic, complete
Cons	May derive irrelevant facts (unfocused)

Backward Chaining (Top-Down)

Goal	Curious(socrates)
Need	Thinker(socrates) [from Rule2]
Need	Philosopher(socrates) [from Rule1]
Pros	Focused, efficient for specific goals
Cons	May loop without proper control

Iterative Deepening

Example

Combine depth-first efficiency with breadth-first completeness: Try proofs of length 1, then 2, then 3, ... First complete proof found is shortest Used in Prover9, E theorem prover

Important Theoretical Results

Completeness Theorems

Example

Propositional logic: Resolution is complete (always terminates) → Decidable! SAT solvers handle millions of variables First-order logic: Resolution is refutation-complete → Semi-decidable: can prove true theorems → May loop forever on non-theorems (undecidable in general) Gödel's Completeness Theorem (1929): Every logically valid FOL formula has a proof (Ensures theorem provers can find proofs that exist) Gödel's Incompleteness Theorem (1931): Any sufficiently powerful formal system has true statements that cannot be proved within the system (Limits what ANY theorem prover can achieve in arithmetic)

Complexity Results

Propositional satisfiability	NP-complete (Cook's theorem)
First-order validity	Undecidable (Church-Turing)
Description logics (OWL)	Decidable fragments of FOL

Modern Theorem Provers

Prover	Logic	Method	Notable Achievement
E	FOL	Superposition	CADE competitions
Vampire	FOL	Resolution + Superposition	Most awards in CASC
Z3	SMT	DPLL(T)	Software verification
Isabelle/HOL	Higher-order	Interactive + auto tactics	Formal math
Lean	Dependent types	Type theory	Mathlib library
Coq	Constructive	Type theory	CompCert verified compiler

Applications of Theorem Proving

Hardware Verification

Prove CPU correctly implements instruction set

Intel uses formal verification after FDIV bug (1994)

Software Verification

Prove programs have no bugs (buffer overflows, null pointers)

seL4 microkernel: formally proved correct (8,700 lines)

Mathematics

Four-Color Theorem (1976): Computer-assisted proof

Kepler Conjecture (2014): Formally verified in Lean

AI Planning

Prove plan achieves goal from initial state

Each plan step is a theorem about state transitions

Knowledge Base Reasoning

Prove queries from ontologies (OWL/DL reasoning)

Check consistency of knowledge bases

Theorem Proving vs. Model Checking

Theorem Proving

Works with formulas symbolically

Proves universal properties (for ALL inputs)

Incomplete for rich logics

Model Checking

Exhaustively checks all states

Proves properties for SPECIFIC system

Complete but limited by state space size (state explosion)

Often combined: model checking for finite systems,

theorem proving for parameterized/infinite systems

Interview Questions

Q: What is the difference between sound and complete proof systems? A: Sound: every provable statement is actually true (no false proofs). Complete: every true statement is provable (no unprovable truths). We always want soundness. Completeness is desirable but sometimes impossible (Gödel's incompleteness for arithmetic). Resolution is both sound and refutation-complete for FOL.

Q: Why can't we just check all possible truth assignments? A: In propositional logic, we could (2^n assignments for n variables), but this is exponential—impractical for large formulas. In first-order logic, the domain is potentially infinite—we can't enumerate all possible interpretations. Theorem proving works syntactically, avoiding this enumeration.

Q: How do modern theorem provers achieve practical performance? A: Through powerful heuristics: clause selection (which clauses to resolve), literal ordering (which literals to resolve on), subsumption (deleting redundant clauses), and term ordering strategies. These don't change what can be proved but drastically reduce the search space explored.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Theorem Proving - Automated Reasoning.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.

Search Terms

artificial-intelligence, artificial intelligence, artificial, intelligence, reasoning, and, inference, theorem

Continue learning this concept

Reasoning And InferenceBackward Chaining - Goal-Driven ReasoningLearn backward chaining. Goal-driven search. Reasoning 2024.Reasoning And InferenceBayesian Networks - ProbabilisticMaster Bayesian networks. DAG, conditional probability. Reasoning 2024.Reasoning And InferenceForward Chaining - InferenceMaster forward chaining. Data-driven inference. Reasoning 2024.Reasoning And InferenceLogical Reasoning - InferenceMaster logical reasoning. Deduction, induction, abduction. AI reasoning 2024.Reasoning And InferenceResolution Method - Logical InferenceMaster resolution. CNF, resolution rule. AI logic 2024.Reasoning And InferenceUncertain Reasoning - Probabilistic AIMaster reasoning under uncertainty. Probability, Bayes. AI 2024.

PreviousResolution Method - Logical Inference NextUncertain Reasoning - Probabilistic AI

AI Notes

Theorem Proving - Automated Reasoning

Learn theorem proving. Proof strategies, SAT. AI 2024.

What is Automated Theorem Proving?

Proof Systems

Natural Deduction

Mirrors human-style reasoning with introduction and elimination rules:

AND-Introduction	AND-Elimination:
IMPLIES-Introduction	IMPLIES-Elimination (Modus Ponens):
[Assume P] P	Q
P	Q

Proof Example: Natural Deduction

Prove: From P	Q and Q→R, derive P→R
1. P	Q (premise)
2. Q	R (premise)
3. \| P (assumption — for	-introduction)
6. P	R (→-introduction, discharging assumption 3)
QED: P	R (hypothetical syllogism)

Sequent Calculus

Uses sequents Γ ⊢ Δ (from assumptions Γ, conclude Δ):

Example

Resolution-Based Theorem Proving

The most common ATP method for first-order logic:

Example

Complete First-Order Example

Axioms

∀x (Philosopher(x) → Thinker(x)) "All philosophers are thinkers"

∀x (Thinker(x) → Curious(x)) "All thinkers are curious"

Philosopher(socrates) "Socrates is a philosopher"

Theorem: Curious(socrates)

Step 1: Negate theorem → ¬Curious(socrates)

Step 2: CNF clauses:

C1: {¬Philosopher(x), Thinker(x)}

C2: {¬Thinker(x), Curious(x)}

C3: {Philosopher(socrates)}

C4: {¬Curious(socrates)} ← negated theorem

Step 3: Resolution

Resolve C2 + C4 (unify x=socrates):

C5: {¬Thinker(socrates)}

Resolve C1 + C5 (unify x=socrates):

C6: {¬Philosopher(socrates)}

Resolve C3 + C6

C7: □ (empty clause!)

Step 4: Contradiction! → Theorem PROVED ✓

Proof Search Strategies

Forward Chaining (Bottom-Up)

Philosopher(socrates) + Rule1	Thinker(socrates)
Thinker(socrates) + Rule2	Curious(socrates) ✓
Pros	Systematic, complete
Cons	May derive irrelevant facts (unfocused)

Backward Chaining (Top-Down)

Goal	Curious(socrates)
Need	Thinker(socrates) [from Rule2]
Need	Philosopher(socrates) [from Rule1]
Pros	Focused, efficient for specific goals
Cons	May loop without proper control

Iterative Deepening

Example

Combine depth-first efficiency with breadth-first completeness: Try proofs of length 1, then 2, then 3, ... First complete proof found is shortest Used in Prover9, E theorem prover

Important Theoretical Results

Completeness Theorems

Example

Complexity Results

Propositional satisfiability	NP-complete (Cook's theorem)
First-order validity	Undecidable (Church-Turing)
Description logics (OWL)	Decidable fragments of FOL

Modern Theorem Provers

Prover	Logic	Method	Notable Achievement
E	FOL	Superposition	CADE competitions
Vampire	FOL	Resolution + Superposition	Most awards in CASC
Z3	SMT	DPLL(T)	Software verification
Isabelle/HOL	Higher-order	Interactive + auto tactics	Formal math
Lean	Dependent types	Type theory	Mathlib library
Coq	Constructive	Type theory	CompCert verified compiler

Applications of Theorem Proving

Hardware Verification

Prove CPU correctly implements instruction set

Intel uses formal verification after FDIV bug (1994)

Software Verification

Prove programs have no bugs (buffer overflows, null pointers)

seL4 microkernel: formally proved correct (8,700 lines)

Mathematics

Four-Color Theorem (1976): Computer-assisted proof

Kepler Conjecture (2014): Formally verified in Lean

AI Planning

Prove plan achieves goal from initial state

Each plan step is a theorem about state transitions

Knowledge Base Reasoning

Prove queries from ontologies (OWL/DL reasoning)

Check consistency of knowledge bases

Theorem Proving vs. Model Checking

Theorem Proving

Works with formulas symbolically

Proves universal properties (for ALL inputs)

Incomplete for rich logics

Model Checking

Exhaustively checks all states

Proves properties for SPECIFIC system

Complete but limited by state space size (state explosion)

Often combined: model checking for finite systems,

theorem proving for parameterized/infinite systems

Interview Questions

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Theorem Proving - Automated Reasoning.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.

Search Terms

artificial-intelligence, artificial intelligence, artificial, intelligence, reasoning, and, inference, theorem

Continue learning this concept

PreviousResolution Method - Logical Inference NextUncertain Reasoning - Probabilistic AI