INFO3208 : Logique
Introduction to logic
- Responsable(s) :
-
- Eric Thierry
- Enseignant(s) :
-
- Natacha Portier
Niveau
L3 / 1e année
Discipline
Informatique
Public externe (ouverts aux auditeurs de cours)
Informations générales sur le cours : INFO3208
Cours de Logique Mathématique, partant des bases de la logique jusqu'aux résultats majeurs du tournant des années 30 (dont les théorèmes d'incomplétude de Gödel).
Ce qui est traité :
- Calcul propositionnel et logique du premier ordre (calcul propositionnel et son théorème de compacité, syntaxe de la logique du premier ordre et preuves en déduction naturelle, sémantique de la logique du premier ordre, théorème de complétude de Gödel, théorème de compacité.)
- L'arithmétique de Peano et les théorèmes d'incomplétude de Gödel
- La théorie des ensembles (théorie naïve des ensembles et définition des ordinaux, axiomes de Zermelo-Fraenkel, axiomes du choix)
- Applications selon le temps qu'il reste (l'élimination des quantificateurs dans les corps réels clos, l'élimination des quantificateurs dans les corps algébriquement clos, le théorème d'Ax-Grothendieck)
Ce qui n'est pas traité :
- La calculabilité et la décidabilité, qui sont traités dans le cours FDI du premier semestre
- Les aspects avancés en lien avec la théorie de la programmation, qui sont traités dans le cours de théorie de la programmation
Prérequis : un niveau L2 en mathématiques.
Chaque semaine, un cours magistral de 2h et un TD de 2h.
Le calendrier suivi est celui du département d'informatique.
Contrôle des connaissances : un ou plusieurs devoirs à la maison, un partiel et un examen. La moyenne des DM et du partiel forma la note de contrôle continu. La note finale est la moyenne des notes de contrôle continu et de l'examen.
Tous les documents sont interdits lors du partiel et de l'examen, qui peuvent comporter des questions de cours.
Bibliographie pour le cours :
- Logique mathématique, René Cori et Daniel Lascar, deux tomes chez Dunod (ou la première édition chez Axiomes). Cours et exercices. Dans le premier tome : Calcul propositionnel, Algèbre de Boole, Calcul des prédicats, Théorèmes de complétude. Second tome : Récursivité (inclus les machines de Turing) , Formalisation de l'arithmétique, théorèmes de Gödel, théorie des ensembles, un peu de théorie des modèles.
- Introduction à la logique, Théorie de la démonstration, René David, Karim Nour et Christophe Raffalli, Dunod
- cours de Zoe Chatzidakis (sur sa page web)
Bibliographie informelle, pour ceux qui veulent suivre le cours et ceux qui ne le veulent pas :
- Logicomix : an epic search for the truth (roman graphique disponible en français et en anglais à la bibliothèque)
- et pourtant... ils ne remplissent pas N ! Claude Lobry (à la bib)
- Le théorème de Gödel, point sciences, Ernest Nagel/James R. Newman, Kurt Gödel/Jean-Yves Girard