IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Logique modale et intensionnalite
Paul Egre
Institut Jean-Nicod, CNRShttp://paulegre.free.fr
Ateliers JSM, Bordeaux, 28 mars 2006
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
References utiles
R. Montague 1968, ‘Pragmatics’M. Aloni 2005, ‘Individual Concepts in Modal PredicateLogic’, Journal of Philosophical Logic.P. Blackburn 1999, M. de Rijke et Y. Venema, Modal Logic,Cambridge.M. Fitting & R. Mendelsohn (1998), First-Order ModalLogic, Kluwer.G.E. Hughes & M.J. Cresswell (1996), A new Introductionto Modal Logic, Routledge.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Parcours prevu
1 Logique modale propositionnelle2 Logique modale quantifiee
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Syntaxe, Semantique et Pragmatique
Montague 1968, sur la division de Morris 1938 :Syntax : ‘relations between linguistic expressions’Semantics : ‘relations between expressions and theobjects to which they refer’Pragmatics : ‘relations among expressions, the objects towhich they refer, and the users or contexts of use of theexpressions’
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
L’indexicalite
Montague 1968 : ‘pragmatics concern itself with what C. S.Peirce had in the last century called indexical expressions,that is words and sentences of which the reference cannotbe determined without knowledge of the context of use;examples are the words ‘I’ and ‘here’, as well as sentencesinvolving tenses’
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique et Pragmatique
‘It seemed to me desirable that pragmatics should at leastinitially follow the lead of semantics, which is primarilyconcerned with the notion of truth (in a model, or under aninterpretation), and hence concern itself also with truth -but withrespect not only to an interpretation but also to a context ofuse’.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Logique modale et pragmatique
Un langage pragmatique : un langage du premier ordreavec egalite et operateurs modauxindices, points de reference et mondes possibles‘For instance, if the only indexical feature of L were theoccurrence of tense operators, then the points of referencemight naturally be chosen as moments of time, regardedas possible moments of utterance’
exemples :‘il pleut’, vrai ou faux selon le contexte‘j’aime lire’ : vrai ou faux selon le locuteur
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Interpretation, Extension et Intension
Semantique : interpretation < W ,D, I >
W = ensemble des mondesD = domaine d’individus DI = fonction d’interpretation, de domaine L×W
Extension = denotation relativement a un mondeIntension = fonction des mondes dans les extensionsExemple : constante d’individu c = ‘le president Americain’(Montague 1968, 99) : ‘we should specify for each moment ithe person regarded as the American President at i ’I(c)(w)= Richard Nixon, I(c)(w ′)=George Bush
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Logiques modales et Pragmatique
‘When we come to consider special disciplines comprehendedby pragmatics - disciplines such as tense logic, modal logic, thelogic of personal pronouns...’⇒ logique temporelle, logique modale standard, logiquedeontique
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Logique epistemique et pragmatique
Montague 1968 n’inclut pas explicitement la logiqueepistemique parmi les specialisations de la pragmatique.Cependant, les verbes d’attitude comme ‘croire’ ou ‘savoir’introduisent de l’indexicalite:
‘il pleut’ vs ‘Pierre croit qu’il pleut’monde reel vs mondes de croyance
Objet de cet atelier : logique modale et applications.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Langage
Alphabet: ensemble denombrable d’atomes p, q, r ,...
1 Atomes: tout atome est une formule2 Si φ est une formule, ¬φ est une formule3 Si φ et ψ sont des formules, alors (φ ∧ ψ) est une formule.4 Si φ est une formule, alors �φ est une formule.5 Rien d’autre n’est une formule.
Abbreviations: ♦φ:= ¬�¬φ(φ ∨ ψ) := ¬(¬φ ∧ ¬ψ)(φ→ ψ) := ¬(φ ∧ ¬ψ)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Semantique de Leibniz-Carnap
Leibniz: une formule est necessairement vraie ssi elle est vraiedans tous les mondes possibles.
Un modele M = 〈W ,V 〉 est un couple constitue d’un ensembleW (de mondes possibles), et d’une fonction d’interpretation Vqui associe a chaque atome du langage un sous-ensemble demondes possibles. La satisfaction des enonces est relative achaque monde possible.
(i) M,w |= p ssi w ∈ V (p)(ii) M,w |= ¬φ ssi M,w 2 φ(iii) M,w |= (φ ∧ ψ) ssi M,w |= φ et M,w |= ψ(iv) M,w |= �φ ssi pour tout v ∈ W , M, v |= φ
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Semantique de Leibniz-Carnap
Leibniz: une formule est necessairement vraie ssi elle est vraiedans tous les mondes possibles.
Un modele M = 〈W ,V 〉 est un couple constitue d’un ensembleW (de mondes possibles), et d’une fonction d’interpretation Vqui associe a chaque atome du langage un sous-ensemble demondes possibles. La satisfaction des enonces est relative achaque monde possible.
(i) M,w |= p ssi w ∈ V (p)(ii) M,w |= ¬φ ssi M,w 2 φ(iii) M,w |= (φ ∧ ψ) ssi M,w |= φ et M,w |= ψ(iv) M,w |= �φ ssi pour tout v ∈ W , M, v |= φ
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Semantique de Leibniz-Carnap
Leibniz: une formule est necessairement vraie ssi elle est vraiedans tous les mondes possibles.
Un modele M = 〈W ,V 〉 est un couple constitue d’un ensembleW (de mondes possibles), et d’une fonction d’interpretation Vqui associe a chaque atome du langage un sous-ensemble demondes possibles. La satisfaction des enonces est relative achaque monde possible.
(i) M,w |= p ssi w ∈ V (p)(ii) M,w |= ¬φ ssi M,w 2 φ(iii) M,w |= (φ ∧ ψ) ssi M,w |= φ et M,w |= ψ(iv) M,w |= �φ ssi pour tout v ∈ W , M, v |= φ
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Validite
Definition: on dit que φ est valide, et on note |= φ, ssi pour toutmodele M et tout monde w du modele, M,w |= φ.
ex: |= �φ→ φPreuve: soit M = 〈W ,V 〉 et w ∈ W tels que M,w |= �φ.Alors pout tout v ∈ W , M, v |= φ, donc en particulierM,w |= φ. Donc M,w |= �φ→ φ.ex: 2 φ→ �φPreuve: soit W = {w , v} tel que: w(p) = 1, v(p) = 0.On a: M,w |= p. Mais M,w 2 �p, puisque M, v |= ¬p.Donc M,w 2 p → �p.Comparer: ”S’il est necessaire qu’il pleuve, alors il pleut””S’il pleut, alors il est necessaire qu’il pleuve”.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Validite
Definition: on dit que φ est valide, et on note |= φ, ssi pour toutmodele M et tout monde w du modele, M,w |= φ.
ex: |= �φ→ φPreuve: soit M = 〈W ,V 〉 et w ∈ W tels que M,w |= �φ.Alors pout tout v ∈ W , M, v |= φ, donc en particulierM,w |= φ. Donc M,w |= �φ→ φ.ex: 2 φ→ �φPreuve: soit W = {w , v} tel que: w(p) = 1, v(p) = 0.On a: M,w |= p. Mais M,w 2 �p, puisque M, v |= ¬p.Donc M,w 2 p → �p.Comparer: ”S’il est necessaire qu’il pleuve, alors il pleut””S’il pleut, alors il est necessaire qu’il pleuve”.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Validite
Definition: on dit que φ est valide, et on note |= φ, ssi pour toutmodele M et tout monde w du modele, M,w |= φ.
ex: |= �φ→ φPreuve: soit M = 〈W ,V 〉 et w ∈ W tels que M,w |= �φ.Alors pout tout v ∈ W , M, v |= φ, donc en particulierM,w |= φ. Donc M,w |= �φ→ φ.ex: 2 φ→ �φPreuve: soit W = {w , v} tel que: w(p) = 1, v(p) = 0.On a: M,w |= p. Mais M,w 2 �p, puisque M, v |= ¬p.Donc M,w 2 p → �p.Comparer: ”S’il est necessaire qu’il pleuve, alors il pleut””S’il pleut, alors il est necessaire qu’il pleuve”.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Validite
Definition: on dit que φ est valide, et on note |= φ, ssi pour toutmodele M et tout monde w du modele, M,w |= φ.
ex: |= �φ→ φPreuve: soit M = 〈W ,V 〉 et w ∈ W tels que M,w |= �φ.Alors pout tout v ∈ W , M, v |= φ, donc en particulierM,w |= φ. Donc M,w |= �φ→ φ.ex: 2 φ→ �φPreuve: soit W = {w , v} tel que: w(p) = 1, v(p) = 0.On a: M,w |= p. Mais M,w 2 �p, puisque M, v |= ¬p.Donc M,w 2 p → �p.Comparer: ”S’il est necessaire qu’il pleuve, alors il pleut””S’il pleut, alors il est necessaire qu’il pleuve”.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Exercice
Determiner si les formules suivantes sont valides:
(1) �p → ��p(2) �p → ♦�p(3) �(p ∨ q) → �(p ∨ q)
(4) ♦(p ∨ q) → (♦p ∨ ♦q)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Lien avec la logique quantifiee
Fonction de traduction ST : des enonces de la logique modalevers ceux de la logique des predicats:
STx(p) = P(x)STx((φ ∧ ψ)) = (STx(φ) ∧ STx(ψ))STx(¬φ) = ¬STx(φ)STx(�φ) = ∀xSTx(φ)STx(♦φ) = ∃xSTx(φ)
Par exemple :STx(�(p → q) ∨�(q → p)) = ∀x(P(x) → Q(x)) ∨ ∀x(Q(x) →P(x))
STx(�♦p)) = ∀xSTx(♦p) = ∀x∃xP(x)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Lien avec la logique quantifiee
Fonction de traduction ST : des enonces de la logique modalevers ceux de la logique des predicats:
STx(p) = P(x)STx((φ ∧ ψ)) = (STx(φ) ∧ STx(ψ))STx(¬φ) = ¬STx(φ)STx(�φ) = ∀xSTx(φ)STx(♦φ) = ∃xSTx(φ)
Par exemple :STx(�(p → q) ∨�(q → p)) = ∀x(P(x) → Q(x)) ∨ ∀x(Q(x) →P(x))
STx(�♦p)) = ∀xSTx(♦p) = ∀x∃xP(x)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Lien avec la logique quantifiee
Fonction de traduction ST : des enonces de la logique modalevers ceux de la logique des predicats:
STx(p) = P(x)STx((φ ∧ ψ)) = (STx(φ) ∧ STx(ψ))STx(¬φ) = ¬STx(φ)STx(�φ) = ∀xSTx(φ)STx(♦φ) = ∃xSTx(φ)
Par exemple :STx(�(p → q) ∨�(q → p)) = ∀x(P(x) → Q(x)) ∨ ∀x(Q(x) →P(x))
STx(�♦p)) = ∀xSTx(♦p) = ∀x∃xP(x)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Verifonctionnalite
Syntaxiquement, � et ♦ sont des operateurs unaires, comme lanegation ¬. Mais ce ne sont pas des operateursverifonctionnels:
Pour la negation, on a: si w(φ) = w(ψ), alorsw(¬φ) = w(¬ψ).Mais on peut avoir: w(φ) = w(ψ), sans quew(�φ) = w(�ψ)
ex: W = {w , v}. On pose: V (p) = W , V (q) = {w}.Alors: w(p) = w(q) = 1. Mais w(�p) = 1, mais w(�q) = 0.
C’est en ce sens que � et ♦ sont des operateurs intensionnels.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Verifonctionnalite
Syntaxiquement, � et ♦ sont des operateurs unaires, comme lanegation ¬. Mais ce ne sont pas des operateursverifonctionnels:
Pour la negation, on a: si w(φ) = w(ψ), alorsw(¬φ) = w(¬ψ).Mais on peut avoir: w(φ) = w(ψ), sans quew(�φ) = w(�ψ)
ex: W = {w , v}. On pose: V (p) = W , V (q) = {w}.Alors: w(p) = w(q) = 1. Mais w(�p) = 1, mais w(�q) = 0.
C’est en ce sens que � et ♦ sont des operateurs intensionnels.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Verifonctionnalite
Syntaxiquement, � et ♦ sont des operateurs unaires, comme lanegation ¬. Mais ce ne sont pas des operateursverifonctionnels:
Pour la negation, on a: si w(φ) = w(ψ), alorsw(¬φ) = w(¬ψ).Mais on peut avoir: w(φ) = w(ψ), sans quew(�φ) = w(�ψ)
ex: W = {w , v}. On pose: V (p) = W , V (q) = {w}.Alors: w(p) = w(q) = 1. Mais w(�p) = 1, mais w(�q) = 0.
C’est en ce sens que � et ♦ sont des operateurs intensionnels.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Correspondance
Etant donne une structure d’interpretation M = 〈W ,V 〉, onnote:
M |= STx(φ) [x := w ] pour dire que M satisfait la formuleSTx(φ) lorsqu’on donne pour valeur w a la variable libre x .Lorsque x est liee par un quantificateur, on pose:M |= ∀xφ [x := w ] ssi pour tout d dans U, M |= φ [x := d ].
M,w |= φ ssi M |= STx(φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Correspondance
Etant donne une structure d’interpretation M = 〈W ,V 〉, onnote:
M |= STx(φ) [x := w ] pour dire que M satisfait la formuleSTx(φ) lorsqu’on donne pour valeur w a la variable libre x .Lorsque x est liee par un quantificateur, on pose:M |= ∀xφ [x := w ] ssi pour tout d dans U, M |= φ [x := d ].
M,w |= φ ssi M |= STx(φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Correspondance
Etant donne une structure d’interpretation M = 〈W ,V 〉, onnote:
M |= STx(φ) [x := w ] pour dire que M satisfait la formuleSTx(φ) lorsqu’on donne pour valeur w a la variable libre x .Lorsque x est liee par un quantificateur, on pose:M |= ∀xφ [x := w ] ssi pour tout d dans U, M |= φ [x := d ].
M,w |= φ ssi M |= STx(φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Correspondance
Etant donne une structure d’interpretation M = 〈W ,V 〉, onnote:
M |= STx(φ) [x := w ] pour dire que M satisfait la formuleSTx(φ) lorsqu’on donne pour valeur w a la variable libre x .Lorsque x est liee par un quantificateur, on pose:M |= ∀xφ [x := w ] ssi pour tout d dans U, M |= φ [x := d ].
M,w |= φ ssi M |= STx(φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Exemple
�(p ∨ q) vs �p ∨�q∀x(P(x) ∨Q(x)) vs ∀xP(x) ∨ ∀xQ(x)
Prenons pour W l’ensemble N des entiers naturels.P(x) := x est pair, Q(x) := x est impair
Comparer a : “tout entier pair est impair ou tout entier impairest pair”.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Preuve du theoreme
Par induction sur la complexite des formules.On pose pour tout atome p, V (p) = V (P).
M,w |= p ssi w ∈ V (p) ssi w ∈ V (P) ssiM |= P(x) [x := w ] ssi M |= STx(p) [x := w ]
La negation et les connecteurs binaires ne posent pas depb.M,w |= �φssi pour tout v ∈ W , M, v |= φssi pour tout v ∈ W , M |= STx(φ) [x := v ] (par hypothesed’induction)ssi M |= ∀xSTx(φ) [x := w ] (par definition)ssi M |= STx(�φ) [x := w ]
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Le carre aristotelicien des oppositions
Un operateur modal peut donc etre vu comme unquantificateur, et un modele 〈W , I〉 de logique modale peutaussi bien etre considere comme un modele pour une formulede la logique quantifiee.�p �¬p∀xP(x) ∀x¬P(x)
♦p ♦¬p∃xP(x) ∃x¬P(x)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Semantique de Kripke
On enrichit les modeles a l’aide de relations d’accessibilite. Unmodele de Kripke est un triplet 〈W ,R,V 〉 avec R une relationbinaire sur W ×W .
M,w |= p ssi w ∈ V (p)
M,w |= ¬φ ssi M,w 2 φ
M,w |= (φ ∧ ψ) ssi M,w |= φ et M,w |= ψ
M,w |= �φ ssi pour tout w ′ tel que wRw ′, M,w ′ |= φ
M,w |= ♦φ ssi il existe w ′ tel que wRw ′ et M,w ′ |= φ.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Semantique de Kripke
On enrichit les modeles a l’aide de relations d’accessibilite. Unmodele de Kripke est un triplet 〈W ,R,V 〉 avec R une relationbinaire sur W ×W .
M,w |= p ssi w ∈ V (p)
M,w |= ¬φ ssi M,w 2 φ
M,w |= (φ ∧ ψ) ssi M,w |= φ et M,w |= ψ
M,w |= �φ ssi pour tout w ′ tel que wRw ′, M,w ′ |= φ
M,w |= ♦φ ssi il existe w ′ tel que wRw ′ et M,w ′ |= φ.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Semantique de Kripke
On enrichit les modeles a l’aide de relations d’accessibilite. Unmodele de Kripke est un triplet 〈W ,R,V 〉 avec R une relationbinaire sur W ×W .
M,w |= p ssi w ∈ V (p)
M,w |= ¬φ ssi M,w 2 φ
M,w |= (φ ∧ ψ) ssi M,w |= φ et M,w |= ψ
M,w |= �φ ssi pour tout w ′ tel que wRw ′, M,w ′ |= φ
M,w |= ♦φ ssi il existe w ′ tel que wRw ′ et M,w ′ |= φ.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Quantification restreinte
La semantique de Kripke, comparee a celle de Carnap, traiteles operateurs modaux comme des quantificateurs restreints.
Comparer:Chacun est venu ∀xV (x)Chaque homme est venu ∀x(H(x) → V (x))Quelqu’un est venu ∃xV (x)Un homme est venu ∃x(H(x) ∧ V (x))
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Validite
Definition: on appelle 〈W ,R〉 un cadreUne formule est valide ssi pour tout cadre et tout modele deKripke base sur ce cadre, elle est vraie en tout monde dumodele.
ex: |= �(φ→ ψ) → (�φ→ �ψ)Preuve: supposons M,w |= �(φ→ ψ) et M,w |= �φ. Alors,pout tout w ′ tel que wRw ′, M,w ′ |= φ et M,w ′ |= φ→ ψ. DoncM,w ′ |= ψ. Ie M,w |= �ψ.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Validite
Definition: on appelle 〈W ,R〉 un cadreUne formule est valide ssi pour tout cadre et tout modele deKripke base sur ce cadre, elle est vraie en tout monde dumodele.
ex: |= �(φ→ ψ) → (�φ→ �ψ)Preuve: supposons M,w |= �(φ→ ψ) et M,w |= �φ. Alors,pout tout w ′ tel que wRw ′, M,w ′ |= φ et M,w ′ |= φ→ ψ. DoncM,w ′ |= ψ. Ie M,w |= �ψ.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Validite
Definition: on appelle 〈W ,R〉 un cadreUne formule est valide ssi pour tout cadre et tout modele deKripke base sur ce cadre, elle est vraie en tout monde dumodele.
ex: |= �(φ→ ψ) → (�φ→ �ψ)Preuve: supposons M,w |= �(φ→ ψ) et M,w |= �φ. Alors,pout tout w ′ tel que wRw ′, M,w ′ |= φ et M,w ′ |= φ→ ψ. DoncM,w ′ |= ψ. Ie M,w |= �ψ.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Invalidite
ex: 2 �φ→ φPreuve: soit W = {w , v} et R = {(w , v)}. V (p) = {v}.
w // vp
La semantique de Kripke est plus generale que celle deCarnap: en ajoutant des modeles, on perd des validites.Comparer:(1) Si chacun est venu, alors Pierre est venu:
√
(2) Si chaque linguiste est venu, alors Pierre est venu: ×
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Invalidite
ex: 2 �φ→ φPreuve: soit W = {w , v} et R = {(w , v)}. V (p) = {v}.
w // vp
La semantique de Kripke est plus generale que celle deCarnap: en ajoutant des modeles, on perd des validites.Comparer:(1) Si chacun est venu, alors Pierre est venu:
√
(2) Si chaque linguiste est venu, alors Pierre est venu: ×
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Invalidite
ex: 2 �φ→ φPreuve: soit W = {w , v} et R = {(w , v)}. V (p) = {v}.
w // vp
La semantique de Kripke est plus generale que celle deCarnap: en ajoutant des modeles, on perd des validites.Comparer:(1) Si chacun est venu, alors Pierre est venu:
√
(2) Si chaque linguiste est venu, alors Pierre est venu: ×
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Exercice
(i) Montrer que les formules suivantes ne sont pas valides:
(1) �p → ♦p(2) �p → ��p
(ii) Comparer les formules a:
(3) S’il est necessaire qu’il pleuve, alors il est possible qu’ilpleuve(4) S’il est necessaire qu’il pleuve, alors il est necessaire qu’ilsoit necessaire qu’il pleuve.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Exercice
(i) Montrer que les formules suivantes ne sont pas valides:
(1) �p → ♦p(2) �p → ��p
(ii) Comparer les formules a:
(3) S’il est necessaire qu’il pleuve, alors il est possible qu’ilpleuve(4) S’il est necessaire qu’il pleuve, alors il est necessaire qu’ilsoit necessaire qu’il pleuve.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Variete des modalites
(1) Modalites alethiques: il est necessaire que, il est possiblequeW= ensemble des mondes possiblesR= accessibilite metaphysique
(2) Modalites epistemiques: Pierre est certain que, Pierren’exclut pas queW= mondes epistemiques possiblesR= incertitude epistemique
(3) Modalites temporelles: il sera toujours le cas que, il seraparfois le cas queW= instants du tempsR= succession temporelle
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Contraintes sur R
La logique sous-jacente a chacune de ces expressionsmodales n’est pas necessairement la meme: on peutnotamment faire varier les contraintes sur R:exemples:
R est reflexive: ∀w(wRw)
R est symetrique: ∀x∀y(xRy → yRx)
R est transitive: ∀x∀y∀z(xRy ∧ yRz → xRz)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Quelques resultats de correspondence
�φ→ φ est valide dans un cadre 〈W ,R〉 ssi R est reflexive.
Preuve: (⇐): supposons R reflexive. Soit M et w tels queM,w |= �φ. Alors pour tout w ′ tel que wRw ′, M,w ′ |= φ, et parreflexivite, M,w |= φ.(⇒): supposons R non-reflexive. Ie il existe w tel que ¬wRw .Dans ce cas, soit V (p) = W − {w}. Clairement, M,w |= �p,mais M,w 2 p.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Quelques resultats de correspondence
�φ→ φ est valide dans un cadre 〈W ,R〉 ssi R est reflexive.
Preuve: (⇐): supposons R reflexive. Soit M et w tels queM,w |= �φ. Alors pour tout w ′ tel que wRw ′, M,w ′ |= φ, et parreflexivite, M,w |= φ.(⇒): supposons R non-reflexive. Ie il existe w tel que ¬wRw .Dans ce cas, soit V (p) = W − {w}. Clairement, M,w |= �p,mais M,w 2 p.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Quelques resultats de correspondence
�φ→ φ est valide dans un cadre 〈W ,R〉 ssi R est reflexive.
Preuve: (⇐): supposons R reflexive. Soit M et w tels queM,w |= �φ. Alors pour tout w ′ tel que wRw ′, M,w ′ |= φ, et parreflexivite, M,w |= φ.(⇒): supposons R non-reflexive. Ie il existe w tel que ¬wRw .Dans ce cas, soit V (p) = W − {w}. Clairement, M,w |= �p,mais M,w 2 p.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Exercices
1. Montrer de la meme facon que �p → ��p est valide dansun cadre ssi R est transitive.2. Montrer que p → �♦p est valide ssi R est symetrique.3. Montrer que �p → ♦p est valide dans un cadre ssi R estserielle, ie ssi ∀x∃yxRy .4. Montrer que ¬�p → �¬�p est valide dans un cadre ssi Rest euclidienne, ie ssi xRy ∧ xRz → yRz
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Resultats de correspondence
T �p → p R est reflexive4 �p → ��p R est transitive5 ¬�p → �¬�p R est euclidienneD �p → ♦p R est serielle
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Applications : logique epistemique
�p represente: “je sais que p”.On decrit canoniquement la connaissance par un systeme quisatisfait:
4: introspection positive5: introspection negativeT: veridiciteD: coherence
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Exemple: logique multi-modale
Un modele multi-agent: 〈W ,R1,R2,V 〉.
Situation: on donne a 1 et a 2 un nombre entier positif. Lesnombres sont necessairement consecutifs.
On represente la structure d’information par des couples(n,n + 1). On note: pn: “1 a le nombre n”, et “qn 2 a le nombren”.
1) Montrer que : dans la situation (3,4), on a: ♦1♦2p5.
2) On definit un operateur C1,2φ pour dire que φ estconnaissance commune entre 1 et 2: ie p, K1p, K2p, K1K1p,K2K1p, ... Montrer que relativement a (2,3), il n’est pasconnaissance commune que les agents ont un nombreinferieur a 100. (!)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Logique temporelle
Un modele lineaire du temps. Structure : 〈W , <,V 〉.
On considere deux modalites: F et P
M,w |= Fp ssi il existe w ′ tel que w > w ′ et M,w ′ |= pM,w |= Pp ssi il existe w ′ tel que w ′ < w et M,w ′ |= p
Par definition: Gp := ¬F¬pHp := ¬P¬p
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Liens avec le langage naturel
Approximations (cf. Blackburn, Tense, Temporal Reference andTense Logic).p Pierre gagne au lotoFp Pierre gagnera au lotoPp Pierre a gagne au lotoPPp (?) Pierre eut gagne au lotoFPp Pierre aura gagne au lotoPF Pierre gagnerait au loto
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Proprietes de la logique temporelle
Exercice: Montrer que
2 Fp → p|= Gp → Fp2 p → GFp|= Gp → GGp
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Exercice
On considere les trois cadres: (Z, <), (Q, <) et (R, <). Danslesquels de ces cadres la formule suivante est-elle valide (cf.Blackburn & al. 1999):
(p ∧ Hp) → FHp ?
Reponse: dans Z seulement (NB. noter la correction d’uneerreur sur R lors de l’expose).
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Limites de pouvoir expressif
La logique modale est-elle aussi expressive que la logique dupremier-ordre ?
Peut-on contraire une relation d’accessibilite a satisfaire:∀x¬Rxx ? ex: “Aucun instant n’est anterieur a lui-meme” ?Reponse: non
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Morphisme borne
Etant donne deux modeles 〈W ,R,V 〉 et 〈W ′,R′,V ′〉, f est unmorphisme borne ssi:
1. w |= p ssi f (w) |= p2. si wRv , alors f (w)R′f (v)3. si f (w)Rv ′, alors il existe v tel que wRv et v ′ = f (v).
ex: les entiers naturels avec < vs le cadre a un seul monde, telque xRx . On pose: f (n) = x pour tout n. Verifier que f est unmorphisme borne.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Invariance par morphisme borne surjectif
Surjectivite: tout element de F ′ est l’image d’un element de F
Proposition: si f est un morphisme borne surjectif de M versM ′, alors pout toute formule et tout w , M,w |= φ ssiM ′, f (w) |= φ.
Preuve: par induction. Si M,w |= ♦φ, alors il existe v tel quewRv et M, v |= φ. Par induction, M ′, f (v) |= φ, et parmorphisme, f (w)R′f (v), ie M ′, f (w) |= ♦φ. Idem pour lareciproque.Preuve
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Indefinissabilite
La notion de morphisme borne surjectif peut etre definie pourles cadres:
Proposition: S’il existe un morphisme surjectif de F vers F ′,alors si F |= φ, alors F ′ |= φ.
Preuve: supposons que F |= φ mais (F ′,V ′),w ′ 2 φ pour unevaluation V . On definit sur F la valuation:V (pi) := {w ∈ W ; f (w) ∈ V ′(pi)}. Alors f est un morphismesurjectif borne entre les modeles. Par surjectivite, il existe w telque f (w) = w ′.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Application
Proposition: ∀x¬Rxx n’est pas definissable. Soit f lemorphisme surjectif de F = 〈N, <〉 sur F ′ = {{w},R}, tel quewRw . Clairement, F |= ∀x¬x < x . Mais on n’a pasF ′ |= ∀x¬xRx . Donc cette propriete n’est pas definissablemodalement, sinon elle serait preservee.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique de CarnapSemantique de Kripke
Bilan
La logique modale propositionnelle n’a pas tout le pouvoirexpressif de la logique du premier ordre (bien qu’elle puisseaussi definir des conditions sur les cadres qui ne sont pasdefinissables au premier-ordre).
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
La logique modale du premier-ordre
La logique modale propositionnelle est une extension de lalogique propositionnelle par l’ajout des operateurs modaux.
On peut de la meme facon definir la logique modale dupremier-ordre en ajoutant au langage de la logique dupremier-ordre des modalites.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Langage
Alphabet: un ensemble denombrable de variables d’individus x ,y , z, ...Ensemble denombrable de symboles de predicats: P, Q, R
Formules atomiques: R(x1, ..., xn).Si φ est une formule, ¬φ est une formuleSi φ et ψ sont des formules, (φ ∧ ψ) est une formuleSi φ est une formule ∃xφ et ∀xφ sont des formulesSi φ est une formule, �φ et ♦φ sont des formules.Rien d’autre n’est une formule.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Exemples
∃x�P(x)
�∃xP(x)
∀x�∃yxRy
∀x�∃y♦xRy
....
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
La distinction de re-de dicto
(1) Necessairement quelqu’un gagnera a la loterie(2) Il y a quelqu’un qui, necessairement, gagnera a la loterie
(3) Je sais que quelqu’un gagnera a la loterie(4) Il y a quelqu’un dont je sais qu’il gagnera a la loterie
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
La distinction de re-de dicto
(1) Necessairement quelqu’un gagnera a la loterie(2) Il y a quelqu’un qui, necessairement, gagnera a la loterie
(3) Je sais que quelqu’un gagnera a la loterie(4) Il y a quelqu’un dont je sais qu’il gagnera a la loterie
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Distinctions de portee
En logique du premier-ordre, on distingue:
(1) ∀x∃yxRy(2) ∃y∀xxRy(3) Tout le monde aime quelqu’un(4) Il y a quelqu’un que tout le monde aime
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Portee des operateurs modaux
�∃xP(x): dans tout monde possible, il y a un P
∃x�P(x): il y a un x qui, dans tout monde possible, est P
Modalite de dicto: � prend portee large sur ∃
Modalite de re: � a portee etroite sur ∃
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
SemantiqueLogique du premier-ordre: rappel
Etant donne un langage L, on appelle L-structure (ou modele)un couple M = 〈U, I〉 constitue d’un univers d’interpretation(domaine d’individus) U et d’une fonction d’interpretation I.Pour R une relation a n arguments, I(R) ⊆ Un.Une fonction d’assignation g: assigne a chaque variable unindividu du domaine.g[d/x ]: l’assignation comme g qui assigne a x l’individu d
M,g |= R(x1, ..., xn) ssi (g(x1), ...,g(xn)) ∈ I(R)
M,g |= ¬φ ssi M,g 2 φ
M,g |= (φ ∧ ψ) ssi M,g |= φ et M,g |= ψ.M,g |= ∃xφ ssi il existe d ∈ U tel que M,w ,g[d/x ] |= φ.M,g |= ∀xφ ssi pour tout d ∈ U, M,g[d/x ] |= φ.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique pour la logique modale du premier-ordre
La logique modale du premier-ordre amene a introduireplusieurs domaines d’individus, autant que de mondes. Lecas le plus simple est celui ou les mondes ont le memedomaine d’individus.Un modele de LMPO : M = 〈W ,R,D, I〉, avec R unerelation d’accessibilite entre mondes de W , et D undomaine d’individus, et I une fonction d’interpretation quiassocie a chaque monde w et a chaque symbole P uneextension Iw (P).
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Les clauses de satisfaction sont les memes qu’aupremier-ordre, sauf qu’on a en plus un parametre de monde, et:
M,w ,g |= �φ ssi pour tout w ′ tel que wRw ′, M,w ′,g |= φ
Validite: φ est valide ssi φ est vrai en tout monde de toutmodele pour toute assignation.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Les clauses de satisfaction sont les memes qu’aupremier-ordre, sauf qu’on a en plus un parametre de monde, et:
M,w ,g |= �φ ssi pour tout w ′ tel que wRw ′, M,w ′,g |= φ
Validite: φ est valide ssi φ est vrai en tout monde de toutmodele pour toute assignation.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Exemple
A-t-on: |= ∀x♦P(x) → ♦∀xP(x) ?
Reponse: nonsoit W = {w1,w2,w3}, et D = {a,b}.On suppose: w1Rw2 et w1Rw3Iw2(P) = {a} et Iw3(P) = {b}.On considere une valuation arbitraire gOn a: M,w ,g |= ∀x♦P(x)Mais on n’a pas: M,w ,g |= ♦∀xP(x)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Exemple
A-t-on: |= ∀x♦P(x) → ♦∀xP(x) ?
Reponse: nonsoit W = {w1,w2,w3}, et D = {a,b}.On suppose: w1Rw2 et w1Rw3Iw2(P) = {a} et Iw3(P) = {b}.On considere une valuation arbitraire gOn a: M,w ,g |= ∀x♦P(x)Mais on n’a pas: M,w ,g |= ♦∀xP(x)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Exemple (suite)
Montrer que:|= ♦∀xP(x) → ∀x♦P(x).
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Semantique a domaines variables
Un modele= M = 〈W ,R,D, I〉 ou D est une fonction qui assignea chaque monde un domaine Dw . On pose: U =
⋃w∈W Dw .
Une assignation assigne a chaque variable un element de U, eta chaque symbole de relation une relation sur U.
M,w ,g |= R(x1, ..., xn) ssi (g(x1), ...,g(xn)) ∈ Iw (R).M,w ,g |= ∀xφ ssi pour tout element d de Dw , M,w ,g[d/x ] |= φ
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Formules de Barcan
(BF-∀) ∀x�φ→ �∀xφ(BF-♦) ♦∃xφ→ ∃x♦φ
Etablir la validite des formules de Barcan dans la semantique adomaine constant.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Formules de Barcan converses
(BFC-∀) �∀xφ→ ∀x�φ(BFC-∃) ∃x♦φ→ ♦∃xφ
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Domaine variable et formule de Barcan
Dw = {a}, Dv = {a,b}Iw (P) = ∅, et Iv (P) = {b}.wRv
Montrer que : ♦∃xP(x) → ∃x♦P(x) n’est pas valide.
Preuve: soit g(x) = bM, v ,g |= P(x)M, v ,g |= ∃xP(x)M,w ,g |= ♦∃xP(x)Mais M,w ,g 2 ∃x♦P(x), car a n’est pas P en v .
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Converse
∃x♦P(x) → ♦∃xP(x)
Contre-modele:w a,b↓v a P(b)
Relativement a w , b est possiblement P, mais dans v , aucunindividu de Dv n’est P.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Domaines croissants
Un modele est monotone (a domaines croissants) ssi pour toutw , v si wRv , alors Dw ⊆ Dv .
Montrer que ∃x♦P(x) → ♦∃xP(x) est valide sur tous lesmodeles croissants.Si tout modele base sur un cadre satisfait CB, alors lesdomaines sont monotones.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Application au langage naturel
Quine (1956)(1) Marie sait que quelqu’un est un espion∃x ∧�S(x)�∃xS(x)
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Exercice
Dans la semantique a domaine constant, montrer:|= ∃x�P(x) → �∃xP(x).
Montrer que la reciproque est fausse.
Paul Egre ateliersJSM
IntroductionLogique modale propositionnelle
Logique modale quantifieeConclusion
Conclusion
Dans cette breve introduction nous avons decouvert:
La logique modale propositionnelle: moins expressive quela logique du premier-ordre, mais potentiellement pluseconome (quantification implicite vs explicite)Logique modale quantifiee: avantage relatif a combiner laquantification implicite et la quantification explicite, plutotque d’utiliser une logique du premier-ordre avec plusieurssortes de variables.
Paul Egre ateliersJSM