Топ-100
Indietro

ⓘ Negazione come fallimento. La negazione come fallimento è una regola di inferenza non monotòna utilizzata nella programmazione logica per derivare n o t p {\dis ..




                                     

ⓘ Negazione come fallimento

La negazione come fallimento è una regola di inferenza non monotòna utilizzata nella programmazione logica per derivare n o t p {\displaystyle \mathrm {not} ~p} dal fallimento nel derivare p {\displaystyle ~p}, dove p {\displaystyle ~p} è un atomo che non si può dedurre automaticamente dal programma.

Questo metodo è la tipica implementazione della closed-world assumption CWA, secondo cui ogni atomo che non è conseguenza logica diretta del programma è considerato falso. Questultima non può essere implementata alla lettera poiché, in generale, la deduzione logica di un atomo a partire da un programma dato è un problema non risolvibile in tempo finito.

Ad esempio, dato un knowledge base:

K B:= { C a n e p l u t o, C a n e l a s i e, C a n e r e x, G a t o s i l v e s t r o } {\displaystyle KB:=\{Canepluto,Canelassie,Canerex,Gattosilvestro\}}

in teoria, è impossibile valutare a priori la dichiarazione ¬ C a n e s i l v e s t r o {\displaystyle \neg Canesilvestro}, poiché è impossibile dire a priori se C a n e s i l v e s t r o {\displaystyle Canesilvestro} è derivabile quindi vero o non derivabile quindi falso, per la CWA dalle altre asserzioni.

Per questo motivo, nei linguaggi di programmazione logica sono stati implementati modelli più limitati della CWA ma che garantiscono la terminazione del programma e la correttezza della risposta. La negation as failure, infatti, per verificare n o t p {\displaystyle \mathrm {not} ~p} ovvero, per verificare che p {\displaystyle ~p} non è derivabile utilizza la risoluzione SLD esaminando soltanto i cosiddetti alberi di fallimento finito con radice p {\displaystyle ~p}. Per questo motivo, la regola è detta più propriamente negazione come fallimento finito.

                                     

1. Prolog

Ad esempio, dato il seguente programma Prolog:

per rispondere alla domanda?- not nonnoa,b., dovrà espandere lalbero con radice nonnoa,b, da cui segue padrea,X, genitoreX,b e poi, indeterministicamente, padreX,b e madreX,b. Entrambi i rami dellalbero falliscono: il primo perché non esiste alcuna X che soddisfi contemporaneamente padrea,X e padreX,b ; il secondo perché madreX,b non ha alcun riferimento nellextensional database.

Segue che nonnoa,b risulta falso e la risposta a

sarà