Mathematical logic through Python / Yannai A. Gonczarowski, Harvard University, Noam Nisan, Hebrew University of Jerusalem.

Format:

Book

Author/Creator:

Gonczarowski, Yannai A., 1981- author.

Nisan, Noam, author.

Language:

English

Subjects (All):

Logic, Symbolic and mathematical.

Python (Computer program language).

Physical Description:

1 online resource (xii, 271 pages) : digital, PDF file(s).

Edition:

1st ed.

Place of Publication:

Cambridge, United Kingdom ; New York, NY : Cambridge University Press, 2022.

Summary:

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.

Contents:

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.

Notes:

Title from publisher's bibliographic system (viewed on 01 Sep 2022).

ISBN:

1-108-95769-2

1-108-95446-4

OCLC:

1293917398