UID:
almafu_9960821766302883
Format:
1 online resource (xii, 271 pages) :
,
digital, PDF file(s).
Edition:
1st ed.
ISBN:
1-108-95769-2
,
1-108-95446-4
Content:
Using a unique pedagogical approach, this text introduces mathematical logic by guiding students in implementing the underlying logical concepts and mathematical proofs via Python programming. This approach, tailored to the unique intuitions and strengths of the ever-growing population of programming-savvy students, brings mathematical logic into the comfort zone of these students and provides clarity that can only be achieved by a deep hands-on understanding and the satisfaction of having created working code. While the approach is unique, the text follows the same set of topics typically covered in a one-semester undergraduate course, including propositional logic and first-order predicate logic, culminating in a proof of Gödel's completeness theorem. A sneak peek to Gödel's incompleteness theorem is also provided. The textbook is accompanied by an extensive collection of programming tasks, code skeletons, and unit tests. Familiarity with proofs and basic proficiency in Python is assumed.
Note:
Title from publisher's bibliographic system (viewed on 01 Sep 2022).
,
Cover -- Half-title -- Title page -- Copyright information -- Dedication -- Contents -- Preface -- 0 Introduction and Overview -- 0.1 Our Final Destination: Gödel's Completeness Theorem -- 0.2 Our Pedagogical Approach -- 0.3 How We Travel: Programs That Handle Logic -- 0.4 Our Roadmap -- Part I Propositional Logic -- 1 Propositional Logic Syntax -- 1.1 Propositional Formulas -- 1.2 Parsing -- 1.3 Infinite Sets of Formulas -- 1.A Optional Reading: Polish Notations -- 2 Propositional Logic Semantics -- 2.1 Detour: Semantics of Programming Languages -- 2.2 Models and Truth Values -- 2.3 Truth Tables -- 2.4 Tautologies, Contradictions, and Satisfiability -- 2.5 Synthesis of Formulas -- 2.A Optional Reading: Conjunctive Normal Form -- 2.B Optional Reading: Satisfiability and Search Problems -- 3 Logical Operators -- 3.1 More Operators -- 3.2 Substitutions -- 3.3 Complete Sets of Operators -- 3.4 Proving Incompleteness -- 4 Proof by Deduction -- 4.1 Inference Rules -- 4.2 Specializations of an Inference Rule -- 4.3 Deductive Proofs -- 4.4 Practice Proving -- 4.5 The Soundness Theorem -- 5 Working with Proofs -- 5.1 Using Lemmas -- 5.2 Modus Ponens -- 5.3 The Deduction Theorem -- 5.4 Proofs by Way of Contradiction -- 6 The Tautology Theorem and the Completeness of Propositional Logic -- 6.1 Our Axiomatic System -- 6.2 The Tautology Theorem -- 6.3 The Completeness Theorem for Finite Sets -- 6.4 The Compactness Theorem and the Completeness Theorem for Infinite Sets -- 6.A Optional Reading: Adding Additional Operators -- 6.B Optional Reading: Other Axiomatic Systems -- Part II Predicate Logic -- 7 Predicate Logic Syntax and Semantics -- 7.1 Syntax -- 7.2 Semantics -- 8 Getting Rid of Functions and Equality -- 8.1 Getting Rid of Functions -- 8.2 Getting Rid of Equality -- 9 Deductive Proofs of Predicate Logic Formulas -- 9.1 Example of a Proof.
,
9.2 Schemas -- 9.3 Proofs -- 9.4 Getting Rid of Tautology Lines -- 10 Working with Predicate Logic Proofs -- 10.1 Our Axiomatic System -- 10.2 Syllogisms -- 10.3 Some Mathematics -- 11 The Deduction Theorem and Prenex Normal Form -- 11.1 The Deduction Theorem -- 11.2 Prenex Normal Form -- 12 The Completeness Theorem -- 12.1 Deriving a Model or a Contradiction for a Closed Set -- 12.2 Closing a Set -- 12.3 The Completeness Theorem -- 12.4 The Compactness Theorem and the "Provability" Version of the Completeness Theorem -- 13 Sneak Peek at Mathematical Logic II: Gödel's Incompleteness Theorem -- 13.1 Complete and Incomplete Theories -- 13.2 Gödel Numbering -- 13.3 Undecidability of the Halting Problem -- 13.4 The Incompleteness Theorem -- Cheatsheet: Axioms and Axiomatic Inference Rules Used in This Book -- Index.
Additional Edition:
ISBN 9781108845076
Language:
English
URL:
https://doi.org/10.1017/9781108954464
Bookmarklink