Acquisition et Représentation des connaissances

Emergence et limites
II- Intelligence artificielle
1- Introduction
2- Définitions
3- Les domaines D’application
4- Les langages de programmation
5- Aperçu sur les systèmes experts
 Intelligence artificielle 1
• Les domaines privilégiés de l'IA : là où il n’y a pas d’algorithme
à la portée des machines.
• Comme les problèmes qui ont une combinatoire trop importante
– crypto-arithmétique, jeux, mots croisés, plannification, jeux, économie, ...

• ... qui nécessitent une démarche heuristique.

exemple: le jeu d'échecs (10160)
Les heuristiques relèvent de connaissances d'ordre pragmatique et traduisent un
savoir-faire, une expérience plutôt qu'un calcul systématique.

• L'intelligence artificielle a aussi vocation à simuler le raisonnement humain.

–modéliser les connaissances et les modes de raisonnement d'un expert humain
–les rendre accessibles à un non informaticien.
 Intelligence artificielle
• Les années lumières (euphorie et grands espoirs) 1956-1966
– Logic Theorist (Newell, Shaw et Simon, 1956)
démonstration de théorèmes de la logique des propositions
Reconnaissance de caractères, La “souris cybernétique”,
le perceptron (Rosenblatt,58), Dames anglaises (Samuel,59)]

– General Problem Solver (1969): résolveur de problèmes général

Projet de traduction automatique (1966: rapport ALPAC)

- Weizenbaum, J., (1966) ELIZA - A computer program for the study of

natural language communication between man and machine.
Communications of the ACM, 9.1:36-45.
 Intelligence artificielle
• Le renouveau (les premiers systèmes experts) 1969-1979
– DENDRAL réalise l'analyse automatique des spectres de masse pour
déterminer la structure moléculaire du corps chimique étudié.
“ Heuristics Dendral : A program for generating explanatory hypotheses
in organic chemistry.” de B. Buchanan, Sutherland, Feigenbaum,
Machine Intelligence, 1969

– MYCIN diagnostique les maladies infectieuses du sang et propose un

traitement approprié. “ Computer based medical consultations :
MYCIN” de E. Shortliffe, 1976

• L’IA institutionnalisée 1980-aujourd’hui

– Une industrie (SE, Systèmes d’apprentissage, interfaces
ergonomiques, Data Mining, etc.)
 Définitions
• 1)Rechercher (analyser, résoudre des problèmes,
trouver des méthodes de résolution)

• 2)Représenter des connaissances (logique, règles,

mémoire, cas, langue naturelle, etc.)

• 3)Mettre en application les idées 1) et 2) (Systèmes

Experts, pilotes automatiques, agents d’interfaces,
robots, Data Mining, etc.)
Quatre types de définition de l’IA
 IA
• C’est le domaine de l’informatique qui étudie comment faire à l’ordinateur
des tâches pour lesquelles l’homme est encore aujourd’hui le meilleur

• C’est donc une investigation à visage humain qui inclut dans son champ
d’étude tous les processus mentaux et moteurs humains:
– Perception, motricité, langage, créativité, apprentissage, raisonnement,
émotion

• Cette définition ne résoud pas la tension existante entre l’IA comme

sciences cognitives et l’IA comme science de l’ingénieur.

• Ces deux visions s’influencent et s’alimentent mutuellement.

 Domaines d’application
• Informatique (systèmes, codage, ... )
• Linguistique (syntaxe, sémantique,
pragmatique, ...)
• Psychologie (intelligence humaine, animale,
développement)
• Ergonomie (analyse des tâches)
• Biologie, Statistique, Economie, …
 suite
• L’ Ambitions initiales abandonnées
– on ne pense plus faire une IA à court terme
• Les retombées de l’IA sont partout
– objets, agents, méthodologies, représentation des connaissances
– approches causales, qualitatives – fouille de données, fouille de
texte
– statistiques non linéaires (réseaux neuronaux)
– programmation par contraintes
– nouvelles méthodes d ’optimisation (évolution artificielle)
• Vous les utilisez au quotidien sans le savoir
- Mobiles
- Jeux de réflexion sur ordinateur
 Les langages de programmation
