Logica proposizionale modale

Logica proposizionale modale

Sandro Zucchi

2009-10

S. Zucchi: Metodi formali per filosofi – Logica proposizionale modale 1

I modi della verita

� Il linguaggio LP ci permette di rappresentare gli enunciaticomplessi dell’italiano formati per mezzo di connettivi come “e”,“o”, “non”, e (se Grice, o Jackson e Lewis, hanno ragione) anchei connettivi “se” e “se e solo se”.

� Vogliamo ora arricchire LP per rappresentare gli enunciaticomplessi dell’italiano formati per mezzo di connettivi come “epossibile che”, “puo”, “e necessario che”, “necessariamente”,“deve”, ecc.

� Tradizionalmente, espressioni di questo genere sono dette“modali”, in quanto, applicate a una frase, ci dicono come questafrase e vera (cioe necessariamente vera oppure possibilmentevera).


Connettivi vero-funzionali e connettivi modali

� Abbiamo visto che i connettivi “e”, “o”, “non” (e forse anchecerte occorrenze di “se”) sono vero-funzionali, ovvero il valoredi verita dell’enunciato composto formato attraverso questiconnettivi e completamente determinato dai valori di veritadegli enunciati a cui essi si applicano.

� Invece, espressioni come “e possibile che”, “e necessario che”,ecc. non sono vero-funzionali.

� Rammentiamo le ragioni per cui il valore di verita di enunciatidella forma “e possibile che A” o “e necessario che A” non ecompletamente determinato dal valore di verita di A.


Possibilita e funzioni di verita� Supponiamo che Leo abbia vinto le elezioni, benche Lea avesse delle buone

possibilita di farcela. Supponiamo inoltre che, prima delle elezioni, io abbiaasserito (1) e (2). Chiaramente, asserendo (1) ho detto il falso, perche poi Leoha vinto. Ma asserendo (2) ho detto il vero, perche che Lea vincesse era unodegli esiti possibili.

(1) Lea vincera le elezioni.

(2) E possibile che Lea vinca le elezioni.

� Consideriamo ora gli enunciati (3) e (4). E chiaro che se asserisco (3) e (4) hodetto il falso in entrambi i casi:

(3) Leo e celibe e non e celibe

(4) E possibile che Leo sia celibe e non sia celibe

� Dunque, il valore di verita di enunciati della forma “e possibile che A” non ecompletamente determinato dal valore di verita di A. Infatti, se applico “epossibile che” all’enunciato falso (1) ottengo un enunciato vero (e cioe (2)),mentre se applico “e possibile che” all’enunciato falso (3) ottengo un enunciatofalso (cioe, (4)).


Necessita e funzioni di verita� Possiamo fare un ragionamento analogo per mostrare che “necessariamente”

non e un connettivo vero-funzionale.� Supponiamo che Leo, sebbene sia stato sul punto di farlo diverse volte, non si

sia mai sposato. Dunque, l’enunciato (5) e vero, ma l’enunciato (6) e falso, dalmomento che Leo avrebbe potuto sposarsi. Invece, (7) e (8) sono entrambiveri.

(5) Leo e celibe

(6) Necessariamente, Leo e celibe

(7) Se Leo e celibe, Leo e celibe

(8) Necessariamente, se Leo e celibe, Leo e celibe.

� Dunque, il valore di verita di enunciati della forma “necessariamente A” non ecompletamente determinato dal valore di verita di A. Infatti, se applico“necessariamente” all’enunciato vero (5) ottengo un enunciato falso (e cioe(6)), mentre se applico “necessariamente” all’enunciato vero (7) ottengo unenunciato vero (cioe, (8)).


Connettivi modali e tavole di verita

� Le considerazioni precedenti mostrano che non e possibileusare le tavole di verita per descrivere le condizioni di veritadei connettivi modali dell’italiano.

� Infatti, come abbiamo appena visto, non e possibile assegnarelo stesso valore di verita a �E necessario che A� in tutti i casiin cui A e falso. E non e possibile assegnare lo stesso valore diverita a �E possibile che A� in tutti i casi in cui A e vero:

ϕ Possibile AV VF ?

ϕ Necessario AV ?F F


Un suggerimento autorevole

� Come dovremo formulare dunque le condizioni di verita deglienunciati che contengono connettivi modali?

� Un buon suggerimento sulla strada da prendere viene daLeibniz. In un saggio del 1686 dal titolo “Verita contingenti enecessarie”, Leibniz afferma:

“[le verita necessarie] non solo varranno mentre ilMondo e cosı com’e, ma varrebbero anche se Dioavesse creato il mondo seguendo un piano diverso.”


Sfruttare il suggerimento

� Il passaggio precedente suggerisce che un enunciato dellaforma “e necessario che S” e vero esattamente nel caso in cuiS e vero non solo nel mondo reale, ma in ogni mondopossibile.

� Seguendo un’intuizione analoga, possiamo assumere che unenunciato della forma “e possibile che S” e vero esattamentenel caso in cui S e vero in almeno un mondo possibile.

� Le condizioni di verita delle formule con cui rappresentiamo glienunciati della forma “e necessario che S” ed “e possibile cheS” saranno dunque formulate seguendo questa idea.

� Prima di procedere a definire in modo preciso un linguaggioformale che contiene operatori modali, sono pero opportunedue riflessioni ulteriori.


I mondi possibili

� La scelta che abbiamo fatto e di interpretare i connettivimodali di necessita e possibilita come quantificatori su mondipossibili, cioe, come espressioni che significano “In ognimondo possibile e vero che” e “In almeno un mondo possibilee vero che”.

� Questa scelta solleva una questione:

• cosa sono i mondi possibili?

� Ecco come risponde D. Lewis, uno che di mondi possibili se neintendeva.


D. Lewis sui mondi possibiliIl mondo in cui viviamo e un cosa assai comprensiva. Ogni legnetto e ogni pietra che vi emai capitato di vedere e parte di esso. Io e voi siamo parte di esso. Ed e parte di esso ilpianeta terra, il sistema solare, l’intera Via Lattea, le galassie remote che vediamoattraverso il telescopio, e (se ci sono cose del genere) tutte le parti di spazio vuoto tra lestelle e le galassie. Non c’e nulla di cosı lontano da noi da non essere parte del nostromondo. Qualsiasi cosa a qualsiasi distanza deve essere inclusa. In modo analogo, ilmondo e comprensivo rispetto al tempo. Nessun antico romano dei tempi andati, nessunpterodattilo dei tempi andati, nessuna nuvola di plasma primordiale dei tempi andati etroppo lontana nel passato, ne le stelle morte sono troppo lontane nel futuro per essereparte dello stesso mondo. . . Il modo in cui le cose sono, nell’accezione piu comprensiva,significa il modo in cui e il mondo intero. Ma le cose potrebbero essere state diverse incosı tanti modi. Questo mio libro potrebbe essere stato terminato in tempo. O, se nonfossi un tizio cosı di buon senso, potrei sostenere non solo che esiste una pluralita dimondi possibili, ma anche una pluralita di mondi impossibili, in cui si parla in modoveritiero contraddicendosi. Oppure potrei non essere esistito per nulla. . . O potrebbe nonesserci mai stata alcuna persona. O le costanti fisiche potrebbero aver avuto dei valoriassai diversi, incompatibili con l’emergere della vita. O potrebbero esserci state delle leggidi natura completamente diverse; e invece degli elettroni e dei quark, potrebbero essercistate delle particelle aliene, senza carica o massa o forza di rotazione, ma con proprietaaliene non condivise da alcunche in questo mondo. Ci sono sempre cosı tanti modi in cuiun mondo potrebbe essere: e uno di questi molti modi e il modo in cui e questo mondo.D. Lewis, On the Plurality of Worlds, 1986


