← Retour

Logique Mathématique et Calculabilité

par: M Mezghiche
Disponible
Pages 128
Dimensions 16*23,5
Publication 2021-09-03
Éditeur —
Papier : 750.00 DA Numérique: 375.00 DA

Ce cours d’introduction à la logique mathématique et de calcula- bilité est conforme au programme officiel du module de logique mathé- matique enseigné en deuxième année d’université aux élèves ingénieur en informatique et aux étudiants des licences de mathématique et d’infor- matique du systéme LMD. Ce livre présente une introduction au calcul propositionnel et au cal- cul des prédicats dont l’objectif est d’expliquer la notion de consistance, de système formel et la notion de sémantique. Il montre aussi comment certaines propriétés des ces deux calculs sont exploitées pour introduire des procédures de déçision de la validité des formules. En plus de cette introduction à la logique ce livre contient une introduction succincte à la notion de calculabilité très utile aux étudiants de Master informatique. Des exercices sont proposés dont certains sont corrigés. La logique mathématique a été, au départ, développée dans le but d’assurer aux mathématiques un fondement plus solide c’est à dire exempt de toute inconsistance, joue aujourd’hui un rôle qui dépasse de beaucoup les objectifs prévus initialement. Parmi ses nombreux domaines d’appli- cations, c’est l’informatique qui, aujourd’hui, retient le plus d’intérêt. Citons par exemple les domaines d’informatique où la logique mathé- matique est intensement sollicitée : la validation et certification de pro- grammes, méthodes formelles, extraction automatique de programmes et démonstration automatique, .... L’étendue des domaines d’application de la logique mathématique incite les étudiants en mathématiques, enseignants et informaticiens à consulter des ouvrages de logique. Ce cours peut constituer une première étape pour se familiariser avec cette discipline.

Afficher la table des matières
1 Rappels mathématiques
Les entiers naturels – 2
Induction mathématique – 3
Démonstration par l’absurde – 5
Démonstration par contradiction – 6
Travaux dirigés – 8
2 Calcul propositionnel
2.1 Préliminaires – 10
2.1.1 Définition des connecteurs →, ¬, ∧ et ∨ – 11
2.2 Syntaxe du langage de la logique propositionnelle – 14
2.3 Sémantique de la logique propositionnelle – 14
2.4 Théorème de remplacement – 16
2.5 Forme normale conjonctive – 19
2.6 Ensemble complet de connecteurs – 21
2.7 Travaux dirigés – 25
3 Calcul propositionnel formel
3.1 Système déductif pour le calcul propositionnel – 28
3.2 Adéquation et complétude du CPF – 34
3.3 Méthode de Davis–Putnam – 38
3.4 Calcul des séquents – 41
3.5 Travaux dirigés – 45
4 Calcul des prédicats du premier ordre
4.1 Langage du calcul des prédicats – 48
4.2 Variables libres et variables liées – 49
4.3 Interprétation – 50
4.4 Satisfaction, valeurs de vérité – 51
4.5 Calcul des prédicats formalisé – 53
4.6 Forme normale prénexe – 62
4.7 Solémisation et résolution – 64
4.7.1 Formes clausales, skolémisation – 65
4.7.2 Procédure de Herbrand – 68
4.7.3 Méthode de résolution, unification – 70
5 Notions de calculabilité
5.1 Introduction – 82
5.2 Notion de calcul effectif et d’algorithme – 82
5.3 Fonctions récursives – 83
5.4 Machines de Turing – 89
5.4.1 Les machines de Turing – 89
5.4.2 Concaténation de machines – 93
5.5 Travaux dirigés – 97
6 λ-Calcul et logique combinatoire
6.1 Le lambda-calcul – 100
6.1.1 λβ-réduction, λβ-conversion – 100
6.1.2 βη-réduction – 102
6.2 La logique combinatoire – 103
6.2.1 Réduction faible, égalité faible – 103
6.2.2 Abstraction – 104
6.2.3 Cβη-réduction et extensionnalité – 105
6.3 Représentation des fonctions récursives – 106
6.4 Travaux dirigés – 109
Annexe
A.1 Correction des exercices du chapitre 1 – 111
A.2 Correction des exercices du chapitre 2 – 112
A.3 Correction des exercices du chapitre 3 – 113
A.4 Correction des exercices du chapitre 4 – 115
A.5 Correction des exercices du chapitre 5 – 117
A.6 Correction des exercices du chapitre 6 – 118
Acheter

Autres livres de : M Mezghiche

Livres dans la même catégorie

Avis des lecteurs

Aucun avis pour le moment.