Semantica del modello stabile

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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

Introduzione[modifica | modifica wikitesto]

Dato il seguente programma:

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

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 è un modello del programma.

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

T T T F.

Questa interpretazione, che chiamiamo è un modello non minimale del programma, in quanto di cardinalità maggiore rispetto a (indicato come ).

Definizione[modifica | modifica wikitesto]

Sia un programma costituito da regole espresse nella forma seguente:

dove sono atomi ground, ovvero non contenenti variabili. Se non contiene negazioni ( in ogni regola del programma) allora, per definizione, l'unico modello stabile di è 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 di atomi ground, una riduzione di relativa a —indicata con —è l'insieme di regole senza la negazione ottenuto a partire da rimuovendo:

  • ogni regola che abbia nel suo corpo, se ;
  • ogni parte all'interno delle restanti regole.

Diciamo che è un modello stabile (o answer set) di se è un modello stabile di . 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[modifica | modifica wikitesto]

Per illustrare le definizioni di cui sopra, controlliamo che è un modello stabile per il programma:

La riduzione di questo programma rispetto a è:

(dato che , la riduzione è ottenuta rimuovendo in tutte le regole che lo contengono)
Il modello stabile (ovvero, il modello minimale) della riduzione è proprio . Di conseguenza, è un modello stabile per il programma.

Controllando gli altri 15 possibili insiemi contenenti gli atomi si dimostra che il programma non ha altri modelli stabili.
Ad esempio, la riduzione relativa all'interpretazione è:

(dato che , la riduzione è ottenuta rimuovendo dal programma tutte le regole contenenti )
Il modello stabile (ovvero, il modello minimale) della riduzione è , che è differente dall'interpretazione di partenza.

Note[modifica | modifica wikitesto]

  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[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]

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