83
Agents Logiques Chap. 7

Agents Logiques

  • Upload
    dionne

  • View
    55

  • Download
    0

Embed Size (px)

DESCRIPTION

Agents Logiques . Chap. 7. Plan. Agents basés sur des connaissances Le monde de Wumpus Logique en général – modèle et entraînement ( entailment ) Logique propositionnelle (booléenne) Equivalence, validité, satisfiabilité Règles d’inférence et preuve de théorème Chaînage avant - PowerPoint PPT Presentation

Citation preview

Page 1: Agents Logiques

Agents Logiques

Chap. 7

Page 2: Agents Logiques

Plan• Agents basés sur des connaissances• Le monde de Wumpus• Logique en général – modèle et entraînement

(entailment)• Logique propositionnelle (booléenne)• Equivalence, validité, satisfiabilité• Règles d’inférence et preuve de théorème

– Chaînage avant– Chaînage arrière – Règle de Résolution

Page 3: Agents Logiques

Base de connaissances

• Base de connaissances = ensemble de phrases dans un langage formel

• Approche déclarative pour construire un agent (ou un système) :– Tell: lui dire ce qu’il doit savoir(Approche procédurale: dire comment faire – étape par étape)

• Ensuite, il peut se demander (Ask) ce qu’il a à faire – les réponses doivent suivre la KB (conséquence logique)

• On peut voir un agent selon son niveau de connaissances• i.e., ce qu’ils savent, indépendamment de comment c’est implanté

• Ou au niveau d’implantation– i.e., structures de données dans la KB et algorithmes pour les manipuler

Page 4: Agents Logiques

An agent simple basé sur connaissances

• L’agent doit être capable de:– Représenter les états, les actions, etc. (un formalisme de représentation)– Intégrer de nouvelles perceptions– Mettre à jour la représentation du monde (modifier KB)– Déduire des propriétés cachées du monde (conséquences)– Déduire des actions appropriées (prendre des décisions – conséquences)

Page 5: Agents Logiques

Description de PEAS dans le monde de Wumpus

• Mesure de performance– Or+1000, mort -1000– -1 par étape, -10 pour utiliser la flèche

• Environnement– Objets: wumpus, agent, fosses, or– Carrés adjacents au wumpus sentent fort (smelly)– Carrés adjacents à une fosse sentent du brises (breezy)– On voit briller (Glitter) ssi l’or est dans le carré– Tirer (Shooting) tue le wumpus si on est face à – Tirer utilise la seule flèche disponible– Saisir (Grabbing) prend l’or si dans le même carré– Relâcher (Releasing) laisse l’or dans le carré

• Senseurs: Puanteur (Stench), Brise (Breeze), Éclat (Glitter), Coup (Bump), Cri (Scream)

• Actuateurs: Left turn, Right turn, Forward, Grab, Release, Shoot

Page 6: Agents Logiques

Caractéristiques du monde de Wumpus

• Observable complètement Non – seulement des perceptions locales

• Déterministe Oui – Le résultat spécifié exactement• Épisodique Non – séquentielle au niveau d’actions• Statique Oui – Wumpus et fosses ne bougent pas• Discret Oui• Seul-agent? Oui – L’agent est le seul à bouger dans

l’environnement

Page 7: Agents Logiques

Explorer le monde de wumpus

Page 8: Agents Logiques

Explorer le monde de wumpus

Page 9: Agents Logiques

Explorer le monde de wumpus

Page 10: Agents Logiques

Explorer le monde de wumpus

Page 11: Agents Logiques

Explorer le monde de wumpus

Page 12: Agents Logiques

Explorer le monde de wumpus

Page 13: Agents Logiques

Explorer le monde de wumpus

Page 14: Agents Logiques

Explorer le monde de wumpus

Page 15: Agents Logiques

Rôles de la ligique

• Peut-on reproduire le raisonnement en logique?

• Pourquoi logique?– Une représentation formelle

• Pour décrire les connaissances et les faits• E.g. AB, A

– Un mécanisme d’inférence prouvé: pour raisonner à partir des connaissances et des faits• E.g. règle Modus Ponens: A, AB |- B

Page 16: Agents Logiques

Logique en général• Les logiques sont des langages formels pour représenter des

