LOGICA MODALĂPENTRU TEORIA

SPAŢIULUI BAZATĂ PE REGIUNI

ÎndrumătorÎndrumător: Prof. Dr. George Georgescu: Prof. Dr. George GeorgescuStudent: Paula TStudent: Paula Tătaruătaru

Despre logica modalDespre logica modalăă

În logica modală apar doi operatori noi faţă de logica clasică:- necesar (□)- posibil (◊)numiţi operatori modali.

Operatorii modali se referă la măsura în care o propoziţie p esteadevărată, de la latinescul modus (măsură).

Construind modalitatea prin conceptul de realizabilitate, sensul cese degajă nu este acela al unei măsuri mai mari sau mai mici deadevăr sau de fals, ci acela al locurilor (interpretărilor) în care opropoziţie este adevărată sau falsă.

Alfabetul unui sistem modal va avea în plus faţă de cel al sistemuluiclasic, operatorul necesitate: □.Vom numi cuvânt un şir finit de simboluri primitive, iar enunţurilese vor construi plecând de la variabilele propoziţionale şi aplicândde un număr finit de ori operatorii propoziţionali clasici şi operatorulmodal.Introducem operatorul posibilitate prin abrevierea ◊p în loc de ¬ □ ¬ p.

Construim un sistem logic modal bazându-ne pe axiomele unui sistemformal al calculului propoziţional, la care adăugăm un numărminimal de axiome, reglementând comportamentul operatoruluimodal.

Sintaxa sistemelor propoziţionale modale

Se consideră următoarele axiome:(A0) axiomele calculului propoziţional(A1) □(p→q) →(□p → □q)(A2) □p→ p(A3) □p → □□p(A4) ◊p → □◊p

Reamintim axiomele calculului propoziţional:(A01) p →(q → p)(A02) (p →(q → r)) →((p → q) →(p → r))(A03) (¬ p → ¬ q) →(q → p)

Vom avea două reguli de deducţie:p, p → q modus ponens (m.p.) q p necesitate (N)□p

Considerăm următoarele sisteme de logică modală:K : A0, A1T : A0, A1, A2S4 : A0, A1, A2, A3S5 : A0, A1, A2, A3, A4Spunem că K şi T sunt sisteme slabe, iar S4 şi S5 sunt sisteme tari.

Teoremele formale se construiesc plecând de la axiome şi aplicând de un număr finit de ori cele două reguli de deduţie.

Semantica sistemelor propoziţionale modale

Semantica unui sistem logic începe cu noţiunea de interpretare.Pentru sistemele modale, conceptul de interpretare se face în raport cu o structură Kripke.

Numim structură Kripke o pereche (X,R), unde X este o mulţime nevidă, iar R este o relaţie binară pe X.

Vom numi interpretare a unui sistem modal în structura Kripke (X,R) corespunzătoare sistemului, o funcţie I : E × X → L2 = {0, 1}ce satisface condiţiile, pentru orice φ, ψ є E, x є X:(a)I(φ ψ,x) = I(φ,x) I(ψ,x); (b) I(¬φ,x) = ¬I(φ,x); (c) I(□φ,x) = {I(φ,y) | y є X, xRy}.

Enunţul φ este adevărat în interpretarea I relativ la x є X, dacă I(φ,x) = 1 şi este universal adevărat dacă este adevărat în orice interpretare.

Teorema de completitudine a lui KripkePentru orice sistem modal S şi pentru orice enunţ φ,φ este teoremă a sistemului S φ este universal adevărat în sistemul S.

Despre RPMLSDespre RPMLS

Logica modală pentru teoria spaţiului bazată pe regiuni (RPMLS = Region-based Propositional Modal Logics of Space) este un nou tip de logică modală potrivită pentru demonstraţii în teoria spaţiului bazată pe regiuni. Aceasta este o alternativă la teoria clasică a spaţiului ce are la bază noţiunea de punct. Teoria spaţiului bazată pe regiuni porneşte de la noţiunea de regiune şi câteva relaţii între regiuni, cum are fi cea de “parte a” sau de “contact”.

Limbajul L(C,≤) al RPMLS este similar cu limbajul de modalitate relativă. L(C,≤) conţine variabile Booleane şi operaţii Booleane. Conectorii modali sunt: ≤ pentru relaţia “parte a” şi C pentru “contact”.

Sintaxa

Introducem notaţiile:a = b : (a ≤ b) (b ≤ a)a ≠ b : ¬(a = b)

Semantica relaţională

Fie F = (X,R) o structură Kripke. Unei structuri Kripke îi putem da o intrepretare spaţială. Elementele lui X vor fi numite celule, iar relaţia R va fi numiă relaţie de adiacenţă. Atunci F va fi numit spaţiu de adiacenţă.

• tabla de şah

Regiunile în spaţiile de adiacenţă sunt submulţimi arbitrare ale lui X, iar două submulţimi a, b sunt în contact – a b, dacă există x є a şi y є b astfel încât să avem xRy.

Fie Σ o clasă de structuri.

Fie A o mulţime de formule.

Logică modală de clase de structuri

Fie Σ o clasă de structuri şi fie L(Σ) mulţimea formulelor adevărate în Σ. Această mulţime o vom numi logica lui Σ. Evident, vom avea:

dacă Σ1 Σ2, atunci L(Σ2) L(Σ1).

Dacă notăm clasa tuturor structurilor cu , atunci, conform proprietăţii de mai sus, L( ) va fi cea mai mică şi va fi notată cu .

Următoarea lemă leagă logica L(Σ) de noţiunea de Σ - consistenţă.

Definibilitate modală

Deoarece structurile reflexive şi simetrice vor avea importanţă mai târziu, vom nota cu (respectiv , ) clasa structurilor reflexive (respectiv simetrice, reflexive şi simetrice) şi cu clasa relaţiilor de echivalenţă. Formulele corespunzătoare care definesc modal aceste proprietăţi le vom nota: (Ref) p ≠ 0 → pCp(Sym) pCq → qCp

Nedefinibilitate modală

Axiomatizări

Pentru început, vom da un sistem axiomatic pentru logica .Acesta va conţine o mulţime de axiome şi o mulţime de reguli de deducţie.

Noţiunea de teoremă a lui este cea standard.

Teoreme de completitudine

Bibliografie

[1] P. Balbiani, T. Tinchev, D. VakarelovModal Logics for Region-based Theories of

SpaceFundamenta Informaticae, vol. 81, pag. 29-82.

2007.

[2] G. GeorgescuLogică matematică şi computaţională. Suport de

curs.

[3] G. GeorgescuTeoria modelelor pentru logici neclasice. Suport

de curs.