A Computational Logic

¿PrefaceI. Introduction A. Motivation B. Our Formal Theory C. Proof Techniques D. Examples E. Our Mechanical Theorem-Prover F. Artificial Intelligence or Logic? G. OrganizationII. A Sketch of the Theory and Two Simple Examples A. An Informal Sketch of the Theory B. A Simple Inductive Proof C. A More Difficult Problem D. A More Difficult Proof E. Summary F. NotesIII. A Precise Definition of the Theory A. Syntax B. The Theory of If and Equal C. Well-Founded Relations D. Induction E. Shells F. Natural Numbers G. Literal Atoms H. Ordered Pairs I. Definitions J. Lexicographic Relations K. Lessp and Count L. ConclusionIV. The Correctness of a Tautology-Checker A. Informal Development B. Formal Specification of the Problem C. The Former Definition of Tautology.Checker D. The Mechanical Proofs E. Summary F. NotesV. An Overview of How We Prove Theorems A. The Role of the User B. Clausal Representation of Conjectures C. The Organization of Our Heuristics D. The Organization of Our PresentationVI. Using Type Information to Simplify Formulas A. Type Sets B. Assuming Expressions True or False C. Computing Type Sets D. Type Prescriptions E. Summary F. NotesVII. Using Axioms and Lemmas as Rewrite Rules A. Directed Equalities B. Infinite Looping C. More General Rewrite Rules D. An Example of Using Rewrite Rules E. Infinite Backwards Chaining F. Free Variables in HypothesesVIII. Using Definitions A. Nonrecursive Functions B. Computing Values C. Diving in to SeeIX. Rewriting Terms and Simplifying Clauses A. Rewriting Terms B. Simplifying Clauses C. The Reverse Example D. Simplification in the Reverse ExampleX. Eliminating Destructors A. Trading Bad Terms for Good Terms B. The Form of Elimination Lemmas C. The Precise Use of Elimination Lemmas D. A Nontrivial Example E. Multiple Destructors and Infinite Looping F. When Elimination Is Risky G. Destructor Elimination in the Reverse ExampleXI. Using Equalities A. Using and Throwing Away Equalities B. Cross-Fertilization C. A Simple Example of Cross-Fertilization D. The Precise Use of Equalities E. Cross-Fertilization in the Reverse ExampleXII. Generalization A. A Simple Generalization Heuristic B. Restricting Generalizations C. Examples of Generalizations D. The Precise Statement of the Generalization Heuristic E. Generalization in the Reverse ExampleXIII. Eliminating Irrelevance A. Two Simple Checks for Irrelevance B. The Reason for Eliminating Isolated Hypotheses C. Elimination of Irrelevance in the Reverse ExampleXIV. Induction and the Analysis of Recursive Definitions A. Satisfying the Principle of Definition B. Induction Schemes Suggested by Recursive Functions C. The Details of the Definition-Time Analysis D. Recursion in the Reverse ExampleXV. Formulating an Induction Scheme for a Conjecture A. Collecting the Induction Candidates B. The Heuristic Manipulation of Induction Schemes C. Examples of Induction D. The Entire Reverse ExampleXVI. Illustrations of Our Techniques via Elementary Number Theory A. Plus.Right.Id B. Commutativity2.of.Plus C. Commutativity.of.Plus D. Associativity.of.Plus E. Times F. Times.Zero G. Times.Add1 H. Associativity.of.Times I. Difference J. Recursion.by.Difference K. Remainder L. Quotient M. Remainder.Quotient.ElimXVII. The Correctness of a Simple Optimizing Expression Compiler A. Informal Development B. Formal Specification of the Problem C. Formal Definition of the Compiler D. The Mechanical Proof of Correctness E. NotesXVIII. The Correctness of a Fast String Searching Algorithm A. Informal Development B. Formal Specification of the Problem C.