Introduction à la logique épistémique avec le Rallye 2013

samedi 6 avril 2013
par  Alain BUSSER

Tricher n’est pas gagner

On dispose de cinq cartes, trois noires et deux rouges. Un jeu consiste à distribuer une carte, face
cachée, à chacun des joueurs qui devront ensuite deviner, à tour de rôle, la couleur de leur carte.
Marc, Franck et Daniel décident de jouer. Marc et Franck sont de fieffés tricheurs mais Daniel a repéré
leur manège et sait que Franck a réussi à voir la couleur des cartes distribuées à Marc et Daniel et que
Marc, lui, n’a pu apercevoir que la couleur de la carte distribuée à Daniel.
Franck parle le premier et, bien qu’ayant des informations capitales, ne peut deviner la couleur de sa
carte ; Marc avoue ensuite ne pas pouvoir, lui non plus, deviner la couleur de sa carte. Daniel affirme
alors qu’il connaît, lui, la couleur de sa carte : il a donc gagné sans avoir triché !

Quelle est la couleur de la carte de Daniel ? Expliquer.

La logique épistémique traitant des connaissances qu’ont les agents Daniel, Marc et Franck sur les cartes, mais aussi des connaissances qu’ils ont sur les connaissances des autres agents, il est nécessaire pour les explications, d’introduire un quatrième agent, qu’on appellera Alain, qui modélise l’élève en train de résoudre l’exercice. Le but de l’exercice est en bref qu’en sachant que Daniel connaît la couleur de sa carte, Alain acquiert une nouvelle connaissance à ce sujet...

Agents

La logique épistémique traite non seulement de la valeur de vérité de propositions telles que 2+2=4 ou la carte de Daniel est rouge, mais aussi de l’accessibilité que plusieurs personnes ont à ces valeurs de vérité. Ces personnes sont nommées agents [1], et de même qu’on note ¬, ∧ et ∨ la négation, la conjonction et la disjonction en logique épistémique comme en logique propositionnelle, on note KD(p) la proposition épistémique « p est vraie et Daniel le sait », avec les notations analogues KM(p), KF(p) et KA(p) pour dire respectivement que Marc, Franck ou Alain sait que p est vraie.

le cas du K

La lettre K est la première lettre du verbe « to know » qui désigne en Anglais le fait de savoir ; cette notation montre l’origine anglosaxonne de la logique épistémique.

Les quatre agents étant supposés logiciens, toute proposition p vraie dans la logique classique vérifie automatiquement KD(p) et idem pour les autres agents ; mais aussi KD(KF(p)) par exemple. Ainsi,

  • 2+2=4 (théorème de la logique classique)
  • KD(2+2=4) (Daniel, parfait logicien, sait que 2+2 font 4)
  • KM(2+2=4) (Marc aussi, se débrouille en logique)
  • KF(KM(2+2=4)) (Franck sait que Marc est logicien, et sait donc que Marc est au courant pour 2+2)
  • etc

Comme il n’y a pas de limite au nombre d’opérateurs du type KA devant une proposition de la logique classique, on réunit toutes ces propositions où 2+2=4 est précédé d’un nombre quelconque de ces opérateurs, sous une nouvelle proposition notée NP(p) et se lisant « p est de notoriété publique ». Ainsi,

  • 2+2=4 (si, si !)
  • chacun des 4 agents est suffisamment bon logicien pour savoir que 2+2=4 ;
  • les 4 agents se connaissent suffisamment bien pour savoir que les autres agents sont au courant pour 2+2 ;
  • etc

Ce qu’on note simplement NP(2+2=4) : Le fait que 2+2=4 est notoire parmi les 4 agents.

Dans cet exercice de Rallye, la couleur de la carte de Daniel n’est justement pas de notoriété publique : Au début, Daniel ne connaît pas cette couleur, et Marc sait que Daniel ignore cette couleur (alors que lui-même la connaît).

Par contre, une proposition peut être vraie sans que Alain le sache (évidemment, ceci n’est pas vrai pour une proposition de la logique classique). Par exemple, on sait (enfin Alain sait) que

  • F♥ ∨ F♠

(la carte de Franck est rouge ou elle est noire), et donc

  • KF(F♥ ∨ F♠)

(Franck sait que sa carte est dans une de ces deux couleurs), mais aucune des propositions suivantes n’est vraie :

  • KF(F♥)
  • KF(F♠)
  • KA(F♥)
  • KA(F♠)

(Franck, comme Alain, ignorent laquelle des deux couleurs est dans la main de Franck)

Franck

