cours-LOG-MOD-1

8/17/2019 cours-LOG-MOD-1

1/47

BibliographieIntroduction

Logique modale propositionnelle

Cours 1 : Logique modale

Odile PAPINI

POLYTECHUniversité d’[email protected]

http://odile.papini.perso.esil.univmed.fr/sources/MASTER2-RE-OP.html

Odile PAPINI MASTER SIS OPTION LOGIQUE

http://find/


2/47



Plan du cours

1 Bibliographie

2 Introduction

3



http://find/http://goback/


3/47



Bibliographie 1 I

Chellas B. F., Modal logic : an introduction,Cambridge University Press, 1980.

Hughes G. E. & Cresswell M. J., A new introduction to modal logic ,

Taylor & Francis 2001.

Blackburn. P. & de Rijke M. & Venema Y., Modal logic ,Cambridge University Press 2001.

Wooldridge., reasoning about rational agents ,MIT Press, 2000.

Wooldridge., An Introduction to multiagents systems ,John Wiley & Sons, (second edition) 2009.


http://find/


4/47



Bibliographie 2 I

Supports de cours logique modale

http ://www.irit.fr/ Andreas.Herzig/CLmai/

http ://www.lipn.univ-paris13.fr/ levy/pdf/CoursLogMod.pdf

http ://www.guillaume.piolle.fr/doc/logique-modale.pdf


Bibli hi



5/47



Logique modale propositionnelle : introduction

Logique classique

logique propositionnelle

sens des formules facile à appréhendercomplexité calculatoire abordableMAIS sémantique et expressivité limitée

logique des prédicats

plus expressiveMAIS complexité calculatoire élevéesens des formules parfois difficile à comprendre


Bibli hi

http://find/


6/47




Limites de l’expressivité de la logique propositionnelle

logique classique : assertions factuelles binaires

tout énonçé est qualifié de vrai ou de faux : il pleut, 2 + 2 = 5,· · ·formules complexes valuées en fonction de leurs composants :sémantique extensionnelle

logique classique : pas toujours adéquate pour leraisonnement

raisonnement sur l’incertainraisonnement sur les situations évolutives


Bibliographie

http://find/


7/47




Logique modale : extension de la logique propositionnelle

formalisation d’énonçés non factuels

raisonnement sur l’incertain et les situations évolutives

logique modale

introduction de modalités pour la compréhension desformules

expressivité : entre la logique propositionnelle et la logique desprédicats

complexité calculatoire mâıtrisée


Bibliographie



8/47




modalit́en’importe quoi qui donne du sens

exprime la sémantique d’un verbe, d’un adjectif, d’un adverbe,· · · portant sur une formule

exemples de modalités

“l’agent sait que”, “l’agent croit que”, “l’agent a confiance en lefait que”, “il sera dorénavant vrai que”, “il est possible que”, “il estnécessaire que”, “il est évident que”, “il est obligatoire que” · · ·

représentation et raisonnement à un niveau élevé d’abstraction

modèle mental d’un agent

description d’une organisation, · · ·


Bibliographie



9/47




modalités : exemples

alétiques : il est possible qu’il pleuve

épistémiques : l’agent sait qu’il pleut, l’agent croit qu’il pleut

temporelles : il va pleuvoir, il a plu

déontiques : il doit pleuvoir

etc· · · autres modalités ou mélanges de modalités


Bibliographie

http://find/


10/47




Ajout de symboles de modalité :

et F une formule de la logique propositionnelle

F : F est nécessaire, toujours vrai, connu, obligatoire, · · ·

F : F est possible, parfois vrai, concevable, permis, · · ·

impossibilité de définir une sémantique extensionnelle

F ¬F F F ¬F ¬F 1 0 ? 1 0 ?

0 1 0 ? ? 1

sémantique basée sur les mondes possibles

distinguer entre situations (alternatives imaginables)“mondes possibles”


Bibliographie

