IA simbolica: logica epistemica

Una logica per ragionare su conoscenza e opinione

Questa parte si basa su un paio di testi:

1. Hans van Ditmarsch, Joseph Y. Halpern, Wiebe van der Hoek, Barteld Kooi. An Introduction to Logics of Knowledge and Belief. Capitolo 1 di Handbook of Epistemic Logic, 2015.

2. Rasmus Rendsvig, John Symons, and Yanjing Wang. Epistemic Logic, The Stanford Encyclopedia of Philosophy, Edward N. Zalta & Uri Nodelman (eds.), 2023.

La logica epistemica studia la nozione di conoscenza (knowledge in inglese; episteme in greco) e la logica doxastica studia la nozione di credenza (belief in Inglese; in greco antico doxa significa opinione). In senso più ampio, queste logiche studiano la nozione di informazione.

Il ragionamento sulla conoscenza presenta sottigliezze che vanno oltre quelle che si presentano nella logica proposizionale o dei predicati. Prendiamo, ad esempio, la legge del terzo escluso nella logica classica, che dice che per qualsiasi proposizione $p$, deve valere o $p$ o $\neg p$ (la negazione di $p$); formalmente, $p \vee \neg p$.

Nel linguaggio della logica epistemica, scriviamo $K_a p$ per dire che "l'agente $a$ conosce $p$" e intuitivamente intendiamo che "in tutti i possibili mondi accessibili dall'agente $a$ la proposizione $p$ è vera".

Questa semplice aggiunta al linguaggio ci permette di porre nuove questioni. Ad esempio, che tipo di situazioni descrivono le seguenti formule? Quali di loro dovrebbero essere valide?

1. $K_a p \vee \neg K_a p$: l'agente $a$ conosce $p$ o non conosce $p$
2. $K_a p \vee K_a \neg p$: l'agente $a$ conosce $p$ o conosce la sua negazione $\neg p$
3. $K_a (p \vee \neg p)$: l'agente $a$ conosce $p$ o la sua negazione $\neg p$
4. $K_a p \vee \neg K_a \neg p$: l'agente $a$ conosce $p$ o non conosce la sua negazione $\neg p$

Abbiamo che, data la semantica che ci interessa, solo la prima e la terza formula sono valide, in quanto sono riformulazioni epistemiche di tautologie proposizionali. La seconda non è valida in quanto l'agente $a$ potrebbe non conoscere $p$ e neppure la sua negata, ovvero avere incertezza su $p$. Anche la quarta formula non è valida in quanto afferma che l'agente $a$conosce $p$ oppure considera $p$ possibile, ma potrebbe darsi che l'agente $a$ conosca la negazione di $p$, rendendo falsa la formula.

Una delle caratteristiche interessanti della logica epistemica è che va oltre la conoscenza fattuale che gli agenti hanno. La conoscenza può riguardare la conoscenza stessa, quindi possiamo scrivere espressioni come $K_a(K_a p \rightarrow K_a q)$: l'agente $a$ sa che se conosce $p$ allora consce anche $q$ (i verbi sapere e conoscere sono usati come sinonimi in questo testo). Le affermazioni sulla conoscenza fattuale vengono anche chiamate di prim'ordine, quelle sulla conoscenza della conoscenza vengono dette di ordine superiore.

Ancora più interessante è la possibilità di modellare la conoscenza degli altri, un aspetto importante quando si ragiona sui protocolli di comunicazione. Supponiamo che Anna conosca un fatto $m$: "Sono incinta". Quindi abbiamo $K_a m$.

Supponiamo che Anna invii questo messaggio via e-mail a Baldo (il padre del bambino) e che Baldo lo legga. Abbiamo quindi $K_a m \wedge K_b m \wedge K_b K_a m$.

Naturalmente sia Anna che Baldo sanno di sapere, ovvero $K_a K_a m \wedge K_b K_b m$. Abbiamo anche $K_a K_b m$? A meno che Anna non abbia informazioni sul fatto che Baldo abbia effettivamente letto il messaggio, non può presumere che l'abbia fatto, quindi abbiamo $\neg K_a K_b m \wedge \neg K_a \neg K_b m$.

Essendo un gentiluomo, Baldo potrebbe rispondere ad Anna dicendo di aver letto il messaggio. A questo punto abbiamo entrambi: $K_a K_b m$ e $K_b K_a m$. Abbiamo anche $K_a K_b K_a m$ (Anna sa che Baldo sa che lei sa, perché Baldo ha risposto a Anna) ma, poiché Baldo non può presumere che Anna abbia letto la conferma, non abbiamo ancora $K_b K_a K_b m$.

A questo punto Anna e Baldo potrebbero prendere il telefono e parlarsi! L'uso del telefono è un buon protocollo che garantisce la conoscenza comune tra Anna e Baldo, ovvero:

$$\begin{array}{l} K_a m \wedge K_b m \ \wedge \\ K_a (K_a m \wedge K_b m) \wedge K_b (K_b m \wedge K_a m) \ \wedge \\ K_a (K_a (K_a m \wedge K_b m) \wedge K_b (K_b m \wedge K_a m)) \wedge \\ K_b (K_a (K_a m \wedge K_b m) \ \wedge K_b (K_b m \wedge K_a m)) \wedge \ldots \end{array}$$

Si noti che la formula della conoscenza comune è infinita e la sua lunghezza cresce in modo esponenziale al crescere dell'ordine della conoscenza. Sviluppando la formula abbiamo 2 congiunzioni al prim'ordine, 4 al second'ordine, 8 al terz'ordine, e in generale $2^n$ all'ordine $n$.

1. Sintassi

2. Semantica

3. Proprietà logiche della conoscenza e delle credenza

4. Conoscenza di gruppo

5. Assiomatizzazione

6. Problemi logici e relativa complessità

7. Limiti dell'approccio logico

Sintassi

La logica modale epistemica estende la logica proposizionale. Il linguaggio della logica proposizionale presuppone un insieme $At$ di proposizioni primitive (o atomiche), tipicamente indicate con $p, q, \ldots$. Esse si riferiscono tipicamente ad affermazioni considerate elementari, cioè prive di struttura logica, come "piove" o "la finestra è chiusa".

La logica proposizionale utilizza gli operatori booleani, come $\neg$ ("non"), $\wedge$ ("e"), $\vee$, ("o"), $\rightarrow$ ("implica") e $\leftrightarrow$ ("se e solo se"), per costruire formule più complesse. Gli unici operatori necessari sono $\neg$e $\wedge$ , infatti:

• $\alpha \vee \beta$ è uguale a $\neg(\neg \alpha \wedge \neg \beta)$
• $\alpha \rightarrow \beta$ è uguale a $\neg \alpha \vee \beta$
• $\alpha \leftrightarrow \beta$ equivale a $(\alpha \rightarrow \beta) \wedge (\beta \rightarrow \alpha)$

Inoltre, definiamo il simbolo vero $\top$ come $p \vee \neg p$ e il simbolo falso $\bot$ come $\neg \top$.

