You are previewing Handbook of Practical Logic and Automated Reasoning.
O'Reilly logo
Handbook of Practical Logic and Automated Reasoning

Book Description

The sheer complexity of computer systems has meant that automated reasoning, i.e. the ability of computers to perform logical inference, has become a vital component of program construction and of programming language design. This book meets the demand for a self-contained and broad-based account of the concepts, the machinery and the use of automated reasoning. The mathematical logic foundations are described in conjunction with practical application, all with the minimum of prerequisites. The approach is constructive, concrete and algorithmic: a key feature is that methods are described with reference to actual implementations (for which code is supplied) that readers can use, modify and experiment with. This book is ideally suited for those seeking a one-stop source for the general area of automated reasoning. It can be used as a reference, or as a place to learn the fundamentals, either in conjunction with advanced courses or for self study.

Table of Contents

  1. Cover
  2. Title
  3. Copyright
  4. Contents
  5. Preface
  6. 1 Introduction
    1. 1.1 What is logical reasoning?
    2. 1.2 Calculemus!
    3. 1.3 Symbolism
    4. 1.4 Boole’s algebra of logic
    5. 1.5 Syntax and semantics
    6. 1.6 Symbolic computation and OCaml
    7. 1.7 Parsing
    8. 1.8 Prettyprinting
  7. 2 Propositional logic
    1. 2.1 The syntax of propositional logic
    2. 2.2 The semantics of propositional logic
    3. 2.3 Validity, satisfiability and tautology
    4. 2.4 The De Morgan laws, adequacy and duality
    5. 2.5 Simplification and negation normal form
    6. 2.6 Disjunctive and conjunctive normal forms
    7. 2.7 Applications of propositional logic
    8. 2.8 Definitional CNF
    9. 2.9 The Davis–Putnam procedure
    10. 2.10 Stålmarck’s method
    11. 2.11 Binary decision diagrams
    12. 2.12 Compactness
  8. 3 First-order logic
    1. 3.1 First-order logic and its implementation
    2. 3.2 Parsing and printing
    3. 3.3 The semantics of first-order logic
    4. 3.4 Syntax operations
    5. 3.5 Prenex normal form
    6. 3.6 Skolemization
    7. 3.7 Canonical models
    8. 3.8 Mechanizing Herbrand’s theorem
    9. 3.9 Unification
    10. 3.10 Tableaux
    11. 3.11 Resolution
    12. 3.12 Subsumption and replacement
    13. 3.13 Refinements of resolution
    14. 3.14 Horn clauses and Prolog
    15. 3.15 Model elimination
    16. 3.16 More first-order metatheorems
  9. 4 Equality
    1. 4.1 Equality axioms
    2. 4.2 Categoricity and elementary equivalence
    3. 4.3 Equational logic and completeness theorems
    4. 4.4 Congruence closure
    5. 4.5 Rewriting
    6. 4.6 Termination orderings
    7. 4.7 Knuth–Bendix completion
    8. 4.8 Equality elimination
    9. 4.9 Paramodulation
  10. 5 Decidable problems
    1. 5.1 The decision problem
    2. 5.2 The AE fragment
    3. 5.3 Miniscoping and the monadic fragment
    4. 5.4 Syllogisms
    5. 5.5 The finite model property
    6. 5.6 Quantifier elimination
    7. 5.7 Presburger arithmetic
    8. 5.8 The complex numbers
    9. 5.9 The real numbers
    10. 5.10 Rings, ideals and word problems
    11. 5.11 Gröbner bases
    12. 5.12 Geometric theorem proving
    13. 5.13 Combining decision procedures
  11. 6 Interactive theorem proving
    1. 6.1 Human-oriented methods
    2. 6.2 Interactive provers and proof checkers
    3. 6.3 Proof systems for first-order logic
    4. 6.4 LCF implementation of first-order logic
    5. 6.5 Propositional derived rules
    6. 6.6 Proving tautologies by inference
    7. 6.7 First-order derived rules
    8. 6.8 First-order proof by inference
    9. 6.9 Interactive proof styles
  12. 7 Limitations
    1. 7.1 Hilbert’s programme
    2. 7.2 Tarski’s theorem on the undefinability of truth
    3. 7.3 Incompleteness of axiom systems
    4. 7.4 Go¨del’s incompleteness theorem
    5. 7.5 Definability and decidability
    6. 7.6 Church’s theorem
    7. 7.7 Further limitative results
    8. 7.8 Retrospective: the nature of logic
  13. Appendix 1 Mathematical background
  14. Appendix 2 OCaml made light of
  15. Appendix 3 Parsing and printing of formulas
  16. References
  17. Index