Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

COURS DE Programmation logique et contrainte Enseignant : Dr. AOUN Oussama An

COURS DE Programmation logique et contrainte Enseignant : Dr. AOUN Oussama Année Universitaire 2020/2021 ENSEM Introduction Classes de langage séquencement des calculs spécifié contrôle total du flot d’exécution objets du langage diversifiés syntaxe riche (lourde :-)) exemples : Pascal, C, C+, C++, Java, … Langages impératifs Langages fonctionnels tout est fonction – syntaxe dépouillée – base mathématique forte : λ-calcul contrôle délégué à l’interprète – utilisation intensive de la récursivité exemples : Lisp, Scheme, Haskell, … Une nouvelle classe : PROgrammation en LOGique PROgrammation en LOGique tout est logique syntaxe simple et dépouillée base théorique : calcul des prédicats encore plus de contrôle donné à la machine récursion non déterminisme exemple : Prolog Objectifs Utiliser PROLOG Réaliser un système expert Résoudre automatiquement des énigmes logiques exprimées en langage naturel Résonner en arbre logique Programmation sous contraintes Logique des propositions Logique des prédicats Unification RAPPELS DE LOGIQUE POUR PROLOG LOGIQUE DES PROPOSITIONS SYNTAXE 7 On définit : Les propositions : a, b, c, … Les constantes : V et F Les connecteurs : ∧(conjonction) ∨(disjonction) ¬ (négation) ⊃(implication) CONSTRUCTION D’UNE FORMULE 8 Une proposition est une formule Si a et b sont des formules, alors ¬a, a∨b, a∧b, a⊃b sont des formules LOGIQUE DES PROPOSITIONS SÉMANTIQUE 9 Les formules sont interprétées dans {V,F} On définit l’interprétation associée à chaque connecteur grâce aux tables de vérité TABLES DE VÉRITÉ DES CONNECTEURS 10 A B ¬A A∧B A∨B A⊃B V V F V V V V F F F V F F V V F V V F F V F F V PROPRIÉTÉS DES FORMULES 11 Une formule est valide si elle est toujours vraie (quelque soit l’interprétation) Une formule est consistante s’il existe une interprétation dans laquelle elle est vraie. Elle est inconsistante dans le cas contraire Problème : étant donnée une formule, est-elle valide ? consistante ? Exemple : que dire de la formule (a⊃b) ⊃(¬b⊃¬a) DRESSONS LA TABLE DE VÉRITÉ 12 a b a⊃b ¬b ¬a ¬b⊃¬a (a⊃b)⊃(¬b⊃¬a) V V V F F V V V F F V F F V F V V F V V V F F V V V V V RÈGLES DE TRANSFORMATION (1) 13 a∨¬a (loi du tiers exclu) ((a⊃b) ∧a) ⊃b (modus ponens) ((a⊃b) ∧¬b) ⊃¬a (modus tollens) (a⊃b) ⇔(¬b ⊃¬a) (contraposition) ¬¬a ⇔a (double négation) a⊃b ⇔¬a ∨b a∨a ⇔a∧a ⇔a (idempotence) RÈGLES DE TRANSFORMATION (2) 14 Lois de De Morgan : • ¬(a∨b) ⇔¬a ∧¬b • ¬(a∧b) ⇔¬a ∨¬b Commutativité et associativité de ∨et ∧ Distributivité de ∨par rapport à ∧et de ∧par rapport à ∨ X∧(X∨Y) = X, X∨(X∧Y) = X (absorption) X∨(¬X∧Y) = X∨Y UNE ÉNIGME POLICIÈRE 15 Un meurtre a été commis au laboratoire, le corps se trouve dans la salle de conférences… On dispose des informations suivantes : La secrétaire déclare qu’elle a vu l’ingénieur dans le couloir qui donne sur la salle de conférences Le coup de feu a été tiré dans la salle de conférences, on l’a donc entendu de toutes les pièces voisines L’ingénieur affirme n’avoir rien entendu On souhaite démontrer que : si la secrétaire dit vrai, alors l’ingénieur ment LOGIQUE DES PRÉDICATS 16 SYNTAXE On définit : Les constantes : V et F Les connecteurs : ∧∨¬ ⊃ Les variables : x, y, z, … Les fonctions : f, g, h, … Les prédicats : p, q, r, … dont ceux d’arité 0 : a, b, c, … Les quantificateurs : ″, ∃ DÉFINITIONS 17 Terme : Une variable est un terme Une constante est un terme Si t1, t2, …, tn sont des termes, alors f(t1,t2,…,tn) est un terme Exemple : fils(x) Atome : Si t1, t2, …, tn sont des termes, et p un prédicat, alors p(t1,t2,…,tn) est un atome Exemple : pere(x,y) CONSTRUCTION D’UNE FORMULE 18 V, F sont des formules Un atome est une formule Si F1 et F2 sont les formules, alors ¬F1, F1∧F2, F1∨F2, F1⊃F2 sont des formules Si F est une formule, ∀x F et ∃x F sont des formule Exemples : ∀x pere(x,fils(x)) ∀x ∀y ∀z (pere(x,y)∧pere(y,z)) ⊃gpere(x,z) Remarque : la logique des propositions est un cas particulier de la logique des prédicats EXEMPLES DE FORMULES VALIDES 19 ∀x¬A ⇔¬ ∃xA ∀xA ⇔¬∃x¬A Comment déterminer qu’une formule est valide ? DÉFINITIONS 20 Littéral Un atome est un littéral (positif) La négation d’un atome est un littéral (négatif) Une clause est une formule qui a la forme d’une disjonction de littéraux Exemple : P(x,y) ∨¬Q(z) Une clause concrète est une clause sans variable Une clause de Horn est une clause comportant au plus un littéral positif On peut toujours transformer une formule en un ensemble (conjonction) de clauses PRINCIPE DE RÉSOLUTION 21 C’est une règle d’inférence qui s’applique aux clauses Principe sur des clauses concrètes : • G = G1∨G2∨…∨Gn • H = ¬G1∨H2∨…∨Hm • K = G2∨…∨Gn ∨H2∨…∨Hm K est le résolvant de G et H, on peut l’ajouter à la conjonction de clauses G1 et ¬G1 sont des littéraux complémentaires JUSTIFICATION 22 (P∨A)∧(¬P∨B) = (P∧B)∨(A∧¬P) ∨(A∧B) (P∨A)∧(¬P∨B) ∧(A∨B) = ((P∧B)∨(A∧¬P) ∨(A∧B))∧(A∨B) = (A∧P∧B)∨(A∧¬P)∨(A∧B)∨(P∧B)∨(A∧¬P∧B)∨(A∧B) = (A∧B) ∨(A∧¬P) ∨(P∧B) CAS PARTICULIERS 23 P et ¬P∨Q se résolvent en Q (modus ponens) ¬G∨H et ¬H∨K se résolvent en ¬G∨K (enchaînement) ¬Q et ¬P∨Q se résolvent en ¬P (modus tollens) UTILISATION 24 Le principe de résolution est une règle d’inférence saine, i.e. tout résolvant est une conséquence logique des deux clauses parentes Pour appliquer le principe de résolution à des clauses non concrètes, on définit l’unification, afin de rechercher des littéraux complémentaires UNIFICATION 25 Deux termes t1 et t2 sont unifiables s’il existe une substitution σ des variables de t1 et t2 telle que ο t1 = σ t2 Exemples : • pere(X,jean) s’unifie avec pere(Y,Z) si X|Y et jean|Z • pere(jean,mere(X)) s’unifie avec pere(Y,mere(pierre)) si jean|Y et X|pierre RÉFUTATION PAR RÉSOLUTION 26 Pour prouver que H est une conséquence logique de G : On transforme G et H en ensemble de clauses On applique le principe de résolution à G∧¬H jusqu’à trouver la clause vide (faux) Ce principe est complet pour les clauses de Horn (Prolog) COURS DE Programmation logique et contrainte Enseignant : Dr. AOUN Oussama Année Universitaire 2020/2021 ENSEM ROLOG Historique 1930 Calcul des prédicats (J. Herbrand) 1965 Principe de résolution (J. A. Robinson) 1970 Utiliser la logique comme langage de programmation clauses de Horn R. Kowalski Q-systèmes A. Colmerauer 1972 Premier interprète PROLOG (A. Colmerauer et P. Roussel) Université d’Aix-Marseille 1977 Premier compilateur PROLOG (D. H. D. Warren) Université d’Édimbourg 1980 Projet japonais de 5e génération 1990 PROLOG évolue vers la Programmation par Contraintes Bibliographie  L. Sterling, E. Shapiro, L’art de Prolog, Masson  Clocksin, Mellish, Programmer en Prolog, Eyrolles LE LANGAGE PROLOG 4 Langage d’expression des connaissances fondé sur le langage des prédicats du premier ordre Programmation déclarative : L’utilisateur définit une base de connaissances L’interpréteur Prolog utilise cette base de connaissances pour répondre à des questions CONSTANTES ET VARIABLES 5 Constantes Nombres : 12, 3.5 Atomes Chaînes de caractères commençant par une minuscule Chaînes de caractères entre " " Liste vide [] Variables Chaînes de caractères commençant par une majuscule Chaînes de caractères commençant par _ La variable « indéterminée » : _ TROIS SORTES DE CONNAISSANCES : FAITS, RÈGLES, QUESTIONS 6 Faits : P(…). avec P un prédicat pere(jean, paul). pere(albert, jean). Clause de Horn réduite à un littéral positif Règles : P(…) :- Q(…), …, R(…). Grpere(X,Y) :- pere(X,Z), pere(Z,Y). Clause de Horn complète Questions : S(…), …, T(…). pere(jean,X), mere(annie,X). Clause de Horn sans littéral positif Univers PROLOG L’univers PROLOG est une base de connaissances décrivant l’état du monde à l’aide de relations (prédicats) portant sur des entités (termes) Un prédicat particulier (=) correspond à l’unification Le langage Syntaxe de PROLOG Considérons l’énoncé Socrate est un homme Tout homme est mortel Socrate est-il mortel ? Calcul des prédicats Prolog x, homme(x) homme(socrate). x, homme(x) mortel(x) mortel(X) :- homme(X). ?- mortel(socrate). Le langage La famille masculin(tom). % tom est de sexe masculin masculin(tim). masculin(bob). masculin(jim). % «paquet» de clauses feminin(pam). feminin(liz). feminin(ann). feminin(pat). enfant(bob,pam). enfant(bob,tom). enfant(liz,tom). enfant(ann,bob). enfant(pat,bob). enfant(tim,liz). enfant(jim,pat). Le langage Premières requêtes masculin(tom). masculin(tim). masculin(bob). masculin(jim). feminin(pam). feminin(liz). feminin(ann). feminin(pat). enfant(bob,pam). enfant(bob,tom). enfant(liz,tom). enfant(ann,bob). enfant(pat,bob). enfant(tim,liz). enfant(jim,pat). Est-ce que pat est un enfant de bob ? ?- enfant(pat,bob). Quels sont les enfants de tom ? ?- enfant(X,tom). X = bob ; Yes X = liz ; Le langage Règles Prolog 1 1 Il peut y avoir plusieurs conditions derrière le « :- », séparées par des virgules ou des points-virgules La virgule correspond à un ET logique (conjonction) Le point-virgule correspond à un OU logique (disjonction) Exemple : La relation telle que si on est le père du père ou de la mère de quelqu’un alors on est son grand-père se traduit par : grandpere(xavier,yves) :- pere(xavier,joe), pere(joe,yves). grandemere(xavier,yves) :- pere(xavier,joe), mere(joe,yves). ou encore par : grandpere(xavier,yves) :- pere(xavier,joe), (pere(joe,yves) ; mere(joe,yves)). Constantes vs Variables 1 2 Constantes: commencent par une minuscule ou entre apostrophes ou entiers ou flottants Variables : commencent par une uploads/Philosophie/ pro-logique-contraintes-complet.pdf