Completitudinea unor sisteme de logica modala: doua abordari

Alexandru Dragomir

July 18, 2013

Abstract

Aceasta lucrare îsi propune sa prezinte doua tipuri de demonstratii ale teoremei de completitudine pen-tru câteva sisteme de logica modala. O sectiune initiala va introduce cititorul în logica modala: limbajulacesteia, unele sisteme axiomatice (K - S5), semantica folosind cadrele si modelele-Kripke, si notiunile devaliditate relativa la cadre si modele. Apoi, dupa ce vom prezenta clasica metoda de a demonstra completi-tudinea modala folosind modelele canonice de tip Henkin, vom prezenta si o demonstratie a lui L.S. Mossce foloseste un concept diferit de model canonic, al carui domeniu este alcatuit din formule canonice.

1 Introducere

Unii logicieni si istorici ai logicii (vezi, spre exemplu [9], p. 2) afirma ca logica modala a aparut ca studiu al

logicii modalitatilor metafizice1: posibilitatea, contingenta si necesitatea. Ce întelegem prin modalitate? Data

fiind o propozitie φ, adevarul acesteia poate fi, spre exemplu, necesar, posibil sau contingent2, cu alte cuvinte,

φ poate fi adevarata în diferite moduri. Sa nu confundam modalitatile adevarului unei propozitii cu gradul de

adevar pe care i-l putem atribui pentru ca, asa cum vom vedea din constructia modelelor pentru logici modale,

functia de valorizare atribuie oricarui atom propozitional ori adevarul, ori falsitatea. În acest sens, logicile

modale sunt clasice sau bivalente, spre deosebire de logicile cu mai multe valori de adevar, logicile fuzzy sau

logicile paraconsistente3 (toate acestea din urma fiind numite non-clasice).

Dar analiza logica a modalitatilor nu s-a limitat la cele câteva notiuni mentionate mai sus. Adevarul unei

propozitii nu poate fi descris doar ca fiind necesar, posibil sau contingent, iar pentru a fi de acord cu aceasta,

sa observam ca un adevar poate fi cunoscut, demonstrabil, relativ la un moment de timp sau la un interval de

timp etc. Ca urmare, ieri, acum, de acum incolo, pâna în acest moment sunt, de asemenea, modalitati. O lista

de categorii de modalitati este oferita de R. Goldblatt în [9], p. 3, si de Von Wright în [28], p.2 (printre altii):

1Numite si aletice.2Un adevar este contingent daca este un adevar de facto, dar nu este si necesar. Spre exemplu, faptul ca Bucuresti este capitala

României este un adevar de facto (cel putin în momentul în care autorul a scris-o), dar nu unul necesar: s-ar fi putut ca România sa aibao alta capitala.

3Logicile paraconsistente sunt logici în care exista contradictii adevarate. În logicile clasice contradictiile sunt întotdeauna false.

1

• deontice: trebuie, este permis, este interzis etc.

• temporale: pâna în acest moment, din acest moment, în acest moment, mâine etc.

• epistemice: stie ca, este cunoscut comun ca4, este cunoscut distribuit ca5 etc.

• doxastice: crede ca6 etc.

• metalogice: este demonstrabil ca etc.

Lucrarea de fata va prezenta, în a doua sectiune, limbajul (vocabularul si regulile de buna formare a propoz-

itiilor lui) si axiomele celor mai folosite logici modale. Apoi, semantica în termeni de cadre si modele-Kripke,

alaturi de notiunile conexe de validitate, deductibilitate, completitudine tare si slaba, definibilitate a claselor de

cadre în functie de formulele modale validate de acestea. De asemenea, vom arata cum logica modala poate

fi utilizata pentru a studia logica notiunii de cunoastere propozitionala. A treia sectiune prezinta teoremele de

completitudine pentru câteva din sistemele prezentate în a doua sectiune. Vom arata cum aceasta proprietate

poate fi demonstrata folosind doua metode:

(1) metoda lui Henkin, folosind modele canonice alcatuite din multimi maximal-consistente (modele canonice-

Henkin), si

(2) metoda lui Moss, folosind modelele cu domenii alcatuite din formule canonice (modele canonice-

Moss).

2 Sintaxa si semantica logicii modale

Aceasta sectiune este rezervata prezentarii sintaxei si semanticii logicii modale. În particular, vom prezenta:

• Gramatica limbajului logicii modale, deci vocabularul si regulile de construire a formulelor bine formate.

• Axiomele si regulile de deductie ale câtorva sisteme de logica modala.

• Semantica lumilor posibile pentru logica modala, mai exact cadrele si modelele Kripke, notiunile de

validitate: validitatea relativa la cadre si validitatea relativa la modele si definirea claselor de cadre în

functie de validarea de catre acestea a anumitor formule modale.

4Cunoasterea comuna este un tip de cunoastere specifica grupurilor de agenti. Un adevar este cunoscut comun daca si numai dacatoti agentii îl stiu, toti agentii stiu ca toti agentii îl stiu, toti agentii stiu ca toti agentii îl stiu ad infinitum (vezi axiomatizarea si definitiasemantica în [26]).

5Asemeni cunoasterii comune, cunoasterea distribuita este un tip de cunoastere specific grupurilor. Informal, un adevar este cunoscutdistribuit daca poate fi derivat din suma adevarurilor cunoscute de toti agentii. Un fapt interesant este ca un adevar cunoscut distribuitîntr-un grup poate sa nu fie cunoscut de unul sau mai multi membri ai grupului. Spre exemplu, daca A stie ca Spock este sau vulcanian,sau klingonian, iar B stie ca Spock nu e klingonian, grupul alcatuit din A si B cunoaste în mod distribuit ca Spock e vulcanian. Evident,nici unul din membrii grupului nu stie adevarata natura a lui Spock.

6Spre deosebire de cunostinte (care apartin categoriei modalitatilor epistemice), credintele sau opiniile pot fi false. Mai exact, cinevapoate crede ceva ce este fals, dar nu poate sti ceva fals.

2

• O scurta subsectiune va fi dedicata prezentarii istorice a dezvoltarii semanticilor pentru logici modale.

• De asemenea, o subsectiune va fi rezervata prezentarii unei aplicatii a logicii modale: logica epistemica.

Toate acestea sunt introduse cu scopul prezentarii în sectiunea a treia a teoremelor de completitudine.

2.1 Limbajul logicii modale

(Indicatii bibliografice: Patrick Blackburn et al., Modal Logic, pp. 9-12, Brian Chellas, Modal Logic. An

Introduction, G.E. Hughes, M.J. Cresswell, A New Introduction to Modal Logic, Mircea Dumitru, Modalitate

si incompletitudine, p. 21)

Sa denotam prin L limbajul logicii modale. La nivel sintactic, limbajul logicii modale include limbajul

logicii propozitionale, si, pentru orice formula φ din L, contine si formulele modalizate �φ (adica: φ este

un adevar necesar). O definitie alternativa spune ca limbajul L cuprinde formulele ♦φ, pentru orice φ ∈ L.

Definitia este echivalenta întrucât ♦ si � sunt operatori interdefinibili (duali). Vom relua toate acestea, formal,

în cele ce urmeaza.

2.1.1 Vocabularul limbajului logicii modale

Vocabularul lui L cuprinde urmatoarele:

1. Variabilele propozitionale (sau atomii propozitionali):

a,b,c, p, p0, p1, p2...,q,r, ...

2. Conectorii propozitionali binari:7 ∧ (conjunctia), ∨ (disjunctia),→ (implicatia),↔ (echivalenta) si, în

fine, conectorul unar ¬ (negatia)8.

3. Constantele propozitionale ⊥ (falsitatea sau absurditatea) si > (adevarul). Acestea doua sunt inter-

definibile: ⊥ := ¬>, > := ¬⊥,

Ca observatie colaterala9, întrucât formulele de tipul φ→ ψ si φ∧ψ sunt echivalente semantic cu formule

ce contin doar conectorii ¬ si ∨ (φ→ψ este echivalenta semantic cu ¬φ∨ψ, iar φ∧ψ este echivalenta semantic

cu ¬(¬φ∨¬ψ)), lista conectorilor poate fi redusa la ¬ si ∨. De altfel, liste alternative ar putea fi ¬ si ∧, sau

¬ si→, de asemenea în virtutea echivalentelor semantice între formulele ce se pot obtine folosind oricare din

aceste cupluri de conective si formulele ce contin restul conectorilor.

4. Semnele de punctuatie: ( si ) (parantezele).

7Sau conectivele propozitionale.8Asa cum vom vedea, spre deosebire de logica propozitionala, logica modala contine doi operatori unari: ¬ si � (sau ♦).9Si poate prematura, deoarece nu am introdus înca semantica conectorilor si o vom utiliza în explicatia ce urmeaza.

3

5. Operatorii modali � si ♦. Deoarece operatorii sunt interdefinibili, vocabularul ar putea include doar

unul din acestia, celalalt putând fi dedus.

2.1.2 Formulele bine formate ale limbajului logicii modale

Vom nota multimea tuturor atomilor propozitionali ai lui L prin Atomi(L). De asemenea, multimea tuturor

propozitiilor sau formulelor bine formate ale lui L va fi notata prin Prop(L) si este construita inductiv dupa

urmatoarele reguli:

1. ∀p∈Atomi(L) =⇒ p∈Prop(L). Toate variabilele propozitionale (si constantele propozitionala⊥ si>)

ale limbajului L sunt formule sau propozitii în L. Vom nota elementele multimii Prop(L) prin litere grecesti.

2. Daca φ,ψ ∈ Prop(L) atunci:

• ¬φ ∈ Prop(L),

• φ∨ψ ∈ Prop(L),

• φ∧ψ ∈ Prop(L),

• φ→ ψ ∈ Prop(L),

• φ↔ ψ ∈ Prop(L),

• �φ ∈ Prop(L),

• ♦φ ∈ Prop(L).

2.2 Axiomatica logicii modale

(Indicatii bibliografice: Patrick Blackburn et al., Modal Logic, p. 33-39, Brian Chellas, Modal Logic. An

Introduction, G.E. Hughes, M.J. Cresswell, A New Introduction to Modal Logic, J. van Benthem, Modal Logic

for Open Minds, notele de curs ale lui Eric Pacuit [22])

Definitia 2.1. O logica modala Λ este o multime alcatuita din toate tautologiile logicii propozitionale10, este

închisa la modus ponens (daca φ ∈ Λ si φ→ ψ ∈ Λ, atunci ψ ∈ Λ) si substitutia uniforma.

Definitia 2.2. O logica modala Λ se numeste normala (sau sistem modal normal), daca:

10O tautologie este definita ca fiind o propozitie adevarata în toate interpretarile posibile. Tinând cont ca o interpretare pentruo formula a logicii propozitionale este o asignare de valori de adevar catre toti atomii propozitionali din care este compusa, definitiatautologiei se reduce la a spune ca aceasta este o fomula adevarata indiferent de asignarea valorilor de adevar catre atomii propozitionaliai acesteia.

4

1. Contine urmatoarele formule:

(K) �(φ→ ψ)→ (�φ→�ψ) (1)

(Dualitatea operatorilor � si ♦) �φ↔¬♦¬φ (2)

2. Este închisa la regula de necesitare (sau generalizare):

(Nec) Daca φ ∈ Λ, atunci �φ ∈ Λ (3)

Definitia 2.3 (Teorema într-un sistem modal). Daca φ ∈ Λ, atunci se spune ca φ este o teorema în sistemul

modal Λ (teorema a logicii modale Λ) si se scrie: `Λ φ; altfel, 0Λ φ.

Definitia 2.4 (Multime Λ-consistenta). O multime de propozitii Γ este Λ-consistenta daca Γ 0Λ ⊥. Altfel, daca

Γ `Λ ⊥, se spune ca Γ este Λ-inconsistenta.

Cu alte cuvinte, o multime de propozitii Γ este Λ-consistenta daca aceasta nu contine o contradictie. Atomul

