• Connexion

en fr

Cours : Logique (S2)

Objectifs : La logique est au fondement à la fois des mathématiques et de l'informatique. Ce cours étudie des aspects de la logique relevant de ces deux disciplines, en abordant des thèmes fondamentaux et des thèmes plus avancés, énumerés ci-dessous. À l'issue du cours, les étudiants disposeront d'une solide formation de base en logique et seront capables d'appliquer des méthodes logiques en informatique.

Plan détaillé : Dans la première partie du cours, les thèmes fondamentaux suivants seront abordés :

• syntaxe et sémantique de la logique propositionnelle et du premier ordre ;
• théorèmes de complétude, de compacité et de Löwenheim-Skolem ;
• incomplétude de l'arithmétique et ses liens avec la théorie de la calculabilité ;
• calculs des séquents et théorie de la preuve : LJ et LK.

Dans la seconde partie du cours, un sous-ensemble (éventuellement strict) des thèmes plus avancés suivants sera abordé :

• logiques intuitionniste et modale, ainsi que leurs sémantiques basées sur les mondes et algébriques ;
• décidabilité de l'arithmétique de Presburger et théorème de Büchi sur la logique monadique du second ordre faible ;
• définissabilité, interpolation et jeux d'Ehrenfeucht-Fraïssé sur des structures (in)finies.

Ce cours préparera les étudiants notamment aux cours du M1 MPRI à l'ENS Paris-Saclay qui approfondissent des notions avancées en logique,

Références :

• Notes de cours.
• thèmes fondamentaux :
  • Heinz-Dieter Ebbinghaus, Jörg Flum et Wolfgang Thomas. Mathematical Logic. 3e éd. Springer Cham, 2021. doi : 10.1007/978-3-030-73839-6, Chapitres II à VI,
  • George S. Boolos et Richard C. Jeffrey. Computability and logic. 3e éd. Cambridge University Press, 1989. doi : 10.5555/70559, Chapitres 10 à 16.
• logique intuitionniste et modale :
  • Anne Troelstra et Dirk van Dalen. Constructivism in mathematics : an introduction. Elsevier Science, 1988, Chapitre 2.
  • P. Blackburn, M. de Rijke et Y. Venema. Modal Logic. Cambridge University Press, 2001, Chapitre 2.
• décidabilité :
  • Heinz-Dieter Ebbinghaus, Jörg Flum et Wolfgang Thomas. Mathematical Logic. 3e éd. Springer Cham, 2021. doi : 10.1007/978-3-030-73839-6, Chapitre 10.
  • Christoph Haase. « A Survival Guide to Presburger Arithmetic ». In : ACM SIGLOG News 5.3 (2018), p. 67-82.
  • Wolfgang Thomas. « Languages, Automata, and Logic ». In : Handbook of Formal Languages. T. 3. Springer Berlin, Heidelberg, 1996, p. 389-455. doi : 10.1007/978-3-642-59126-6_7.
• définissabilité, interpolation et jeux :
  • Heinz-Dieter Ebbinghaus, Jörg Flum et Wolfgang Thomas. Mathematical Logic. 3e éd. Springer Cham, 2021. doi : 10.1007/978-3-030-73839-6, Chapitre 3.