01/10/2019

Mme AMIROUCHE
Département Informatique
UMMTO

1
 01/10/2019

Partie I
Introduction au paradigme de la
programmation logique

Principe général
 L’idée de la programmation logique est d’utiliser
l’ordinateur pour tirer des conclusions à partir
de descriptions déclaratives d’un problème
donné.
 De telles descriptions constituent le programme
logique.
 Un programme logique est composé d’une suite
finie de formules logiques constituant des
axiomes à partir desquels un problème est résolu.
 Dans la majorité des systèmes de programmation
logique, les axiomes sont formalisés dans la
logique des prédicats (ou logique de premier
ordre) par des clauses de Horn. 4

2
 01/10/2019

Caractéristiques
 Formalisation des informations :
 Un programme logique est une description des objets et des
relations entre les objets de l’univers du discours.
 La formalisation de cette description se fait dans un langage
dérivé de la logique.

 Le mécanisme d’inférence :
 La suite des actions à entreprendre pour trouver la solution
d’un problème donné n’est pas décrite à l’avance dans le
programme.
 Le langage de programmation logique intègre un
mécanisme de raisonnement (dit mécanisme
d’inférence) qui se charge d’entreprendre les actions
nécessaires sur la description faite par le programmeur,
pour aboutir à une solution du problème décrit.
 Ce mécanisme d’inférence est une procédure de résolution de
la logique mathématique.
5

Avantages
 Il n’y a plus d’erreurs de programmation : En effet, le programmeur ne
décrit plus les mécanismes de résolution qui sont à la charge du
langage lui-même. Il se contente de décrire simplement l’univers du
discours.
 Style de programmation adapté aux non informaticiens : la seule
aptitude requise pour programmer dans ce style, est une pensée
logique, rationnelle permettant de poser un problème en termes
d’hypothèses, de conclusions et d’axiomes disponibles.
 La longueur des programmes diminue puisque toute la partie sensée
coder la démarche de résolution du problème est déléguée au langage
lui-même, et ne figure pas dans le programme.
 Les modifications d’un programme, par ajout ou suppression de
données, n’affectent pas son exécution. En effet, toute nouvelle requête
(but) est examinée seulement en relation avec les informations
(données) existantes dans le programme. Le but réussit s’il est résolu
par les données du programme ; Il échoue sinon.

3
 01/10/2019

Inconvénient
 Il n’y a pas d’outils de contrôle de la validité de la
description :
 même si la consistance et la complétude théoriques
peuvent être vérifiées dans un système logique
formel, on ne peut aucunement vérifier les
erreurs dues à une mauvaise maîtrise des
connaissances de l’univers du discours. Or une
mauvaise description du problème peut conduire à
des résultats erronés.

Concepts de base
 Un programme logique est une suite finie de
clauses de Horn.
 En programmation logique, les clauses se
classifient en faits, règles et requêtes.
 Un programme logique est constitué d’une séquence
de faits et de règles.
 Un programme logique est interrogé par des
requêtes (ou buts).

4
 01/10/2019

Clauses de Horn
 Une clause de Horn est une clause comportant
au plus un littéral positif. Elle est de la forme :
x1  x k A  B1 ,  , Bl 

où A, B1,..., Bl sont des atomes et l >= 1.

 Les atomes Bi/ i = 1,,l, sont les hypothèses de la

clause de Horn et A sa conclusion.

Sémantique d’une clause de

Horn
 Etant donnée la clause de Horn suivante:
x1  x k A  B1 ,  , Bl 

 La sémantique d’une telle clause est que A est vraie

si tous les Bi sont vrais,
autrement dit: B1  B2    Bn  A

A  B1 , B2 , , Bn A si B1 , B2 ,  et Bn
 La notation se lit
10

5
 01/10/2019

Buts , Faits et Règles

 Un but est une clause de Horn sans
conclusion, c’est donc une clause de la forme:
x1  x k  B1 , , Bl 

Les atomes Bi sont les sous-buts de ce but.

 Un fait est une clause de Horn sans

hypothèses, c’est une clause de la forme:
x1  x k A  

 Une règle est une clause de Horn avec une

conclusion et des hypothèses, c’est une clause
de la forme: x1  x k A  B1 ,  , Bl 
11

Application
 Etant donnés les énoncés suivants en langue
naturelle :
 $1 : « les Sims » est un jeu
 $2 : Amine aime le sport
 $3 : Amine aime la télé
 $4 : Nassim aime les Sims
 $5 : Nassim aime tous ceux qui aiment la télé
 $6 : Tout individu peut jouer à un jeu qu’il aime

12

6
 01/10/2019

 En introduisant les constantes "Nassim", "Amine", "la_télé",

"le_sport", et "les_sims", les variables x et y, et les prédicats
"est_un_jeu/1", "aime/2" , et "peut_jouer/2", nous pouvons
former le programme logique suivant :

 C1 : est_un_jeu(Les_Sims) ←
 C2 : aime(Amine, le_sport) ←
 C3 : aime(Amine, la_télé) ←
 C4 : aime(Nassim, Les_Sims) ←
 C5: aime(Nassim, x) ← aime(x, la_télé)
 C6 : peut_jouer (x,y) ← est_un_jeu (y), aime(x, y)

 Les clauses de Horn C1, C2, C3 et C4 sont des faits.

 Les clauses de Horn C5 et C6 sont des règles. Elles