• – Lisp (1960, J. MacCarthy)

• – Prolog (1973, A. Colmerauer), Prolog avec

contraintes

• – SmallTalk (1972, A. Kay)

• – JAVA (1994) , C++, Scheme, ...

 Constat
• Apport de l ’IA:
• – « experience-based reasoning » - façon de penser, d ’aborder les
problèmes
• – modélisation
• – découverte de connaissances
• – amélioration de méthodes et approches existantes
statistiques et data mining
RO et PPC et CBR
Recherche d ’informations et de connaissances
Interfaces
partage de connaissances
réalité virtuelle
 Constat 2
Reconnaissance et synthèse de la parole(ex: réservation d’hôtel )
• Reconnaissance et synthèse d'images (ex. recherche d’info)
• Reconnaissance de l'écriture (ex: recon. cheques, codes postaux)
• Langage naturel (ex: interfaces, text mining, Web Mining)
• Planification (ex: Partage resource satellite DigitalWpress ’s service PCAIApril2000)
• Aide à la décision (ex: SE temps réels et autonome: contrôle de trajectoire du satellite
Voyager)
• Aide à la programmation (ex: agents d’interface)
• Apprentissage / Adatptatif (ex: construction de systèmes experts, classification
automatique de galaxie, contrôleurs de robots ...)
• • Jeux (e.g. Echecs(DeeperBlue à 2600), Checkers (Champion), Othello (Champion),
BackGammon(champion), GO (bon amateur).
• • Médecine:
Aide à la décision (SE), prédiction de patients à risques, analyse automatique d ’images
médicales
 Les grandes questions de l’IA
• Représenter, acquérir des connaissances
• Algorithmes généraux de résolution de problème
• Intelligence artificielle « collective »
• Formaliser, mécaniser # types de raisonnement
• Evaluer des situations, décider, planifier
• Raisonner sur le temps et l’espace
• Résumer, apprendre, découvrir
• Langue et IA
• Indexation et IA
• Réalité virtuelle et IA
 Multiples facettes de l’IA
• Facette des mathématiques
– formalisation du raisonnement mathématique (logique)
– Contribution à de nouveaux champs (logiques modales -> logique possibiliste)
• Facette informatique
– Nouveau « paradigmes » de programmation
• Programmation logique
• Programmation objet
• Programmation fonctionnelle
– Nouvelles façons de voir les systèmes d’information
• Gestion de la connaissance
• Indexation WEB (semantic web)
• Description des documents numériques
– Applications nombreuses
• Aide à la décision
• Aide au diagnostic
• Aide à la planification
• Aide au traitement automatique de la langue
• Aide à la conception
• …
– Omniprésence dans les Systèmes de Traitement de l’Information et de la
Communication (STIC)
 Multiples facettes de l’IA
• Sciences de la cognition et IA
– C’est le même projet au départ
– Vision symbolique (la pensée est un calcul sur des
symboles avec processeur et mémoires)
– Vision sub-symbolique (la vision symbolique fonctionne
mais est virtuelle, les mécanismes sont biologiques mais
produisent le même effet au niveau macroscopique)
Réseaux neuronaux, automates cellulaires.
– Vision « sociale » : la connaissance émerge de
comportements distribués dans un environnement
(approche multiagents). Réseaux neuronaux dynamiques,
colonies d’insectes, etc.
Représentation de connaissances
 Représentation
• une représentation est une structure de
symboles pour décrire un modèle (une
approximation) du monde dans le contexte
d’une tâche particulière.
• pour manipuler des connaissances explicites,
un système doit utiliser un langage formel de
représentation, le plus efficacement possible
 Typologie des connaissances
• connaissances relatives a des objets ainsi qu’a
leurs propriétés et relations
Ex: le carburateur est un élément du moteur
• connaissances relatives a des
éléments/actions
Ex: un moteur en marche fait du bruit et de la
fumée
 Typologie des connaissances
• connaissances relatives a des liens de cause entre des
objets/actions
Ex: l’utilisation du ”levier de vitesse” facilite le démarrage du
moteur
• connaissances relatives a des axiomes/lois
Ex: le taux maximum de CO 2 toléré dans le moteur
• connaissances relatives a des stratégies/heuristiques de
résolution/déduction
Ex: pour examiner l’´etat des freins, il faut
1. bloquer les roues
2. les démonter
 suite
• connaissances relatives a des connaissances
= méta-connaissances
Ex: si le taux de CO 2 dans la fumée est
supérieur au seuil acceptable, il n’est pas
nécessaire d’inspecter l’état des freins, la
voiture est refusée au contrôle technique
Différentes utilisations des connaissances

• Acquisition de nouvelles connaissances

- insertion dans la base de connaissances
- classification/mise en relation avec les autres
connaissances
• Recherche de connaissances nécessaires a la
résolution d’un problème
• Raisonnement
Représentation des connaissances
• Pour des problèmes jouets, la représentation
n’est pas vraiment importante.
« Donnez moi les textes concernant les transaction en Europe d'un
montant supérieur à 1 Meuro »
Actions
- Analyser la structure de la requête, identifier « l ’information »
(concept) cherché
- Trouver dans le texte cette information (et non seulement « des mots
de la requête ») : analyse locale, matching de « structures
informationnelle »
- Retourner les passages concernés
 Réponse
Documents : articles et dépêches économiques
Méthode :
– RD pour une première sélection de documents + trouver des passages
« homogènes »
– EI pour un matching « fin » des requêtes sur le texte.
On cherche à instancier une « Micro fiche ». Exemple :
un EVT de type TRANSACTION associé à une ENTITE LIEU de valeur
'Europe' et une ENTITE MONTANT de valeur supérieure à la valeur
donnée de 1 Meuro.
 Donc
• Les domaines complexes demandent des représentations plus générales et
plus flexibles.

• Comment représenter des concepts comme:

- Actions, Temps, Objets physiques, Croyance

• Mise en évidence de deux problèmes en amont :
- L'acquisition des connaissances
• Comment donner la connaissance à une machine ?

- La modélisation des connaissances

• Comment définir ce qu'est la connaissance ?
• Comment la traduire en structures manipulables par un logiciel ?
 Syntaxe- sémantique
• Toute expression de ce langage s’établit à l’aide
de symboles dont les associations sont régies
par des règles qui forment la syntaxe de la
représentation.
• Si à toute expression syntactiquement correcte
de la représentation on fait correspondre une
situation de l’univers de référence, on adjoint
une sémantique à ce formalisme de
représentation.
 Syntaxe et sémantique
• L’interprétation de la connaissance pour l’élaboration d’une
représentation comporte deux niveaux : le niveau syntaxique et le niveau
sémantique.
• Le niveau syntaxique détermine le langage de description des différentes
connaissances du monde : c’est à partir de ce langage que le système
construit la représentation informatique (structures de données) ;
La syntaxe d’un système de représentation doit pouvoir exprimer les
différents types et modalités de la connaissance du monde traité;

• le niveau sémantique donne une signification dans le monde réel aux

éléments de la représentation, établissant le lien entre le monde et la
représentation.
la sémantique doit faire une interprétation correcte des éléments, relations
et lois du monde réel.
 Syntaxe – Sémantique
recherche de frontière
• Internet, et surtout le Web, est aujourd'hui la
plus grande source de connaissances qui existe.
- Technologie pour Accéder à des informations
non structurées, hétérogènes et distribuées
- L’accès à l’information et à des sources de
connaissance devient essentiel
Due aux : IRC, ICQ, Chat, email, News groups, FTP,
WWW, E-commerce, B2B, B2C, etc.
 Exemple : www
• HTML et PDF sont principalement des
langages de présentation de données
• <H2> Triple X </H2> : ne dit rien sur le titre
sauf pour des humains
 Syntaxe
• HTML a été conçu pour afficher des données
et se concentre surtout sur leur présentation
• XML a été conçu pour décrire des données et
se concentre sur la structure de ces données.
• XSL / XSLT transforme XML en HTML
 syntaxe
• - « La sémantqiue » est un domaine qui étudie comment les
symboles se référent aux objects
- « Note » ne référence rien pour une machine, la référence est
uniquement faite dans l’esprit des lecteur humains

• XML
- Ne contient aucune sémantique formelle pour l’ordinateur
- Ce sont les humains qui donnent un sens, une sémantique,
aux balises et leur contenu pas les machines.

• D’où RDF pour la sémantique

 sémantique
• Actuellement, pas d’accès réel au contenu des
documents
• Problèmes:
- Contenu et Information pas accessible ni
interprétable par des machines
- Pas possible de composer dynamiquement
des documents cohérents et adaptés aux
utilisateurs
 sémantique
• RDF – Resource Description Framework
• RDFS – Resource Description Framework
Schema
• RDF/RDFS a été créé pour le traitement des
métadonnées. Ce sont des langages de
description de métadonnées au niveau
sémantique
 RDF
• RDF est un simple modèle relationnel
- Une déclaration RDF est constituée d’un triplet
« Objet, Attribut, Valeur », dont chaque membre
peut être un littéral ou une ressource web
• Ce triplet peut être interprété comme le tuple
suivant :
« Sujet, Prédicat, Objet » ou encore
Prédicat (Sujet, Objet)
 RDF Schema
• RDF Schéma est une extension de RDF avec
laquelle il est possible de
- Décrire les concepts utilisés dans des
déclarations RDF
- Un ensemble de contraintes sur les objets
et les valeurs du triplet.
 limites
• Chacun peut développer son schéma RDFS pour
exprimer les liens sémantiques pour son site web

• Problème : compatibilité sémantique des

connaissances exprimées sur différents sites web
• Solution : standardisation des schéma de
connaissances pour les domaines d’application
- Utilisation des ontologies (extensions de RDFS)
Techniques de représentation de
connaissances
INTRODUCTION
 Raisonnement

• raisonnement formel: mainpulation syntaxique de

reglesd’inférence

• raisonnement procédural exécution, simulation

d’une procédure
• raisonnement par analogie
Ex: * les pinsons sont comme des moineaux
* les moineaux ont des ailes → les pinsons ont des
ailes
• raisonnement par généralisation/abstraction
• Ex: les pinsons ont des ailes
• les moineaux ont des ailes
• les corbeaux ont des ailes
• ...
• ⇒ les oiseaux ont des ailes
• raisonnement par défaut
une propriété est satisfaite tant que rien ne
permet d’´etablir le contraire
⇒ une connaissance n’est pas éternelle:
elle peut etre remise en cause par
l’acquisistion d’une nouvelle connaissance
 Méta connaissances
• Pour la définition d’un plan
Ex: Si l’on recherche une thérapie alors:
• 1. acquérir les informations cliniques sur les patients
• 2. trouver, s’ils existent, les organismes responsables de
l’infection
• 3. identifier les organismes les plus vraisemblables
• 4. trouver tous les médicaments potentiellement utiles
• 5. choisir les plus adaptés en plus petit nombre
(MYCIN)
 But du raisonnement
• concerne la manipulation de la connaissance déjà acquise
pour produire une nouvelle connaissance.
• connaissances cohérentes et complètes, le raisonnement
consiste à rendre explicites des connaissances qui sont
implicites
• Connaissances imprécises utilise des techniques
d’approximation comme les probabilités et les ensembles
flous.
• connaissances incomplètes nécessite des hypothèses le
raisonnement par défaut et le raisonnement avec un
ensemble de possibilités
 Perception du monde
• le monde est unique et les agents le perçoivent tous de la
même manière(classique)
• le monde est unique et les agents le perçoivent de manière
complémentaire( les gestionnaires des bases de données)
• le monde est unique, sa représentation est incomplète et il
est perçu différemment par les différents agents(les
systèmes de robotique)
• les agents ont une vision subjective du monde

L’incomplétude de la représentation
 La représentation
• La représentation de la connaissance est donc
la modélisation des différents éléments du
monde réel et la détermination de procédures
d’interprétation faisant le lien entre le monde
et le modèle
 Types et modalités
• différents types :
concept, fait, méthode, modèle, heuristique,
événement, prototype, objet, etc.

• différentes modalités:
statique ou évolutive, fixe ou modifiable,
certaine ou incertaine, valide ou périmée,
objective ou subjective.
 Techniques de représentation

• Une technique de représentation des

connaissances est une façon de représenter la
connaissance dans un ordinateur pour qu’elle
soit utilisée par un programme pour inférer des
nouvelles connaissances.
• Logique, règles de production, réseaux
sémantique, schéma, logiques terminologiques,
graphes conceptuels……
 Logique
• La logique la plus utilisée est la logique des
prédicats du premier ordre.
• Le premier fruit utilisé jusqu’à présent
PROLOG(83).
• Les SEs
 La représentation logique

• formules logiques bien formées :

– syntaxe précise,
• formées à partir de prédicats, de connecteurs logiques
(et, ou, implication et négation), de quantificateurs
existentiel et universel et de variables et constantes.
• Un prédicat correspond à une fonction donnant une
valeur de vérité (vrai ou faux),
• les variables et les constantes sont interprétées dans
des contextes spécifiques.
 Exemple logique

• Les prédicats à un paramètre chien et aboie

et la constante Olafo :

• 1) chien (Olafo)
• 2) "x chien(x) => aboie(x)
 Mécanismes de raisonnement