Quando ragioniamo sulla conoscenza, dobbiamo poter fare riferimento al soggetto, cioè all'agente di cui stiamo parlando. Un agente è un'entità umana o artificiale. In IA, tipicamente l'agente è una entità artificiale. Per fare ciò, assumiamo un insieme finito Ag di agenti. Per ragionare sulla conoscenza, aggiungiamo al linguaggio della logica proposizionale gli operatori $K_a$, dove $K_a \varphi$ denota "l'agente $a$ conosce $\varphi$". Sia $Op = \{K_a \ |\ a \in Ag\}$ l'insieme degli operatori di conoscenza per ogni agente. Il duale dell'operatore di conoscenza è $M_a \varphi$ e denota "l'agente $a$ considera possibile $\varphi$"; è definito come $\neg K_a \neg \varphi$.

Siamo pronti a definire il linguaggio della logica modale epistemica $L(At, Ag, Op)$ con la seguente grammatica BNF (Backus-Naur Form):

$$\varphi := p \ | \ \neg \varphi \ | \ (\varphi \wedge \varphi) \ | \ K_a \varphi$$

dove $p \in At$ e $a \in Ag$.

Si noti che una formula è illimitata ma finita. Inoltre, il linguaggio della logica proposizionale è $L(At, \emptyset, \emptyset) = L(At)$ e il linguaggio della logica (uni-)modale è $L(At, \{a\}, \{k_a\})$; nel caso della logica uni-modale $K_a$ è solitamente indicato come $\Box$ e $M_a$ è solitamente indicato come $\Diamond$. Quando c'è più di un agente si parla di logica multimodale.

Semantica

Definiamo ora un modo per determinare sistematicamente il valore di verità di una formula, cioè di dare una semantica al linguaggio modale epistemico. Nella logica proposizionale, il fatto che una proposizione $p$ sia vera o meno dipende dalla situazione in cui ci troviamo. Le situazioni rilevanti sono formalizzate utilizzando le valutazioni, dove una valutazione è una funzione $V \ : \ At \rightarrow \{vero, falso\}$ che determina il valore di verità delle proposizioni primitive.

Una valutazione può essere estesa in modo da determinare la verità di tutte le formule, utilizzando una semplice definizione induttiva:

• $\varphi \wedge \psi$ è vera in $V$ sse sia $\varphi$ che $\psi$ sono vere in $V$;
• $\neg \varphi$ è vera in $V$ sse $\varphi$ è falsa in $V$.

Per modellare la conoscenza utilizziamo idee che risalgono al filosofo finlandese Jaakko Hintikka.

Pensiamo a un agente che considera possibili un certo numero di situazioni diverse, chiamate mondi o stati, che sono coerenti con le informazioni di cui l'agente dispone.

Per esempio, se l'agente sa che oggi è un giorno di fine settimana, allora in un mondo possibile oggi è sabato e in un altro mondo possibile oggi è domenica, ma non esiste un mondo in cui oggi è lunedì.

Quindi ogni agente ha la sua relazione di accessibilità che dice quali mondi sono accessibili (considerati possibili) a partire da un dato mondo.

Diremo che un agente conosce una formula in un mondo se la formula è vera in tutti i mondi che l'agente considera possibili a partire da quel mondo.

Quindi, piuttosto che usare una singola situazione per dare significato alle formule modali, come nella logica proposizionale, usiamo un insieme di tali situazioni; inoltre, in ogni situazione, consideriamo, per ogni agente, quali altre situazioni l'agente considera possibili.

La struttura risultante è un grafo etichettato, chiamato modello di Kripke, dove i nodi sono i mondi e gli archi sono i collegamenti di accessibilità per gli agenti; ogni arco è etichettato con un insieme non vuoto di agenti. Segue un esempio con 4 mondi $\{v, w, s, u\}$ e due agenti ($a$ e $b$).

Un modello di Kripke con 4 mondi e 2 agenti.

Formalmente, dato un insieme $At$ di proposizioni primitive e un insieme $Ag$ di agenti, un modello di Kripke è una struttura $M = (S, R, V)$, dove:

• $S \neq \emptyset$ è un insieme di stati (o mondi);
• $R \ : \ Ag \rightarrow {\cal P}(S \times S)$ è una funzione che per ogni agente $a \in Ag$ restituisce una relazione di accessibilità $R_a \subseteq S \times S$ (un insieme di coppie di stati);
• $V \ : \ S \rightarrow (At \rightarrow \{vero, falso\})$ è una funzione che per ogni stato $s \in S$ restituisce una valutazione delle proposizioni nello stato$s$.

La classe di tutti i modelli di Kripke è indicata con $\cal K$. Una struttura di Kripke $F = (S, R)$ si concentra solo sul grafo sottostante un modello, senza considerare la valutazione.

Siamo pronti a definire la verità di una formula in un modello di Kripke e uno stato del modello. Dato un modello $M = (S, R, V)$ e un mondo $s \in S$, definiamo cosa significa che una formula $\varphi$ è vera in $(M, s)$, scritto $M, s \vDash \varphi$, induttivamente come segue:

• $M, s \vDash p$ sse $V(s)(p) = vero$ per $p \in At$
• $M, s \vDash \varphi \wedge \psi$ sse $M, s \vDash \varphi$ e $M, s \vDash \psi$
• $M, s \vDash \neg \varphi$ sse non vale $M, s \vDash \varphi$ (scritto anche come $M, s \not\vDash \varphi$)
• $M, s \vDash K_a \varphi$ sse $M, t \vDash \varphi$ per ogni $t$ tale che $(s,t) \in R_a$ (scritto anche come $R_a st$)

Si ricordi che $M_a \varphi := \neg K_a \neg \varphi$; segue facilmente che:

• $M, s \vDash M_a \varphi$ sse $M, t \vDash \varphi$ per qualche $t$ tale che $(s,t) \in R_a$

Quindi l'operatore modale $K$ corrisponde ad una quantificazione universale del tipo $\forall x. \varphi(x)$ e il suo duale $M$ corrisponde ad una quantificazione esistenziale del tipo $\exists x. \varphi(x)$.

Infine scriveremo $M \vDash \varphi$ se $M, s \vDash \varphi$ per ogni mondo $s \in S$.

Vediamo un esempio. Anna e Baldo si sono dati appuntamento per la prima volta per un aperitivo, ma, essendo la prima uscita, nessuno sa il numero di telefono dell'altro. Ognuno sa quanto tempo serve per arrivare da casa al luogo dell'incontro, quindi, assumendo che entrambi abbiano un orologio, ognuno è consapevole se sarà puntuale o in ritardo all'appuntamento, ma non potendo comunicare con l'altro, non ha questa informazione per l'altro. Possiamo modellare questa situazione con il modello di Kripke rappresentato in figura, dove le etichette $a$ e $b$ sugli archi indicano rispettivamente la relazione di accessibilità di Anna e Baldo e le proposizioni $t_a$ e $t_b$ indicano rispettivamente che Anna e Baldo sono puntuali (quindi $\neg t_a$ indica che Anna è in ritardo e similmente per Baldo).

La rappresentazione epistemica dell'appuntamento tra Anna e Baldo.

