title: Semantica del modello stabile
text: # 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. Il concetto 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,\ {\hbox{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 ${\hbox{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},{\hbox{not }}C_{1},\dots ,{\hbox{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}\not \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,\ {\hbox{not }}q.$
  
  La riduzione di questo programma rispetto a $I$ è:
  
      $p\$
      $r\leftarrow p,\ q$
      $s\leftarrow p.$
  
  (dato che $q\not \in I$, la riduzione è ottenuta rimuovendo ${\hbox{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 ${\hbox{not }}q\$) Il modello stabile (ovvero, il modello minimale) della riduzione $P^{I'}$ è $\{p\}$, che è differente dall'interpretazione di partenza.
  
  