Semantica di Kripke

Capitolo 1

La semantica di Kripke1.1 Linguaggi enunciativi modali

Tipicamente, un linguaggio enunciativo modale dispone degli usuali connettivi , , , , di Lp (v. ??) e, in aggiunta, di uno o pi` operatori modali. u Nel caso pi` semplice quello del linguaggio proposizionale monomodale u si aggiungono a Lp i due operatori unari e che come sappiamo corrispondono, nella lettura aletica (una fra le tante!), alle locuzioni ` necessario e che . . . , risp. ` possibile che . . . . Luso dellattributo monomodale pu` e o suonare strano visto che gli operatori modali sono due. Il fatto ` che e e risultano interdenibili grazie alle equivalenze A A , A A 1

che, per A qualsiasi, risultano sempre valide quando la teorizzazione delle modalit` viene basata come di solito si fa sulla logica classica2 . a Mono(modale) vuole dunque dire: una sola coppia di operatori modali interdenibili: volendo, si pu` sempre prendere come primitivo uno solo tra o e , e denire metalinguisticamente laltro sulla scorta delle leggi sopra ricordate. In certi sistemi di logica modale applicata (p. es. le logiche epistemiche e le logiche dinamiche, che vedremo pi` avanti nei ??) risulta invece nau turale disporre di pi` di un operatore di tipo (e quindi anche, primitivi o u1 Si tratta delle leggi di contraddittoriet` del cosiddetto quadrato modale aristotelico a (De Interpretatione, 1213), in base alle quali un enunciato ` necessario ( A) se e solo se e la sua negazione ` impossibile (A), e un enunciato ` possibile (A) se e solo se la sua e e negazione non ` necessaria ( A). e 2 Quando si parla, senza ulteriori qualicazioni, di logiche modali, si intende sempre logiche modali classiche, caratterizzate dal fatto che gli operatori non modali sottostan` no alla semantica bivalente standard e che gli operatori e sono interdenibili. E bene sapere che sono stati studiati anche (ma noi non li tratteremo) sistemi modali basati su logiche non-classiche, in particolare quella intuizionistica, dove tipicamente linterdenibilit` a tra e ` la prima a saltare. e

1

2

CAPITOLO 1. LA SEMANTICA DI KRIPKE

non, di altrettanti operatori di tipo ): in questo caso si parla di linguaggi proposizionali multimodali.

1.1.1

Il linguaggio monomodale Lsi basa su un alfabeto che

Il linguaggio proposizionale monomodale L dispone dei seguenti simboli primitivi:

(i) variabili proposizionali o atomi: uninnit` numerabile p0 , p1 , p2 . . . , a (ii) costanti logiche: , , , , , (iii) simboli ausiliari: le parentesi ) e ( . Linsieme delle formule di L (useremo anche qui le lettere A, B, C . . . come metavariabili per formule) ` denito induttivamente come ci si aspetta: e gli atomi (metavariabili: p, q, r . . .) sono L -formule; se A e B sono L -formule allora lo sono anche: (A B) , (A B) , (A B) , A , A ; nientaltro ` una L -formula. e Le nozioni di sottoformula, lunghezza (o grado) di una formula ecc., a suo tempo introdotte per Lp , si lasciano estendere a L nel modo ovvio (esercizio). Anche per quanto riguarda la scrittura delle formule faremo economia di parentesi secondo convenzioni analoghe a quelle adottate per Lp , omettendo le parentesi pi` esterne e anche quelle pi` interne nei casi in u u cui sia possibile reintrodurle senza ambiguit` sulla base della stipulazione a che , e legano pi` di e che, a loro volta, legano pi` di e . u u Useremo alloccorrenza alcune abbreviazioni, in particolare: := p0 p0 ,n-volte

,,

A , (A B) ,

:= 3 ; A (0A

nA

:=

...

:= A) ,

e analogamente per .

Concludiamo con la denizione di alcune nozioni che ci serviranno pi` avanti. u Denizione 1.1.1. Una L -sostituzione ` una applicazione dallinsieme e {p0 , p1 , p2 . . .} degli atomi nellinsieme delle L -formule. Se A ` una formula e di L e ` una sostituzione, indichiamo con A la formula ottenuta da A e rimpiazzandovi ciascuna occorrenza di ciascun atomo p con la formula (p) (esercizio: dare una denizione induttiva). Se ` la L -sostituzione tale che (p) = p per ogni atomo p, conveniamo e di scrivere A invece che A : intuitivamente, si tratta della formula che si ottiene da A rimpiazzando ogni occorrenza di un atomo con la sua negazione.3 Sono possibili altre scelte: basta che e stiano per una Lp -tautologia, risp. una Lp -contraddizione arbitrariamente pressate.

1.1. LINGUAGGI ENUNCIATIVI MODALI

3

Denizione 1.1.2. Sia A una formula di L . A ` la formula denita e induttivamente come segue: p := p , (B) := B , (B C) := B C , (B C) := B C , (B C) := (C B ) , B . B, se A B; , altrimenti. A

(B C) := (C B ) , ( A) := B e (A) :=

Inne Ad , la formula duale di A, ` e

` E facile vericare che nel caso particolare (che ` poi quello che veramente e ci interesser`) in cui A ` una formula della forma B C con B e C prive di a e la duale di A, Ad , ` la formula ottenuta interscambiando / e / e e poi invertendo la direzione del condizionale. Per esempio: ( p p)d (p p) ( (p q) p q)d p q (p q) .

Esercizio 1.1.3. Dimostrare che, a meno di doppie negazioni, A coincide con A e Ad d coincide con A. Ogni formula di Lp ` anche una formula di L , perch il linguaggio L e e ` unestensione di Lp . La seguente denizione ` pertanto sensata: e e Denizione 1.1.4. Una formula A di L ` una L -tautologia se e solo se e esistono una tautologia B di Lp e una L -sostituzione tali che A B . Come gi` detto, la teorizzazione delle modalit` si basa sulla logica clasa a sica, ossia la semantica dei connettivi , , , , ` quella bivalente. Dune que, intuitivamente, una L -tautologia ` una formula modale che ` sempre e e vera in virt` della sola forma logica non modale. Per esempio, per ogni A, B: u A A, A ( B A) .

Tutte le L -tautologie risulteranno pertanto essere automaticamente leggi logiche modali. Il vero problema, che aronteremo a partire dalla prossima sezione, sar` quello di identicare le leggi logiche modali che sono genuinaa mente tali, ossia quelle formule di L che risultano sempre vere in virt` del u signicato dei connettivi e dei due operatori modali.

4


1.1.2

Linguaggi multimodali

Sia A = {a, b, c . . .} un qualsiasi insieme non vuoto, nito o innito numerabile. Il linguaggio enunciativo multimodale LA a A dimensioni e linsieme delle LA -formule sono deniti esattamente come il linguaggio monomodale L e linsieme delle L -formule, tranne che al posto di , abbiamo, per ogni a A, una coppia a , a di operatori modali4 . Tutte le nozioni sopra introdotte relativamente a L (sostituzione, formula duale ecc.) si lasciano trasferire nel modo ovvio ai linguaggi multimodali. Per aiutare lintuizione, si pensi p. es. agli elementi di A come agenti, oppure come azioni, oppure come programmi (non necessariamente deterministici). Possibili letture alternative di a (dualmente per a ) sono allora: lagente a sa / crede che A , a seguito dellazione a ` vero che A , e A vale al termine dellesecuzione del programma a . Oppure, ad esempio, possiamo prendere un A con due soli elementi, diciamo 1 e 2, e leggere 1 come necessit` logica e 2 come necessit` sica ( 2 A = a a A vale in conseguenza delle leggi della sica).

1.2

Semantica di Kripke per i linguaggi enunciativi modali

Iniziamo lesposizione dei concetti fondamentali della semantica a modi possibili. Denizione 1.2.1 (Cornice modale). Una cornice modale (ingl.: frame) ` e una struttura F = W, R dove: W ` un insieme non vuoto, e R ` una relazione binaria su W . e Attenzione! In base alla denizione, su R non c` alcuna ipotesi: pu` ese o sere p. es. riessiva come non riessiva, transitiva come non transitiva, ecc. Quando vorremo cornici in cui R soddisfa una o pi` determinate propriet` u a lo diremo esplicitamente.4

Talora risulta conveniente scrivere [a] e a invece di

a

e a .

1.2. SEMANTICA DI KRIPKE PER I LINGUAGGI ENUNCIATIVI MODALI5 Terminologia e rappresentazione graca delle cornici. Linsieme W ` chiamato di solito insieme dei mondi possibili , o pi` e u brevemente mondi (Worlds), della cornice F. Useremo di preferenza le lettere i, j, . . . , x, y . . . per denotare mondi. La relazione R ` detta di solito relazione di accessibilit` tra mondi e a (accessibility, alternativeness relation) della cornice F. Scriveremo iRj invece di R(i, j) per esprimere che la relazione R intercorre tra il mondo i e il mondo j. Possibili letture: j ` accessibile da i , e j ` unalternativa possibile per i , e i vede j / j ` visto da i . e Si osservi che questa terminologia non ` neutrale, nel senso che si attaglia e bene solo alla lettura aletica delle modalit`. Nella lettura temporale, per a esempio, si preferisce parlare di istanti o momenti invece che di mondi, e di successivo a invece che accessibile da. Nella lettura dinamica gli elementi di W si chiamano stati (di un sistema, di un computer, . . . ) e la relazione R si chiama relazione di transizione. E cos` via. Chi non si vuole compromettere pu` adottare una terminologia pi` astratta e asettica o u (i) chiamando F grafo orientato (matematicamente una cornice modale non ` altro che questo) e vertici (punti , nodi ) gli elementi di W , e (ii) e leggendo iRj semplicemente come i freccia j. Anche se in base alla denizione data niente vieta che linsieme W sia innito, qui di solito avremo a che fare con cornici nite e in tal caso le disegneremo cos` : 5

2

3

4

1 Vediamo le convenzioni grache adottate: Un mondo viene rappresentato con un cerchietto; siccome capita di doversi riferire a questo o quel mondo, a ciascun mondo diamo un nome (usiamo di solito i numeri naturali), riportato dentro il cerchietto.

6

CAPITOLO 1. LA SEMANTICA DI KRIPKE Per indicare che il mondo n vede il mondo m (ossia che vale nRm) scriviamo una freccia che va dal primo al secondo e se n e m sono mondi diversi che si vedono reciprocamente (ossia valgono tanto nRm quanto mRn) scriviamo una doppia freccia tra i due nellesempio ` il caso dei mondi 1 e 3. e Poich in generale non ` detto che R sia riessiva, per indicare che un e e certo mondo n vede se stesso (nRn) conveniamo, invece che mettere una freccia da n a n (sarebbe un po pesante), di scrivere: m m per indicare un mondo m riessivo, ossia tale che mRm , e per indicare un mondo m che non vede se stesso.

Si noti bene: visto che non ` detto che R sia transitiva, la presenza di una e freccia da n a m e di una da m a k non implica che n veda k: se vogliamo dire che anche n vede k ci vuole lapposita freccia. Nellesempio: 1R2 e 2R5 ma non 1R5 , Si noti inne: nellesempio, il mondo 5 non vede alcun mondo, incluso se stesso. Un mondo siatto, ossia un i tale che j W (iRj), si chiama un punto morto (dead end ); la particolarit` dellesempio non deve far supporre n che in una cora e nice ci debba essere per forza un mondo (come 1, nel nostro caso) dal quale tutti gli altri siano raggiungibili con una o pi` R-transizioni, n u e che non ci possano essere mondi isolati, mondi cio` che n vedono n e e e sono visti da altri mondi, tranne al massimo se stessi. Quelli che seguono sono, a tutti gli eetti, quattro esempi di cornici: 3 4 5 mentre 1R3 e 3R4 e anche 1R4 .

1

1

1

2

1

2

Esercizio 1.2.2. Fare semplici esempi di cornici modali la cui relazione di accessibilit` R ha/non ha una o pi` delle seguenti propriet`: riessivit`, a u a a irriessivit`, simmetria, antisimmetria, transitivit`, intransitivit`. a a a Per avere un modello di Kripke per il linguaggio proposizionale modale L (diremo in breve un modello modale o anche, semplicemente, un modello) basta ora prendere una cornice F = W, R e aggiungere uninformazione precisa circa lo stato di verit` di ciascun atomo p relativamente a ciascun a mondo di W .

1.2. SEMANTICA DI KRIPKE PER I LINGUAGGI ENUNCIATIVI MODALI7 Denizione 1.2.3 (Valutazione e modello modale). Sia F = W, R una cornice. Una valutazione v su F ` una funzione e v : W AT {0, 1} che associa a ciascun un mondo i W e ciascun atomo p del linguaggio un valore di verit` v(i, p) {0, 1} (1 = vero, 0 = falso)5 . a Un modello modale M ` una tripla W, R, v dove F = W, R ` una e e cornice e v ` una valutazione su F . Si dice che M ` basato su F . e e Quando un modello M = W, R, v ` nito ` di solito facile rappresene e tarlo gracamente. Basta disegnare la cornice e poi indicare solo la parte positiva di v scrivendo, accanto a ciascun mondo i, gli atomi che l` sono veri ossia quei p (se ce ne sono) tali che v(i, p) = 1. Per fare un esempio: 5 p

2 q

3

4 p, r

1 p Decodica: ciascun atomo diverso da p, q, r ` falso ovunque; p ` vero solo ai e e mondi 1, 4 e 5; r ` vero solo al mondo 4; ecc. e Siamo interessati a denire la nozione di verit` di una formula A a un a mondo i di un modello M, cosa che scriveremo cos` : M, i A 6.

Se A ` atomica non ci sono problemi: la valutazione v di M ci fornisce gi` e a linformazione. Si tratta allora di estendere questa informazione anche alle formule complesse individuando le opportune clausole induttive. E lidea guida ` quella che ci si aspetta: usare le tavole di verit` classiche per le e a formule composte con un connettivo verofunzionale e lintuizione leibniziana (corretta dalla presenza della relazione di accessibilit`) per le formule che a cominciano con o : B (B) ` vera al mondo i quando B ` vera in tutte le e e (in almeno una delle) alternative possibili per i. Ecco dunque la denizione si noti che scriviamo M, i A per non(M, i A) (lettura: A non ` e vera / ` falsa al mondo i di M): eEquivalentemente, si pu` denire una valutazione v come una funzione unaria che a o ciascun atomo p associa un sottinsieme v(p) di W , e poi porre v(i, p) = 1 se i v(p), e v(i, p) = 0 altrimenti. 6 Notare bene luso del simbolo invece di |= per esprimere la verit` a un mondo. a5

8


Denizione 1.2.4 (verit` a un mondo di un modello). La relazione ternaria a che intercorre tra un modello M = W, R, v , un mondo i di W e una formula A quando la formula A ` vera al mondo i in M, in simboli M, i A , e ` denita per induzione sulla costruzione della formula A come segue: e (i) M, i (ii) M, i (iii) M, i (iv) M, i (v) M, i (vi) M, i (vii) M, i p B sse sse v(i, p) = 1, M, i M, i M, i M, i B, B e M, i C, C, C, B) , B. dove p ` una variabile proposizionale , e

BC BC BC B B

sse sse sse

B oppure M, i B oppure M, i

sse sse

per ogni j W (se iRj allora M, j esiste un j W tale che iRj e M, j

Quando dal contesto sar` chiaro a quale M ci riferiamo, scriveremo a brevemente i A per M, i A. Osservazioni importanti e convenzioni 1.2.5. 1. Notare bene che, in base alle clausole (vi) e (vii), si ha: M, i M, i B sse esiste un j W (iRj e M, j B) ; B) .