Si noti che, per esempio, se Anna sa di essere puntuale (mondi $w$ e $v$), i mondi possibili per Anna sono quelli in cui Baldo è puntuale ($w$) o in ritardo ($v$). Similmente per Baldo. Inoltre, se Anna sa di essere in ritardo (mondi $s$ e $u$), i mondi possibili per Anna sono quelli in cui Baldo è puntuale ($s$) o in ritardo ($u$). Similmente per Baldo. Ognuno dei quattro mondi rappresenta una delle possibili situazioni di puntualità e ritardo per Anna e Baldo. Si noti che i mondi $w$ e $u$, ad esempio, non sono mutuamente accessibili né per Anna né per Baldo. Infatti, se Anna sa si essere puntuale nel mondo $w$, è inconcepibile per lei il mondo $u$ in cui è in ritardo; d'altronde se Anna sa di essere in ritardo nel mondo $u$ non potrà essere puntuale nel mondo $w$; lo stesso per Baldo.

Valgono le seguenti:

1. $M, w \vDash t_a \wedge t_b$: nel mondo $w$ sia Anna che Baldo sono puntuali
2. $M, w \vDash K_a t_a \wedge K_b t_b$: nel mondo $w$ sia Anna che Baldo sanno che saranno puntuali
3. $M, w \vDash \neg K_b t_a \wedge \neg K_a t_b$: nel mondo $w$ sia Anna che Baldo non sanno se l'altro sarà puntuale. Equivalentemente possiamo scrivere $M, w \vDash M_b \neg t_a \wedge M_a \neg t_b$, ovvero nel mondo $w$ sia Anna che Baldo ritengono possibile che l'altro sia in ritardo
4. $M, w \vDash K_a (K_b t_b \vee K_b \neg t_b)$: nel mondo $w$ Anna sa che Baldo sa se sarà puntuale o in ritardo. D'altronde questo vale indipendentemente dal particolare mondo, quindi è vero in tutti mondi, ossia possiamo scrivere $M \vDash K_a (K_b t_b \vee K_b \neg t_b)$. Si noti che vale anche $M \vDash K_b t_b \vee K_b \neg t_b$, da cui segue la precedente.
5. $M \vDash K_a t_a \vee \neg K_a t_a$: in tutti i mondi Anna sa si essere puntuale oppure non sa di esserlo. Si noti che questa è una tautologia, quindi è vera indipendentemente dal modello, ovvero è vera in tutti i modelli.

Ricordiamo che $\cal{K}$ è la classe di tutti i modelli. Sia $\cal{X} \subseteq \cal{K}$ una classe di modelli e $\varphi$ una formula. Diremo che:

• $\varphi$ è valida in $\cal X$, e scriveremo $\cal{X} \vDash \varphi$, se $M \vDash \varphi$ per ogni modello $M \in \cal{X}$;
• $\varphi$ è soddisfacibile in $\cal X$ se $M, s \vDash \varphi$ per qualche modello $M \in \cal{X}$ e stato $s$ del modello.

Ad esempio, come abbiamo osservato sopra, $K_a t_a \vee M_a \neg t_a$ è una formula valida. Inoltre $K_b t_b \vee K_b \neg t_b$ è soddisfacibile (basta prendere il modello di sopra e un qualunque stato del modello), ma non è valida in $\cal K$, la classe di tutti i modelli. E' facile costruire un modello $M$ in cui esiste un mondo $w$ tale che $t_b$ è vera in alcuni mondi raggiungibili da $w$ e falsa in altri, dunque non è vero che $t_b$ è sempre vera o sempre falsa in tali mondi, dunque $\cal{K} \not\vDash \varphi$. D'altronde se scegliamo $\cal{X} \subseteq \cal{K}$ come la classe dei modelli lineari, ovvero in cui ogni mondo ha esattamente un successore, allora $\cal{X} \vDash \varphi$, cioè $\varphi$ è valida in $\cal X$.

Definiamo infine una serie di classi di modelli in termini di proprietà delle relazioni di accessibilità in tali modelli. Poiché dipendono solo dalla relazione di accessibilità, avremmo potuto definirle anche per le strutture sottostanti; infatti, le proprietà sono talvolta chiamate proprietà delle strutture.

Sia $R$ una relazione di accessibilità su un dominio di stati $S$:

1. Se $R$ non ha alcuna proprietà particolare, indicheremo la relativa classe dei modelli di Kripke con $\cal K$.
2. $R$ è riflessiva se per tutti gli $x$ si ha $Rxx$. La classe dei modelli di Kripke riflessivi è indicata con $\cal KT$.
3. $R$ è simmetrica se per tutti gli $x, y$, se $Rxy$ allora $Ryx$. La classe dei modelli di Kripke simmetrici è indicata con $\cal KB$.
4. $R$ è transitiva se per tutti $x, y, z$, se $Rxy$ e $Ryz$ allora $Rxz$. La classe dei modelli di Kripke transitivi è indicata con $\cal K4$.
5. $R$ è seriale se per tutti gli $x$ esiste un $y$ tale che $Rxy$. La classe dei modelli di Kripke seriali è indicata con $\cal KD$.
6. $R$ è Euclidea se per tutti gli $x, y, z$, se $Rxy$ e $Rxz$ allora $Ryz$. La classe dei modelli di Kripke euclidei è indicata con $\cal K5$.
7. $R$ è una relazione di equivalenza se $R$ è riflessiva, simmetrica e transitiva. La classe dei modelli di Kripke in cui le relazioni sono relazioni di equivalenza è denotata con $\cal KTB4$ e più spesso con $\cal S5$.

Vale che una relazione di equivalenza partiziona l'insieme dei mondi in insiemi non vuoti, disgiunti e la cui unione restituisce l'intero insieme dei mondi.

Mostrare che una relazione riflessiva e Euclidea è una relazione di equivalenza e viceversa. In altri termini, mostrare che $\cal{KTB4} = \cal{KT5}$. Mostrare inoltre che una relazione riflessiva è anche seriale.

Proprietà logiche della conoscenza e della credenza

La classe $\cal S5$ dei modelli associati a relazioni di equivalenza è stata tipicamente usata per modellare la conoscenza. In tal caso la relazione di accessibilità è anche detta relazione di indistinguibilità, in quanto due mondi associati dalla relazione sono indistinguibili in base all'informazione che l'agente ha a disposizione. Ad esempio, se ho la sola informazione che è un giorno del fine settimana, il mondo del Sabato e della Domenica sono indistinguibili.

Vediamo quali sono le formula valide che contraddistinguono la classe dei modelli $\cal S5$ e i sui sovrainsiemi fino alla classe $\cal K$ di tutti i modelli.

Regola della sostituzione delle istanze delle tautologie proposizionali

Se $\varphi$ è una istanza modale di una tautologia proposizionale, allora ${\cal K} \vDash \varphi$.

Ad esempio, dato che $p \vee \neg p$ e $p \rightarrow (q \rightarrow p)$ sono tautologie proposizionali, allora anche le seguenti formule sono sempre valide: $Kp \vee \neg Kp$ e $K(p \vee q) \rightarrow (Kr \rightarrow K(p \vee q))$.

Regola del modus ponens

Se ${\cal K} \vDash \varphi$ e ${\cal K} \vDash \varphi \rightarrow \psi$ allora ${\cal K} \vDash \psi$.

Una delle regole classiche del ragionamento, la storia del modus ponens risale all'antichità: il primo a descriverla esplicitamente fu Teofrasto (371 circa – 287 circa a.C.).

Regola della generalizzazione della conoscenza

Se ${\cal K} \vDash \varphi$ allora ${\cal K} \vDash K \varphi$

