Three Views of Logic: Mathematics, Philosophy, and Computer Science

Description

Demonstrating the different roles that logic plays in the disciplines of computer science, mathematics, and philosophy, this concise undergraduate textbook covers select topics from three different areas of logic: proof theory, computability theory, and nonclassical logic. The book balances accessibility, breadth, and rigor, and is designed so that its materials will fit into a single semester. Its distinctive presentation of traditional logic material will enhance readers' capabilities and mathematical maturity. The proof theory portion presents classical propositional logic and first-order logic using a computer-oriented (resolution) formal system. Linear resolution and its connection to the programming language Prolog are also treated. The computability component offers a machine model and mathematical model for computation, proves the equivalence of the two approaches, and includes famous decision problems unsolvable by an algorithm. The section on nonclassical logic discusses the shortcomings of classical logic in its treatment of implication and an alternate approach that improves upon it: Anderson and Belnap's relevance logic. Applications are included in each section. The material on a four-valued semantics for relevance logic is presented in textbook form for the first time. Aimed at upper-level undergraduates of moderate analytical background, Three Views of Logic will be useful in a variety of classroom settings. * Gives an exceptionally broad view of logic * Treats traditional logic in a modern format * Presents relevance logic with applications * Provides an ideal text for a variety of one-semester upper-level undergraduate courses Cover Title Copyright Contents Preface Acknowledgments PART 1. Proof Theory 1 Propositional Logic 1.1 Propositional Logic Semantics 1.2 Syntax: Deductive Logics 1.3 The Resolution Formal Logic 1.4 Handling Arbitrary Propositional Wffs 2 Predicate Logic 2.1 First-Order Semantics 2.2 Resolution for the Predicate Calculus 2.2.1 Substitution 2.2.2 The Formal System for Predicate Logic 2.2.3 Handling Arbitrary Predicate Wffs 3 An Application: Linear Resolution and Prolog 3.1 OSL-Resolution 3.2 Horn Logic 3.3 Input Resolution and Prolog Appendix A: The Induction Principle Appendix B: First-Order Valuation Appendix C: A Commentary on Prolog References PART 2. Computability Theory 4 Overview of Computability 4.1 Decision Problems and Algorithms 4.2 Three Informal Concepts 5 A Machine Model of Computability 5.1 Register Machines and RM-Computable Functions 5.2 Operations with RM-Computable Functions; Church-Turing Thesis; LRM-Computable Functions 5.3 RM-Decidable and RM-Semi-Decidable Relations; the Halting Problem 5.4 Unsolvability of Hilbert’s Decision Problem and Thue’s Word Problem 6 A Mathematical Model of Computability 6.1 Recursive Functions and the Church-Turing Thesis 6.2 Recursive Relations and RE Relations 6.3 Primitive Recursive Functions and Relations; Coding 6.4 Kleene Computation Relation Tn(e, a1, . . . , an, c) 6.5 Partial Recursive Functions; Enumeration Theorems 6.6 Computability and the Incompleteness Theorem List of Symbols References PART 3. Philosophical Logic 7 Non-Classical Logics 7.1 Alternatives to Classical Logic vs. Extensions of Classical Logic 7.2 From Classical Logic to Relevance Logic 7.2.1 The (So-Called) “Paradoxes of Implication” 7.2.2 Material Implication and Truth Functional Connectives 7.2.3 Implication and Relevance 7.2.4 Revisiting Classical Propositional Calculus: What to Save,What to Change, What to Add? 8 Natural Deduction: Classical and Non-Classical 8.1 Fitch’s Natural Deduction System for Classical Propositional Logic 8.2 Revisiting Fitch’s Rules of Natural Deduction to Better Formalize the Notion of Entailment—Necessity 8.3 Revisiting Fitch’s Rules of Natural Deduction to Better Formalize the Notion of Entailment—Relevance 8.4 The Rules of System FE (Fitch-Style Formulation of the Logic of Entailment) 8.5 The Connective “Or,” Material Implication, and the Disjunctive Syllogism 9 Semantics for Relevance Logic: A Useful Four-Valued Logic 9.1 Interpretations, Valuations, and Many Valued Logics 9.2 Contexts in Which This Four-Valued Logic Is Useful 9.3 The Artificial Reasoner’s (Computer’s) “State of Knowledge” 9.4 Negation in This Four-Valued Logic 9.5 Lattices: A Brief Tutorial 9.6 Finite Approximation Lattices and Scott’s Thesis 9.7 Applying Scott’s Thesis to Negation, Conjunction, and Disjunction 9.8 The Logical Lattice L4 9.9 Intuitive Descriptions of the Four-Valued Logic Semantics 9.10 Inferences and Valid Entailments 10 Some Concluding Remarks on the Logic of Entailment References Index