Description

Ce module donnera aux étudiants de master informatique les fondements logiques nécessaires pour aborder la modélisation du raisonnement, la représentation des connaissance, la formalisation de problèmes et la spécification de programmes, toutes connaissances indispensables en intelligence artificielle, en bases de données, en recherche opérationnelle et en algorithmique. De plus, il initiera les étudiants à la programmation logique et au langage PROLOG.

Le programme comprend quatre parties plus ou moins équilibrées: 1- Le calcul propositionnel: on enseignera d'abord les fondements de la représentation des connaissances en logique, puis la syntaxe et la sémantique. 2- PROLOG: Une fois les notions de base de logique introduite, on donnera une première introduction pratique à PROLOG ; cela devrait illustrer l'intérêt de la logique tout en familiarisant les étudiants à ce langage. 3- Le calcul des prédicats: outre les notions classiques de syntaxe et de sémantique étendues à la logique du premier ordre, on abordera l'unification et la règle de résolution qui servent de fondement au langage PROLOG. 4- La démonstration automatique et la programmation logique: cette troisième partie montrera en quoi PROLOG est un démonstrateur automatique de théorème. Elle en exposera les fondements théoriques. Elle en enseignera ensuite l'utilité pratique en précisant les principes de programmation logique et du langage PROLOG et en montrant cela facilité la programmation.

Bibliographie

• Systèmes formels, Introduction à la logique et à la théorie des langages, Benzaken, Masson , 1991.

• Outils logiques pour l'intelligence artificielle , J-P Delahaye, Eyrolles, 1986.

• The Art of Prolog, Shapiro & Sterling, MIT Press, 1986.

Contenu indicatif par semaine

• cours • petite introduction à la logique, à la logique mathématique et à leur histoire. • langage des propositions, • table de vérité, conséquence logique, • théorème de déduction TD • exercice sur la représentation de connaissances en logique des propositions • manipulation de tables de vérité • exercices de démonstration de validité, applications du théorème de déduction

• • syntaxe, démonstration, théorème. • notion de schéma d'axiome, • démonstration de cohérence et de complétude du calcul des propostions. TD • manipulation du système axiomatique vu en cours • présentation du système de la déduction naturelle • démontrations de théorèmes avec plusieurs systèmes d'axiomes

• • formes normales, • méthode des arbres sémantiques • règle de résolution (en logique des propositions), TD • exercices de mise sous forme normale • application de la méthode des arbres sémantiques • preuve par réfutation en logique des propositions

• • Èléments de base de la syntaxe PROLOG (termes, littéraux, clauses...). • Déclarativité. • Non-déterminisme, interprétation procédurale avec des arbres et/ou et avec des arbres de dérivation. • Différences et analogies avec la programmation impérative et procédurale: notions de récursion, d' accumulateur, de variable, ...) TD • Dérécursion de programmes logiques • Programmes simples en PROLOG avec différentes structures de données (sur liste, sur arbres, ...)

• • notion de variable, de prédicat et de quantificateur, • occurrences libres, liées, substitution, etc.; • extension des schémas d'axiomes déjà vu à la logique du premier ordre • représentation des connaissances en logique du premier ordre. TD • Portée des quantificateurs • Démonstration de théorèmes en logique du premier ordre

• • satisfiabilité, validité, conséquence logique revisitée; • Extension des arbres sémantiques à la logique du premier ordre TD • Application de la méthode des arbres • Théorème de Herbrand

• • forme normale conjonctive et disjonctive, skolémisation • mise sous forme clausale, TD • Exercices de mise sous forme de clause

• • filtrage, unification, • résolution, • démonstration automatique de théorème TD • Exercices sur le filtrage et l'unification • Manipulation de la résolution • Stratégies d'application de la résolution

• • Clauses de Horn, • Stratégie de résolution linéaires, ordonnées, ... TD • Exemples de stratégies d'application de la résolution, • Exemples de programmes logiques simples (addition, ...)

• • Les trois coupures de PROLOG, négation, nombres, prédicats dynamiques... • Applications de PROLOG pour la programmation de quelques algorithmes classiques: parcours de graphes, tris, analyseurs syntaxiques... TD • Programmes sur les nombres • Exemples de programmes sur les graphes (programmes d'IA: parcours du graphe des états) • Programmation d'analyseurs syntaxiques • Systèmes de trace