Comme on ne s’intéresse pas à la couleur des deux cartes non distribuées, on est face à 8 mondes où sont données les couleurs des cartes des trois agents :

  • F♥M♥D♥ (monde impossible puisqu’il n’y a que deux cartes rouges dans le jeu) ;
  • F♥M♥→D♠
  • F♥→M♠→D♥
  • F♥→M♠→D♠
  • F♠→M♥D♥
  • F♠→M♥→D♠
  • F♠→M♠→D♥
  • F♠→M♠→D♠

Une proposition épistémique est considérée comme vraie si elle l’est dans tous les mondes possibles (les 7 derniers ci-dessus). Mais si une proposition est de la forme KAp, pour qu’elle soit vraie, il faut que p soit vraie dans tous les mondes accessibles à l’agent A. Les flèches ci-dessus figurent la relation d’accessibilité entre les mondes de Franck, de Marc et de Daniel telle que donnée dans l’énoncé. La relation d’accessibilité est supposée transitive : Tout ce que sait Marc est connu de Franck, et donc il faudrait rajouter une flèche allant directement de Franck à Daniel ; celle-ci est supposée sans être dessinée. Pour le deuxième des mondes ci-dessus (le premier des mondes possibles), le diagramme complet ressemblerait plutôt à ceci :

F♥
M♥D♠

Dans ce monde, les propositions suivantes sont vraies :

  • F♥
  • M♥
  • D♠
  • KM(D♠) (d’après la flèche, comme Marc voit la carte de Daniel, Marc sait que celle-ci est noire)
  • KF(M♥)
  • KF(D♠) (la relation d’accessibilité étant, dans ce problème, transitive).
  • mais ¬KF(F♥) (Franck ignore la couleur de sa carte)

Disjonction et modalité

Comme F♥ ∨ F♠ (tiers exclu), et comme Franck est logicien (onglet précédent), on a

  • KF(F♥ ∨ F♠)

cependant, on n’a ni KF(F♥) ni KF(F♠)

(Franck sait que sa carte est ou bien rouge, ou bien noire, mais ignore laquelle des deux propositions est vraie).


Comme M♥D♥ ⇒ F♠ (parce qu’il n’y a que deux cartes rouges dans le jeu), et que Franck est logicien, on a

  • KF(M♥D♥ ⇒ F♠)

Or le fait que Franck est logicien, s’exprime en partie par l’axiome suivant de la logique épistémique : KF(p⇒q) ⇒ (KFp ⇒ KFq) ; dans le cas présent, cet axiome permet de déduire que

  • KF(M♥D♥) ⇒ KF(F♠)

Dans le monde suivant :

  • F♠→M♥D♥

la proposition suivante devient alors vraie (alors qu’elle ne l’est pas dans les autres mondes) :

  • KF(F♠)

notation

On dit que le monde F♠→M♥D♥ est un modèle de la proposition KF(F♠), ou que la proposition KF(F♠) modélise le monde F♠→M♥D♥, et on note

  • F♠→M♥D♥ ⊨ KF(F♠)

Or, l’affirmation de Franck s’exprime ainsi en logique épistémique :

  • ¬ KF(F♥) ∧ ¬ KF(F♠)

(Franck ne sait pas que sa carte est rouge, et il ne sait pas que sa carte est noire) ; cette affirmation est contradictoire avec KF(F♠) d’après cet axiome de la logique propositionnelle :

  • ¬ KF(F♥) ∧ ¬ KF(F♠) ⇒ ¬ KF(F♠) ;

On a montré par l’absurde que le modèle F♠→M♥D♥ est à éliminer.

Marc

Donc (d’après l’onglet précédent), il ne reste plus que 6 des mondes initiaux (l’un est impossible, un autre exclu par l’affirmation de Franck) :

  1. F♥M♥→D♠
  2. F♥→M♠→D♥
  3. F♥→M♠→D♠
  4. F♠→M♥→D♠
  5. F♠→M♠→D♥
  6. F♠→M♠→D♠

Par ailleurs, toujours d’après l’onglet précédent, la proposition ¬ (M♥D♥), affirmée indirectement par Franck, devient de notoriété publique entre les trois agents (et même les 4, Alain, étant à l’écoute des trois, ne perd aucune miette de leur conversation). C’est-à-dire

  • ¬ (M♥D♥)
  • KF (¬ (M♥D♥))
  • KM (¬ (M♥D♥))
  • KD (¬ (M♥D♥))
  • KA (¬ (M♥D♥))
  • mais aussi KMKF(¬ (M♥D♥))
  • KDKF(¬ (M♥D♥))
  • pire : KDKMKF(¬ (M♥D♥))

