05. Logiche non monotone

A che servono le logiche non monotone?

Le logiche non monotone permettono di gestire le conoscenze ritrattabili in modo agevole.
Un essere umano normalmente ha tanta conoscenza di tipo tassonomico (gerarchico, conoscenza organizzata in classi).

Ad esempio sappiamo che gli uccelli volano.

bird(x) -> flies(x) //sappiamo che gli uccelli volano.

Tuttavia ci sono delle eccezioni come i pinguini, e quindi la nostra regola logica diventa:
bird(x), not abnormal(x) -> flies(x) //le virgole sono usate al posto degli and.

Questa regola si legge così: se c'è un'evidenza chiara che l'uccello x non sia anormale, allora volerà.

Problema del frame, problema di ramificazione, problema di qualificazione

Continuiamo ad aggiungere regole:

ostrich(x) -> bird(x), not flies (x) //se x è uno struzzo è un uccello ma non vola.
ostrich(x) -> abnormal(x)

Supponiamo di trovare uno struzzo che vola, come ritraiamo la conoscenza in questo caso? Cioè come facciamo a modificare la conoscenza acquisita fino a quel momento?
Questa questione fa sorgere alcuni problemi:
  • Posto che ho evidenza di fatti che vanno contro alcune delle regole nel bagaglio della conoscenza acquisita fino a quel momento, quanta di questa conoscenza rimane valida? (Problema del frame , forma di resilienza o resistenza della conoscenza acquisita rispetto alla nuova conoscenza)
  • Come identifico la parte di conoscenza soggetta a cambiamento in base ai nuovi dati? (problema di ramificazione)
  • Siamo sicuri che i nuovi dati portino davvero nuova conoscenza? Cioè che le cose stanno come dicono i nuovi dati? In altri termini, cosa diventa vero e cosa diventa falso? (problema di qualificazione)

Tutti questi problemi dipendono dal fatto che noi conosciamo parzialmente il mondo, se conoscessimo tutto il dominio della conoscenza da rappresentare non avremmo più problemi. D'altronde non dovremmo neanche dedurre o indurre regole, perchè tutta la conoscenza possibile si avrebbe per elencazione ed infine non ci sarebbe il problema di ritrattare la conoscenza, visto che nessuna regola andrà a cozzare con nuovi dati poichè tutto è noto.

Assumption logic, deduzione sotto assunzione.

<T,A>
T è una teoria logica di 1° ordine (ricordo che la logica di primo ordine racchiude, come caso particolare, la logica proposizionale).
A è un insieme di assunzioni, cioè predicati o lettere scelte per completare T. L'insieme A impone dei vincoli sul modello per T, quindi l'insieme A modifica la verità di T.

Estensione (Extension): è un sottoinsieme $A' \subseteq A$ massimale consistente con T, ovvero $T \cup A' \not\models \mathtt{false}$ quindi l'insieme A' non permette, combinato con T, di ottenere contraddizioni (di dedurre il falso).

Se abbiamo la coppia <T,A> ed un'estensione A' di A allora abbiamo la deduzione sotto assunzione ("s.a") che si scrive come segue:
$\left \langle T,A \right \rangle \underset{\tt{s.a.}}\models f$. Questa deduzione non studiamo come farla ma sappiamo che il risultato è equivalente (cioè è vero che la coppia <T,A> deduce sotto assunzione f) al risultato dell'operazione $T \cup A' \models f$.

Come è stato accennato, A modifica la semantica (il modello) di T. L'insieme A è come se fosse un insieme di fatti che devono essere necessariamente presi per veri nel modello di T. Spesso usando tutto A si ottengono delle contraddizioni, quindi al suo posto si usa un insieme massimale consistente con la teoria T, appunto A'.

E' possibile, come si vede intuitivamente, avere diverse A' massimali, quindi quando vale la deduzione sotto assunzione? Se usiamo una semantica brave (coraggiosa) possiamo dire che se esiste almeno un A' massimale per cui vale $T \cup A' \models f$, allora vale $\left \langle T,A \right \rangle \underset{\tt{s.a.}}\models f$.
Con la semantica conscious o cauta invece posso dire che $\left \langle T,A \right \rangle \underset{\tt{s.a.}}\models f$ vale se $T \cup A' \models f$ vale per ogni A' massimale estraibile da A.

Esempio di deduzione sotto assunzione

