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,\text{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 $\text{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^{\prime }$ è un modello non minimale del programma, in quanto di cardinalità maggiore rispetto a $I$ (indicato come $I<I^{\prime }$).

Definizione

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

$A\leftarrow B_1,\dots ,B_m,\text{not }{C}_1,\dots ,\text{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 $not{C}_i$ nel suo corpo, se $C_i\in I$;
• ogni letterale $not{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,\text{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 $\text{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^{\prime }=\{p,q,r\}$ è:

$p$

$r\leftarrow p,q.$

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

Bibliografia

• Template:Cita pubblicazione
• Template:Cita libro

Voci correlate

• Teoria dei modelli
• Answer set programming