← Retour

An introduction to Mathematical Logic & Computability

par: S. DJEDDAI & S.HAMADOUCHE & M.MEZGHICHE
Disponible
Pages 144
Dimensions 16*23,5
Publication 2025-10-03
Éditeur —
Papier : 950.00 DA Numérique: 475.00 DA

Logic takes part of our everyday lives, we use it every day both personally and professionally. We use logic to establish observations, to define concepts, or to formalize theories. We use logic to draw conclusions from these pieces of information. We are using logical proofs to convince others of these conclusions. In computer science, mathematical logic plays an important role. It represents the main stream of the mathematical foundations of computing. Mathematical logic is essential for the practice of computer science and its applications. It constitutes the foundations of programming languages, databases, artificial intelligence, and software engineering. Mainly, it allows one to formalize the notion of demonstration. In Artificial intelligence, the principles of mathematical logic are applied in auto- mated reasoning systems to deduce conclusions starting from premisses. In software engineering, it is used mainly within the development cycle of critical software. This kind of software does not accept errors. It is used to prove mathematical theorems and validate technical representations to ensure zero failure. Therefore, it provides a development framework that enables the production of robust, efficient, and reliable software. The purpose of mathematical logic is to study mathematics as a language. When you want to learn a particular language, you just need to determine a list of particu- larities that allow you to differentiate it from other languages. These particularities are represented by the syntax and semantics of the language. In one hand syntax is linked to the form of the language, it constitutes the rules allowing you to define how you write correctly in this language. On other hand semantics, on the other hand, determines the meaning of combinations of words written in this language. In this book, we introduce the basic concepts of mathematical logic and com- putability. In the first part, we present an introduction to propositional calculus and predicate calculus. For each of them, we will study syntax as well as semantics in order to explain the notion of consistency and formal systems. It shows how some properties of these two calculi are exploited to introduce decision procedures for the validity of formulas. The second part presents the recursive functions, Turing machines, and λ-calculus. These theories give a rigorous definition to the notion of effective calculus that allows us to understand the notion of universal calculus and algorithm. The scope of the applications of mathematical logic in computer science suggests that students as well as teachers in computer science should consult works on logic. This course can serve as a first step becoming familiar with this discipline.

Afficher la table des matières
Foreword 5
1 Mathematical Reminders 7
1.1 Natural Numbers – 7
1.1.1 Mathematical Induction – 8
1.2 Proof by Contradiction – 9
1.3 Proof by Contraposition – 10
Exercises – 11
2 Propositional Logic 13
2.1 Notion of Proposition 13
2.2 Syntax of Propositional Logic
2.2.1 Alphabet – 14
2.2.2 Connectives – 14
2.2.3 Convention – 14
2.2.4 Well-formed Formulas – 15
2.3 Semantic Study of Propositional Logic
2.3.1 Interpretation – 16
2.3.2 Truth Tables – 17
2.3.3 Model – 18
2.3.4 Satisfiability and Validity – 19
2.3.5 Logical Consequence – 20
2.3.6 Substitution and Replacement Theorem – 21
2.4 Complete Set of Connectives 23
2.5 Conjunctive Normal Form
2.5.1 Conjunctive Normal Form Algorithm – 25
Exercises – 30
3 Formal Propositional Logic 37
3.1 Natural Deduction System
3.1.1 Syntax – 38
3.1.2 Rules of Inference – 39
3.2 Soundness and Completeness of Natural Deduction
3.2.1 Soundness – 40
3.2.2 Completeness – 42
3.3 Sequent Calculus 43
3.4 Resolution
3.4.1 The Davis–Putnam Method – 45
3.4.2 Refutation – 46
Exercises – 47
4 First-Order Predicate Calculus 51
4.1 Predicate Calculus Language – 52
4.2 Free Variables and Bound Variables – 53
4.3 Interpretations and Models – 54
4.4 Satisfaction and Validity – 56
4.5 Prenex Normal Form – 58
4.6 Resolution
4.6.1 Clausal Forms and Skolemization – 59
4.6.2 Herbrand’s Procedure – 61
4.6.3 Resolution Method – 63
4.6.4 Unification – 63
4.7 Formalized Predicate Calculus – 67
Exercises – 72
5 Computability 77
5.1 Introduction to Computability
5.1.1 From Algorithms to Computability – 78
5.1.2 Computability Theory – 79
5.1.3 Computable Functions – 79
5.1.4 Non-computable Functions – 79
5.1.5 Decidability and Computability – 80
5.1.6 Computability Formalisms – 80
5.2 Recursive Functions
5.2.1 Basic Functions – 81
5.2.2 Operations – 82
5.2.3 Definitions – 83
5.2.4 Example – 83
5.2.5 Recursive Predicates – 84
Exercises – 85
5.3 Turing Machine
5.3.1 Informal Definition – 86
5.3.2 Formal Definition – 87
5.3.3 Convention – 88
5.3.4 Turing Machines and Computable Functions – 88
5.3.5 Elementary Machines – 89
5.3.6 Composition of Turing Machines – 90
5.3.7 Church Thesis – 91
Exercises – 92
5.4 Lambda Calculus
5.4.1 Syntax of λ-Calculus – 93
5.4.2 Free and Bound Variables – 93
5.4.3 α-congruent Terms – 94
5.4.4 Substitution – 94
5.4.5 β-Reduction – 95
5.4.6 Representation of Recursive Functions – 96
5.4.7 Computability and λ-Calculus – 97
5.4.8 Procedure = λ-terms – 98
Exercises – 100
6 Answers to Selected Exercises
6.1 Propositional Logic – 103
6.2 Formal Propositional Logic – 115
6.3 Predicate Calculus – 120
6.4 Computability – 126
6.5 λ-Calculus – 130
Acheter

Livres dans la même catégorie

Avis des lecteurs

Aucun avis pour le moment.