http://find/


11/47

g pIntroduction



sémantique des mondes possibles : exemple


Bibliographie

http://find/


12/47

g pIntroduction



carré logique Aristote

Figure: source : Jean-Claude Choul


Bibliographie

http://find/


13/47

IntroductionLogique modale propositionnelle


Figure: source : cours G. Piolle


Bibliographie



14/47



Soit p une proposition : “il pleut”

exemples de formules épistémiques

p il pleut,

¬p il ne pleut pas,p l’agent sait qu’il pleut,¬p l’agent sait qu’il ne pleut pas,p l’agent tient pour concevable qu’il pleuve,¬p l’agent tient pour concevable qu’il ne pleuve pas,p l’agent sait qu’il sait qu’il pleut,¬p l’agent sait qu’il ne sait pas s’il pleut.


BibliographieI d i

http://find/


15/47



exemple : Le probl̀eme des trois conseillers. J. Mc Carthy. 1978

Un roi désirant savoir lequel de ses trois conseillers est le plusagace peint un point blanc sur le front de chacun d’eux. Le roileur dit qu’il a peint un point blanc ou un point noir sur le front de

chacun et qu’au moins un des points est blanc ; il demande ensuitechaque conseiller de deviner la couleur de son propre point.Aprés un temps de réflexion le premier répond qu’il ne sait pas.Entendant cela le second répond qu’il ne sait pas non plus.Aprés avoir entendu la réponse des deux premiers, le troisièmedéclare que son point est blanc.

Pourquoi ?


BibliographieI t d ti

http://find/


16/47



exemple : Le probl̀eme des trois conseillers. J. Mc Carthy. 1978

Formalisation en logique modale multi-agents S5

si un conseiller a un point blanc les autres le savent

si si un conseiller n’a pas de point blanc les autres le savent

au moins un conseiller a un point blanc

les conseillers 1 et 2 ne connaissent pas la couleur de leurpoint

preuveAvec ces hypothèses on peut démontrer par une dérivation enlogique épistemique S5 multi-agents que le troisième conseiller saitqu’il a un point blanc.



http://find/


17/47



Le langage de logique modale propositionnelle

Vocabulaire

un ensemble infini dénombrable de propositions

les constantes : 0 (Faux) et 1 (Vrai)

les connecteurs : ¬, ,

∧,

∨,

→,

↔les modalités : ,



http://find/


18/47



Définitions

formules bien formées de la logique modale propositionnelle :

• 0 et 1 sont des formules• une variable propositionnelle est une formule• si A et B sont des formules alors

¬ A, A ∧ B , A ∨ B , A → B , A ↔ B sont des formules• si A est une formule alors A, A sont des formules• si A est une formule alors A =def ¬¬A





19/47



Système formel de la logique modale propositionnelle(système K )

les axiomessoit A, B , C des formules de la logique modale propositionnelle

A1) (A → (B → A))

A2) ((A → (B → C )) → ((A → B ) → (A → C )))

A3) ((¬ A → ¬ B ) → (B → A))

K) ((A → B ) → (A → B ))



http://find/


20/47



règles de déduction

modus ponens

Γ A, ∆ A → B

Γ, ∆ B

nécéssité (règle N)

Γ A

Γ A





21/47



K -dérivation (déduction)

F : une formule modale, Γ : un ensemble de formules modales

une K -dérivation de F à partir de Γ est une séquence de formulesse terminant par F , dont chaque formule est :

soit une axiome

soit un membre de Γ

soit obtenu par l’application des règles de substitution, demodus ponens ou de nécessité

une K -preuve de F est une K -dérivation de F à partir de ∅ : F





22/47



Quelques théorèmes du système K

K1) (P ∧ Q ) → (P ∧ Q )

K2) (P ∧ Q ) → (P ∧ Q )

K3) (P ∧ Q ) ↔ (P ∧ Q )





23/47



règles dérivées

DR 1) A→B A→B