constituent la partie procédurale du programme.
13

 Supposons le but suivant:

G: ← peut_jouer (Nassim, y)
Qui traduit la question suivante:
« A quoi peut jouer Nassim? »

 La réponse du système logique, étant donné le

programme logique fourni, sera :
y = Les_Sims

 Pour dériver cette conclusion à partir des faits et

règles du programme, en vue de prouver le but
donné, le système de programmation logique se
base sur l’algorithme de résolution de la logique de
premier ordre. 14

7
 01/10/2019

Illustration du mécanisme d’inférence

1. On construit tout d’abord la négation du but, soit :
G’:  peut_jouer (Nassim, y)
2. Puis, considérant les formes clausales des différentes clauses de Horn du
programme logique, on procède par résolution comme suit:
 C1 : est_un_jeu(Les_Sims)
 C2 : aime(Amine, le_sport)
 C3 : aime(Amine, la_télé)
 C4 : aime(Nassim, Les_Sims)
 C5: aime(x, la_télé)  aime(Nassim, x)
 C6 : est_un_jeu (y)  aime(x, y)  peut_jouer (x,y)
 G’:  peut_jouer (Nassim, y)
 _______________
 C7 : est_un_jeu (y)   aime(Nassim, y)
Par résolution de G’ et C6, par la substitution {x\Nassim}
 C8 : aime (Nassim, les-Sims)
Par résolution de C7 et C1, par la substitution {y\les-Sims}
  Par résolution de C8 et C4.
Le but est donc prouvable moyennant la substitution {y\les-Sims} 15

Représentation par arbre inversé

16

8
 01/10/2019

Partie II
Le langage Prolog

Introduction à Prolog
 créé, en France, vers 1972, par Alain Colmerauer et
Philippe Roussel de l’université d’Aix-Marseille.

 langage de programmation déclaratif ( par

opposition aux langages de programmation
procéduraux classiques procéduraux).

9
 01/10/2019

Caractéristiques
 langage de programmation logique.

 formalisation des informations données par des

clauses de Horn.

 mécanisme d'inférence basé sur le mécanisme

de résolution de la logique des prédicats
résolution.

Implémentations
Le langage Prolog possède plusieurs
implémentations dont:
 SWI-Prolog ([Link]
 Open Prolog ([Link]/open-prolog)
 Visual-Prolog ()
 Turbo-Prolog ()
…

10
 01/10/2019

1. Syntaxe et Terminologie Prolog

1. Le programme Prolog
 Un programme Prolog consiste en une suite de
données
 Les données sont :
 des Faits
ou = Base de connaissances
 des Règles
 Un programme Prolog est interrogé par une
requête (ou but).
 Les données et les requêtes sont des clauses de
Horn.

11
 01/10/2019

Les Faits
 Un fait est une relation (prédicat) entre un certain
nombre d’objets, qui sont des termes de la logique des
prédicats.
Cette relation est inconditionnellement vraie.

 Exemple: pere (mohamed, amine).

 Les faits forment la partie déclarative du programme.

 Un fait peut contenir une variable, à l’exemple de:

egal(X,X).

 La variable dans un fait est quantifiée universellement.

egal(X,X) équivaut à X egal(X,X)

Les règles (1)

 Une règle exprime une relation entre des
prédicats apparaissant dans les faits.

 Les règles sont des formules implicatives de

la logique des prédicats, sur lesquelles le
programme applique l’unification et la
résolution.
 Les règles forment la partie procédurale du
programme.

12
 01/10/2019

Les règles (2)

 Une règle a la forme suivante:
A:- B1, B2, …, Bn.
où
 A est la tête de la règle (ou conclusion)
 la conjonction d’atomes B1, B2, …, Bn forme
le corps de la règle
 Les Bi (i=1..n) sont des prémisses (ou
hypothèses)
 Le symbole :- se lit « si »

Les règles (3)

 Une règle peut contenir des variables.

 Une variable apparaissant dans la tête

d'une règle (et éventuellement dans son
corps) est quantifiée universellement.

 Une variable apparaissant dans le corps

d'une règle mais pas dans sa tête est
quantifiée existentiellement.

13
 01/10/2019

Exemple
 Soit la règle suivante:

meme_pere(X,Y) :- pere(P,X), pere(P,Y).

 se traduit en logique des prédicats comme suit:

XY (( P (pere(P,X) pere(P,Y)))  meme_pere(X,Y))

Les Buts
 Un but en Prolog est une requête liée aux prédicats
apparaissant dans la base de connaissances du
programme.

 Un but est une suite d'atomes logiques séparés par des

virgules.

 Une requête peut comporter des variables. Elles sont

alors quantifiées existentiellement.
 Par exemple, le but :
? pere (X,Y).

correspond à la formulation suivante:

?  X  Y pere(X,Y).

14
 01/10/2019

Programme Prolog (1)

 Un programme Prolog est constitué d'une