logique

• Le raisonnement logique est un raisonnement déductif qui essaie

d’expliciter les informations implicites contenues dans une base de
connaissances.
• Le mécanisme de déduction utilise un ensemble de règles d’inférence
pour déduire des nouveaux faits à partir des faits connus.
• Ces règles:
– le modus ponens,
– le modus tollens et
– la spécialisation universelle.

(sont combinées avec des manipulations syntaxiques des formules (filtrage et

unification) pour élaborer la déduction )
 Définitions logique

• Elle est basée sur le principe de la démonstration automatique

de théorèmes(utilisant la logique du premier ordre)

• Un programme en Logique est un ensemble d'énoncés.

• Les énoncés sont des formules du calcul du premier ordre ne

contenant pas de variables libres.

• Tout problème calculable peut être formulé dans ce langage.

 Syntaxe : Éléments de base

• Constantes : a, b, c,...
• Variables : x, y, z,...
• Fonctions : f, g, h, ....
• Relation( prédicat ou fonctions booléennes):
P, Q, R
 Syntaxe : définition d'un terme

•  Toute constante est un terme.

•  Toute variable est un terme.
•  Si t1, t2, ..tn sont des termes et si f est une
fonction n-aire, alors f(t1, t2, ..,tn) est un
terme.
 Syntaxe : définition d'un atome

