Semantica del modello stabile

Il modello stabile (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, è alla base dell'answer set programming.

Introduzione

Dato il seguente programma:

p

r \leftarrow p, q

s \leftarrow p, not q .

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

$p$	$q$	$r$	$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 $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:

$p$	$q$	$r$	$s$
T	T	T	F.

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

Definizione

Sia $P$ un programma costituito da regole espresse nella forma seguente:

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

dove $A, B_{1}, \dots, B_{m}, C_{1}, \dots, C_{n}$ sono atomi ground, ovvero non contenenti variabili. Se $P$ non contiene negazioni ( $n = 0$ in ogni regola del programma) allora, per definizione, l'unico modello stabile di $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 $I$ di atomi ground, una riduzione di $P$ relativa a $I$ —indicata con $P^{I}$ —è l'insieme di regole senza la negazione ottenuto a partire da $P$ rimuovendo:

ogni regola che abbia $n o t C_{i}$ nel suo corpo, se $C_{i} \in I$ ;
ogni letterale $n o t C_{j}$ all'interno delle restanti regole se $C_{j} \in̸ I$ .

Diciamo che $I$ è un modello stabile (o answer set) di $P$ se $I$ è un modello stabile di $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 $I = {p, s}$ è un modello stabile per il programma:

p

r \leftarrow p, q

s \leftarrow p, not q .

La riduzione di questo programma rispetto a $I$ è:

p

r \leftarrow p, q

s \leftarrow p .

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

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

p

r \leftarrow p, q .

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

Note

↑ Russel-Norvig, p. 453.
↑ (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

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[1] Russel-Norvig, p. 453.

[liberatore-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).