DR 2) A↔B A↔B

DR 3) A→B A→B

Eq ) si A ↔ B remplacer A par B (ou B par A)



L i d l i i ll



24/47



règles dérivées plus générales :

régularité pour (r̀egle R)

Γ A → B

Γ A → B

régularité généralisée pour

Γ (A1 ∧ · · · ∧ An) → B

Γ ( A1 ∧ · · · ∧ An) → B régularité pour

Γ A → B

Γ A → B



L i d l iti ll

http://find/


25/47



Quelques théorèmes du système K (suite)

K4) (P ∨ Q ) → (P ∨ Q )

K5) P ↔ ¬ ¬P

K6) (P ∨ Q ) ↔ (P ∨ Q )

K7) (P → Q ) ↔ (P → Q )

K8) (P ∧ Q ) → (P ∧ Q )

K9) (P ∨ Q ) → (P ∨ Q )




http://find/


26/47



D’autres axiomesT) A → A : tout ce qui est su (cru) est vrai

D) A → A : tout ce qui est su (cru) est cohérent

B) A → A : rien n’est vrai sans qu’on ne sache qu’ilpeut être su (cru)

4) A → A : si on sait (croit) A alors on sait qu’on

sait (croit) A

5) A → A : si on ne sait (croit) pas A alors on saitqu’on ne sait (croit) pas A (croit) A




http://find/


27/47



Système formel K : formé à partir des axiomes, A1, A2, A3, K

Système formel KT : formé à partir des axiomes, A1, A2, A3, Ket de l’axiome de la connaisance T) : A → A

Système formel KT4 ou S4 : formé à partir des axiomes, A1,A2, A3, K, T et del’axiome d’introspection positive 4) : A → A

Système formel KT45 ou S5 : formé à partir des axiomes, A1,A2, A3, K, T, 4 et del’axiome d’introspection négative 5) : A → A




http://find/


28/47



Quelques théorèmes du système T

T1) P → P

T2) (P → P )




http://find/


29/47



Quelques théorèmes du système S 4

S4-1) P → P

S4-2) P ↔ P

S4-3) P ↔ P S4-4) P → P

S4-5) P → P

S4-6) P ↔ P

S4-7) P ↔ P




http://find/


30/47

g q p p


Quelques théorèmes du système S 5

S5-1) P → P

S5-2) P ↔ P

S5-3) P ↔ P S5-4) (P ∨ Q ) ↔ (P ∨ Q )

S5-5) (P ∨ Q ) ↔ (P ∨ Q )

S5-6) (P ∧ Q ) ↔ (P ∧ Q )

S(5-7) (P ∧ Q ) ↔ (P ∧ Q )






31/47

g q p p


sémantique de la logique modale propositionnelle

sémantique des “mondes possibles”

une formule modale évaluée dans un “univers” de mondespossiblesune relation d’accessibilité lie les mondes possibles entre eux

A est vraie dans un monde possible ω si A est vraie dans tous

les mondes possibles accessibles à partir de ω

A est vraie dans un monde possible ω si A est vraie dans aumoins un monde possible accessible à partir de ω




http://find/


32/47

Exemple 1 : on lance une pièce de monnaie

p : ”on obtient PILE” f : ”on obtient FACE”

p est possible f est possiblep ∨ f est nécessairement VRAIp ∧ f est impossible : nécessairement FAUX


BibliographieIntroductionLogique modale propositionnelle

http://find/


33/47

Logique modale propositionnelle :sémantique

sémantique des mondes possibles : exemple



http://find/


34/47

Exemple 2 : on lance deux pièces de monnaie 1 et 2

p i : ”on obtient PILE pour i ” ¬p i : ”on obtient FACE pour i ”



http://find/


35/47


sémantique : définitions

système : paire (W , R) où W est l’ensemble des interprétationsdu langage et R est une relation binaire sur W ω, ω