Il dibattito sulla natura dei mondi

� L’idea di Lewis e che ci siano tanti mondi possibili diversi, entita concrete dellostesso tipo del nostro mondo, ma distinte da esso. Questa tesi e chiamata disolito realismo modale.

� Altri filosofi rifiutano questa idea e ritengono che ci sia un unico mondo, cheinclude tutto cio che c’e.

� Si noti pero che la tesi che i connettivi modali, da un punto di vista semantico,sono quantificatori su mondi possibili non ci dice nulla sulla natura delle entitasu cui quantificano. In particolare, non ci costringe ad accettare l’idea che sianoentita concrete, dello stesso tipo del mondo attuale, ma distinte da esso.

� Un sostenitore della tesi che i connettivi modali sono quantificatori su mondipossibili potrebbe ritenere che ci sia un unico mondo, quello in cui viviamo, eche le entita su cui i connettivi modali quantificano siano anche loro parte diquesto mondo (siano, ad esempio, entita astratte come insiemi di frasi, oproprieta, ecc.). Questa tesi e chiamata di solito attualismo modale.

� La questione della natura dei mondi appartiene a un corso di metafisica piu che aun corso di metodi formali per filosofi. Dunque, non cercheremo di risolverla qui.


Le varieta della necessitaLa seconda riflessione, che invece ha conseguenze piu dirette per noi, ha originedal fatto che le espressioni modali occorrono con sensi diversi. Ecco qualcheesempio:

(9) Necessariamente, se oggi piove, oggi piove.

(10) E impossibile che Socrate sia un numero primo.

(11) E necessario che i giovani cedano il posto a sedere alle personeanziane.

(12) E impossibile viaggiare piu veloci della luce.

(13) Questo vino deve essere stato affinato in barrique.

(14) Nel 1932 era possibile per la Gran Bretagna evitare di entrare inguerra con la Germania, ma nel 1937 era necessario che la GranBretagna entrasse in guerra. (Thomason 2002)

(15) E necessario che distrugga le prove o che dica che i giudici sonocomunisti. (Adattato da Lewis 1979)

(16) E impossibile finire gli esercizi per domani.


Necessita logica ampia

� Gli enunciati (9) e (10) illustrano quella che Plantinga chiama“necessita logica ampia” (e il concetto di possibilitacorrispondente):


(10) E impossibile che Socrate sia un numero primo.

� Per questo senso di “necessita”, le condizioni di veritasuggerite dal passo di Leibniz sembrano appropriate. Nonesiste alcuna circostanza possibile in cui e falso che se oggipiove, oggi piove o in cui Socrate e un numero primo.Dunque, parrebbe che un enunciato e necessariamente vero,nel senso della necessita logica ampia, se e solo se e vero intutti i mondi possibili.


Necessita deontica

� Consideriamo ora l’enunciato (11):

(11) E necessario che i giovani cedano il posto a sedere alle personeanziane.

� Se asseriamo (11), presumibilmente intendiamo dire che se tuttiadempiessero ai propri obblighi morali sarebbe vero che i giovani cedono ilposto a sedere alle persone anziane.

� Il tipo di di necessita inteso quando affermiamo (11) e detto necessitadeontica.

� E chiaro che per gli enunciati che esprimono una necessita deontica lecondizioni di verita suggerite dal passo di Leibniz non sono appropriate: laverita di (11) non richiede che l’enunciato “i giovani cedono il posto asedere alle persone anziane” sia vero in tutti i mondi possibili. Infatti,(11) e vero anche se nel mondo attuale ci sono molti giovani maleducatiche non cedono il posto a sedere alle persone anziane.


Necessita fisica


(12) E impossibile viaggiare piu veloci della luce.

� Se asseriamo (12), evidentemente non intendiamo dire che inogni circostanza possibile e falso che si viaggi piu veloci dellaluce.

� Cio che intendiamo asserire pare invece questo: in ognicircostanza possibile in cui valgono le stesse leggi di naturache valgono attualmente e falso che si viaggi piu veloci dellaluce.

� Il tipo di necessita espresso da (12) e detto necessita fisica.


Necessita epistemica

� Supponiamo di assaggiare un vino e di emettere questo giudizio dopoun’attenta riflessione:

(13) Questo vino deve essere stato affinato in barrique.

� Ovviamente, non intendiamo dire che non esiste alcuna circostanzapossibile in cui questo vino e stato affinato in una botta diversa.Intendiamo dire invece che, in base alle conoscenze che abbiamo ottenutoall’assaggio, possiamo concludere che il vino e passato in barrique. Intermini di mondi possibili, potremmo parafrasare questa affermazionedicendo: il vino e stato affinato in barrique in tutti i mondi compatibilicon cio che sappiamo attualmente, avendolo assaggiato.

� Il tipo di di necessita inteso quando affermiamo (13) e detto necessitaepistemica. Di nuovo, se il nostro ragionamento precedente e corretto, laverita di (13) comporta che l’enunciato “il vino e stato affinato inbarrique” sia vero in un sottoinsieme di mondi possibili.


Necessita storica

� Quando emettiamo (14), non intendiamo dire che in tutte le circostanzepossibili la Gran Bretagna entra in guerra nel ‘37. Se Hitler non avessepraticato una politica cosı aggressiva, molto probabilmente la GranBretagna non sarebbe entrata in guerra nel ‘37.

(14) Nel 1932 era possibile per la Gran Bretagna evitare di entrare inguerra con la Germania, ma nel 1937 era necessario che la GranBretagna entrasse in guerra. (Thomason 2002)

� Cio che intendiamo dire e che, data la situazione che si era determinatanel ‘37, era impossibile per la Gran Bretagna evitare la guerra. In terminidi mondi possibili, potremmo esprimere questo tipo di necessita dicendoche in tutti i mondi possibili in cui il corso degli eventi fino al ‘37 eidentico a quello del mondo attuale, la Gran Bretagna entra in guerra.