T:
bird(x), not ab(x) -> flies(x)
ostrich(x)         -> ab(x), not flies(x)
bird(t) //fatto, equivale ad una regola scritta in questo modo 
                                                            true -> bird(t)
ostrich(f)

A:
{not ab(t), not ab(f)}
//se non c'è evidenza del contrio io suppongo che tutto sia normale

Se calcoliamo l'implicazione logica con $A \cup T$ otteniamo una contraddizione poichè dal solo T io posso implicare ab(f) (poichè ostrich(f) attiva la regola che mi fa dedurre ab(f), not flies(f) ) che ha il suo negato in A.
Dunque A non è un'estensione, usiamo A'={ not ab(t) } 1, dunque la teoria che useremo per lavorare con la semantica a modelli "classica" è $T \cup A'$.

A livello semantico è come se T fossero le regole certe, di cui sappiamo la verità universale, mentre A sono regole che normalmente valgono (fino a quando non si ha un dato contrario). Dunque dobbiamo usare quelle assunzioni consistenti con le regole certe per avere una teoria non contraddittoria.

Vediamo casi con più estensioni disponibili.

T:
republican(x), not ab_r(x) -> not pacifist(x)
quacker(x), not ab_q(x)    -> pacifist(x)
quacker(n), republican(n)

A:
{not ab_r(n), not ab_q(n)}

Al solito $T \cup A$ non è consistente poichè da T si può implicare ab_r(n) or ab_q(n) mentre in A c'è la negazione di entrambi. Si hanno due estensioni valide:
A':
{not ab_r(n)}, //porta ad implicare che n non è pacifista
{not ab_q(n)}  //porta ad implicare il contrario di sopra

Qui entra in gioco la semantica coraggiosa o quella cauta, infatti come rispondiamo alla domanda "<T,A> permette di implicare che 'n' è pacifista"?
Con la semantica brave possiamo rispondere positivamente se almeno una estensione permette di dedurre pacifist(n) , con la semantica consciuos no.

Utilizzare la semantica cauta non impedisce la deduzione di nuova conoscenza

Semplicemente la limita rispetto alla semantica brave (che permette di dedurre conoscenza con meno vincoli). Vediamo un esempio:

T:
rep(x) , not ab_r(x) -> hawk(x)
q(x), not ab_q(x)    -> pacifist(x)
q(n), rep(n)
hawk(x)              -> p.mot(x)
pacifist(x)          -> p.mot(x)

A:
{not ab_r(n), not ab_q(x)}

Da questa si avrà $T \cup A \underset{\tt{cauta}}{\not\models} \tt{hawk(n)}$ e $T \cup A \underset{\tt{cauta}}{\not\models} \tt{pacifist(n)}$ ma comunque riesco a dedurre qualcosa, ovvero:
$T \cup A \underset{\tt{cauta}}{\models} \tt{p.mot(n)}$

Nota in questo caso l'estensione considerata è A'=A quindi la deduzione sotto assunzione di <T.A> equivale all'implicazione classica con $T \cup A$.

Estensioni con priorità

Capiteranno dei casi in cui esistono più estensioni non solo massimali ma, in funzione della realtà che si cerca di descrivere tramite T, un'estensione è più attinente alla realtà di un'altra. Esempio:

T:
bird(x), not ab_b(x)    -> flies(x)
ostrich(x)              -> bird(x)
ostrich(x), not ab_o(x) -> not flies(x)
ostrich(f)

A:
{not ab_b(f), not ab_o(f)}