B sse per ogni j W (se iRj allora M, j

2. Se i ` un punto morto (ossia, ricordiamo, non vede n se stesso n altri e e e mondi) allora valgono automaticamente, per B qualsiasi: M, i B e M, i B .

Il motivo di questo comportamento apparentemente strano dei punti morti ` semplice: la condizione j(iRj implica . . .) ` sempre vacuae e mente soddisfatta da un tale i (lantecedente ` falso per qualsiasi j !), e mentre la condizione duale j(iRj e . . .) ` sempre vacuamente non e soddisfatta da un tale i (il primo membro della congiunzione ` falso e per qualsiasi j !). 3. Le clausole relative ai connettivi verofunzionali sono locali : non si esce dal mondo al quale stiamo valutando la data formula B C, B C ecc. Quelle relative agli operatori modali invece non lo sono: per valutare B a i si deve uscire da i, e analogamente per valutare B. Non sono tuttavia neppure globali in senso forte: il valere o meno di M, i B (e analogamente per M, i B) non dipende proprio da tutto ci` che accade in qualunque altro mondo, ma solo da ci` che o o accade in i, nei mondi visti da i, nei mondi visti da questi mondi e cos` via (v. la precisazione di questa idea nellEsercizio 1.2.9).

1.2. SEMANTICA DI KRIPKE PER I LINGUAGGI ENUNCIATIVI MODALI9 4. Se ` un insieme di formule, scriviamo e M, i

brevemente per M, i A per ogni A . Di conseguenza M, i vuol dire che c` una formula A tale che M, i A. e Esempio 1.2.6. Sia M il modello disegnato a pagina 7. Valgono:

3 p : infatti gli unici mondi che 3 vede sono 1 e 4 (attenzione: 3R3 non vale: cerchietto tratteggiato!) e ad entrambi ` vero p ; e 3 p p : questo segue da quanto sopra e da 3 di verit` del condizionale ; a p per la clausola

3 ( p p) : infatti 4 ppe1 p p perch sia in 4 che e in 1 p ` vero, e daltra parte 3 vede solo 4 e 1 ; e 1 1 ( p p) : infatti 1 vede 3 e, come sappiamo, 3 ( p p) : infatti 1 vede 4 e, come gi` vericato, 4 a p p; p p;

2 (p q) : infatti 2 vede solo se stesso (cerchietto non tratteggiato = punto riessivo!) e 5; ma in 2 vale p, dunque anche p q, mentre in 5 vale q e dunque anche p q ; i s per qualunque mondo i e atomo s diverso da p, q, r : infatti un tale atomo ` falso ovunque nel nostro modello; e Esercizio 1.2.7. Sempre con riferimento al modello precedente, vericare: (a) 1 (c) 1 (e) 2 (g) 1 (i) 3 (m) 5 (n) i p, p, p, p, q , (b) 3 (d) 1 (f) 2 (h) 3 (l) 4 p (sebbene 3 p, p, (r q) , q , (r p)) (attenzione!), p),

