Three Views of Logic

Preface ix Acknowledgments xiii PART 1. Proof Theory 1 Donald Loveland 1 Propositional Logic 3 1.1 Propositional Logic Semantics 5 1.2 Syntax: Deductive Logics 13 1.3 The Resolution Formal Logic 14 1.4 Handling Arbitrary Propositional Wffs 26 2 Predicate Logic 31 2.1 First-Order Semantics 32 2.2 Resolution for the Predicate Calculus 40 2.2.1 Substitution 41 2.2.2 The Formal System for Predicate Logic 45 2.2.3 Handling Arbitrary Predicate Wffs 54 3 An Application: Linear Resolution and Prolog 61 3.1 OSL-Resolution 62 3.2 Horn Logic 69 3.3 Input Resolution and Prolog 77 Appendix A: The Induction Principle 81 Appendix B: First-Order Valuation 82 Appendix C: A Commentary on Prolog 84 References 91 PART 2. Computability Theory 93 Richard E. Hodel 4 Overview of Computability 95 4.1 Decision Problems and Algorithms 95 4.2 Three Informal Concepts 107 5 A Machine Model of Computability 123 5.1 RegisterMachines and RM-Computable Functions 123 5.2 Operations with RM-Computable Functions; Church-Turing Thesis; LRM-Computable Functions 136 5.3 RM-Decidable and RM-Semi-Decidable Relations; the Halting Problem 144 5.4 Unsolvability of Hilbert's Decision Problem and Thue'sWord Problem 154 6 A Mathematical Model of Computability 165 6.1 Recursive Functions and the Church-Turing Thesis 165 6.2 Recursive Relations and RE Relations 175 6.3 Primitive Recursive Functions and Relations; Coding 187 6.4 Kleene Computation Relation Tn(e, a1, ... , an, c) 197 6.5 Partial Recursive Functions; Enumeration Theorems 203 6.6 Computability and the Incompleteness Theorem 216 List of Symbols 219 References 220 PART 3. Philosophical Logic 221 S. G. Sterrett 7 Non-Classical Logics 223 7.1 Alternatives to Classical Logic vs. Extensions of Classical Logic 223 7.2 From Classical Logic to Relevance Logic 228 7.2.1 The (So-Called) "Paradoxes of Implication" 228 7.2.2 Material Implication and Truth Functional Connectives 234 7.2.3 Implication and Relevance 238 7.2.4 Revisiting Classical Propositional

Donald W. Loveland is professor emeritus of computer science at Duke University. Richard E. Hodel is associate profesor emeritus of mathematics at Duke University. S.G.Sterrett is research associate in the Department of Philosophy at Carnegie Mellon University.