� Solitamente, si dice che enunciati come (14) esprimono una necessitastorica.


Necessita italica

� Supponiamo che l’enunciato (15) sia emesso da un politico chevuole evitare la galera. Quando emette (15), il politico in questionenon vuol dire che in tutti mondi possibili o distrugge le prove o diceche i giudici sono comunisti (esistono mondi lontani da questo in cuicolui che emette (15) nel nostro mondo e una persona onesta).

(15) E necessario che distrugga le prove o che dica che i giudicisono comunisti.

� Cio che il politico intende e che, se non vuole andare andare ingalera, deve distruggere le prove o dire che i giudici sono comunisti.Nel linguaggio dei mondi possibili, (15) e vero se e solo se il politicodistrugge le prove o dice che i giudici sono comunisti in tutti imondi in cui non va in galera.


Necessita studentesca

� Infine, lo studente che afferma (16) non vuol dire che nonesiste alcuna circostanza possibile in cui finisce gli esercizi perdomani.

(16) E impossibile finire gli esercizi per domani.

� Intende dire invece che, date le sue motivazioni, la suavelocita nel fare gli esercizi, i suoi impegni serali, ecc., eimpossibile per lui finire gli esercizi entro domani.

� Nel linguaggio dei mondi possibili, questo equivale a dire che(16) e vero se e solo se lo studente in questione non finisce gliesercizi in tutti i mondi che sono simili al mondo attuale perquanto riguarda le sue motivazioni, la sua velocita nel fare gliesercizi, i suoi impegni serali, ecc.


Validita e tipi di necessita

� Dunque, i connettivi modali dell’italiano possono occorrerecon sensi diversi, possono esprimere tipi diversi di necessita.

� Ora, il nostro scopo, nel definire un linguaggio formale perrappresentare gli enunciati modali dell’italiano, e quello diindividuare le forme di argomentazione che garantiscono lavalidita delle argomentazioni in cui occorrono dei connettivimodali.

� Il problema e che le forme di argomentazione che garantisconola validita non sono affatto le stesse per tutti i sensi deiconnettivi modali.

� Vediamo un esempio.


Un esempionecessita logica

� Consideriamo l’enunciato (9):


� L’enunciato (9) esprime una necessita logica. E chiaro che eimpossibile che (9) sia vero e (17) falso:

(17) Se oggi piove, oggi piove.

� In generale, se “necessariamente” esprime una necessitalogica, e ragionevole supporre che gli argomenti della forma�Necessariamente S. Dunque, S� siano validi.


Un esempionecessita fisica


(18) Necessariamente, un velivolo non supera i 300.000km al secondo.

� L’enunciato (18) esprime una necessita fisica. Di nuovo, eimpossibile che (18) sia vero e (19) falso:

(19) Un velivolo non supera i 300.000 km al secondo.

� In generale, se “necessariamente” esprime una necessita fisica,e ragionevole supporre che gli argomenti della forma�Necessariamente S. Dunque, S� siano validi.


Un esempionecessita deontica

� Consideriamo tuttavia l’enunciato (11):

(11) E necessario che i giovani cedano il posto a sederealle persone anziane.

� L’enunciato (11) esprime una necessita deontica. In questocaso, e possibile che (11) sia vero e (20) falso:

(20) I giovani cedono il posto a sedere alle personeanziane.

� In generale, se “necessariamente” esprime una necessitadeontica, non e ragionevole supporre che gli argomenti dellaforma �Necessariamente S. Dunque, S� siano validi.


Distinguere i diversi tipi di necessita

� I connettivi modali dell’italiano possono dunque esprimerenozioni di necessita distinte e questi sensi distinti deiconnettivi modali possono dar luogo a forme diargomentazioni valide diverse, a logiche diverse.

� E chiaro che, se il nostro scopo e quello di identificare leforme di argomentazioni valide che caratterizzano i connettivimodali dell’italiano, non possiamo ignorare queste distinzioni,altrimenti potremmo caratterizzare come valido un argomentoche non lo e affatto o come invalido un argomento che invecee valido.

� Dobbiamo dunque distinguere tra sensi diversi dei connettivimodali quando li rappresentiamo in un linguaggio formale.


Connettivi diversi

� Un modo ovvio per distinguere tra sensi diversi dei connettivimodali dell’italiano quando costruiamo un linguaggio formalee quello di introdurre nel linguaggio formale connettivi diversiper sensi diversi.

� Questa e anche la strada che seguiremo qui. Per esempio,useremo

• i connettivi � e � per necessita e possibilita logica ampia;• i connettivi O e P per necessita e possibilita deontica;• i connettivi L e M per necessita e possibilita fisica;• e cosı via, per ogni senso di “necessario” e “possibile” che

vogliamo rappresentare.


Quantificazione ristretta

� Una volta che abbiamo introdotto connettivi diversi perrappresentare sensi diversi delle espressioni modalidell’italiano, dobbiamo specificare le condizioni di verita deglienunciati formati attraverso questi connettivi.

� Per illustrare i sensi diversi di “necessario”, “possibile”, ecc.,abbiamo usato espressioni come “vero in tutti i mondipossibili”, “vero in tutti i mondi possibili in cui valgono lenostre leggi fisiche”, “vero in tutti i mondi possibilicompatibili con cio che sappiamo”, ecc.

� Questo suggerisce che le condizioni di verita per gli enunciatiformati per mezzo di connettivi modali possano esseredescritte formalmente in termini di quantificazione su mondipossibili restringendo opportunamente l’insieme dei mondi sucui stiamo quantificando.


Relazioni di accessibilita

� Un modo per esplicitare le restrizioni a un certo insieme dimondi, quando descriviamo le condizioni di verita per glienunciati formati attraverso un connettivo modale, consistenel far uso di una relazione di accessibilita tra mondi.

� Cos’e una relazione di accessibilita tra mondi? Possiamofarcene un’idea intuitiva considerando i diversi tipi di necessitadi cui abbiamo parlato.

• Nel caso della necessita logica ampia, i mondi accessibili da unmondo w sono, presumibilmente, tutti i mondi possibili.

• Nel caso della necessita fisica, i mondi accessibili da un mondow sono, presumibilmente, i mondi in cui valgono le stesse leggidi natura di w.

• Nel caso della necessita deontica, i mondi accessibili da unmondo w sono, presumibilmente, i mondi in cui tutti fannoquello che e moralmente giusto fare in w.

• E cosı via.


Condizioni di verita per i connettivi modali

� Una volta introdotte relazioni di accessibilita distinte per idiversi tipi di necessita potremmo cercare di definire cosı lasemantica dei connettivi modali che abbiamo introdotto:

• ��ϕ� e vero ad un mondo w sse �ϕ� e vero ad ogni mondoaccessibile da w, dove tutti i mondi sono accessibili daqualunque mondo;