Ovvero, gli agenti conoscono tutte le formule valide. Questa regola è anche chiamata regola della necessità (necessitation rule). E' valida per la classe ${\cal K}$ di tutti i modelli.

Assioma di distribuzione della conoscenza

${\cal K} \vDash (K \varphi \wedge K (\varphi \rightarrow \psi)) \rightarrow K \psi$

Questo assioma, tradizionalmente conosciuto come K, stabilisce il modus ponens come regola di inferenza a livello epistemico. E' valido per la classe ${\cal K}$ di tutti i modelli.

Assioma della consistenza

${\cal KD} \vDash K \varphi \rightarrow M \varphi$

Ovvero, se conosco qualcosa, lo ritengo anche possibile.

L'assioma di consistenza, noto come D, è valido per la classe dei modelli seriali ${\cal KD}$.

Mostrare che:

1. se un modello è seriale, allora D è vero in tutti i suoi mondi

2. se un modello non è seriale, allora D non è vero in almeno un mondo (più precisamente, dato un frame $F = (S,R)$ non seriale esiste una valutazione $V$tale che D non è vero in almeno un mondo del modello $M = (S, R, V)$)

L'assioma D è equivalente a $K \varphi \rightarrow \neg K \neg \varphi$: se conosco qualcosa, non posso conoscere anche il suo contrario. Ovvero sono consistente. Esso è anche equivalente a $\neg K \bot$, cioè non conosco il falso, o equivalentemente $M \top$, cioè credo nel vero.

Assioma della verità

${\cal KT} \vDash K \varphi \rightarrow \varphi$

Questo assioma, noto anche come T, dice che se un agente conosce dei fatti, questi devono essere veri (nel mondo corrente). Esso può essere espresso anche nella sua contrapposizione: $\varphi \rightarrow \neg K \neg \varphi$, ovvero se qualcosa è vero nel mondo corrente non posso conoscere il suo contrario. L'assioma T è valido per la classe dei modelli riflessivi ${\cal KT}$.

Mostrare che:

1. se un modello è riflessivo, allora T è vero in tutti i suoi mondi

2. se un modello non è riflessivo, allora T non è vero in almeno un mondo

L'assioma di verità è spesso considerato la principale caratteristica che distingue la conoscenza (knowledge) dalla credenza (belief). Come vedremo, nella logica doxastica l'assioma di verità T è sostituito dall'assioma di coerenza D.

L'assioma di introspezione positiva

${\cal K4} \vDash K \varphi \rightarrow KK\varphi$

Questa proprietà e la successiva affermano che un agente ha introspezione sulla propria conoscenza. L'assioma dell'introspezione positiva 4 dice specificamente che un agente sa di sapere ciò che sa: se conosco qualcosa, so di conoscerlo.

Equivalentemente, questo assioma dice che un agente non sa ciò che non sa di sapere: $\neg K K \varphi \rightarrow \neg K\varphi$

Questo assioma è valido per la classe dei modelli transitivi ${\cal K4}$.

Mostrare che:

1. se un modello è transitivo, allora 4 è vero in tutti i suoi mondi

2. se un modello non è transitivo, allora 4 non è vero in almeno un mondo

L'assioma di introspezione negativa

${\cal K5} \vDash \neg K \varphi \rightarrow K \neg K\varphi$

L'assioma dell'introspezione negativa, noto anche come assioma 5, dice che un agente sa di non sapere ciò che non sa: se non conosco qualcosa, so di non conoscerlo.

Equivalentemente, questo assioma dice che un agente sa ciò che non sa di non sapere: $\neg K \neg K \varphi \rightarrow K\varphi$

Questo assioma è valido per la classe dei modelli euclidei ${\cal K5}$.

Mostrare che:

1. se un modello è euclideo, allora 5 è vero in tutti i suoi mondi

2. se un modello non è euclideo, allora 5 non è vero in almeno un mondo

L'assioma della simmetria

${\cal KB} \vDash \varphi \rightarrow K M \varphi$

L'assioma di simmetria, noto anche come assioma B, dice che se qualcosa è vero, allora un agente sa di ritenerlo possibile.

Equivalentemente, questo assioma dice che se un agente ritene possibile di conoscere qualcosa, allora quel qualcosa è vero: $M K \varphi \rightarrow \varphi$

Questo assioma è valido per la classe dei modelli simmetrici ${\cal KB}$.

Mostrare che:

1. se un modello è simmetrico, allora B è vero in tutti i suoi mondi

2. se un modello non è simmetrico, allora B non è vero in almeno un mondo

Si noti che se $\cal{X}$ e $\cal{Y}$ sono insiemi di modelli e $\cal{X} \subseteq \cal{Y}$, allora ${\cal Y} \vDash \varphi$ implica ${\cal X} \vDash \varphi$. Dato che una relazione di equivalenza è per definizione riflessiva, simmetrica e transitiva, e inoltre è Euclidea e seriale, allora la classe di modelli ${\cal S5}$, eredita tutti gli assiomi elencati in questa sezione, che quindi potremmo definire gli assiomi della conoscenza.

Conoscenza e credenza

${\cal S5} = \cal{KT45}$ è spesso definita la logica della conoscenza, caratterizzata da:

1. l'assioma della verità T (che cattura la riflessività dei modelli)

2. l'assioma dell'introspezione positiva 4 (che cattura la transitività dei modelli)