•  Si t1, t2, ..., tn sont des termes et si P est un

prédicat n-aires alors P(t1, t2, .., tn) est un
atome.
Syntaxe : définition d'une formule

• Tout atome est une formule.

• Si P et Q sont deux formules alors :
• Non P, P & Q, P V Q, P ==> Q, P <==> Q,  x
P(x),  x P(x) sont des formules.
 Sémantique

• Quand on attribue des valeurs a chaque terme

et à chaque symbole de prédicat dans une fbf
on dit qu'une interprétation est donnée a la
fbf.

• Si les valeurs de vérité de fbf sont les mêmes

pour toute interprétation, on dit qu'il sont
équivalents.
 Sémantique

• Soit à évaluer
• E :   x (( A(a, x) V B(f(x)) & C(x)) ==> D(x)
• A, B, C et D sont des prédicats.
• Soit l'interprétation suivante de domaine D =
{1, 2}
• a=2
• f(1) = 2 ; f(2) = 1
• A(2, 1) = vrai ; A(2, 2) = faux
• B(1) = vrai ; B(2) = faux
• C(1) = vrai ; C(2) = faux
• D(1) = faux ; D(2) = vrai
 Sémantique ( Évaluation ) :

• Cas x = 1

• A(2, 1) vrai et B(2) faux donc A(2, 1) V B(2) vrai

• C(1) vrai donc (A(2, 1) V B(2)) & C(1) vrai
• D(1) faux l'implication est donc fausse

• Cas x = 2
• On montre de la même façon que E est vraie

• Puisque E n'est pas vrai pour tout x, l'expression est alors fausse.
 Propriétés

• L'évaluation de fbf complexes peut être facilité par

une phase de substitution( transformation
syntaxique)

• On dispose alors des propriétés suivantes :

• F, G et H sont des fbf ne contenant pas de variable,

F[x] est une fbf contenant la variable x.
 Propriétés

• Double négation NON ( NON F) = F

• Commutativité F & G = G & F, F V G = G V F
• Associativité F&(G&H)=(F&G)&H
FV(GVH)=(FVG)VH
• Distributivité F V( G & H) = (F V G) & ( F V H)
F &( G V H) = (F & G) V ( F & H)
• De Morgan NON ( F & G ) = NON F V NONG
NON ( F V G) = NON F & NON G
 Propriétés
• F ==> G = NON F V G
• F <==> G = (NON F V G)&(NON G VF)

• NON (x F[x] ) =   x NON F[x]

• NON ( x F[x] ) =  x NON F[x]

• x F[x] &  x G[x] =  x ( F[x] & G[x] )

•  x F[x] V   x G[x] =   x ( F[x] V G[x] )

Inconsistance et validité d'une formule

• fbf inconsistante (in satisfiable) fausse pour toute

interprétation.

• fbf valide : vraie pour toute interprétaion. (Donc fbf

satisfiable : vraie pour quelques interpétations
,fbf non valide : fausse pour quelques interpétations )

• Conséquences
– fbf valide ==> fbf satisfiable
– fbf inconsistante ==> fbf invalide
Inconsistance et validité d'une formule

• Q est une conséquence logique de P1, P2, ....Pn ] <==> [Si P1

& p2 ...& Pn est vraie pour toute interprétation, alors Q est
aussi vrai].

