Intelligence Artificielle AI - Prolog : TD4 IA et Logique
Télécharger PDFExercice 1 : Test d’embauche et logique des prédicats
Un test d’embauche consiste à vérifier une règle avec 4 cartes : E, K, 4 et 7.
On sait que :
- chaque carte a d’un côté un nombre et de l’autre une lettre
- la consigne est : si une carte montre une voyelle d’un côté, elle doit montrer un nombre pair de l’autre côté.
a. Introduction des prédicats et fonctions
Définissons les prédicats et fonctions suivants :
- V(x) : x est une voyelle
- P(x) : x est un nombre pair
- Verso(x, y) : "..." est le caractère au verso de la carte portant le signe x (y représentant le verso)
b. Représentation des informations en calcul des prédicats
Les informations peuvent être exprimées sous forme de formules logiques :
- ∀x [V(x) → ∃y (Verso(x, y) ∧ P(y))]
- Verso(E, K)
- Verso(K, 4)
- Verso(4, 7)
- Verso(7, ?)
La loi "le verso du verso redonne le recto" implique que si une carte a un verso, ce verso doit correspondre à une autre carte.
c. Conversion en clauses
Les formules logiques du point b peuvent être converties en clauses :
- ¬V(x) ∨ ¬Verso(x, y) ∨ P(y)
- Verso(E, K)
- Verso(K, 4)
- Verso(4, 7)
- Verso(7, ?)
d. Application de la méthode de résolution
Pour valider la solution, il faut vérifier les cartes suivantes :
- la carte E (voyelle visible, vérification du verso)
- la carte 7 (nombre impair visible, vérification de la consigne)
Si la consigne n’est pas respectée, cela signifie que l’on a oublié de vérifier :
- la présence d’une voyelle au verso d’une carte (ex. : K)
- la présence d’un nombre impair au recto d’une carte (ex. : 7)
e. Dessiner les arbres de dérivation
Les arbres de dérivation doivent illustrer les étapes suivantes :
- Application des règles de prédicats pour vérifier les implications
- Examen des cas possibles (voyelle/non-voyelle, pair/impair)
- Validation de la consigne en testant les cartes pertinentes
f. Application du théorème de Herbrand
Le théorème de Herbrand peut être appliqué pour vérifier que la consigne est respectée en considérant les instances possibles des prédicats.
Exercice 2 : Démonstration en logique des prédicats
Dans le "monde de Tarski", on utilise des prédicats et une relation pour décrire une configuration d’objets.
a. Préparation des formules et clauses
Les formules données sont :
- Pyramide(C) : C est une pyramide
- ∀t [Cube(t) → GaucheDe(C, t)] : Tous les cubes sont à gauche de C
- ∃y ∃z [Cube(y) ∧ Pyramide(z) ∧ GaucheDe(y, z)] : Il existe un cube à gauche d’une pyramide
- ∀u ∀v ∀w [(GaucheDe(u, v) ∧ GaucheDe(v, w)) → GaucheDe(u, w)] : La relation GaucheDe est transitive
L’énoncé à démontrer est :
E : ∃x [Pyramide(x) ∧ GaucheDe(C, x)] : Il existe une pyramide à droite de C.
Conversion en clauses :
- Pyramide(C)
- Cube(t) → GaucheDe(C, t)
- Cube(y) ∧ Pyramide(z) ∧ GaucheDe(y, z)
- (GaucheDe(u, v) ∧ GaucheDe(v, w)) → GaucheDe(u, w)
b. Application de la règle de résolution avec unification
Pour démontrer E, on applique les règles suivantes :
- Utiliser la transitivité de GaucheDe pour établir une relation entre C et une pyramide
- Trouver un cube y tel que GaucheDe(y, z) avec Pyramide(z)
- Unifier les variables pour obtenir une contradiction
FAQ
1. Pourquoi ne faut-il vérifier que certaines cartes dans l’exercice 1 ?
Seules les cartes qui peuvent violer la règle doivent être vérifiées : une voyelle au recto ou un nombre impair au verso.
2. Comment appliquer la transitivité dans l’exercice 2 ?
La transitivité permet de déduire que si un objet A est à gauche de B et B à gauche de C, alors A est à gauche de C.
3. Que signifie le théorème de Herbrand dans ce contexte ?
Il permet de vérifier la validité d’une solution en considérant toutes les instances possibles des prédicats et relations.