suite de clauses (faits et règles) regroupées
en paquets.

 Chaque paquet définit un prédicat et est

constitué d'un ensemble de clauses dont
l'atome de tête a le même symbole de
prédicat et la même arité.

 L'ordre des paquets dans le programme

n'est pas significatif.

 Deux clauses d'un même paquet sont liées par

un ou logique.
 Par exemple, le prédicat personne défini par les
deux clauses:
personne(X):- homme(X).
personne(X) :- femme(X).
se lit ``pour tout X, personne(X) est vrai si homme(X)
est vrai ou femme(X) est vrai''.
 Clause équivalente en Prolog:

personne(X):- homme(X); femme(X).

 L'ordre des clauses d’un même paquet est

significatif.

15
 01/10/2019

Exécution d’un programme Prolog

 Exécuter un programme Prolog consiste à poser une
requête à l'interprète Prolog.
 Si la requête ne comporte pas de variables, la réponse de
Prolog est:
 ``true'' si le but est une conséquence logique du
programme,
 ``false'' si le but n'est pas une conséquence logique du
programme.

 Si la requête comporte des variables, la réponse de Prolog

est l'ensemble des valeurs des variables pour lesquelles
le but est une conséquence logique du programme.

Exercice 1
Combien de faits, règles, clauses et prédicats contient la
base de connaissances suivante. Identifier les têtes des
règles ainsi que les prémisses qu’elles contiennent.

 femme(maria).
 femme(sarah).
 homme(amine).
 personne(X) :- homme(X); femme(X).
 aime(X, Y) :- connait(Y, X).
 pere(Y, Z) :- homme(Y), fils(Z, Y).
 pere(Y, Z) :- homme(Y), fille(Z, Y).

16
 01/10/2019

2. Syntaxe des données

 Prolog manipule des objets.
 Ces objets sont:
 des termes :
 variables,
 constantes,
 fonctions sur les termes,

 Des prédicats (ou atomes logiques)

 Des listes.

Les variables
 Les variables représentent des objets inconnus de l'univers.
 Syntaxiquement, une variable est une chaîne alphanumérique commençant
par une majuscule ou par un souligné.
(1) X, Yy, Pere, _toto, A21 sont des variables,
(2) x, yy, pere, toto, 2A, « Pere », 321 ne sont pas des variables.

 Prolog offre la possibilité d’utiliser une variable anonyme , notée par le

caractère souligné ''_'' .
 La variable anonyme représente un objet dont on ne souhaite pas connaître la
valeur.
 Par exemple, en posant
pere(Mohamed, _)

on déclare simplement que Mohamed est pere de quelqu'un.

17
 01/10/2019

Les constantes (1)

 Les constantes représentent les objets
simples connus de l'univers du programme.

 Deux types de constantes:

 les termes atomiques (ou termes
élémentaires),
 les nombres

Les constantes (2)

 Un terme atomique est:
 Une chaîne alphanumérique commençant par une
minuscule,
 ou toute séquence de symboles placée entre quotes (ou
entre guillements).
(1) toto, aX12, jean_Paul_2, ‘Paul’, ‘5tx’, ‘_3P’ sont des
termes atomiques
(2) Paul , _3P, 5tx, Toto, 1Y ne sont pas des termes
atomiques.
 les nombres : Ce sont des entiers ou des réels.
211356 , -325 , 0.00013569 , -5.89 sont des nombres.

18
 01/10/2019

Les fonctions
 Les fonctions sont des termes composés de l'univers du
programme.
 Syntaxiquement, un terme composé est de la forme:
foncteur(t1, ..., tn)
 foncteur est une chaîne alphanumérique commençant par
une minuscule,
 t1, ..., tn sont des termes.

 Exemple
adresse(18, "rue des Lilas", Ville)
est un terme composé de foncteur adresse d'arité 3, dont
les deux premiers arguments sont les termes élémentaires
18 et "rue des lilas" et le troisième argument est la variable
Ville.

Les prédicats
 Un prédicat (ou atome logique) exprime une
relation ou une propriété de termes.
 Syntaxiquement, un atome logique est de la forme:
pred(t1, ..., tn )

 où le symbole de prédicat pred est une chaîne

alphanumérique commençant par une minuscule,
 t1, ..., tn sont des termes.
 Le prédicat pred est d’arité n. On le notera
pred/n

19
 01/10/2019

Structure d’arbre d’un prédicat (1)

 A tout prédicat correspond un arbre:
 dont la racine est le symbole du prédicat ,
 les nœuds internes sont les fonctions
contenues dans ce prédicat,
 les feuilles de l’arbre sont les variables et
les constantes qui apparaissent dans les
fonctions et dans le prédicat lui-même.

Structure d’arbre d’un prédicat (2)

pere(Mohamed, Amine) est-plus-grand(+(X,2), :(Y,3))

habite(X, adresse(12,"rue r",nice))

20
 01/10/2019

Structure d’arbre d’un prédicat (3)

 Prolog utilise les arbres de prédicats

pour contrôler le succès de
l’unification:
 Quand deux prédicats sont unifiés, leurs
arbres correspondants sont identiques.