• Exemples :

• P & NON P : inconsistante ( fausse pour toute interprétation)

• P V NON P : valide ( vrai pour toute interprétation)

 Variables liées et libres

• Dans l'expression
x ( P(x) ==> Q(x, y) )

• x est une variable liée et y est une variable libre.

Une expression ne peut être évaluée que
lorsque toutes les variables sont liées. Aussi,
nous exigeons que toutes les fbf contiennent
que les variables liées.
 Forme normale conjonctive

• Soient F1, F2, ...des formules :

• Si chaque Fi est uniquement sous forme
disjonctive de littéraux(V), alors la forme F1 &
F2 &.....Fn est dite une forme normale
conjonctive.

• Exemple : (NON P V Q V R) & (NON P V NON Q)

& NON R est une forme conjonctive.
 Forme normale disjonctive
•Soient F1, F2, ...des formules :

•Si chaque Fi est uniquement sous forme conjonctive de littéraux(V),

alors la forme F1 V F2 V.....Fn est dite une forme normale
disjonctive.

•Exemple:
(P & Q & R) V (Q & R) V P est une forme disjonctive.

•Il a été démontré que toute formule peut être transformée en une
forme normale disjonctive ou conjonctive.
 Règles d'inférence

• Les règles d'inférence fournissent un moyen de faire des