In questo caso prevale l'estensione A'={not ab_o(f) poichè ha più attinenza alla realtà (se f è uno struzzo normale [no abnormal] non vola, piuttosto che considerarlo un uccello normale). Dunque si possono vedere le varie estensioni come un reticolo (un insieme parzialmente ordinato di solito secondo l'operatore di inclusione).
Cioè data una possibile estensione, si hanno sottoestensioni che aumentano l'attinenza con la realtà poichè si prendono come veri fatti specifici e non tanti fatti assieme. Si può immaginare che la sottoestensione estrema è composta da un solo fatto. Quindi la priorità di applicazione minima è data dall'estensione massimale e poi via via all'aumentare della priorità diminuisce la cardinalità delle sottoestensioni. Se abbiamo più sottoestensioni ad una data priorità, quale si sceglie per descrivere al meglio la realtà? Questo è un problema non banale se si cerca di risolverlo automaticamente o quando si hanno poche informazioni sul dominio che si vuole rappresentare.

Default Logic

Con questo tipo di logica si tiene sempre separata la conoscenza certa, che solitamente sarà chiamata teoria T, dalla conoscenza che normalmente vale (che userà la logica di default).

La conoscenza di default modella ragionamenti che normalmente si fanno sempre per assunzione. Il fatto che siano di uso comune li fa diventare di default, del tipo "a meno che non ho evidenza del contrario, vale quello che dico". La loro notazione è la seguente:

(1)
\begin{gather} \frac{\tt{football: \neg snow}}{\tt{matchTakePlace}} \end{gather}

Che si legge come: posto che vogliamo giocare a pallone, se non nevica la partita sarà giocata. Se non nevica è conoscenza normale, bisogna avere evidenza che nevichi per non giocare la partita.
Questa costruzione, che appartiene alla logica di default, è diversa da football, not snow -> matchTakePlace , poichè nella deduzione classica la partita avrà luogo se si deduce esplicitamente (si è certi) che non nevica. Invece con la logica di default se non riusciamo a dedurre che nevica (che nevica, non che non nevica!) allora la partita avrà luogo, in particolare basta esserne quasi certi . Tradurre questo ragionamento con la deduzione classica è possibile ma è più macchinoso.

Dubbio: il seguente esempio non riesco a vederlo poichè le giustificazioni sono alternativamente vere, come facciamo a dedurre conoscenza se non tutte le giustificazioni sono vere? Ed anche se ne basta una, prendiamo, in questo caso, comunque l'ombrello?
Sostanzialmente alla conclusione si arriva se una giustificazione è vera o lo sono tutte?
Da come è descritta l'applicabilità di un default (più sotto), questo si applica (quindi si ottiene la conseguenza) solo se per ogni giustificazione è vero che il suo opposto non sta nella conoscenza acquisita fino a quel momento.
Quindi per il seguente esempio non non sappiamo se piove ma è anche vera la closed world assumption ed inoltre sappiamo che ciò che non sta nell'estensione è ragionevolmente falso. Quindi se non ci sta nè not piovepiove , qualcosa non torna perchè ciò che è vero deve stare nell'estensione ed una delle due cose è vera. Quindi l'estensione avrà il contrario di una giustificazione quindi, per come lo leggo io, questo default sembra inapplicabile.

Altro esempio di ragionamento semplificato

(2)
\begin{gather} \frac{\tt{true: piove; \neg piove}}{\tt{prendiOmbrello}} \end{gather}

Il presupposto è 'true' quindi è vero che faremo certe supposizioni. Se supponiamo che piova e non deduciamo il contrario allora prendiamo l'ombrello, nel caso contrario no.

Tipi di conoscenza modellabili con la default logic

La default logic permette di rappresentare diversi tipi di ragionamento:

Prototipale

Ragionamento che evolve con l'apprendimento.

(3)
\begin{gather} \frac{\tt{ child(x): hasParents(x) }}{\tt{ hasParents(x) }} \end{gather}

Se x è un bambino e non c'è evidenza che non abbia i genitori, allora li ha.

No risk reasoning

(4)
\begin{gather} \frac{\tt{ accused(x): innocent(x) }}{\tt{ innocent(x) }} \end{gather}

Un accusato è innocente se non c'è evidenza del contrario.

Gerarchie con eccezioni

Tipicamente i molluschi hanno la conchiglia ma i polpi non la hanno:
Conoscenza certa polpi(x) -> noConchiglia(x), mollusco(x)
Conoscenza tipica o di default:

(5)
\begin{gather} \frac{\tt{mollusco(x): conchiglia(x)}}{\tt{conchiglia(x)}} \end{gather}

Ovvero se non c'è evidenza che il mollusco non abbia la conchiglia, allora la ha.

Closed world assumption CWA

Se da una teoria non posso dedurre qualcosa, allora il suo opposto sarà vero.
In default logic si modella così: data una teoria T di conoscenze certe, voglio applicare la CWA su alcune conoscenze (formule logiche) quindi avrò:

(6)
\begin{gather} \frac{\tt{true} : \neg \varphi }{\neg \varphi} \cup T \end{gather}

Dove i default modellano la CWA per le formule $\varphi$ ed in più abbiamo la conoscenza certa T.
Come funziona?
Se $T \models \varphi$ il default non si applica poichè c'è evidenza che $\neg \varphi$ sia falso.
Se da T non riesco a dedurre $\varphi$ allora posso ritenere che $\neg \varphi$ sia vero e quindi deduco $\neg \varphi$.

Formalizzazione di una teoria di default

Una teoria di default è una coppia $\Delta = (W, D)$.
W è una teoria in logica del primo ordine (ricordo che la logica del primo ordine racchiude la logica proposizionale).
D è un insieme di default che servono a modellare il ragionamento di "default" o comune.

Un default ha la struttura seguente:

(7)
\begin{gather} d = \frac{a:g_1;\dots;g_n}{c} \end{gather}

'd' è il default.
'a' è la premessa, prerequisito del default. Ovvero pre(d)=a .
$\left \{ g_1,\dots,g_n \right \}$ sono le giustificazioni del default. Dunque just(d)= {g1 , …, gn} . Le giustificazioni considerate tutte assieme formano la "giustificazione" del default.
'c' è la conseguenza del default ( cons(d)=c ).

In notazione compatta indicheremo un default come segue:
pre : giust / cons oppure (pre : giust) / cons , siccome non c'è ambiguità spesso usereremo la prima notazione.

Nota: le giustificazione e la conseguenza sono formule ground della logica proposizionale (no variabili), il prerequisito invece è un atomo ground (sempre senza variabili).

Default normali

Un default si dice normal se la giustificazione coincide con la conseguenza.

Default seminormali

Un default è seminormale se la conseguenza è un sottoinsieme della sua giustificazione (considerando l'intera giustificazione del default).

Default con logica del primo ordine

Abbiam detto che un default non contiene variabili, allora come mai prima ne abbiam scritti tanti con le variabili? Per brevità. Se il dominio delle costanti è finito (ricordo che un predicato ground può essere visto sostanzialmente come una lettera della logica proposizionale) allora possiamo sempre riscrivere un default espresso in logica del primo ordine in tanti default ground (cioè con formule ed atomi ground).
Esempio:

(8)
\begin{gather} d = \frac{a(x):b(x)}{c(x)} \end{gather}

Per la logica del primo ordine è sempre implicita la quantificazione universale, quindi se $x \in {e_1, ..., e_n}$ allora io avrò il default che deve essere scritto $\forall \ x$, dunque avrò l'insieme dei default:

(9)
\begin{gather} \left \{ d = \frac{a(e_1):b(e_1)}{c(e_1)} , \ \dots \ , d = \frac{a(e_n):b(e_n)}{c(e_n)} \right \} \end{gather}

Poi le formule ground della logica di primo ordine "dovrebbero" essere riscritte in forma proposizionale per aderire a quanto detto riguardo la forma della giustificazione e della conseguenza di un default.

Come si legge un default?

Se il prerequisito è vero e possiamo assumere (cioè non deduciamo il contrario) che valgano le giustificazioni (non si valuta un or delle giustificazioni, sembra essere piuttosto un and) allora possiamo dedurre la conseguenza.

Dubbio: le giustificazioni sono in or? In and o cosa? Se leggi l'applicabilità del default, scritta in seguito, sembra l'and perchè deve essere vero che ciò che è contrario alle giustificazioni deve stare fuori dall'estensione. Spiegato male o sono io che ho preso appunti a muzzo?

Come facciamo a dire che il prerequisito è vero? Lo deduciamo dalla teoria "di base"(o che dà conoscenza sulle cose certe) W.
Quando deduciamo qualcosa questo qualcosa entra nell'insieme della conoscenza dedotta fino a quel punto e permette di rendere altri prerequisiti veri. Se deduciamo qualcosa contrario ad un elemento presente nell'insieme della conoscenza dedotta fino a quel momento, togliamo l'elemento. Ad esempio se deduciamo not a ed invece sapevamo che era valido a fino a quel momento, togliamo a dall'insieme della conoscenza dedotta.

Default applicabili. Struttura logica deduttivamente chiusa

Data una struttura (un insieme di formule logiche) deduttivamente chiusa E, ovvero tale che $Th(E) \subseteq E$, cioè l'insieme della conoscenza deducibile o derivabile (se lo si deduce si applica la semantica dei modelli, se lo si deriva si applica la regola di inferenza) da E è già inclusa in E quindi non si deriva niente i nuovo.
In altre parole la definizione è $Th(E) = \left \{ a \ | \ \ E \models a \right \}$, questo si riferisce alla deduzione. Si ha lo stesso con la derivazione qualora la regola di inferenza sia corretta e completa perchè in questo caso il comportamento della derivazione o della deduzione è identico.
Si ha che un default d è applicabile ad E rispetto ad E se:

(10)
\begin{gather} pre(d) \in E \wedge \left ( \forall g_i \in just(d) \left ( \neg g_i \not\in E \right ) \right ) \end{gather}

Ovvero se la premessa del default è vera per E e non è vero che è esplicitamente noto il contrario di qualche giustificazione (cioè la negazione di una giustificazione sta in E).
Osserviamo che d è applicabile ad E poichè il prerequisito si trova in E. L'applicabilità si ha rispetto ad E poichè nessuna delle giustificazioni si trova negata in E. Se avessimo avuto le giustificazioni valutate in E1 avremmo detto applicabile ad E rispetto ad E1.
'E' è detta estensione e coincide con il significato di modello in logica del primo ordine e non con l'estensione della logica sotto assunzione.

In questo modo, sapendo che la conoscenza dedotta si può modificare con le conseguenze di un default, non è sempre vero che dati due default applicabili posso applicare l'uno e l'altro in qualsiasi ordine.

Caratteristiche dell'estensione nella teoria di default

Modello o estensione è uguale per la teoria della logica di default.

  • 'E' deve contenere la conoscenza certa. Quindi dato W, $W \subset E$.
  • L'estensione deve essere chiusa rispetto alla deduzione classica, quindi $Th(E) \subseteq E$.
  • Se esiste un default 'd' in D applicabile ad E la sua conseguenza deve entrare a far parte del modello. Quindi $\forall \ d \ \mbox{applicabile ad E rispetto ad E} \Rightarrow cons(d) \in E$.

Fra tutte le estensioni cerchiamo quelle minimali, poichè è inutile tener dentro roba deducibile dagli altri concetti in quanto diventa più costoso il calcolo della deducibilità se c'è ridondanza.

Tuttavia ciò non è abbastanza per individuare le estensioni minimali. Esempio (uso una notazione compatta):
Delta = ( W={a}, D={(a:b)/b} )
Un'etensione per Delta è E={a, not b} . Sembra antiintuitivo ma rispetta le caratteristiche per l'estensione. Contiene W, è chiusa deduttivamente rispetto a se stessa anche perchè l'unico default che c'è non è applicabile in quanto la giustifizione è bloccata. Inoltre è minimale perchè non si può togliere nessun elemento da essa per ottenere una nuova estensione.

Quindi modifichiamo le caratteristiche dell'estensione (o modello) per la teoria logica di default.
Data la teoria di default Delta = ( W, D ) . E è un'estensione per Delta se:

  • $E = \bigcup_{\forall \ i} \ E_i$
  • $E_0 = W$ (si parte dalla certezza)
  • $E_{i+1} = Th\left ( E_i \cup \left \{ cons(d) \ | \ pre(d) \in E_i \wedge \left ( \forall g_i \in just(d) \left ( \neg g_i \not\in E \right ) \right ) \right \} \right )$ (ovvero E_i+1 è la conseguenza della deduzione applicata a partire dalle conoscenze presenti in E_i a cui si aggiungono le conseguenze dei default applicabili ad E )

Il problema è che E, rispetto al quale posso vedere se il default è applicabile, lo ottengo alla fine del calcolo quindi nel mezzo del calcolo non so se le giustificazioni rispettano il vincolo. Quindi la definizione di estensione è corretta ma non è costruttiva per ottenere E.

Ottenere un'estensione in modo costruttivo

Si utilizza una tecnica che rende induttive le definizioni non induttive (cioè rende costruttive le definizioni). Per far questo dobbiamo introdurre alcuni nuovi concetti.

Sequenze di default, insieme In ed insieme Out.

Usiamo $\pi$ per denotare una sequenza finita o infinita composta dai default presenti in delta (la teoria logica di default in uso). La notazione per descrivere $\pi$ è la seguente:
$\pi = \left \langle d_0, d_1, \ \dots \ , d_i, \ \dots \right \rangle$ (notare che è infinita così)
I default non si ripetono, quindi $d_i \neq d_j , \ i \neq j$, dunque se i default in Delta sono limitati, $\pi$ sarà una sequenza finita. $\pi$ indica la sequenza di applicazione dei default (ciò non vuol dire che i default in quella sequenza siano tutti applicabili, significa che si prova ad applicarli in quella sequenza).
$\pi (k)$ è la parte iniziale iniziale della sequenza $\pi$ che contiene tutti i default fino al k-esimo, dunque contiene k+1 default, cioè $\pi (k) = \left \langle d_0, d_1, \ \dots \ , d_k \right \rangle$ con $k < \text{length} (\pi)$ (strettamente minore, visto che si parte da 0).

Definiamo quindi due insiemi:
$In(\pi) = Th \left ( W \cup \left \{ cons(d) \ | \ d \in \pi \right \} \right )$
Ovvero In è l'insieme delle conseguenze ottenibili dalla conoscenza W e dai default in $\pi$. Nota: in questo caso non si valuta se i default sono applicabili, si prendono le loro conseguenze e basta. E' una definizione è la si accetta come tale.
$Out(\pi) = \left \{ \neg g \ | \ \exists \ d \wedge g \in just(d) \wedge d \in \pi \right \}$ , ovvero Out raccoglie tutti gli opposti delle giustificazioni dei default in $\pi$.

Esempio: ( \pi = $\pi$ )
Delta = ( {a}, { d_1 = a: not b / not b , d_2 = b : c / c } )
Con \pi = <d_1> abbiamo:
In(\pi) = Th({a, not b}) (nota: ci vuole sempre Th poichè si indica che In sono le conseguenze dell'insieme dato come argomento di Th)
Out(\pi) = {b}

Con \pi_1 = <d_2,d_1> abbiamo:
In(\pi_1) = Th({a, not b, c})
Out(\pi) = {b, not c}

Bisogna notare che le due sequenze non sono sempre utilizzabili perchè l'applicazione di un default potrebbe rendere inapplicabile un default succesivo della stessa sequenza del default applicato, tuttavia le definizioni di In ed Out non tengono conto dell'applicabilità dei default quindi per ogni sequenza è sempre possibile costruirli.

Processi, processi succesful e closed

Una sequenza di default $\pi$ si dice processo se $\forall \ k, \ d_{k+1}$ è applicabile ad $In(\pi_k)$ rispetto ad $In(\pi_k)$.
Ovvero una sequenza di default è utilizzabile se ogni default non ancora applicato, preso in ordine dalla sequenza, è applicabile rispetto a ciò che è stato dedotto in precedenza (ciò è definito da In).
Questa definizione di processo garantisce che se la base di conoscenza (W) non è contraddittoria (cioè posso dedurre il falso da questa), In non sarà mai inconsistente (cioè In non conterrà una formula e la sua opposta).

Dubbio- Solved: wait, la frase "Questa definizione di processo garantisce che se la base di conoscenza (W) non è contraddittoria (cioè posso dedurre il falso da questa), In non sarà mai inconsistente (cioè In non conterrà una formula e la sua opposta)." non mi torna del tutto: W={a,b} , D={ d_1 = true : b / not a } con processo \pi = <d_1>, credo sia inconsistente perchè In conterrà a e not a. Molto probabilmente non ho ben afferrato, devo chiedere.
Soluzione: leggi le sezioni successive, in particolare si dice che se io deduco da un default qualcosa che è pari al negato di ciò che avevo precedentemente dedotto, poi l'estensione costruita fino a quel momento, essendo inconsistente, può dedurre di tutto (ex falso quodlibet) e quindi anche la negazione della giustificazione del default usato. Quindi il default risulta inapplicabile rispetto all'estensione finale (che comprende tutto ed è pari ad $In(\pi)$), quindi il processo non sarà closed e quindi non si ha un'estensione.

Dato un processo $\pi$ questo è:

  • succesful se $In(\pi) \cap Out(\pi) = \emptyset$ altrimenti è un processo failed. Cioè non si deduce ciò che va in conflitto con le giustificazioni dei default in $\pi$.
  • closed se per ogni default applicabile ad $In(\pi)$ rispetto a $In(\pi)$ è vero che il default $\in \pi$. Ovvero non esistono default di Delta applicabili ad $In(\pi)$ che non siano già presenti in $\pi$.

esempi:
Delta = ( {a}, { d_1 = a: not b / d , d_2 = true : c / b } )
Con \pi_1 = <d_1> . questo è innanzitutto un processo (poichè è applicabile al processo precedente che contiene in pratica solo le conseguenze di W). Poi è un processo succesful poichè non ci sono conflitti tra conseguenze e giustificazioni ma non è closed poichè d_2 rimane applicabile.
(Grazie del fix vincenzo M.)

Ottenere l'Estensione della teoria di default tramite processo induttivo

Teorema: data una teoria di default Delta = ( W, D ) , 'E' è un'estensione di Delta se e solo se esiste un processo $\pi$ su Delta closed e succesful tale che $In(\pi) = E$.

Quindi possiamo calcolare le estensioni di Delta calcolando tutti i processi closed e successful di Delta.

Calcolare i processi closed e successful di Delta

Non sappiamo costruire direttamente tutti i processi closed e succesful, cosa facciamo allora? Poichè D in Delta è finito, e poichè un processo è una sequenza di default non ripetuti, potremmo generare tutti i processi possibili. Questa costruzione si appoggia sulla costruzione del process tree.
Il primo nodo dell'albero (la radice) è il processo vuoto ( $\pi_W$ ), ovvero non si hanno default applicati ed in pratica si hanno solo le conseguenze di W. Poi si costruiscono i vari processi etichettando i rami con il nome del default utilizzato ed il nuovo nodo indicherà l'In e l'Out del processo equivalente al path per arrivare al nodo. Cioè un passaggio avrà la seguente struttura:

nodo precedente basato su pi_k: In( <pi_k> ) , Out( <pi_k>) 
  -- DefaultApplicato d_(k+1) --> 
nodo successivo: In( <pi_k, d_(k+1)> ) , Out( <pi_k, d_(k+1)> )

Nota: sembra che dal process tree i processi permettano solo di aumentare la conoscenza. Ciò è parzialmente vero, perchè ad ogni default applicato 'In' aumenta. Il problema è che se non si ha un processo closed e successful, l'aumento di conoscenza è inutile in quanto non fruibile poichè alla fine il processo non sarà un'estensione.

Quindi la partenza sarà

//si parte dalle certezze W
In( pi_w = empty ) = empty , 
Out( pi_w = empty ) = empty 
   -- DefaultApplicato d_1 (è un default generico nella lista) -->   
        //per ogni default in D possiamo generare un nodo distante 1 dalla radice

In(<d_1> ) , 
Out(<d_1>)

Con questa costruzione cerchiamo di arrivare ad un nodo che restituisca un processo chiuso e successful, che ci darà l'estensione pari ad In(processo) . Nota: poichè costruiamo, seguendo i rami del process tree, processi, i nuovi default che applichiamo devono permettere di rispettare definizione di processo, quindi devono essere applicabili al passo successivo.

Teorie coerenti e teorie inconsistenti

Una teoria è incoerente quando non esistono modelli (o estensioni) per essa. Ovvero data la definizione di estensione per la teoria ed un algoritmo per costruirli, non si ottiene alcuna estensione che rispetta la definizione.

Una teoria è inconsistente quando esiste un'estensione per questa (cioè che rispetta la definzione di estensione per la teoria data) ma da questa si può dedurre il falso (vuol dire che l'estensione comprende un predicato ed il suo negato). Se si deduce il falso, in seguito alla deduzione del falso io posso dedurre tutto (ex falso quodlibet) dunque diventa una teoria banale poichè comprende qualsiasi predicato verificabile o meno. (Se puoi approfondisci anche se già così dovrebbe capirsi)

Un esempio lo si ha con l'analisi nella prossima sezione.

Teoria di default inconsistente

Una teoria di default Delta = ( W, D ) è inconsistente solo se W è inconsistente. Questo perchè l'applicazione dei default alla base (cioè W) può portare all'assenza di estensioni, poichè potremmo applicare un default la cui conseguenza è il contrario della giustificazione non permettendo di trovare, nel process tree, un processo successful e closed che rispetti la definizione prima esposta. Ad esempio:
Delta = ( {} , {true: a / not a} )
Se io applico l'unico default, nel process tree, è vero che è applicabile, ma mi porta a:

//si parte dalle certezze W
In( pi_w = empty ) = empty , 
Out( pi_w = empty ) = empty 
   -- DefaultApplicato d_1 --> 
In = Th( {not a} ) , 
Out = {not a}

Quindi l'unico processo possibile, cioè <d_1> , per definizione, non è successful quindi non esistono estensioni per Delta. Basta aggiungere, in qualsiasi teoria, un default come quello visto, perchè il default ( true : a / not a ) è sempre applicabile2, che scompare la possibilità di ottenere un'estensione.

Tuttavia i default non generano mai inconsistenza, questo perchè potrei avere un default che ha come conseguenza l'opposto di qualcosa già presente in E. Se così fosse, per ciò che si è detto prima (ex falso quodlibet) io potrei dedurre qualsiasi cosa, anche la negazione di almeno una giustificazione del default, quindi il default non sarebbe applicabile all'estensione, dunque l'estensione per Delta sarebbe un'altra visto che l'estensione corrente ha permesso di applicare un default a lei inapplicabile (perchè in seguito l'estensione si è espansa tramite ex falso quodlibet).

Varianti della default logic

La Default logic è stata variata perchè ha qualche difetto (anche solo per la facilità di espressione di alcune cose), basti pensare al costo computazionale per dire se una teoria Delta implica semanticamente qualche formula. Bisogna trovare il process tree e quindi un'estensione e poi fare l'implicazione semantica $E \models \tt{formula}$.

nota: in generale il linguaggio di rappresentazione della conoscenza è scelto rispetto al problema.

Un problema della default logic, i default "distruttivi"

Come abbiam accennato, basta un default nell'insieme D di Delta, ovvero true : a / not a che non si trova più nessuna estensione dal process tree. Il problema è il seguente: ma se fino al passo 'k' tutto andava bene, perchè poi devo perdere la conoscenza acquisita? Non posso decidere di fermarmi al passo 'k' invece di arrivare ad inglobare il default distruttivo?

Teorie logiche di default semi-monotone

Quindi ci si potrebbe soffermare alle teorie dove i default non diminuiscono la conoscenza ma la possono solo aumentare, dette teorie di default semi-monotone. Una teoria di default è semi-monotona se:

Teorema: per ogni coppia < Delta = ( W, D ) , Delta' = ( W, D' ) > con $D \subseteq D'$ vale la proprietà seguente:

  • Per ogni estensione E di Delta esiste un'estensione E' di Delta' tale che $E \subseteq E'$

Questa classe di teorie di default è ovviamente un sottoinsieme di tutte quelle possibili.

Teorie logiche di default con almeno un'estensione, teorie normali

Le teorie normali ammettono che Delta abbia almeno un'estensione e ciò si ha con soli default normali. Si nota che true: a / not a non è un default normale. Ovviamente dato il limite dei default normali si avrà un limite espressivo con queste teorie. Questo perchè la conseguenza di un default normale è pari alla sua giustificazione (la forma è pre : a / a ), quindi è difficile controllare un default con un altro default (il controllo si ha tramite le conseguenze che dovrebbero 'disattivare' certe giustificazioni).

Giustificazioni in contraddizione, vincolo di join giustification.

Consideriamo la segunte teoria:
Delta = ( empty, { d1 = true : p / q , d2 = true : not p / r } )
L'estensione è E = { q, r } poichè seguendo le definizioni date che le giustificazioni siano in contraddizione non è un problema. Infatti è vero che not p o p non sono in E, quindi entrambi i default sono applicabili. Tuttavia ci sarebbero dei casi in cui semanticamente ciò non è accettabile. Ad esempio se p = piove , q = sto in casa e r = faccio sport all'aperto, avrei che sia che piova o che sia bel tempo io comunque sono sia in casa sia fuori a fare sport.
Quindi l'idea è quella di inserire vincoli di consistenza tra giustificazioni di default diversi, quando per le definizioni date sinora abbiamo visto che non c'è nessun vincolo tra giustificazioni di default diversi.
Il vincolo diventa: le giustificazioni dei default che vogliamo applicare devono essere contemporaneamente ammissibili, altrimenti la sequenza dei default che si vogliono applicare non è più applicabile. Questo vincolo è detto join giustification.
Ovviamente, come negli altri casi, con questo vincolo si perde espressività ed alcuni default non saranno utilizzabili.

Altra soluzione, "disattivare" i default che generano inconsistenza

Come abbiam visto un default è applicabile se la premessa è vera e non c'è evidenza del contrario di una giustificazione. Per evitare teorie inconsistenti (cioè inserire nell'estensione il contrario di qualcosa già presente in questa) si aggiunge il vincolo che un default è applicabile anche se non genera inconsistenze nella teoria. Così si evita di perdere una buona teoria che diventa inconsistente a causa di pochi default.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License