3. l'assioma dell'introspezione negativa 5 (che cattura l'essere Euclideo dei modelli)

Come abbiamo detto, 4 è ridondante in $\cal S5$ dato che una relazione riflessiva e Euclidea è anche transitiva.

La logica della credenza, detta anche logica doxastica, è invece spesso rappresentata da $\cal KD45$ ed è quindi caratterizzata da:

1. l'assioma della coerenza D (che cattura la serialità dei modelli)

2. l'assioma dell'introspezione positiva 4 (che cattura la transitività dei modelli)

3. l'assioma dell'introspezione negativa 5 (che cattura l'essere Euclideo dei modelli)

In questo caso l'assioma 4 è necessario. La differenza tra credere e conoscere sta dunque nell'assioma della verità T, presente nella conoscenza, che è sostituito con quello della coerenza D per catturare la credenza.

Dato che una relazione simmetrica è anche seriale, accettare l'assioma della verità implica accettare anche quello della coerenza. In altri termini sia la conoscenza che la credenza sono coerenti, ovvero non posso conoscere e non posso credere in una contraddizione (il falso). Inoltre, la conoscenza è più forte della credenza: se conosco un fatto allora credo in quel fatto. Ma non vale il viceversa: posso credere in qualcosa che non conosco. Tipicamente la conoscenza si associa al rigore (scientifico o matematico). Ad esempio conosco che la terra è sferica o che esistono infiniti numeri primi. La credenza è una modalità più debole e in generale posso credere in qualsiasi cosa che non sia una palese contraddizione. Ad esempio posso credere nell'esistenza della materia oscura o nel fatto che ogni numero pari maggiore di 2 sia la somma di due numeri primi (congettura di Goldbach). Ma non posso credere che la terra sia piatta o che esista un numero primo maggiore di tutti gli altri primi.

Se volessimo rappresentare entrambe le modalità, conoscenza $K_a$ e credenza $B_a$ per ogni agente $a$ nello stesso linguaggio modale, occorre fare attenzione a come costruire i modelli di Kripke. Come abbiamo visto, le relazioni di accessibilità $R_{a}^{K}$ associate alla conoscenza e $R_{a}^{B}$ associate alla credenza hanno proprietà strutturali diverse (per esempio una è riflessiva e l'altra solo seriale), dunque vanno tenute distinte. Fissata la modalità, ovvero conoscenza o credenza, le relazioni di accessibilità per ogni agente hanno invece le stesse proprietà strutturali (godono degli stessi assiomi), ma naturalmente possono differire nello specifico una volta che queste proprietà sono soddisfatte.

Conoscenza di gruppo

Nella vita ordinaria, ragioniamo su ciò che gli altri sanno. In particolare, ci preoccupiamo di ciò che gli altri sanno (o credono) di noi, e spesso in modo specifico di ciò che loro sanno di ciò che noi sappiamo.

Anna sa che Baldo sa che lei è incinta? Baldo sa questo?

La logica epistemica può rivelare interessanti caratteristiche epistemiche dei sistemi che coinvolgono gruppi di agenti. In alcuni casi, ad esempio, i fenomeni sociali emergenti dipendono dal fatto che gli agenti ragionano in modi particolari sulla conoscenza e sulle credenze di altri agenti.

Ad esempio, gli automobilisti sanno che un semaforo rosso indica che devono fermarsi a un incrocio. Tuttavia, affinché la convenzione dei semafori funzioni, è necessario che gli automobilisti sappiano che anche gli altri automobilisti sanno che il rosso significa stop. Il ruolo convenzionale dei semafori si basa sul fatto che tutti gli automobilisti sanno che tutti gli automobilisti conoscono la regola, ovvero che la regola è un elemento di conoscenza comune.

Vi sono tre tipi di conoscenza di gruppo: distribuita, mutua e comune. Facciamo un esempio. Il docente mantiene un canale Discord dove partecipano gli studenti del corso. Per premiare gli studenti per il loro impegno ha deciso di creare un wallet bitcoin, depositare alcuni fondi, e condividere con gli studenti la relativa seed phrase (SP) del wallet. Può condividere la SP in diversi modi:

1. suddivide la stringa della SP in tanti pezzi quanti sono gli studenti e invia in privato un pezzo ad ogni studente;

2. confida ad ogni studente in privato l'intera SP;

3. pubblica la SP sul canale Discord in modo che tutti la vedano.

Le tre conoscenze sono diverse:

• nel primo caso la SP è conoscenza distribuita. Ovvero se tutti gli studenti mettono assieme la loro conoscenza, ottengono la chiave d'accesso. Ma nessuno individualmente conosce la SP. Una volta prelevati i fondi, possono decidere come spartirseli (ad esempio in parti uguali o sorteggiando un vincitore);

• nel secondo caso la SP è conoscenza mutua. Ogni studente conosce interamente la SP, ma non sa che gli altri la conoscono. Ad esempio, se la ricompensa andasse solo al primo che riesce ad accedere al wallet prelevando i fondi, in tal caso gli studenti non avrebbero fretta di prelevare i fondi, non sapendo di essere in competizione;

• nel terzo caso la SP è conoscenza comune. Tutti sanno la SP e tutti sanno che tutti sanno la SP e così via all'infinito. Nel caso di competizione per la ricompensa, gli studenti si affretterebbero a prelevare i fondi, sapendo di essere in competizione con gli altri.

Si noti che la conoscenza mutua implica quella distribuita: se un agente del gruppo conosce qualcosa allora lo può distribuire al gruppo. Inoltre, la conoscenza comune implica quella mutua: se il gruppo ricorsivamente conosce qualcosa allora ogni agente del gruppo la conosce direttamente.

Conoscenza distribuita

La conoscenza distribuita è la conoscenza che un gruppo di agenti avrebbe se condividesse l'informazione che ognuno possiede. Gli agenti di un gruppo $G$ conoscono in modo distribuito $\varphi$ se un ipotetico agente saggio che avesse tutta la conoscenza degli agenti del gruppo conosce $\varphi$.

Definiamo il nuovo operatore modale $D_G$ per la conoscenza distribuita. La formula $D_G \varphi$ si legge: $\varphi$ è conoscenza distribuita tra il gruppo di agenti in $G$.

L'operatore $D_G$ ha semantica sull'intersezione delle relazioni di accessibilità degli agenti in $G$. L'idea è che se anche solo uno degli agenti esclude che un mondo sia accessibile dal mondo corrente, allora tale sarà per l'intero gruppo. Sia dunque:

$$R_{G}^{D} = \bigcap_{a \in G} R_a$$

Consideriamo l'esempio in figura:

Nell'esempio di sopra, solo i tre cappi sui nodi appartengono alla relazione $R_{G}^{D}$, con $G = \{a,b\}$.

La semantica dell'operatore $D_G$ è quindi:

$M, s \vDash D_G \varphi$ sse $M, t \vDash \varphi$ per ogni $t$ tale che $(s, t) \in R_{G}^{D}$

Nell'esempio di sopra, vale che $w_1 \vDash D_G \, p$ e $w_2 \vDash D_G \, p$ con $G = \{a,b\}$.

Conoscenza mutua

Gli agenti di un gruppo $G$ conoscono in modo mutuo $\varphi$ se tutti gli agenti del gruppo conoscono singolarmente $\varphi$. La conoscenza mutua è un sottoinsieme di quella distribuita: conoscere mutuamente qualcosa implica che la si conosce anche in modo distribuito ma non vale il viceversa.

Possiamo quindi definire un nuovo operatore di conoscenza mutua $E_G$ (everybody knows) definito nel seguente modo:

$$E_G \varphi := \bigwedge_{a \in G} K_a \varphi$$

La formula $E_G \varphi$ is legge: $\varphi$ è mutuamente conosciuta da tutti gli agenti del gruppo $G$. Nell'esempio di sopra, se $G = \{a,b\}$, allora vale che $w_1 \vDash E_G \, p$ ma $w_2 \not\vDash E_G \, p$, in quanto $w_2 \not\vDash K_a \, p$.

Conoscenza comune

Il fatto che tutti gli agenti di un gruppo conoscano un fatto in prim'ordine non significa the conoscano quel fatto con un ordine superiore di conoscenza. Gli agenti di un gruppo $G$ conoscono in modo comune $\varphi$ se ognuno conosce $\varphi$ e ognuno sa che sé stesso e gli altri agenti conoscono $\varphi$ e così via ab infinitum. In altri termini, usando una definizione ricorsiva:

$\varphi$ è conoscenza comune se tutti gli agenti conoscono $\varphi$ e tutti gli agenti ricorsivamente sanno che $\varphi$ è conoscenza comune.

La conoscenza comune è dunque la più restrittiva tra quelle analizzate ed in particolare è un sottoinsieme di quella mutua (e quindi anche di quella distribuita). Nell'esempio di sopra, vale che $w_1 \vDash K_a p \wedge K_b p$ ma $w_1 \not\vDash K_b K_a p$.

Potremmo pensare di definire l'operatore modale di conoscenza comune $C_G$ in termini di quello di conoscenza mutua $E_G$ come segue:

$$C_G \varphi := \bigwedge_{k \geq 0} E_{G}^{k} \varphi$$

dove $E_{G}^{k}$ indica $k$ applicazioni di $E_{G}$, ovvero:

• $E_{G}^{0} \varphi = \varphi$
• per $k > 0$, $E_{G}^{k} \varphi = E_G E_{G}^{k-1}\varphi$

Ad esempio, se $G = \{a,b\}$, allora:

$$\begin{array}{l} E_{G}^{2} \,\varphi = E_{G} E_{G} \varphi = E_G (K_a \varphi \wedge K_b \varphi) = \\ K_a (K_a \varphi \wedge K_b \varphi) \wedge K_b (K_a \varphi \wedge K_b \varphi) = \\ K_a K_a \varphi \wedge K_a K_b \varphi \wedge K_b K_a \varphi \wedge K_b K_b \varphi \end{array}$$

dove nell'ultimo passaggio abbiamo usato la proprietà distributiva del quantificatore universale $K$ rispetto alla congiunzione $\wedge$.

Questa definizione di conoscenza comune è però problematica, in quanto la formula con cui abbiamo definito $C_G \varphi$ è infinita, mentre il nostro linguaggio modale contiene solo formule finite. Procediamo dunque in modo diverso. Definiamo una nuova relazione di accessibilità per la conoscenza comune come la chiusura riflessiva e transitiva dell'unione delle relazioni di accessibilità degli agenti del gruppo, ovvero:

$$R_{G}^{C} = (\bigcup_{a \in G} R_a)^*$$

Data una relazione $R$, la sua chiusura riflessiva e transitiva

$$R^* = \bigcup_{k \geq 0} R^k$$

dove:

• $(s, t) \in R^0$ sse $s = t$
• per $k > 0$, abbiamo che $(s, t) \in R^{k}$ sse esiste $r$ tale che $(s, r) \in R$ e $(r, t) \in R^{k-1}$

In termini topologici, $R^{k}$ rappresenta la relazione cammino di lunghezza $k$ e $R_{G}^{C}$ è la relazione cammino di lunghezza arbitraria sul grafo che contiene l'unione delle relazioni degli agenti nel gruppo $G$, ovvero un mondo $t$ è accessibile da un mondo $s$ attraverso $R_{G}^{C}$ se esiste un cammino - una sequenza di nodi uniti da archi - di lunghezza finita (possibilmente nulla) da $s$ a $t$ sul grafo formato dalle relazioni degli agenti nel gruppo $G$.

La semantica dell'operatore $C_G$ è quindi:

$M, s \vDash C_G \varphi$ sse $M, t \vDash \varphi$ per ogni $t$ tale che $(s, t) \in R_{G}^{C}$

Nell'esempio di sopra, vale che $w_1 \not\vDash C_G p$ dato che $w_3$ è raggiungibile da $w_1$ attraverso un cammino di lunghezza 2 che passa prima per un arco di $b$ e poi un arco di $a$; inoltre in $w_3$ non vale $p$. In altri termini, $w_1 \not\vDash K_b K_a p$.

E' facile mostrare che la seguente formula, che caratterizza la gerarchia tra le conoscenze di gruppo, è valida in tutti i modelli per ogni agente $a \in G$ e formula $\varphi$:

$$(C_G \varphi \rightarrow E_G \varphi) \wedge (E_G \varphi \rightarrow K_a \varphi) \wedge (K_a \varphi \rightarrow D_G \varphi)$$

Assiomatizzazione

Finora la formalizzazione del ragionamento è stata definita in base alla nozione di verità: ${\cal X} \vDash \varphi$ significa che $\varphi$ è vera in tutti i modelli di $\cal X$.

In questa sezione, discutiamo una forma di ragionamento in cui una conclusione è inferita puramente sulla base della sua forma sintattica. Sebbene esistano diversi modi per farlo, nella logica epistemica il modo più diffuso per definire l'inferenza deduttiva è la definizione di un sistema di assiomi alla Hilbert. Tali sistemi forniscono una nozione molto semplice di prova formale. Alcune formule sono valide a priori solo perché hanno una certa forma sintattica. Questi sono gli assiomi del sistema. Le regole del sistema dicono che si può concludere che una formula è un valida perché altre formule sono valide.

Cominciamo col definire un sistema assiomatico di base chiamato K su un linguaggio modale $L = L(At, Op, Ag)$ con $Op = \{K_a \ | \ a \in Ag\}$.

1. Assioma 1. Tutte le istanze di sostituzione delle tautologie proposizionali

2. Assioma K. $(K_a \varphi \wedge K_a (\varphi \rightarrow \psi)) \rightarrow K_a \psi$ per ogni $a \in Ag$
3. Regola MP (modus ponens). Da $\varphi$ e $\varphi \rightarrow \psi$ deriva $\psi$
4. Regola Nec (regola della necessità). Da $\varphi$ deriva $K_a \varphi$ per ogni $a \in Ag$

Una prova formale (detta anche dimostrazione o derivazione) è un elenco di formule, dove ogni formula è un assioma del sistema o può essere ottenuta applicando una regola di inferenza del sistema alle formule che si trovano prima nell'elenco. Una prova di $\varphi$ è una derivazione la cui ultima formula è $\varphi$. Se esiste una prova di $\varphi$ nel sistema di assiomi K diremo che $\varphi$ è un teorema di K e scriveremo $\mathbf{K} \vdash \varphi$.

La seguente figura mostra un esempio di prova in K per il seguente teorema:

$$\mathbf{K} \vdash K_a (\varphi \wedge \psi) \rightarrow (K_a \varphi \wedge K_a \psi)$$

La dimostrazione del teorema

Si noti che la tautologia al passo 9 è della forma: $(\alpha \rightarrow \beta) \rightarrow ((\alpha \rightarrow \gamma) \rightarrow (\alpha \rightarrow (\beta \wedge γ)))$. Questo teorema può essere usato, assieme agli assiomi e alle regole del sistema logico, per dimostrarne altri. Osserviamo che questo teorema è anche una formula valida nella classe $\cal X$ di tutti i modelli di Kripke. Infatti, la quantificazione universale $K_a$ distribuisce rispetto alla congiunzione $\wedge$: se in ogni mondo accessibile valgono entrambe $\varphi$ e $\psi$, allora in ogni mondo accessibile vale $\varphi$ e inoltre in ogni mondo accessibile vale $\psi$. Quindi possiamo anche scrivere:

$$\cal{K} \vDash K_a (\varphi \wedge \psi) \rightarrow (K_a \varphi \wedge K_a \psi)$$

Questa corrispondenza tra sintassi e semantica, ovvero tra derivabilità (mediante una prova, o proof-theoretic) e validità (su una classe di modelli, o model-theoretic), è una delle proprietà fondamentali di un sistema logico. In particolare, se $L$ è un linguaggio, $\cal X$ una classe di modelli, e X un sistema di assiomi, diremo che:

1. X è corretto (sound in Inglese) rispetto a $\cal X$ e $L$ se ogni teorema in X è una formula valida in $\cal X$, ovvero $\mathbf{X} \vdash \varphi$ implica $\cal{X} \vDash \varphi$;
2. X è completo (complete in Inglese) rispetto a $\cal X$ e $L$ se ogni formula valida in $\cal X$ è un teorema in X, ovvero $\cal{X} \vDash \varphi$ implica $\mathbf{X} \vdash \varphi$.

Possiamo estendere il sistema logico K con altri assiomi per la conoscenza e la credenza, in particolare:

1. T: $K_a \varphi \rightarrow \varphi$ (riflessività)
2. D: $M_a \top$ (serialità)
3. B: $\varphi \rightarrow K_a M_a \varphi$ (simmetria)
4. 4: $K_a \varphi \rightarrow K_a K_a \varphi$ (transitività)
5. 5: $\neg K_a \varphi \rightarrow K_a \neg K_a \varphi$ (proprietà Euclidea)

Ad esempio, indicheremo con KT il sistema logico che estende K con T e KT5 il sistema logico che estende K con T e 5.

Fissato il linguaggio della logica epistemica $L = L(At, Op, Ag)$ con $Op = \{K_a \ | \ a \in Ag\}$ vale che:

1. K è corretto e completo rispetto a $\cal K$ (qualsiasi modello)
2. KT è corretto e completo rispetto a $\cal KT$ (modelli riflessivi)
3. KD è corretto e completo rispetto a $\cal KD$ (modelli seriali)
4. KB è corretto e completo rispetto a $\cal KB$ (modelli simmetrici)
5. K4 è corretto e completo rispetto a $\cal K4$ (modelli transitivi)
6. K5 è corretto e completo rispetto a $\cal K5$ (modelli Euclidei)

Questi risultati si estendono ad ogni combinazione di assiomi, ad esempio il sistema S5, ovvero KT5, è corretto e completo rispetto ai modelli con relazione di equivalenza $\cal S5$.

La dimostrazione della correttezza è semplice: basta dimostrare che gli assiomi del sistema logico sono validi e poi per induzione che il processo di dimostrazione che usa le regole logiche preserva la validità. Dimostrare la completezza è un po' più difficile. Esistono diversi approcci, ma quello comune consiste nel dimostrare che se una formula non è dimostrabile, allora esiste un modello in cui è falsa. Esiste un modello speciale, chiamato modello canonico, che lo dimostra simultaneamente per tutte le formule.

Possiamo anche definire assiomi per la conoscenza di gruppo, ovvero per i due operatori $C_G$ (conoscenza comune) e $D_G$ (conoscenza distribuita) per cui abbiamo dovuto introdurre nuove relazioni di accessibilità.

Per quanto riguarda la conoscenza distribuita basta introdurre come minimo un assioma che afferma che la conoscenza dei singoli agenti è conoscenza distribuita: $K_a \varphi \rightarrow D_G \varphi$ per ogni $a \in G$. Altri assiomi, ad esempio quello della riflessività, possono essere introdotti per caratterizzare ulteriormente la relazione di accessibilità.

Per la conoscenza comune, occorre aggiungere un assioma e una regola:

1. Assioma Fix: $C_G \varphi \rightarrow E_G(\varphi \wedge C_G \varphi)$
2. Regola Ind: Da $\varphi \rightarrow E_G (\varphi)$ segue $\varphi \rightarrow C_G \varphi$

L'assioma del punto fisso Fix dice che la conoscenza comune può essere vista come il punto fisso di un'equazione: la conoscenza comune di $\varphi$ è valida se tutti sanno sia che $\varphi$ è valida sia che $\varphi$ è, ricorsivamente, una conoscenza comune.

Ind è chiamata regola di induzione e può essere utilizzata per derivare la conoscenza comune induttivamente. Se è vero che $\varphi$ è "evidente", nel senso che se è vera, allora tutti la conoscono (ad esempio perché la scriviamo in un posto dove tutti la possono leggere), allora possiamo dimostrare per induzione che se $\varphi$ è vera, allora lo è anche $E_{G}^{k} (\varphi)$ per tutti i $k \geq 0$, ma questo significa che $C_G \varphi$ è vera. Sebbene la conoscenza comune sia stata definita come un operatore infinito, un po' sorprendentemente questi assiomi e regole finite la caratterizzano completamente.

Problemi logici e relativa complessità

Dato un linguaggio $L$ e una classe di modelli $\cal X$, possiamo indagare almeno i seguenti problemi:

1. Soddisfacibilità: Data una formula $\varphi \in L$, verificare se esiste un modello $M \in \cal{X}$ e un mondo $w$ del modello $M$ tale che $M, w \vDash \varphi$
2. Validità: Data una formula $\varphi \in L$, verificare se per tutti i modelli $M \in \cal{X}$ e per ogni mondo $w$ del modello $M$ vale che $M, w \vDash \varphi$
3. Verifica di modello (model checking): Data una formula $\varphi \in L$, un modello $M \in \cal{X}$ e un mondo $w$ del modello $M$, verificare se $M, w \vDash \varphi$

Il campo della complessità computazionale si occupa della questione della quantità di risorse necessarie per risolvere un problema specifico. Le risorse di maggiore interesse sono il tempo di calcolo e lo spazio di memoria. La complessità computazionale pone quindi domande del tipo: se il mio input aumentasse di dimensione, quanto spazio e tempo in più sarebbero necessari per calcolare la risposta? Formulare la domanda in questo modo presuppone già che il problema in questione possa essere risolto in tempo finito con un algoritmo, cioè che il problema sia decidibile (si noti che esistono problemi indecidibili). Fortunatamente, questo è il caso dei problemi elencati sopra.

Per ragionare sulla complessità di un algoritmo, distinguiamo varie classi di complessità. Se un algoritmo deterministico può risolvere un problema in un tempo polinomiale rispetto alla dimensione dell'input, si dice che il problema è in P. E' possibile mostrare che il problema del model checking per la logica modale epistemica (con molti agenti) è polinomiale.

La classe NP è la classe dei problemi risolvibili da un algoritmo non deterministico in tempo polinomiale. Un algoritmo non deterministico è in un certo senso molto più potente di uno deterministico, perché può indagare in parallelo una pluralità di possibili scelte. Se immaginiamo queste scelte rappresentate da una struttura ad albero, un algoritmo deterministico deve percorrere una dopo l'altro, ovvero sequenzialmente, i cammini di scelta, mentre un algoritmo non deterministico li elabora in modo parallelo.

La soddisfacibilità della logica proposizionale è un esempio di problema in NP: un algoritmo non deterministico di soddisfacibilità prima sceglie una tra le tante assegnazioni di verità per le proposizioni primitive e poi verifica che la formula sia effettivamente vera sotto questa assegnazione di verità.

Un problema che è difficile almeno come qualsiasi problema in NP è detto NP-hard. Un problema è NP-completo se è sia in NP che NP-hard; è noto che il problema della soddisfacibilità per la logica proposizionale è NP-completo. Queste definizioni si generalizzano a tutte le classi di complessità.

Nessuno ha ancora dimostrato se P = NP o meno. La congettura corrente è che P sia un sottoinsieme stretto di NP (si noti infatti che ogni problema polinomiale in modo deterministico è anche polinomiale in maniera non deterministica). I problemi NP-completi sono dunque considerati problemi difficili da risolvere, ovvero con complessità più che polinomiale e tipicamente utilizzano un tempo esponenziale rispetto alla dimensione dell'input.

Infine, PSPACE è la classe dei problemi risolvibili usando spazio polinomiale rispetto alla dimensione dell'input e EXPTIME è la classe dei problemi risolvibili in un tempo esponenziale rispetto alla dimensione dell'input. Si sa che:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

Abbiamo che:

1. Il problema della soddisfacibilità per le logiche della conoscenza e della credenza per un solo agente, $\cal S5$ e $\cal KD45$, è esattamente difficile come il problema della soddisfacibilità per la logica proposizionale, ovvero NP-completo;
2. Il caso generale multi-agente (senza conoscenza comune) è PSPACE-completo;

3. Il caso generale multi-agente con conoscenza comune è EXPTIME-completo.

La complessità del problema della validità è equivalente a quella della soddisfacibilità.

Mostriamo infine che il problema del model checking per la logica epistemica ha complessità polinomiale, in particolare lineare nel prodotto della lunghezza della formula da verificare e la dimensione del modello. La seguente procedura implementa un model checker per la logica epistemica multi-agente. L'idea è di etichettare ogni mondo del modello con le sotto-formule della formula da verificare che sono vere in quel mondo, partendo dalle variabili proposizionali e incrementando progressivamente la dimensione della sotto-formula fino ad arrivare alla formula da verificare.

Sia $n = |S|$ il numero di mondi del modello, $m = |\bigcup_a R_a|$ il numero di archi del modello e $k$ la lunghezza della formula $\alpha$, ovvero il numero di operatori più il numero di proposizioni presenti della formula. Si noti che il numero di sottoformule in $Sub(\alpha)$ è $k$. Quindi, il ciclo principale della procedura viene eseguito per $k$ volte. I casi booleani costano $O(n)$ e il caso modale costa $O(n + m)$. Pertanto, la complessità del model checking risulta $O(k \cdot (n + m))$ nel caso peggiore. La complessità è dunque lineare nel prodotto della lunghezza della formula e della dimensione del modello.

Si consideri il modello su un solo agente anonimo $M = (S, R, V)$ con:

• $S = \{a,b,c,d\}$
• $R = \{(a,b), (b,a), (b,c), (c,b), (c,d), (d,c), (d,a), (a,d)\}$ (un quadrato simmetrico)
• $V(a) = \emptyset$, $V(b) = \{p\}$, $V(c) = \{q\}$, $V(d) = \{p,q\}$.

Si consideri inoltre la formula $\alpha = K p \wedge M \neg q$. Usando l'algoritmo del model checking, etichettare ogni stato del modello con le sottoformule di $\alpha$ vere in quello stato e infine identificare gli stati in cui $\alpha$ è vera.

Limiti dell'approccio logico

L'approccio logico ha dei limiti pratici e concettuali. Come abbiamo visto, ragionare con la logica epistemica è un problema computazionalmente difficile, in particolare se deve essere affrontato in tempo reale. Solo la verifica di modello, infatti, è un problema trattabile computazionalmente. Viceversa, verificare se un formula è un teorema (è valida) ha complessità esponenziale nella lunghezza della formula. Se la formula è moderatamente lunga, o peggio se è dinamica e cresce in lunghezza nel tempo, la complessità del ragionamento logico diventa proibitiva.

Da un punto di vista concettuale, occorre tenere presente che gli assiomi della conoscenza sono idealizzazioni e, in effetti, i logici non sostengono che siano validi per tutte le possibili interpretazioni della conoscenza. Vediamo alcune criticità.

È umano affermare un giorno di conoscere un certo fatto, per poi ritrovarsi ad ammettere il giorno dopo di essersi sbagliati, il che mette in crisi l'assioma T - $K \varphi \rightarrow \varphi$ - che afferma che se un agente conosce un fatto allora questo è vero.

Anche l'introspezione positiva è stata considerata problematica. L'assioma 4 - $K \varphi \rightarrow KK\varphi$ - afferma che se un agente sa un fatto allora sa di saperlo. Ma, ad esempio, si consideri un allievo a cui viene posta una domanda di cui non conosce la risposta. Può darsi che, ponendo altre domande, l'allievo sia in grado di rispondere prima o poi alla domanda originale. A quanto pare, l'allievo conosceva la risposta, ma non era consapevole di saperlo, quindi non sapeva di conoscere la risposta.

L'assioma più discutibile è quello dell'introspezione negativa, ovvero 5 - $\neg K \varphi \rightarrow K \neg K\varphi$ - che afferma che se non conosco un fatto, so di non saperlo. È possibile che un lettore di questo corso non sappia (ancora) cos'è una rete neurale ricorrente, ma prima di leggere questa frase sapeva di non saperlo? Questi esempi suggeriscono che una ragione dell'ignoranza può essere la mancanza di consapevolezza.

Si potrebbe sostenere che gli assiomi "problematici" per la conoscenza dovrebbero essere semplicemente omessi, o forse indeboliti, per ottenere un sistema appropriato per la conoscenza. Ma che dire dei principi fondamentali della logica modale, l'assioma K e la regola di inferenza Nec? Quanto sono accettabili per la conoscenza? Come ci si potrebbe aspettare, non dobbiamo dare nulla per scontato.

L'assioma K di distribuzione della conoscenza - $(K \varphi \wedge K (\varphi \rightarrow \psi)) \rightarrow K \psi$ - presuppone ragionatori perfetti, in grado di inferire le conseguenze logiche della loro conoscenza. Può accadere di conoscere dei fatti ma di non averli messi in relazione, e quindi di non aver dedotto una conseguenza. Per esempio, questo assioma implica che, sotto alcune lievi ipotesi, un agente sa che giorno della settimana sarà il 26 luglio 5018. Per rispondere a questa domanda è sufficiente che (1) l'agente conosca la data di oggi e quale giorno della settimana è oggi, (2) conosca le regole per l'assegnazione delle date, il calcolo degli anni bisestili e così via (tutto ciò può essere codificato come assiomi in una logica epistemica con l'appropriato insieme di proposizioni primitive). Applicando K a questo insieme di fatti, ne consegue che l'agente deve sapere oggi che giorno della settimana sarà il 26 luglio 5018.

La regola Nec della necessità afferma che se $\varphi$ è valida allora lo è anche $K \varphi$. La necessità presuppone che gli agenti possano inferire tutti i teoremi del sistema logico. Poiché dire se una formula è valida è computazionalmente difficile, questo non sembra così plausibile. Questa idealizzazione è spesso riassunta come onniscienza logica: il nostro agente conoscerebbe tutto ciò che è logicamente deducibile.

In sostanza, il problema è che agenti finiti, biologici o artificiale, sono vincolati da limiti alle loro capacità cognitive e di ragionamento. L'approccio della logica epistemica e doxastica sembra invece implicare abilità sovrumane come la conoscenza di tutte le tautologie. Pertanto, la preoccupazione è che queste logiche siano semplicemente inadatte a catturare la conoscenza e la credenza reali, così come queste nozioni figurano nella vita umana ordinaria.

Curiosamente, il fatto che, nella realtà, gli agenti non siano ragionatori ideali, né logicamente onniscienti, è talvolta una caratteristica sfruttata dai sistemi computazionali. La crittografia, ad esempio, è utile perché gli intrusi artificiali o umani, a causa delle loro capacità limitate, non sono in grado di calcolare i fattori primi di un grande numero in un tempo ragionevole.

Nonostante questi problemi, le proprietà della logica della conoscenza si sono dimostrare essere un'utile idealizzazione della conoscenza per molte applicazioni nel campo dei sistemi distribuiti e dell'economia.