On voit là tout l’intérêt de la notation NP(¬ (M♥D♥))...

La règle de DeMorgan permet de réécrire ¬ (M♥D♥) sous la forme M♠ ∨ D♠. Comme ce fait est devenu notoirement public, on a

  • D♥ ∧ (M♠ ∨ D♠) ⇒ M♠
  • KM(D♥ ∧ (M♠ ∨ D♠)) ⇒ KM(M♠)
  • D♥ ⇒ KM(M♠)

Or ceci est contradictoire avec l’affirmation de Marc : ¬ KM(M♥) ∧ ¬ KM(M♠), de laquelle découle ∧ ¬ KM(M♠).

On a donc démontré par l’absurde que les mondes 2 et 5 ci-dessus sont également à écarter.

Daniel

Il ne reste donc que 4 mondes qui puissent modéliser les affirmations de l’énoncé :

  1. F♥M♥→D♠
  2. F♥→M♠→D♠
  3. F♠→M♥→D♠
  4. F♠→M♠→D♠

Ces mondes ont en commun la couleur de la carte de Daniel, laquelle est donc déterminée. Cette couleur devient d’ailleurs de notoriété publique, puisque maintenant que Daniel connaît la couleur de sa carte, tous la connaissent (les deux autres, parce qu’ils l’avaient vue), mais aussi

  • KMKD(D♠)
  • KFKD(D♠)
  • KFKMKD(D♠)
  • KAKD(D♠)
  • KAKFKD(D♠)
  • etc

Par conséquent, la phrase suivante de l’énoncé était superflue :


Daniel affirme
alors qu’il connaît, lui, la couleur de sa carte

En résumé :

  1. Après la déclaration de Franck, Daniel sait que Franck ne sait pas quelle est la couleur de la carte de Franck ;
  2. cela ne permet pas à Daniel de savoir quelle est la couleur de sa carte.
  3. Mais Marc aussi, sait que Franck ignore la couleur de la carte de Franck ;
  4. Malgré cela, Marc ne sait toujours pas quelle est la couleur de la carte de Marc.
  5. Mais Daniel sait que Marc sait que Franck ignore la couleur de sa propre carte ;
  6. et comme Daniel sait aussi que Marc ne connaît pas la couleur de sa propre carte, Daniel sait maintenant quelle est la couleur de sa propre carte.
  7. Et comme Alain suit tout cela, Alain sait maintenant aussi quelle est la couleur de la carte de Daniel.
  8. Alain a un peu le vertige...

Alain et Daniel connaissent maintenant la couleur de la carte de Daniel, et c’est tout. Ils en savent maintenant autant que Marc, qui n’a pas réussi à acquérir de nouvelles informations. Celui qui en sait le plus (et depuis le début), c’est Franck, qui connaît, outre la couleur de la carte de Daniel, celle de la carte de Marc.

On constate que celui qui au début du jeu, avait le moins d’informations sur le jeu, est le seul à pouvoir dire à la fin, la couleur de sa carte. C’est la conséquence du fait que par leurs affirmations, les tricheurs lui ont apporté les informations qu’ils avaient sur la couleur de sa carte, alors que lui ne pouvait, et pour cause, apporter d’information sur la couleur des autres cartes.

Alain

La logique épistémique est toutefois insuffisante à elle seule, à expliquer l’évolution des informations lors du dialogue entre agents. On lui substitue de plus en plus d’autres logiques :

  • la logique du dialogue
  • la logique des questions
  • la logique doxastique, où à la notion de connaissance (non révisable parce que nécessairement vraie), on substitue celle de croyance révisable à la lumière de nouvelles informations : On peut croire à quelque chose de faux.

C’est une démarche voisine que celle initié par Thomas Bayes, qui, en donnant à chaque croyance un poids (ici, sa probabilité), permet de voir comment évoluent les croyances des agents lors des différentes phases du dialogue entre eux. L’inférence bayésienne consiste à évaluer comment les différentes déclarations des agents, modifient les probabilités des différents mondes vus ci-avant. Tout d’abord, on leur attribue des probabilités a priori, et ensuite, chaque affirmation d’un agent mène à leur remplacement par des probabilités conditionnelles.

Probabilités a priori

