ème
Université d’Alger 1 Ben Youcef BenKhedda 3 année Système Informatique (L3-SI)
Département Mathématiques et Informatique Série de TD
Intelligence Artificielle (IA)
Programmation Logique Exercice 4 :
et Système Expert Considérer le programme Prolog suivant:
Apprécier (Omar, X): - Burger1 (X),!, fail.
Exercice 1 : Apprécier (Omar, X): - Burger (X).
Burger (X): - Burger1 (X).
Soit un programme constitué avec les clauses relatives Burger (X): - Burger2 (X).
aux prédicats q, r, p avec 3 possibilités de positions de Burger (X): - Burger3 (X).
la coupure pour p(X, Y). Burger2 (a).
Burger1 (b).
1) Donner les solutions et la représentation de l’arbre Burger2 (c).
de résolution de chaque but pi(X, Y) Burger3 (d).
q(a). Donner la représentation de l’arbre de résolution et
q(b). la solution du But Apprécier (Omar, X)
q(c). Indiquer s’il s’agit d’un ‘green‘ ou ‘red’ cut.
r(b, b1).
r(c, c1). Exercice 5
r(a, a1).
r(a, a2). Considérer la base de règles et faits suivante pour
r(a, a3). diagnostiquer les problèmes d'auto:
p0(X, Y) :- q(X), r(X, Y).
p1(X, Y) :- q(X), r(X, Y), !. (R1) Si gaz_dans_le_moteur et se_tourne, Alors
p2(X, Y) :- q(X), !, r(X, Y). problème (bougies)
p3(X, Y) :- !, q(X), r(X, Y).
pi(d, d1). % avec i successivement 0, 1, 2, 3 (R2) Si se_tourne et non (s'allume), Alors problème
(batterie)
Exercice 2
(R3) Si se_tourne et s'allume, Alors problème
Considérer le programme Prolog suivant: (démarreur).
Etudiant (X): - Masculin (X), not(Salarié (X)).
Masculin (Anis). (R4) Si gaz_dans_le_réservoir et
Masculin (Karim). gaz_en_carburateur, Alors gaz_dans_le_moteur
Salarié (Karim).
gaz_dans_le_réservoir
Donner les réponses générer par Prolog pour les gaz_en_carburateur
questions suivantes : se_tourne
?- Etudiant (Anis). - Le but est de résoudre problème (X)?
?- Etudiant (Karim).
?- Etudiant (qui). 1) Résoudre le problème en utilisant le chaînage
?- not(Salarié (qui)). avant (Forward chaining)
2) Résoudre le problème en utilisant le chaînage
Exercice 3 : arrière (Backward chaining)
3) Supposons que le but est de prouver le
Écrivez un prédicat Chevauchement (S1, S2) qui problème (batterie) avec le même ensemble
de faits initiaux. Dessinez l'espace de
réussit si les listes S1 et S2 ont un élément
recherche en fonction des règles
commun.
déclenchables.
Puis écrire un prédicat Disjoint (S1, S2) qui
réussit si S1 et S2 n'ont pas d'élément commun
ème
Université d’Alger 1 Ben Youcef BenKhedda 3 année Système Informatique (L3-SI)
Département Mathématiques et Informatique Série de TD
Intelligence Artificielle (IA)
Représentation Graphique Déduire par le mécanisme d'inférence de nouvelles connaissances
du réseau construit
des Connaissances
Exercice 2 :
Construire un réseau sémantique représentant :
I. Réseaux Sémantiques (RS) : - Youcef étudiant L1, 18 ans.
- Hassiba étudiante L2, 19 ans.
Exercice 1 :
- Houari étudiant L3, 21 ans.
Construire un réseau sémantique représentant les connaissances - Malika étudiante L2, 20 ans.
suivantes: - Ali étudiant M1, 21 ans.
- Les oiseaux et les mammifères sont les deux des animaux.
- Les animaux peuvent marcher. Construire le réseau sémantique permettant de poser la
question « quelles sont les filles qui sont en L2 » ?
- Les chats sont des animaux et mangent des rongeurs. - Proposer une construction de réseau sémantique pour
- Les chats domestiques sont des variétés de chats qui mangent rependre à cette question
des souris.
Exercice 3 :
- Les chats ont quatre pattes
Représenter sur un même réseau les informations suivantes :
- Morris est un chat domestique.
« Pierre sait qu’il est scientifique, Jone croit que Pierre n’est pas
- Les oiseaux peuvent voler scientifique, Paul ne sait pas que Pierre est scientifique »
- Pingouin, Moineau, Aigle sont tous des oiseaux
- Les pingouins peuvent aussi nager
- Fred est un pingouin
1
Exercice 4 :
Considérez le réseau sémantique suivant:
1) Quels nœuds sont des concepts, et quels nœuds sont des
objets?
2) Décrivez quelques significations possibles des arcs de
propriétés.
3) Quelle est la couleur du vélo de Lilian?
4) Quelle est la couleur du vélo d’un étudiant?
5) Quels sont les points communs entre les VTT et les
opéras?
6) Peut-on dire que Lilian apprécie l’opéra Don Giovanni ?
Exercice 5 :
Extraire les connaissances du réseau sémantique suivant et les
représenter en logique des Prédicats
ème
Université d’Alger 1 Ben Youcef BenKhedda 3 année Système Informatique (L3-SI)
Département Mathématiques et Informatique Série de TD
Intelligence Artificielle (IA)
Exercice 2 :
Représentation Logique 1- B est-elle une conséquence logique de A?
// Montrer A╞ B avec la table de vérité i.e (A B est une
des Connaissances tautologie ?)
A = (p → m) ʌ m B = p
A=p→mʌp B= m
A = (P ˅ Q) ʌ (┐P ˅ R) B=QʌR
I. Logique Propositionnelle : A = (P → Q) ʌ (P → ┐Q) B = ┐P
A = {P → R ; Q → R} B = (P ˅ Q ) → R
Exercice 1 :
1- Des touristes font chacun une déclaration, représenter ces 2- les formules suivantes sont-elles cohérentes ? // il existe I tel que
déclarations en logique propositionnelle : I(P)=1 ?
« Nous avons visité Alger et Béjaïa mais pas Oran» (a ˅ ┐b) ʌ (┐a ˅ b) ʌ ┐ (a ↔ b)
« Nous avons visité Oran et Béjaïa mais pas Alger » b → (┐c → ┐(b → c))
« Nous avons visité Alger et Oran mais pas Béjaïa »
3- les ensembles de formules suivants sont-ils satisfaisables ?
// il existe I tel que qlq soit p, I(P)= 1 ?
2- Représenter les assertions suivantes en logique propositionnelle
F = {a ˅ b ˅ c; ┐a ˅ b; ┐a ˅ c; ┐b; ┐c}
Il pleut aujourd'hui G = {a ˅ b; ┐a; ┐b}
il ne pleut pas aujourd'hui H = { a ˅ b; a ˅ c ; ┐b ˅ ┐c ; ┐a}
s'il pleut aujourd'hui et quelqu'un ne porte pas de parapluie il
va tomber malade Exercice 3 :
Si quelqu'un tombait malade, soit il ne portait pas de
Pour chacune des formules ci-dessous, indiquer une formule
parapluie, soit il sortait sans veste
logiquement équivalente et telle que: - les seules variables
propositionnelles utilisées sont p et q; - les seules connecteurs sont et
. 1. p q 2. p → q 3. p ↔ q
1
Exercice 4 :
Soit le raisonnement suivant 2- Prouver la proposition A ʌ C ʌ D avec la résolution :
« - Quand il fait froid, je mets ma veste ou je ne sors pas. ┐A→B
B→A
- Je ne reste à la maison que sans veste et par temps chaud.
A→ (C ʌ D)
Donc si je ne mets pas ma veste, c’est qu’il fait chaud. »
1- Formaliser ce raisonnement en utilisant les variables suivantes : Exercice 8:
P : il fait froid, Convertir les phrases suivantes en forme de clauses.
Q : je mets ma veste, (a) p ∧ q ⇒ r ∨ s (c) p ∨ q ⇒ r ∨ s
R : je reste à la maison. (b) ¬(p ∨ q ∨ r) (d) ¬(p ∧ q ∧ r)
2- Montrer que le raisonnement ci-dessus est correct (valide) : Exercice 9:
• Considérez les phrases suivantes: (4 vraies déclarations)
Exercice 5 : 1) Les mammifères boivent du lait
Considérant la liste des axiomes suivants : 2) L'homme est mortel
1. A→(B→A), 3) L'homme est un mammifère
2. (¬A→¬B)→(B→A), 4) Ali est un homme
3. ¬¬A→A, • Prouver: 5) Ali boit du lait.
4. A→A. • Prouver: 6) Ali est mortel
Représenter toutes les phrases sous une forme de clauses
En utilisant la règle d’inférence du Modus Ponens, prouver les Prouver 5 et 6 en utilisant modus ponens
Prouver 5 et 6 en utilisant la résolution
déductions suivantes: A⊢B→A.
Exercice 10:
Exercice 6 :
Quels sont les résultats de l'application de la résolution propositionnelle
1- Convertir en logique Propositionnelle:
aux paires de clauses suivantes?
- Il pleut, il neige ou il fait sec.
(a) {p, q, ¬r} et {r, s} - Il fait chaud.
(b) {p, q, r} et {r, ¬s, ¬t} - Il ne pleut pas.
(c) {q, ¬q} et {q, ¬q}
- Il ne neige pas.
(d) {¬p, q, r} et {p, ¬q, ¬r}
- S'il fait beau, alors c'est bon de marcher.
Exercice 7: - Si le temps est sec et chaud, il fait beau.
1- Montrer que A╞ B en utilisant la résolution 2- Prouve par résolution: "Il est bon de marcher"
A = {P → R ; Q → R} B = (P ˅ Q ) → R 2
ème
Université d’Alger 1 Ben Youcef BenKhedda 3 année Système Informatique (L3-SI)
Département Mathématiques et Informatique Série de TD
Intelligence Artificielle (IA)
Représentation Logique Donner la négation des 3 dernières formules et les traduire en langage
naturel.
des Connaissances
Exercice 12 :
Traduire les formules suivantes en langage naturel:
II. Logique du Premier Ordre : ∀x [ (Voiture (x) ʌ Moteur_Puissant (x) ʌ Roues (x, 4) ) →
Rapide (x)]
Exercice 11 :
∀x ∀y [ (Parent (x, y) ʌ Ancêtre (y)) → Ancêtre (x) ]
Traduire en logique du premier ordre: ∀x ∀y [ ( Voiture (x) ʌ Sur_la_Route (x, y) ʌ Rapide (y) ʌ
1) Tout le monde est content. Conditions_Normales (y) ) → Vitesse _autorisée (x) ]
2) Tout le monde a un père
3) Il y a au moins un enseignant. Exercice 13 :
4) Personne ne peut être un père de lui-même
5) Il y a au moins deux médecins. Y a-t-il quelqu'un qui est une belle-mère de Pierre?
6) Les médecins ne sont pas des avocats. - mère (x, z) ʌ mariée (z, y) → belle-mère (x, y)
7) Si quelqu'un est une mère de quelqu'un d'autre, alors ce dernier - femelle (x) ʌ parent (x, y) → mère (x, y)
ne peut pas être une mère de l'autre. - femme (Marianna)
8) Tout le monde a au plus une mère. - parent (Marianna, Marie)
9) Les médecins traitent tout le monde. - marié (Marie, Pierre)
10) Les médecins poursuivent en justice s'ils sont poursuivis.
11) Tous les employés ont un revenu. Exercice 14 :
12) Certains employés sont en vacances.
13) Aucun employé n'est au chômage. Transformer la formule suivante en un ensemble de clauses
14) Certains employés ne sont pas satisfaits de leur salaire politique.
┐∀x ∃y [∀z (R(x, y, z) → ∀u (S (x, y) ˅ T (y, z, u))) ʌ
15) Je voyage toujours quelque part non loin de la ville où je vis.
16) Je voyage parfois quelque part non loin de la ville où je vis. ∃k S (x, y, k)].
17) Je visite parfois tous mes endroits préférés non loin de la ville Unifier les littéraux suivants:
où je vis. 1- P(x, f(x), g(y, z)) et P(f(z), k; v))
2- P(x, f(x), v) et P(f(z), x, v)).
3
Exercice 15 : Exercice 17 :
1) Chaque boule est rouge, verte ou bleue Vérifier par résolution le raisonnement suivant:
2) Si x est à gauche de y alors x n'est pas à droite de y
3) La boule rouge est à gauche de la boule verte « Chaque animal dans cette pièce est un chat ou un oiseau.
4) La boule b est verte et la boule a n'est pas verte Par conséquent, il y a un animal dans cette pièce qui est un chat ou un
oiseau. »
Traduire en formules de premier ordre
Vérifiez par résolution si la boule a est bleue. Exercice 18:
Exercice 16 : Soit les phrases suivantes :
Un déplacement de l'endroit x à l'endroit y est possible dans un jeu, s’il 1) Pour tout problème, il y a quelqu’un qui l’a créé.
y a une flèche entre x et y. 2) Seuls les gens imprudents créent des problèmes.
3) Ne sont blâmés que des gens imprudents.
4) Les gens imprudents blâmés ne créent pas de problèmes.
5) Il y a des problèmes.
6) Il y a des gens imprudents non blâmés.
Représenter ces phrases en logique des prédicats
Donner les formes de Skolem correspondant à chaque phrase
Prouver par résolution : {(1), (2), (3), (4), (5)} ╞ (6)
Considérer les conditions suivantes pour un jeu particulier:
1) De chaque endroit, il y a un mouvement.
2) Chaque fois qu'il y a un mouvement de x à y, il y a aussi un
mouvement de y à x.
3) Pour tous les endroits x; y; z, s'il y a des mouvements de x à y
et de x à z alors il y a aussi un mouvement de y à z.
Exprimer ces conditions dans la logique de prédicats.
Vérifier par résolution que « De chaque endroit, il y a un
mouvement vers lui-même. »
Université d’Alger 1 Ben Youcef BenKhedda 3ème année Système Informatique (L3-SI)
Département Mathématiques et Informatique Série de TD
Intelligence Artificielle (IA)
Résolution de Problèmes colonne vide la plus à gauche, donner une
démonstration des stratégies de recherche :
Problème 1 :
• Retour en arrière
On considère la hiérarchie de répertoires suivante : • En Largeur d’abord
. : mon_repertoire rep tata toto tutu • En profondeur d’abord
./mon_repertoire: directory loto lulu
./mon_repertoire/directory: auto moto velo Problème 3 :
./rep: aaa chato gato rado rato
On considère le problème de "la traversée du
./rep/aaa: fado java torot
pont" qui est le suivant : quatre personnes
doivent traverser un pont en 17 minutes.
1- Dessiner l'arborescence de ce répertoire.
Chacune d'entre elles marche à une vitesse
2- Donner la liste des fichiers contenant le mot
maximale donnée. Une personne peut
« to » fournie par une recherche en profondeur.
traverser le pont en 1 minute, une autre en 2
3- Donner la liste des fichiers contenant le mot
minutes, une autre en 5 minutes et la
« to » fournie par une recherche en largeur.
dernière en 10 minutes.
Il est impossible de traverser le pont sans
Problème 2 torche, et ces quatre personnes n'ont en tout
qu'une torche. Le pont ne peut supporter que
Le but du problème des N reines est de placer N le poids de 2 personnes et le temps de
reines sur un échiquier de telle sorte qu'aucune reine parcourt est celui de la plus lente.
n'en attaque une autre. (Une reine attaque n'importe 1- Proposer une modélisation du problème
quelle pièce dans la même rangée, colonne ou 2- Dessinez le début de l'arbre de recherche
diagonale.) La figure suivante montre une tentative
de solution échouée de 8 reines : la reine dans la Problème 4 :
colonne la plus à droite est attaquée par la reine en
haut à gauche. Considérer la carte suivante. Le but est de
trouver le chemin le plus court de A vers I.
Le coût de chaque connexion est indiquée.
Une heuristique h est donnée comme suit :
1- Proposer une formalisation de ce problème Nosed A B C D E F G H I
2- Préciser la taille de l’espace de recherche pour 8 h 10 4 5 10 10 3 3 4 0
reines -
- 1- Appliquez la recherche A* en utilisant h.
On considère un échiquier de 4 reines, et que - Donner le chemin solution ainsi que son coût.
chaque nouvelle reine est placée dans la
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
PDF Compressor Free Version
ème
Université d’Alger 1 Ben Youcef BenKhedda 3 année Système Informatique (L3-SI)
Département Mathématiques et Informatique Série de TD
Intelligence Artificielle (IA)
Représentation Graphique Déduire par le mécanisme d'inférence de nouvelles connaissances
du réseau construit
des Connaissances
Exercice 2 :
Construire un réseau sémantique représentant :
I. Réseaux Sémantiques (RS) : - Youcef étudiant L1, 18 ans.
- Hassiba étudiante L2, 19 ans.
Exercice 1 :
- Houari étudiant L3, 21 ans.
Construire un réseau sémantique représentant les connaissances - Malika étudiante L2, 20 ans.
suivantes: - Ali étudiant M1, 21 ans.
- Les oiseaux et les mammifères sont les deux des animaux.
- Les animaux peuvent marcher. Construire le réseau sémantique permettant de poser la
question « quelles sont les filles qui sont en L2 » ?
- Les chats sont des animaux et mangent des rongeurs. - Proposer une construction de réseau sémantique pour
- Les chats domestiques sont des variétés de chats qui mangent rependre à cette question
des souris.
Exercice 3 :
- Les chats ont quatre pattes
Représenter sur un même réseau les informations suivantes :
- Morris est un chat domestique.
« Pierre sait qu’il est scientifique, Jone croit que Pierre n’est pas
- Les oiseaux peuvent voler scientifique, Paul ne sait pas que Pierre est scientifique »
- Pingouin, Moineau, Aigle sont tous des oiseaux
- Les pingouins peuvent aussi nager
- Fred est un pingouin
1
Exercice 4 :
Considérez le réseau sémantique suivant:
1) Quels nœuds sont des concepts, et quels nœuds sont des
objets?
2) Décrivez quelques significations possibles des arcs de
propriétés.
3) Quelle est la couleur du vélo de Lilian?
4) Quelle est la couleur du vélo d’un étudiant?
5) Quels sont les points communs entre les VTT et les
opéras?
6) Peut-on dire que Lilian apprécie l’opéra Don Giovanni ?
Exercice 5 :
Extraire les connaissances du réseau sémantique suivant et les
représenter en logique des Prédicats
