TD — Séance 2 — L’IA qui raisonne

TD de la séance 2 d’Introduction à l’intelligence artificielle : logique, inférence, résolution, unification.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Formaliser en logique propositionnelle et du premier ordre, classer des formules par leurs tables de vérité, décider une conséquence logique par les modèles et par réfutation, mettre en FNC et en forme clausale, dérouler les chaînages avant et arrière, unifier des termes et conduire une résolution au premier ordre. Durée : une séance de TD.

NoteConventions

V : vrai, F : faux. Les tables de vérité suivent l’ordre V avant F, la dernière colonne variant le plus vite. Une preuve par réfutation se présente en table numérotée : n°, clause, origine (la base, la négation du but, ou les numéros des deux clauses résolues). Le chaînage avant traite l’agenda comme une file (tête à gauche) ; le chaînage arrière essaie les règles dans l’ordre de l’énoncé et prouve les prémisses de gauche à droite, avec une pile des buts en cours. Variables : minuscules ; constantes : majuscule initiale.

Exercice 1 : le TER de Diamniadio

Coumba se rend chaque matin à l’université par le TER depuis Diamniadio. On note \(G\) : « il y a une grève », \(T\) : « le TER circule », \(A\) : « Coumba arrive à l’heure », \(B\) : « Coumba prend le bus », \(P\) : « il pleut ».

  1. Formaliser : (1) s’il n’y a pas de grève, le TER circule ; (2) Coumba arrive à l’heure, à moins que le TER ne circule pas ; (3) Coumba prend le bus seulement si le TER ne circule pas ; (4) il n’y a ni grève ni pluie ; (5) le TER circule si et seulement s’il ne pleut pas et qu’il n’y a pas de grève ; (6) il est faux que Coumba soit en retard alors que le TER circule.
  2. Deux des six formules sont équivalentes : lesquelles ? Le justifier par des équivalences.
  3. Remplir la table de vérité de \(\varphi_1=(P\to Q)\to(\neg Q\to\neg P)\), \(\varphi_2=(P\lor Q)\land(\neg P\lor\neg Q)\), \(\varphi_3=(P\leftrightarrow Q)\land(P\leftrightarrow\neg Q)\) et \(\varphi_4=((P\to Q)\land(\neg P\to Q))\to Q\).
  4. Classer chaque formule (valide, satisfiable non valide, insatisfiable) ; pour \(\varphi_2\), donner ses modèles sur \((P,Q)\) et une phrase française qui la traduit.
\(P\) \(Q\) \(R\) \(\varphi_1\) \(\varphi_2\) \(\varphi_3\) \(\varphi_4\)
1
2
3
4
5
6
7
8

Exercice 2 : modèles, conséquence et dérivation

La base KB contient \(\neg G\to T\), \(T\to A\) et \(G\to\neg A\) (les symboles de l’exercice 1).

  1. Remplir la table des huit interprétations et donner les modèles de KB.
  2. Décider, par les modèles, si \(\mathrm{KB}\models T\), \(\mathrm{KB}\models A\lor G\), \(\mathrm{KB}\models G\leftrightarrow\neg A\), \(\mathrm{KB}\models\neg T\lor\neg G\).
  3. Le modus ponens seul dérive-t-il \(A\lor G\) de KB ? Qu’en conclure sur la complétude du modus ponens ?
  4. Prouver \(\mathrm{KB}\models A\lor G\) par réfutation (mettre KB et la négation du but en clauses).
\(G\) \(T\) \(A\) \(\neg G\to T\) \(T\to A\) \(G\to\neg A\) KB
1
2
3
4
5
6
7
8

Exercice 3 : le verger de Leuk-le-Lièvre

Leuk-le-Lièvre visite un verger en grille \(3\times3\) ; la case \((i,j)\) est à la ligne \(i\) et à la colonne \(j\). Un ou plusieurs serpents s’y cachent ; dans une case, Leuk entend un sifflement si et seulement si un serpent est dans une case voisine (nord, sud, est, ouest). On note \(Z_{i,j}\) : « un serpent est en \((i,j)\) », \(S_{i,j}\) : « sifflement en \((i,j)\) ». Leuk part de \((1,1)\), case sans serpent, et entend : rien en \((1,1)\), un sifflement en \((1,2)\), rien en \((2,1)\).

  1. Écrire les règles du sifflement en \((1,1)\), \((1,2)\) et \((2,1)\) (équivalences).
  2. Mettre les règles de \((1,2)\) et \((2,1)\) en FNC, en nommant chaque étape.
  3. Numéroter les clauses (1 à 4 pour \((1,2)\), 5 à 8 pour \((2,1)\), 9 et 10 les percepts \(S_{1,2}\) et \(\neg S_{2,1}\), 11 le départ sûr, 12 la négation du but) et prouver \(Z_{1,3}\) par réfutation, en préférant les clauses d’un littéral.
  4. Sans hypothèse sur le nombre de serpents, quelles cases sont sûres ? Combien de configurations de serpents sur les neuf cases sont compatibles avec les percepts ?