• �Oϕ� e vero ad un mondo w sse �ϕ� e vero ad ogni mondoaccessibile da w, dove un mondo w’ e accessibile da w sse inw’ tutti fanno quello che e moralmente giusto fare in w;

• �Lϕ� e vero ad un mondo w sse �ϕ� e vero ad ogni mondoaccessibile da w, dove un mondo w’ e accessibile da w sse in we in w’ valgono le stesse leggi di natura;

• e cosı via.


Relazioni di accessibilta e argomentazioni valide

� Il modo di procedere che abbiamo descritto e un modo abbastanzanaturale per descrivere la semantica degli operatori modali. Perosolleva una domanda.

� Abbiamo visto che sensi diversi di “necessario” possono dar luogo aforme di argomentazioni valide diverse, per esempio nel caso dellanecessita logica ampia e della necessita deontica.

� Ma altri sensi di “necessario” potrebbero dar luogo alle stesse formedi argomentazioni valide. Ad esempio, la necessita logica ampia e lanecessita fisica danno luogo alle stesse forme di argomentazionivalide o no? Finora non abbiamo trovato differenze al riguardo.

� Le condizioni di verita che abbiamo proposto per il connettivo dinecessita logica ampia � e il connettivo di necessita fisica Ldifferiscono esclusivamente per la relazione di accessibilita.

� Come possiamo determinare quando due relazioni di accessibilitadistinte danno luogo alle stesse forme di argomentazioni valide o aforme di argomentazioni valide diverse?


Proprieta formali delle relazioni di accessibilita

� Un metodo che si e rivelato utile per indagare a quali forme diargomentazione valide danno luogo sensi diversi di “necessario” e“possibile” e quello di caratterizzare questi diversi sensi in termini diproprieta formali delle relazioni di accessibilita.

� Per esempio, una relazione di accessibilita R, come qualunque relazione,

puo godere oppure no di proprieta di questo genere:

• universalita: per ogni w, w’, wRw’;

• riflessivita: per ogni w, wRw;

• simmetria: per ogni w, w’, se wRw’, allora w’Rw;

• transitivita: per ogni w, w’, w”, se wRw’, e w’Rw”, allora wRw”;

• estendibilita: per ogni w, c’e un w’ tale che wRw’;

(wRw si legge come il mondo w’ e accessibile dal mondo w).

� Nel formulare le condizioni di verita per i diversi operatori modali cheintrodurremo, caratterizzeremo dunque le relazioni di accessibilitaattraverso le proprieta formali di questo genere.


Accessibilita per la necessita logica ampia

� Per ora, ci concentreremo sui sensi di “necessario” e “possibile” checorrispondono alla necessita e alla possibilita logica ampia, cioe suglioperatori � e �.

� Un problema che sorge nel dare la semantica dei connettivi modali eche spesso, anche per lo stesso senso di “necessario”, “possibile”,non c’e consenso su quali siano le forme di argomentazioni valide.Questo vale anche per la necessita logica ampia.

� Per esempio, Plantinga (1974) e molti altri filosofi con lui ritengonoche per la necessita logica ampia siano adeguate certe forme diargomentazione che corrispondono all’idea leibniziana di necessitacome verita in tutti i mondi possibili (in questo caso, la relazione diaccessibilita R e universale).

� Altri autori, come Salmon (1989) e Bonevac (2003) ad esempio,differiscono su questo.

� Come dobbiamo formulare dunque la semantica per � e �?


Linguaggi per la possibilita logica ampia

� Una strada possibile e scegliere l’interpretazione chesolitamente viene assunta per i connettivi di necessita epossibilita logica ampia, cioe quella secondo cui la relazione diaccessibilita R e universale.

� Qui non seguiremo questa strada. Considereremo invecelinguaggi diversi che corrispondono a interpretazioni diversedei connettivi di necessita e possibilita logica ampia.

� Un vantaggio di questa scelta, come vedremo, e che cipermette identificare dei requisiti minimi che questi connettividevono soddisfare.


Il linguaggio LK

� Il primo linguaggio modale che consideriamo lo chiamiamo LK.

� Questo linguaggio, in realta, non e adeguato per caratterizzarei connettivi di necessita e possibilita logica ampia, in quantonon assicura la validita di certe forme di argomentazione chevengono generalmente ritenute valide per questi connettivi.

� Tuttavia, LK ci servira come base per costruire linguaggi piuadeguati.


Il linguaggio LKi simboli

� Un numero infinito di lettere proposizionali: p1 p2 p3 p4 . . .

� I connettivi: ∧ ∨ ⊃ ≡ ∼� Le parentesi: ( )

� Gli operatori di necessita e di possibilita: � �


Il linguaggio LKle formule ben formate

(a) Le lettere proposizionali sono formule ben formate di LK(dette formule atomiche).

Se ϕ e ψ sono formule ben formate di LK, allora:

(b) ∼ ϕ e una formula ben formata di LK,

(c) (ϕ ∧ ψ) e una formula ben formata di LK,

(d) (ϕ ∨ ψ) e una formula ben formata di LK,

(e) (ϕ ⊃ ψ) e una formula ben formata di LK,

(f) (ϕ ≡ ψ) e una formula ben formata di LK,

(g) �ϕ e una formula ben formata di LK,

(h) �ϕ e una formula ben formata di LK.

(i) Nient’altro e una formula ben formata di LK.

(Convenzione: e possibile tralasciare le parentesi, quando noncrea ambiguita).


Verita relativa a un mondo

� Un ingrediente fondamentale della semantica di LK e deglialtri linguaggi modali che considereremo, oltre ai mondipossibili e alla relazione di accessibilita, e la nozione di veritaa un mondo (di cui in realta abbiamo gia fatto uso in modoinformale nella discussione precedente).

� A differenza delle valutazioni per LP, che assegnano valori diverita alle formule, le valutazioni per LK (cosı come per glialtri linguaggi modali) assegnano valori di verita alle formulerelativamente a un mondo.

� Vediamo come.


Il linguaggio LKmodelli

Un modello per LK e una tripla <W, R, ν>, dove

1. W e un insieme non vuoto di mondi possibili,

2. R e una relazione binaria tra elementi di W (la relazione diaccessibilita),

3. ν e una funzione che assegna un valore di verita alle formuledi LK relativamente a un mondo nel modo seguente:


per ogni mondo w in W,

(a) se ϕ e una lettera proposizionale di LK, ν(ϕ, w) ∈ {0, 1};se ϕ e ψ sono formule ben formate di LK, allora:

(b) ν(∼ ϕ, w)=1 se ν(ϕ, w)=0, altrimenti ν(∼ ϕ, w)=0;(c) ν(ϕ ∧ ψ, w)=1 se ν(ϕ, w)=1 e ν(ψ, w)=1, altrimenti