démonstrations ou des déductions logiques. Le problème est le
suivant : étant donné un ensemble d'énoncés {s1, s2, ...sn} les
prémices, prouver la vérité de s( conclusion).

• L'utilisation de la table de vérité est un moyen de

démonstration(sémantique). D'autres méthodes reposent
uniquement sur les transformations syntaxiques. Elles utilisent
alors les règles d'inférences suivantes : Modus Ponens, Modus
tollens, Chaînage, Substitution, Conjonction, contraposée.
 Règles clés utilisées dans les
démonstrateurs

• Modus ponens

• De P et P-->Q, on déduit Q, qui s'exprime

• P
• P-->Q
• ---------Modus Ponens
• Q
 Règles clés utilisées dans les
démonstrateurs

• Modus Tollens

• De Non Q et P -->Q, on déduit Non P.

• Non Q
• P ==> Q
• ----------Modus Tollens
• Non P
 Règles clés utilisées dans les
démonstrateurs

• Chaînage
• De P --> Q et Q --> R, on déduit P --> R
• P-->Q
• Q-->R
• P-->R

• Cette dernière est équivalente à:

• Non P V Q
• Non Q V R
• Non P V R
 Autres règles :

• Substitution :
De P & Q, on déduit P
P&Q
P
• Conjonction :
De P et de Q, on déduit P & Q
P
Q
 P & Q
 Autres règles :

