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. Il concetto di modello stabile, introdotto da Gelfond e Lifschitz nel 1988,[2] è alla base dell'answer set programming.

IntroduzioneModifica

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

DefinizioneModifica

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.

EsempioModifica

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.

NoteModifica

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

BibliografiaModifica

  • 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 correlateModifica

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