∈ W , ωRω : ω est accessible à partir de ω

valuation : application v de W × P dans {0, 1} qui associe unevaleur de vérit́e v (ω, p ) à la variable p dans l’interprétation ω

modèle : triplet M = (W , R, v ) où (W , R) est un système et v une valuation

notation : M, ω |= F : F est vraie dans le monde possible ω pourle modèle M



http://find/


37/47


une formule A est valide dans un modèle M = (W , R, v ) ssi A estvraie dans tous les mondes possibles du modèle

notation M |= A

une formule A est valide dans un système (W , R) ssi A est vraiedans tout modèle M = (W , R, v )

notation (W , R) |= A

une formule A est valide (ou est une tautologie ), ssi A est vraiedans tout système (W , R)

notation |= A



http://find/


38/47

Exemple 2 : on lance deux pièces de monnaie 1 et 2M, ω1 |= p 1 M, ω2 |= p 1 M, ω3 |= p 1

M, ω1 |= (p 1 ∨ p 2) M, ω2 |= (p 1 ∨ p 2)M, ω2 |= ♦(p 1 ∨ p 2)



http://find/


39/47

Sémantique des mondes possibles : exercice

Figure: source : Stephan Merz



http://find/


40/47


Montrer :

A ≡ ¬¬A

|= (A → B ) → (A → B )

|= F (où si F est une tautologie )





41/47


Montrer que dans le système K les axiomes suivants ne sont pasdes tautologies :

T) A → A

4) A → A

5) A → A



L d l ll

http://find/


42/47


propriétés de R :

ŕeflexive : ∀ωi , ω j , ωi Rω j

sérielle : ∀ωi , ∃ω j , ωi Rω j

transitive : ∀ωi , ω j , ωk , si ωi Rω j et ω j Rωk alors ωi Rωk

euclidienne : ∀ωi , ω j , ωk , si ωi Rω j et ωi Rωk alors ω j Rωk

symétrique : ∀ωi , ω j , si ωi Rω j alors ω j Rωi



L i d l i i ll

http://find/


43/47


il y a une infinit́e de logiques modales qui se comportent plus ou

moins bien :

K : logique modale la plus faible, formule caractéristique :

(A → B ) → (A → B )

T : systèmes réflexifs, R est réflexive, formule caractéristique :

A → A

D : systèmes sériels, R est sérielle, formule caractéristique :

A → A

K 4 : systèmes transitifs, R est transitive, formulecaractéristique :

A → A



L i d l i i ll

http://find/


44/47


S 4 : systèmes réflexifs et transitifs, R est réflexive et transitive

KB : systèmes symétriques, R est symétrique, formulecaractéristique :

A → AB : systèmes réflexifs et symétriques, R est réflexive etsymétrique

S 5 : systèmes réflexifs, symétriques et transitifs R esteuclidienne, formule caractéristique :

¬A → ¬A



L i d l iti ll



45/47


résultats de correction et de complétude

le système formel K

théorème (de correction) : soit A une formule modale, si Aalors |= A(les formules qui sont des théorèmes du système K sont destautologies pour la classe K )

théorème (de compĺetude) : soit A une formule modale, si |= Aalors A



L i d l iti ll

http://find/


46/47


résultats de correction et de complétude

système formel T

théorème : A → A est une tautologie ssi R est réflexive

système formel S 4

théorème : A → A est une tautologie ssi R est transitive

système formel S 5

théorème : ¬A → ¬A est une tautologie ssi R esteuclidienne




http://find/


47/47


quelques résultats de décidabilité

définition : une logique modale L poss̀ede la propríet́e de modèle

fini si pour toute formule A qui n’est pas valide dans L , il existeun modèle fini dans lequel A est falsifié

proposition : si une logique modale L possède une procédure depreuve et la propriété de modèle fini alors L est décidable

théorème : K , T , S 4, S 5 sont décidables

http://find/

Documents

cours-LOG-MOD-1