設(shè)謂詞公式G的子句集為S，則按下述方法構(gòu)造的個(gè)體變?cè)騂稱為公式G或子句集S的海伯倫域(Herbrand域，簡(jiǎn)稱H域)：(1)令H0是S中所出現(xiàn)的常量的集合。若S中沒(méi)有常量出現(xiàn)，就任取一個(gè)常量a∈D，規(guī)定H0=a。(2)令Hi+1=Hi∪{S中所有的形如f(t1,...,tn)的元素)，其中f(t1,...,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，而t1,...,tn是Hi中的元素。i=0，1，2，…。

外文名

Herbrand Universes

所屬學(xué)科

數(shù)學(xué)

定義

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

子句集S中的基礎(chǔ)子句的項(xiàng)(常元)構(gòu)成S的

海伯倫域

(Herbrand域，簡(jiǎn)稱H域，Herbrand Universes)，構(gòu)成方法如下：令F是出現(xiàn)在S中的函數(shù)符號(hào)的集合，除非F包含的所有函數(shù)符號(hào)均為0階(這時(shí)公式退化為常量的集合)，否則，F(xiàn)是集合，其中表示S中的常元，，D是一個(gè)個(gè)體域：F是函數(shù)構(gòu)成的表達(dá)式的集合，是的映射。S的H域是所有項(xiàng)的集合，。

由于F的階可超窮增加，因此，H域是一個(gè)可數(shù)超窮集。

例題解析

海伯倫域

海伯倫域

海伯倫域

例1

求的H城，是解釋的常元，是變?cè)?/p>

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

例2

求命題的子句集的H域。

海伯倫域

海伯倫域

海伯倫域

(是常元)

海伯倫域

海伯倫域

海伯倫域

海伯倫域

(最外層的中有n個(gè))

海伯倫域

海伯倫域

海伯倫域

即的H域。

海伯倫化

海伯倫域

海伯倫域

Herbrand化(H化)

子句(或文字A，或原子A)的所有變?cè)籋域的元素替換，這一過(guò)程稱為H化，H化的結(jié)果稱為一個(gè)H化基例，也稱為H化基子句 (或H化基文字，或H化基原子)。

海伯倫域

海伯倫域

例3

，的H化的若干結(jié)果是

海伯倫域

海伯倫域

海伯倫域

現(xiàn)在考慮對(duì)子句結(jié)構(gòu)進(jìn)行進(jìn)一步的細(xì)化分析。

海伯倫域

海伯倫域

海伯倫域

子句集中允許有V連接的子句，如。如果細(xì)分它為更簡(jiǎn)單的形式即兩個(gè)原子和。

海伯倫域

子句集中的原子A的H域解釋

是指子句集的每個(gè)原子A進(jìn)行H化基原子。然后指定(映射到)一個(gè)真假值，即A的H域解釋是，A是子句集中的H化原子。

海伯倫域

顯然，原子A的H化是更“小”的命題結(jié)構(gòu)的H化，也是解釋的特例。

海伯倫域

子句或原子的H化是以下所述的一階公式G的解釋的特例，即解釋域?yàn)橛騂。

海伯倫域

一階公式G的一個(gè)解釋

是指對(duì)公式G的變?cè)?、函?shù)、原子謂詞公式進(jìn)行如下指定(映射)：

(1)從非空的項(xiàng)變?cè)≈捣秶鶧內(nèi)為每個(gè)項(xiàng)變?cè)付ㄒ粋€(gè)元素，即{公式G的項(xiàng)變?cè)?#125;→D；

海伯倫域

(2)為每個(gè)m元函數(shù)指定一個(gè)D的元素，即；

海伯倫域

(3)為每個(gè)n元原子謂詞公式指定一個(gè)真假值，即。

第(1)步稱為半解釋。后面對(duì)其他非空域進(jìn)行變?cè)馁x值也稱為相應(yīng)域的半解釋。

相關(guān)概念

定義1

不含有任何連接詞的謂詞公式叫 原子公式，簡(jiǎn)稱

原子

，而原子或原子的否定統(tǒng)稱

文字

。

定義2子句

就是由一些文字組成的析取式。

海伯倫域

定義3

不包含任何文字的子句稱為

空子句

，記為。

定義4

由子句構(gòu)成的集合稱為

子句集

。

定義5

設(shè)謂詞公式G的子句集為S，則按下述方法構(gòu)造的個(gè)體變?cè)騂稱為公式G或子句集S的

Herbrand域

，簡(jiǎn)稱

H域

。

海伯倫域

海伯倫域

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

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

(2)令{S中所有的形如的元素)，其中是出現(xiàn)于G中的任一函數(shù)符號(hào)，而是中的元素。i=0，1，2，…。

定義6

下列集合稱為子句集S的

原子集

：

海伯倫域

A={所有形如的元素}

海伯倫域

海伯倫域

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

定義7

將沒(méi)有變?cè)霈F(xiàn)的原子、文字、子句和子句集分別稱作

基原子

、

基文字

、

基子句

和

基子句集

。

定義8

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

基例

。

海伯倫域

海伯倫域

海伯倫域

海伯倫域

定義9

(可滿足性、不可滿足性)對(duì)于一個(gè)變?cè)杂傻囊浑A語(yǔ)言公式G，如果至少存在一個(gè)D論域上的一個(gè)解釋，在此解釋下G為真，則稱G是

可滿足

的，即；反之，如果對(duì)于任何解釋G均為假，則稱G是

不可滿足

的，即，或。

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

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

不可滿足意義下的一致性

定理1

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

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

海伯倫域

的子句集

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

當(dāng)時(shí)，若設(shè)P的子句集為，的子句集為，則一般情況下，并不等于，而是要比復(fù)雜得多。但是，在不可滿足的意義下，子句集與是一致的，即不可滿足不可滿足。

海伯倫理論

H域上的解釋

定義10

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

H解釋

。

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

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

海伯倫域

海伯倫域

海伯倫域

海伯倫域

海伯倫域

定理2

設(shè)是子句集S在域D上的一個(gè)解釋，則存在對(duì)應(yīng)于的H域解釋，使得若有，就必有。

定理3

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

證明：

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

海伯倫域

海伯倫域

海伯倫域

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

定理4

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

該常理稱為Herbrand定理。