First-order logic and automated theorem proving
Author(s)
Bibliographic Information
First-order logic and automated theorem proving
(Graduate texts in computer science)
Springer-Verlag, c1996
2nd ed
- : pbk.
Available at 31 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
Note
Includes bibliographical references and index
Description and Table of Contents
- Volume
-
ISBN 9780387945934
Description
This graduate-level text presents fundamental concepts and results of classical logic in a rigorous mathematical style. Applications to automated theorem proving are considered and usable Prolog programs provided. It will serve both as a first text in formal logic and an introduction to automation issues for students in computer science or mathematics. The book treats propositional logic, first-order logic, and first-order logic with equality. In each case the initial presentation is semantic, to define the intended subjects independently of the choice of proof mechanism. Then many kinds of proof procedure are introduced. Results such as completeness, compactness, and interpolation are established, and theorem provers are implemented in Prolog. This new edition includes material on AE calculus, Herbrand's Theorem, Gentzen's Theorem, and related topics.
- Volume
-
: pbk. ISBN 9781461275152
Description
There are many kinds of books on formal logic. Some have philosophers as their intended audience, some mathematicians, some computer scien tists. Although there is a common core to all such books, they will be very different in emphasis, methods, and even appearance. This book is intended for computer scientists. But even this is not precise. Within computer science formal logic turns up in a number of areas, from pro gram verification to logic programming to artificial intelligence. This book is intended for computer scientists interested in automated theo rem proving in classical logic. To be more precise yet, it is essentially a theoretical treatment, not a how-to book, although how-to issues are not neglected. This does not mean, of course, that the book will be of no interest to philosophers or mathematicians. It does contain a thorough presentation of formal logic and many proof techniques, and as such it contains all the material one would expect to find in a course in formal logic covering completeness but, not incompleteness issues. The first item to be addressed is, What are we talking about and why are we interested in it? We are primarily talking about truth as used in mathematical discourse, and our interest in it is, or should be, self evident. Truth is a semantic concept, so we begin with models and their properties. These are used to define our subject.
Table of Contents
1 Background.- 2 Propositional Logic.- 2.1 Introduction.- 2.2 Propositional Logic-Syntax.- 2.3 Propositional Logic-Semantics.- 2.4 Boolean Valuations.- 2.5 The Replacement Theorem.- 2.6 Uniform Notation.- 2.7 Koenig's Lemma.- 2.8 Normal Forms.- 2.9 Normal Form Implementations.- 3 Semantic Tableaux and Resolution.- 3.1 Propositional Semantic Tableaux.- 3.2 Propositional Tableaux Implementations.- 3.3 Propositional Resolution.- 3.4 Soundness.- 3.5 Hintikka's Lemma.- 3.6 The Model Existence Theorem.- 3.7 Tableau and Resolution Completeness.- 3.8 Completeness With Restrictions.- 3.9 Propositional Consequence.- 4 Other Propositional Proof Procedures.- 4.1 Hilbert Systems.- 4.2 Natural Deduction.- 4.3 The Sequent Calculus.- 4.4 The Davis-Putnam Procedure.- 4.5 Computational Complexity.- 5 First-Order Logic.- 5.1 First-Order Logic-Syntax.- 5.2 Substitutions.- 5.3 First-Order Semantics.- 5.4 Herbrand Models.- 5.5 First-Order Uniform Notation.- 5.6 Hintikka's Lemma.- 5.7 Parameters.- 5.8 The Model Existence Theorem.- 5.9 Applications.- 5.10 Logical Consequence.- 6 First-Order Proof Procedures.- 6.1 First-Order Semantic Tableaux.- 6.2 First-Order Resolution.- 6.3 Soundness.- 6.4 Completeness.- 6.5 Hilbert Systems.- 6.6 Natural Deduction and Gentzen Sequents.- 7 Implementing Tableaux and Resolution.- 7.1 What Next.- 7.2 Unification.- 7.3 Unification Implemented.- 7.4 Free-Variable Semantic Tableaux.- 7.5 A Tableau Implementation.- 7.6 Free-Variable Resolution.- 7.7 Soundness.- 7.8 Free-Variable Tableau Completeness.- 7.9 Free-Variable Resolution Completeness.- 8 Further First-Order Features.- 8.1 Introduction.- 8.2 The Replacement Theorem.- 8.3 Skolemization.- 8.4 Prenex Form.- 8.5 The AE-Calculus.- 8.6 Herbrand's Theorem.- 8.7 Herbrand's Theorem, Constructively.- 8.8 Gentzen's Theorem.- 8.9 Cut Elimination.- 8.10 Do Cuts Shorten Proofs?.- 8.11 Craig's Interpolation Theorem.- 8.12 Craig's Interpolation Theorem-Constructively.- 8.13 Beth's Definability Theorem.- 8.14 Lyndon's Homomorphism Theorem.- 9 Equality.- 9.1 Introduction.- 9.2 Syntax and Semantics.- 9.3 The Equality Axioms.- 9.4 Hintikka's Lemma.- 9.5 The Model Existence Theorem.- 9.6 Consequences.- 9.7 Tableau and Resolution Systems.- 9.8 Alternate Tableau and Resolution Systems.- 9.9 A Free-Variable Tableau System With Equality.- 9.10 A Tableau Implementation With Equality.- 9.11 Paramodulation.- References.
by "Nielsen BookData"