[科普中國(guó)]-回答集編程

回答集編程是語法上類似傳統(tǒng)邏輯編程而語義上密切于非單調(diào)邏輯的一種聲明式編程。在傳統(tǒng)邏輯編程和回答集編程之間的主要區(qū)別是如何表示否定為失敗。在傳統(tǒng)邏輯編程中，否定為失敗指示推導(dǎo)失?。辉诨卮鸺幊讨?，它指示一個(gè)文字的一致性。

語法回答集編程由規(guī)則的集合構(gòu)成，每個(gè)規(guī)則由一個(gè)頭部和一個(gè)后部構(gòu)成:

head \leftarrow body

規(guī)則的頭部和后部二者都是文字的集合，每個(gè)文字都是可能被否定的原子。與傳統(tǒng)邏輯程序相反，原子都是命題而不是一階的，并且可以使用兩種形式的否定去否定它們: 經(jīng)典否定(指示為 \neg)和否定為失敗(指示為 not)。文字要么是原子要么是(使用經(jīng)典否定)否定的原子。下面是一個(gè)例子程序:

a \leftarrow b, not~c

a, not~\neg c \leftarrow not~d, \neg e

\neg c \leftarrow not~\neg e, a

依據(jù)第一個(gè)規(guī)則，a 是真，只要 b 是真，并且 c 可以被假定為假而不產(chǎn)生矛盾。1

語義程序的語義基于它的回答集，每個(gè)回答集都是文字集合。對(duì)于不包含否定為失敗的程序，程序的語義基于閉包和最小性的概念:

程序在一個(gè)文字集合下閉合，如果這個(gè)集合包含至少一個(gè)在某個(gè)規(guī)則的頭部中的文字，而總是包含在規(guī)則的體部中的所有文字。

文字集合是一個(gè)程序回答集，如果在這個(gè)程序閉合于的文字集合中、它(在集合的容量(containment)上)是最小化的。

如果程序包含使用否定為失敗否定的一些文字，語義要求額外的簡(jiǎn)約概念:

一個(gè)程序在一個(gè)文字集合下的簡(jiǎn)約是通過對(duì)每個(gè)規(guī)則進(jìn)行下列變更而獲得的程序:

除去在頭部中的、使用否定為失敗否定的并且在集合中的所有文字；

除去在后部中的、使用否定為失敗否定的并且在集合中不包含的所有文字；

刪除整個(gè)規(guī)則，如果在應(yīng)用完上面兩個(gè)規(guī)則之后，它仍然包含(使用否定為失敗)否定的原子。

文字集合是一個(gè)程序的回答集，如果它是這個(gè)程序在這個(gè)集合自身下的簡(jiǎn)約的回答集。換句話說，可以通過運(yùn)行下列非確定性的算法來計(jì)算一個(gè)回答集可以:

選擇文字集合 L;

計(jì)算程序 P 在 L 下的簡(jiǎn)約 PL;

如果 L 是 PL 所閉合的最小化文字集合則

輸出 L

最初的文字集合 L 的選擇是非確定性的。確定 L 是否為一個(gè)回答集的算法，首先計(jì)算程序在 L 下的簡(jiǎn)約，并接著檢查 L 是否是這個(gè)無否定為失敗的程序的回答集。

一個(gè)回答集程序可以有零個(gè)、一個(gè)或多個(gè)回答集。一個(gè)程序蘊(yùn)涵一個(gè)文字，如果它的所有的回答集都包含這個(gè)文字。2

比較與 Prolog 相反，回答集程序的語義不依賴于規(guī)則的求值和原子在每個(gè)規(guī)則中的特定次序。1

比較、復(fù)雜性和實(shí)現(xiàn)與Prolog相反，回答集程序的語義不依賴于規(guī)則的求值和原子在每個(gè)規(guī)則中的特定次序。

檢查一個(gè)程序的回答集的存在性的復(fù)雜性，和檢查一個(gè)程序是否蘊(yùn)涵一個(gè)文字復(fù)雜性，范圍是從P到多項(xiàng)式層次的第二級(jí)，依賴于一個(gè)程序可以滿足也可以不滿足的一組條件(就是說分層、頭部中的析取)。

實(shí)現(xiàn)了回答集編程的三個(gè)系統(tǒng)是：smodels、dlv 和 cmodels。2

本詞條內(nèi)容貢獻(xiàn)者為:

李航 - 副教授 - 西南大學(xué)