Negace jako selhání - Negation as failure

Negace jako selhání (NAF, zkráceně) je a nemonotónní pravidlo odvození v logické programování, používá se k odvození ${ displaystyle mathrm {not} ~ p}$ (tj. to ${ displaystyle ~ p}$ se předpokládá, že nebude držet) ze selhání odvození ${ displaystyle ~ p}$. Všimněte si, že ${ displaystyle mathrm {not} ~ p}$ se může lišit od výpisu ${ displaystyle neg p}$ z logická negace z ${ displaystyle ~ p}$, záleží na úplnost odvozovacího algoritmu, a tedy i na formálním logickém systému.

Negace jako selhání byla důležitou vlastností logického programování od prvních dnů obou Plánovač a Prolog. V Prologu se obvykle implementuje pomocí extralogických konstruktů Prologu.

Sémantika plánovače

V Planneru lze negaci jako selhání implementovat takto:

-li (ne (fotbalová branka p)), pak (tvrdit ¬p)

který říká, že pokud je vyčerpávající hledání dokázat p selže, pak tvrdí ¬p.^[1] To uvádí tento návrh p se při každém dalším zpracování předpokládá jako „není pravdivé“. Nicméně, Planner není založen na logickém modelu, logická interpretace předchozího zůstává nejasná.

Sémantika prologu

V čistém Prologu, literály NAF formuláře ${ displaystyle mathrm {not} ~ p}$ může nastat v těle klauzulí a lze je použít k odvození dalších literálů NAF. Například vzhledem k tomu, jen čtyři věty

${ displaystyle p leftarrow q land mathrm {not} ~ r}$

${ displaystyle q leftarrow s}$

${ displaystyle q leftarrow t}$

${ displaystyle t leftarrow}$

NAF je odvozeno ${ displaystyle mathrm {not} ~ s}$, ${ displaystyle mathrm {not} ~ r}$ a ${ displaystyle ~ p}$.

Sémantika dokončení

Sémantika NAF zůstala otevřeným problémem až do roku 1978, kdy Keith Clark ukázal, že je to správné s ohledem na dokončení logického programu, kde, volně řečeno, „pouze“ a ${ displaystyle leftarrow}$ jsou interpretovány jako „kdyby a jen kdyby“, psané jako „iff“ nebo „${ displaystyle equiv}$".

Například dokončení čtyř výše uvedených klauzulí je

${ displaystyle p equiv q land mathrm {not} ~ r}$

${ displaystyle q equiv s lor t}$

${ displaystyle t equiv mathrm {true}}$

${ displaystyle r equiv mathrm {false}}$

${ displaystyle s equiv mathrm {false}}$

Pravidlo odvození NAF simuluje uvažování explicitně s dokončením, kde jsou obě strany ekvivalence negovány a negace na pravé straně je distribuována dolů na atomové vzorce. Například ukázat ${ displaystyle mathrm {not} ~ p}$„NAF simuluje uvažování s ekvivalencemi

${ displaystyle mathrm {not} ~ p equiv mathrm {not} ~ q lor r}$

${ displaystyle mathrm {not} ~ q equiv mathrm {not} ~ s land mathrm {not} ~ t}$

${ displaystyle mathrm {not} ~ t equiv mathrm {false}}$

${ displaystyle mathrm {not} ~ r equiv mathrm {true}}$

${ displaystyle mathrm {not} ~ s equiv mathrm {true}}$

V non-výrokovém případě je třeba doplnit doplnění o axiomy rovnosti, aby se formalizoval předpoklad, že jednotlivci s odlišnými jmény jsou odlišní. NAF to simuluje selháním sjednocení. Například, vzhledem k tomu pouze dvě věty

${ displaystyle p (a) leftarrow}$

${ displaystyle p (b) leftarrow}$ t

NAF je odvozeno ${ displaystyle mathrm {not} ~ p (c)}$.

Dokončení programu je