ν(ϕ ∧ ψ, w)=0;(d) ν(ϕ ∨ ψ, w)=1 se non accade che ν(ϕ, w)=0 e ν(ψ, w)=0,

altrimenti ν(ϕ ∨ ψ, w)=0;(e) ν(ϕ ⊃ ψ, w)=1 se non accade che ν(ϕ, w)=1 e ν(ψ, w)=0,

altrimenti ν(ϕ ⊃ ψ, w)=0;(f) ν(ϕ ≡ ψ, w)=1 se ν(ϕ, w)=ν(ψ, w), altrimenti

ν(ϕ ≡ ψ, w)=0.(g) ν(�ϕ, w)=1 se per ogni w’ in W tale che wRw’, ν(ϕ, w’)=1,

altrimenti ν(�ϕ, w)=0;(h) ν(�ϕ, w)=1 se c’e almeno un w’ in W tale che wRw’ e ν(ϕ,

w’)=1, altrimenti ν(�ϕ, w)=0.

(“ν(ϕ, w)=1” si legge come “il valore di verita di ϕ al mondo w e 1”).


Validita in LK

� Un argomento in LK con premesse ϕ1, . . . , ϕn e conclusione ψe valido in LK se non esiste un modello <W, R, ν> di LK eun mondo w in W tali che ν(ϕ1, w) = 1, . . . , ν(ϕn, w) = 1 eν(ψ, w) = 0.

� Se un argomento e valido in LK diremo anche che le suepremesse implicano la sua conclusione in LK.

� In simboli, quando un argomento in LK e valido, scriveremo:

{ϕ1, . . . , ϕn} |=LK ψ

� Una formula ben formata ϕ di LK e valida (|=LK ϕ) se e solose non esiste un modello <W, R, ν> di LK e un mondo w inW tali che ν(ϕ, w)=0.


Nota storicaModelli di Kripke

� Questo modo di dare la semantica dei connettivi modali, permezzo di modelli che consistono in un insieme di mondi, unarelazione di accessibilita e una funzione che assegna un valoredi verita alle formule relativamente a un mondo, e dovuto aKripke (1963).

� Tuttavia, l’idea di utilizzare una relazione di accessibilita tramondi per la semantica delle espressioni modali e venuta inmente a diversi autori piu o meno contemporaneamente(Geach, Prior, Hintikka, Kanger, Montague e Kripke).

� (Una storia degli sviluppi della logica modale dalla finedell’Ottocento a oggi la trovate in Goldblatt 2005).


Proprieta di LK

� Soffermiamoci ora su alcune proprieta del linguaggio LK.

� Questo sara utile per comprendere bene come sicaratterizzano rispetto a LK i linguaggi che introdurremo perla necessita e la possibilita logica ampia.


Proprieta di LKmondi accessibili

� Si noti che, se non ci sono mondi accessibili da un mondo w, allora, perqualsiasi ϕ, ν(�ϕ, w)=0 e ν(�ϕ, w)=1 (cioe, ogni enunciato della forma��ϕ� e vero a w e ogni enunciato della forma ��ϕ� e falso a w).

� Per capire perche ν(�ϕ, w)=1, se non ci sono mondi accessibili da w,dobbiamo prima convincerci di questo: dire che una formula e vera a ognimondo accessibile equivale a dire che non esiste un mondo accessibile acui e falsa.

� Una volta che ci siamo convinti, possiamo ragionare cosı:

• se non ci sono mondi possibili accessibili da w, non esiste unw’ tale che wRw’;

• dunque, a maggior ragione, non esiste un w’ tale che wRw’ eν(ϕ, w’)=1;

• dunque, per ogni w in W tale che wRw’, ν(ϕ, w’)=1;• dunque, ν(�ϕ, w)=1.


Proprieta di LKregola di necessitazione

� Si noti che, se una formula ϕ e valida in LK, allora anche lanecessitazione di ϕ lo e: in simboli, se |=LK ϕ, allora|=LK �ϕ.

� Possiamo convincerci che le cose stanno cosı con questosemplice ragionamento:

• se ϕ e valida in LK, allora per ogni modello <W, R, ν> di LKe mondo w in W, ν(ϕ, w)=1;

• dunque, per ogni modello <W, R, ν> di LK e mondo w in W,ν(ϕ, w’)=1 per ogni mondo w’ in W tale che wRw’;

• dunque, per ogni modello <W, R, ν> di LK e mondo w in W,ν(�ϕ, w)=1, ovvero |=LK �ϕ.


Proprieta di LKequivalenza di �∼�ϕ� e ��∼ ϕ�

� Si noti che ∼�ϕ |=LK �∼ ϕ, per ogni formula ϕ.Infatti:

• supponiamo che <W, R, ν> sia un modello qualunque di LK ew sia un mondo in W tale che ν(∼�ϕ, w)=1.

• dunque, ν(�ϕ, w)=0;• dunque, non esiste un mondo w’ in W tale che wRw’ e ν(ϕ,

w’)=1;• dunque, per ogni mondo w’ in W tale che wRw’, ν(ϕ, w’)=0;• dunque, per ogni mondo w’ in W tale che wRw’,

ν(∼ ϕ, w’)=1;• dunque, ν(�∼ ϕ, w)=1;• dunque, non esiste un modello <W, R, ν> di LK e un mondo

w in W tali che ν(∼�ϕ, w)=1 e ν(�∼ ϕ, w)=0, ovvero∼�ϕ |=LK �∼ ϕ.

� In modo simile, possiamo convincerci che �∼ ϕ |=LK∼�ϕ.


Proprieta di LKequivalenza di �∼�ϕ� e ��∼ ϕ�

� Si noti che ∼�ϕ |=LK �∼ ϕ, per ogni formula ϕ.Infatti:

• supponiamo che <W, R, ν> sia un modello qualunque di LK ew sia un mondo in W tale che ν(∼�ϕ, w)=1.

• dunque, ν(�ϕ, w)=0;• dunque, esiste un mondo w’ in W tale che wRw’ e ν(ϕ, w’)=0;• dunque, esiste un mondo w’ in W tale che wRw’ e

ν(∼ ϕ, w’)=1;• dunque, ν(�∼ ϕ, w)=1;• dunque, non esiste un modello <W, R, ν> di LK e un mondo

w in W tali che ν(∼�ϕ, w)=1 e ν(�∼ ϕ, w)=0, ovvero∼�ϕ |=LK �∼ ϕ.

� Con un ragionamento analogo, possiamo convincerci che�∼ ϕ |=LK ∼�ϕ.


Proprieta di LKequivalenza di ��ϕ� e �∼�∼ ϕ�

� Si noti che �ϕ |=LK ∼�∼ ϕ, per ogni formula ϕ.Infatti:

• supponiamo invece che �ϕ �LK ∼�∼ ϕ;• dunque, c’e un modello <W, R, ν> di LK e un mondo w in W