⊥ are rolul de a simboliza orice contradictie. Acest lucru este evident din semantica acestuia: lui nu îi este

asignata valoarea de adevar adevarat de catre nici o interpretare, în nici o lume posibila.

Definitia 2.5. Fie Γ = {ψ1, ..., ψn, φ} o multime de formule modale. φ este deductibila din multimea Γ = {ψ1,

... , ψn} de asumptii daca (∧

i≤n ψi)→ φ este o tautologie.

Acum, sa vedem cum pot fi definite deductiile într-un sistem modal:

Definitia 2.6 (Deductie într-un sistem modal Λ). O deductie modala în sistemul Λ este o secventa finita

〈α1, ...,αn〉 care, pentru orice i≤ n, respecta urmatoarea regula: orice αi este ori o tautologie, ori o instanta a

unei axiome (rezultatul aplicarii regulii de substituire) din Λ, ori rezultatul aplicarii regulii de necesitare (deci

αi are forma �α j, pentru j < i), ori rezultatul aplicarii regulii modus ponens (exista j,k < i asa încât αk are

forma α j→ αi).

Daca un αi de forma φ se afla într-o deductie modala 〈α1, ...,αn〉 într-un sistem Λ, vom nota aceasta prin:

`Λ φ. Cu alte cuvinte, orice element al unei demonstratii modale 〈α1, ...,αn〉 este teorema, în sensul expus mai

sus in Definitia 2.3.

Definitia 2.7. [Deductie din asumptii într-un sistem modal]

Fie Γ o multime de formule modale (asumptii). O deductie modala a lui φ din Γ, într-un sistem Λ este o

secventa finita 〈α1, ...,αn〉 care respecta urmatoarea regula, pentru orice i ≤ n: ori αi este o tautologie, ori

αi ∈ Γ, ori αi este o instanta a unei axiome din Λ, ori αi este rezultatul aplicarii regulii modus ponens, ori αi

este de forma �α j, pentru j < i si `Λ α j (este rezultatul aplicarii regulii necesitarii).

Urmatoarele doua leme stabilesc reguli de deductie conservative pentru logicile modale normale. Conser-

vativitatea lor consta în faptul ca rezultatul aplicarii acestora este reductibil la aplicarea regulilor de deductie

ale unui sistem modal normal si nu necesita introducerea niciunei reguli externe acestuia.

5

Lema 2.1. În orice logica modala normala Λ, daca `Λ φ↔ ψ, atunci `Λ ♦φ↔ ♦ψ.

Demonstratie.

(=⇒) Sa presupunem ca: `Λ φ→ ψ. Atunci, folosind regulile de deductie ale logicii propozitionale, avem:

(1) `Λ ¬ψ→ ¬φ (contrapozitia). Utilizând regula necesitarii, obtinem: `Λ �(¬ψ→ ¬φ). Substituind în

Axioma K, avem ca: (2) `Λ �(¬ψ→ ¬φ)→ (�¬ψ→ �¬φ). Aplicând regula modus ponens la (1) si (2),

