Logique - 4MMLOG

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)

• Logique propositionnelle :
  + Syntaxe des formules, symboles propositionnels, connecteurs, interprétations, tables de vérité.
  + Notions de modèle, satisfaisabilité, validité d’une formule ; relation de conséquence logique.
  + Systèmes formels. Déduction naturelle, système de Fitch.
  + Équivalence logique, transformations de formules, formes normales.
  + Le problème SAT ; algorithme DPLL. Résolution propositionnelle.

• Logique du premier ordre :
  + Syntaxe : prédicats, fonctions, variables, quantificateurs.
  + Sémantique : interprétations, valuations, modèles, satisfaisabilité, validité, conséquence.
  + Substitutions ; système de Fitch en logique du premier ordre.
  + Formes clausales, unification, résolution en logique du premier ordre.
  + Formes de Skolem, complétude de la résolution, semi-décidabilité de la logique du premier ordre.
  + Théories du premier ordre. Propriétés des relations binaires : (anti)symétrie, (ir)réflexivité, transitivité.
  + Égalité
  + Notions d’arithmétique de Peano et idée du théorème d’incomplétude de Gödel
  + Satisfaisabilité modulo des théories
  
• Autres logiques

Contrôle des connaissances

Evaluation : 25% de Devoir à la maison et 75% de Examen écrit (3h)

Rattrapage : Examen écrit (3h)

Calendrier

Le cours est programmé dans ces filières :

• Cursus ingénieur - Tronc Commun - Semestre 7

Informations complémentaires

Code de l'enseignement : 4MMLOG
Langue(s) d'enseignement :

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