tali che ν(�ϕ, w)=1 e ν(∼�∼ ϕ, w)=0;• dunque, ν(�∼ ϕ, w)=1;• dunque ν(∼�ϕ, w)=1 (per l’equivalenza stabilita in

precedenza);• dunque, ν(�ϕ, w)=0, contrariamente a quanto ipotizzato.

� Con un ragionamento analogo, possiamo convincerci che∼�∼ ϕ |=LK �ϕ.


Proprieta di LKequivalenza di ��ϕ� e �∼�∼ ϕ�

� Si noti che �ϕ |=LK ∼�∼ ϕ, per ogni formula ϕ.Infatti:

• supponiamo invece che �ϕ �LK ∼�∼ ϕ;• dunque, c’e un modello <W, R, ν> di LK e un mondo w in W

tali che ν(�ϕ, w)=1 e ν(∼�∼ ϕ, w)=0;• dunque, ν(�∼ ϕ, w)=1;• dunque ν(∼�ϕ, w)=1;• dunque, ν(�ϕ, w)=0, contrariamente a quanto ipotizzato.

� Con un ragionamento analogo, possiamo convincerci che∼�∼ ϕ |=LK �ϕ.


Proprieta di LKinvalidita di ��p ⊃ p�

� Si noti che �LK �p ⊃ p, per ogni lettera proposizionale p.Possiamo vedere che le cose stanno cosı mostrando uncontro-modello, ovvero un modello <W, R, ν> tale che c’e unmondo w in W a cui ��p ⊃ p� e falsa. Un contro-modello diquesto genere e qualsiasi modello tale che

• W={w1, w2};• R={< w1, w2 >, < w2, w2 >} (vale a dire, w1Rw2 e w2Rw2,

cioe w2 e accessibile da w1 e da w2);• ν(p, w1)=0 e ν(p, w2)=1.• In questo modello, ��p� e vera a w1, in quanto p e vera in

tutti i mondi accessibili da w1, ovvero in w2. Ma p e falsa inw1, in quanto ν(p, w1)=0. Dunque, ��p ⊃ p� e falsa in w1,in quanto l’antecedente e vero e il conseguente falso in w1.


Inadeguatezza di LK

� Il linguaggio LK non e adeguato per rappresentare i connettividi necessita e possibilita logica ampia.

� L’ultima proprieta di LK che abbiamo considerato e sufficientea mostrare che non lo e.

� Infatti, abbiamo visto che una proprieta caratteristica dellanecessita logica ampia e questa: se un enunciato S enecessariamente vero in italiano, nel senso della necessitalogica ampia, allora S e vero.

� Ma ��p ⊃ p� non e una formula valida in LK, e dunquequesta proprieta non e garantita per LK.


Diagnosi delle cause� Per quale ragione ��p ⊃ p� non e valida in LK?

� Riflettiamo sui contro-modelli che abbiamo dato:

• W={w1, w2};• R={< w1, w2 >, < w2, w2 >} (vale a dire, w1Rw2 e w2Rw2,

cioe w2 e accessibile da w1 e da w2);• ν(p, w1)=0 e ν(p, w2)=1;

� Cio che permette di costruire un modello in cui ��p ⊃ p� e falsa ad unmondo e evidentemente il fatto che i mondi accessibili da un mondo datonon includono necessariamente quel mondo, cioe il fatto che la relazionedi accessibilita non e necessariamente riflessiva.

� Per esempio, nei contro-modelli che abbiamo costruito, vediamo che w1

non e accessibile da w1, ed e questo che determina la possibilita che��p� sia vera a w1 senza che �p� sia vera a w1, e dunque ��p ⊃ p� siafalsa a w1.

� Dal momento che non abbiamo imposto nessuna condizione sullarelazione di accessibilita R, niente ci impedisce di costruire un modellocon una relazione di accessibilita tale che “��p ⊃ p�” risulta invalida.


Tableaux per LK

� Per LK non introdurremo un sistema di deduzione naturale,ma ci limiteremo a dare un sistema di tableaux per lederivazioni. Chiameremo questo sistema LK(TAB).

� (LK(TAB), cosı come i sistemi di tableaux che introdurremoin seguito, e basato su Priest 2001).


La forma delle regole

� Le regole di LK(TAB) hanno una forma molto simile a quelle per itableaux della logica proposizionale, con qualche differenza.

� Nelle regole dei tableaux per il linguaggio della logicaproposizionale, ogni nodo era occupato da una formula.

� Nelle regole di LK(TAB), le regole dei tableaux per il linguaggio LK,ogni nodo e occupato

• da una riga della forma �ϕ, i�, dove i e un numero naturale,oppure

• da una riga della forma irj , dove i e j sono numeri naturali.

� Intuitivamente, possiamo pensare ai numeri naturali che occorronoin un nodo come a mondi possibili. Possiamo leggere “ϕ, i” come“la formula ϕ e vera al mondo i” e “irj” come “il mondo j eaccessibile dal mondo i”.

� (Ufficialmente, le regole di LK(TAB) non fanno pero alcunriferimento al significato dei simboli che manipolano).


Regole per LK(TAB)connettivi vero-funzionali


Regole per LK(TAB)connettivi modali


Come applicare le regole� Ogni premessa ϕ alla radice dell’albero deve occorrere con il numero 0: �ϕ, 0�.

La negazione della conclusione, �∼ψ�, alla radice dell’albero deve occorrere conil numero 0: �∼ψ, 0�.

� Nella regola per la necessita le righe ��ϕ, i� e �irj� devono essere entrambepresenti per poter applicare la regola (non e pero necessario che siano adiacentine nell’ordine indicato).

� Un ramo del tableaux e chiuso se e solo per qualche formula ϕ e qualchenumero i , sia �ϕ, i� che �∼ ϕ, i� occorrono sul ramo.

� Le definizioni di tableau chiuso, terminato e derivabilita in LK(TAB) sono le

consuete:

• Un tableau e terminato se e solo se ogni regola che puo essere applicata e

stata applicata.

• Un tableau e chiuso se ogni suo ramo e chiuso; altrimenti e aperto.

• ψ e derivabile in LK(TAB) da un insieme di formule Σ se e solo se c’e un

tableau terminato e chiuso la cui radice consiste nei membri di Σ e nella

negazione di ψ.

• {ϕ1, . . . , ϕn} �LK (TAB) ψ =def . ϕ e derivabile in LK(TAB) dall’insieme di

formule {ϕ1, . . . , ϕn}.• �LK (TAB) ψ =def . ϕ e derivabile in LK(TAB) dall’insieme di vuoto ∅.


Completezza e correttezza

� E possibile dimostrare che le regole di LK(TAB) permettonodi derivare una conclusione da un insieme di premesseesattamente nel caso in cui le premesse implicano laconclusione in LK.

� In simboli:

{ϕ1, . . . , ϕn} �LK (TAB) ψ sse {ϕ1, . . . , ϕn} |=LK ψ.

� (Come caso particolare, e possibile mostrare che �LK (TAB) ψsse |=LP ψ).


Estensioni di LK� Se L e L′ hanno la stessa sintassi, diciamo che L′ e

un’estensione di L esattamente nel caso in cui, per ogniformula ϕ, se Σ |=L ϕ, allora Σ |=L′ ϕ; L′ e un’estensionepropria di L sse L′ estende L e qualche argomento valido inL′ non e valido in L.

� Esamineremo ora tre linguaggi distinti che sono tuttiestensioni proprie di LK.

� Dunque, ogni argomento valido in LK e valido anche neilinguaggi che introdurremo.

� Questi linguaggi possono essere visti come ipotesi diverse sulsenso di “necessario” e “possibile” che corrisponde allanecessita logica ampia, benche l’ultimo che esamineremo siaquello solitamente associato a questa nozione.

� (In generale, i linguaggi che estendono LK sono detti linguaggidella logica modale normale).


Il linguaggio LT

� Il primo linguaggio che introduciamo e il linguaggio LT.

� Il linguaggio LT e definito esattamente come il linguaggio LK,eccetto per la definizione di modello.

� In particolare, la seconda clausola nella definizione di modello,viene modificata cosı:

• Un modello per LT e una tripla <W, R, ν>, dove

1. . . .2. R e una relazione binaria tra elementi di W riflessiva (la

relazione di accessibilita),3. . . .


Il linguaggio LS4

� Il secondo linguaggio che introduciamo e il linguaggio LS4.

� Il linguaggio LS4 e definito esattamente come il linguaggioLT, eccetto per la definizione di modello.


• Un modello per LS4 e una tripla <W, R, ν>, dove

1. . . .2. R e una relazione binaria tra elementi di W riflessiva e

transitiva (la relazione di accessibilita),3. . . .


Il linguaggio LS5

� Il terzo linguaggio che introduciamo e il linguaggio LS5.

� Il linguaggio LS5 e definito esattamente come il linguaggioLS4, eccetto per la definizione di modello.


• Un modello per LS5 e una tripla <W, R, ν>, dove

1. . . .2. R e una relazione binaria tra elementi di W universale (la

relazione di accessibilita),3. . . .


Commenti sui linguaggi LT, LS4, LS5


Validita di ��ϕ ⊃ ϕ� in LT

� Abbiamo visto che LK era inadeguato in quanto rendeva ��p ⊃ p�invalida.

� La nostra diagnosi era che questo dipendesse dal fatto che in LKnon e richiesto che la relazione di accessibilita R sia riflessiva.

� Ora, cio che contraddistingue LT e proprio che la relazione diaccessibilita e riflessiva, e dunque, per ogni formula ϕ, la validita di��ϕ ⊃ ϕ� e assicurata in LT.

� Infatti, supponiamo che, per qualche formula ϕ, ��ϕ ⊃ ϕ� siainvalida in LT. In questo caso, c’e un modello per LT tale che��ϕ ⊃ ϕ� e falsa in qualche mondo del modello. Supponiamo chew sia un mondo del genere. Allora, ��ϕ� e vera in w e ϕ falsa in w.Dunque, ϕ e vera in tutti i mondi accessibili da w. Dal momentoche la relazione di accessibilita e riflessiva, ne segue che w eaccessibile da w e dunque ϕ e vera in w, in contraddizione con laconclusione precedente che ϕ e falsa in w.


Validita di ��ϕ ⊃ ϕ� in LS4 e LS5

� Una breve riflessione ci mostra che la validita di ��ϕ ⊃ ϕ� eassicurata anche in LS4 e LS5.

� Infatti, in LS4 la relazione di accessibilita R e riflessiva oltreche transitiva e quindi il ragionamento precedente permostrare che ��ϕ ⊃ ϕ� e valida per ogni formula ϕ si applicadi nuovo.

� In LS5, d’altra parte, la relazione di accessibilita R euniversale, cioe ogni mondo e accessibile da ogni mondo.Dunque, in particolare, ogni mondo sara accessibile da sestesso. Dunque, la validita di ��ϕ ⊃ ϕ� e assicurata anche inS5.


Inclusione tra insiemi di argomenti validi

� Il fatto precedente e un caso particolare di un fatto molto piugenerale: LT e un’estensione propria di LK, LS4 e un’estensionepropria di LT e LS5 e un’estensione propria di LS4.

� Vale a dire, gli argomenti validi in LK sono tutti validi in LT (ma nonviceversa), gli argomenti validi in LT sono tutti validi in LS4 (ma nonviceversa), e gli argomenti validi in LS4 sono tutti validi in LS5 (manon viceversa).


Inclusione tra insiemi di modelli� Questa relazione tra gli argomenti validi in LK, LT, LS4 e LS5 e una

conseguenza del modo in cui abbiamo definito i modelli per questi linguaggi.

In particolare, dalla definizione segue che

• ogni modello per LS5 e un modello per LS4;

• ogni modello per LS4 e un modello per LT;

• ogni modello per LT e un modello per LK.

� Se questo e vero, e facile verificare che l’insieme degli argomenti validi in LS5include l’insieme degli argomenti validi in LS4, che include l’insieme degliargomenti validi in LT, che include l’insieme degli argomenti validi in LK.


Principi caratteristiciLT

� Abbiamo visto che LK non assicura la validita di ��ϕ ⊃ ϕ�per ogni ϕ, mentre la validita di enunciati di questa forma eassicurata in LT, grazie al fatto che la relazione di accessibilitae riflessiva.

� In questo senso, diciamo che ��ϕ ⊃ ϕ� e il principiocaratteristico di LT: ogni sua istanza e valida in LT (e in tuttele sue estensioni), ma questo non vale nei linguaggi che LTestende propriamente.

� Al pari di LT, anche LS4 e LS5 hanno ciascuno un principiocaratteristico.


Principi caratteristiciLS4

� Il principio caratteristico di LS4 e ��ϕ ⊃ ��ϕ�.

� Infatti, la condizione che la relazione di accessibilita sia transitiva, tipica deimodelli per LS4, assicura la validita di ogni istanza di ��ϕ ⊃ ��ϕ� (mentrequesto non vale se la relazione di accessibilita e solo riflessiva, come richiestoper i modelli di LT).

� Supponiamo infatti che ci sia una formula ϕ tale che ��ϕ ⊃ ��ϕ� e invalidain LS4. Dunque, c’e un modello per LS4 tale che ��ϕ� e vera e ��ϕ� falsain qualche mondo del modello. Sia w un mondo di questo genere. Dunque, ϕe vera in ogni mondo accessibile da w (in quanto ��ϕ� e vera in w). Inoltre,per qualche mondo w’ accessibile da w, ��ϕ� e falsa in w’ (in quanto ��ϕ�e falsa in w). Dunque, per qualche mondo w” accessibile da w’, ϕ e falsa inw”. Ma R e transitiva, e dunque w” e accessibile da w (in quanto w’ eaccessibile da w e w” da w’). Dunque, essendo ϕ e vera in ogni mondoaccessibile da w, sara vera anche in w”, in contraddizione con la conclusioneprecedente che ϕ e falsa in w”.