obtinem: `Λ �¬ψ→�¬φ. Atunci avem, echivalent, folosind regulile logicii propozitionale, ca: `Λ ¬�¬φ→¬�¬ψ (contrapozitia). Prin dualitate, obtinem: `Λ ♦φ→ ♦ψ, ceea ce aveam de demonstrat.

(⇐=) Presupunem ca `Λ ψ→ φ si, urmând un rationament analog celui de mai sus, obtinem ca `Λ ♦ψ→♦φ, ceea ce aveam de demonstrat.�

Lema 2.2. În orice logica modala normala Λ, daca `Λ φ→ ψ, atunci `Λ �φ→�ψ.

Demonstratie.

(1) φ→ ψ (din ipoteza)

(2) �(φ→ ψ) (aplicând regula necesitarii la rândul (1))

(3) �(φ→ ψ)→ (�φ→�ψ) (o instanta a axiomei K)

(4) �φ→�ψ (modus ponens la rândurile (2) si (3)) �

2.2.1 Alte sisteme de logica modala

Noi sisteme de logica modala pot fi obtinute adaugând axiome la sistemul minimal ce contine doar K (si

bineînteles, toate tautologiile propozitionale). Între cele mai cunoscute si utilizate axiome sunt urmatoarele:

• (4) ♦♦p→ ♦p sau �p→��p

• (5) ♦p→�♦p sau ¬�p→�¬�p

• (T) p→ ♦p sau �p→ p

• (B) p→�♦p

• (D) �p→ ♦p

• (L) �(�p→ p)→�p

• (E) ♦p→�♦p

6

Adaugând axiomele de mai sus axiomei K obtinem diferite sisteme de logica modala. Printre cele mai

cunoscute si folosite sunt:

• K = {K}

• KT = K+T

• S4 = K+T+4

• S5 = K+T+4+B= K+T+5

K

T

S4 S5

(T )

(4) (5)

(B)

2.3 Cadre si modele-Kripke

(Indicatii bibliografice: capitolele referitoare la cadre si modele-Kripke din Patrick Blackburn et al., Modal

Logic, Brian Chellas, Modal Logic. An Introduction, G.E. Hughes, M.J. Cresswell, A New Introduction to

Modal Logic)

Definitia 2.8 (Cadru Kripke). Un cadru-Kripke este o multime ordonata (pereche): F= (W,R), unde W este o

multime oarecare de lumi posibile11 iar R este o relatie binara între elemente ale lui W: R⊆W ×W.

Evaluarea folosind lumi posibile este de inspiratie filosofica leibniziana: în conceptia lui Leibniz, un adevar

necesar este un adevar în toate lumile posibile. Asa cum vom vedea mai jos, intuitia aceasta este conservata în

definitia semantica a operatorului necesitatii, �. Elementele care alcatuiesc domeniul unui cadru sunt numite

si stari epistemice, puncte, noduri. Le vom folosi intersanjabil, întrucât lucrarea are un scop matematic si nu

unul metafizic: nu are nici o importanta ce întelegem prin lume posibila. Trebuie mentionat, totusi, ca în cazul

logicilor modale cuantificate, consideratiile metafizicienilor asupra identitatii trans-mundane (putem considera

doi indivizi a doua lumi posibile diferite drept identici?) au dus la semantici diferite de cea clasica oferita de

Kripke: spre exemplu, semantica folosind contraparti12 (counterpart semantics) a lui David Lewis [20]. În linii

11Numite si noduri, puncte sau stari, în functie de logica caror notiuni este în discutie.12Sau "omologi", conform traducerii lui Mircea Dumitru a textului lui Kripke ([19]), Naming and Necessity.

7

mari, spre deosebire de semantica lui Kripke, în care indivizii asignati lumii actuale sunt asignati si altor lumi

posibile, semantica lui David Lewis foloseste indivizi distincti în fiecare lume posibila (o implicatie imediata

este ca nu exista identitate între doi indivizi trans-mundani, ci doar similaritate). Sa ne întoarcem la prezentarea

semanticii pentru logica modala propozitionala.

Asa cum poate fi observat din definitie, un cadru-Kripke este un graf. Utilitatea acestora va fi relevata de

constructiile si teoremele prezentate în capitolele urmatoare.

Definitia 2.9 (Model Kripke). Un model-Kripke este o multime ordonata M = (F,V ) = (W,R,V ). Asa cum

este definit, consta dintr-un cadru-Kripke (sau graf) si o functie de evaluare13 ce asigneaza fiecarui atom

propozitional o multime de lumi din W 14: V : Atomi(L)−→ 2W

Definitia 2.10. Având în vedere constructia prezentata mai sus, acum poate fi definita relatia de satisfacere

|=: |=⊆ (M,w)×Prop(L) drept cea mai mica relatie care respecta conditiile (bineînteles, dat fiind un model

M= (W,R,V )):

R0. M,w 6|=⊥ si M,w |=>, pentru orice w ∈ dom(M)

R1. M,w |= p ddaca15 w ∈V (p), oricare ar fi w ∈W si oricare p ∈ Atomi(L)

R2. M,w |= ¬φ ddaca M,w 6|= φ, pentru oricare φ ∈ Prop(L)

R3. M,w |= φ∧ψ ddaca M,w |= φ si M,w |= ψ, pentru oricare φ,ψ ∈ Prop(L)

R4. M,w |= φ∨ψ ddaca M,w |= φ sau M,w |= ψ, ∀φ,ψ ∈ Prop(L)

R5. M,w |= φ→ ψ ddaca M,w 6|= φ sau M,w |= ψ, ∀φ,ψ ∈ Prop(L)

R6. M,w |= ♦φ ddaca ∃u : Rwu si M,u |= φ,∀φ ∈ Prop(L)

R7. M,w |=�φ ddaca ∀u : Rwu =⇒M,u |= φ,∀φ ∈ Prop(L)

Nu vom discuta regulile R0 - R5, întrucât sunt identice cu cele folosite pentru a interpreta formulele logicii

propozitionale clasice. Sa luam un exemplu. Ceea ce spune regula R3 este ca o conjunctie între φ si ψ este

adevarata în lumea w ddaca atât φ cât si ψ (amândoua conjunctele) sunt adevarate în lumea w. Însa, R6 si R7sunt specifice doar logicii modale. Intuitia din spatele acestora urmeaza îndeaproape definitiile leibniziene ale

necesitatii si posibilitatii: o propozitie este necesar adevarata daca este adevarata în toate lumile posibile si este

posibil adevarata daca este adevarata în cel putin o lume posibila. Introducerea relatiei de accesibilitate a facut

realizabila iterarea multipla a operatorilor modali. Pentru claritate, sa vedem cum se citesc regulile R6 si R7:

• R6 se citeste: în modelul M, relativ la lumea w, este posibil adevarat ca φ ddaca este satisfacuta propozitia

φ în cel putin o lume u accesibila lumii w.13Numita si functie de asignare sau valuatie (din engleza: valuation function. Le vom folosi intersanjabil.14În cele ce urmeaza vom nota multimea-putere a unei multimi (multimea tuturor submultimilor unei multimi) prin 2W .15Ddaca înseamna daca si numai daca. Alternativ, vom folosi si simbolul⇐⇒.

8

• R7 se citeste: în modelul M, relativ la lumea w, este necesar adevarat ca φ ddaca φ este adevarata în orice

lume accesibila lumii w.

Metaforic, atunci când o lume u este accesibila unei lumi w, se mai spune ca lumea w vede lumea u.

Având în vedere constructia prezentata mai sus, avem mai multe notiuni de validitate posibile, fiecare din

ele relativa la structura aleasa: modelele sau cadrele-Kripke:

Definitia 2.11 (Validitate într-un model). Fie M = (F,V ) = (W,R,V ) un model Kripke. Atunci, spunem ca

formula φ este valida în modelul M ddaca pentru orice w ∈ dom(M) =W are loc: M,w |= φ.

Acum, o definitie a validitatii într-un cadru poate fi data în functie de validitatea în modelele care pot fi

construite peste un cadru ales:

Definitia 2.12 (Validitate într-un cadru). Fie F= (W,R) un cadru-Kripke. Atunci, spunem ca o formula φ este

valida în cadrul F ddaca pentru orice model M al cadrului F formula φ este valida în modelul M (vezi mai sus

definitia validitatii într-un model).

Urmatoarele notatii vor fi ajutatoare în expunerea teoremei de completitudine tare:

Definitia 2.13. Γ |=M φ ddaca: daca M,w |= Γ, atunci M,w |= φ, pentru orice w din domeniu. Adica: pentru

orice w ∈ dom(M) =W, daca pentru orice ψ din Γ tine M,w |= ψ, atunci M,w |= φ

Definitia 2.14. Γ |=F φ ddaca pentru orice model M construit peste F avem: Γ |=M φ.

Definitia 2.15. Vom spune ca un cadru are proprietatea P (sau, prin abuz de limbaj ca este P) ddaca relatia

acestuia de accesibilitate are proprietatea P

Spre exemplu, pentru un cadru F= (W,R):

• F este reflexiv ddaca R este reflexiva, adica ∀w ∈W : (w,w) ∈ R.

• F este simetric ddaca R este simetrica, adica ∀w,u : Rwu⇒ Ruw.

• F este tranzitiv ddaca R este tranzitiva, adica ∀w,u,v : (Rwu∧Ruv)⇒ Rwv.

• F este reflexiv si tranzitiv ddaca F este reflexiv si F este tranzitiv.

Definitia 2.16 (Clase de cadre definite de o proprietate). O formula a limbajului logicii modale φ defineste o

clasa de cadre C cu proprietatea P ddaca ∀F ∈ C : F |= φ ddaca F are proprietatea P.

Ca observatie de fond, sa ne amintim ca un cadru valideaza o formula φ ddaca orice model construit pe baza

acestuia valideaza formula φ, iar un model valideaza o formula ddaca relativ la orice lume posibila a domeniului

sau este adevarata formula φ.

Exemple:

9

Propozitia 2.1. Clasa cadrelor reflexive este definita de formula �φ→ φ.

Demonstratie.

(=⇒) Daca un cadru este reflexiv, atunci valideaza formula �φ→ φ.

Sa presupunem ca avem un cadru F reflexiv. Trebuie sa aratam ca M,w |= �φ→ φ, pentru orice w ∈W .

Sa alegem o w din W si sa presupunem ca M,w |= �φ. Acum, trebuie sa aratam ca M,w |= φ. Din definitia

semantica a operatorului necesitatii, avem ca ∀u : Rwu⇒M,u |= φ. Pentru ca F este reflexiv, avem ca ∀w : Rww,

deci M,w |= φ, ceea ce ne trebuia.

(⇐=) Daca un cadru valideaza �φ→ φ, atunci este reflexiv.

Sa demonstram contrapozitiva, adica: daca un cadru nu este reflexiv, adica exista w asa încât e fals ca Rww,

atunci nu valideaza �φ→ φ: F 6|= �φ→ φ, ceea ce se întâmpla daca exista un model astfel încât M,w |=�φ∧¬φ. Sa luam modelul M a carui functie de evaluare atribuie atomul p fiecarei lumi posibile care nu este

w. Atunci, indiferent ce lumi posibile vede w, va fi adevarat ca p, deci M,w |=�p. Însa, pentru ca relativ la w

este fals ca p, avem M,w |=¬p, deci, punând în conjunctie cele doua mici rezultate, avem ca M,w |=�p∧¬p,

deci M,w |= ¬(�p→ p), deci M,w 6|=�p→ p.

Propozitia 2.2. Clasa cadrelor tranzitive este definita de formula �φ→��φ.

Demonstratie.

(=⇒) Daca un cadru este tranzitiv, atunci valideaza formula �φ→��φ.

Sa presupunem ca avem F tranzitiv, deci ca pentru orice w,u,v, avem ca daca Rwu si Ruv, atunci Rwv. Sa

aratam ca pentru orice w ∈W , daca M,w |=�φ, atunci M,w |=��φ. Sa presupunem ca M,w |=�φ. Atunci,

în toate lumile u legate prin relatia R de w este adevarat ca φ. Daca relativ la toate aceste u ar fi adevarat ca

�φ, atunci la w ar fi adevarat ca ��φ. Sa zicem ca u vede o lume v: Ruv. Atunci, pentru ca R e tranzitiva, si

w vede pe v: Rwv. Dar am asumat ca toate lumile pe care le vede w satisfac φ, deci si v satisface φ. Atunci,

pentru ca v ales la întâmplare satisface φ, avem ca u satisface �φ si, pentru ca w vede u, w satisface ��φ. Deci

M,w |=��φ, ceea ce ne trebuia.

(⇐=) Daca un cadru valideaza formula �φ→��φ, atunci acel cadru este tranzitiv.

Sa presupunem ca F |= �φ→ ��φ. Sa presupunem ca, pentru orice w,u,v, avem ca Rwu si Ruv. Sa

aratam ca Rwv. Sa alegem un model M asa încât functia de evaluare sa atribuie atomul p tuturor si doar lumilor

accesibile din w. Atunci, pentru ca M,w |=��p, înseamna ca relativ la toate u este adevarat ca �p, deci toate

lumile pe care le vede u satisfac p. Pentru ca functia de evaluare V a atribuit p tuturor si doar lumilor pe care le

vede w, înseamna ca w vede toate lumile v pe care le vede u: Rwv, ceea ce ne trebuia.

Propozitia 2.3. Clasa cadrelor simetrice este definita de formula φ→�♦φ.

Demonstratie.

10

(=⇒) Daca un cadru este simetric, atunci valideaza φ→�♦φ.

Sa presupunem ca F este simetric. Atunci, sa alegem unul din modelele care se bazeaza pe acesta. Relativ

la orice lume a acestui model: M,w |= φ si sa aratam ca M,w |= �♦φ. Sa presupunem ca Rwu. Din conditia

simetriei avem ca u vede w, deci u |= ♦φ. Pentru ca situatia e valabila pentru orice u accesibil lui w (orice u

accesibil lui w satisface ♦φ), avem ca M,w |=�♦φ.

(⇐=) Daca un cadru valideaza φ→�♦φ, atunci este simetric.

Sa demonstram contrapozitiva: daca un cadru nu este simetric, adica exista doua lumi w si u asa încât w

vede u dar u nu vede w, atunci nu valideaza φ→ �♦φ. Sa construim un model definit asa încât sa-i atribuie

doar lumii w atomul p: M,w |= p. Atunci, orice lume u valideaza ¬♦p pentru ca u nu vede singura lume în

care e adevarat ca p, chiar w. Atunci, pentru ca w vede u |= ¬♦p, avem ca w |= ♦¬♦p care este echivalenta cu

M,w |= ¬�♦p, ceea ce ne trebuia.

2.4 Observatii de natura istorica

Am remarcat, mai sus, faptul ca definitia semantica a operatorului necesitatii respecta intuitia lui Leibniz cu

privire la ce anume înseamna adevar necesar, si anume adevar în toate lumile posibile. Atunci, în mod natural,

definitia operatorului ar fi trebuit sa fie astfel:

M,w |=�φ⇐⇒∀u : M,u |= φ (4)

În fapt, aceasta a fost definitia oferita de R. Carnap [3] (cf. lucrarii lui Zalta, [29] p. 7). Defectul acesteia,

însa, este ca nu poate da seama de întelesul iterarilor multiple de operatori. În sens tehnic, are loc urmatoarea:

Propozitia 2.4. Daca operatorul necesitatii este definit în stilul lui Carnap [3], atunci:

MCarnap,w |=Carnap ��φ⇐⇒MCarnap,w |=Carnap �φ (5)

Demonstratie.

Prima directie: MCarnap,w |=Carnap ��φ =⇒MCarnap,w |=Carnap �φ.

Sa presupunem ca MCarnap,w |=Carnap ��φ. Atunci, în toate lumile domeniului modelului M este adevarat

ca �φ. Dar, conform definitiei semantice a operatorului �, aceasta înseamna ca în toate lumile domeniului este

adevarat ca φ. Pentru ca în toate lumile modelului M este adevarat ca φ, atunci în orice lume, deci si în w, este

adevarat ca �φ.

A doua directie: MCarnap,w |=Carnap �φ =⇒MCarnap,w |=Carnap ��φ.

Sa presupunem ca MCarnap,w |=Carnap �φ. Atunci, în orice lume este adevarat ca φ. Pentru ca în orice

lume este adevarat ca φ, atunci în orice lume este adevarat ca �φ. Din aceasta obtinem ca în orice lume este

adevarat ca ��φ.

11

Daca în semantica operatorului � ar fi fost utilizate relatii de accesibilitate, atunci am fi putut construi un

contraexemplu în care într-o anumita lume sa fie adevarat ca �φ si sa fie fals ca ��φ. Sa construim acest

model-contraexemplu. Fie M al carui domeniu este alcatuit din w, u si v. Lumea w vede lumea u si lumea

u vede lumea v. Functia de asignare atribuie atomul p lumii u, dar nu si lumii v. Atunci, pentru ca w vede o

singura lume, u, iar la u este adevarat ca p, la w este adevarat ca �p. Dar pentru ca lumea u vede o lume în care

este fals ca p, avem ca relativ la lumea u nu este necesar ca φ: ¬�p. Pentru ca lumea w vede lumea u relativ la

care e adevarat ca ¬�p, la w e adevarat ca ♦¬�p. Dualitatea operatorilor ♦ si � (adica legea: ♦¬p↔¬�p)

ne asigura ca ♦¬�p este echivalenta cu ¬��p.

Primul logician care a folosit relatii de accesibilitate între lumi posibile pentru a oferi definitii semantice

pentru operatorii modali a fost A.N. Prior [24] (conform [5], p.108, în lucrarea Three-valued logic and future

contingents, Philos. Quart. 3, 317–26, 1953). Introducerea relatiilor binare între lumi posibile l-a dus la

concluzia ca un sistem de tipul S4 necesita proprietatea tranzitivitatii pentru cadrul care-l caracterizeaza. De

asemenea, Hintikka [10] a introdus, independent, relatii binare între lumi posibile pentru a oferi o semantica

operatorului permisibilitatii din logica deontica. B. Jack Copeland [5], p. 124, mentioneaza faptul ca Hintikka

a propus demonstratii de completitudine pentru S5 si sisteme mai slabe în cadrul unor seminarii de logica ce

s-au desfasurat în perioada 1958-1959 la Harvard.

Numele lui Kripke a fost legat de aceste modele pentru ca a fost primul care a demonstrat completitudinea

pentru sistemul S5 cu operatori pentru identitate si cuantificare (conform [5], p. 129), în lucrarea sa din 195916,

A Completeness Theorem in Modal Logic [16]. În demonstratia sa, Kripke [19], a folosit si adaptat la logica

modala metoda tablourilor semantice (sau a arborilor de adevar) a lui E.W. Beth [1] (cf. [5], p. 129). Câtiva ani

mai târziu, într-o lucrare publicata în 1963 dar finalizata în 1962, Kripke [18] introduce relatii de accesibilitate

între lumi posibile si demonstreaza completitudinea sistemelor de logica modala propozitionala B, M, S4,

S5. Completitudinea logicilor modale cuantificate (extinderi ale logicilor B, M, S4, S5 cu operatori pentru

cuantificare) o stabileste într-un alt articol publicat în 1963: Semantical considerations on modal logic [17].

Totusi, asemenea rezultate fusesera deja anticipate de Hintikka17, Montague18 si altii.

Poate mult mai interesant, Tarski si Jonsson [12], [13], [14] au publicat în perioada 1948 - 1952 (conform

[5], p. 105) o serie de articole dedicate algebrelor booleene cu operatori în care au demonstrat teoreme de

reprezentare pentru acestea. Completitudinea logicilor modale K-S5 decurge din acestea, însa relevanta pentru

logica modala a rezultatelor obtinute (conectarea sintaxei si semanticii) le-a scapat.

16B. Jack Copeland [5], p. 129, aduce în vedere faptul ca textul publicat în 1959 fusese scris în 1958, deci se poate spune ca SaulKripke a fost printre primii care au furnizat rezultate de completitudine. Mai sus, am notat faptul ca Hintikka prezentase în 1958propriile demonstratii de completitudine.

17B. Jack Copeland [5], p. 124, mentioneaza faptul ca Hintikka a propus demonstratii de completitudine pentru S5 si sisteme maislabe în cadrul unor seminarii de logica ce s-au desfasurat în perioada 1958-1959 la Harvard.

18Vezi [5], pp. 111-112 pentru o analiza a contributiilor lui Montague.

12

2.5 Logica epistemica

(Indicatii bibliografice: H.P. van Ditmarsch, W. van der Hoek, B. Kooi, Dynamic Epistemic Logic, R. Fagin,

J.Y. Halpern, Y. Moses, M. Vardi, Reasoning about Knowledge)

Acum, sa aratam în ce fel logica modala este utila în studiul logicii modalitatilor epistemice. Pentru început,

sa notam ca logica epistemica este, în fapt, o logica modala ai carei operatori pentru necesitate sunt cititi

"agentul a stie ca"19. Acum, limbajul formal al logicii modale este util în descrierea unor contexte sau situatii

epistemice. O afirmatie de tipul Ion stie ca Andrei nu stie ca Radu stie ca φ este usor si intuitiv reprezentabila

sintactic astfel: KIon¬KAndreiKRaduφ. Odata formalizate propozitii ale limbajului natural ce surprind astfel de

situatii epistemice, aparatul axiomatic-deductiv ne poate spune ce anume putem deduce din acestea. Deductiile

se pot face instantiind schemele de axiome ale sistemului ales si aplicând doua reguli de deductie (modus

ponens si o regula care permite prefixarea cu un operator epistemic a oricarei formule deja deduse (regula

necesitarii). Spre exemplu, axiomele celui mai folosit sistem de logica epistemica, S5, suprind formal câteva

intuitii filosofice asupra proprietatilor cunoasterii propozitionale, si anume: nu poti cunoaste ceva ce este fals,

daca stii ca φ atunci stii ca stii ca φ, si daca nu stii ca φ, atunci stii ca nu stii ca φ20:

• Axioma K: Ka(φ→ ψ)→ (Kaφ→ Kaψ): daca agentul a stie ca φ implica ψ, atunci, daca agentul a stie

ca φ, atunci agentul a stie ca ψ.

• Axioma facticitatii cunoasterii: Kaφ→ φ: daca agentul a stie ca φ, atunci φ este un adevar. Cu alte cuvinte,

este imposibil ca agentul a sa stie ca φ si φ sa fie ceva fals. În fapt, aceasta axioma face deosebirea între

a cunoaste si a avea o opinie. De ce? Continutul unei opinii, φ, poate fi fals. Urmând aceasta linie de

argumentare, în logica doxastica este respinsa aceasta axioma.

• Axioma introspectiei pozitive: Kaφ→ KaKaφ: daca agentul a stie ca φ, atunci el stie ca stie ca φ.

• Axioma introspectiei negative: ¬Kaφ→ Ka¬Kaφ: daca agentul a nu stie ca φ, atunci el stie ca nu stie ca

φ.

De asemenea, dar la nivel semantic, reprezentarea contextelor epistemice se poate face si în termenii unui

model-Kripke. Odata fixat modelul care reprezinta cunostintele agentilor, putem afla, folosind metode seman-

tice, ce afirmatii sunt adevarate despre situatia descrisa. Sa exemplificam. Sa presupunem ca agentul a se afla în

Cluj si nu stie daca în Bucuresti ploua sau nu. Aceasta situatie poate fi modelata astfel: lumea posibila w descrie

situatia în care ploua în Bucuresti si lumea u descrie lumea în care nu ploua în Bucuresti. Sa presupunem ca, de

facto, ploua în Bucuresti, deci w este reprezentarea corecta a lumii actuale. Sa folosim urmatoarea conventie:

φ va denota propozitia ploua în Bucuresti, deci ¬φ va însemna nu ploua în Bucuresti. Atunci, w ∈ V (φ) si

u 6∈ v(φ), deci M,w |= φ si M,u |= ¬φ⇐⇒M,u 6|= φ. În logica epistemica, relatia de accesibilitate Ra leaga

19Pentru introduceri cuprinzatoare în logica epistemica pot fi consultate [27] si [26].20Hintikka, [11], argumenteaza pentru folosirea sistemului modal S4 si împotriva folosirii axiomei introspectiei negative, specifice

sistemului S5.

13

doua lumi pe care agentul a le considera a fi candidati la fel de plauzibili, având în vedere informatia pe care o

detine a, la a descrie starea actuala de lucruri. Faptul ca a nu stie daca ploua sau nu în Bucuresti este reprezentat

facând accesibila lui a lumea u, din w: wRau. Cu alte cuvinte, a nu poate decide care din lumile posibile w si u

este sau descrie corect lumea actuala. Pentru ca din w agentul a vede o lume u relativ la care e fals ca φ, relativ

la w este fals ca agentul a stie ca φ : M,w |= ¬Kaφ pentru ca e fals ca ∀u : wRau =⇒M,u |= φ. Asa cum se

vede, semantica operatorului Ka este identica cu cea a operatorului �. Sa ne amintim ca axiomele celei mai

folosite logici epistemice sunt axiomele sistemului modal S5. Sistemul S5 este consistent si complet cu privire

la clasa cadrelor reflexive, simetrice si tranzitive, deci, în modelul M ce descrie contextul epistemic de mai sus,

relatia Ra trebuie sa aiba proprietatile reflexivitatii, simetriei si tranzitivitatii. Figura urmatoare reprezinta grafic

modelul Kripke M= (W = {w,u},{(w,w),(w,u),(u,w),(u,u)} ∈ Ra,w ∈V (φ)):

w

|= φ

|= ¬Kaφ

u

|= ¬φ

|= ¬Kaφ

aa a

Sa observam ca în amândoua lumile tine urmatoarea: ¬Kaφ. Atunci, relativ la w, dar si la u, vom avea

Ka¬Kaφ. Deductiv, puteam obtine aceasta substituind în Axioma introspectiei negative: ¬Kaφ→ Ka¬Kaφ.

Pentru ca în amândoua lumile tine Ka¬Kaφ, obtinem ca la w si u este adevarat ca KaKa¬Kaφ. Deductiv, puteam

obtine acest rezultat substituind în Axioma introspectiei pozitive: Kaφ→ KaKaφ.

Teoremele de completitudine si consistenta pentru, sa zicem, sistemul S5 conecteaza dimensiunea sintactica

(axiomatica) de cea semantica, asigurându-ne ca orice am deduce din axiome despre ce cunosc agentii este un

adevar si ca orice adevar despre ceea ce cunosc agentii poate fi demonstrat pornind de la axiome si aplicând

regulile de deductie.

3 Completitudinea unor sisteme de logica modala

(Indicatii bibliografice: Patrick Blackburn et al., Modal Logic, pp. 190-198, Brian Chellas, Modal Logic: An

Introduction, pp. 53 - 61, Mircea Dumitru, Modalitate si Incompletitudine, pp. 29 - 48)

Informal, completitudinea unui sistem logic este proprietatea acelui sistem de a putea demonstra orice for-

mula adevarata. Usor de înteles din aceasta definitie informala este ca proprietatea completitudinii conecteaza

latura semantica a unei logici de cea sintactica (axiomatica): daca o formula φ este adevarata, atunci acea

formula poate fi derivata într-un numar finit de pasi din axiome si aplicând regulilele de deductie. Am obser-

vat, însa, ca exista mai multe notiuni de adevar pentru o formula a logicii modale: (1) validitatea relativa la

14

un model-Kripke (vezi Definitia 2.11), si (2) validitatea relativa la un cadru-Kripke (vezi 2.12). Dar care din

cele doua tipuri de validitate suprinde ideea de adevar care intereseaza o teorema de completitudine? Mircea

Dumitru, în [7] pp. 24-26, argumenteaza ca notiunea de validitate relativa la cadre-Kripke este cea potrivita,

deoarece validitatea într-un model nu este conservata de regula substitutiei uniforme (una din regulile de de-

ductie ale unui sistem modal). Fie modelul M= (W = {w,u},(w,u) ∈ R,{w,u} ∈V (p),{u} ∈V (q)). Atunci,

avem ca M,w |= �p→ p, deoarece M,w |= p si M,w |= �p, pentru ca în singura lume pe care o vede w,

si anume u, este adevarat ca p. Pe de alta parte, M,w 6|= �q→ q, pentru ca M,w |= �q si M,w 6|= q. Sa

presupunem ca sistemul logic modelat de M contine axioma ` �p→ p (axioma T). Atunci, folosind regula

