Logique et programmation logique

  • Cours (CM) 18h
  • Cours intégrés (CI) -
  • Travaux dirigés (TD) 22h
  • Travaux pratiques (TP) 6h
  • Travail étudiant (TE) -

Langue de l'enseignement : Français

Niveau de l'enseignement : B2-Avancé - Utilisateur indépendant

Description du contenu de l'enseignement

Cette UE vise trois objectifs, liés à diverses facettes de la logique. Premièrement, étudier les fonctions booléennes, leurs représentations et simplifications, en lien avec la conception logique de circuits. Deuxièmement, introduire les notions de logique mathématique classique (d'ordre 0 et 1) et les appliquer à la déduction par la méthode de résolution. Troisièmement, introduire le paradigme de programmation logique par la pratique du langage Prolog. Programme :
Fonctions booléennes: formes normales, diagrammes, simplification ; ensembles dénombrables, ensembles récursifs, récursivement énumérables ; systèmes formels ; calcul propositionnel : axiomatique, déductions, interprétation, tautologies, satisfiabilité ; clauses, résolution sans variable ;. calcul des prédicats : axiomatique, interprétation, mise en forme de formules ; élimination des quantificateurs, unification ; résolution avec variables. Langage Prolog : faits, règles, fonctionnement de l'interprète, coupure, négation.

Compétences à acquérir

À l'issue de cette UE un étudiant devrait :
- savoir manipuler et simplifier des fonctions booléennes ;
- comprendre la notion de système formel et savoir formaliser un problème ;
- savoir utiliser le calcul des propositions et le calcul des prédicats ;
- comprendre la distinction entre syntaxe (déductions formelles) et sémantique (interprétations), en particulier comprendre la notion de modèle ;
- savoir traduire des énoncés du langage courant en logique du premier ordre ;
- pouvoir faire des déductions par la méthode de résolution (avec ou sans variables) ;
- comprendre et savoir résoudre un problème pratique simple en utilisant la programmation en Prolog.

Bibliographie, lectures recommandées

Bibliographie
- J.P. Delahaye : Outils logiques pour l'intelligence artificielle, 3e édition, Paris, Eyrolles, 1988.
- Serenella Cerrito : Logique pour l'informatique, introduction à la déduction automatique, Vuibert, 2008.
- René Cori et Daniel Lascar : Logique mathématique, tome 1, Dunod, 2003.

Pré-requis recommandés

À l'entrée de cette UE, un étudiant devrait :
- connaître le codage binaire (cf. Bases de l'architecture informatique en S1) ;
- connaître les rudiments de la théorie des ensembles et de la récursion (cf. Fondement du calcul et du raisonnement en S2) ;
- avoir des notions de différents paradigmes de programmation.

Contact

UFR de mathématique et d'informatique

7, rue René Descartes
67084 STRASBOURG CEDEX
0368850200

Formulaire de contact