[科普中國(guó)]-基子句集

如果一個(gè)子句中的原子公式都是基礎(chǔ)文字，那么它就是基礎(chǔ)子句(也稱(chēng)基子句)。特別地，空子句是基礎(chǔ)子句?；A(chǔ)子句的集合稱(chēng)為基礎(chǔ)子句集(也稱(chēng)基子句集)1。

定義不含有任何連接詞的謂詞公式叫原子公式，簡(jiǎn)稱(chēng)原子，而原子或原子的否定統(tǒng)稱(chēng)文字。子句就是由一些文字組成的析取式。由子句構(gòu)成的集合稱(chēng)為子句集。將沒(méi)有變?cè)霈F(xiàn)的子句集分別稱(chēng)作基子句集2。

相關(guān)概念定義1 不含有任何連接詞的謂詞公式叫原子公式，簡(jiǎn)稱(chēng)原子，而原子或原子的否定統(tǒng)稱(chēng)文字2。

定義2 子句就是由一些文字組成的析取式。

定義3 不包含任何文字的子句稱(chēng)為空子句，記為 。

定義4 由子句構(gòu)成的集合稱(chēng)為子句集。

定義5 設(shè)謂詞公式G的子句集為S，則按下述方法構(gòu)造的個(gè)體變?cè)騂稱(chēng)為公式G或子句集S的Herbrand域，簡(jiǎn)稱(chēng)H域。

(1)令H0是S中所出現(xiàn)的常量的集合。若S中沒(méi)有常量出現(xiàn)，就任取一個(gè)常量 ，規(guī)定 。

(2)令 {S中所有的形如 的元素)，其中 是出現(xiàn)于

G中的任一函數(shù)符號(hào)，而 是 中的元素。i=0，1，2，…。

定義6下列集合稱(chēng)為子句集S的原子集：

A={所有形如 的元素}

其中， 是出現(xiàn)在S中的任一謂詞符號(hào)，而 則是S的H域上的任意元素。

定義7 將沒(méi)有變?cè)霈F(xiàn)的原子、文字、子句和子句集分別稱(chēng)作基原子、基文字、基子句和基子句集。

定義8 當(dāng)子句集S中的某個(gè)子句C中的所有變?cè)?hào)均以其H域中的元素替換時(shí)，所得到的基子句稱(chēng)作C的一個(gè)基例。

定義9(可滿(mǎn)足性、不可滿(mǎn)足性)對(duì)于一個(gè)變?cè)杂傻囊浑A語(yǔ)言公式G，如果至少存在一個(gè)D論域上的一個(gè)解釋，在此解釋下G為真，則稱(chēng)G是可滿(mǎn)足的，即；反之，如果對(duì)于任何解釋G均為假，則稱(chēng)G是不可滿(mǎn)足的，即。

對(duì)于一個(gè)變?cè)杂傻囊浑A語(yǔ)言公式集，即，如果至少存在一個(gè)D的解釋，在此解釋下，的每個(gè)以D為論域的公式均為真，則稱(chēng)為可滿(mǎn)足的；如果D的所有解釋都有假公式，則稱(chēng)是不可滿(mǎn)足的1。

不可滿(mǎn)足意義下的一致性

定理1 設(shè)有謂詞公式G，而其相應(yīng)的子句集為S，則G是不可滿(mǎn)足的充分必要條件是S是不可滿(mǎn)足的。

要再次強(qiáng)調(diào)：公式G與其子句集S并不等值，只是在不可滿(mǎn)足意義下等價(jià)。

的子句集

當(dāng) 時(shí)，若設(shè)P的子句集為 ， 的子句集為 ，則一般

情況下， 并不等于 ，而是要比 復(fù)雜得多。但是，在不可滿(mǎn)足的意義下，子句集 與 是一致的，即 不可滿(mǎn)足 不可滿(mǎn)足2。

海伯倫(Herbrand)理論H域上的解釋

定義10 如果子句集S的原子集為A，則對(duì)A中各元素的真假值的一個(gè)具體設(shè)定都是S的一個(gè)H解釋2。

可以證明，在給定域D上的任一個(gè)解釋 ，總能在H域上構(gòu)造一個(gè)解釋與之對(duì)應(yīng)，使得如果D域上的解釋能滿(mǎn)足子句集S，則在H域的解釋也能滿(mǎn)足S(即若，就有)。

定理2 設(shè)是子句集S在域D上的一個(gè)解釋?zhuān)瑒t存在對(duì)應(yīng)于的H域解釋，使得若有，就必有。

定理3 子句集S不可滿(mǎn)足的充要條件是S對(duì)H域上的一切解釋都為假。

證明： 充分性：若S在一般域D上是不可滿(mǎn)足的，必然在H域上是不可滿(mǎn)足的，從而對(duì)H域上的一切解釋都為假。

必要性：若S在任一H解釋下均為假，必然會(huì)使S在D域上的每一個(gè)解釋為假。否則，如果存在一個(gè)解釋使S為真，那么依據(jù)定理2可知，一定可以在H域找到相對(duì)應(yīng)的一個(gè)解釋使S為真。這與S在所有H解釋下均為假矛盾。

定理4 子句集S不可滿(mǎn)足的充要條件是存在一個(gè)有限的不可滿(mǎn)足的基例集S’。

該常理稱(chēng)為Herbrand定理2。

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

胡建平 - 副教授 - 西北工業(yè)大學(xué)