AccueilLicence généraleInformatiqueEnseignementsLogique

Licence InformatiqueUE Logique

Contenu

Cette unité d'enseignement a pour objectif de raisonner sur les formalismes logiques au cœur des mathématiques et de l'informatique. Des systèmes formels de déduction sont étudiés, tant pour aider à mieux prouver manuellement des théorèmes que pour comprendre comment automatiser les preuves.

  • Logique propositionnelle
    • Syntaxe, sémantique, formes normales
    • Modélisation SAT, algorithmes pour SAT
    • Etude d'un système de déduction (calcul des séquents ou déduction naturelle) : correction et complétude
    • Clause de Horn, résolution
    • Théorème de compacité
  • Logique du premier ordre
    • Syntaxe, sémantique, formes normales prénexes, skolémisation
    • Modélisation
    • Calcul des séquents (éventuellement sans coupure) : correction et complétude
    • Substitution, unification, résolution
    • Programmation logique
  • Ouverture vers d'autres formalismes logiques : logique du second ordre, logiques modales

Compétences visées

  • Utiliser les concepts fondamentaux de l'informatique (langages formels, logique, et graphes) pour la programmation et la modélisation.
  • Se servir aisément des bases de la logique pour valider ou réfuter un raisonnement.
  • Rédiger de manière synthétique et rigoureuse des preuves.
  • Traduire un problème simple en langage mathématique.
  • Reconnaître les concepts fondamentaux d'importantes théories mathématiques actuelles.
  • Apprécier la rigueur d'un raisonnement mathématique ou logique et en déceler les failles éventuelles.

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Bibliographie

  • Introduction à la logique, Théorie de la démonstration. René David, Karim Nour, Christophe Raffalli. Dunod, 2004.
  • Logique mathématique (tome 1). René Cori et Daniel Lascar. Dunod, 2003.
  • Logique, réduction, résolution. René Lalement. Masson, 1990.
  • Outils logiques pour l'intelligence artificielle. Jean-Paul Delahaye. Eyrolles, 1988.
  • Approche logique de l'intelligence artificielle. André Thayse. Eyrolles, 1988.

Pré-requis obligatoires

  • Langage mathématique
  • Algorithmique et structures discrètes

Volume des enseignements

  • Cours magistraux : 18 heures
  • Travaux dirigés : 32 heures
  • Travaux pratiques : 10 heures

Les formations qui utilisent cet enseignement