Three Views of Logic: Mathematics, Philosophy, and Computer Science pdf epub mobi txt 电子书 下载 2025

想要找书就要到 小美书屋

立刻按 ctrl+D收藏本页

你会得到大惊喜!!

This book is based on an interdisciplinary course on logic offered to upper-level undergraduates at Duke University over a period of more than ten years. Why an interdisciplinary course on logic? Although logic has been a discipline of study in philosophy since ancient times, in recent decades it has played an important role in other disciplines as well. For example, logic is at the core of two programming languages, is used in program verification, has enriched philosophy (and computer science) with non-classical logics that can deal constructively with contradictions, and has shaken the foundations of mathematics with insight into non-computable functions and non-provability. Several of these ideas are treated in this book.

This book addresses select topics drawn from three different areas of logic: proof theory, computability theory, and philosophical logic. A common thread throughout is the application of logic to computers and computation.

Part 1 on Proof Theory introduces a deductive system (resolution logic) that comes from an area of research known as automated deduc- tion.

Part 2 on Computability Theory explores the limits of computation using an abstract model of computers called register machines.

Part 3 on Philosophical Logic presents a certain non-classical logic (relevance logic) and a semantics for it that is useful for automated reasoning systems that must deal with the possibility of inconsistent information.

The three areas from which the special topics are drawn — proof theory, computability theory, and philosophical logic — exhibit the different roles that logic plays in three different disciplines: computer science, mathematics, and philosophy. The three parts of the book were written by a computer scientist, a mathematician, and a philosopher, respectively, and each part was reviewed by the other two authors for accessibility to students in their fields. The three parts of the book are roughly of equal length. The second part, on computability theory, is largely independent of the first, but the third part, on philosophical logic, is best presented after the first two parts.

Preface
Acknowledgments
PART 1. Proof Theory by DONALD W. LOVELAND
1 Propositional Logic
1.1 PropositionalLogicSemantics
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 91
PART 2. Computability Theory by RICHARD E. HODEL
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 219 References
PART 3. Philosophical Logic by S. G. STERRETT
7 Non-Classical Logics
7.1 AlternativestoClassicalLogicvs.Extensionsof
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
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 InferencesandValidEntailments
Some Concluding Remarks on the Logic of Entailment
References
Index
· · · · · · (收起)