Logique des Prédicats du Premier
Ordre
Exercices : Inférence, Unification et Chaînage
Logique et IA
Partie I — Règles d'Inférence en LPO
Les règles d'inférence permettent de dériver de nouvelles formules à partir de formules
connues. En logique du premier ordre, les règles principales sont : Modus Ponens
généralisé, l'instanciation universelle (UI) et l'instanciation existentielle (EI).
Exercice 1 — Instanciation universelle et chaîne d'inférences
Base de connaissances
(1) ∀x∀y Mère(x,y) ⇒ Parent(x,y)
(2) ∀x∀y Père(x,y) ⇒ Parent(x,y)
(3) ∀x∀y Parent(x,y) ⇒ Ancêtre(x,y)
(4) ∀x∀y∀z Ancêtre(x,y) ∧ Ancêtre(y,z) ⇒ Ancêtre(x,z)
(5) Mère(Fatima, Omar)
(6) Père(Omar, Karim)
Prouver par instanciation universelle et Modus Ponens que :
• Ancêtre(Fatima, Karim) est déductible de cette base.
Détaillez chaque étape de la preuve en indiquant la règle appliquée et la substitution
utilisée.
Preuve pas à pas :
Exercice 2 — Modus Ponens généralisé
Base de connaissances (domaine médical)
(1) ∀x Fièvre(x) ∧ Toux(x) ⇒ SuspectGrippe(x)
(2) ∀x SuspectGrippe(x) ∧ TestPositif(x) ⇒ DiagGrippe(x)
(3) ∀x DiagGrippe(x) ⇒ Prescrire(x, Tamiflu)
(4) Fièvre(Ali) ∧ Toux(Ali) ∧ TestPositif(Ali)
Questions :
1. Appliquez le Modus Ponens généralisé pour dériver SuspectGrippe(Ali). Indiquez la
substitution utilisée.
2. Continuez la chaîne pour dériver DiagGrippe(Ali) puis Prescrire(Ali, Tamiflu).
3. Si l'on ajoute le fait Fièvre(Sara) ∧ Toux(Sara) mais pas TestPositif(Sara), peut-on
dériver Prescrire(Sara, Tamiflu) ? Justifiez.
Réponses :
Exercice 3 — Représentation et inférence
Traduisez les phrases suivantes en LPO, puis effectuez les inférences demandées.
Phrases à traduire :
4. Tout étudiant qui réussit tous ses examens obtient son diplôme.
5. Aucun étudiant n'obtient son diplôme sans avoir réussi au moins un examen.
6. Sara est étudiante et elle a réussi l'examen de logique et celui de bases de données.
7. L'examen de logique et l'examen de bases de données sont des examens.
Inférences à dériver :
• Sara a-t-elle obtenu son diplôme ? Justifiez votre raisonnement.
Traductions LPO :
Inférence :
Partie II — Unification
L'unification est le processus qui consiste à trouver une substitution σ rendant deux
expressions logiquement identiques. L'Unificateur le Plus Général (UPG) est la substitution
la moins contraignante permettant d'unifier deux expressions.
Exercice 4 — Calcul des substitutions
Pour chaque paire d'expressions (p, q), trouvez l'unificateur le plus général σ ou indiquez
l'échec d'unification. Justifiez chaque cas.
Expression p Expression q Substitution σ (à trouver)
Aime(x, Marie) Aime(Ahmed, y)
Parent(x, f(x)) Parent(g(y), z)
P(x, g(x), y) P(f(z), g(f(z)), z)
Aime(x, x) Aime(Ali, Marie)
Voisin(x, f(y)) Voisin(f(a), f(b))
Q(x, g(y), x) Q(f(a), g(f(a)),
f(a))
Note : pour les cas d'échec, expliquez pourquoi l'unification est impossible (occur check,
incompatibilité de foncteurs, etc.).
Exercice 5 — Occur check et UPG
Le vérificateur d'occurrence (occur check) empêche de créer des substitutions circulaires.
Pour chaque paire ci-dessous :
• Appliquez l'algorithme d'unification standard.
• Indiquez si l'occur check est déclenché (et pourquoi).
• Si l'unification réussit, donnez l'UPG ; sinon, expliquez l'échec.
a) p = F(x, g(x)) q = F(y, y)
b) p = F(x) q = F(g(x))
c) p = Connaît(x, y) q = Connaît(y, Frère(y))
Analyse des trois paires :
Exercice 6 — Application de l'unification à l'inférence
Base de règles
R1 : ∀x∀y Visite(x,y) ∧ Habite(y,z) ⇒ Connaît(x,z)
R2 : ∀x∀z Connaît(x,z) ⇒ Aime(x,z)
F1 : Visite(Youssef, Laila)
F2 : Habite(Laila, Casablanca)
Questions :
8. Unifiez la prémisse de R1 avec F1 et F2 ; donnez la substitution complète.
9. Appliquez la substitution pour dériver Connaît(Youssef, Casablanca).
10. En appliquant à nouveau l'unification avec R2, dérivez Aime(Youssef, Casablanca).
11. Si on ajoute F3 : Visite(Youssef, f(Laila)), l'unification avec R1 est-elle possible ?
Comparez avec F1.
Détail des unifications et dérivations :
Partie III — Chaînage Avant (Forward Chaining)
Le chaînage avant part des faits connus et applique les règles disponibles pour dériver de
nouveaux faits, jusqu'à atteindre le but recherché ou l'épuisement des règles applicables.
Exercice 7 — Chaînage avant (propositionnel)
Base de faits initiale : A, C, D
Règles :
R1 : A ∧ B ⇒ E
R2 : C ∧ D ⇒ B
R3 : B ∧ C ⇒ F
R4 : E ∧ F ⇒ G
R5 : A ∧ C ⇒ H
Questions :
12. Appliquez l'algorithme de chaînage avant pour dériver G. Tracez chaque itération
(règle appliquée, nouveaux faits ajoutés).
13. Quel est l'ensemble final de faits dérivables ?
14. Modifiez légèrement la base initiale : si D est absent, G est-il encore dérivable ?
Justifiez.
Étape Règle appliquée Fait(s) dérivé(s) Base de faits mise à
jour
1
Exercice 8 — Chaînage avant en LPO
Base de connaissances (domaine familial)
(1) ∀x∀y Mère(x,y) ⇒ Parent(x,y)
(2) ∀x∀y Père(x,y) ⇒ Parent(x,y)
(3) ∀x∀y Parent(x,y) ⇒ Ancêtre(x,y)
(4) ∀x∀y∀z Ancêtre(x,y) ∧ Ancêtre(y,z) ⇒ Ancêtre(x,z)
(5) Mère(Khadija, Amina)
(6) Père(Amina, Yacine)
(7) Père(Yacine, Nour)
Questions :
15. Appliquez le chaînage avant pour dériver tous les faits possibles. Tracez le
processus étape par étape, en précisant l'unification utilisée à chaque application de
règle.
16. Peut-on dériver Ancêtre(Khadija, Nour) ? Si oui, en combien d'étapes minimum ?
17. Ajoutez le fait Père(Nour, Rania). Quels nouveaux faits peut-on dériver
supplémentairement ?
Dérivation complète :
Partie IV — Chaînage Arrière (Backward Chaining)
Le chaînage arrière part d'un objectif à prouver et le décompose récursivement en sous-
objectifs, jusqu'à n'avoir que des faits directement connus dans la base.
Exercice 9 — Chaînage arrière (propositionnel)
Base de faits : P, Q, S
Règles :
R1 : P ∧ Q ⇒ R
R2 : R ∧ S ⇒ T
R3 : T ∧ U ⇒ V
R4 : Q ∧ S ⇒ U
Questions :
18. Prouvez V par chaînage arrière. Dessinez l'arbre AND/OR des sous-objectifs.
19. Tracez le chemin de preuve complet, de l'objectif V jusqu'aux faits de base.
20. Comparez avec le chaînage avant : y a-t-il des règles jamais déclenchées en avant
mais nécessaires en arrière (ou vice-versa) ?
Arbre AND/OR (à compléter) :
Objectif : V
└── ... (à développer)
Exercice 10 — Chaînage arrière en LPO
Base de connaissances (animaux)
(1) ∀y∀z Cochon(y) ∧ Escargot(z) ⇒ PlusRapide(y,z)
(2) ∀z Mince(z) ∧ Rampe(z) ⇒ Escargot(z)
(3) Cochon(Pat)
(4) Mince(Steve)
(5) Rampe(Steve)
Questions :
21. Prouvez PlusRapide(Pat, Steve) par chaînage arrière. Détaillez chaque unification.
22. Listez tous les sous-objectifs générés dans l'ordre, et indiquez comment chacun est
résolu (fait direct ou règle).
23. Peut-on prouver PlusRapide(Steve, Pat) ? Justifiez.
Trace du chaînage arrière :
Sous-objectif Règle / Fait utilisé Substitution σ
Exercice 11 — Comparaison avant / arrière
Base de connaissances (droit)
(1) ∀x Citoyen(x) ∧ MajeurLégal(x) ⇒ DroitDeVote(x)
(2) ∀x Né(x, Maroc) ⇒ Citoyen(x)
(3) ∀x Age(x,a) ∧ a ≥ 18 ⇒ MajeurLégal(x)
(4) Né(Hassan, Maroc)
(5) Age(Hassan, 22)
(6) Né(Lena, France)
(7) Age(Lena, 25)
Questions :
24. Prouvez DroitDeVote(Hassan) par chaînage avant. Tracez toutes les étapes.
25. Prouvez DroitDeVote(Hassan) par chaînage arrière. Comparez l'efficacité avec la
méthode précédente.
26. Que se passe-t-il si l'on tente de prouver DroitDeVote(Lena) dans chaque méthode ?
27. En général, quand est-il préférable d'utiliser le chaînage avant ? Le chaînage arrière
? Donnez des critères précis.
Chaînage avant (Hassan) :
Chaînage arrière (Hassan) :
Analyse comparative :
Partie V — Exercice de Synthèse
Exercice 12 — Système expert simplifié
On modélise un système d'aide au diagnostic automobile. Utilisez toutes les notions vues
(inférence, unification, chaînage) pour répondre aux questions.
Base de connaissances
(1) ∀v MoteurNeDémarre(v) ∧ BatterieVide(v) ⇒ ProblèmeBatterie(v)
(2) ∀v MoteurNeDémarre(v) ∧ ¬BatterieVide(v) ⇒ AutrePannePossible(v)
(3) ∀v ProblèmeBatterie(v) ⇒ Recommander(v, ChargerBatterie)
(4) ∀v VoyantHuile(v) ∧ NiveauHuileBas(v) ⇒ RisquePanneMot(v)
(5) ∀v RisquePanneMot(v) ⇒ Recommander(v, VérifierHuile)
(6) MoteurNeDémarre(Voiture1)
(7) BatterieVide(Voiture1)
(8) VoyantHuile(Voiture1)
(9) NiveauHuileBas(Voiture1)
Questions :
28. Par chaînage avant, dérivez tous les faits possibles concernant Voiture1. Tracez les
étapes.
29. Par chaînage arrière, prouvez Recommander(Voiture1, ChargerBatterie). Détaillez
les unifications.
30. Ajoutez une nouvelle voiture : MoteurNeDémarre(Voiture2). Sans information sur la
batterie, que peut-on conclure ? Quelle règle s'applique et via quel mécanisme ?
31. Si l'on veut prouver ∃ v Recommander(v, VérifierHuile), quelle méthode est la plus
adaptée ? Justifiez et exécutez la preuve.
Question 1 — Chaînage avant :
Question 2 — Chaînage arrière :
Questions 3 et 4 :
Aide-mémoire — Notations
Symbole Signification Exemple
∀x Pour tout x ∀x Humain(x) ⇒ Mortel(x)
∃x Il existe x ∃x Aime(x, Marie)
⇒ Implique A ⇒B
∧ Et (conjonction) A ∧ B
∨ Ou (disjonction) A ∨ B
¬ Non (négation) ¬A
{x/t} Substituer x par t {x/Ali, y/Fès}
UPG Unificateur le Plus Général σ = {x/a, y/b}
σ Substitution (sigma) pσ = qσ
p ≐ q Unifier p et q Aime(x,y) ≐ Aime(Ali,z)