informations tel que des conclusions peuvent être tirées.• La syntaxe définit les règles pour écrire des phrases du langage• La sémantique définit le “sens” des phrases

– i.e., définit la vérité d’une phrase dans un monde

• E.g., le langage d’arithmétique– x+2 ≥ y est une phrase; x2+y > {} n’est pas une phrase– x+2 ≥ y est vrai ssi le nombrer x+2 n’est pas plus petit que y– x+2 ≥ y est vrai dans un monde où x = 7, y = 1– x+2 ≥ y est faux dans in monde où x = 0, y = 6

• E.g. le français– « Mets est une dans » n’est pas une phrase– « Je mange une pomme » est une phrase– « Je me promène » n’est pas vrai maintenant– « Je donne un cours » est vrai

Page 17: Agents Logiques

Entraînement/Implication (Entailment)

• Entraînement signifie qu’une chose suit sémantiquement une autre (╞ ):

KB ╞ α• La base de connaissances KB entraîne la phrase α ssi α

est vrai dans tous les mondes où KB est vrai

– E.g., la KB contenant “the Giants won” et “the Reds won” entraîne “Either the Giants won or the Reds won”

– E.g., x+y = 4 entraîne 4 = x+y

– L’entraînement est une relation entre des phrases qui est basée sur la sémantique• On ne peut pas créer cette relation n’importe comment• E.g. x+y = 4 ╞ x-y = 4 ne doit pas être créée de façon générale.

Page 18: Agents Logiques

Modèle• Les logiciens pensent typiquement en terme de modèles, qui sont

des mondes structurés formellement, par rapport auxquels la vérité est évaluée.

• On dit que m est un modèle d’une phrase α si α est vrai dans m

• M(α) est l’ensemble de modèles de α

• On note KB ╞ α ssi M(KB) M(α)

– E.g. KB = Giants won and Red won – α = Giants won

Page 19: Agents Logiques

Entraînement dans le monde de wumpus

Situation après avoir rien détecté dans [1,1], bougé à droite et senti la brise à [2,1]

Considérer les modèles possibles pour KB en supposant il y a seulement des puits

3 choix booléens 8 modèles possibles

Page 20: Agents Logiques

Modèles Wumpus(mondes possibles)

Page 21: Agents Logiques

Modèles Wumpus

• KB = règles du monde wumpus + observations

Page 22: Agents Logiques

Modèles Wumpus

• KB = règles du monde wumpus + observations• α1 = "[1,2] est sécuritaire", KB ╞ α1, prouvé par model

checking

Page 23: Agents Logiques

Modèles Wumpus

• KB = règles du monde wumpus + observations

Page 24: Agents Logiques

Modèles Wumpus

• KB = règles du monde wumpus + observations• α2 = "[2,2] est sécuritaire", KB ╞ α2

Page 25: Agents Logiques

Inférence• KB ├i α = la phrase α peut être dérivée de KB par une

procédure i qui manipule les symboles et des expressions (on verra comment définir une telle procédure)

• Adéquation (Soundness): i est adéquate si quand KB ├i α est vrai, KB╞ α l’est aussi.

• Complétude (Completeness): i est complète si quand KB╞ α est vrai, KB ├i α l’est aussi

• À venir: nous allons définir une logique (logique du premier ordre) qui est suffisamment expressive pour exprimer presque tout ce qu’on veut exprimer, et pour laquelle il existe une procédure d’inférence à la fois adéquate et complète.

• C’est-à-dire, la procédure peut répondre à toute question dont la réponse suit logiquement KB

Page 26: Agents Logiques

Logique propositionnelle: Syntaxe

• La logique propositionnelle est la logique la plus simple pour illustrer les idées de base

• Syntaxe = règle de grammaire

• Les symboles de proposition P1, P2 etc. sont des phrases– Si S est une phrase, S est une phrase (négation)– Si S1 et S2 sont des phrases, S1 S2 est une phrase (conjonction)– Si S1 et S2 sont des phrases, S1 S2 est une phrase (disjonction)– Si S1 et S2 sont des phrases, S1 S2 est une phrase (implication)– Si S1 et S2 sont des phrases, S1 S2 est une phrase

(biconditionnel)

Page 27: Agents Logiques

Logique propositionnelle: Sémantique

Chaque modèle spécifie la valeur vrai/faux pour un symbole de proposition

E.g. P1,2 P2,2 P3,1

false true false

Avec ces symboles, 8 modèles possibles peuvent être énumérés automatiquement

Règles pour évaluer la vérité par rapport à un modèle m:S is true iff S is false S1 S2 is true iff S1 is true and S2 is trueS1 S2 is true iff S1is true or S2 is trueS1 S2 is true iff S1 is false or S2 is true i.e., is false iff S1 is true and S2 is falseS1 S2 is true iff S1S2 is true and S2S1 is true

Processus récursif simple pour évaluer une phrase arbitrairement complexe, e.g.,P1,2 (P2,2 P3,1) = true (true false) = true true = true

Page 28: Agents Logiques

Table de vérité pour les connecteurs logiques

Pour ce système avec 2 symboles de proposition:- 4 mondes possibles

Page 29: Agents Logiques

Phrase dans le monde de Wumpus

Supposons que Pi,j est vrai si il y a une fosse à [i, j].Et Bi,j est vrai si il y a une brise à [i, j].

P1,1

B1,1

B2,1

• "Pits cause breezes in adjacent squares” (une fosse cause la brise dans les carrés adjacents)B1,1 (P1,2 P2,1)B2,1 (P1,1 P2,2 P3,1)

Page 30: Agents Logiques

Table de vérité pour inférence

À vérifier

Vérifier pour chaque ligne où KB est vraie (modèle de KB) si la conclusion est aussi vraie.

Page 31: Agents Logiques

Inférence par énumération• Profondeur d’abord pour énumérer tous les modèles• Procédure adéquate et complète

• C’est une approche sémantique• Pour n symboles, complexité en temps O(2n), en espace O(n)

Page 32: Agents Logiques

Méthodes de preuve• Méthodes de preuve divisées grosso modo en 2 catégories:

– Model checking (Vérification de modèles)• Énumération en utilisant une table de vérité (toujours exponentiel en n)• Retour en arrière (backtracking) amélioré, e.g., Davis--Putnam-

Logemann-Loveland (DPLL)• Recherche heuristique dans l’espace de modèles (adéquate mais non

complet)e.g., algorithme hill-climbing qui favorise le conflit minimal

– Application de règles d’inférence• Génération légitime (sound) de phrases nouvelles à partir des

anciennes• Preuve = une séquence d’applications de règles d’inférence• Peut utiliser les règles d’inférence comme opérateur dans un algorithme

de recherche standard• Typiquement, ceci demande à transformer une phrase en une forme

normale (pour simplifier la procédure)

Page 33: Agents Logiques

Par ordinateur?• L’ordinateur a beaucoup de problème pour manipuler la

sémantique– Il peut faire la vérification dans une table de vérité– Mais complexité exponentielle

• Une approche syntaxique– Manipulations des expressions pour tenter d’arriver à la

conclusion– Procédure d’inférence

• En maths?

Page 34: Agents Logiques

Équivalences logiques• 2 phrases sont logiquement équivalentes ssi elles sont

vraies dans les mêmes modèles : α ≡ ß ssi α╞ β et β╞ α

Page 35: Agents Logiques

Comment vérifier l’équivalence?

• Vérifier dans la table de vérité si 2 expressions ont toujours les mêmes valeurs de vérité

• A B et (A) B sont équivalentes?

• Utilité des équivalences– Une expression peut être transformée en une

autre équivalente

Page 36: Agents Logiques

Validité et satisfiabilité d’une phrase

Une phrase est valide si elle est vrai dans tous les modèles,e.g., True, A A, A A, (A (A B)) B

(tautologie)

La validité est reliée à l’inférence via le Théorème de déduction:KB ╞ α si et seulement si (KB α) est valide

Une phrase est satisfiable si elle est vraie dans quelques modèlese.g., A B, C

Une phrase est insatisfiable si elle n’est vraie dans aucun modèlee.g., AA

La satisfiabilité est reliée à l’inférence via la propriété suivante:KB ╞ α si et seulement si (KB α) est insatisfiable (preuve par contradiction/réfutation)

Page 37: Agents Logiques

Méthodes de preuve• Méthodes de preuve divisées grosso modo en 2 catégories:

– Model checking (Vérification de modèle)• Énumération en utilisant une table de vérité (toujours exponentiel en n)• Retour en arrière (backtracking) amélioré, e.g., Davis--Putnam-

Logemann-Loveland (DPLL)• Recherche heuristique dans l’espace de modèles (adéquate mais non

complet)e.g., algorithme hill-climbing qui favorise le conflit minimal

– Application de règles d’inférence• Génération légitime (sound) de phrases nouvelles à partir des

anciennes• Preuve = une séquence d’applications de règles d’inférence• Peut utiliser les règles d’inférence comme opérateur dans un algorithme

de recherche standard• Typiquement, ceci demande à transformer une phrase en une forme

normale (pour simplifier la procédure)

Page 38: Agents Logiques

Règles d’inférence• Forme générale d’une règle

ab

– Signification: Si a est accepté, alors on accepte aussi b

– Une procédure de preuve• Ensemble de phrases KB0

• Pour une règle d’inférence, si a est dans KB0, alors on ajoute dans KB0: KB1

• Si dans un KBn, on voit la conclusion C, alors C est prouvée.• On notera KB0 ├ C

Page 39: Agents Logiques

Règles: exemples• Modus Ponens

a, a b b

• Modus Tolensb, a b a

• Et-éliminationa b a

• Et-introduction a, ba b

Page 40: Agents Logiques

Exemple de preuve• KB0 = {A, A B, C, BC D} a = D KB0 ├ a ?1. KB1 avec MP: {A, A B, C, BC D, B}2. KB2 avec Et-intro: {A, A B, C, BC D, B, BC}3. KB2 avec MP: {A, A B, C, BC D, B, BC, D}4. Prouvé #

• Recherche– KB0, KB1, KB2 comme états– Une application de règle d’inférence = successeur

Page 41: Agents Logiques

Règle de RésolutionConjunctive Normal Form (CNF) (forme normale conjonctive)

conjonction de disjonctions de littéraux= clauses

E.g., (A B) (B C D)

• Règle de résolution (pour CNF):li … li … lk, m1 … mj … mn

li … li-1 li+1 … lk m1 … mj-1 mj+1 ... mn

où li et mj sont des littéraux complémentaires(i.e. li = mj)

E.g., P1,3 P2,2 , P2,2

P1,3

• Règle de résolution est adéquate et complète pour la logique de proposition

Page 42: Agents Logiques

RésolutionUne démonstration informelle de l’adéquation de la règle de

résolution: l1 … li-1 li li+1 … lk ≡ (li … li-1 li+1 … lk) lim1 … mj-1 mj mj+1 ... mn ≡ mj (m1 … mj-1 mj+1 ... mn)

(li … li-1 li+1 … lk) li mj (m1 … mj-1 mj+1 ... mn)

(li … li-1 li+1 … lk) (m1 … mj-1 mj+1 ... mn)

≡ li … li-1 li+1 … lk m1 … mj-1 mj+1 ... mn

Page 43: Agents Logiques

RésolutionUne démonstration informelle de l’adéquation de la règle de

résolution: A B C ≡ (A C) BD B E ≡ B (D E)

(A C) B B (D E)

(A C) (D E)

≡ A C D E

Page 44: Agents Logiques

Conversion en CNFB1,1 (P1,2 P2,1)

1. Éliminer , remplacer α β par (α β)(β α).(B1,1 (P1,2 P2,1)) ((P1,2 P2,1) B1,1)

2. Éliminer , remplacer α β par α β.(B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

3. Déplacer vers l’intérieur en utilisant les règles de Morgan et double-négation:

(B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

4. Appliquer la loi de distributivité ( sur ) et aplatir :(B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1)

Page 45: Agents Logiques

Algorithme de preuve par Résolution

• Preuve par contradiction/réfutation, i.e., montrer que KBα est insatisfiable (ou monter que ça mène à la contradiction ( ) en utilisant la règle de résolution

Page 46: Agents Logiques

Exemple

KB = (B1,1 (P1,2 P2,1)) B1,1

α = P1,2

Page 47: Agents Logiques

Chaînage avant et arrière• Forme Horn (plus restreinte)

KB = conjonction de Clauses Horn– Clause Horn =

• Symbole de proposition; ou• (conjonction de symboles) symbole

– E.g., C, (B A), (C D B)

• Modus Ponens (Pour forme Horn): complet pour KB en forme Horn

α1, … ,αn, α1 … αn β

β

• Peut être utilisé avec chaînage avant (forward chaining) ou chaînage arrière (backward chaining).

• Ces algorithmes sont très naturels et demandent un temps linéaire

Page 48: Agents Logiques

Chaînage avant• Idée: Activer une règle dont les prémisses sont

satisfaites dans KB,– Ajouter son conclusion dans KB, jusqu’à la requête soit trouvée

dans KB

Page 49: Agents Logiques

Algorithme

• Chaînage avant est adéquat et complet pour KB en Horn

Page 50: Agents Logiques

Exemple de chaînage avant

Page 51: Agents Logiques

Exemple de chaînage avant

Page 52: Agents Logiques

Exemple de chaînage avant

Page 53: Agents Logiques

Exemple de chaînage avant

Page 54: Agents Logiques

Exemple de chaînage avant

Page 55: Agents Logiques

Exemple de chaînage avant

Page 56: Agents Logiques

Exemple de chaînage avant

Page 57: Agents Logiques

Exemple de chaînage avant

Page 58: Agents Logiques

Preuve de complétude(Prouver qu’une conclusion sémantiquement

valide sera ajouté dans la KB)

• Chaînage avant dérive toute phrase atomique qui est entraînée par KB

1. Il atteint un point fixe où aucune phrase atomique nouvelle est dérivée

2. Considérer cet état final comme un modèle m, qui assigne true/false aux symboles

3. Chaque clause dans la KB originale est vraie dans m a1 … ak b

4. Donc, m est un modèle de KB5. Si KB╞ q, q est vraie dans chaque modèle de KB, y

compris m6. Donc, q peut être dérivée.

Page 59: Agents Logiques

Chaînage arrièreIdée: travailler vers arrière à partir de la requête q:

Pour prouver q par chaînage arrière,Si q est déjà connue, ouProuver par chaînage arrière toutes les prémisses d’une règle

d’inférence qui conclut en q

Éviter des boucles : vérifier si un nouveau sous-but est déjà dans le stack de buts (- comparer avec la recherche dans un graphe)

Éviter la répétition : vérifier si le nouveau sous-but1. est déjà prouvé vrai, ou2. a déjà échoué dans sa preuve

Page 60: Agents Logiques

Exemple de chaînage arrière

Page 61: Agents Logiques

Exemple de chaînage arrière

Page 62: Agents Logiques

Exemple de chaînage arrière

Page 63: Agents Logiques

Exemple de chaînage arrière

Page 64: Agents Logiques

Exemple de chaînage arrière

Page 65: Agents Logiques

Exemple de chaînage arrière

Page 66: Agents Logiques

Exemple de chaînage arrière

Page 67: Agents Logiques

Exemple de chaînage arrière

Page 68: Agents Logiques

Exemple de chaînage arrière

Page 69: Agents Logiques

Exemple de chaînage arrière

Page 70: Agents Logiques

Chaînage avant vs. arrière• Ch. avant est une procédure data-driven, automatique,

inconsciente du problème à résoudre,– e.g., reconnaissances d’objet, décisions routine

• Peut faire beaucoup de travail non pertinent au but

• Ch. arrière est une procédure goal-driven, appropriée pour la résolution du problème,– e.g., où sont mes clés? Comment puis-je entrer dans un

programme de doctorat?

• Complexité de Ch. arrière peut être beaucoup moins que linéaire à la taille de KB

Page 71: Agents Logiques

Méthodes de preuve• Méthodes de preuve divisées grosso modo en 2 catégories:

– Model checking (Vérification de modèle)• Énumération en utilisant une table de vérité (toujours exponentiel en n)• Retour en arrière (backtracking) amélioré, e.g., Davis--Putnam-

Logemann-Loveland (DPLL)• Recherche heuristique dans l’espace de modèles (adéquate mais non

complet)e.g., algorithme hill-climbing qui favorise le conflit minimal

– Application de règles d’inférence• Génération légitime (sound) de phrases nouvelles à partir des

anciennes• Preuve = une séquence d’applications de règles d’inférence• Peut utiliser les règles d’inférence comme opérateur dans un algorithme

de recherche standard• Typiquement, ceci demande à transformer une phrase en une forme

normale (pour simplifier la procédure)

Page 72: Agents Logiques

Inférence propositionnelle efficace

2 familles d’approches efficaces pour l’inférence propositionnelle

• Algorithmes de recherche en arrière complète– Algorithme DPLL (Davis, Putnam, Logemann, Loveland)

• Algorithmes de recherche locale incomplète– Algorithme WalkSAT

Page 73: Agents Logiques

Algorithme DPLLDéterminer si une phrase de logique propositionnelle en entrée (en

CNF) est satisfiable.

Améliorations sur l’énumération de la table de vérité:1. Terminaison hâtive

Une clause est vraie si chaque littéral est vrai.Une phrase (conjonction de clauses) est fausse si une de ses clauses est

fausse.

2. Heuristique de symbole purSymbole pur: toujours apparaître avec le même « signe » dans toutes les

clauses. e.g., Dans les 3 clauses (A B), (B C), (C A), A et B sont purs, C n’est

pas pur. Faire un symbole pur vrai.

3. Heuristique de clause unitéClause unité: seulement un littéral dans la clauseLa seule littérale dans la clause doit être vraie.

(Comparer avec la recherche heuristique)

Page 74: Agents Logiques

Algorithme DPLL

Page 75: Agents Logiques

Algorithme WalkSAT• Algorithme incomplet, recherche locale• Fonction d’évaluation : heuristique de conflit min pour

minimiser le nombre de clauses insatisfaites

• Compromis entre voracité et le caractère aléatoire

• Principe:– Assignations de true/false aux propositions– Dans une clause non satisfaite, flip une assignation d’une

proposition• Aléatoirement (avec prob. p)• Qui maximise le nombre de clauses satisfaites

Page 76: Agents Logiques

Algorithme WalkSAT

Page 77: Agents Logiques

Problèmes de satisfiabilité difficiles

• Considérer des phrases 3-CNF aléatoires. e.g.,(D B C) (B A C) (C B E) (E D B) (B E C)

m = nb. de clauses n = nb. de symbols

– Problème difficiles semblent apparaître autour de m/n = 4.3 (point critique)

Page 78: Agents Logiques

Problèmes de satisfiabilité difficiles

Page 79: Agents Logiques

Problèmes de satisfiabilité difficiles

• Temps médiane pour 100 phrases 3-CNF aléatoires satisfiables, n = 50

Page 80: Agents Logiques

Agent basé sur inférence dans le monde de wumpus

Un agent du monde wumpus utilisant la logique propositionnelle :

- Exprimer les observations et les règles du jeuP1,1 W1,1 Bx,y (Px,y+1 Px,y-1 Px+1,y Px-1,y) (en réalité: B2,2 (P2,3 P2,1 P3,2 P1,2), …)Sx,y (Wx,y+1 Wx,y-1 Wx+1,y Wx-1,y)W1,1 W1,2 … W4,4 W1,1 W1,2 W1,1 W1,3 …

64 symboles de proposition distincts, 155 phrases

Page 81: Agents Logiques
Page 82: Agents Logiques

• KB contient des phrases "physiques" pour chaque carré

• Pour chaque moment t et chaque place [x,y],

Lx,y FacingRight t Forward t Lx+1,y

• Prolifération rapide de clauses• Intractable pour des applications réelles• Vers la logique de prédicats (logique de premier ordre)

Limitation de capacité d’expression de logique propositionnelle

tt

Page 83: Agents Logiques

Sommaire• Les agents logiques appliquent des inférences sur une base de

connaissances pour dériver de nouvelles informations (conclusions) et prendre des décisions

• Concepts de base en logique:– syntaxe: structure formelle de phrases– sémantique: vérité de phrases par rapport aux modèles– entaînement: une phrase nécessairement vrai étant donné une autre– inférence: dériver des phrases à partir des autres phrases– Adéquation (soundness): des dérivations produisent seulement des phrases

impliquée (conséquences logiques)– complétude: des dérivations peuvent produire toutes les phrases impliquées

(conséquences logiques)• Le monde de Wumpus demande la capacité de représenter des

informations partielles et négatives, raisonner pour des cas, etc.• La règle de résolution (et la procédure d’inférence correspondante) est

complète pour la logique de propositions• Chaînage avant et arrière demandent un temps linéaire, sont complets pour

des clauses Horn• Logique propositionnelle manque d’expressivité