• Contraposée

De P --> Q, on déduit Non Q --> Non P

P --> Q
Non Q --> Non P
 Exemple de formalisation
• Un meurtre a été commis au laboratoire, dans salle de
conférence
• On dispose des informations suivantes :
– La secrétaire déclare qu’elle a vu l’ingénieur dans le couloir qui
donne sur la salle de conférences
– Le coup de feu a été tiré dans la salle de conférences, on l’a donc
entendu de toutes les pièces voisines
– L’ingénieur affirme n’avoir rien entendu
• On souhaite démontrer que si la secrétaire dit vrai, alors
l’ingénieur ment
 formalisation
• p : la secrétaire dit vrai
• q : l’ingénieur était dans le couloir au moment du
crime
• r : l’ingénieur était dans une pièce voisine de la salle
de conférences
• s : l’ingénieur a entendu le coup de feu
• t : l’ingénieur dit vrai
 Résolution

• Les informations de l’énoncé se traduisent par

les implications :

pq, q  r, r  s, t  s
• Il s’agit de prouver la validité de la formule :

(p  q  q  r  r  s  t  s)  (p  t)
 Résolution 2
(p  q  q  r  r  s  t  s)  (p  t)
• La formule ne peut être fausse que si
– (p  t) est faux, soit p et t vrais
– la prémisse est vraie, soit toutes les implications vraies
• Comme t doit être vrai, s doit être faux, donc r
faux, donc q faux, donc p faux, et il y a
contradiction
 Définitions
• Littéral
– Un atome est un littéral (positif)
– La négation d’un atome est un littéral (négatif)
• Une clause est une formule qui a la forme d’une
disjonction de littéraux
• Une clause concrète est une clause sans variable
• Une clause de Horn est une clause comportant au
plus un littéral positif
• Toute formule peut etre transformer en ensble de
clauses
 Les transformations
En plus des lois de Morgan, commutative, associative
et distributive
1-Forme prénexe :
une fbf en logique des prédicats est dite en forme
prénexe (fnp) ssi elle est de la forme :
• (Q1 X1) (Q2 X2) ... (Qn Xn) M(X1,X2,...,Xn)
Préfixe Matrice
• où chaque (Qi Xi) est soit Xi soit Xi et où M est
une fbf ne contenant aucun quantificateur.
 Méthode