((p (q r))

A A per ogni A e ogni i {1, 2, 3, 4, 5} (attenzione!).

Esercizio 1.2.8. Per ogni formula modale A sia strip(A) la formula di Lp che si ottiene da A eliminando tutte le occorrenze degli operatori modali (se ne pu` dare una ovvia denizione induttiva: provare). Si consideri un o qualsiasi modello M basato su una cornice che consta di un unico mondo, diciamo 1, e tale che 1R1. Vericare che per ogni formula A : M, 1 A M, 1 strip(A) .

Trovare poi un modello (piccolo !) nel quale quanto sopra non vale.

10


Esercizio 1.2.9. Si ricordi (v. ??) che la n-esima potenza peirceana R[n] (n 0) di una relazione binaria R ` quella relazione che intercorre tra un e i e un j quando si arriva da i a j con esattamente n transizioni di tipo R (dunque in particolare R[0] coincide con lidentit` e R[1] coincide con R). a 1. Vericare che in ogni modello: M, i M, inA

sse j(iR[n] j M, j

A)7 , A) .

n A sse j(iR[n] j M, j

2. Dato un modello M = W, R, v e un i W , sia Mi il modello W i , Ri , v i dove: W i := {x W | n 0 (iR[n] x)} , Ri e v i sono le restrizioni di R, risp. di v, a W i . Ovviamente W i W . Vericare che per ogni x W i e ogni A vale: Mi , x A sse M, x A.

Il modello Mi si chiama troncamento di M a i . Sia M un modello modale. Come anche si vede dagli esempi fatti, pu` o benissimo accadere che una formula A sia vera a un certo mondo i di M e falsa a un altro. Ma ci sono anche formule A che sono vere a ogni mondo del modello (ad esempio s nel modello dellEsempio 1.2.6): una tale formula la diciamo vera in M, in simboli |=M A. Ora, un modello ha due componenti: la cornice F su cui ` basato e la e valutazione v. Se teniamo ferma la prima e facciamo variare la seconda, ottenendo cos` un modello M via via diverso ma strutturalmente simile al primo, ` ovvio aspettarsi che alcune formule vere in M diventino non vere e in M , e viceversa. Diremo che una formula A ` valida in una cornice F, in e simboli |=F A , quando questo non accade, ossia quando A ` vera in tutti i e modelli basati su F. Intuitivamente: A vale indipendentemente dai valori di verit` delle sue componenti atomiche, ma dipendentemente dalla struttura a dellinsieme dei mondi possibili, cio` dalla cornice modale scelta. e Di nuovo (lo vedremo), la nozione di validit` in una cornice non ` stabile: a e ci sono formule valide in una cornice e non valide in unaltra. Ma ci sono anche formule (per il momento, sicuramente le Lp -tautologie perch?) che e sono valide in tutte le cornici ossia, equivalentemente, vere in tutti i modelli : le chiamiamo verit` (leggi ) logiche modali minimali, o formule K-valide (o a ancora: leggi della logica K), e per dire che A ` fra queste scriviamo anche eAttenzione! Qui e e subito sotto e sono usati metalinguisticamente. Si tratta di un abuso notazionale conveniente (che faremo spesso anche in seguito) ma non pericoloso, perch` risulter` sempre chiaro dal contesto duso a quale livello e a (linguistico / metalinguistico) siamo.7

1.2. SEMANTICA DI KRIPKE PER I LINGUAGGI ENUNCIATIVI MODALI11 |=K A (o A K). Una verit` logica modale minimale `, intuitivamente, una a e formula vera indipendentemente dal suo contenuto come pure da ogni ipotesi ` sul sistema dei mondi possibili. E giunto il momento di fare i primi esempi genuini di legge logica modale di tipo minimale (tanti altri ne vedremo nella sezione seguente). Esempio 1.2.10. Per ogni A : |=K (A B) ( A B). Per dimostrarlo, bisogna far vedere che per un arbitrario M = W, R, v , un arbitrario mondo i W e una A qualsiasi vale: (1.2.1) (1.2.2) segue (1.2.3) M, i B ossia: per ogni j W , se iRj allora M, j B. Sia dunque j un mondo tale che iRj. Per (1.2.2) e la clausola di verit` a a un mondo relativa alle formule che iniziano con segue che M, j A B e che M, j A. Ma allora (clausola del condizionale!) M, j B, come volevamo. Osservazione 1.2.11. Quanto sopra provato pu` anche essere espresso cos` o : lo schema (A B) ( A B) ` K-valido. e Uno schema, ricordiamo, rappresenta una collezione di formule aventi tutte la stessa forma logica. Dire di un certo schema che ` valido (pi` in generale: e u che ha una certa propriet`) equivale a dire che ogni sua istanza (cio` ogni a e formula che ha la forma esibita dallo schema) ` valida (ha quella propriet`). e a Quindi, si noti bene (perch` dora in avanti ci esprimeremo spesso in termini e di schemi): dire che un certo schema non ` valido (non ha P) signica che e c` almeno una sua istanza che non ` valida (che non ha P). e e Per comodit`, alcuni schemi rilevanti sono contrassegnati da una sigla. Quela lo dellEsempio 1.2.10 che esprime la distributivit` di a sul condizionale ` chiamato K. e Esempio 1.2.12. I seguenti due schemi sono K-validi: I A A , I A A (leggi di interdenibilit` a / ). Infatti, in base alle clausole della Denizione 1.2.4, si ha che per ogni modello M = W, R, v e ciascun mondo i W i A per ogni j W (se iRj allora j non esiste j W (iRj e non j non esiste j W (iRj e j non i i A A , A) A) A) M, i (i) M, i (A B) ( A (A B) B) A ossia, in base alla clausola di verit` di un condizionale, che dalle assunzioni a (ii) M, i

12


il che implica che M, i A A. Per laltro schema (N.B.: sono luno il duale dellaltro; v. Denizione 1.1.2) si ragiona analogamente. Per motivi che diverranno presto chiari, risulta importante anche domandarsi quali formule, pur non essendo valide in tutte le cornici, sono per` o valide in tutte le cornici la cui relazione di accessibilit` R gode di una certa a propriet` P, p. es. riessivit`, simmetria, ecc. (per brevit` parleremo di a a a cornici riessive, cornici simmetriche ecc.). Anche qui ` bene fare subito e un esempio (la questione sar` arontata pi` sistematicamente nella sezione a u 1.4). Esempio 1.2.13. Lo schema T A A non ` K-valido, per` ` valido e oe in ogni cornice riessiva. Qui si fanno due aermazioni. Per vericare la prima, si consideri il seguente modello M0 : 2 p 1 M0 , 1 p perch lunico mondo che 1 vede ` 2 (1 non vede se stesso!) dove e e p ` vero per costruzione; daltra parte, sempre per costruzione, M0 , 1 p . e Si conclude che M0 , 1 p p e dunque che p p che ` unistanza e di T non ` una legge logica minimale. e Sia ora invece M = W, R, v un qualsiasi modello nel quale la relazione di accessibilit` R ` riessiva (diremo anche: un modello riessivo; si noti che a e il modello M0 appena visto non lo `!). Se i W e M, i e A (A formula qualsiasi) allora abbiamo per denizione di : () M, j A per ogni j che i vede.

Ma dallipotesi che R ` riessiva segue in particolare che i vede i e dunque, e per (), che M, i A. Ergo: M, i A A. Ma i ` arbitrario, quindi e |=M A A per ogni M riessivo, come volevamo. Lasciamo per esercizio la analoga verica del fatto che anche lo schema duale di T (a necesse ad esse ), e cio` Td A A (ab esse ad posse) non e ` vero in tutti i modelli ma ` valido in tutte le cornici riessive. e e Osservazione 1.2.14. Lo schema T (e quindi anche T d ) ` chiaramente e accettabile nella lettura aletica delle modalit` come pure in quella epistemica a (tutto ci` che ` conosciuto ` vero8 ). Non lo ` invece n in quella doxastica o e e e e (si possono benissimo credere proposizioni false!) n in quella deontica (non e tutti i mondi sono deonticamente perfetti: nel mondo attuale accade spesso che gli obblighi non vengano rispettati).8 Si ricordi la caratterizzazione della conoscenza come credenza vera e giusticata, di origine platonica.

1.2. SEMANTICA DI KRIPKE PER I LINGUAGGI ENUNCIATIVI MODALI13 In generale, se C ` una classe non vuota di cornici, diciamo che una e formula A ` una legge logica modale di tipo C quando A ` valida in ogni e e cornice F che appartiene alla classe C. Cos` in particolare, legge logica , modale minimale = legge logica modale di tipo K , dove con K conveniamo di indicare la classe di tutte le cornici. Per riassumere i fondamentali concetti n qui introdotti: Denizione 1.2.15. 1. |=M A sse M, i A per ogni i W (A vera nel modello M)

2. |=F A sse |=M A per ogni M basato su F (A valida nella cornice F) 3. |=C A sse |=F A per ogni cornice F C (A valida nella classe C). Osservazioni importanti e convenzioni 1.2.16. 1. Per andare aventi senza problemi, si tenga sempre ben presente la catena di equivalenze (I) A legge modale minimale A valida in tutte le cornici A vera in tutti i modelli A vera a ogni mondo di ogni modello e la sua versione relativizzata (II) A legge modale di tipo C A valida in tutte le cornici in C A vera in tutti i modelli basati su una cornice in C A vera a ogni mondo di ogni modello basato su una cornice in C. 2. Si faccia la massima attenzione: mentre M, i A, la negazione di M, i A , equivale a M, i A , non ` per niente vero che M A , e cio` la negazione di |=M A , equivale a |=M A. La prima dice che e A ` vera a ogni mondo di M, la seconda dice che A ` vera a ogni e e mondo di M ossia, equivalentemente, che A non ` vera (` falsa) a ogni e e mondo di M. Lo stesso dicasi per il rapporto tra F A e F A e per quello tra C A e C A . 3. Se C ` una classe di cornici, deniamo e Log(C) := {A | |=C A} . Log(C) sta per logica (o: insieme delle leggi logiche) di (tipo) C. Ovviamente, |=C A , A Log(C) e A ` C-valida e

14

CAPITOLO 1. LA SEMANTICA DI KRIPKE sono tre modi diversi per dire la stessa cosa. Ricordando che K := Log(K) abbiamo cos` per quanto visto negli , Esempi 1.2.10 e 1.2.12, K , I , I K , mentre per lo schema T e il suo duale T d abbiamo: T , Td K / e T , Td Log(Rf)

dove Rf denota la classe delle cornici riessive. Convenzione: se F ` una cornice, Log(F) sta per Log({F}). e 4. Se C, D sono due classi di cornici e C D, allora se A ` valida in e ogni cornice appartenente a D lo ` a maggior ragione in ogni cornice e appartenente a C. Dunque valgono: C D Log(D) Log(C) e ovviamente anche: F C Log(C) Log(F) .

5. Qualcuno avr` notato che mentre abbiamo denito la nozione di verit` a a logica modale (di tipo K, cio` minimale, e poi in generale di tipo C), e non abbiamo denito le corrispondenti nozioni di conseguenza logica modale. Il motivo principale ` che in quanto segue ci concentreremo e solo sul problema della classicazione e poi dellassiomatizzazione dei vari tipi di leggi logiche modali. Un secondo motivo ` che nella see mantica di Kripke ci sono in realt` due diverse nozioni di conseguenza a logica che vanno prese in considerazione, e quindi avremmo dovuto per forza complicare un po le cose (v. 1.5.2). Esercizio 1.2.17. Con riferimento a quanto visto nellEsercizio 1.2.8, dimostrare che Log(1) = {A | strip(A) TAUT} , e dove 1 ` la cornice 1 (un solo mondo, e riessivo) e TAUT ` linsieme delle e Lp -tautologie. Esercizio 1.2.18 (p-epimorsmi). Siano F = W, R e F = W , R due cornici modali. Una funzione f : W W che soddisfa le condizioni: f ` suriettiva e xy W (xRy f (x)R f (y)) x W y W (f (x)R y y W (xRy f (y) = y ))

1.2. SEMANTICA DI KRIPKE PER I LINGUAGGI ENUNCIATIVI MODALI15 ` detta essere un p-epimorsmo di F su F , in simboli f : F p F . Provare e a fare qualche esempio signicativo di p-epimorsmo (alcuni ne vedremo pi` u avanti) e dimostrare che f (f : F p F ) Log(F) Log(F ) .

Suggerimento: Dato un p-morsmo f di F su F e un arbitrario modello M = W , R , v basato su F si denisca la valutazione v su F ponendo v(i, p) := v (f (i), p) per ogni i W e ogni atomo p. Si consideri poi il modello M = W, R, v (che ` basato su F) e si dimostri, usando le propriet` e a di f , che per ogni A e ogni i W : M, i A M , f (i) A.

Osservazione 1.2.19. Fin qui ci siamo limitati a presentare la semantica kripkeana per il linguaggio monomodale L . Se si vuole trattare un linguaggio multimodale LA a A dimensioni, i cambiamenti da fare sono davvero ` minimi e del tutto naturali. E infatti suciente: Prendere cornici A-dimensionali, cio` strutture e F = W, {Ra }aA che invece di una sola relazione di accessibilit` ne hanno tante quanti a sono gli elementi di A, ossia una per ciascuna coppia a , a (a A). Denire il concetto di modello come nella Denizione 1.2.3 salvo che la cornice ` ora A-dimensionale (la valutazione per` resta una sola!) e e o poi cambiare le clausole (vi) e (vii) della Denizione 1.2.4 in (vi) per a A : M, i M, iaB

sse sse

per ogni j W (se iRa j allora M, j esiste un j W (iRa j e M, j B) .

B) ,

(vii) per a A : a B

La denizione di tutte le restanti nozioni (verit` in un modello, validit` in a a una cornice e in una classe di cornici A-dimensionali, ecc.) resta, mutatis mutandis, invariata9 . Analogamente, tutti i concetti e i risultati della presente sezione e di quelle che seguono si lasciano naturalmente e facilmente estendere ai linguaggi multimodali (provare via via, per esercizio).9 Semmai diventa pi` complicato disegnare cornici e modelli (bisogna ovviamente u etichettare le frecce, ecc.).

16


1.3

Logica minimale K e principio di dualit` a

Dimostreremo qui innanzitutto due semplici ma importanti risultati relativi a cornici e classi di cornici qualsivoglia. Successivamente, vedremo qualche altro esempio di leggi logiche modali minimali come pure di formule che non lo sono. Lemma 1.3.1. 1. |=F Sia F = W, R una qualsiasi cornice. Per ogni A, B : B) , |=F A A , |=F A A ;