Les listes
 La liste est composée d’une séquence de termes placés entre
crochets et séparés par des virgules.
 Exemple : la séquence [vinaigre, toto, salade, football, X,
biscuit] est une liste.

 Une liste permet de regrouper au sein d’un même objet, plusieurs

autres objets, permettant ainsi de réduire la taille d’un
programme Prolog.
 Exemple: Soit la base de connaissances suivante d’un
programme Prolog :
aime(Nassim, football).
aime(Nassim, cinéma).
aime(Nassim, pizza).
alors cet ensemble de faits peut être remplacé par le seul fait
suivant :
aime(Nassim, [football, cinéma, pizza]).

21
 01/10/2019

 La liste vide est une liste qui ne contient aucun

élément. Elle est notée [].

 Une liste non vide est composée de deux

termes, la tête de liste et la queue de liste.
 La tête de liste est un terme quelconque de
Prolog,
 la queue de liste est obligatoirement une
liste.

 Exemple : la liste [football, cinéma, pizza] a

pour tête le terme constant football, et pour
queue la liste [cinéma, pizza].

 Une liste peut être écrite sous forme de

prédicat, en utilisant le symbole de prédicat
spécial ''.'' (point) sous forme :
. (tête_de_liste, queue_de_liste)

Ou de façon plus générale :

. (tête1, . (tête2, . (tête3, ….(tête, []) …)))

 la liste .(X,L) est notée de manière

équivalente par [X|L] ou [X:L] (selon les
versions de prolog)

22
 01/10/2019

Exemples
 La liste [football, cinéma, pizza] peut se noter de manière
équivalente par :
. (football, .(cinéma, .(pizza, [])))
[football| [cinéma, pizza]]
[football , cinéma|[pizza]]
[football , cinéma, pizza|[]]
…
 Le symbole ''.'' est considéré comme un prédicat généralisé, dont
la forme est inconnue. On ne peut pas l’utiliser dans une requête
Prolog.

 En particulier, on ne peut pas interroger Prolog par les

requêtes suivantes:
? .(salade, .(vinaigre, [])).
? [salade, vinaigre]
? [X, vinaigre]

Arithmétique en Prolog
Opérateur Numérique Littéral
(terme à terme)
égalité = := =@=
inégalité \= = \=@=
Plus petit que < @<
Plus petit ou égal à =< @=<
Plus grand que > @>
Plus grand ou égal à >= @>=
Unification = =
Non unification not(=) not(=)

23
 01/10/2019

a. Égalité structurelle
 term1=@= term2 est vraie si term1 est
