Semantica del modello stabile

Il modello stabile^[1] (stable model), o answer set, è un concetto utilizzato per definire una semantica dichiarativa nella programmazione logica con negazione. La nozione di modello stabile, introdotto da Gelfond e Lifschitz nel 1988,^[2] è alla base dell'answer set programming.

Introduzione

Dato il seguente programma:

${\displaystyle p\ }$

${\displaystyle r\leftarrow p,\ q}$

${\displaystyle s\leftarrow p,\ {\hbox{not }}q.}$

la query ${\displaystyle p}$ avrà successo, in quanto il programma indica ${\displaystyle p}$ come un fatto; la query ${\displaystyle q}$ fallirà per negation by default, in quanto non occorre in nessuna parte sinistra delle regole del programma. Anche la query ${\displaystyle r}$ fallirà, in quanto nel corpo della regola appare un atomo con valore negativo. Infine, la query ${\displaystyle s}$ avrà successo, in quanto sia l'obiettivo ${\displaystyle p}$ che ${\displaystyle {\hbox{not }}q}$ sono positivi. Quindi, l'interpretazione di default ${\displaystyle I}$ dei quattro letterali sarà la seguente:

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle r}$	${\displaystyle s}$
T	F	F	T.

Se calcoliamo i valori di verità delle regole del programma mediante l'interpretazione di cui sopra, risulteranno tutti essere T. In altre parole, l'interpretazione ${\displaystyle I}$ è un modello del programma.

Tuttavia, possono esistere altre interpretazioni, in generale non minimali, che rendono vere tutte le regole del programma. In questo caso:

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle r}$	${\displaystyle s}$
T	T	T	F.

Questa interpretazione, che chiamiamo ${\displaystyle I'}$ è un modello non minimale del programma, in quanto di cardinalità maggiore rispetto a ${\displaystyle I}$ (indicato come ${\displaystyle I<I'}$).

Definizione

Sia ${\displaystyle P}$ un programma costituito da regole espresse nella forma seguente:

${\displaystyle A\leftarrow B_{1},\dots ,B_{m},{\hbox{not }}C_{1},\dots ,{\hbox{not }}C_{n}}$

dove ${\displaystyle A,B_{1},\dots ,B_{m},C_{1},\dots ,C_{n}}$ sono atomi ground, ovvero non contenenti variabili. Se ${\displaystyle P}$ non contiene negazioni (${\displaystyle n=0}$ in ogni regola del programma) allora, per definizione, l'unico modello stabile di ${\displaystyle P}$ è il suo modello minimale.

Per estendere questa definizione al caso dei programmi con negazione, è necessario il concetto ausiliario di "riduzione", definito come segue.

Per ogni insieme ${\displaystyle I}$ di atomi ground, una riduzione di ${\displaystyle P}$ relativa a ${\displaystyle I}$—indicata con ${\displaystyle P^{I}}$—è l'insieme di regole senza la negazione ottenuto a partire da ${\displaystyle P}$ rimuovendo:

• ogni regola che abbia ${\displaystyle not\ C_{i}}$ nel suo corpo, se ${\displaystyle C_{i}\in I}$;
• ogni letterale ${\displaystyle not\ C_{j}}$ all'interno delle restanti regole se ${\displaystyle C_{j}\not \in I}$.

Diciamo che ${\displaystyle I}$ è un modello stabile (o answer set) di ${\displaystyle P}$ se ${\displaystyle I}$ è un modello stabile di ${\displaystyle P^{I}}$. Dato che la riduzione non contiene negazioni, la definizione di modello stabile per quest'ultima è già stata data, per cui la definizione non è ricorsiva.

In generale, un programma può avere più answer set.

Esempio

Per illustrare le definizioni di cui sopra, controlliamo che ${\displaystyle I=\{p,s\}}$ è un modello stabile per il programma:

${\displaystyle p\ }$

${\displaystyle r\leftarrow p,\ q}$

${\displaystyle s\leftarrow p,\ {\hbox{not }}q.}$

La riduzione di questo programma rispetto a ${\displaystyle I}$ è:

${\displaystyle p\ }$

${\displaystyle r\leftarrow p,\ q}$

${\displaystyle s\leftarrow p.}$

(dato che ${\displaystyle q\not \in I}$, la riduzione è ottenuta rimuovendo ${\displaystyle {\hbox{not }}q\ }$ in tutte le regole che lo contengono)
Il modello stabile (ovvero, il modello minimale) della riduzione ${\displaystyle P^{I}}$ è proprio ${\displaystyle \{p,s\}}$. Di conseguenza, ${\displaystyle I=\{p,s\}}$ è un modello stabile per il programma.

Controllando gli altri 15 possibili insiemi contenenti gli atomi ${\displaystyle p,\ q,\ r,\ s}$ si dimostra che il programma non ha altri modelli stabili.
Ad esempio, la riduzione relativa all'interpretazione ${\displaystyle I'=\{p,q,r\}}$ è:

${\displaystyle p\ }$

${\displaystyle r\leftarrow p,\ q.}$

(dato che ${\displaystyle q\in I'}$, la riduzione è ottenuta rimuovendo dal programma tutte le regole contenenti ${\displaystyle {\hbox{not }}q\ }$)
Il modello stabile (ovvero, il modello minimale) della riduzione ${\displaystyle P^{I'}}$ è ${\displaystyle \{p\}}$, che è differente dall'interpretazione di partenza.

Note

1. Russel-Norvig, p. 453.
2. (EN) Paolo Liberatore, Stable Model Semantics, su cs.cmu.edu, Carnegie Mellon University. URL consultato il 2 aprile 2016 (archiviato il 15 settembre 2015).

Bibliografia

• M. Gelfond e V. Lifschitz, The stable model semantics for logic programming, in Proceedings of the Fifth Logic Programming Symposium, The MIT Press, 1988, pp. 1070-1080.
• Stuart Russel, Peter Norvig, Intelligenza artificiale - Un approccio moderno, vol. 1, 2ª ed., Milano, Pearson Education Italia, 2005, ISBN 88-7192-228-X.

Voci correlate

• Teoria dei modelli
• Answer set programming