Negarea ca eșec

Negarea ca eșec ^[1] (cunoscută și sub numele de NaF , din engleză negation as failure , sau negație în mod implicit ) este o regulă de inferență non- monotonă utilizată în programarea logică pentru a obține $\mathrm {not} ~p$ ${\ displaystyle \ mathrm {not} ~ p}$ ${\ displaystyle \ mathrm {not} ~ p}$ din eșecul derivării $p$ ${\ displaystyle ~ p}$ ${\ displaystyle ~ p}$ , unde este $p$ ${\ displaystyle ~ p}$ ${\ displaystyle ~ p}$ este un atom care nu poate fi dedus automat din program (deoarece nu este o consecință logică a faptelor și regulilor conținute în program).

Conceptul negației ca eșec a fost introdus de Keith L. Clark în articolul cu același nume din 1978.

Descriere

Această metodă este implementarea tipică a presupunerii lumii închise (CWA), conform căreia orice atom care nu este o consecință logică directă a programului este considerat fals. Acesta din urmă nu poate fi implementat literal, deoarece, în general, deducerea logică a unui atom pornind de la un anumit program este o problemă care nu poate fi rezolvată în timp finit.

De exemplu, având în vedere o bază de cunoștințe:

KB:=\{Cane(pluto),Cane(lassie),Cane(rex),Gatto(silvestro)\}

{\ displaystyle KB: = \ {Dog (bar), Dog (lassie), Dog (rex), Cat (sylvester) \}}

{\ displaystyle KB: = \ {Dog (bar), Dog (lassie), Dog (rex), Cat (sylvester) \}}

în teorie, este imposibil să se evalueze afirmația a priori $\neg Cane(silvestro)$ ${\ displaystyle \ neg Dog (sylvester)}$ ${\ displaystyle \ neg Dog (sylvester)}$ , întrucât este imposibil de spus a priori dacă $Cane(silvestro)$ ${\ displaystyle Dog (sylvester)}$ ${\ displaystyle Dog (sylvester)}$ este derivabil (prin urmare adevărat) sau nedirectabil (prin urmare fals, pentru CWA) din celelalte afirmații.

Din acest motiv, au fost implementate modele CWA mai limitate în limbajele de programare logice, dar care garantează încetarea programului și corectitudinea răspunsului. Negarea ca eșec, de fapt, de verificat $\mathrm {not} ~p$ ${\ displaystyle \ mathrm {not} ~ p}$ ${\ displaystyle \ mathrm {not} ~ p}$ (adică pentru a verifica asta $p$ ${\ displaystyle ~ p}$ ${\ displaystyle ~ p}$ nu este diferențiat) utilizează rezoluția SLD examinând doar așa-numiții arbori de eșec finit înrădăcinat $p$ ${\ displaystyle ~ p}$ ${\ displaystyle ~ p}$ . Din acest motiv, regula se numește mai corect negație ca eșec finalizat .

Prolog

De exemplu, având în vedere următorul program Prolog :

 bunic ( X , Z ) : - tată ( X , Y ), părinte ( Y , Z ).
părinte ( X , Y ) : - tată ( X , Y ).
părinte ( X , Y ) : - mamă ( X , Y ).
tată ( a , b ).
mama ( b , c ).

să răspund la întrebare ?- not nonno(a,b). , va trebui să extindă arborele cu nonno(a,b) rădăcină nonno(a,b) , din care urmează padre(a,X), genitore(X,b) și apoi, nedeterminat , padre(X,b) și madre(X,b) . Ambele ramuri ale copacului eșuează: prima pentru că nu există un X care să satisfacă simultan padre(a,X) și padre(X,b) ; a doua deoarece madre(X,b) nu are nicio referință în extensia la baza de date.

Rezultă că nonno(a,b) este fals și răspunsul a

 ? - nu bunicul ( a , b ).

Sara

 da .

Notă

^ Russel-Norvig , p. 453 .

Bibliografie

( EN ) KL Clark, Negation as failure ( PDF ), în Logic and Data Bases , Gallaire și Minker, 1978, ISBN 978-1-4684-3386-9 .
Stuart Russel, Peter Norvig, Inteligența artificială - O abordare modernă , vol. 1, ediția a II-a, Milano, Pearson Education Italia, 2005, ISBN 88-7192-228-X .

Elemente conexe

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] Russel-Norvig , p. 453 .

[1]