${ Displaystyle p (X) equiv X = a lor X = b}$

rozšířené o axiomy jedinečných jmen a axiomy uzavření domény.

Sémantika dokončení úzce souvisí s popis a do předpoklad uzavřeného světa.

Autoepistemická sémantika

Sémantika dokončení ospravedlňuje interpretaci výsledku ${ displaystyle mathrm {not} ~ p}$ závěru NAF jako klasické negace ${ displaystyle neg p}$ z ${ displaystyle p}$. V roce 1987 však Michael Gelfond ukázal, že je také možné interpretovat ${ displaystyle mathrm {not} ~ p}$ doslova jako „${ displaystyle p}$ nelze zobrazit ","${ displaystyle p}$ není známo „nebo“${ displaystyle p}$ není věřeno ", jako v autoepistemická logika. Autoepistemickou interpretaci dále rozvinuli Gelfond a Lifschitz v roce 1988 a je základem programování sady odpovědí.

Sémantika autoepistemiky čistého programu Prolog P s literály NAF se získá „rozšířením“ P sadou základních (bez proměnných) literálů NAF Δ, což je stabilní V tom smyslu, že

Δ = {${ displaystyle mathrm {not} ~ p}$ | ${ displaystyle p}$ není implikováno P ∪ Δ}

Jinými slovy, soubor předpokladů Δ o tom, co nelze zobrazit, je stabilní právě když Δ je množina všech vět, které z programu P rozšířeného o Δ skutečně nelze zobrazit. Tady, kvůli jednoduché syntaxi čistých programů Prolog, lze „implicitně“ chápat velmi jednoduše jako odvozitelnost pomocí modus ponens a samotného univerzálního instancování.

Program může mít nulové, jedno nebo více stabilních rozšíření. Například,

${ displaystyle p leftarrow mathrm {not} ~ p}$

nemá stabilní expanze.

${ displaystyle p leftarrow mathrm {not} ~ q}$

má přesně jednu stabilní expanzi Δ = {${ displaystyle mathrm {not} ~ q}$}

${ displaystyle p leftarrow mathrm {not} ~ q}$

${ displaystyle q leftarrow mathrm {not} ~ p}$

má přesně dvě stabilní expanze Δ₁ = {${ displaystyle mathrm {not} ~ p}$} a Δ₂ = {${ displaystyle mathrm {not} ~ q}$}.

Autoepistemickou interpretaci NAF lze kombinovat s klasickou negací, jako v rozšířeném logickém programování a programování sady odpovědí. Spojením dvou negací je možné vyjádřit například

${ displaystyle neg p leftarrow mathrm {not} ~ p}$(předpoklad uzavřeného světa) a

${ displaystyle p leftarrow mathrm {not} ~ neg p}$ (${ displaystyle p}$ výchozí nastavení).

Poznámky pod čarou

Reference

• K. Clark [1978, 1987]. Negace jako selhání. Čtení v monotónním uvažování, Morgan Kaufmann Publishers, strany 311-325.
• M. Gelfond [1987] O stratifikovaných autoepistemických teoriích Proc. AAAI 1987, strany 207-211.
• M. Gelfond a V. Lifschitz [1988] Sémantika stabilního modelu pro logické programování Proc. 5. mezinárodní konference a sympozium o logickém programování (R. Kowalski a K. Bowen, eds), MIT Press, strany 1070-1080.
• J.C. Shepherdson [1984] Negace jako selhání: Srovnání Clarkovy dokončené datové databáze a Reiterova předpokladu uzavřeného světa, Journal of Logic Programming, svazek 1, 1984, strany 51–81.
• J.C. Shepherdson [1985] Negace jako porucha II, Journal of Logic Programming, sv. 3, 1985, strany 185-202.

externí odkazy

• Zpráva z workshopu W3C o pravidlech jazyků pro interoperabilitu. Zahrnuje poznámky o NAF a SNAF (rozsahovaná negace jako porucha).