substitutiei uniforme, obtinem ca ` �q→ q. Urmând [7], vom numi aceasta formula o instanta-substitutie

a axiomei T. Sa observam ca �q→ q nu este o formula valida în sensul Definitiei 2.11, adica în sensul de

a fi satisfacuta în fiecare lume posibila a domeniului modelului M, pentru ca exista o lume în care �q→ q

este falsa. Deci M 6|= �q→ q, în ciuda faptului ca ` �q→ q. Dar, daca urmam Definitia 2.12 si consideram

adevarul unei formule ca fiind validitatea ei relativ la un cadru sau o clasa de cadre, orice instanta-substitutie a

axiomei �p→ p este valida în clasa cadrelor reflexive (cadrele a caror relatie de accesibilitate este reflexiva)

asa cum se poate vedea din demonstratia Propozitiei 2.1.

O strategie de a stabili completitudinea unui sistem de logica modala este adaptarea strategiei folosite de

L. Henkin în cazul logicilor propozitionale si cu predicate de ordinul întâi. Intuitia din spatele demonstratiei de

tip Henkin este construirea unui model "surogat" (numit model canonic) pentru sistemul logic a carui completi-

tudine vrem sa o demonstram, model care sa satisfaca toate si doar formulele derivabile. În cazul unei logici

modale Λ, modelul canonic pentru sistemul Λ realizeaza scopul de a valida toate si doar formulele demonstra-

bile în Λ. De aici, completitudinea relativa la o clasa de cadre reiese imediat: sistemul este complet relativ la

cadrul sau, mai general, la clasa de cadre peste care se poate construi modelul sau canonic. Spre exemplu, în

cazul sistemului KT, modelul sau canonic, sa-i zicem MCan = (WCan,RCan,VCan) este construit peste cadrul

FCan = (WCan,RCan). Atunci, sistemul KT este complet relativ la clasa cadrelor tranzitive daca FCan apartine

clasei cadrelor tranzitive. În cele ce urmeaza vom detalia formal toate definitiile si argumentele prezentate mai

sus.

Pentru început, sa vedem ce înseamna completitudinea unui sistem de logica modala. Un sistem modal

normal Λ este caracterizat de o clasa de cadre C ddaca: orice teorema formala demonstrabila în Λ este F-valida

(valida în toate cadrele F ale clasei de cadre C) si orice secventa C-valida (valida în toate cadrele F ale clasei de

cadre C) este Λ-demonstrabila. Completitudinea, atunci, este una din directiile afirmatiei de mai sus: un sistem

modal normal Λ este complet cu privire la clasa de cadre C ddaca orice formula C-valida este Λ-demonstrabila.

Fie Λ un sistem logic modal normal si C o clasa de cadre-Kripke. Atunci, având în minte definitiile 2.11, 2.12,

2.13, 2.14, 2.7, putem defini formal notiunile de completitudine tare si slaba:

Definitia 3.1 (Completitudine tare). Λ e tare completa relativ la C ddaca pentru orice Γ∪{φ} avem ca: daca

Γ |=C φ, atunci Γ `Λ φ.

Definitia 3.2 (Completitudine slaba). Λ e slab completa relativ la C ddaca |=C φ, atunci `Λ φ.

15

3.1 Demonstratii de completitudine folosind metoda lui Henkin

Odata definite notiunile de completitudine tare si slaba, putem începe sa prezentam demonstratia de completi-

tudine tare folosind metoda lui Henkin, mai exact, folosind constructia modelului canonic ce valideaza toate si

doar formulele demonstrabile în sistemul a carui completitudine ne intereseaza. Completitudinea slaba decurge

din completitudinea tare, asa încât prezentarea teoremelor si demonstratiilor pentru completitudinea slaba este

superflua. Constructia modelului canonic presupune, la rândul ei, introducerea notiunii de multime maximal

consistenta, iar demonstratia-Henkin va presupune folosirea Lemei lui Lindenbaum si a proprietatilor multim-

ilor maximal consistente. Le vom prezenta în subsectiunile urmatoare. Desigur, cititorul familiarizat cu toate

acestea poate sari la subsectiunea 3.1.3.

3.1.1 Multimi Λ-maximal consistente (Λ−mmc)

Definitia 3.3. O multime Γ este maximal-consistenta ddaca:

(1) Γ este Λ-consistenta si:

(2) daca o multime Σ contine multimea Γ, atunci Σ este Λ-inconsistenta (conditia maximalitatii):

∀Σ : Γ⊂ Σ =⇒ Σ `Λ ⊥ (6)

Lema 3.1 (Lema lui Lindenbaum). Fie Γ o multime Λ-consistenta. Atunci exista o multime Γ+ maximala si

consistenta astfel încât Γ⊆ Γ+.

Informal, Lema lui Lindenbaum spune ca orice multime consistenta de formule poate fi extinsa pâna la (sau

scufundata într-o) multime maximala si consistenta de formule.

(Indicatii bibliografice: Mircea Dumitru, Modalitate si Incompletitudine, pp. 32-39, Brian Chellas, Modal

Logic: An Introduction, pp.55-58., Patrick Blackburn et al., Modal Logic, pp. 199-200)

Pentru a demonstra Lema lui Lindenbaum 3.1, sa presupunem ca toate propozitiile lui L pot fi enumerate

asa încât orice propozitie sa apartina acestei enumerari, dar fara a fi necesar ca o propozitie sa apara o singura

data: φ1, φ2, φ3... si sa luam multimea Σ ca fiind multimea acestora. Apoi, definim o secventa infinita de

multimi de propozitii Γ0, Γ1, Γ2... , respectând urmatoarele reguli:

(1) Γ0=Γ

(2) Γn+1 =

Γn∪{φn+1} , daca Γn∪{φn+1} 0Λ ⊥(consistenta)

Γn , altfel

(3) Γ+=⋃

n≥0 Γn

16

Echivalent, (2) se poate scrie:

2.1. Γn+1 =

Γn∪{¬φn+1} , daca Γn∪{φn+1} `Λ ⊥

Γn∪{φn+1} , daca Γn∪{φn+1} 0Λ ⊥

1. Vom arata ca Γ+ este consistenta: Γ+ 0Λ ⊥. Sa presupunem ca nu este, deci exista o submultime finita

inconsistenta Γ′ a lui Γ+: Γ′⊆ Γ+, Γ′ `Λ⊥. Putem deduce ca exista Γi construita dupa regulile (1)-(3) : Γ′⊆ Γi,

care sa fie inconsistenta, ceea ce contrazice constructia multimilor {Γi} (vezi regulile (1)-(3)). Deci, Γ+ este

Λ-consistenta.

2. Vom arata ca Γ+ este maximala. Sa amintim ca Γ+ =⋃

n≥0 Γn. Vom arata maximalitatea lui Γ+

prin reducere la absurd. Sa presupunem ca Γ+ nu este maximala. Atunci, exista Γ++ asa încât: Γ++ 0Λ ⊥(consistenta) si Γ+ ( Γ++. Din acestea deducem ca exista un ψ asa încât: ψ ∈ Γ++ si ψ /∈ Γ+. Din faptul ca

φ1, φ2, ... este o enumerare a lui L (a tuturor propozitiilor lui L), avem ca exista un indice k asa încât φk = ψ.

Bineînteles, se pastreaza cele de mai sus: φk 6∈ Γ+ si φk ∈ Γ++. Din constructia multimilor {Γ}, avem ca

Γk = Γk−1∪{¬φk} (daca φk nu apartine lui Γk, atunci ¬φk apartine lui Γk). Bineînteles, Γ+ = Γk, iar din faptul

ca ¬φ ∈ Γ+, avem ca ¬φ ∈ Γ++ (multimile Γ sunt ordonate crescator fata de relatia de incluziune). Ceea ce

contrazice faptul ca φ ∈ Γ++ din ipoteza si consistenta multimii Γ++. Deci Γ+ este maximala.

3.1.2 Proprietati ale Λ-multimilor maximal consistente

Propozitia 3.1. Fie Λ un sistem modal normal si Γ o Λ-multime maximal consistenta (Λ−mmc). Atunci:

1. φ ∈ Γ⇐⇒ Γ `Λ φ (7)

2. Daca φ ∈ Γ,φ→ ψ ∈ Γ, atunci ψ ∈ Γ(Γ este închisa sub regula modus ponens) (8)

3. Λ⊆ Γ (9)

4. ∀φ : φ ∈ Γ sau ¬φ ∈ Γ (10)

5. ∀φ,ψ : φ∨ψ ∈ Γ⇐⇒ φ ∈ Γ sau ψ ∈ Γ (11)

6. ∀φ,ψ : φ,ψ ∈ Γ⇐⇒ φ∧ψ ∈ Γ (12)

7.∀φ,ψ : φ→ ψ ∈ Γ⇐⇒ daca φ ∈ Γ, atunci ψ ∈ Γ (13)

8. > ∈ Γ (14)

9. ⊥ /∈ Γ (15)

Demonstratii.

1. Aceasta proprietate stabileste un fapt interesant: deductibilitatea unei propozitii dintr-o Λ-mmc coincide

cu apartenenta propozitiei la aceasta21.

(=⇒)Vom arata ca φ ∈ Γ =⇒ Γ `Λ φ. Vom asuma ca φ ∈ Γ. Stim ca φ→ φ este o tautologie a logicii

21Brian Chellas [4], p. 53.

17

propozitionale, deci `Λ φ→ φ, ceea ce este echivalent cu φ `Λ φ. Pentru ca φ ∈ Γ, avem ca Γ `Λ φ.

(⇐=) Vom arata ca Γ `Λ φ=⇒ φ∈ Γ, cu alte cuvinte, ca o Λ-mmc este închisa fata de consecinta semantica

deductiva22. Vom asuma ca Γ `Λ φ si, pentru a ajunge la o contradictie, ca φ /∈ Γ. Din maximalitatea lui Γ

obtinem ca Γ∪{φ} ` ⊥. De unde rezulta: Γ ` ¬φ, care contrazice asumptia facuta. �

2. Vom rationa prin reducere la absurd. Sa presupunem ca φ ∈ Γ, φ→ ψ ∈ Γ si ψ /∈ Γ. Având în vedere

faptul ca Γ este maximal consistenta, din ψ /∈Γ obtinem ca Γ0ψ (*) Din φ∈Γ, avem ca Γ` φ, iar din φ→ψ∈Γ

avem ca Γ ` φ→ ψ. Folosind regula de deductie modus ponens, din Γ ` φ si Γ ` φ→ ψ obtinem Γ ` ψ (**).

Concluziile derivate din presupozitie, adica (*) si (**), se contrazic, deci presupozitia acestei demonstratii este

falsa. �

3. Ceea ce spune aceasta proprietate este ca o Λ-multime maximala consistenta (Γ este o Λ−mmc) contine

toate teoremele sistemului logic Λ. Fie φ ∈ Λ si avem de aratat ca Γ `Λ φ, pentru Γ o Λ−mmc. Din φ ∈ Λ,

rezulta ca `Λ φ. Aceasta înseamna ca exista o teorema a sistemului Λ: (∧n

i=1 ψi)→ φ, cu n = 0. Pentru ca

n = 0, /0 `Λ φ. Pentru ca multimea vida este inclusa în orice multime, avem ca pentru o multime Σ aleatoare :

Σ `Λ φ. �

4. Vom asuma, pentru a obtine o contradictie, ca: φ /∈ Γ si ¬φ /∈ Γ, care sunt echivalente cu Γ 0Λ φ si

Γ 0Λ ¬φ. Prima din ele implica Γ∪{¬φ} 0Λ ⊥, iar a doua Γ∪{φ} 0Λ ⊥. �

5. Evidenta.

6. (=⇒) φ,ψ ∈ Γ =⇒ φ∧ψ ∈ Γ. Folosind (1), avem ca: Γ `Λ φ si Γ `Λ ψ. Urmând regulile calculului

propozitional, obtinem: Γ `Λ φ∧ψ si, din (1), ca φ∧ψ ∈ Γ.

(⇐=) φ∧ψ ∈ Γ =⇒ φ,ψ ∈ Γ. Din (1), avem ca: Γ `Λ φ∧ψ. Regulile logicii propozitionale (integrate

logicii modale) ne asigura ca Γ `Λ φ, deci φ ∈ Γ (folosind (1)) si Γ `Λ ψ, deci ψ ∈ Γ (din (1)). �

7. (=⇒) este identica cu (2), adica închiderea fata de modus ponens a multimilor maximal consistente.

(⇐=) (φ ∈ Γ =⇒ ψ ∈ Γ) =⇒ (φ→ ψ ∈ Γ). Vom demonstra o forma echivalenta (prin contrapozitie):

(φ→ ψ /∈ Γ) =⇒ (φ ∈ Γ si ψ /∈ Γ). Din φ→ ψ /∈ Γ obtinem, prin (1), ca Γ 0Λ φ→ ψ, deci Γ ` ¬(φ→ ψ), de

unde Γ ` φ∧¬ψ. Obtinem ca Γ `Λ φ si Γ `Λ ¬ψ, care ne duc la Γ `Λ φ si Γ 0Λ ψ. Acestea, pe rând, prin (1),conduc înspre concluzia cum ca φ ∈ Γ si ψ /∈ Γ, ceea ce ne trebuia. �

8. Având în vedere ca e un adevar al logicii propozitionale ca ` >, avem, bineînteles, ca `Λ >. Apoi,

folosind (1): > ∈ Γ. �

9. Sa presupunem, pentru a reduce la absurd, ca ⊥ ∈ Γ. Din (1), obtinem: Γ `Λ ⊥, adica Γ este inconsis-

tenta, ceea ce contrazice ipoteza conform careia Γ este maximala si consistenta. �

22v. si Mircea Dumitru [7], pp. 35-36 pentru demonstratie si comentarii.

18

3.1.3 Modele Canonice

(Indicatii bibliografice. Vom urmari: Patrick Blacburn et al., Modal Logic, pp. 198-204, Mircea Dumitru,

Modalitate si incompletitudine, pp. 40-41, Brian Chellas, Modal Logic: An Introduction, Hughes si Cresswell,

A New Introduction to Modal Logic)

Definitia 3.4. În cele ce urmeaza, un model canonic va fi notat astfel: MCan = (WCan,RCan,VCan) si construit

urmând regulile:

• WCan este multimea tuturor Λ-multimilor maximal consistente. Altfel spus, oricare w ∈WCan este o

Λ−mmc si orice Λ−mmc este un element al domeniului WCan (o lume posibila).

• RCan, relatia canonica de accesibilitate, este binara:

RCan ⊆WCan×WCan (16)

si este definita de regula:

wRCanu ddaca ∀φ ∈ u⇒ ♦φ ∈ w (17)

Sau echivalent, dar pentru operatorul necesitatii:

wRCanu ddaca ∀φ : �φ ∈ w⇒ φ ∈ u (18)

• Valuatia actioneaza astfel încât:

MCan,w |= p ddaca p ∈ w, pentru p ∈ Atomi(L) (19)

Lema 3.2 (Lema existentei23). Informal, ceea ce spune aceasta lema este ca daca o formula modalizata ♦φ se

afla în w, atunci exista o lume (multime maximal consistenta) accesibila din w, care sa contina pe φ. Formal:

♦φ ∈ w, atunci ∃u ∈WCan : (w,u) ∈ RCan si φ ∈ u (20)

Demonstratie.

Sa presupunem ca ♦φ ∈ w. În continuare, demonstratia se bazeaza pe a construi o lume u+ care sa fie

accesibila lumii w si al carei membru sa fie φ. Sa presupunem ca acea lume este multimea u = {φ}∪{ψ |�ψ ∈w}. Trebuie sa aratam ca respecta conditia consistentei. Pentru reductio, sa presupunem ca nu. Atunci, ⊥ ∈ u,

ceea ce înseamna ca exista o multime de formule {ψi} astfel încât :

(1) `∧

i≤n ψi→¬φ

Aplicând regula necesitarii la (1), avem:

(2) `�(∧

i≤n ψi→¬φ)

Acum, aplicând axioma K asupra formulei (2), obtinem urmatoarea instanta a respectivei axiome:

(3) `�(∧

i≤n ψi→¬φ)→ (�(∧

i≤n ψi)→�¬φ)