• 1- Eliminer les connecteurs  et <->
• 2- Accoler les connecteurs  aux atomes concernés
• 3- Rebaptiser les variables liées si nécessaire de sorte que chaque
quantificateur gouverne une variable originale
• 4- Déplacer tous les quantificateurs à gauche de la formule (sans
changer l'ordre relatif)

((Q1 X) F(X))  ((Q2 Y) H(Y))  (Q1 X) (Q2 Y) (F(X)  (H(Y))

((Q1 X) F(X))  ((Q2 Y) H(Y)) (Q1 X) (Q2 Y) (F(X) (H(Y))

 Forme de Skolem
• fnp G' d'une fbf G on peut produire une forme
standard de Skolem par les transformations ci-
après soit :
G' = (Q1 X1) (Q2 X2)... (Qn Xn) M(X1, X2,... Xn) fnp
de G

1- Eliminer les quantificateurs existentiels

Soit Qr un existentiel dans le préfixe de G'
 suite
• a) Si aucun quantificateur universel n'apparaît avant Qr
c'est-à-dire dans
(Q1 X1) ... (Qr-1 Xr-1)
• on choisit un symbole de constante c différent de toute
constante apparaîssant dans la matrice M
• on supprime Qr Xr du préfixe on remplace Xr par c dans
la matrice M
– (X) (Y) (P(X)  Q(Y))
Choix de la constante a/X ce qui donne
(Y) (P(a)  Q(Y)) fss
 Suite 2
• b) Si Qs1 Qs2... Qsm sont m quantificateurs
universels apparaîssant avant Qr dans le préfixe
• on choisit un symbole de fonction f d'arité m
différent de toute fonction apparaîssant dans la
matrice M on supprime QrXr du préfixe on
remplace tout Xr dans M par f(Xs1, Xs2,... Xsm)
2- On itère le processus jusqu'à ce qu'il n'y ait
plus de quantificateur existentiel dans le préfixe
 Forme clausale
• Gs une forme standard de Skolem d'une fbf G
1. Eliminer tous les quantificateurs
• Il ne reste que des quantificateurs universels. On allège la notation
en les supprimant.
• On suppose donc désormais que toutes les variables sont
quantifiées universellement.
2. Passer sous forme normale conjonctive
3. Eliminer les connecteurs 
• La conjonction de clauses obtenues au 2. est considérée comme un
ensemble de clauses S
4. Distinguer les variables des clauses distinctes si c'est nécessaire
 Exemple
• Exemple
• X P(X) Y Q(Y)
• Skolem X (P(X)  Q(f(X)))
• Clauses X (P(X)  Q(f(X)))
• Ens. Clauses  S = {P(X),Q(f(X))}
• Clauses X P(X) Y Q(Y)
• Skolem X P(X) Q(a)
• Ens. Clauses  S = {P(X),Q(a)}
 Principe de Résolution
• C’est une règle d’inférence qui s’applique aux
clauses
• Principe sur des clauses concrètes :
– G = G1 G2  …  Gn
– H = G1  H2  …  Hm
– K = G2  …  Gn  H2  …  Hm
– K est le résolvant de G et H
• G1 et G1 sont des littéraux complémentaires
 Suite du principe
• Le principe de résolution est une règle
d’inférence saine, i.e. tout résolvant est une
conséquence logique des deux clauses parentes

• Pour appliquer le principe de résolution à des

clauses non concrètes, on définit l’unification,
afin de rechercher des littéraux complémentaires
 Unification
• Deux termes t1 et t2 sont unifiables s’il existe
une substitution s des variables de t1 et t2 telle
que s(t1) = s(t2)
• Exemples :
– pere(X,jean) s’unifie avec pere(Y,Z) si X|Y et jean|
Z
– pere(jean,mere(X)) s’unifie avec
pere(Y,mere(pierre) si jean|Y et X|pierre