(A B) ( A

2. se A ` una Lp -tautologia allora |=F A ; e 3. se |=F A B e |=F A allora |=F B ; 4. se |=F A allora |=F A;

5. se |=F A allora |=F A per qualsiasi sostituzione ; 6. se A ` una L -tautologia allora |=F A ; e Lo stesso vale per una arbitraria classe C di cornici (al posto di F). Dimostrazione. (1): labbiamo dimostrato negli Esempi 1.2.10 e 1.2.12. (2) e (3): ovvi, perch` a ciascun mondo la semantica dei connettivi verofune zionali ` locale ed ` quella delle tavole di verit`. e e a (4): ` semplicissimo. Si assuma () |=F A. Per provare |=F A basta far e vedere che per qualunque modello M basato su F e qualunque mondo i si ha che A ` vera in M a ogni mondo che i vede. Ma per lassunzione () A e ` vera ad ogni mondo k di M, quindi in particolare a quelli che i vede. e (5) ` facile da vericare (esercizio) una volta provato il seguente lemmettino. e Siano M = W, R, v un modello e una sostituzione. Deniamo il modello M (basato sulla stessa cornice di M) come M := W, R, v , dove v (i, p) = 1, se M, i (p); 0, altrimenti.

Allora, per ogni formula A e ogni i W , vale M, i A M , i A.

La semplice dimostrazione, per induzione sulla complessit` di A, ` lasciata a e come esercizio. (6): segue da (2) e (5) per denizione di L -tautologia. Da (1)(6) e dal fatto che, per denizione, A Log(C) F C ( A Log(F) ) , segue facilmente che le stesse propriet` valgono anche per una arbitraria a classe C di cornici.

` 1.3. LOGICA MINIMALE K E PRINCIPIO DI DUALITA

17

Osservazione 1.3.2. Quindi, per ogni classe C di cornici, linsieme delle leggi logiche di tipo C : (i) contiene tutte le istanze in L delle tautologie classiche; (ii) contiene tutte le istanze dello schema K di distributivit` di a su e degli schemi di / interdenibilit`; (iii) ` chiuso sotto la regola a e del modus ponens e sotto la regola che da A fa passare a A (che pi` avanti u impareremo a chiamare regola di necessitazione); (iv) ` chiuso sotto la regola e di sostituzione (enunciativa). Si noti bene: il punto (iv) sancisce anche per il contesto logico modale ci` che gi` o a sappiamo valere per il contesto non modale: la legalit` logica ` quea e stione di forma, non di contenuto. In particolare, ci assicura che uno schema ` C-valido se e solo se ` tale una sua arbitraria istanza princie e pale, ossia unistanza in cui il posto delle lettere schematiche ` preso e da atomi (atomi diversi per lettere diverse!); il punto (iii) dice che se A ` legge logica di un tipo qualsiasi allora e anche A ` legge logica di quel tipo. Non dice che A A ` una e e 10 legge logica! Veniamo ora al secondo risultato. Abbiamo visto (Esempio 1.2.12) che lo schema A A vale in tutte le cornici, come pure il suo duale A A. Analogamente (Esempio 1.2.13), in tutte le cornici riessive valgono lo schema A A e il suo duale A A. Ebbene, non si tratta di un caso, bens` di una conseguenza di un principio generale. Teorema 1.3.3 (Principio di dualit`). Sia C una qualsiasi classe di cornici. a Per ogni A : |=C A sse |=C Ad . Dimostrazione. Ci limitiamo a dare una traccia, da completare per esercizio. Sia C qualsivoglia. Il primo passo consiste nel vericare (si tenga ben presente la Denizione 1.1.2) che per ogni formula A : (1) |=C A A .

La dimostrazione di (1) ` per induzione sulla complessit` di A e sfrutta in e a modo essenziale il Lemma 1.3.1. Da (1) segue (2) |=C A |=C Ad .

Valga infatti |=C A. Allora, per la validit` della regola di sostituzione, a Lemma 1.3.1.(5), abbiamo |=C A e, per (1), |=C A . La conclusione |=C AdIl principio A A ` chiaramente controintuitivo e indesiderabile: in particolare, e se accettato in sistemi nei quali si accetta lo schema T, provoca il cosiddetto collasso delle modalit` ossia lequivalenza logica di A con A e la conseguente banalizzazione a delloperatore .10

18


segue dalla denizione di formula duale (pi` legge della doppia negazione). u Inne, applicando (2) alla formula Ad e ricordando che Ad d coincide con A a meno di doppie negazioni (e dunque |=C Ad d A) si conclude che anche laltra direzione di (2) vale. Esploriamo ora la logica K ossia linsieme delle leggi modali di tipo K. Esempio 1.3.4. Lo schema A B (A B) ` una legge di K. e Questa volta, per cambiare, ragioniamo per assurdo (si pu` anche fare un o ragionamento diretto: provare). Se A B (A B) Log(K) allora / per certe A, B ci sono un modello M e un suo mondo i tale che M, i A B (A B) ,

ossia: (a) i A , (b) i B, (c) i (A B). Da (c) segue che c` un j tale che iRj e j e A B, quindi j A oppure j B. Ma nel primo caso siamo in contraddizione con (a) (perch da (a) e ` e iRj segue j A), e nel secondo, analogamente, con (b). E importante osservare che il ragionamento che abbiamo appena fatto altro non ` se non e la costruzione di un albero di Beth modale11 chiuso! Siamo infatti partiti ipotizzando la non validit` della formula sotto esame, e da qui abbiamo svia luppato unanalisi sistematica giusticata dalle clausole della denizione di verit` di una formula a un mondo di un modello che ci ha alla ne a condotto a un albero con due rami, entrambi chiusi (in ciascuno si asserisce e contemporaneamente si nega che una stessa formula ` vera a un certo mondo e di uno stesso modello). La conclusione ` allora che lipotesi di partenza non e sta in piedi, ossia che la formula che ci interessa ` valida. e Esempio 1.3.5. Lo schema (A B) A B ` una legge di K. e Chi vuole pu` fare la verica, ma quanto asserito segue gi`, automaticameno a te, da quanto visto nellesempio precedente in forza del Principio di dualit` a (Teorema 1.3.3). Esempio 1.3.6. Lo schema A B (A B) non ` K-valido12 . e Qui il compito ` diverso da prima, si tratta di trovare un contromodello. Rie cordando quanto detto nellOsservazione 1.3.2 circa la validit` / non validit` a a di schemi, ` chiaro che dobbiamo trovare un contromodello per e p q (p q) ,11 Esiste in eetti anche una buona teoria degli alberi di Beth per la logica modale. Purtroppo non possiamo soermarci su di essa, ma i ragionamenti fatti in questo e nel successivo esercizio dovrebbero bastare a capire intuitivamente come tali alberi modali funzionano, almeno nel caso della logica modale minimale. 12 Almeno nella lettura aletica ` intuitivamente chiaro si tratta di un principio non e accettabile: fare qualche controesempio nel linguaggio naturale.

` 1.3. LOGICA MINIMALE K E PRINCIPIO DI DUALITA

19

ossia un qualche M tale che per un qualche suo mondo, che chiameremo 1: (1.3.1) M, 1 p q (p q) .

Per trovarlo (se c`; in questo caso c`!) ragioneremo, analogamente a quanto e e fatto nellEsempio 1.3.4, come se si stesse costruendo un albero di Beth modale a partire da (1.3.1). La dierenza ` che al termine dellanalisi ci troveree mo con (almeno) un ramo aperto, dal quale si pu` estrarre il contromodello o cercato. Allora: sulla base di (1.3.1) deve accadere che (a) 1 p , (b) 1 q , (c) 1 (p q) .

Per (a) e (b) ci devono essere due mondi distinti 2 e 3 (non c` motivo per e cui debbano essere lo stesso mondo; ragionamento per esposizione! ) tali che (d) 1R2 , 2 p, (e) 1R3 , 3 q.

Per (c), daltra parte (esemplicazione! ), a ogni mondo che 1 vede o non ` e vera p o non ` vera q. Allora per (d) ed (e) devono valere, rispettivamente: e (f) M, 2 q, (g) M, 3 p.

Lanalisi ` conclusa: siamo in contraddizione? No: le informazioni atomie che cui siamo arrivati, ossia (d)(g), sono compatibili (corrispondono a un ramo aperto dellalbero) e ci dicono come M ` fatto. Precisamente: la cornie ce di M ha solo tre mondi (1, 2, 3) e la relazione R di accessibilit` intercorre a solo tra 1 e 2 e tra 1 e 3 (quindi nessun mondo vede se stesso). Quanto alla valutazione v di M, questa ` tale che p ` vero solo al mondo 2, q ` vero solo e e e al mondo 3 e ogni altro atomo ` falso ovunque. e Non ci resta allora che disegnare il nostro M: 2 p 1 Chi non ` convinto che davvero M soddisfa (1.3.1) pu` fare la verica. e o N.B.: ovviamente, quello trovato non ` lunico contromodello. P. es., anche e se rendiamo riessivi tutti e tre i punti del nostro M, il risultato non cambia (verica per esercizio). Esercizio 1.3.7. Applicando il principio di dualit`, concludere dallesempio a precedente che (A B) A B non ` una legge minimale. e Esercizio 1.3.8. Vericare che sono leggi minimali gli schemi: (1) (3) (5) A B (A B) (A B) A B (2) (A B) A B (4) (A B) A B ( A A) (6) A B (A B) (8) ( A A) A B (A B) 3 q

(7) A

20


Esercizio 1.3.9. Vericare che per qualsiasi cornice F : |=F A B |=F A B e |=F A B .

Concludere che linsieme delle leggi di tipo C, per C una classe qualsiasi di cornici, ` chiuso sotto le regole: e AB A BD-

AB A B

D-

.

Esercizio 1.3.10. Provare che nessuna delle seguenti ` una legge di K. In e certi casi si deve esibire lopportuno contromodello (utilizzare, per trovarlo, il metodo dellEsempio 1.3.6); in altri basta applicare il principio di dualit` a a formule che gi` si sa non essere leggi. a (1) (3) (A B) (A B) (5) (6) (7) (9) A A A A A A A A (2) A A A) B

(4) A (7) A

(6) A A (8) (A (10)

(A B) A

Esercizio 1.3.11. Sebbene T A A non sia una legge di K, vale che se A ` una legge di K allora anche A lo ` (chiusura sotto la regola di e e denecessitazione). Dimostrarlo. [Suggerimento:] usare la costruzione dellEsercizio 1.2.9. Esercizio 1.3.12. Dimostrare (con metodi analoghi a quelli del precedente esercizio) che per ogni A, B vale: A B K sse A K oppure B K.

Si tratta della cosiddetta propriet` di primalit` modale. a a

1.4

Altri tipi signicativi di leggi modali

Grazie allEsempio 1.2.13 sappiamo che nelle cornici riessive ` valido lo e schema A A (T), che per` non ` K-valido. In realt` si pu` dimostrare o e a o qualcosa di pi` forte: T vale in tutte e sole le cornici riessive. u Lemma 1.4.1. Se A A Log(F) per ogni A, allora F ` riessiva. e

Dimostrazione. Proviamo il contrapposto. Se F = W, R non ` riessiva ale lora ci devessere almeno un mondo di W che non vede se stesso. Fissiamone uno: i0 W e i0 Ri0 . Deniamo ora una valutazione v su F ponendo, per ogni atomo p : 1, se i = i0 e p p0 ; v(i, p) = 0, altrimenti.

1.4. ALTRI TIPI SIGNIFICATIVI DI LEGGI MODALI

21

Consideriamo il modello M := W, R, v basato su F. Se i0 Rj allora j = i0 (i0 non vede se stesso!) e quindi, per denizione di v, M, j p0 . Ma allora M, i0 p0 e daltra parte, sempre per denizione di v, M, i0 p0 : segue che p0 p0 ` falso nel modello M e, a seguire, che p0 p0 e / Log(F). ` E questo un primo esempio della cosiddetta corrispondenza modale: Denizione 1.4.2. Uno schema modale X e una propriet` P di relazioni a binarie si corrispondono modalmente quando per ogni cornice F = W, R vale: X Log(F) R ha la propriet` P . a A volte, diremo anche che X e P si corrispondono, dove P ` la classe delle e cornici la cui relazione di accesibilit` ha la propriet` P. Segue dalla dea a nizione che se X e P si corrispondono allora X Log(P). Notare inoltre che, per il Principio di dualit`, la corrispondenza13 X P comporta anche a la corrispondenza X d P, e viceversa, dove X d ` lo schema duale di X. e

1.4.1

Le logiche D, T, B, K4, S4, S5

Le pi` note fra le corrispondenze modali sono racchiuse nel u Teorema 1.4.3. Schema T: 4: D: AA A A A A A A Sch. Duale A A A A A A A A A A ` Proprieta corrispondente di R Riessivit`: x(xRx) a Transitivit`: xyz(xRy yRz xRz) a Serialit`: xy(xRy) a Simmetria: xy(xRy yRx) Euclideicit`: xyz(xRy xRz yRz) a

B: A E : A

Dimostrazione. (T) : vedi Esempio 1.2.13 e Lemma 1.4.1. (4) : sia M un modello basato su una cornice transitiva, e per assurdo esistano un mondo i di M e una formula A tali che i A A, ossia i A e i A. Dunque c` un j tale che iRj e j e A e quindi anche un k tale che jRk e k A. Per transitivit` segue iRk e dunque a i A : contraddizione. Per provare laltra direzione, prendiamo una qualsiasi cornice F = W, R non transitiva e ssiamo (ci devono essere perSi noti che, in forza del punto (5) del Lemma 1.3.1, avremmo potuto denire equivalentemente il concetto di corrispondenza con riferimento a formule invece che a schemi modali. Infatti uno schema X corrisponde a P se e solo se unistanza principale di X corrisponde a P.13

22


forza) tre mondi x, y, z tali che xRy e yRz ma non xRz. Sia v la valutazione su F tale che per ogni i W e ogni atomo p : v(i, p) = 1 sse xRi e p p0 .

Allora, nel modello M = W, R, v basato su F si ha, per denizione di v: M, x p0 , ma M, y p0 perch yRz e z e p0 in quanto (xRz).

Segue che M, x p0 e quindi che M p0 p0 : c` dunque e unistanza dello schema 4 che non ` valida nella cornice non transitiva F. e (D, B, E) : A questo punto, lasciamo per esercizio la facile verica del fatto che i restanti schemi D, B e E sono validi, rispettivamente, in ogni cornice seriale, in ogni cornice simmetrica e in ogni cornice euclidea. Per quanto riguarda laltro verso della corrispondenza (quegli schemi sono validi solo in quel tipo di cornici), indichiamo la strada lasciando la verica dei dettagli per esercizio. Se F = W, R ` una cornice non seriale, allora c` almeno un mondo x e e che ` un punto morto (y W (xRy)). Segue allora immediatamente e dallOsservazione 1.2.5 che se M ` un qualsiasi modello basato su tale cornice e si ha M, x A A, per A arbitraria. Se F = W, R non ` simmetrica, possiamo ssare due mondi x, y tali che e xRy ma non yRx. Si consideri una valutazione v su F che rende vero latomo p0 al solo mondo x, e si verichi che nel modello M risultante M, x p0 p0 . Se F = W, R non ` euclidea, possiamo ssare tre mondi x, y, z tali che e xRy, xRz ma non yRz. Si consideri una valutazione v su F che rende vero latomo p0 al solo mondo z, e si verichi che nel modello M risultante M, x p0 p0 . Osservazione 1.4.4. Tutti e cinque gli schemi D, T, B, 4, E risultano intuitivamente validi nella lettura aletica delle modalit`. Nella lettura epistemia ca lo schema 4 esprime un principio di introspezione positiva (sapere che A comporta il sapere di sapere che A) mentre E esprime un principio di introspezione negativa (prendendo B per A e applicando le leggi di interdenibilit` si ottiene infatti B B : non sapere che B comporta il a sapere di non sapere che B). Lo schema D, a dierenza di T, ` invece cae ratteristico della lettura deontica: esprime infatti che ci` che ` obbligatorio o e ` anche lecito. e Indichiamo dora in avanti con Rf (risp. Ser, Sim, Tr, Eucl) la classe di tutte le cornici in cui R ` riessiva (risp. seriale, simmetrica, transitiva, e euclidea), con RfTr la classe di tutte le cornici in cui R ` sia riessiva che e transitiva, e cos` via per le altre combinazioni. Con Equiv indichiamo inne la classe di tutte le cornici in cui R ` una relazione di equivalenza, ossia ` e e riessiva, simmetrica e transitiva. Non ` dicile vericare (esercizio) che R e


23

` una relazione di equivalenza se e solo se ` riessiva e euclidea. Pertanto, e e abbiamo: Equiv RfSimTr RfEucl . Sulla base delle corrispondenze del Teorema 1.4.3 si possono ora denire svariati concetti alternativi di legge modale una variet` cio` di logiche a e modali che estendono K sostituendo alla classe K di tutte le cornici (che caratterizza la logica modale minimale) volta volta una sottoclasse C di K determinata da una delle cinque propriet` di riessivit`, serialit`, transia a a tivit`, simmetria, euclideicit` o da unopportuna combinazione di queste. a a Per varie ragioni in primo luogo di rispondenza a speciche letture degli operatori modali, e poi anche di tipo storico si considerano di solito almeno le sei logiche seguenti: Denizione 1.4.5. T D K4 B S4 S5 := := := := := := Log(Rf) Log(Ser) Log(Tr) Log(RfSim) Log(RfTr) Log(Equiv) (dunque (dunque (dunque (dunque (dunque (dunque T T); D D); 4 K4); T, B B); T, 4 S4); T, 4, B, E S5).

I relativi rapporti di inclusione sono completamente descritti dal Diagramma 1.4.6. Una freccia da L a L indica linclusione propria di L in L : ogni legge di L ` una legge di L , ma ci sono leggi di L che non sono e leggi di L. K4 K D T B S4 S5

Esercizio 1.4.7. Dimostrare che il diagramma ` fedele, ossia che indica tutti e e soli i rapporti di inclusione tra le sette logiche in esame. Suggerimento: Per provare che una logica Log(C) ` inclusa () in unaltra e logica Log(D) basta vericare (cf. il punto 4 dellOsservazione 1.2.16) che D C. P. es.: dal fatto che un mondo x vede se stesso segue logicamente che c` almeno un mondo che x vede; dunque ogni cornice riessiva ` seriale, e e e perci` D = Log(Ser) Log(Rf) = T. o Per provare invece che Log(C) Log(D), nel nostro caso specico (attenzione: non in generale!) ` suciente grazie alle corrispondenze del Teorema e 1.4.3 trovare una cornice F D C . In tal caso, infatti, si ha che se X ` lo schema caratteristico di una delle propriet` che caratterizzano C e che e a F non ha allora X Log(C) ma X Log(F) e quindi anche X Log(D) / /

24


in quanto F D. Un solo esempio. La cornice F = {0, 1, 2}, R , dove R sussiste tra due mondi qualsiasi tranne che tra 1 e 3 e tra 3 e 1, appartiene a Rf Sim ma non ` transitiva. Dunque 4 Log(RfTr) e 4 Log(RfSim), e / cosicch S4 B. e Esercizio 1.4.8. Le combinazioni possibili (non vuote) delle cinque propriet` di riessivit`, serialit`, transitivit`, simmetria, euclideicit` sono in a a a a a tutto 25 1 = 31, ma non danno luogo ad altrettante classi distinte di cornici; per esempio SerSimTr RfEucl (provare che una relazione seriale, transitiva e simmetrica ` anche riessiva). Identicare tutte le classi di e cornici due a due distinte di questo tipo, e disegnare il diagramma delle inclusioni delle corrispondenti logiche. Esercizio 1.4.9. Ciascuno dei seguenti schemi vale in alcune, ma non in tutte, delle logiche del Diagramma 1.4.6. Determinare, caso per caso, quali: (1) (3) (5) (7) ( A B) ( B A) A A A A (2) (4) (6) A AA A A A

(8) A A

Esercizio 1.4.10. Quali, tra gli schemi dellEsercizio 1.3.10, valgono in S5? Esercizio 1.4.11. ( ( A A) legge di tipo RfTr. Vericarlo. A) ( ( A A) A) ` una e

Esercizio 1.4.12 (Modalizzatori). Chiamiamo modalizzatore un blocco nito, anche vuoto, di e (p. es.: , , , . . .). Diciamo che due modalizzatori 1 e 2 sono equivalenti in una logica modale L quando per ogni formula A : (1 A 2 A) L . Per esempio, e sono equivalenti in S4. Dimostrare che:

1. in K4 e in B (e di conseguenza in K, D e T) esistono inniti modalizzatori non equivalenti; 2. in S4 vi sono esattamente sette modalizzatori non equivalenti: , , , , , ; 3. in S5 vi sono esattamente tre modalizzatori non equivalenti: , ,

, .

Esercizio 1.4.13. Ci sono fondate ragioni per identicare nella logica S5, la pi` forte tra quelle sin qui considerate, il sistema intuitivamente pi` adeu u guato alla lettura aletica di e . Dimostrare che la semantica kripkeana per S5 si pu` drasticamente semplicare, omettendo ogni riferimento alla o


25

relazione di accessibilit`: dunque cornice = insieme non vuoto W (di mona di) e, leibnizianamente, A (A) vera al mondo i W A vera a ogni (a un qualche) mondo j W . Suggerimento: in una direzione usare lovvio fatto che la relazione totale su W ` una relazione di equivalenza; nellaltra direzione usare il metodo e introdotto nellEsercizio 1.2.9.

1.4.2

Corrispondenza modale

Concludiamo con qualche ulteriore ragguaglio sullinteressante fenomeno della corrispondenza modale, esemplicato per il momento dal Teorema 1.4.3. Vediamo, intanto, altre corrispondenze notevoli. Esercizio 1.4.14. Dimostrare (si suggerisce di rivedere il primo punto dellEsercizio 1.2.9) che per ogni l, m, n, k 0 lo schema Gl,m l n,km

A

n k

A (schema di Geach generalizzato)

corrisponde alla propriet` xyz(xR[l] y xR[n] z u(yR[m] u zR[k] u)) a della relazione R di accessibilit`. a Dando gli opportuni valori ai parametri l, m, n, k ricavare poi, come casi particolari, le cinque corrispondenze del Teorema 1.4.3 e anche le seguenti: Schema A A ` Proprieta di R Co-riessivit`: a xy(xRy x = y) Identit`: a xy(xRy x = y) Univocit` a destra: a xyz(xRy xRz y = z) Funzionalit` (totale): a A A Semidensit`: a Conuenza: x!y(xRy) xy(xRy z(xRz zRy)) xyz(xRy xRz u(yRu zRu))

A A A A A A A A

Esercizio 1.4.15. Dimostrare la corrispondenza modale tra lo schema L ( A B) ( B A)

e la propriet` xyz(xRy xRz yRz zRy) (connessione). a La logica delle cornici riessive, transitive e connesse si chiama S4.3. Vale (dimostrarlo facendo uso delloperazione di troncamento, v. Esercizio 1.2.9) che S4.3 = Log(RfTrLin) dove Lin ` la classe delle cornici che soddisfano e la propriet` di linearit` : xy(xRy yRx). Segue da questo che S4.3 ` a a e intuitivamente adeguata a una lettura temporale delloperatore ( A = ` ora vero e sempre sar` vero che A) unita allassunzione della linearit` e a a dellinsieme W degli istanti temporali. Esercizio 1.4.16. Diciamo che una cornice W, R ` noetheriana quando e non contiene R-catene innite ascendenti x0 Rx1 Rx2 R . . ..

26 (1)

CAPITOLO 1. LA SEMANTICA DI KRIPKE Dopo aver vericato che una cornice noetheriana ` sempre irriessiva e (x xRx), dimostrare la corrispondenza modale tra lo schema GL ( A A) A

e la classe delle cornici noetheriane transitive. (2) Applicando il Teorema di compattezza della logica elementare (v. ??), dimostrare che la propriet` di essere una relazione noetheriana e trana sitiva non ` elementarmente esprimibile. e La logica delle cornici noetheriane e transitive, GL (lacronimo rimanda ai nomi Gdel e Lb), ` la pi` nota delle logiche della dimostrabilit` (provability o o e u a logics), nelle quali loperatore modale viene letto come predicato formale (canonico) di dimostrabilit` in una teoria numerica elementare (tipicamente a PA). In eetti, risulta (Teorema di Solovay, 1976) che GL riesce a catturare modalmente le propriet` generali di tale predicato, e a fornire una versione a astratta dei teoremi limitativi di Gdel. o Alla luce del fenomeno della corrispondenza il linguaggio modale enunciativo (e pi` in generale quello multimodale) pu` anche essere riguardato come u o un linguaggio per parlare di (esprimere propriet` di) strutture relazionali, a come le cornici (e pi` in generale le cornici A-dimensionali), che ` alternativo u e allusuale linguaggio della logica dei predicati con identit` : laddove questo a usa le variabili individuali e eventualmente predicative, i quanticatori e lidentit`, il linguaggio modale usa le variabili enunciative e gli operatori a e . Per fare un semplice esempio: vista la corrispondenza tra lo schema 4 e la propriet` di transitivit`, la formula modale p a a p e la formula elementare xyz(xRy yRz xRz) dicono, relativamente a una struttura relazionale di tipo W, R , esattamente la stessa cosa. Linsieme delle cornici in cui p p ` valida nel senso della semantica kripkeana coincide con e linsieme dei modelli di xyz(xRy yRz xRz) nel senso della semantica tarskiana. La logica modale enunciativa `, dal punto di vista pi` naturale, e u unestensione della logica enunciativa classica; ma dal punto di vista delle considerazioni sopra svolte ` legittimo vederla anche come un frammento e della logica quanticazionale classica. E ora un breve accenno al diverso potere espressivo dei due linguaggi, quello modale e quello quanticazionale. Gi` sappiamo (Esercizio 1.4.16) a che esistono condizioni su R che sono modalmente ma non elementarmente esprimibili. Si potrebbe per` pensare che ogni propriet` elementare su R sia o a anche modalmente esprimibile. Ma cos` non `. e Esempio 1.4.17. La propriet` di irriessivit`, x(xRx), non ` modalmena a e te esprimibile, ossia non esiste alcuno schema modale che le corrisponde. La dimostrazione pi` semplice ed elegante usa la tecnica dei p-epimorsmi u (v. Esercizio 1.2.18). Si considerino infatti la cornice irriessiva N = N, S ,

1.5. CALCOLI MODALI DI TIPO ASSIOMATICO

27

dove N ` linsieme dei numeri naturali e S ` la relazione di successore immee e diato (nSm sse m = n + 1), e la cornice riessiva 1 fatta da un solo mondo, ` diciamo , che vede se stesso. E facile vericare che f : N p 1 dove f ` la funzione che manda ogni n N sullunico elemento di 1, cio` . e e Ma allora, per quanto dimostrato sui p-epimorsmi, si ha (1) Log(N) Log(1) .

Se ci fosse uno schema X che corrisponde modalmente alla propriet` di a irriessivit` allora in particolare tale X sarebbe valido in N, in quanto ira riessiva, e non sarebbe valido in 1, in quanto riessiva: ma allora, contro (1), Log(N) Log(1) . Esercizio 1.4.18. Con metodo analogo, provare che le propriet` (elementaa ri) di intransitivit` (xyz(xRy yRz xRz)), antisimmetria (xy(xRy a yRx x = y)) e asimmetria (xy(xRy yRx)) non sono modalmente esprimibili, nel senso della corrispondenza.

1.5

Calcoli modali di tipo assiomatico

Nelle precedenti sezioni abbiamo arontato lo studio delle modalit` con a strumenti esclusivamente semantici, anzi pi` esattamente con gli strumenti u della semantica a mondi possibili 14 . Abbiamo in particolare individuato una logica modale di base, K, denendola semanticamente come linsieme delle formule valide in tutte le cornici, poi abbiamo preso in considerazione vari possibili raorzamenti di K, ciascuno denito come linsieme delle formule valide in una determinata classe di cornici. Generalizzando, nel contesto della semantica di Kripke risulta del tutto naturale alla luce del Lemma 1.3.1 chiamare logica modale enunciativa un qualsiasi insieme L della forma Log(C), con C K15 . In questa sezione vogliamo accennare a una caratterizzazione alternativa, di tipo sintattico: intuitivamente, una logica modale enunciativa sar` ora a linsieme di tutte le formule che sono dimostrabili in un calcolo di tipo assiomatico 16 ottenuto estendendo un qualsiasi calcolo assiomatico valido e comSicuramente la semantica pi` naturale dal punto di vista intuitivo per i linguaggi u modali, ma non certo lunica semantica disponibile. Una semantica essenzialmente pi` u potente (ma pi` astratta e molto meno intuitiva) ` per esempio quella algebrica, nata u e prima della semantica di Kripke e basata su una opportuna generalizzazione delle algebre di Boole. 15 ` E possibile dimostrare (con tecniche piuttosto complesse) che linsieme di tutte le logiche modali enunciative non solo ` innito, ma addirittura ha la cardinalit` del continuo. e a 16 Noi non ne parleremo, ma ` bene sapere che almeno per alcune note logiche modali e esistono anche buoni calcoli di tipo analitico, in particolare sotto forma di opportune generalizzazioni del calcolo delle sequenze.14

28


pleto per la logica enuncativa classica (per esempio il calcolo C presentato nella sezione ??) con opportuni assiomi e regole di inferenza modali. Nel 1.5.1 vedremo come sono fatti i calcoli assiomatici corrispondenti (in virt` di altrettanti teoremi di adeguatezza, cio` di validit` e completezza) u e a alle sette logiche K, K4, D, T, B, S4, S5 del Diagramma 1.4.6. Nel 1.5.2 accenneremo alla dimostrazione dei teoremi di adeguatezza e alla pi` u generale questione del rapporto tra la via semantica e la via sintattica nella caratterizzazione del concetto di logica modale enunciativa.

1.5.1

I calcoli CK, CK4, CD, CT, CB, CS4, CS5

Denizione 1.5.1. Il calcolo assiomatico CK ` determinato da: e Assiomi logici: tutte le istanze in L degli undici schemi dassioma [P1.1] [P4.3] del calcolo proposizionale classico C (v. ??) e dei due schemi modali [K] (A B) ( A B)

[I] A A Regole di inferenza: la regola di separazione (modus ponens) RS e la regola di necessitazione RN: A RN . A Denizione 1.5.2. 1. Per calcolo (o sistema) modale normale intendiamo una qualsiasi estensione assiomatica CX del calcolo base CK, ossia un calcolo assiomatico che dierisce da questultimo solo per avere eventuali altri schemi dassioma (anche uninnit`) oltre a [K] e [I] (le regole dinferenza a restano dunque le due solite: RS e RN). 2. Con CK + X1 + . . . + Xn indichiamo il calcolo modale normale i cui schemi dassioma aggiuntivi sono X1 , X2 , . . . Xn . 3. Un calcolo normale CX ` detto nitamente assiomatizzato quando ` e e della forma CK + X1 + . . . + Xn per certi X1 , X2 , . . . Xn . Le nozioni di dimostrazione formale in un calcolo normale CX e di lemma logico (o teorema) di CX sono denite in modo del tutto analogo a quanto fatto relativamente al calcolo proposizionale classico C: una dimostrazione formale in CX ` una successione nita A1 , . . . , An e di L -formule ciascuna delle quali o ` istanza di uno degli schemi dase sioma di CX oppure si ottiene da formule precedenti per applicazione di una delle due regole RS e RN. A ` un lemma di CX (in simboli: A) se esiste una dimostrazione e CX formale in CX che termina con A.


29

Il calcolo base CK risulta adeguato alla logica modale minimale K ovvero, detto in altri termini, valido e completo rispetto alla nozione di K-validit`: a Proposizione 1.5.3. Per ogni A: A sse A K (ossia |=K A). CK

Calcoli normali adeguati (e nitamente assiomatizzati ) per ciascuna delle rimanenti sei logiche del Diagramma 1.4.6 si ottengono ora aggiungendo al sistema base CK lo o gli schemi caratteristici (nel senso del Teorema 1.4.3) della classe di cornici che determina semanticamente quella logica. Denizione 1.5.4. CD CT CK4 CB CS4 CS5 := := := := := := CK + D CK + T CK + 4 CK + T + B CK + T + 4 CK + T + B + 4 (D A A) (T A A) (4 A A) (B A A)

Proposizione 1.5.5. Per ogni L {D, T, K4, B, S4, S5} e ogni A: A CL sse A L.

Ossia: A sse |=Ser A, A sse |=Rf A, A sse |=Tr A, ecc. CD CT CK4 Come gi` sappiamo, in generale non ` facile trovare le dimostrazioni a e nei calcoli di tipo assiomatico. Facciamo un solo esempio. Esempio 1.5.6. 1. 2. 3. 4. 5. 6. 7. 8. CD . prop17 RN: 1 D RS: 2,3 I I RS: 4,6 def. : 7

Chi sente di avere suciente dimestichezza pu` cimentarsi nei seguenti o esercizi.17 ` E facile vericare che un calcolo modale normale dimostra ogni L -tautologia. Quando in una dimostrazione formale ce ne occorre una, conveniamo di scriverla direttamente in una riga, giusticandola con la sigla prop. In modo analogo possiamo giusticare le righe che seguono da righe precedenti per applicazione di una regola proposizionale ` eliminabile. E chiaro che ogni siatta dimostrazione stenograca pu` essere trasformata o in una dimostrazione in senso proprio.

30


Esercizio 1.5.7. Dimostrare che ogni calcolo modale normale ` chiuso sotto e le due regole D- e D- dellEsercizio 1.3.9 e sotto la regola di rimpiazzamento: BC A[p := B] A[p := C] A dierenza di quanto avviene nella logica enunciativa, il rimpiazzamento non vale in generale sotto forma di implicazione logica, ossia non in tutti i calcoli normali CX si ha (LR) (A B) (A[p := B] A[p := C]). CX

Individuare una condizione necessaria e suciente anch CX soddis (LR) e e concludere che in CS5 (e quindi in ogni suo sottosistema) (LR) non vale. Esercizio 1.5.8. Rifare sintatticamente gli esercizi delle precedenti sezioni nei quali si chiede di vericare che una certa formula ` legge di una delle e sette logiche K , . . . , S5 ossia ` valida nella relativa classe di cornici. Fare e cio` vedere che tale formula ` dimostrabile nel calcolo corrispondente. e e Esercizio 1.5.9. Dimostrare sintatticamente che il calcolo CD ` equivalente e al calcolo CK + . Nota: si tratta di far vedere che una formula A ` dimostrabile in CD sse ` e e dimostrabile in CK + . A tal ne, ` suciente (perch?) far vedere e e che: (i) lo schema D si dimostra in CK + ; (ii) lo schema si dimostra in CD (e questo gi` lo sappiamo dellEsempio 1.5.6). a Esercizio 1.5.10. Dimostrare sintatticamente che il calcolo CS5 ` equivae lente al calcolo CK + T + E. Esercizio 1.5.11. Con riferimento alloperazione strip denita nellEsercizio 1.2.8, dimostrare che per ogni L {K, D, T, K4, B, S4, S5} e ogni formula A vale A strip(A) , CL C dove C ` il calcolo proposizionale classico. Mostrare come da ci` segue e o immediatamente una dimostrazione sintattica di consistenza per il calcolo CL ( CL ). Esercizio 1.5.12 (Interpretazione monadica). Sia L un linguaggio elementare avente come uniche costanti descritive i predicati unari P0 , P1 , P2 . . . e sia x una variabile individuale di L arbitrariamente pressata. Deniamo una traduzione dallinsieme delle formule modali nellinsieme delle formule di L in cui occorre (libera o vincolata) solo la variabile x ponendo: p := Pi (x) , i (B) := B ,

1.5. CALCOLI MODALI DI TIPO ASSIOMATICO (B C) := B C ( B) := xB , (B) := xB . ( {, , , }) ,

31

Vericare che per ogni L {K, D, T, K4, B, S4, S5} e ogni formula modale A vale: A A . CL CQ Osservazione 1.5.13. Le versioni multimodali dei calcoli assiomatici monomodali CK, CD ecc. sono quelle che ci si aspetta. Il calcolo CKA per il linguaggio A-dimensionale LA si ottiene da CK rimpiazzando gli schemi [K] e [I] e la regola RN con le famiglie: {a (A

B) (

aA

a B)}aA ,

{a A

a A}aA ,

A aA

.aA

Analogamente, CDA ` CKA + { a A a A}aA , e cos` via. Anche per e questi calcoli valgono, mutatis mutandis, le Proposizioni 1.5.3 e 1.5.5.

1.5.2

Validit`, completezza, propriet` del modello nito a a

Se L {K, K4, D, T, B, S4, S5} indichiamo con CL il corrispondente calcolo assiomatico (v. Denizione 1.5.4) e con CL la corrispondente classe di cornici (cos` CK = K, CS4 = RfTr ecc.; v. Denizione 1.4.5). Le Proposizioni 1.5.3 e 1.5.5 stabiliscono, per ciascuna di queste sette logiche, lequivalenza tra la caratterizzazione sintattica e quella semantica, e come al solito risultano dalla composizione delle due asserzioni di validit` e completezza. La a prima segue facilmente dal lavoro gi` fatto. a Esercizio 1.5.14. Dimostrare che per ogni L {K, K4, D, T, B, S4, S5}: A CL |=CL A per ogni formula A .

Suggerimento: ragionando per induzione sulla lunghezza delle dimostrazioni in CL, basta far vedere che gli assiomi di CL sono CL -validi e che le due regole RS e RN preservano la CL -validit`: v. Lemma 1.3.1 e Teorema 1.4.3. a Quanto alla completezza, le cose non sono cos` semplici: di solito, la si dimostra aplicando il cosiddetto metodo del modello canonico, che risulta applicabile anche a molte altre logiche modali (non per` a tutte). Sorvolando o sui dettagli, ci limitiamo a dare solo unidea della strategia dimostrativa che Partiamo da un arbitrario calcolo modale normale CX, e procediamo come segue.

32


1: Dato un insieme (anche innito) di formule, diciamo che A ` CXe deducibile da , in simboli A, quando esiste una successione nita CX A1 , . . . , An di formule tale che An A e, per 1 k n, Ak (i) ` istanza e di uno degli schemi dassioma di CX, oppure (ii) appartiene a , oppure (iii) si ottiene da due formule precedenti per applicazione della regola RS, oppure (iv) si ottiene da una formula precedente che non dipende da alcuna assunzione18 in mediante applicazione di RN. Per questa nozione di deducibilit` si dimostra valere, usando in modo esa senziale la restrizione relativa alla regola RN19 , il Teorema di deduzione (analogamente a quanto si ha per i calcoli CQ e C, cf. ??): , A B CX AB. CX

Diciamo poi che ` CX-consistente quando CX . Segue dal Teorema e di deduzione che ` CX-consistente se e solo se per ogni sottinsieme nito e {B1 , . . . , Bn } di si ha che CX (B1 . . . Bn ). 2: Si denisce il concetto di insieme di formule CX-massimale. Un insieme ` tale quando ` CX-consistente ma nessuna sua estensione propria lo ` e e e (equivalentemente: CX ma + A per ogni A ). / CX Con MAXCX denotiamo la collezione degli insiemi CX-massimali. Non ` dicile vericare che ogni MAXCX (i) contiene ogni formula che e da esso si CX-deduce e (ii) si comporta come una valutazione bivalente relativamente ai connettivi verofunzionali (A sse A , A B sse / A o B , ecc.). Inoltre, con una tecnica alla Lindenbaum del tutto simile a quella impiegata nella dimostrazione del Lemma ??, si dimostra che ogni insieme CX-consistente pu` essere esteso a un insieme CX-massimale o (Lemma di estensione). 3: Si associa a ciascun calcolo normale CX un particolare modello di Kripke i cui mondi sono proprio gli insiemi CX-massimali. Pi` esattamente, si u deniscono: la cornice canonica FCX := MAXCX , RCX di CX, dove RCX sse A A per ogni formula A ; CX CX il modello canonico MCX := FCX , v di CX, dove v(, p) = 1 sse p . CXUn assioma non dipende da niente; unassunzione dipende da se stessa; la conclusione di unapplicazione di RS o RN dipende dal complesso delle assunzioni da cui dipendono le premesse. 19 Se si elimina tale restrizione si ottiene la nozione pi` debole di CX-derivabilit`, per u a la quale il Teorema di deduzione non vale pi`. P. es., ` chiaro che in qualunque CX si u e deriva (ma in generale non si deduce; perch?) e A da A; tuttavia A A non ` un e lemma logico di ogni CX!18


33

4: Si dimostra, sfruttando la denizione di MCX , le propriet` degli insiemi a massimali e il Lemma di estensione20 , il Teorema del modello canonico: per ogni MAXCX e ogni A : MCX , A A. CX

5: Sia ora A tale che CX A. Segue per il Teorema di deduzione che {A} ` CX-consistente, e quindi per il Lemma di estensione che {A} per e un certo MAXCX . Allora CX A (consistenza!) e, per il teorema del modello canonico, MCX , A. Dunque: ogni A che non ` lemma logico e di CX ` falsa nel modello canonico associato a CX. e metodo del modello canonico: Se A ` C-valida e FCX C allora e MCX |= A cosicch, per quanto visto al punto precedente, A ` lemma e e logico di CX. Dunque: per dimostrare che un calcolo normale CX ` valido e completo rispetto a e una data classe C di cornici ` suciente vericare che CX sia valido rispetto e a C e che la cornice canonica FCX di CX appartenga a C. dimostrazione della completezza per L {K, K4, D, T, B, S4, S5}: Applicando il metodo del modello canonico e tenendo conto del gi` dimoa strato Teorema di validit`, basta provare che FCL CL . Questo ` ovvio per a e K (CK ` la classe di tutte le cornici!) mentre per le rimanenti sei logiche e scende da: () T (risp. D, 4, B) CX FCX Rf (risp. Ser, Tr, Sim).

Verichiamo solo il caso di T. Se MAXCX e A allora, per CX CX RS con A A, si ottiene A. Segue, per denizione di RCX , che CX RCX e quindi che FCX Rf. Esercizio 1.5.15. 1. Dimostrare nei dettagli quanto enunciato passi (1) (5). 2. Dimostrare i restanti casi di (). 3. Come ulteriore applicazione del metodo del modello canonico dimostrare (cf. Esercizio 1.4.15) che il calcolo CK + T + 4 + L assiomatizza la logica S4.3. zione suciente20 Lo si usa per provare che se MAXCX e tale che RCX e CX B. CX

B allora esiste un MAXCX

Semantica di Kripke

Documents

Transcript of Semantica di Kripke