23V. si Patrick Blackburn et al. [2], pp. 200-201, Brian Chellas [4], p. 172.

19

Aplicând modus ponens la rândurile (2) si (3) obtinem:

(4) `�∧

i≤n ψi→�¬φ

Ne vom folosi de faptul ca în orice logica modala normala tine urmatoarea:

(5) `∧

i≤n�ψi→�∧

i≤n ψi.

Acum, aplicând o regula de deductie a calculului propozitional numita silogismul ipotetic 24 liniilor (4) si

(5) obtinem:

(6) `∧

i≤n�ψi→�¬φ

Din ipoteza avem ca {�ψi}i≤n ∈ w, deci, pentru ca w este o multime maximala consistenta,∧

i≤n�ψi ∈ w.

Atunci, �¬φ ∈ w. Dar �¬φ↔ ¬♦φ, deci ¬♦φ, ceea ce contrazice faptul ca ♦φ ∈ w. Deci u este consis-

tenta. Acum, pentru ca este consistenta, Lema lui Lindenbaum (3.1) ne asigura ca exista o multime maximala

consistenta care contine pe u, si anume u+. În concluzie, existenta lumii u+ a fost demonstrata. �

Lema 3.3 (Lema adevarului într-un model canonic25).MCan,w |= φ ddaca φ ∈ w pentru φ ∈ Prop(L) si w ∈WCan (21)

Demonstratie.

Demonstratia se face prin inductie pe lungimea formulei φ. Asadar, trebuie demonstrat ca echivalenta

stipulata de teorema tine pentru φ de forma p (atom propozitional, iar acesta va fi cazul de baza al argumentului

inductiv), pentru cazurile boolene: ¬φ, φ∧ψ, φ∨ψ, φ→ ψ si pentru cazul modal �φ. Le vom demonstra pe

rând:

MCan,w |= p⇐⇒ p ∈ w (22)

Demonstratie. Imediata, din definitia valuatiei (vezi 3.4) modelelor canonice.

MCan,w |= ¬φ⇐⇒¬φ ∈ w (23)

Demonstratie.

(=⇒) Daca MCan,w |= ¬φ, atunci, din definitia relatiei de satisfactie (2.10) într-un model Kripke, avem ca

MCan,w 6|= φ. Atunci, din ipoteza inductiei, avem ca φ 6∈ w. Pentru ca w este o Λ−mmc, obtinem imediat ca

¬φ ∈ w.

(⇐=) Daca ¬φ ∈ w, atunci, din maximal-consistenta lui w, avem ca φ 6∈ w. Apoi, din ipoteza inductiei, ca

MCan,w 6|= φ. Deci, din definitia relatiei de satisfactie (2.10), ca MCan,w |= ¬φ.

24Daca ` φ→ ψ si ` χ→ φ, atunci ` χ→ ψ.25V. si Patrick Blackburn et al. [2], p. 201, Hughes si Cresswell [6] pp. 118-119, Brian Chellas [4] pp.172-173.

20

MCan,w |= φ∧ψ⇐⇒ φ∧ψ ∈ w (24)

Demonstratie.

(=⇒) Avem urmatoarele echivalente:

MCan,w |= φ∧ψ⇐⇒MCan,w |= φ si MCan,w |= ψ (25)

MCan,w |= φ⇐⇒ φ ∈ w (26)

MCan,w |= ψ⇐⇒ ψ ∈ w (27)

Acum, trebuie sa aratam ca din φ ∈ w si ψ ∈ w obtinem ca φ∧ψ ∈ w. Rezultatul a fost demonstrat în

subsectiunea dedicata multimilor maximal consistente (vezi proprietatea (6) din Propozitia 3.1).

MCan,w |= ♦φ⇐⇒ ♦φ ∈ w (28)

Demonstratie.

(=⇒) Sa presupunem ca MCan,w |= ♦φ. Atunci, din definitia semantica a operatorului posibilitatii, avem

ca exista u ∈WCan astfel încât (w,u) ∈ RCan si Mcan,u |= φ. De aici, din ipoteza inductiei avem ca φ ∈ u. Din

definitia relatiei de accesibilitate într-un model canonic obtinem imediat ca ♦φ ∈ w

(⇐=) Sa presupunem ca ♦φ ∈ w. Atunci, conform Lemei de existenta 3.2 demonstrata mai sus, avem

ca exista u ∈WCan astfel încât φ ∈ u si (w,u) ∈ RCan. Din ipoteza inductiei, avem ca daca u ∈WCan, atunci

MCan,u |= φ. În conjunctie cu faptul ca (w,u) ∈ RCan, avem ca MCan,w |= ♦φ, ceea ce doream. �

Teorema 3.4 (Teorema Modelului Canonic26). Orice logica modala Λ este completa în sens tare relativ la

modelul ei canonic.

Demonstratie.

Sa presupunem ca Σ este o multime Λ-consistenta: Σ 6` ⊥. Atunci exista o multime maximal consistenta Σ+

care contine multimea Σ (Lema lui Lindenbaum). Lema adevarului 3.3 ne asigura ca Σ+ este o lume posibila27

a domeniului WCan care satisface fiecare φ ∈ Σ: MCan,Σ+ |= Σ. �

Care este sensul teoremei de mai sus? Informal, ea spune ca daca o multime este consistenta, atunci este

realizabila în (sau modelabila de catre) modelul ei canonic.

Teorema 3.5 (Teorema de completitudine tare a sistemului K28). Sistemul K este complet în sens tare cu privire

la clasa tuturor cadrelor-Kripke.

Demonstratie.26V. Patrick Blackburn et al. [2], p. 201, Hughes si Creswell [6], p. 119, Brian Chellas [4], p. 173.27Sa ne amintim ca într-un model canonic lumile posibile sunt multimi maximale si consistente de formule, conform Definitiei 3.4.28V. Patrick Blackburn et al. [2], p. 202, Hughes si Creswell [6], p. 120. Brian Chellas [4], p. 175.

21

Orice multime consistenta Σ de formule ale sistemului K este satisfacuta într-o lume posibila. Demon-

stratia este asemanatoare cu cea pentru Teorema modelului canonic 3.4. Sa zicem ca Σ 6`K ⊥, sau ca Σ este

K-consistenta. Atunci, fie modelul canonic pentru sistemul K, MKCan chiar MCan asa cum este definit mai

sus. În acest caz, conform Teoremei 3.4, Σ este satisfacuta într-o K−mmc29 Σ+ care extinde multimea Σ.

Cadrului peste care este construit modelul canonic nu îi este impusa nici o proprietate (cum ar fi, spre exemplu,

reflexivitatea, simetria sau tranzitivitatea), deci completitudinea este relativa la orice clasa de cadre-Kripke. �

Cu toate acestea, cadrul canonic obisnuit nu este cadrul care permite demonstrarea completitudinii tari a

oricarui sistem de logica modala (care sa includa strict pe K). Unele modificari facute asupra acestuia permit

teoreme de completitudine pentru mai multe sisteme de logica modala. Mai exact, modificarile care trebuie

aduse sunt structurale, afectând doar relatia de accesibilitate între multimile maximal consistente ce compun

domeniul.

Teorema 3.6 (Teorema de completitudine pentru sistemul K430). Sistemul K4 = K+(4) = K+♦♦p→♦p este

complet în sens tare relativ la clasa tuturor cadrelor canonice tranzitive (a caror relatie de accesibilitate este

tranzitiva).

Demonstratie.

Pentru început, sa ne amintim proprietatea tranzitivitatii unei relatii binare: ∀x,∀y,∀z : (xRy∧yRz)→ xRz).

Sa presupunem ca Σ este o multime K4-consistenta: Σ 6`K4 ⊥. Sa numim MK4Can modelul canonic, iar CK4

Can

cadrul canonic utilizat în demonstratie. Din Lema lui Lindenbaum 3.1 stim ca exista Σ+, o K4−mmc. Din

Teorema modelului canonic 3.4 avem ca MK4Can,Σ

+ |= Σ, pentru Σ+ o K4−mmc. Acum, trebuie sa aratam ca

FK4Can este un cadru tranzitiv. Sa vedem ca RK4

Can este tranzitiva. Sa presupunem ca wRK4Canu si uRK4

Canv si sa aratam

ca wRK4Canv. Sa presupunem ca φ ∈ v. Atunci, pentru ca lumea u vede v prin relatia de accesibilitate RK4

Can, avem

ca ♦φ ∈ u. La fel, pentru ca wRK4Can, avem ca ♦♦φ ∈ w. Pentru ca w este o K4−mmc, obtinem ♦♦φ→ ♦φ.

Pentru ca ♦♦φ→ ♦φ ∈ w si ♦♦φ ∈ w, prin proprietatea (7) demonstrata în Propozitia 3.1, obtinem ca ♦φ ∈ w.

Atunci, folosind Lema existentei 3.2, avem ca wRK4Canv, ceea ce ne trebuia. �

Teorema 3.7 (Teorema de completitudine pentru sistemul S531). Sistemul S5 este complet în sens tare relativ

la clasa tuturor cadrelor canonice reflexive, simetrice si tranzitive.

Demonstratie.

Asemanatoare teoremei de completitudine tare pentru K4. Vezi si Patrick Blackburn et al. [2] p. 205,

Hughes si Cresswell [6] p. 121.

29Renuntam la denumirea generica de Λ−mmc deoarece ne intereseaza sistemul modal K si nu unul normal oarecare.30V. Patrick Blackburn et al. [2], p. 204.31V. Patrick Blackburn et al. [2], p. 205.

22

3.2 Demonstratia de completitudine slaba a lui L. Moss

(Indicatii bibliografice: articolul lui L. Moss, Finite Models Constructed From Canonical Formulas [21] si

prezentarea lui Eric Pacuit, disponibila la adresa: http://ai.stanford.edu/~epacuit/classes/modal-spr2012/

ml-filtration-completeness.pdf [22])

În aceasta subsectiune vom prezenta o demonstratie a completitudinii slabe a sistemului K datorata lui L.S.

Moss [21].32 Înaintea prezentarii demonstratiei lui Moss vor fi amintite si prezentate câteva notiuni tehnice. În

primul rând, este vorba de o teorema de completitudine slaba, deci nu este cazul ca oricare ar fi multimea Σ

K-consistenta de formule, daca φ este consecinta semantica din Σ, atunci φ este deductibila din Σ în sistemul

K. Demonstratia lui Moss nu face apel la modelele canonice-Henkin, alcatuite din lumi posibile reprezentate

sub forma unor multimi maximale si consistente de formule, ci la un tip special de modele-surogat alcatuite

din formule canonice (modele pe care le vom numi modele canonice-Moss), formule ce reprezinta fiecare

lume posibila sub forma unei conjunctii (1) a tuturor atomilor atribuiti lumii posibile respective si (2) a tuturor

formulele modale satisfacute relativ la acea lume posibila. Vom detalia în urmatoarele pagini notiunile de

formula canonica a unei lumi posibile, model canonic-Moss al carui domeniu este alcatuit din formule canonice

si alte câteva notiuni conexe si utile în demonstratie.

3.2.1 Formule canonice

Cel mai important concept folosit în teorema lui Moss este cel de formula canonica. Intuitiv, formula canonica

a unei lumi posibile w este o formula construita din toate formulele adevarate relativ la w, de la atomii propoz-

itionali asignati de functia de valorizare V , la formulele modalizate de tip ♦φ, adevarate la w daca lumi u relativ

la care e adevarat ca φ sunt accesibile prin relatia R lumii w. Felul în care sunt utilizate formulele canonice este

analog felului în care sunt utilizate multimile maximal consistente în demonstratia "clasica", de tip Henkin, de

mai sus. În cazul teoremei de tip Henkin, domeniul modelului canonic contine multimi maximal-consistente

w care contin ca elemente toate formulele satisfacute în acea lume w (asa cum au fost asignate prin functia

de valorizare V catre w), iar în cazul teoremei lui L. Moss, lumile modelului canonic-Moss construit pentru

a interpreta sistemul de logica modala K sunt nu multimi, ci constructe sintactice: formulele canonice. În ce

sens sunt constructe sintactice? Simplu, formulele canonice sunt formule ale limbajului modal. Acum, daca

satisfacerea unei formule φ la o lume a modelului canonic se traducea prin apartenenta formulei φ la multimea

maximal-consistenta w (Lema adevarului pentru modelele canonice-Henkin 3.3), în modelele canonice-Moss,

satisfacerea formulei φ relativ la o lume α este echivalenta cu implicarea formulei φ de catre formula α (vom

vedea Lema adevarului pentru modelele canonice-Moss): α→ φ. Modelele canonice-Moss vor fi construite în

asa fel încât fiecare formula α sa fie K-consistenta (adica derivabila în sistemul K). Atunci, în virtutea Lemei

adevarului, faptul ca o lume satisface formula φ (deci α→ φ, cum am prezentat mai sus) va implica faptul ca

`K α→ φ. Odata stabilit acest lucru, un pas rapid ne va conduce la rezultatul de completitudine slaba dorit:

32Trebuie mentionat faptul ca Moss reuseste sa demonstreze în [21] completitudinea slaba pentru sisteme de logica modala maiputernice decât K. Nu le vom prezenta pe toate acestea, ci ne vom concentra doar asupra celei pentru K.

23

`K φ. Sa detaliem.

Definitia 3.5. Pentru cele ce urmeaza, sa presupunem ca multimea de atomi propozitionali este numerotata:

Atomi(L) = {p1, ..., pn}.

Definitia 3.6. Adâncimea unei formule φ este cea mai lunga succesiune de operatori modali din formula φ, se

noteaza h(φ) si este definita inductiv, precum urmeaza:

• h(pi) = 0

• h(¬φ) = h(φ)

• h(φ∧ψ) = h(φ)∧h(ψ)

• h(♦φ) = h(φ)+1

Definitia 3.7. Ordinul unei formule, ord(φ) este cel mai mare indice al unui atom propozitional care apare în

formula φ:

• ord(pn) = n

• ord(¬φ) = ord(φ)

• ord(φ∧ψ) = max{ord(φ),ord(ψ)}

• ord(♦φ) = ord(φ)

Acum, pentru a construi formulele canonice, vom avea nevoie sa definim multimi de formule de anumite

adâncimi si ordine. Multimea Lh,n, mai jos definita, denota multimea tuturor formulelor de adâncime cel mult

egala (sau egala) cu h si ordin cel mult egal (sau egal) cu n:

Definitia 3.8. Lh,n = {φ | φ ∈ L,h(φ)≤ h,ord(φ)≤ n}

Exemplu. Pentru a exemplifica cele trei notiuni de mai sus, sa luam formula:

φ := ♦p0∧�♦�p1∧♦¬♦p4 (29)

Avem, atunci, adâncimea h(φ)= 3, pentru ca cea mai lunga secventa de operatori este �♦� (care prefixeaza

atomul p1), iar ordinul ord(φ) = 4, deoarece 4 este cel mai mare indice al unui atom folosit în formula φ, si

anume p2. Deci φ se afla în multimea L3,4. Bineînteles, se afla si în L3,5, L4,4, si, în genere, în Lh≥3,n≥4.

Sa ne amintim ca formula canonica a unei lumi posibile w este o formula alcatuita din toti atomii propoz-

itionali ai lui w si toate formulele modalizate satisfacute de w. Pentru a oferi definitia formala a unui astfel

de construct sintactic, trebuie sa avem o reprezentare sintactica a actiunii functiei de valorizare (functia care

asigneaza multimi de lumi posibile atomilor propozitionali).

24

Definitia 3.9. Fie n ∈ N si {p1, ..., pn} o multime de atomi propozitionali. Atunci, pentru T ⊆ {p1, ..., pn}:T :=

∧pi∈T

pi∧∧

pi∈{p1,...,pn}−T

¬pi (30)

Exemplu. Fie n = 5. Atunci, multimea de atomi asupra carora vom lucra este {p1, p2, p3, p4, p5}. Fie

T = {p2, p3, p4}. Atunci, {p1, ..., p5}−T = {p1, p5} si, în fine: T = p2∧ p3∧ p4∧¬p1∧¬p5.

În cele ce urmeaza, vom arata felul în care sunt construite multimi de formule canonice. Mai jos este

definita metoda inductiva de construire a multimilor de formule canonice.

Definitia 3.10 (Multimi de formule canonice). Vom nota prin Ch,n o multime oarecare de formule canonice de

adâncime h si ordin n. Constructia este inductiva:

• C0,n = {T | T ⊆ {p1, ..., pn}}

• Ch+1,n := {αS,T | S⊆Ch,n,T ⊆ {p1, ..., pn}}, pentru αS,T o formula canonica definita astfel:

• αS,T := T ∧∧

φ∈S♦φ∧�φ∈S∨

φ

Asa cum se vede, C0,n este multimea tuturor valorizarilor posibile si, într-un sens, ele reprezinta toate lumile

posibile ale unui model. De ce? Pentru ca lumile posibile pot fi vazute ca stari de fapt, conjunctii literali qi,

unde orice qi este sau un atom pi sau negatia acestuia, ¬pi. La nivelul Ch+1,n putem reprezenta nu doar atomii

asignati unei lumi posibile ci si formulele modalizate, adica rezultatul interactiunii lumilor posibile între ele:

daca o lume w vede o lume u în care este adevarat ca p, atunci ♦p este adevarata în w etc.

Exemplu. Sa exemplificam fiecare din elementele introduse:

• C0,1 = {p1,¬p1}

• C0,2 = {p1,¬p1, p2,¬p2}

• C1,1 = {αS,T | S⊆C0,1,T ⊆ {p1}}

Atunci, avem o multime de formule canonice αi:

• α1 = p1, pentru T = p1 si S = /0, caz în care nu exista nici un φ ∈ S.

• α2 = ¬p1, pentru T = ¬p1 si S = /0.

• α3 = p1∧♦p1∧�p1, pentru T = p1 si S = {p1}

• α4 = ¬p1∧♦p1∧�p1, pentru T = ¬p1 si S = {p1}

• α5 = p1∧♦¬p1∧�¬p1, pentru T = p1 si S = {¬p1}

• α6 = ¬p1∧♦¬p1∧�¬p1, pentru T = ¬p1 si S = {¬p1}

25

• α7 = p1∧ (♦p1∧♦¬p1)∧�(p1∨¬p1), pentru T = p1 si S = {p1,¬p1}

• α8 = ¬p1∧ (♦p1∧♦¬p1)∧�(p1∨¬p1), pentru T = ¬p1 si S = {p1,¬p1}

Asa cum se vede din definitie, o formula canonica α este definita în functie de o multime de atomi propoz-

itionali T si o multime S ⊆Ch,n de alte formule canonice. Multimea T este utila în a introduce formula T ca

parte (conjunct) al formulei canonice. În fapt, T introduce toti atomii care au fost asignati de functia de val-

orizare lumii posibile a carei formula canonica o construim. Multimea S este utila în introducerea în formula

canonica a tuturor formulelor modalizate care sunt adevarate în lumea posibila aleasa. Sa remarcam faptul ca

procedura de mai sus ne permite sa obtinem toate formulele canonice posibile într-un model. Daca dorim sa

aflam formula canonica a unei anumite lumi posibile putem urma constructia inductiva oferita de Moss:

• φ0w :=

∧pi∈T pi∧

∧pi 6∈T ¬pi

• φh+1w := φ0

w∧∧

wRu♦φhu∧�

∨aRb φh

u

Faptul ca în definitia de mai sus este folosita relatia de accesibilitate ne permite sa "cautam" în alte lumi

posibile formulele care trebuie modalizate în w.

Asemeni modelului canonic definit în sectiunea anterioara, modelul canonic Moss este construit cu intentia

de a satisface toate si doar teoremele unui sistem logic. În particular, modelul canonic-Moss este alcatuit din

multimea tuturor formulelor canonice care sunt K-consistente:

Definitia 3.11 (Modelul canonic Moss). Fie C= (C,R,V ) un model-Kripke definit astfel:

• C = {α | α ∈Ch,n,α este formula K-consistenta: `K α}

• Daca α∧♦β este consistenta, atunci αRβ, pentru α,β ∈C

• V (pi) = {α | α ∈C,` α→ pi}, oricare ar fi pi ∈ {p1, ..., pn}

Sa observam similaritatea cu ideea din spatele constructiei modelului canonic-Henkin: amândoua modelele

sunt construite asa încât sa puna în legatura notiunea semantica de validitate cu o notiune sintactica de demon-

strabilitate: apartenenta la o multime maximal-consistenta în cazul modelului canonic-Henkin si faptul de a fi

teorema a sistemului K (sau derivabila în sistemul K din multimea vida de ipoteze sau asumptii).

3.2.2 Teorema lui Moss pentru sistemul K

Definitia 3.12. Fie o multime X = {φ1, ...,φn}. Vom nota expresia "exact un element din X" prin: ⊕X sau

⊕{φ1, ...,φn}. Formal, este definita astfel:

⊕X =∨i∈A

(φi∧¬∨j 6=i

φ j) (31)

26

Urmatoarele leme vor conduce la demonstrarea teoremei de completitudine slaba pentru sistemul K.

Lema 3.8. Pentru orice h si n, avem:

`K ⊕Ch,n (32)

Demonstratie. Vezi demonstratia pentru Lema 2.6 din [21].

Lema 3.9. Pentru ψ ∈ Lh,n, avem:

` ψ↔∨{α ∈Ch,n | ` α→ ψ} (33)

Demonstratie. Vezi demonstratia pentru Lema 4.2 din[21].

Lema 3.10. Pentru φ ∈ Lh,n, exact una din urmatoarele are loc: `K α→ φ, ori `K α→¬φ

Demonstratie. Vezi demonstratia pentru Lema 2.7 din [21], sau demonstratia pentru Lema 3.1 din [22].

Lema 3.11 (Lema existentei). Fie ψ ∈ Lh,n si φ ales arbitrar. Sa presupunem ca ` φ∧♦ψ. Atunci exista

α ∈Ch,n asa încât ` α→ ψ.

Demonstratie.

Continutul lemei este intuitiv si este asemanator cu cel al Lemei de Existenta (3.2): în fapt, spune ca daca

este derivabila posibilitatea unei formule (♦ψ), atunci exista o lume posibila în care acea formula este adevarata:

α→ ψ. Pentru a întelege ce înseamna α→ ψ, sa ne amintim ca α este o formula canonica a unei lumi posibile,

adica o formula obtinuta din conjunctia tuturor adevarurilor care tin la acea lume.

Conform Lemei (3.9), avem ca:

` ♦ψ↔∨{♦α | α ∈Ch,n,` α→ ψ} (34)

` φ∧♦ψ↔∨{φ∧♦α | α ∈Ch,n,` α→ ψ} din (34) (35)

