5.3 NI per programmi non definiti

Utilizzando gli operatori di unione e intersezione visti in precedenza, è possibile dare una definizione dell'operatore di negazione intensionale [MPRT90] per una particolare classe di programmi che estende quella per cui era stata data la definizione precedente.

Tali programmi ammettono l'uso di letterali negativi nel corpo delle clausole; non ammettono invece variabili locali al corpo delle clausole: è importante notare che tale ultimo vincolo non limita l'espressività dei programmi ottenibili rispetto a quelli non n.v.i.

Come nella definizione precedente di NI, si otterrà un nuovo programma $P^{-}$ che denoterà il complemento di $P$.

La classe di programmi considerata è la seguente:

Definizione 5.9  

Dato un linguaggio del primo ordine $L = <\Pi , \Sigma>$, con il simbolo di predicato binario $eq \in \Pi$, la classe dei programmi logici su $L$ è induttivamente definita come segue:

1. $0$ è un programma (il programma vuoto);

2. $EQ$: $eq(x,x)$ è un programma;

3. $p(t) \leftarrow B_{1} ,\ldots ,B_{k}$ è un programma, dove $p$ è un simbolo in $\Pi$ differente da $eq$, $p(t)$ è un atomo non ristretto, e $B_{1} ,\ldots ,B_{k}$ è una congiunzione di letterali in $L$.

4. $P\cup Q$ è un programma se $P$ e $Q$ lo sono.

A questo punto è utile introdurre un modo alternativo di definire il complemento di un programma logico, che si basa sull'idea di considerare la negazione come un tipo particolare di informazione positiva. Si considererà il linguaggio del primo ordine sottostante il programma come esteso a $L'$ = $<\Pi \cup \tilde \Pi >$ dove $\tilde \Pi$ = $\{ \tilde p \}_{p \in \Pi}$ . I letterali in $\Pi$ saranno chiamati letterali positivi e quelli in $\tilde \Pi$ letterali negativi.

I programmi definiti le teste delle cui clausole sono positive (rispettivamente negative) vengono detti programmi positivi (rispettivamente negativi). Sarà inoltre necessario distinguere tra il programma vuoto positivo $0$ e quello vuoto negativo $1$.

L'operatore di complementazione, avuto un programma positivo (risp. negativo), restituisce un programma negativo (risp. positivo) che rappresenta la conoscenza complementare implicitamente contenuta nel programma originale.

Il complemento di un programma $M$ è denotato da $\bar{M}$.

Definizione 5.10  

Per induzione sulla struttura di $M$, $\bar{M}$ è definito come segue:

1. $\begin{array}{ll} \overline{0} = \cup \{\tilde p(x) \mid \tilde p \in \tilde \Pi \} \par & \overline{1} = \cup \{ p(x) \mid p \in \Pi \} \end{array}$

2. $\begin{array}{ll} \overline{(p(t) \leftarrow B_{1} ,\ldots ,B_{k}) } = & \overl... ... q \in \tilde \Pi \} & \cup \{q(x) \mid q \neq p, q \in \Pi \} \par\end{array}$

   
   

   dove $\tilde B_{i}$ = $\left \{ \begin{array}{l} q(s) \mbox{ se } B_{i} = \tilde q(s) \\ \tilde q(s) \mbox{ se } B_{i} = q(s) \end{array} \right.$

   
   

3. $\overline{M_{1} \cup M_{2} } = \overline{M_{1} } \cap \overline{M_{2} }$

4. 
    $\overline{EQ}$ = 
   
   $\cup \{ \tilde eq(f(x),g(y)) \mid f, g \in \Sigma , f \neq g \}$ 
   
   
   		 $\cup \{ \tilde eq(f(x_{1} , \ldots ,x_{n}), f(y_{1}, \ldots ,y_{n}) \leftarrow \tilde eq(x_{i}, y_{i}) \mid f \in \Sigma , i = 1, \ldots ,n \}$
   

5. $\overline{\overline{EQ}} = EQ$

L'idea è quella di trasformare un programma $P$ sul linguaggio $L=<\Pi,\Sigma>$ nella coppia di programmi definiti $<P^{+},P^{-}>$ sul linguaggio esteso $L'=<\Pi \cup \tilde \Pi,\Sigma>$. $P^{+}$ è il programma positivo che rappresenta l'informazione positiva di $P$, mentre $P^{-}$ è il programma negativo che rende esplicita l'informazione negativa di $P$. Ciò è formalizzato nella seguente definizione:

Definizione 5.11  

Sia $P$ un programma. Allora

• $P^{+}$ è ottenuto da $P$ rimpiazzando ogni letterale negativo $\neg q(t)$ con $\tilde q(t)$;

• $P^{-} = \overline{P^{+}}$

Esempio 5.2  

Dato il programma

$$P = ( p(0). \cup p(s(x)) \leftarrow \neg p(x) )$$

si ottiene

$$P^{+} = ( p(0). \cup p(s(x)) \leftarrow \tilde p(x))$$

$$P^{-} = ( \tilde p(s(x)) \leftarrow p(x))$$

La possibilità di trattare programmi come una coppia di programmi definiti permette di fare a meno della regola di negazione come fallimento finito nel processo di valutazione delle queries su $P$, rimpiazzandola con l'ordinaria risoluzione SLD su $<P^{+},P^{-}>$. La correttezza di questo procedimento è provata dal seguente teorema:

Teorema 5.5  

Per ogni atomo ground $q(u)$ in $B_{L}$, con $L$ linguaggio del programma $P$:

1. $q(u) \in SS_{SLDNF}(P) \ \Leftrightarrow \ q(u) \in SS_{SLD}(P^{+} \cup P^{-})$

2. $q(u) \in FF_{SLDNF}(P) \ \Leftrightarrow \ \tilde q(u) \in SS_{SLD}(P^{+} \cup P^{-})$

e, dualmente,

1. $q(u) \in FF_{SLDNF}(P) \ \Leftrightarrow \ q(u) \in FF_{SLD}(P^{+} \cup P^{-})$

2. $q(u) \in SS_{SLDNF}(P) \ \Leftrightarrow \ \tilde q(u) \in FF_{SLD}(P^{+} \cup P^{-})$