Toutes les probabilités auront pour dénominateur la factorielle de 5, soit 120, puisque c’est le nombre de manières d’ordonner les 5 cartes avant d’en distribuer 3.

  • Le monde F♥M♥D♥ a bien entendu une probabilité nulle puisqu’il n’y a en tout que deux cartes rouges dans le jeu complet.
  • F♥M♥→D♠ peut être obtenu de 6 (nombre de façons de permuter les 3 cartes noires) fois 2 (nombre de manières de permuter les deux cartes rouges) soit 12 manières possibles ; sa probabilité est donc 12/120=1/10=0,1.
  • F♥→M♠→D♥ et F♠→M♥D♥ sont également de probabilité 1/10=0,1.
  • F♥→M♠→D♠ est défini par le choix d’une carte rouge distribuée à Franck (deux possibilités) et de deux cartes noires (parmi trois : 3 possibilités) distribuées à Marc et Daniel. Ce nombre de possibilités doit être multiplié par 2 (échange de la carte rouge et de la carte noire non distribuées) et encore par 2 (on ne change pas la configuration en échangeant les cartes de Marc et Daniel) ; soit 24 possibilités ; donc sa probabilité est 24/120=⅕=0,2.
  • F♠→M♥→D♠ est aussi de probabilité ⅕
  • F♠→M♠→D♥, aussi a pour probabilité ⅕.
  • F♠→M♠→D♠ est de probabilité 1/10 puisqu’il y a 6 manières de ranger les cartes noires, fois deux manières de ranger les deux cartes rouges non distribuées.

On vérifie que 0,1+0,1+0,1+0,2+0,2+0,2+0,1=1 comme il se doit.

Probabilités modifiées par l’annonce de Franck

Comme on parle de probabilités, on ne notera plus la conjonction « et » par un ∧ mais par la notation probabiliste ∩.

L’annonce de Franck est liée à l’évènement conditionnant M♠ ∪ D♠ ; la probabilité de cet évènement est 0,9 d’après les résultats ci-dessus (la probabilité de son contraire est 1/10). D’après la définition des probabilités conditionnelles, les probabilités ci-dessus sont divisées par 9/10, soit

  1. F♥M♥→D♠ n’est plus de probabilité 1/10, mais maintenant sa probabilité a augmenté ; elle est passée à 1/9.
  2. F♥→M♠→D♥ voit aussi sa probabilité passer de 1/10 à 1/9 ;
  3. mais F♠→M♥D♥ est maintenant de probabilité (conditionnelle) nulle.
  4. F♥→M♠→D♠ voit sa probabilité passer de ⅕ à 2/9.
  5. F♠→M♥→D♠ est aussi de probabilité 2/9 maintenant.
  6. F♠→M♠→D♥, aussi a pour probabilité 2/9.
  7. F♠→M♠→D♠ voit sa probabilité passer de 1/10 à 1/9, une augmentation donc.

Probabilités modifiées par l’annonce de Marc

Par son annonce, Marc change à nouveau l’univers de probabilité, l’évènement conditionnant étant le contraire de M♠ ∩ D♥. Ce dernier est la réunion des deux évènements 2 et 6 ci-dessus, et leur probabilité va donc devenir nulle ; de plus, ils sont disjoints et la probabilité de leur réunion est 1/9+2/9=⅓. La probabilité de l’évènement conditionnant (qui est la réunion des évènements 1,3,4,5 et 7) est donc 1-⅓=⅔. Chacun de ces évènements va donc voir sa probabilité divisée par ⅔ ; soit

  1. F♥M♥→D♠ dont la probabilité 1/10 est passée à 1/9, a comme nouvelle probabilité ⅙.
  2. F♥→M♠→D♥ voit sa probabilité devenir nulle (incompatible avec l’évènement conditionnant) ;
  3. mais F♠→M♥D♥ reste de probabilité nulle.
  4. F♥→M♠→D♠ dont la probabilité était passée de ⅕ à 2/9, est maintenant passée à ⅓.
  5. F♠→M♥→D♠ est aussi de probabilité ⅓ maintenant.
  6. F♠→M♠→D♥, est maintenant impossible (ou plutôt incompatible avec l’évènement conditionnant).
  7. F♠→M♠→D♠ voit sa probabilité passer de 1/9 à ⅙.

Par addition, on peut donc en déduire la probabilité des couleurs des cartes de chacun :

  • P(F♥)=⅙+⅓=½ (mais après être passée à 4/9 après l’annonce de Franck) ;
  • Donc P(F♠)=½ aussi (après être passée à 5/9 lors de l’annonce de Franck).
  • P(M♥)= ⅙+⅓=½ (sa valeur initiale était ⅖ comme pour les autres, et elle était passée à ⅓ lors de l’annonce de Franck ; elle n’a donc fait qu’augmenter lors des différentes annonces).
  • P(M♠)=½ (mais comme elle valait ⅗ au début, elle a décru en commençant même par augmenter à ⅔).
  • P(D♠)=1 (valeur initiale : ⅗ puis après l’annonce de Franck, ⅔).
  • P(D♥), initialement égale à ⅖, est descendue à ⅓ après l’annonce de Franck, pour finalement chuter à 0 après l’annonce de Marc.