Formula∨{φ∧♦α | α ∈Ch,n,` α→ ψ} semnifica exact ceea ce cautam întrucât sensul ei este urmatorul:

exista macar o formula de tip φ∧♦α derivabila, cu proprietatea ca ` α→ ψ. Având în vedere ca am presupus

consistenta lui φ∧♦ψ, obtinem imediat si consistenta lui∨{φ∧♦α | α ∈ Ch,n,` α→ ψ}. Pentru claritate,

rationamentul este urmatorul:

(1) ` φ∧♦ψ (ipoteza)

(2) ` φ∧♦ψ↔∨{φ∧♦α | α ∈Ch,n,` α→ ψ} (ipoteza)

(3) ` (φ∧♦ψ→∨{φ∧♦α | α∈Ch,n,`α→ψ})∧(

∨{φ∧♦α | α∈Ch,n,`α→ψ}→ φ∧♦ψ) (din definitia

conectorului↔)

(4) ` φ∧♦ψ→∨{φ∧♦α | α ∈Ch,n,` α→ ψ} (din (3), eliminând conjunctia)

(5) `∨{φ∧♦α | α ∈Ch,n,` α→ ψ} (modus ponens aplicat la liniile (4) si (1))

27

Lema 3.12 (Lema adevarului). Pentru n fixat, pentru oricare formula φ ∈ Lh,n si oricare α ∈ C≤h,n, are loc

urmatoarea echivalenta:

Ch,n,α |= φ (36)

`K α→ φ (37)

Demonstratie.

Prima directie. Sa presupunem ca Ch,n,α |= ♦φ. Fie β ∈ Ch,n asa încât `K α∧♦β si Ch,n,β |= φ. Din

ipoteza inductiei avem ca daca Ch,n,β |= φ, atunci `K β→ φ. Atunci, `K ♦β→ ♦φ, conform Propozitiei 2.1.

Acum, sa ne amintim ca am asumat ca ` α∧♦β si sa urmarim urmatorul rationament:

(1) ` ♦β→ ♦φ (ipoteza)

(2) ` α∧♦β (ipoteza)

(3) ` α (din (2), eliminând conjunctia)

(4) ` ♦β (din (2), eliminând conjunctia)

(5) ` ♦φ (aplicând modus ponens la rândurile (1) si (4))

(6) ` α∧♦φ (din rândurile (3) si (5), introducând conjunctia)

Deci ` α si ` ♦β. Lema 3.10 ne asigura ca ori ` α→ ♦φ, ori ` α→¬♦φ. Daca ar fi cel de-al doilea caz,

atunci ar fi contrazis faptul obtinut mai devreme: ` α∧♦φ. De ce? Sa urmarim rationamentul:

(1) ` α→¬♦φ (ipoteza)

(2) ` α∧♦φ (ipoteza)

(3) ` α (din (2), eliminând conjunctia)

(4) ` ♦φ (din (2), eliminând conjunctia)

(5) ` ¬♦φ (aplicând modus ponens la rândurile (1) si (3)

(6) ` ♦φ∧¬♦φ (din rândurile (4) si (5)), Contradictie!

A doua directie. Sa presupunem ca ` α→ ♦φ. Pentru ca α este formula canonica (α ∈ Ch,n), avem ca

` α. Prin modus ponens obtinem ca ` ♦φ. Pentru ca ` α si ` ♦φ, avem ca ` α∧♦φ. Lema existentei (3.11) ne

asigura ca exista β∈Ch,n asa încât `α∧♦β si ` β→ φ. Dar aceasta înseamna ca formulele canonice sunt legate

prin relatia de accesibilitate: αRβ si ca Ch,n,β |= φ. Deci, din definitia semantica a operatorului posibilitatii,

avem ca Ch,n,α |= ♦φ, ceea ce doream. �

Teorema 3.13 (Teorema lui Moss de completitudine slaba pentru K). K este slab complet: pentru oricare

φ ∈ L, daca |= φ, atunci `K φ.

28

Demonstratie.

Fie h si n asa încât φ ∈ Lh,n. Sa presupunem ca |= φ. Atunci, pentru orice α ∈Ch,n, avem ca:

Ch,n,α |= φ (38)

Atunci, din Lema adevarului (3.12), avem ca, pentru oricare α ∈Ch,n:

`K α→ φ (39)

De aici, ca:

`K∨

Ch,n→ φ (40)

Din Lema (3.8), avem ca `K ⊕Ch,n. Dar atunci:

`K∨

Ch,n (41)

Aplicând modus ponens la (40) si (41), obtinem imediat ceea ce ne interesa:

`K φ (42)

3.3 Importanta teoremelor de completitudine a logicii modale pentru alte sisteme de logica

Teoremele de completitudine pentru sistemele K-S5 au o importanta practica în dezvoltarea logicilor epistemice

dinamice. Sa detaliem. Unii logicieni au remarcat incapacitatea logicii epistemice traditionale (a sistemelui S5)

de a reprezenta învatarea de catre agenti artificiali a unor noi adevaruri. Sa urmarim un exemplu inspirat din

[25] (p. 4). Sa presupunem ca doua persoane, (neinspirat) numite A si B, cer doua chei catre doua camere la

receptia unui hotel: A cere cheia pentru camera 12, iar B cere cheia care camera 34. Hotelierul, distrat, aduce

cheile, dar uita ce cheie trebuie data cui. Întrebând cui ar trebui sa-i revina cheia 12 si aflând ca este a lui A,

infereaza ca 34 este a lui B. Sa remarcam ca înainte de a întreba, el nu stie ca 34 trebuie data lui B: ¬Khotelier34B,

dar dupa întrebare, da: Khotelier34B. Cu alte cuvinte, în urma primirii raspunsului, el învata un adevar. Acest

tip de învatare este imposibil de reprezentat în logica epistemica: ori Khotelier34B este adevarata, ori Khotelier34B

este falsa, dar nu amândoua, iar trecerea de la falsitatea lui Khotelier34B la adevarul acesteia nu poate fi facut

prin nici un mijloc formal. În acest scop au fost construite logicile epistemice dinamice (vezi [26]). Aceste

logici includ, la nivel sintactic si semantic, operatori ce reprezinta actiuni epistemice, actiuni care schimba

cunoasterea agentilor unui grup. Un exemplu sunt anunturile publice într-un grup de agenti. Dupa un anunt

public al unei formule φ, agentii vor elimina incertitudinea legata de formula anuntata. Deci, la nivel semantic,

anuntarea unei formule implica eliminarea lumilor posibile în care nu este adevarat ca φ. Logica anunturilor

publice, descoperita independent de J. Gerbrandy ([8]) si J. Plaza ([23]) cuprinde un astfel de operator pentru

anunturi publice si o semantica bazata pe functii care transforma modelele Kripke (elimina lumile posibile în

care este falsa formula anuntata în grup). Spre exemplu, expresia dupa un anunt public ca ca φ, devine adevarat

ca ψ este redata formal 〈!φ〉ψ si este evaluata la o lume posibila:

M,w |= 〈!φ〉ψ ddaca M,w |= φ si M|φ,w |= ψ (43)

Unde modelul transformat, M|φ = (W |φ,R|φ,V |φ) , este definit astfel:

29

• W |φ = {w ∈W |M,w |= φ}

• R|φ = R∩ (W |φ×W |φ)

• V |φ =V ∩W |φ

Axiomele logicii anunturilor publice vor fi:

• (PAL1) 〈!φ〉p↔ φ∧ p

• (PAL2) 〈!φ〉¬ψ↔ φ∧¬〈!φ〉ψ

• (PAL3) 〈!φ〉(ψ∧χ)↔ (〈!φ〉ψ∧〈!φ〉χ)

• (PAL4) 〈!φ〉Kaψ↔ φ∧Ka(φ→ 〈!φ〉ψ)

Axiomele (PAL1)-(PAL4) sunt interesante pentru ca scopul acestora este sa reduca toate formulele logicii

anunturilor publice la formule ale logicii epistemice obisnuite. Asa cum se vede, fiecare axioma comuta op-

eratorii logicii anunturilor publice cu operatorii logicii epistemice. Axioma (PAL1) este cea care transforma,

finalmente, o formula dinamica într-una statica. Apoi, pentru ca logica epistemica S5 este completa, iar cele

doua logici sunt egal expresive, logica anunturilor publice este completa. Demonstratiile de completitudine si

cele legate de compararea expresivitatii celor doua tipuri de logici pot fi citite în [15] si [26]. În scopul aces-

tei sectiuni, una din concluzii ar putea fi aceasta: orice demonstratie de completitudine pentru o logica modala

(epistemica) este utila pentru ca permite construirea de axiome de reductie pentru alte logici (în cazul prezentat,

logici epistemice dinamice).

References

[1] E.W. Beth. Semantic entailment and formal derivability. Medelingen van de Koninklijke Nederlandse

Akademie van Wetenschappen, Afdeling Letterkunde, 18(13):309–342, 1955.

[2] de Rijke, M., Blackburn, P.,, Venema, Y.,. Modal Logic. Cambridge University Press, 2002.

[3] Rudolf Carnap. Semnificatie si necesitate - Un studiu de semantica si logica modala. Editura Dacia,

Cluj-Napoca, 1972.

[4] Brian Chellas. Modal Logic: An Introduction. Cambridge University Press, 1980.

[5] B. Jack Copeland. The genesis of possible worlds semantics. Journal of Philosophical Logic, 31(2):99–

137, 2002.

[6] Hughes, G.E. Cresswell, M.J.,. A New Introduction to Modal Logic. Routledge, 1996.

[7] Mircea Dumitru. Modalitate si incompletitudine. Paideia, Bucharest, 2001.

30

[8] Groeneveld, W. Gerbrandy, J.,. Reasoning about Information Change. Journal of Logic, Language and

Information, Volume 6, Number 2,, 6(2):147–169, 1997.

[9] Robert Goldblatt. Mathematical modal logic: a view of its evolution. J. of Applied Logic, 1(5-6):309–392,

October 2003.

[10] J. Hintikka. Quantifiers in deontic logic. Societas Scientiarum Fennica, Commentationes Humanarum

Litterarum, 13.4, 1957.

[11] J. Hintikka. Knowledge and Belief. Ithaca, N.Y.,Cornell University Press, 1962.

[12] Tarski, A. Jonsson, B.,. Boolean algebras with operators. Bull. Amer. Math. Soc., (54):79–80, 1948.

[13] Tarski, A. Jonsson, B.,. Boolean algebras with operators, part 1. Amer. J. Math., (73):891–939, 1951.

[14] Tarski, A. Jonsson, B.,. Boolean algebras with operators, part ii. Amer. J. Math., (74):127–162, 1952.

[15] Barteld Kooi. Expressivity and completeness for public update logics via reduction axioms. Journal of

Applied Non-Classical Logics, 17(2):231–253, 2007.

[16] Saul Kripke. A completeness theorem in modal logic. J. Symbolic Logic, (24):1–14, 1959.

[17] Saul Kripke. Semantical considerations on modal logic. Acta Philosophica Fennica, (16):83–94, 1963.

[18] Saul Kripke. Semantical analysis of modal logic i: Normal modal propositional calculi. Z. Math. Logik

Grundlag. Math., (9):67–96, 1964.

[19] Saul Kripke. Numire si necesitate. Editura All, 2001.

[20] David Lewis. Counterpart theory and quantified modal logic. Journal of Philosophy, (65):113–126, 1968.

[21] L.S. Moss. Finite models constructed from canonical formulas. Journal of Philosophical Logic,

36(6):605–640, 2007.

[22] Eric Pacuit. Filtrations and basic proof theory, notes for lecture 5. http://ai.stanford.edu/

~epacuit/classes/modal-spr2012/ml-filtration-completeness.pdf, mar 2012. Online: data

ultimei accesari: 11.07.2013.

[23] J. Plaza. Logics of public communications. In Ras, Z.W., Emrich, M.L., Pfeifer, M.Z., Hadzikadic, M.,

editor, Proc. 4th International Symposium on Methodologies for Intelligent Systems, pages 201 – 216.

Oak Ridge Laboratory, 1989.

[24] A.N. Prior. Three-valued logic and future contingents. Philosophical Quarterly, (3):317–326, 1953.

[25] Martinez, M. van Benthem, J.,. The stories of logic and information. http://www.illc.uva.nl/

Research/Reports/PP-2008-04.text.pdf/, 2008. Online: data ultimei accesari: 11.07.2013.

[26] van Ditmarsch, H.P., Kooi, B., van der Hoek, W. Dynamic Epistemic Logic. Springer, 2006.

31

[27] Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M. Reasoning about Knowledge. The MIT Press, Cambridge,

Massachusetts, 1995.

[28] G. von Wright. An Essay in Modal Logic. North-Holland Publishing Company, 1951.

[29] E. Zalta. Basic concepts in modal logic. http://mally.stanford.edu/notes.pdf, 1995. Online: data

ultimei accesari: 11.07.2013.

32