Ensimag Rubrique Formation 2022

Logique pour l'informatique - 3MM1LPI

  • Volumes horaires

    • CM 18.0
    • Projet -
    • TD 18.0
    • Stage -
    • TP -
    • DS -

    Crédits ECTS

    Crédits ECTS 3.0

Objectif(s)

La logique joue un rôle fondamental en informatique dans la spécification, construction et vérification des programmes, comme langage de programmation, dans son lien étroit avec la calculabilité. Elle joue aussi un rôle clé en intelligence artificielle, dans les bases de données, en probabilités, etc. L’objectif du cours est de donner les bases pour son utilisation dans les différents domaines.

Responsable(s)

Nils GESBERT

Contenu(s)

  • Première période : logique propositionnelle.
    1. Syntaxe des formules, symboles propositionnels, connecteurs, interprétations, tables de vérité.
    2. Notions de modèle, satisfaisabilité, validité d’une formule ; relation de conséquence logique.
    3. Formes normales.
    4. Systèmes formels. Déduction naturelle, système de Fitch
    5. Le problème SAT ; algorithme DPLL.
  • Deuxième période : logique du premier ordre.
    1. Prédicats, fonctions, variables, quantificateurs.
    2. Interprétations, valuations, modèles, satisfaisabilité, validité, conséquence.
    3. Variables libres et liées, renommage ; formes normales.
    4. Système de Fitch au premier ordre.
    5. Théories du premier ordre.
    6. Propriétés des relations binaires : (anti)symétrie, (ir)réflexivité, transitivité
    7. Égalité
    8. Notions d’arithmétique de Peano et idée du théorème d’incomplétude de Gödel
    • Ce cours est donné en Période(s) Académique(s) 1 et 2 **

Prérequis

Néant

Contrôle des connaissances

Evaluation : Examen Ecrit (2h)

Rattrapage : Examen oral (exposé, soutenance, etc..) (40 min)

Session 1 :

  • Période 1
    - E1 = examen écrit 2h, tous documents autorisés, pas de matériel
  • Période 2
    - E2 = examen écrit 2h, tous documents autorisés, pas de matériel
  • N1 = max(E1, (E1 + E2)/2)

Session 2 :

  • ET2 = oral de 40 min, tous documents autorisés, pas de matériel
  • N2 = ET2

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Alternance - Alternance 1ere annee
cf. l'emploi du temps 2025/2026

Informations complémentaires

Code de l'enseignement : 3MM1LPI
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

  • Equipe Bases théoriques de l'informatique

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

Polycopié du cours, contenant les énoncés de tous les exercices à faire en TD ainsi que leurs corrigés
Course notes containing the solutions to all proposed problems.