� (Lasciamo come esercizio il compito di mostrare che ��ϕ ⊃ ��ϕ� non evalido per ogni ϕ, se la relazione di accessibilita e solo riflessiva).


Principi caratteristiciLS5

� Il principio caratteristico di LS5 e ��ϕ ⊃ ��ϕ�.

� Questo principio e assicurato se richiediamo che la relazione diaccessibilita sia universale, come richiesto dai modelli per LS5, ma non serichiediamo che sia semplicemente riflessiva e transitiva (lasciamo laprova come esercizio).

� Un altro modo per assicurare validita di ��ϕ ⊃ ��ϕ� per ogni ϕ eaggiungere la condizione che la relazione di accessibilita sia simmetrica,oltre che transitiva e riflessiva

� E possibile mostrare (non lo faremo qui) che queste due condizioni suimodelli sono equivalenti in questo senso: gli argomenti che risultanovalidi se la relazione di accessibilita e universale sono esattamente glistessi che risultano validi se la relazione di accessibilita e riflessiva,transitiva e simmetrica.

� (Per questa ragione, la semantica di LS5 viene talvolta formulatarichiedendo che la relazione di accessibilita sia riflessiva, transitiva esimmetrica).


Iterazione delle modalitaLS5

� Concludiamo la discussione delle proprieta dei linguaggi che abbiamointrodotto, menzionando (senza provarla) una proprieta ulteriore di LS5.

� Le regole di formazione dei linguaggi modali permettono di costruire delleformule che contengono sequenze consecutive di operatori modali. Peresempio, queste sono formule ben formate di LK, LT, LS4 e LS5:

(a) ��p

(b) ��(p ⊃ �q)

(c) ��∼�q

� In LS5, e possibile eliminare tutti gli operatori modali tranne l’ultimo(tranne cioe quello indicato in blu nelle formule) e ottenere una formulaequivalente.

� Dunque, in LS5 le formule (a)-(c) sono equivalenti ad (a’)-(c’):

(a’) �p

(b’) �(p ⊃ �q)(c’) �∼�q


Deduzione naturale per la logica modale proposizionale

� Introdurremo ora tre sistemi di deduzione naturale per ilinguaggi che abbiamo definito, che chiameremo

• T(NAT)

• S4(NAT)

• S5(NAT)

� I sistemi si basano su Gettier (1982) e Salmon (1994).


Il sistema T(NAT)

� Il sistema T(NAT) consiste in queste regole:

• tutte le regole di LP(NAT);

• le regole di inferenza �E, �I, MN + le regole diinscatolamento e cancellazione specifiche di T(NAT).


Regole di inferenza �E, �I, MN


Righe accessibili

� Per definire le regole di inscatolamento e cancellazionespecifiche di T(NAT) definiamo la nozione di riga accessibile.

� Nel definire le derivazioni in LP abbiamo detto che una riga edisponibile se e solo se non e inscatolata e non contiene laparola ‘Prova’ non cancellata.

� Aggiungiamo ora che una riga disponibile e accessibile se esolo se c’e al piu una riga �Prova: �ξ� o �Prova: �ξ� noncancellata che la segue.

� (Chiaramente, questo vuol dire che una riga puo essereaccessibile a un certo punto della prova e non essereaccessibile in un altro punto.)


Regole di inscatolamento e cancellazione di T(NAT)Le regole di inscatolamento e cancellazione specifiche di T(NAT) sonoqueste:

dove (a) ��ϕ� e accessibile quando ϕ viene introdotta come assunzione, e (b)nelle prove inscatolate tutti i riferimenti esterni alle prove sono a righeaccessibili applicando la regola �E.


Il sistema S4(NAT)

� Il sistema S4(NAT) consiste in queste regole:


• le regole di inferenza �E, �I, MN + le regole diinscatolamento e cancellazione specifiche di S4(NAT).


Regole di inscatolamento e cancellazione di S4(NAT)Le regole di inscatolamento e cancellazione specifiche di S4(NAT)sono queste:

dove (a) ��ϕ� e accessibile quando ϕ viene introdotta come assunzione, e (b)nelle prove inscatolate tutti i riferimenti esterni alle prove sono a righeaccessibili applicando la regola �E o la regola R a enunciati della forma ��χ�.


Il sistema S5(NAT)

� Il sistema S5(NAT) consiste in queste regole:


• le regole di inferenza �E, �I, MN + le regole diinscatolamento e cancellazione specifiche di S5(NAT).


Regole di inscatolamento e cancellazione di S5(NAT)Le regole di inscatolamento e cancellazione specifiche di S5(NAT)sono queste:

dove (a) ��ϕ� e accessibile quando ϕ viene introdotta come assunzione, e (b)nelle prove inscatolate tutti i riferimenti esterni alle prove sono a righeaccessibili applicando la regola �E o la regola R a enunciati della forma ��χ� o��χ�.


Completezza e correttezza

� Per ciascuno dei sistemi di deduzione naturale che abbiamointrodotto e possibile mostrare che permette di derivare unaconclusione da un insieme di premesse esattamente nei casi incui le premesse implicano la conclusione nel linguaggiocorrispondente.

� In simboli:

{ϕ1, . . . , ϕn} �T\S4\S5(NAT ) ψ sse{ϕ1, . . . , ϕn} |=LT\LS4\LS5 ψ.

� (Come caso particolare, e possibile mostrare che�T\S4\S5(NAT ) ψ sse |=LT\LS4\LS5 ψ).


Tableaux per LT, LS4, LS5

� Concludiamo introducendo dei sistemi di tableaux per ilinguaggi che abbiamo considerato:

• T(TAB)

• S4(TAB)

• S5(TAB)

� Come per i sistemi di deduzione naturale, e possibile mostrareche questi sistemi di tableaux permettono di derivare unaconclusione da un insieme di premesse esattamente nei casi incui le premesse implicano la conclusione nei linguaggicorrispondenti.


Regole per T(TAB)

� Le regole per T(TAB) sono le regole per LK(TAB) + la regolaseguente:


Regole per S4(TAB)Le regole per S4(TAB) sono:

� le regole di T(TAB) + la regola seguente:


Regole per S5(TAB)Le regole per S5(TAB) sono:

� le regole di necessita negata e possibilita negata di LK(TAB)+ le regole seguenti di possibilita e necessita:


Logica proposizionale modale

Documents

Transcript of Logica proposizionale modale