In writing this book, our goal was to produce a text suitable for a first course in mathematical logic more attuned than the traditional textbooks to the recent dramatic growth in the applications of logic to computer science. Thus our choice of topics has been heavily influenced by such applications. Of course, we cover the basic traditional topics - syntax, semantics, soundness, completeness and compactness - as well as a few more advanced results such as the theorems of Skolem-Lowenheim and Herbrand. Much of our book, however, deals with other less traditional topics. Resolution theorem proving plays a major role in our treatment of logic, especially in its application to Logic Programming and PROLOG. We deal extensively with the mathematical foundations of all three of these subjects. In addition, we include two chapters on nonclassical logic- modal and intuitionistic - that are becoming increasingly important in computer science. We develop the basic material on the syntax and se­ mantics (via Kripke frames) for each of these logics. In both cases, our approach to formal proofs, soundness and completeness uses modifications of the same tableau method introduced for classical logic. We indicate how it can easily be adapted to various other special types of modal log­ ics. A number of more advanced topics (including nonmonotonic logic) are also briefly introduced both in the nonclassical logic chapters and in the material on Logic Programming and PROLOG.

Inhalt

I: Prepositional Logic.- I.1 Orders and Trees.- I.2 Propositions, Connectives and Truth Tables.- I.3 Truth Assignments and Valuations.- I.4 Tableau Proofs in Propositional Calculus.- I.5 Soundness and Completeness of Tableau Proofs.- I.6 Deductions from Premises and Compactness.- I.7* An Axiomatic Approach.- I.8 Resolution.- I.9 Refining Resolution.- I.10 Linear Resolution, Horn Clauses and PROLOG.- II: Predicate Logic.- II. 1 Predicates and Quantifiers.- II.2 The Language: Terms and Formulas.- II.3 Formation Trees, Structures and Lists.- II.4 Semantics: Meaning and Truth.- II.5 Interpretation of prolog Programs.- II.6 Proofs: Complete Systematic Tableaux.- II.7 Soundness and Completeness of Tableau Proofs.- II.8* An Axiomatic Approach.- II.9 Prenex Normal Form and Skolemization.- II.10 Herbrand's Theorem.- II.11 Unification.- II.12 The Unification Algorithm.- II.13 Resolution.- II.14 Refining Resolution: Linear Resolution.- III: PROLOG.- III.1 SLD-Resolution.- III.2 Implementations: Searching and Backtracking.- III.3 Controlling the Implementation: Cut.- III.4 Termination Conditions for PROLOG Programs.- III.5 Equality.- III.6 Negation as Failure.- III.7 Negation and Nonmonotonic Logic.- III.8 Computability and Undecidability.- IV: Modal Logic.- IV. 1 Possibility and Necessity; Knowledge or Belief.- IV.2 Frames and Forcing.- IV.3 Modal Tableaux.- IV.4 Soundness and Completeness.- IV.5 Modal Axioms and Special Accessibility Relations.- IV.6* An Axiomatic Approach.- V: Intuitionistic Logic.- V.1 Intuitionism and Constructivism.- V.2 Frames and Forcing.- V.3 Intuitionistic Tableaux.- V.4 Soundness and Completeness.- V.5 Decidability and Undecidability.- V.6 A Comparative Guide.- Appendix A: An Historical Overview.- A.1 Calculus.- A.2 Logic.- A.3 Leibniz's Dream.- A.4 Nineteenth Century Logic.- A.5 Nineteenth Century Foundations of Mathematics.- A.6 Twentieth Century Foundations of Mathematics.- A.7 Early Twentieth Century Logic.- A.8 Deduction and Computation.- A.9 Recent Automation of Logic and PROLOG.- A.10 The Future.- Appendix B: A Genealogical Database.- 1. History of Mathematics.- 2. History of Logic.- 3. Mathematical Logic.- 4. Intuitionistic, Modal, and Temporal Logics.- 5. Logic and Computation.- Index of Symbols.- Index of Terms.