REPUBLIQUE DU CAMEROUN REPUBLIC OF CAMEROON
Paix -Travail - Patrie Peace - Work - Fatherland
MINISTERE DE MINISTRY OF HIGHER
L'ENSEIGNEMENT SUPERIEUR EDUCATION
UNIVERSITY OF NGAOUNDERE
TPE DE SYSTEME MULTI-AGENTS
SEMANTIQUE DE KRIPKE
Master II SLED
Noms & Prénoms Matricule
TALA SIMO CECILE AUDE 16B739FS
TCHAYA NGONGAG VANNELLE L 16A018FS
TCHOUKOUEGNO DE MOFO GABBI .E 16B140FS
ZOUFANE YOUGOUDA EMMANUEL 16A014FS
Enseignant : Dr. Vivient Kamla
Année académique
2020/2021
Table des matières
Introduction......................................................................................................................................2
I. Les différentes notions..................................................................................................................3
II. Représentation et fonctionnalité................................................................................................4
III. Validité, satisfaisabilité, équivalence.........................................................................................8
IV. Correspondance et complétude.................................................................................................9
V. Limites de la sémantique des mondes possibles.........................................................................10
Conclusion......................................................................................................................................11
1
Introduction
En logique mathématiques la sémantique de Kripke est une sémantique formelle utilisée
pour les logiques non-classiques comme la logique intuitionniste et certaines logiques modales .Elle
a été développée a la fin des années 1950 et début des années 1960 par Saul Kripke. Elle a fondé la
théorie des mondes possibles . L’ intérêt de la sémantique des mondes possibles pour les systèmes
multi-agents est de pouvoir représenter facilement les croyances mutuelles que les agents peuvent
avoir les uns envers les autres et de prendre en compte un ensemble d’assertions Dans ce travail
nous allons définir les différentes notions de la logique de Kripke , montrer sa représentation et sa
fonctionnalité ensuite nous allons parler de sa correspondance et de sa complétude et enfin dégager
quelques limites de cette semantique.
2
I. Les différentes notions
➢ Mondes possibles : Soit un ensemble infini de mondes possibles noté Wn ,Wn interprète
les propositions atomiques par la stipulation aux mondes possibles où elles sont vraies et,
par omission, à ceux où elles sont fausses. De plus, une formule est vraie dans un monde
possible α si et seulement si α ∈ W n , c’est-à-dire que ce monde doit être présent dans W n , c’est-à-dire que ce monde doit être présent dans
l’ensemble des mondes possibles de Wn .Cela nous mène à une définition précise d’un cadre
et modèle
➢ Cadre de Kripke : Un cadre (ou structure) de Kripke est un couple (W, R), où W est un
ensemble de mondes Wn appelé parfois univers et où R est une relation binaire sur ces
mondes. R est appelée la « relation d’accessibilité » du cadre. Un cadre de Kripke définit
donc quels mondes sont accessibles depuis chacun des mondes du cadre.
Un cadre de Kripke est habituellement représenté sous la forme d'un graphe orienté dont les mondes
sont les sommets et dont la relation d'accessibilité donne les arcs. Une telle relation R définit les
mondes accessibles depuis chaque monde. Dans l'exemple ci-dessous, w 3 et w4 sont les deux
mondes accessibles depuis w2.
La structure ( ᴎ, <), c'est-à-dire l'ensemble des entiers naturels muni est de la relation d’ordre
« strictement inférieur », est un autre exemple de cadre. Chaque entier est un monde possible et un
monde est en relation avec un autre si et seulement si le nombre correspondant au premier monde
est strictement inférieur au nombre correspondant au second.
➢ Modèle de Kripke : Un modèle de Kripke est un triplet (W, R, h) où W est un ensemble de
mondes dit univers, R une relation binaire dite d’accessibilité et h une fonction de valuation
sur les atomes d’un langage propositionnel. Pour chaque proposition p, h(p) est l’ensemble
des mondes de W où p est vraie. Un cadre de Kripke peut donc être commun à plusieurs
modèles de Kripke distincts (disposant chacun d'une fonction de valuation h spécifique).
3
II. Représentation et fonctionnalité
L’idée intuitive est de considérer que chaque agent peut envisager un certain nombre de
mondes qu’il imagine envisageables. On dit alors qu’un agent croit une proposition si elle est vraie
dans tous les mondes qu’il imagine. Par exemple, si Jean croit que le réservoir d’essence de sa
voiture est plein, cela signifie qu’il peut envisager plusieurs mondes possibles — dans certains
Napoléon est mort à Sainte-Hélène, dans d’autres il est mort à l’ı̂le d’Elbe, dans d’autres encore
Napoléon est mort aux Tuileries, Jean n’a pas de croyances sur la mort de Napoléon — mais que
dans tous ces mondes le réservoir d’essence de sa voiture est plein. Pour exprimer cette idée, il est
nécessaire d’avoir un langage de représentation des connaissances. De manière classique, nous
utiliserons un langage modal, c’est-à-dire un langage correspondant à celui de la logique
propositionnelle ou à celui de la logique des prédicats, auquel on ajoutera un opérateur de croyance
ou de savoir, ce que l’on appelle des modalités.
Par la suite nous noterons croire(A,P) pour indiquer que l’agent A croit la proposition P,
c’est-à-dire que l’opérateur modal croire est appliqué à la proposition P et indexé par l’agent A. Par
exemple, la phrase Jean croit que le réservoir de Titine est plein s’exprime ainsi:
croire(Jean,plein(réservoir(Titine)))
où Titine est la voiture de Jean. En terme de sémantique des mondes possibles, cela signifie qu’il
existe un ensemble de mondes, appelé W , tels que, à partir du monde W 0 considéré comme le
monde “réel”, Jean ne voit (ou n’imagine) que des mondes dans lesquels le réservoir de sa voiture
est plein. La figure 5.3 représente cette situation (on suppose de plus qu’il existe une règle de la
forme [Link](x) ¬plein(x)). Dans certains des mondes que Jean imagine Titine est neuve, dans
d’autres elle ne l’est plus. Parfois, Napoléon est mort à Sainte-Héléne, mais dans tous les cas
Figure 5.3: Un modèle de mondes possibles (b) correspondant aux croyances de Jean
4
(a)
il n’imagine que des mondes dans lesquels le réservoir de Titine est plein, et c’est pour cela que l’on
peut dire que Jean croit effectivement cette proposition. De plus, Jean croit quelque chose de faux.
En effet, il est dit dans le monde originel W0 que le réservoir n’est pas plein (il est même vide), mais
cela Jean ne le voit pas. Plus formellement, on appelle interprétation en termes de mondes possibles,
un modèle de Kripke M défini comme un n-uplet
M =< W, I, R 1, ..., R n >
où W est un ensemble de mondes possibles (ou d’états possibles du monde si l’on préfère), où R i
est une relation d’accessibilité associée à l’agent i, et où I est une fonction de valuation qui associe
une valeur de vérité à une proposition et à un monde, c’est-à-dire une fonction de type
I : Proposition × W → {V rai, F aux}
L’interprétation d’une proposition contenant une croyance peut alors être donnée par une relation de
conséquence sémantique notée |= où M, w |= φ signifie que/phi est vrai dans le monde w du modèle
M . Cette relation est définie récursivement ainsi dans le cadre d’une logique modale
propositionnelle 11 :
M, w|= φ si φ est une proposition primitive et I(φ, w) = V rai
M, w|= I ¬φ ssi M, w 6| = I φ
M, w|= I φ ∧ ψ ssi M, w |= I et M, w |= I ψ
M, w|= I φ ∨ ψ ssi |= I φ ou |= I ψ
M, w|= I φ ψ ssi M, w 6| = I φ ou M, w |= I ψ
M, w|= I croire(a, φ) ssi
pour tout monde w i tel que w R a w i , M, w i |= I φ
Il ne suffit pas de donner une sémantique à un opérateur modal. Encore faut-il être capable de
caractériser les différentes propriétés que l’on attache à ces formes de connaissances. Celles-ci
peuvent être définies par un ensemble d’axiomes qui caractérisent les aspects inférentiels des
croyances.
Le premier de ces axiomes, l’axiome de distribution, porte sur le fait que les croyances ou
les savoirs d’un agent suivent le principe du modus ponens: si un agent croit une implication entre
deux termes, alors s’il croit le premier, il croit aussi le second. Cet axiome, qui est souvent
considéré comme l’élément principal des logiques des savoirs et des croyances, peut avoir plusieurs
expressions équivalentes:
croire(A, (P Q)) croire(A, P Croire(A, Q)) (K)
croire(A, P) ∧ croire(A, (P Q)) croire(A, Q)
L’axiome de non contradiction caractérise les facultés logiques d’un agent. S’il croit
quelque chose, alors il ne croit pas son contraire, ce que l’on note:
croire(A, P) ¬croire(A, ¬P)) (D)
par exemple, si Jean croit que son réservoir d’essence est plein, alors il ne croit pas
5
que son réservoir est vide. Les agents cognitifs peuvent être considérés comme des agents
conscients de leur propres croyances. Cela indique que si un agent croit quelque chose, alors il croit
qu’il le croit. Cette propriété est matérialisée par les axiomes d’introspection positive et négative:
croire(A, P) croire(A, croire(A, P)) (4)
¬croire(A, P) croire(A, ¬croire(A, P) (5)
L’axiome de savoir considère que tout ce que croit un agent est vrai, et est noté
ainsi:
croire(A, P) P (T )
Cet axiome n’est pas adapté aux croyances: il est en effet possible d’avoir des croyances
fausses, et c’est d’ailleurs ce que nous avions reconnu comme étant l’une des caractéristiques
fondamentales des croyances. Lorsque Jean croit que son réservoir est plein, il se peut qu’il soit
vide. En revanche, la notion de savoir, telle qu’elle est utilisée en logique, suppose que tout savoir
est vrai, c’est-à-dire qu’un agent ne peut savoir quelque chose de faux. De ce fait, l’axiome de
connaissance, qui est l’un des pivots des logiques des savoirs, ne sera pas utilisé pour la
représentation des croyances. Il est possible de panacher ces propriétés et de ne conserver que les
axiomes que l’on désire. Dans ce cas on obtiendra à chaque fois un système logique différent, dans
lequel certaines déductions pourront être faites et pas d’autres. La figure 5.4 (Konolige 1986)
représente l’ensemble des systèmes modaux correspondant à ces axiomes ainsi que leurs liens de
dépendance.
Figure 5.4: Les différentes logiques modales définissables à partir des axiomes K,D,T,
4 et 5. Une flèche X → Y indique que tous les théorèmes de X se retrouvent intégralement dans Y.
Les noms entre () correspondent à leur dénomination usuelle.
L’intérêt de la sémantique des mondes possibles est de pouvoir relier les axiomes de ces
systèmes logiques modaux aux propriétés des relations d’accessibilité. L’axiome K est
indispensable parce qu’il permet d’interpréter les propositions modales en termes de mondes
possibles. L’axiome T est caractéristique d’une relation d’accessibilité réflexive. Lorsqu’elle est en
plus transitive on obtient le système S4. Lorsqu’il s’agit de relations d’équivalence, c’est-à-dire si
l’accessibilité est réflexive, symétrique et transitive, le système d’axiome correspondant est S5. Les
logiques des savoirs utilisent généralement les logiques S4 ou S5. En revanche les logiques des
croyances, qui ne peuvent accepter l’axiome T, utilisent généralement KD45, la plus forte des
logiques des croyances.
L’autre intérêt de la sémantique des mondes possibles pour les systèmes multi-agents est de
pouvoir représenter facilement les croyances mutuelles que les agents peuvent avoir les uns envers
les autres et de prendre en compte un ensemble d’assertions telles que :
croire(Jean, plein(réservoir(Titine)))
6
croire(Marie, vide(réservoir(Titine)))
croire(Marie, croire (Jean, vide(réservoir(Titine))))
dans laquelle Marie croit non seulement que le réservoir de Titine est vide, mais aussi que Jean croit
que le réservoir est vide, alors que ce dernier croit que le réservoir est plein. Cela signifie d’abord
simplement que dans tous les mondes accessibles initialement par Jean (c’est-à-dire accessible
depuis W0) le réservoir de Titine est plein et que dans tous les mondes accessibles initialement par
Marie, le réservoir est vide. La croyance mutuelle est précisée en disant que dans tous les mondes
accessibles par Marie, la proposition
croire(Jean, vide(réservoir(Titine)))
est vraie, c’est-à-dire que dans tous les mondes accessibles par Jean à partir des mondes initialement
accessibles par Marie, la proposition
vide(réservoir(Titine))
est vérifiée, comme le montre la figure 5.5.
Figure 5.5: Un modèle de mondes possibles indiquant les croyances respectives de Jean et de Marie.
Celle-ci croit que Jean croit que le réservoir est vide alors qu’il croit en fait qu’il est plein.
7
III. Validité, satisfaisabilité, équivalence
➢ Une formule ɸ est Kripke-valide si et seulement si elle est vraie en tout monde de tout
modèle de Kripke, on le note |=ɸ :
➢ Une formule ɸ est Kripke-satisfaisable si et seulement s'il existe un monde w d'un modèle
M où |ɸ est vraie :
➢ Une formule est Kripke-équivalente à une formules φ si et
seulement si pour tout monde w de tout modèle M, ϕ est vraie si et seulement si φ est vraie :
Implique et est impliquée par
À titre d'exemple, la formule de Kripke (axiome K commun à
toutes les logiques modales normales) est Kripke-valide :
On peut également définir les notions de validité, de satisfaisabilité et d'équivalence en se
restreignant à un modèle, à un cadre ou à une classe de cadre, plutôt qu'à l'ensemble des modèles :
• Une formule est valide dans un modèle si et seulement si elle est vraie en tout monde de ce
modèle ;
• Une formule est valide dans un cadre si et seulement si elle est valide dans tout modèle
basé sur ce cadre ;
• Une formule est valide dans une classe de cadres si et seulement si elle est valide dans tout
cadre de la classe.
Ces dernières définitions permettent d'exprimer des vérités contingentes, par opposition à des
vérités absolues (en logique modale normale) représentées par la Kripke-validité.
8
IV. Correspondance et complétude
Les propriétés de la relation d'accessibilité qui caractérise un cadre de Kripke sont étroitement liées
aux axiomes de la modalité qui doit y trouver sa sémantique : n'importe quel cadre de Kripke ne
peut pas représenter n'importe quelle logique modale. Henrik Sahlqvist a donné une correspondance
précise entre certains types de formules (les formules de Sahlqvist) et l'expression en logique du
premier ordre de propriétés sur la relation d'accessibilité : une formule de Sahlqvist est valide dans
la classe des cadres de Kripke dont la relation d'accessibilité vérifie cette propriété.
Par exemple, la formule ne peut être valide que lorsque le monde courant est accessible depuis lui-
même : en fait cette formule est valide dans tous les cadres de Kripke dont la relation d'accessibilité
est réflexive. L'algorithme de Sahlqvist, associé à cette correspondance, permet de déterminer
l'expression caractérisant la relation d'accessibilité, à partir de la formule modale. Le tableau suivant
donne les propriétés de relations associées à des formules courantes en logique modale normale :
9
V. Limites de la sémantique des mondes possibles
Bien que très utilisée en Intelligence Artificiel Distribuée pour décrire les croyances et les savoirs
des agents, la sémantique des mondes possibles et les logiques modales qui y sont associées sont
très controversées. La première de ces controverses concerne l’omniscience logique des agents ainsi
définis. La sémantique des mondes possibles réclame absolument une règle, appelée règle de
nécessité qui indique que toute formule valide (c’est-à-dire universellement vraie quel que soit le
modèle) fait nécessairement partie des croyances de l’agent, ce que l’on exprime de la manière
suivante:
L’inconvénient, c’est que cette règle, lorsqu’elle est associée à l’axiome K, impose à l’agent d’être
capable de déduire toutes les conséquences logiques de ses croyances et en particulier celles qui
proviennent des conséquences universellement valides. Par exemple si Jean croit que le réservoir de
sa voiture est plein, et qu’il soit vrai que sa voiture puisse rouler 200 kilomètres sans avoir besoin
de reprendre de l’essence, alors, d’après la sémantique des mondes possibles, Jean doit
nécessairement croire qu’il pourra rouler 200 kilomètres. Mais cela n’est peut-être pas une croyance
de jean ,s’il croit que sa voiture peut rouler pendant 300 km sans faire le plein. Dans ce système, on
ne peut donc pas croire quelque chose qui soit en contradiction avec un fait universellement vrai.
Les croyances fausses sont donc interdites, ce qui est pourtant le propre des croyances. De plus cette
sémantique ne prend pas en compte le fait que les agents disposent de mémoire et de processeurs
limités. On ne peut donc se sortir de ces difficultés qu’en supposant que cette sémantique définit des
agents dont les performances de déduction sont “idéales”. On fera aussi attention à limiter au
maximum le nombre de formules universellement valides de telle manière que des déductions non
voulues ne puissent pas être engendrées par le système.
10
Conclusion
Parvenu au terme de notre analyse, force est de constater que la sémantique de Kripke jouent
un rôle important dans les systèmes multi-agents ; cette logique permet de représenter facilement les
croyances mutuelles que les agents peuvent avoir les uns envers les autres et de prendre en compte
un ensemble d’assertions. L’inconvénient de ce système est que on ne peut pas croire quelque chose
qui soit en contradiction avec un fait universellement vrai.
11
Bibliographie
➢ Jacques Ferber 1995 « Les Systèmes Multi Agents: vers une intelligence
collective »
➢ Kripke S. A. (1991) “Semantical Considerations on Modal Logic.” In
Reference and Modality, Linsky (Ed.), p. 63-72, Oxford University Press.
➢ [Link]
➢ Support de Cours
12