n° clause origine (n° + n°)
13
14
15
16
17
18
19
20

Exercice 4 : la rizière de Podor

Un agent commande l’irrigation d’une rizière de Podor. Ses règles, dans cet ordre : (1) \(\mathit{pompe\_ok}\land\mathit{gasoil}\to\mathit{moteur}\) ; (2) \(\mathit{riziere\_inondee}\to\mathit{eau}\) ; (3) \(\mathit{moteur}\land\mathit{vanne\_ouverte}\to\mathit{eau}\) ; (4) \(\mathit{eau}\land\mathit{canal\_propre}\to\mathit{riziere\_inondee}\) ; (5) \(\mathit{pluie}\to\mathit{canal\_propre}\) ; (6) \(\mathit{gasoil}\to\mathit{facture}\) ; (7) \(\mathit{riziere\_inondee}\to\mathit{recolte}\). Les faits, dans cet ordre : \(\mathit{pompe\_ok}\), \(\mathit{gasoil}\), \(\mathit{vanne\_ouverte}\), \(\mathit{pluie}\). Le but est \(\mathit{recolte}\).

  1. Dérouler le chaînage avant : pour chaque tour, le symbole sorti, les compteurs modifiés (\(c_k\) pour la règle \(k\)), les symboles ajoutés et l’agenda. Que se passe-t-il quand un symbole sort une seconde fois ?
  2. Dérouler le chaînage arrière : les buts examinés, dans l’ordre, avec la pile.
  3. À quel appel le test de la pile intervient-il ? Que se passerait-il sans lui ?
  4. Comparer le nombre de symboles traités et de buts examinés ; quels symboles le chaînage avant établit-il sans qu’ils servent au but ?
Tour sort compteurs modifiés ajouté agenda après le tour
1
2
3
4
5
6
7
8
9
10
11
12
13
Appel but pile (buts en cours) établi par
1
2
3
4
5
6
7
8
9
10
11
12

Exercice 5 : le marché Tilène de Ziguinchor

Au marché Tilène, on note \(V(x)\) : \(x\) est vendeur, \(G(x)\) : \(x\) est grossiste, \(F(y,x)\) : \(y\) fournit \(x\), \(P(x,y)\) : \(x\) paie \(y\).

  1. Formaliser : (1) tout vendeur a un fournisseur grossiste ; (2) aucun grossiste n’est vendeur ; (3) un même grossiste fournit tous les vendeurs ; (4) tout vendeur paie chacun de ses fournisseurs.
  2. Évaluer chaque formule dans la structure de domaine \(\{\mathit{Mame},\mathit{Lamine},\mathit{Sokhna},\mathit{Bocar}\}\) où \(V=\{\mathit{Mame},\mathit{Lamine}\}\), \(G=\{\mathit{Sokhna},\mathit{Bocar}\}\), \(F=\{(\mathit{Sokhna},\mathit{Mame}),(\mathit{Bocar},\mathit{Lamine})\}\), \(P=\{(\mathit{Mame},\mathit{Sokhna})\}\), en donnant un témoin ou un contre-exemple.
  3. Mettre (1) et (3) en forme clausale ; expliquer pourquoi l’une donne une fonction de Skolem et l’autre une constante.
  4. Écrire la négation de (3) en forme prénexe, puis en français.
formule vraie ou fausse témoin ou contre-exemple
(1)
(2)
(3)
(4)

Exercice 6 (approfondissement) : unification et résolution au premier ordre

  1. Unifier chaque paire, en donnant les appels successifs de l’algorithme et l’UPG, ou la cause de l’échec :

    (1) \(\mathit{Fournit}(x,\mathit{Mame})\) et \(\mathit{Fournit}(\mathit{Sokhna},y)\) (2) \(P(x,g(x))\) et \(P(g(y),z)\) (3) \(Q(x,x)\) et \(Q(f(y),y)\)
    (4) \(R(x,\mathit{Bocar},x)\) et \(R(\mathit{Lamine},y,y)\) (5) \(S(f(x),y,x)\) et \(S(z,g(z),w)\)

  2. Dans une famille de Kolda (\(\mathit{Geniteur}(x,y)\) : \(x\) est un parent de \(y\) ; \(\mathit{GP}\) : grand-parent) : \[\forall x\,\forall y\,\forall z\,((\mathit{Geniteur}(x,y)\land\mathit{Geniteur}(y,z))\to\mathit{GP}(x,z)),\] \(\mathit{Geniteur}(\mathit{Aliou},\mathit{Bocar})\), \(\mathit{Geniteur}(\mathit{Bocar},\mathit{Ndeye})\). Prouver \(\exists w\,\mathit{GP}(\mathit{Aliou},w)\) par résolution, et en extraire \(w\).

  3. On ajoute \(\forall x\,\mathit{Geniteur}(\mathit{pere}(x),x)\). Donner les trois réponses à \(\exists v\,\mathit{GP}(v,\mathit{Ndeye})\), chacune justifiée par une réfutation. Ces trois termes désignent-ils nécessairement trois personnes distinctes ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet