Représentation des connaissances Cours 1....

Représentation des connaissances

Cours 1. Logique

Prédicats et arguments

Calcul des propositions

Logique du premier ordre

Objectifs

Manipulation du langage humain par l'ordinateur

Simuler le comportement d'une personne, par exemple :

- apprendre à utiliser un logiciel en lisant le manuel

- s'apercevoir qu'on a été insulté

- rédiger une dissertation sur un sujet donné

Pour cela il faut relier les éléments linguistiques à des

représentations du monde

Des objets qui représentent le sens d'un texte

Prédicats et arguments

êtreNoir(ceChat)

êtreNoir() : prédicat

ceChat : argument

dormir(Luc)

prendre(Luc, leParapluieDeLuc) deux arguments

au-Dessous(température, 0°C)

frère(Luc, Marc)

demander(Luc, Marie, sortirCeSoir) trois arguments

date(mortDeJean-Paul, 2avril2007)

Utilisation

Chacune de ces formules a une valeur : vraie ou fausse

Confronter une représentation sémantique à une base de faits

Exemple

Requête : Est-ce que le vol 123 fait escale à Bombay ?

Base de faits : la liste des vols avec leurs escales, sous la

forme vol(123, Paris, Bombay, Nouméa)

Réponse : Oui

Prédicats et arguments

Chaque argument est une variable

Il peut prendre des valeurs variées

marquer(Zidane, but) : non (on ne peut pas marquer autre chose)

marquerBut(Zidane) : oui

casser(Luc, Marc, figure) : non

casserLaFigure(Luc, Marc) : oui

Compositionnalité

Le sens de la formule est calculable à partir du sens des éléments

Prédicats et arguments

En général 1 à 3 arguments

0 argument : pleuvoir(), faireChaud()

4 arguments : parier(Luc, Marie, LucArrivePremier, 15€)

n arguments : mission(QENO, ..., NanterrePréfecture, LaDéfense,

CharlesDeGaulleEtoile, Auber, ChâteletLesHalles,

GareDeLyon, Nation, Vincennes, ValDeFontenay,

NoisyLeGrandMontDEst, NoisyChamps, Noisiel, Lognes, ...)

Représentations non ambiguës

Les textes sont ambigus

Luc tire sur la poignée

Les représentations sémantiques ne doivent pas l'être

traction(Luc, laPoignée)

tir(Luc, laPoignée, arme)

Représentations uniques

Il y a toujours plusieurs façons de dire la même chose

La représentation sémantique doit être la même

Est-ce que le Samouraï fait les sushi ?

Est-ce qu'ils ont des sushi au Samouraï ?

Est-ce qu'on sert des sushi au Samouraï ?

Le Samouraï fait-il des sushi ?

servir(Samouraï, sushi)

Déductions

Raisonner et aboutir à une conclusion

Exemple

Requête : Est-ce que tous les vols de Paris à Nouméa font

escale à Bombay ?

Base de faits : la liste des vols avec leurs escales

vol(234, Paris, Singapour, Nouméa)

Réponse :

Non, le vol 234 de Paris à Nouméa ne fait pas escale à

Bombay

Abstraction

Pour chaque application, choisir le bon niveau de détail

Application Prédicat

banlieue mission(QENO, ..., Auber, ..., Lognes, ...)

transport aérien train(aéroportRoissy, Paris)

transport réfrigéré température(conteneurL5, - 18°C)

voiture tropChaud()

instructions lancer(Luc, nettoyRegistres, optionSvg)

instructions lancer(nettoyRegistres, optionSvg)

Rôles thématiques

Chaque argument a une relation avec le prédicat

parier(Luc, Marie, LucArrivePremier, 15€)

argument 1 parieur 1

2 parieur 2

3 pari du parieur 1

4 enjeu

Les rôles thématiques sont les étiquettes de ces relations

Rôles thématiques

Principaux rôles thématiques (1/2)

agent prendre(Luc, leParapluieDeLuc)

expérienceur aimer(Luc, Marie)

patient prendre(Luc, leParapluieDeLuc)

cause casser(vent, branches)

résultat peindre(Luc, paysage, surLeMur)

contenu aimer(Luc, sortirAvecMarie)

Rôles thématiques

Principaux rôles thématiques (2/2)

destination cacher(Luc, parapluie, dansLePlacard)

source sortir(Luc, beurre, frigo)

position êtreDans(beurre, frigo)

instrument revêtir(Luc, salleDeBains, carrelage)

bénéficiaire envoyer(Luc, lettre, Marie)

détrimentaire voler(Luc, sac, Marie)

Rôles thématiques

parier(Luc, Marie, LucArrivePremier, 15€)

argument 1 parieur 1 agent

2 parieur 2 agent

3 pari du parieur 1 contenu

4 enjeu ?

Calcul des propositions

Formules

Propositions : vraies ou fausses

Connecteurs logiques et, ou, non...

a ou b

a b

Chaque formule contient un nombre fini de propositions

En pratique, on prend comme propositions des prédicats

Calcul des propositions

Entités

Servent d'arguments aux prédicats

Une entité ne peut pas être elle-même un prédicat

pleuvoir()

prendre(moi, monParapluie)

Formules

Propositions

Connecteurs logiques et, ou, non...

non pleuvoir() ou prendre(moi, monParapluie)

pleuvoir() prendre(moi, monParapluie)

Calcul des propositions

Variables

Une variable peut représenter une proposition dont on ne sait pas si

elle est vraie ou fausse

Dans un monde donné, elle est soit vraie soit fausse

non pleuvoir() ou prendre(moi, monParapluie)

pleuvoir() prendre(moi, monParapluie)

Tautologie

Formule vraie dans n'importe quel monde

Calcul des propositions

Proposition vraie dans tous les mondes de l'application

vol(234, Paris, Singapour, Nouméa) escale(234, Singapour)

vol(234, Paris, Singapour, Nouméa) source(234, Paris)

vol(234, Paris, Singapour, Nouméa) destination(234, Nouméa)

Calcul des propositions

Déduction

Formule supposée vraie :

non (pleuvoir() ou faireChaud())

Formule déduite :

non pleuvoir() et non faireChaud()

Notations

non (pleuvoir() ou faireChaud()) ├ non pleuvoir() et non faireChaud()

non (pleuvoir() ou faireChaud())

non pleuvoir() et non faireChaud()

Déduction automatique : tables de vérité, modus ponens, tableaux

sémantiques...

Tables de vérité

Interprétation

Indique les valeurs des propositions (vraies ou fausses)

Tables de vérité : chaque ligne correspond à une interprétation

Modus ponens

Déduction

Formules supposées vraies :

pleuvoir()

pleuvoir() prendre(moi, monParapluie)

Formule déduite :

prendre(moi, monParapluie)

modus ponens (+ 6 axiomes)

pleuvoir()

pleuvoir() prendre(moi, monParapluie)

prendre(moi, monParapluie)

Tableaux sémantiques

Détermine si un ensemble de formules peuvent être vraies

ensemble

Si elles le peuvent, construit une interprétation où elles le sont

Règles non branchantes

a et b a non non a a

b

Règles branchantes

a ou b a b

a b non a b

a b a et b non a et non b

Tableaux sémantiques

On ferme une branche quand elle contient une contradiction

Une branche non fermée donne une interprétation

Exemple : vérifier si a et non b, b et non c, c a peuvent être

vrais ensemble

On suppose que p (non h c) et que p non h. Peut-on en

déduire que p c ?

Vérifier si p (non h c), p non h et non (p c) peuvent

être vrais ensemble. Si non, la déduction est valide.

Logique du premier ordre

On ajoute des variables et les quantificateurs (cela revient à

accepter une infinité de propositions)

Entités

Prédicats dont les arguments sont des entités

Connecteurs logiques et, ou, non...

Quantificateurs