Voici l’évolution temporelle des probabilités que la carte de chacun soit rouge :

et l’évolution des probabilités que la carte de chacun soit noire :


[1parce que l’utilisation essentielle de la logique épistémique est l’informatique théorique, où les processeurs ont, ou non, accès à la valeur de certaines variables, comme par exemple dans un système bicœur ; les agents ne sont donc pas nécessairement des personnes


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 11 octobre 2017, 14h-18h, campus du Tampon
- Mercredi 22 novembre 2017, 14h-18h, campus du Tampon
- Mercredi 7 février 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 7 mars 2018, 14h-18h, campus du Tampon
- Mercredi 4 avril 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 2 mai, 14h-18h, campus du Tampon
- Mardi 5 juin 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 6 juin, 14h-18h, campus du Tampon

Fête de la science

Du 13 au 18 novembre 2017.
Thème : « La recherche à l’heure du numérique »

Semaine des mathématiques

Du 26 au 31 mars 2018.
Thème : « Mathématiques et mouvement »


Brèves

Décès de Raymond Smullyan

mercredi 15 mars

Le logicien Raymon Smullyan est décédé en février 2017, à l’âge respectable de 97 ans : Il avait eu Alonzo Church comme professeur ! Pour en savoir plus, voir cet article

Travailler à plusieurs

lundi 19 décembre 2016

Les enseignements d’exploration au lycée imposent aux enseignants de travailler ensemble. Chantal Tuffery-Rochdi a analysé dans sa thèse les pratiques des enseignants de MPS (méthodes et pratiques scientifiques). Elle répond aux questions des Cahiers pédagogiques.

Un document sur Eduscol

mardi 19 mai 2015

Un document clarifiant bien la façon dont les mêmes concepts vivent en mathématiques et dans les sciences « exactes » les utilisant, publié par Eduscol en octobre 2014. Citons-les :
« Le document proposé ci-dessous s’adresse aux professeurs de mathématiques, physique-chimie et sciences de l’ingénieur intervenant dans le segment [Bac-3 ; Bac+3]. Il vise à les informer des différences de présentation et d’interprétation qui sont faites de certains concepts mathématiques dans les autres disciplines. Ces éclaircissements peuvent contribuer à harmoniser et à clarifier l’utilisation de ces notions auprès des élèves. »

Histoire de la comptabilité

vendredi 28 décembre 2012

Sur ce site (en anglais) dédié à la comptabilité, on trouve des informations intéressantes sur l’histoire et les pratiques de ce domaine, qui peuvent être utiles aux professeurs enseignant des mathématiques financières (et aussi aux autres...).

La CGE et la réforme des lycées

lundi 16 janvier 2012

La Conférence des Grandes Écoles publie 19 préconisations pour la réforme du lycée.

Sur le Web : Les 19 préconisations

Pratique des mathématiques en série STD2A

lundi 16 janvier 2012

Le site de l’IGEN offre des recommandations et des ressources pour enseigner les mathématiques en série STD2A. Les thèmes abordés (couleurs et nuances de gris, arcs et architecture, jeux vidéos, photo et tableur, perspectives parallèles...) sont de nature à donner aussi des idées d’activités aux enseignants des autres séries !

En cheminant avec Kakeya

lundi 16 janvier 2012

Un livre (à télécharger) de Vincent Borelli et Jean-Luc Rullière qui présente le calcul intégral et la dérivation en s’appuyant sur la question de Kakeya. Pour les lycéens, les étudiants et tous les esprits curieux qui souhaitent voir les mathématiques sous un jour différent.

Sur le Web : Livre à télécharger

Bicentenaire Galois

lundi 12 septembre 2011

À l’occasion du bicentenaire de la naissance d’Évariste Galois (1811-2011), l’Institut Henri Poincaré et la Société mathématique de France organisent un ensemble de manifestations et proposent un site contenant diverses ressources documentaires susceptibles d’intéresser les enseignants.

Statistiques

Dernière mise à jour

jeudi 12 octobre 2017

Publication

772 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

231 aujourd'hui
1277 hier
2129922 depuis le début
37 visiteurs actuellement connectés