PROGRAMMATION LOGIQUE log

Introduction 1
1 Rappels de logique mathématique 3
1.1 Calcul des prédicats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Langage du calcul des prédicats . . . . . . . . . . . . . . . . . 3
1.2 Formes normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Forme normale Prenexe . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Forme normale de Skolem . . . . . . . . . . . . . . . . . . . . 10
1.2.3 Clauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Programmation logique 16
2.1 Langage logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Unication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Résolution SLD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Domaines d'application de la programmation logique . . . . . . . . . 25
2.6 Exemples de programmes logiques . . . . . . . . . . . . . . . . . . . . 26
2.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Le langage PROLOG 31
3.1 Présentation de Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.1 Constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.3 Prédicat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.4 Faits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.5 Règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
ii
3.2.6 Buts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Algorithme d'unication de PROLOG . . . . . . . . . . . . . . . . . 35
3.3.1 Extraction de l'information . . . . . . . . . . . . . . . . . . . 38
3.4 Exécution d'un programme Prolog . . . . . . . . . . . . . . . . . . . . 39
3.4.1 Algorithme d'exécution . . . . . . . . . . . . . . . . . . . . . . 39
3.4.2 Points de choix . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Calcul en Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.6.1 Calcul de toutes les solutions . . . . . . . . . . . . . . . . . . 43
3.7 Stratégie de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.8 Stratégie de sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.9 Manipulation dynamique des programmes . . . . . . . . . . . . . . . 45
3.10 Trace d'exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.11 SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.12 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 Les listes et arbres en PROLOG 50
4.1 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.1.1 Unication des listes . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.2 Quelques opérations sur les listes . . . . . . . . . . . . . . . . 52
4.2 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Représentation par des listes . . . . . . . . . . . . . . . . . . . 60
4.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5 La coupure 65
5.1 Coupure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.1 Dangers avec la coupure . . . . . . . . . . . . . . . . . . . . . 70
5.2 Négation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72