Formules

x restaurant(x) et servir(x, sushi) et êtrePrèsDe(x, laGare)

x restaurantJaponais(x) servir(x, sushi)

Logique du premier ordre

x un "et" sur toutes les valeurs possibles de x

x un "ou" sur toutes les valeurs possibles de x

Déduction par modus ponens

x restaurantJaponais(x) et êtrePrèsDe(x, laGare)

x restaurantJaponais(x) servir(x, sushi)

x servir(x, sushi) et êtrePrèsDe(x, laGare)

restaurantJaponais(leSamouraï)

x restaurantJaponais(x) servir(x, sushi)

servir(leSamouraï, sushi)

Logique du premier ordre

Formule --> FormuleAtomique

| Formule Connecteur Formule

| non Formule

| Variable Formule

| Variable Formule

| ( Formule )

FormuleAtomique --> Predicat ( Arguments )

Arguments --> Argument AutresArguments

| ε

AutresArguments --> , Argument AutresArguments

| ε

Logique du premier ordre

Argument --> Constante

| Variable

Connecteur --> et | ou |

Constante --> ceChat | Luc | leParapluie...

Variable --> x | y | z...

Predicat --> êtreNoir | dormir...

Tableaux sémantiques

Nouvelles règles

x a(x) a(t)

x a(x) a(t) [t nouvelle variable encore inutilisée]

x a(x) x a(x)

x a(x) x a(x)

Exemple : de x a(x) peut-on déduire y a(y) ?

Logique du premier ordre

Tous les conducteurs ont eu au moins un accident

Tous les conducteurs n'ont pas eu d'accident

Aucun conducteur n'a eu d'accident

Tous les convives qui avaient mangé des oeufs ont été malades

Tous les convives qui avaient mangé des oeufs n'ont pas été

malades

Aucun convive qui avait mangé des oeufs n'a été malade

Aucun convive qui n'avait pas mangé d'oeufs n'a été malade

Tous les convives qui ont été malades avaient mangé des oeufs

Tous les convives qui ont été malades n'avaient pas mangé d'oeufs

Pierre n'est pas éligible à moins qu'il n'ait démissionné

Logique du premier ordre

Raisonnement par chaînage avant

On ajoute la formule déduite à l'ensemble des formules et on

recommence

Raisonnement par chaînage arrière

On veut savoir si servir(leSamouraï, sushi)

On suppose que x restaurantJaponais(x) servir(x, sushi)

On construit la formule

restaurantJaponais(leSamouraï)

On cherche à savoir si elle est vraie : on recommence

Logiques d'ordre supérieur

Les arguments d'un prédicat peuvent être des formules avec

prédicat et arguments

Second ordre

date(mort(Jean-Paul), 2avril2007)

demander(Luc, Marie, sortir(Luc, Marie, ceSoir))

enSilence(quitter(lesEtudiants, laSalle))

séquence(pleuvoir(), arcEnCiel(), soleil())

tromperie(contrat(Luc, sociétéTéléphone))

Troisième ordre

souhait(Luc, non tromperie(contrat(Luc, sociétéTéléphone)))

Autres notions

Le temps

Luc mange des oeufs

1) habituellement

2) en ce moment

Luc mange plusieurs oeufs

1) en même temps

2) l'un après l'autre

3) par jour

Autres notions

Les présuppositions

Luc mange déjà des oeufs

Présuppositions :

- on s'attendait à ce que cela ne soit pas le cas maintenant

- on s'attendait à ce que cela soit le cas plus tard

Luc mange encore des oeufs

Autres notions

Modalités

Luc peut manger des oeufs

Luc doit manger des oeufs

1) probablement

2) obligatoirement

Luc mange peut-être des oeufs

Luc ne saurait manger des oeufs

Autres notions

Coréférence

Un des ordinateurs est tombé en panne. Il a été réparé

rapidement

*Tous les ordinateurs ne sont pas restés en état de marche. Il a

été réparé rapidement