`structurellement' égal à term2.

 Deux termes sont structurellement égaux si

les représentations de leurs arbres sont
identiques et s’ils ont le même modèle de
variables.

! Le symbole ’= ’ en prolog signifie l'unification et

non l’affectation ou l’égalité.

Remarque
 On a:

?- 3 =:= 2+1. (comparaison de nombres)

true

?- 3 =@= 2+1. (comparaison de termes)

false

24
 01/10/2019

?- a =@= A
faux ?- X = 3, Y = 2+1, X =:= Y.
?- A =@= B false
vrai ?- 1 + 2 =:= 2 + 1.
?- x(A, A) =@= x(B, C) Yes.
faux ?- 1 + 2 = 2 + 1.
?- x(A, A) =@= x(B, B) No.
vrai ?- p(X,X) = p(1,1).
?- x(A, B) =@= x(C, D) X=1
vrai
?- p(X,X) = p(1,W).
?- X = 3, X = Y.
X=1, W=1
X = 3, Y = 3
?- X = 3, X =:= Y. ?- p(Y,fun(Y)) = p(toto,Z).
No Y = toto , Z = fun(toto)
?- X = 3, Y = 2+1, X = Y. ?- p(X,X,2) = p(1,W,W).
No No

b. Opérateurs arithmétiques
 Prolog fournit les opérateurs arithmétiques
+ - * / mod
 Ces opérateurs peuvent s’écrire :

 en notation infixée classique:

expr1 op expr2

 ou en notation préfixée, sous forme de

prédicats:
op(expr1, expr2)

25
 01/10/2019

Remarque
 +(2, *(3,5)) correspond au terme 2 + 3 * 5,

?- 2 + 3 * 5 = +(2, *(3, 5)).

true

Cependant:

?- 17 = 2 + 3 * 5.
false

c. Affectation
 l’opérateur "arithmétique" is/2 est l’opérateur
d’affectation.
 Syntaxe:
X is exp.
 Où exp est une expression arithmétique.
 La valeur de l’expression exp est calculée puis la
variable X est instanciée avec le résultat.
 Si l’expression exp contient des variables, celles-ci
doivent être d’abord instanciées avec une valeur
numérique.

26
 01/10/2019

Remarque 1 sur l’affectation

 l’expression à droite de l'opérateur is ne doit pas
contenir de variable libre (non instanciée),

 ?- Y is 3+X.
Variable libre
error: is/2: Arguments are not sufficiently
instantiated

Remarques 2 sur l’affectation

 l’expression à gauche de l'opérateur is ne peut être
qu'une valeur numérique, et non pas une expression
quelconque.
?- X = 5 + 2, X is 3 + 4.
false

?- 5+2 is 3+4.
false.
X est une
expression

27
 01/10/2019

 ?- 17 is 2 + 3 * 5.
 ?- X = 4, Y is 2 * X.
Yes.
X=4
 ?- is (17, +(2, *(3,5))). Y=8
Yes.
 ?- X = 7, X is 3 + 4.
 ?- X is 3+4. X=7
X=7

 ?- 7 is 3 + X.  ?- X = 6, X is 3 + 4.
Error No

Manipulation des listes (1)

Une liste [X| L] est une structure
récursive composée de:
 une tête X: le premier élément de la
liste
 une queue L: la liste L – {X}.

28
 01/10/2019

Manipulation des listes (2)

 les prédicats Prolog qui manipulent les
listes sont généralement définis par :
 une ou plusieurs clauses récursives, qui
définissent la relation sur la liste [X| L]
en fonction de la relation sur la queue
de liste L,
 une ou plusieurs clauses non récursives
assurant la terminaison du programme,
qui définissent la relation pour une liste
particulière (exemple: la liste vide...).

Exemple 1
Ecrire le prédicat membre/2 Prolog qui est vrai si
un élément appartient à une liste.

 Solution

membre(H, [H| _ ]).

membre(H, [ _ | T]):- membre(H, T).

29
 01/10/2019

Exemple 2
 Ecrire le prédicat non_membre/2 qui prenant un
élément et une liste en arguments, est vrai si et
seulement si l’élément n’appartient pas à la liste (le
symbole différent est noté \= =).

 Solution

non_membre(I, [ ]).
non_membre(I, [ K |T]):- \== (I, K), non_membre(I, T).

Exemple 3
 Ecrire le prédicat different/1 qui est vrai si tous les
éléments d’une liste sont (deux à deux) différents.

 Solution

different([ ]).
different ([X |L]) :- non_membre(X,L), different (L).

30
 01/10/2019

Exemple 4
 Ecrire le prédicat concat/3 de concaténation de
deux listes.

 Solution

concat([], L, L).
concat( [A|S], L, [A|R]) :- concat(S, L, R).

Exemple 5
 Ecrire le prédicat long/2 qui calcule de la
longueur d’une liste.

 Solution

long([ ], 0).
long([_ |L], N) :- long(L, P), N is P+1.

Le prédicat is est utilisé pour forcer l’évaluation de l’expression

arithmétique 1+P, dont la valeur sera unifiée avec N.

31
 01/10/2019

Autres Exercice
1. Ecrire un prédicat prolog plus_un/2 qui reçoit en
entrée une liste d’entiers et qui retourne en sortie
une autre liste d’entiers dont les éléments sont
obtenus en ajoutant 1 à chacun des éléments de la
liste initiale.

2. Ecrire un prédicat prolog dedouble/2 qui

permet de dédoubler chacun des éléments d’une
liste donnée en argument.

Solution des exercices

Exo1:

 plus_un([X],[Y]):-Y is X+1.
 plus_un([X|L],[Y|T]):- Y is X+1, plus_un(L,T).

Exo2:

 dedouble([],[]).
 dedouble([X|L],[X,X|T]):- dedouble(L,T).

32
 01/10/2019

Remarque
 Il existe de nombreux prédicats de manipulation des listes
qui sont prédéfinis en Prolog, dont:
 Append(List1,List2,List3) qui réussit si la liste List3 est le
résultat de la concaténation des listes List1 et List2 dans cet
ordre.
 length(?List, N) qui réussit si N est le nombre d’éléments
de la liste List.
 member(Elem, List) qui réussit si Elem peut être unifié
avec un membre de la liste List.
 last(List, Elem) réussit si Elem s’unifie avec le dernier
élément de la liste List.
 …

Unification des listes

• L’opérateur d’unification est noté =
• Deux listes sont unifiables si elles ont même tête et même queue.
?- [a, b] = [X , Y].
?- [a, b] = [X | Y].
X = a, Y = b
X = a, Y = [b]
?- [a] = [X].
?- [a] = [X | Y].
X=a
X = a, Y = []
?- [a, [b]] = [X , Y].
?- [a, [b]] = [X | Y].
X = a, Y = [b]
X = a, Y = [[b]]
?- [a | [b]] = [X| Y].
?- [a, b, c, d] = [X, Y | Z].
X = a, Y = [b]
X = a, Y = b, Z = [c, d]
?- [a, b| [c, d]] = [X, Y | Z].
?- [[a, b, c], d, e] = [X | Y].
X = a, Y =b, Z= [c, d]
X = [a, b, c], Y = [d, e]

33
 01/10/2019

Exercice 4
Donner la réponse de prolog à chacune des unifications suivantes :

 [a, b, c, d] = [H | T].
 [a, b, c, d] = [a, b, [c, d]].
 [a, [b, c, d]] = [H | T].
 [a, b, c, d] = [a, b | [c, d]].
 [] = [H | T].  [a, b, c, d] = [a, b, c, [d]].
 [a] = [H | T].  [a, b, c, d] = [a, b, c| [d]].
 [prolog, 3, X, 'Logique?'] = [A, B |  [a, b, c, d] = [a, b, c, d, []].
Z].  [a, b, c, d] = [a, b, c, d | []].
 [[a, b, c], [d, e, f], [g, h, i]] = [H |  [] = _.
T].  [] = [_].
 [a(X, c(d, Y)), b(2, 3), c(d, Y)] =  [] = [_ | []].
[H | T].
 [a, b, c, d] = [a, [b, c, d]].
 [a, b, c, d] = [a | [b, c, d]].

Exercice 5
Cinq maisons consécutives, de couleurs
différentes, sont habitées par des hommes de
différentes nationalités. Ils possèdent tous un
animal différent, ont chacun une boisson
préférée différente et fument des cigarettes
différentes.

On sait que:

34
 01/10/2019

Le norvégien habite la première maison,

La maison à coté de celle du norvégien est bleue,
L'habitant de la troisième maison boit du lait,
L'anglais habite la maison rouge,
L'habitant de la maison verte boit du café,
L'habitant de la maison jaune fume des kool,
La maison blanche se trouve juste après la verte,
L'espagnol a un chien,
L'ukrainien boit du thé,
Le japonais fume des craven,
Le fumeur de old-gold a un escargot,
Le fumeur de gitane boit du vin,
Un voisin du fumeur de chesterfield a un renard,
Un voisin du fumeur de kool a un cheval.
Qui boit de l'eau ? Qui possède un zèbre ?

indications
 Pour résoudre ce problème, on vous suggère d'écrire la
relation maison(C,A,B,F,N) où
 C est une couleur qui prend sa valeur dans l’ensemble des 5
couleurs {rouge, bleu, jaune, verte, blanche},
 A est un animal, qui prend sa valeur dans l’ensemble de 5
animaux {chien, renard, cheval,escargot, zèbre}
 B est une boisson qui prend ses valeurs dans l’ensemble de 5
boissons {lait, thé, vin, eau, café}
 F est une marque de cigarettes qui prend sa valeur dans
l’ensemble des marques de cigarettes {Kool, Craven, Old-
gold, chesterfield, gitane},
 N est une nationalité qui prend sa valeur dans l’ensemble des
5 nationalités {norvégien, espagnol, ukrainien,
japonais,anglais}.
 Le quartier est une liste de 5 maisons consécutives.

35
 01/10/2019

Exercice 6
 Dans l’énoncé suivant, chaque lettre représente un
chiffre et un seul. Trouver la ou les solutions à :

MOT FORTY NEUF

+ MOT + TEN + UN
+ MOT + TEN + UN
= BLA = SIXTY = ONZE

Le mécanisme de résolution de
Prolog
 Prolog fonctionne en mode de chaînage
arrière:
 Il démarre à partir des buts à démontrer et
cherche des faits permettant de les déduire (on
parle de raisonnement guidé par les buts).
 La méthode de déduction utilisée est basée sur
le principe de résolution de la logique des
prédicats.
 Son mode de fonctionnement est comme suit:

36
 01/10/2019

Pour prouver un but (requête) composé d’une suite

d’atomes logiques :
G   A1 , A2 , ... An 

 PROLOG commence par prouver le premier de ces

atomes logiques A1.
 Pour cela, PROLOG cherche dans le programme, une
clause (fait ou règle) dont la tête (ie. la conclusion)
s’unifie avec A1 : soit par exemple la clause R
suivante : ' ' ' '
R : A0 :  A1 , A2 ,..., Am
telle que  
mgu A1 , A0'  s

 PROLOG remplace le premier but à prouver (A1) par les

atomes logiques du corps de la clause R, en leur
appliquant la substitution (s).

Le nouveau but à prouver devient:

     
G  s A1' , s A2' ,..., s Am' , A2 , ... An 
 Prolog recommence ce processus jusqu’à ce que le but à
prouver soit vide.

 Lorsque tous les buts sont résolus, la requête est

satisfaite, et prolog affiche le résultat.

37
 01/10/2019

Notons que:

 Si le but initial (la requête) comporte des variables,

Prolog affiche les valeurs de ces variables, obtenues
par application des substitutions successives
utilisées lors de la résolution.

 Si le but initial ne comporte pas de variables,

Prolog affiche pour seule réponse ‘true’ ou ‘false’
selon que le but est satisfiable ou non.

Remarque 1
 Il peut exister plusieurs clauses candidates d’un
programme PROLOG, dont les têtes s’unifient avec un but
atomique donné.
 Dans ce cas, PROLOG choisit la première clause
rencontrée dans le code du programme.
 Si celle-ci mène à un échec, la règle suivante de même tête
est examinée.
 Si elle mène à un succès, alors le but est résolu.
 Prolog marque cette règle et tente ensuite de résoudre
le but suivant dans la liste des buts éventuels en
attente.

 PROLOG répétera successivement le processus de

preuve pour chacune des clauses candidates, et peut
ainsi retourner plusieurs solutions.

38
 01/10/2019

Remarque 2:
 La stratégie de recherche de PROLOG est dite recherche
en profondeur d’abord. Elle consiste ainsi à poursuivre un
but jusqu’à le démontrer.
 Cette stratégie dépend:
 d’une part de l’ordre de définition des clauses dans un
paquet (les clauses candidates sont considérées dans leur
ordre d'apparition dans le paquet),
 et d’autre part de l’ordre des atomes logiques dans une
clause (on prouve les atomes logiques selon leur ordre
d'apparition dans la clause).
 Un mauvais ordre peut conduire la stratégie de recherche à
boucler indéfiniment.

Remarque 3:
 Lors de la résolution, PROLOG construit l’arbre
de preuve ou arbre de recherche.

39
 01/10/2019

Un exemple d’application
 Considérons le programme Prolog suivant:
 Est_un_jeu (les_Sims).
 est_un_jeu (half_life).
 est_un_jeu (fifa-street).
 aime(amine, la_télé).
 aime(amine, fifa_street).
 aime(nassim, les_Sims).
 aime(nassim, half-life).
 aime(nassim,X) :-aime(X, la_télé).
 peut_jouer(X,Y) :-est_un_jeu(Y), aime(X, Y).

et soit le but
?- aime(X, Y).

Les réponses de Prolog au but donné sont :

- X= amine, Y= la_télé ;
- X= amine, Y= fifa-street ;
- X= amine, Y= la_télé ;
- X= nassim, Y= les-Sims ;
- X= nassim, Y= half-life ;
- X= nassim, Y= amine;
- false

Remarque :
 On introduit le point virgule à la fin de chaque réponse
pour demander à Prolog d’affiche le résultat suivant.
 Lorsqu’il n’y a plus de résultats à afficher, Prolog retourne
false.

40
 01/10/2019

Arbre de résolution du premier but

 Considérons le second but suivant:

?-peut-jouer (X,Y).

 Et les réponses associées de Prolog:

 X= nassim, Y= les-Sims ;
 X= nassim, Y= half-life;
 X= amine, Y= fifa-street ;
 X= amine, Y= la_télé ;

41
 01/10/2019

Arbre de résolution du second but

Le Backtracking ou Retour arrière

 Lors de la résolution, lorsqu’un sous-but n’est pas satisfait
(échec de résolution), Prolog effectue un retour arrière (ou
remontée de l’arbre de recherche), vers le but précédent
prouvé afin de tenter de le satisfaire à nouveau par une autre
alternative.
 Lors de ce processus de retour arrière, toutes les variables
qui étaient liées sont libérées de nouveau. Prolog tente alors
de resatisfaire le but précédent à l’aide de la clause suivante
possible dans le programme.
 Ce processus est appliqué itérativement jusqu’à ce que le sous
but soit satisfait ou jusqu’à ce qu’il n’y ait plus de clauses à
unifier. Dans ce cas, Prolog remonte vers le but précédant le
but courant, et tente de le satisfaire à nouveau… Le processus
s’arrête lorsqu’il n’y a plus de buts à satisfaire.

42
 01/10/2019

Exemple de résolution avec Retour arrière

Considérons le programme suivant :

 p(X) :- a(X).
 p(X) :- b(X), c(X), d(X), e(X).
 p(X):- f(X). Et soit le but:
 a(1). ?-p(X).
 b(1).
 b(2).
 c(1).  Réponses de Prolog:
 X=1;
 c(2).
 X=2;
 d(2).
 X=3 ;
 e(2).  false
 f(3).

Arbre de Résolution

Backtracking

43
 01/10/2019

La coupure
 La coupure est un mécanisme de contrôle des
retours-arrières en Prolog.
 La coupure est implémentée par le prédicat cut,
noté !, qui permet d’élaguer (ie. de couper) des
branches de l’arbre de recherche, empêchant ainsi
la remontée dans l’arbre.
 Le prédicat cut est toujours vrai.

Fonctionnement de la coupure
Supposons une règle de la forme :
q :- p1, p2, …, pn, !,r1, r2, …, rm.

 A la résolution, une fois le cut atteint, on se restreint aux

seuls choix (ie. valeurs) de p1, p2, …, pn, établis avant
le cut.
 On ne peut pas remonter vers une autre alternative de q
(la clause qui a introduit le cut).
 Cependant, on peut faire des retours arrières sur tous les
atomes r1, r2, …, rm, et sur toutes les alternatives
atteintes avant d’atteindre q.
 Ainsi, dans l’arbre de recherche, tous les noeuds au dessus
du cut, jusqu’au nœud contenant le but qui a induit la
sélection de la clause contenant le cut, sont élagués.

44
 01/10/2019

Exemple avec coupure

Considérons le programme suivant :

 P(X) :- a(X).
 P(X) :- b(X), c(X),!, d(X), e(X).
 P(X):- f(X).
Et soit le but:
 a(1).
 b(1). ?-p(X).
 b(2).
 c(1).
 c(2).  La Réponse de Prolog:
 X=1;
 d(2).  No.
 e(2).
 f(3).

Arbre de résolution

45
 01/10/2019

Un autre exemple
Considérons le prédicat max(N,M,Max)qui est vérifié si Max
est le nombre maximum entre N et M.

 Une solution possible est :

 max(N,M,N) :- N >= M.
 max(N,M,M) :- M > N.

 Mais une solution plus efficace est la suivante:

 max(N,M,N) :- N >= M, !.
 max(N,M,M):- M > N.
car dès que le premier but de la première règle est vérifiée, il n’y
a plus d’autres solutions

Coupures vertes
• Les coupures qui ne changent pas le sens
d’un prédicat sont des coupures vertes.
• La coupure dans l’exemple max/3 ci-dessus
est une coupure verte :
– Le nouveau code donne exactement les
mêmes résultats que la version initiale
sans coupure,
– Mais est plus efficace.
 on peut enlever la coupure verte le programme
fonctionnera toujours correctement.

46
 01/10/2019

Coupure rouge
• Une coupure rouge est une coupure qui change
le sens d’un prédicat .
• Ainsi la coupure introduite dans le prédicat p/1
définit précédememnt (paragraphe: coupure)
est un exemple de coupure rouge:
– Les deux programmes avec et sans coupure ne sont
pas équivalents
 Contrairement à la coupure verte, le retrait
d’une coupure rouge conduit à un programme
au fonctionnement erroné.

Utilisation du CUT
 Le CUT peut être utilisé pour:
 Rendre la recherche déterministe, à l’exemple
du prédicat Membre avec coupure:
 ? Membre(a,[a,b,c,a,d,a]). avec un tel but on
peut vouloir une seule solution et pas trois

 exprimer la conditionnelle si ...alors ... Sinon

 exprimer la négation.

47
 01/10/2019

Recherche déterministe
 Considérons le prédicat:
 membre(H, [H| _ ]).
 membre(H, [ _ | T]):- membre(H, T).

 Et le but:
 ? Membre (a, [a,b,c,a,d,a]).

 Les solutions de Prolog à ce but sont:

 true ;
 true ;
 true ;
 false.

 En reconsidérant l’exemple précédent avec la

coupure:
 membre(H, [H| _ ]):-!.
 membre(H, [ _ | T]):- membre(H, T).

 Et le but:
 ? Membre (a, [a,b,c,a,d,a]).

 La seule solution (Recherche déterministe) de

Prolog à ce but est:
 True.

48
 01/10/2019

La conditionnelle
 Implémentation du si-alors-sinon (désigné ici par
le prédicat if):

if(P,Q,R):-P,!,Q.
if(P,Q,R):-R.

 Le but if(P,Q,R) peut être démontré si P est vrai

(règle 1) ou, en alternative, si P est faux (règle 2).

Un exemple d’utilisation du if:

la factorielle

if(P,Q,R):-P,!,Q.
if(P,Q,R):-R.

fact(N, M):- if ( (N=:=0),

M is 1,
(fact(N-1, P), M is N*P)
).

49
 01/10/2019

La négation en Prolog (1)

 Considérons le programme suivant:
 homme(moh).
 homme(ali).
 femme(maria).
 egal(X,X).

 Et soit le but:
 ?- homme(wassim).

 La réponse de prolog à ce but est :

 false.

Négation en Prolog (2)

 La réponse False de Prolog au but

précédent est une négation par
l'échec, et non une négation logique.

50
 01/10/2019

Négation par l’échec/ Négation logique

 Dans la négation par l’échec, un prédicat est
considéré comme faux si, en un temps fini, Prolog
échoue à montrer qu'il est vrai => hypothèse du
monde clos.

 Dans la négation logique, un prédicat est

considéré comme faux si on peut montrer que sa
négation est vraie.

Hypothèse du monde clos et Négation

par l’échec

 Dans l'hypothèse du monde clos on

considère que tout ce qui doit être
connu est inclus dans la base de
connaissances.
 Si un fait n’est pas dans la base de
connaissances, il est considéré
comme faux.

51
 01/10/2019

 Si F est une formule, sa négation logique

est notée not(F) ou not F.

 Dans l'hypothèse du monde clos,

not(F) est vraie signifie que la formule
F n’est pas démontrable (négation
par l'échec), et non que F est une
formule fausse (au sens de la négation
logique)

La négation logique en Prolog:

le prédicat not
not(P) :- P, !, fail.
not(P).

 Pour démontrer not(P), Prolog essaie de

démontrer P:
• S’il réussit, une coupure élimine les points de
choix éventuellement créés durant cette
démonstration puis échoue (grâce au prédicat
fail).
• Si la démonstration de P échoue (selon
l’hypothèse du monde clos), Prolog utilise la
deuxième règle qui réussit.

52
 01/10/2019

Utilisations de la négation logique

 Vérifier qu’une formule n’est pas vraie.
 La négation logique ne doit être utilisée
que sur des prédicats dont les arguments
sont déterminés et à des fins de vérification.
 Son utilisation ne devrait jamais
déterminer la valeur d’une variable.

Négation et variables (1)

homme(moh).
homme(ali).
femme(maria).
egal(X,X).

?- homme(moh). Négation par l’absence

true
?- homme(slim).
false
?- not(homme(slim)). Négation logique
true
?- not(homme(X)).
false
Prolog ne retourne pas
X=slim !!!

53