人工智能第三章歸結推理方法課件

第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理歸結推理命題邏輯謂詞邏輯Skolem標準形、子句集基本概念謂詞邏輯歸結原理合一和置換、控制策略數(shù)理邏輯命題邏輯歸結Herbrand定理第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理定義能夠分辨真假的語句稱作命題。定義一個語句如果不能再進一步分解成更簡單的語句，并且又是一個命題，則稱此命題為原子命題。原子命題是命題中最基本的單位。我們一般用P、Q、R、…大寫拉丁字母表示命題，而命題的真與假分別用“T”與“F”表示。用大寫英文字母表示的命題既可以是一個特定的命題，也可以是一個抽象的命題。前者稱為命題常量，后者稱為命題變量。對于命題變量而言，只有把確定的命題代入后，它才可能有明確的邏輯值（T或F）。3.1命題邏輯3.1.1命題命題：能判斷真假（不是既真又假）的陳述句。

簡單陳述句描述事實、事物的狀態(tài)、關系等性質。例如：1．

1+1=22．

雪是黑色的。3．

北京是中國的首都。4．

到冥王星去渡假。

判斷一個句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現(xiàn)在是假，隨著人類科學的發(fā)展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個例子都是命題。而例如：1．

快點走吧！2．

到那去？3．

x+y>10

等等句子，都不是命題。命題表示公式（1）將陳述句轉化成命題公式。如：設“下雨”為p，“騎車上班”為q，，1．“只要不下雨，我騎自行車上班”?！玴是q的充分條件， 因而，可得命題公式：～p→q2．“只有不下雨，我才騎自行車上班”。～p是q的必要條件， 因而，可得命題公式：q→～p命題公式的解釋p79定義：設公式A含有n個命題變項p，p，…，p，給p，p，…，p各指定一個值，稱為對A的一個賦值或解釋。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值，若使A的真值為假，則稱這組值為A的成假賦值。若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。求下列公式的真值表，并求成真賦值和成假賦值:┐p∧q）→┐r命題邏輯基礎基本等值式24個p80交換率：p∨q<=>q

∨p

；

pΛq<=>qΛp

結合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

命題邏輯基礎基本等值式p80摩根率:～(p∨q)

<=>～

pΛ

～q

；

～(pΛq)

<=>～

p∨

～q

吸收率:p∨(pΛq)<=>p；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p；

pΛ1

<=>p

蘊含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。范式的性質：析取范式是矛盾式，當且僅當每個簡單合取式是矛盾式。合取范式是永真式，當且僅當每個簡單析取式是永真式。存在定理：任何命題公式都存在著與之等值的析取范式和合取范式。求合取范式的步驟：（１）消去多余的｛∨，∧｝以及→聯(lián)結詞（２）去掉否定～符號（３）利用分配率例：3.1,3.2命題證明方法1（自然演繹推理）---P83邏輯結論：對于Ａ→Ｂ，如果永真，則稱Ｂ是Ａ的邏輯結論，即Ａ推出Ｂ的結論正確，Ａ為真則Ｂ為真，記為Ａ=>Ｂ。常用推理定律：附加：Ａ=>（Ａ∨Ｂ）簡化：（Ａ∧Ｂ）=>Ａ

析取三段論:┓A，A∨B?B

假言三段論:A→B，B→C?A→C

等價三段論:A?B，B?C?A?C

構造性二難:A→C，B→D，A∨B?C∨D假言推理:A→B?B拒取式:┓B，A→B?┓A

P84/例3.3常用的推理規(guī)則：

（１）前提引入規(guī)則

（２）結論引入規(guī)則

（３）置換規(guī)則：等價的可以置換例３.4：證明：如果今天是下雨天，則要帶傘或帶雨衣。如果走路上班，則不帶雨衣。今天下雨，走路上班，所以帶雨傘。解：把題目用命題公式表示：今天下雨p，帶傘q，帶雨衣r，走路上班s前提：p→（q∨r），s→～r，p，s要證的結論：q

證明：①p→（q∨r）②p前提引入

③（q∨r）假言推理

④s⑤s→～r前提引入

⑥～r假言推理⑦q析取三段論什么叫歸結歸結式：對任意兩個子句C1和C2，若C1中有一個文字L1，而C2中有一個與L1成互補的文字L2，則分別從C1、C2中刪去L1和L2，并將其剩余部分組成新的析取式，則稱這個新子句為歸結式或預解式。這里的"□"表示"空"的意思，有時用NIL表示。如果子句集中出現(xiàn)了"空"，則表示該子句集存在矛盾，是不可滿足的。例：設兩個子句C1＝L∨C1′，C2＝（~L）∨C2′，則歸結式C＝C1′∨C2′。當C1′＝C2′＝□時，C＝□。

命題證明方法2--命題邏輯的歸結反演法基本單元：簡單命題（陳述句）歸結法基本方法：

例如：命題：A1、A2、A3和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B歸結反演即采用反證法（或歸謬法）p85：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

命題邏輯的歸結法建立子句集(例如P86/3.53.6)合取范式：命題、命題和的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

歸結式設C1,C2是子句集中的兩個子句，如果C1中的文字L1與C2中文字L2互補，則可以從C1和

C2中分別消去文字L1和文字L2，并將中余下的部分按析取關系構成一個新子句C12，這個過程就叫歸結。如子句：C1=P∨Q,C2=~P∨W

，歸結式：C12

=W∨Q

性質：歸結式C12是親本子句C1和

C2邏輯結論。

C1ΛC2→C12，注意：反之不一定成立。命題邏輯的歸結法歸結過程p87將命題寫成合取范式求出子句集對子句集使用歸結推理規(guī)則歸結式作為新子句參加歸結歸結式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結：除了有量詞和函數(shù)以外，其余和命題歸結過程一樣。命題邏輯歸結例題（2）子句集為： {～P∨Q，～Q，P}（4）對子句集中的子句進行歸結可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結）5.

， （2，4歸結）

由上可得原公式成立。P123/3.16--1P123/3.18—1,3第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理3.2謂詞邏輯基礎一階邏輯3.2.1基本概念個體詞：表示主語的詞謂詞：刻畫個體性質或個體之間關系的詞量詞：表示數(shù)量的詞謂詞歸結原理基礎 小王是個工程師。 8是個自然數(shù)。 我去買花。 小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個體詞，而“是個工程師”、“是個自然數(shù)”、“去買”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質，第三個謂詞“去買”表示的一個動作也表示了主、賓兩個個體詞的關系，最后一個謂詞“是朋友”表示兩個個體詞之間的關系。謂詞歸結原理基礎3.2.2一階謂詞邏輯公式及其解釋個體常量：a,b,c個體變量：x,y,z謂詞符號：P,Q,R謂詞：由謂詞符號和個體（項）組成。例P(x,y)一階謂詞：謂詞中不含有謂詞。n元謂詞：就是有n個項。量詞符號：,謂詞歸結原理基礎例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個體域D為人類集合時，可符號化為：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百歲以上。在個體域D是全總個體域時，引入特殊謂詞R(x)表示x是人，可符號化為：（1）x（R(x)→P(x)）, 其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。

3.2.2一階謂詞邏輯1謂詞公式原子公式：單個謂詞就是原子公式。謂詞公式：簡單說就是由原子公式、連接詞、否定符號以及量詞構成的式子。指導變量：量詞后面的變量稱為指導變量。x、y轄域：就是量詞管轄的區(qū)域。約束出現(xiàn)：在轄域內，受量詞約束的變量是約束出現(xiàn)。自由出現(xiàn)：在轄域內，不受量詞約束的變量是約束出現(xiàn)。換名規(guī)則：將量詞轄域中某個約束出現(xiàn)的個體變量改成在此轄域中未出現(xiàn)過的個體變量符號。xP(x,y)∧R(x,y)

約束變元與自由變元指出下列各式量詞的轄域及變元的約束情況：（1）x（F（x，y）→G（x，z））（2）x（P（x）→yR（x，y））（3）x（F（x）→G（y））→y（H（x）∧M（x，y，z））解（1）對于x的轄域是A=（F（x，y）→G（x，z）），在A中，x是約束出現(xiàn)的，而且約束出現(xiàn)兩次，y，z均為自由出現(xiàn)，而且各自由出現(xiàn)一次。（2）對于x的轄域是（P（x）→yR（x，y）），y的轄域是R（x，y），x，y均是約束出現(xiàn)的。（3）對于x的轄域是（F（x）→G（y）），其中x是約束出現(xiàn)的，而y是自由出現(xiàn)的。對y的轄域是（H（x）∧M（x，y，z）），其中y是約束出現(xiàn)的，而x，z是自由出現(xiàn)的。在整個公式中，x約束出現(xiàn)一次，自由出現(xiàn)兩次，y約束出現(xiàn)一次，自由出現(xiàn)一次，z僅自由出現(xiàn)一次。替換規(guī)則：對某個自由變量用與原公式中所有個體變量符號不同的變量去替代，且處處替代。

xP(x,y)∧R(x,y)替換xP(x,z)∧R(x,z)2.謂詞公式的解釋對謂詞公式的各變量常量去替代，就構成了一個謂詞公式的解釋。當存在解釋能使謂詞公式為真時，則稱這個解釋滿足謂詞公式。這個解釋就是這個謂詞公式的模型。兩個謂詞公式等價，當且僅當所有的解釋下兩個謂詞公式的值是相同的。永真式不可滿足式歸結原理就是對謂詞公式的正確性證明轉化為不可滿足性證明。2．約束變元的換名與自由變元的代入例對公式x（P（x）→R（x，y））∧Q（x，y）進行換名。解對約束變元x換名為t后為t（P（t）→R（t，y））∧Q（x，y）同理，對公式中的自由變元也可以更改，這種更改稱作代入。自由變元的代入規(guī)則是：（1）對于謂詞公式中的自由變元，可以代入，此時需要對公式中出現(xiàn)該自由變元的每一處進行代入。（2）用以代入的變元與原公式中所有變元的名稱都不能相同替換規(guī)則——將公式中的自由變項(所有出現(xiàn))更換成公式中未出現(xiàn)的變項。例如：

換成

(1)解：

量詞否定等值式

換名規(guī)則

量詞轄域的擴張謂詞公式的解釋P92/例子3.8給出如下的解釋I：1.非空個體域D={2,3}2.D中特定的元素a=23.函數(shù)f(x)為：f(2)=3，f(3)=24.謂詞P(x)為：P(2)=0，P(3)=1G(x,y)為：G(i,j)=1，i,j=2,3求出?x(P(f(x))∧G(x,f(x))在此解釋下的真值解：B?(P(f(2))∧G(2,f(2)))∨(P(f(3))∧G(3,f(3)))?(P(3)∧G(2,3))∨(P(2)∧G(3,2))?(1∧1)∨(0∧1)?1結論：在解釋I下，?x(P(f(x))∧G(x,f(x))為真。例子?x(F(x)∧G(x,a)解：給出如下的解釋I：1.非空個體域D={2,3}2.D中特定的元素a=23.函數(shù)f(x)為：f(2)=3，f(3)=24.謂詞F(x)為：F(2)=0，F(xiàn)(3)=1G(x,y)為：G(i,j)=1，i,j=2,3A?(F(2)∧G(2,2))∧(F(3)∧G(3,2))?0∧1∧1∧0?0結論：在解釋I下，?x(F(x)∧G(x,a)為假。3.2.3謂詞歸結原理基礎量詞否定等值式：～(x

）

M（x）<=>（y

）～

M（y）～(x

）

M（x）<=>（y

）～

M（y）量詞分配等值式：(x

）(

P（x）ΛQ（x）)<=>(x

）

P（x）Λ(x

）

Q（x）(x

）(

P（x）∨Q（x）)<=>(x

）

P（x）∨

(x

）

Q（x）消去量詞等值式：設個體域為有窮集合（a1,a2,…an）(x

）

P（x）<=>P（a1）ΛP（a2）Λ…ΛP（an）(x

）P（x）<=>P（a1）∨

P（a2）∨…∨

P（an）謂詞歸結原理基礎量詞轄域收縮與擴張等值式p93：(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）量詞擴展證明x（A（x）→B）

x（A（x）∨B）

xA（x）∨B

xA（x）∨B

xA（x）→B量詞分配定律。前束范式的定義p93定義一個公式，如果量詞均在全式的開頭且它們的轄域都延伸到整個公式的末尾，則該公式稱為前束范式。根據定義，前束范式的一般形式為：(Q1x1)(Q2x2)…(Qnxn)P(x1,x2,…,xn)。其中，

Qi(1≤i≤n)或為或為，

xi

是個體變元。沒有量詞的謂詞公式稱為平凡的前束范式?！纠?x)(y)A(x,y)(x)(y)(z)(A(x)B(y,z))

A(x,y)都是前束范式，但(x)P(x)(x)Q(x)不是前束范式。定理對于任一謂詞公式，都存在著與它等價的前束范式。證明略。將一謂詞公式轉換為與之等價的前束范式的步驟：第一步：消去冗余量詞且對給定的謂詞公式的所有約束變元換名，使之和所有的自由變元都不同名，但要保持自由變元不動。第二步：利用等價公式(AB)(AB)∧(BA)及(AB)﹁A∨B將公式中的聯(lián)結詞和去掉。第三步：利用等價公式﹁﹁AA﹁(A∨B)﹁

A∧﹁B﹁(A∧B)﹁A∨﹁B﹁(x)P(x)(x)﹁P(x)﹁(x)P(x)(x)﹁P(x)進行否定深入，將﹁號深入到命題變元和原子謂詞公式的前面。第四步：將所有的量詞移到全式的最前面。(量詞轄域的擴張與收縮)例求下列謂詞公式的前束范式。（1）xy（zA（x，z）∧A（x，z））→tB（x，y，t）解（1）xy（zA（x，z）∧A（x，z））→tB（x，y，t）

﹁xy（zA（x，z）∧A（x，z））∨tB（x，y，t）

xy（z﹁A（x，z）∨﹁A（x，z））∨tB（x，y，t）（量詞轉化）

xy（w﹁A（x，w）∨﹁A（x，z））∨tB（u，v，t）（改名及代入規(guī)則）

xywt（﹁A（x，w）∨﹁A（x，z）∨B（u，v，t））（量詞轄域擴張）

【例】將公式(x)(y)((z)(P(x,z)∧P(y,z))

(v)Q(x,y,v))化成前綴范式。解：(x)(y)((z)(P(x,z)∧P(y,z))

(v)Q(z,y,v))(x)(y)(﹁(z)(P(x,z)∧P(y,z))∨(v)Q(x,y,v))(x)(y)((z)(﹁P(x,z)∨﹁P(y,z))∨(v)Q(x,y,v))(x)(y)(z)(v)((﹁P(x,z)∨﹁P(y,z))∨Q(x,y,v))

謂詞推理P94/3.9謂詞推理涉及量詞的消去和引入。(x)P(x)==》P(y)(x)P(x)==》P(c)例：p94/3.10P94謂詞推理謂詞推理中除了運用命題邏輯相同的推理規(guī)則外，還要進行量詞的削去和引入。P95/3.10解：設Ｐ(x)：ｘ是20世紀７０年代的漫畫Q(ｙ):ｙ日本漫畫家的作品a:一幅漫畫前提x(Ｐ(x)

→Q(x)),P(a)結論Q(a)證明①x(Ｐ(x)

→Q(x))②P(a)③Ｐ(a)

→Q(a)④Q(a)謂詞推理要運用與命題邏輯相同的推理規(guī)則和量詞的消去和引入。任意量詞可以消去，用變量或常量表示，存在量詞可以用常量表示。對于任意量詞，ｘ為自由變量，ｙ為不在Ｐ中約束出現(xiàn)的個體變量時：ｘＰ（ｘ）=>Ｐ（ｙ）ｃ為常量

ｘＰ（ｘ）=>Ｐ（ｃ）對于存在量詞，

ｘＰ（ｘ）=>Ｐ（ｃ）對于變量引入量詞：

Ｐ（ｙ）=>ｘＰ（ｙ）要求ｙ在Ｐ（ｙ）中自由出現(xiàn)，且為真，ｘ不在Ｐ（ｙ）中約束出現(xiàn)。Ｐ（ｃ）=>ｘＰ（ｘ）要求ｃ是特定常量，取代ｃ的ｘ不能在Ｐ（ｃ）中出現(xiàn)。3.2.4謂詞知識表示謂詞可用來表示知識知識：是人們在認識、改造世界中經驗的總結或者實事的描述。使用邏輯法表示知識，將自然語言描述的知識，通過謂詞、函數(shù)加以描述，獲得邏輯謂詞公式，進而利用計算機進行處理。例：校長與小李打網球?？梢员硎緸椋憾x：Play(x,y,z)表示，ｘ和ｙ打ｚ這種球Play(zhang,li,tennis)清華是個大學定義：Univ(x)表示ｘ是大學Univ(qinghua)常用的可以用蘊含代表規(guī)則：人人都受法律管制：

Human(x)→Lawed(x)如果ｘ犯罪則被懲罰Commit(x)→Punished(x)（Human(x)→Lawed(x)）→（Commit(x)→Punished(x)）應用謂詞表示知識應用廣泛：（１）易于用數(shù)據庫存貯知識（２）謂詞具有完備邏輯推理方法（３）表達的知識具有科學嚴密性（４）邏輯推理具有知識的一致性3.3謂詞邏輯歸結原理3.3.1歸結原理命題：A1、A2、A3和B求證：A1ΛA2ΛA3成立，則B成立，反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）3.3.2Skolem標準形1.前束范式2.Skolem標準形Skolem標準形=前束范式中消去所有量詞的公式謂詞歸結子句形(Skolem標準形)即：把所有的量詞都提到前面去，然后消掉所有量詞 (Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)約束變項換名規(guī)則：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）謂詞歸結子句形(Skolem標準形)

量詞消去原則： （1）消去存在量詞“”，用常量a,b代替。（2）略去全程量詞“”。 注意：左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。

謂詞歸結子句形(Skolem標準形)Skolem定理p100： 謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。SKOLEM標準形定義： 消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標準形同G并不等值。謂詞歸結子句形(Skolem標準形)P100/例3.12:將下式化為Skolem標準形： ～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))解：第一步，消去→號，得： ～(～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))第二步，～深入到量詞內部，得： (x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))第三步，變元易名，得 (x)((y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量詞左移，直至所有的量詞移到前面，得： (x)(y)(u)(v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前束范式謂詞歸結子句形(Skolem標準形)

第五步，消去“”（存在量詞），略去“”全稱量詞 消去(y)，因為它左邊只有(x)，所以使用x的函數(shù)f(x)代替之，這樣得到： (x(u)(v)P(a,x,f(x))∨(Q(v,b)∨R(u)) 消去(u)，同理使用g(x)代替之，這樣得到： (x(v)P(a,x,f(x))∨(Q(v,b)∨R(g(x))) 則，略去全稱變量，原式的Skolem標準形為：

P(a,x,f(x))∨(Q(v,b)∨R(g(x)))

3.3.3子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集S的求?。篏→SKOLEM標準形 →消去存在變量 →以“，”取代“Λ”，并表示為集合形式。謂詞歸結子句形定理3.1G是不可滿足的<=>S是不可滿足的G與S不等價，但在不可滿足得意義下是一致的。

定理： 若G是給定的公式，而S是相應的子句集，則G是不可滿足的<=>S是不可滿足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G謂詞歸結子句形G=G1ΛG2ΛG3Λ…ΛGn的子句形G的字句集可以分解成幾個單獨處理。

有SG=S1US2US3U…USn 則SG

與S1US2US3U…USn在不可滿足得意義上是一致的。 即SG不可滿足<=>S1US2US3U…USn不可滿足求取子句集例(1)P102/例3.13：對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？求：用一階邏輯表示這個問題，并建立子句集。解：這里我們首先引入謂詞： P(x,y)表示x是y的父親 Q(x,y)表示x是y的祖父 ANS(x)表示問題的解答求取子句集例(2)對于第一個條件，“如果x是y的父親，y又是z的父親，則x是z的祖父”，一階邏輯表達式如下： A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對于第二個條件：“每個人都有父親”，一階邏輯表達式： A2：(y)(x)P(x,y) SA2：P(f(y),y)對于結論：某個人是它的祖父 B：(x)(y)Q(x,y) 否定后得到子句：～（(x)(y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)則得到的相應的子句集為：{SA1，SA2，S～B}第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理歸結原理歸結原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數(shù)，所以要考慮合一和置換。

3.3.4置換問題的引入：~P(x)∨Q(y)與~P(a)∨Q(z)可否歸結，只要x取a即可。置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變量。定義： 置換是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的變量，t1,t2,…,tn是不同于xi的項（常量、變量、函數(shù)）；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，而且xi不能循環(huán)地出現(xiàn)在另一個ti中。例如 {a/x，c/y，f(b)/z}是一個置換。 {g(y)/x，f(x)/y}不是一個置換，

置換的合成設＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,un/yn}，是兩個置換。 則與的合成也是一個置換，記作·。它是從集合 {t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,un/yn} 中刪去以下兩種元素：當ti=xi時，刪去ti/xi(i=1,2,…,n);當yi{x1,x2,…,xn}時，刪去uj/yj(j=1,2,…,m) 最后剩下的元素所構成的集合。合成即是對ti先做置換然后再做置換，置換xi置換的合成例：設：＝{f(y)/x,z/y}，＝{a/x,b/y,y/z}，求與的合成。解：先求出集合 {f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(b)/x,y/y,a/x,b/y,y/z} 其中，f(b)/x中的f(b)是置換作用于f(y)的結果；y/y中的y是置換作用于z的結果。在該集合中，y/y滿足定義中的條件i，需要刪除；a/x，b/y滿足定義中的條件ii，也需要刪除。最后得

·＝{f(b)/x，y/z}合一合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞公式一致”。定義：設有公式集F＝{F1，F(xiàn)2，…，F(xiàn)n}，若存在一個置換，可使F1＝F2＝…=Fn，則稱是F的一個合一。同時稱F1，F(xiàn)2，...，F(xiàn)n是可合一的。

例： 設有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，則＝{a/x,g(a)/y,f(g(a))/z}是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。

最一般合一：設δ是謂詞公式集F，如果對F的任意一個合一θ都存在一個置換λ使得θ=δ·λ，則稱δ是一個最一般的合一mgu.最一般合一求取方法：逐一比較找出不一致，并做合一置換算法：對于F1和F2①令W={F1,F2}②令k=0，W0=W,δ0=ε③如果Wk已合一，停止,δk=mgu,，否則找不一致集Dk④若Dk中存在元素vk和tk，其中vk不出現(xiàn)于tk中，轉⑤，否則不可合一⑤令δk+1=δk·{tk/vk},Wk+1=Wk·{tk/tk}=Wδk+1⑥k=k+1轉③?？勺C明若F1和F2可合一，算法必停于③一個公式集的最一般合一也可不唯一，如{P（x），P（y）}，{y/x}、{x/y}都是它的最一般合一例：設有兩個謂詞公式：E1：P(x,y,z);E2：P(x,f(a),g(b))分別從E1與E2的第一個符號開始逐個向右比較，此時發(fā)現(xiàn)E1中的y與E2中的f(a)不同，則它們構成了一個不一致集：D1={y,f(a)}當繼續(xù)向右比較時，又發(fā)現(xiàn)中E1中的z與E2中g(b)不同，則又得到一個不一致集：D2={z,g(b)}最一般合一置換的結果：σ={f(a)/y,g(b)/z}例：設E1=P(a,v,f(g(y)))，E2=P(z,f(a),f(u))，求E1和E2的最一般合一置換。答案為：σ={a/z,f(a)/v,g(y)/u}合一的其他例子p105/3.16最一般合一置換的求取算法說明下列文字集不能合一的理由：

（1）{P（f（x，x），A），P（f（y，f（y，A）)A）}

（2）{~P（A），P（x）}

（3）{P（f（A），x），P（x，A）}

答：（1）{P(f(x，x)，A)，P(f(y，f(y，A))，A)}

在合一時，f(x,x)要與f(y,f(y,a))進行合一，x置換成y后，y要與f(y,a)進行合一，出現(xiàn)了嵌套的情況，所以不能進行合一。

（2）{~P（A），P（x）}

一個是謂詞P，一個是P的反，不能合一。

（3）{P（f（A），x），P（x，A）}

在合一的過程中，x置換為f(A)，而f(A)與A不能合一。3.3.5歸結式P106謂詞歸結的注意事項：謂詞的一致性，P()與Q()，不可以歸結常量的一致性，P(a,…)與P(b,….)，不可以歸結，P(a,….)與P(x,…)，可以歸結變量與函數(shù)，P(a,x,….)與P(x,f(x),…)，不可以；是不能同時消去兩個互補對，P∨Q與～P∨～Q的空，不可以先進行內部簡化（置換、合并）

3.3.6歸結過程寫出謂詞關系公式→用反演法寫出謂詞表達式→SKOLEM標準形→子句集S→對S中可歸結的子句做歸結→歸結式仍放入S中，反復歸結過程→得到空子句

?得證P108/3.18“快樂學生”問題假設任何通過計算機考試并獲獎的人都是快樂的，任何肯學習或幸運的人都可以通過所有的考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。

解：先將問題用謂詞表示如下：R1:“任何通過計算機考試并獲獎的人都是快樂的” (x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯學習或幸運的人都可以通過所有考試” (x)(y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“張不肯學習但他是幸運的” ～Study(zhang)∧Lucky(zhang)R4:“任何幸運的人都能獲獎” (x)(Luck(x)→Win(x,prize))結論：“張是快樂的”的否定～Happy(zhang)例題“快樂學生”問題由R1及邏輯轉換公式:P∧W→H=～（P∧W）∨H，可得(1)～Pass(x,computer)∨～Win(x,prize)∨Happy(x)由R2：(2)～Study(y)∨Pass(y,z)(3)～Lucky(u)∨Pass(u,v)由R3：(4)～Study(zhang)(5)Lucky(zhang)由R4：(6)～Lucky(w)∨Win(w，prize)由結論：(7)～Happy(zhang) （結論的否定）(8)～Pass(w,computer)∨Happy(w)∨～Luck(w)(1)(6)，{w/x}(9)～Pass(zhang,computer)∨～Lucky(zhang)(8)(7)，{zhang/w}(10)

～Pass(zhang,computer) (9)(5)(11)

～Lucky(zhang) (10)(3)，{zhang/u,computer/v}(12)

?

(11)(5)

設子句集S={P∨Q，Q∨R，P，R∨T}，則其歸結過程如圖，歸結結果為T

P∨QQ∨RP∨RPRR∨TT【例題】已知：A:(x)((y)(P(x,y)∧Q(y))→(y)(R(y)∧T(x,y)))B:～(x)R(x)→(x)(y)(P(x,y)→～Q(y))求證：B是A的邏輯結論。證明首先將A和～B化為子句集(1)～P(x,y)∨～Q(y)∨R(f(x))(2)～P(x,y)∨～Q(y)∨T(x,f(x))//(1)(2)為A(3)～R(z)(4)P(a，b)(5)Q(b)//(3)(4)(5)為B(6)～P(x,y)∨～Q(y)（1）與（3）歸結，σ={f(x)/z}(7)～Q(b) （4）與（6）歸結，σ={a/x,b/y}(8)NIL（空子句）（5）與（7）歸結所以B是A的邏輯結論。課堂練習P123/3.19—(1)(2)3.21—(1)(2)用歸結方法【例題】判斷下列子句集中哪些是不可滿足的：{?P∨Q,?Q,P,?P}{P∨Q,?P∨Q,P∨?Q,?P∨?Q}{P(y)∨Q(y),?P(f(x))∨R(a)}{?P(x)∨Q(x),?P(y)∨R(y),P(a),S(a),?S(z)∨?R(z)}{?P(x)∨Q(f(x),a),?P(h(y))∨Q(f(h(y)),a)∨?P(z)}{P(x)∨Q(x)∨R(x),?P(y)∨R(y),?Q(a),?R(b)}歸結原理總結歸結法的實質：歸結法是僅有一條推理規(guī)則的推理方法。歸結的過程是一個語義樹倒塌的過程?！鵋erbrand定理的不實用性引出了可實用的歸結法。第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理3.3.7歸結過程的控制策略要解決的問題：歸結方法的知識爆炸?？刂撇呗缘哪康臍w結點盡量少控制策略的原則給出控制策略，以使僅對選擇合適的子句間方可做歸結。避免多余的、不必要的歸結式出現(xiàn)?；蛘哒f，少做些歸結仍能導出空子句?？刂撇呗缘姆椒?1) 刪除策略 => 完備名詞解釋：歸類：設有兩個子句C和D，若有置換使得C

D成立，則稱子句C把子句D歸類。 由于小的可以代表大的，所以小的吃掉大的了。例如：C=P(X),D=P(a)VQ(y)={a/x}，C=P(a){P(a)VQ(y)},事實上，P(a)成立時，P(a)VQ(y)一定成立，所以小的吃掉大的了。刪除策略1。含有永真式的子句2。被子句集中其他子句歸類的子句例子參考/thucs/GD_jsj_026y/word/text/chapter02/sec05/part1/2_5_1.htm現(xiàn)在討論歸類算法。

給了子句C，D。令

θ＝{a1/,…,an/}

其中,…,是出現(xiàn)于D中的所有變量。a1,…,an是C，D中未出現(xiàn)的常量。

設D＝L1∨…∨Lm

Dθ＝L1θ∨…∨Lmθ是基子句了。

～Dθ＝～L1θ∧…∧～Lmθ

歸類問題本是Cσ與D中部分文字合一的問題，作了上述準備，便化成了Cσ與～Dθ的歸結問題了。由于依歸類的定義，不允許D的變量做置換的，所以先將D中元素以常量代入，為用歸結法自然要將Dθ取否定。

歸類算法

(1)令W＝{～L1θ,…,～Lmθ}

(2)令K＝0，U0＝{C}

(3)如果Uk包含□，停止，這時C把D歸類。否則令UR+1＝{C1,C2的歸結式│C1∈Uk,C2∈W}

(4)如果Uk+1是空集，停止，這時C不能把D歸類。否則K+1→K轉(3)刪除歸結例:

C＝～P(x)∨(Q(f(x),a)

D=～P(h(y))∨(Q(f(h(y)),a)∨P(z)

使用歸類算法可知C把D歸類

先作θ＝{b/y,c/z}

Dθ=～P(h(b))∨Q(f(h(b)),a)∨P(c)

～Dθ={P(h(b)),～Q(f(h(b)),a),～P(c)}

(1)W={P(h(b)),～Q(f(h(b)),a),～P(c)}

(2)U0={C}={～P(x)∨Q(f(x),a)}

(3)U0不包含□，作

U1={Q(f(h(b)),a),～P(h(b))}

(4)U1不空□

(5)U2含□

從而C把D歸類?？刂撇呗缘姆椒?2)采用支撐集 <=>完備

支撐集：設有不可滿足子句集S的子集T，如果S-T是可滿足的，則T是支持集。

采用支撐集策略時，從開始到得到的整個歸結過程中，只選取不同時屬于S-T的子句，在其間進行歸結。就是說，至少有一個子句來自于支撐集T或由T導出的歸結式。

例如：A1ΛA2ΛA3Λ～B中的～B可以作為支撐集使用。要求每一次參加歸結的親本子句中，只要應該有一個是有目標公式的否定（～B）所得到的子句或者它們的后裔。支撐集策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用支撐集策略達到加快歸結速度的目的。問題是如何尋找合適的支撐集。一個最容易找到的支撐集是目標子句的非，即S～B。參考p111/例子

ST可滿足支撐集示意圖支撐集：設有不可滿足子句集S的子集T，如果S-T是可滿足的，則T是支持集。想法是簡單，想要證明

A1∧A2∧A3→B成立

或A1∧A2∧A3∧～B不可滿足

分析一下出現(xiàn)矛盾的原因，不會在A1，A2，A3間發(fā)生，自然是出于～B的引入，于是不必在找不到矛盾的A1，A2，A3間做歸結了。

采用支撐集S＝{P∨Q,～P∨R,～Q∨R，～R}

取T＝{～R}

支持集歸結過程

(1)P∨Q

(2)～P∨R

(3)～Q∨R

(4)～R

(5)～P(2)(4)

(6)～Q(3)(4)

(7)Q(1)(5)

(8)P(1)(6)

(9)R(3)(7)

(10)□(6)(7)

這是采用了支持集策略的全面歸結過程。

控制策略的方法(3) 語義歸結 <=> 完備

語義歸結策略是將子句S按照一定的語義分成兩部分，約定每部分內的子句間不允許作歸結。同時還引入了文字次序，約定歸結時其中的一個子句的被歸結文字只能是該子句中“最大”的文字。 語義歸結策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用語義歸結策略達到加快歸結速度的目的。問題是如何尋找合適的語義分類方法，并根據其含義將子句集兩個部分中的子句進行排序。P111/例子語義歸結例子（1）例:

S＝{～P∨～Q∨R,P∨R,Q∨R,～R}

我們先規(guī)定S中出現(xiàn)的文字的次序，如依次為P，Q，R或記作P>Q>R。再選取S的一個解釋I，如令

I＝{～P,～Q,～R}

用它來將S分成兩個部分。規(guī)定在I下為假的子句放入S1'中，在I下為真的子句放入S2'中。于是有

S1'={P∨R,Q∨R}

S2'＝{～P∨～Q∨R,～R}

規(guī)定S1'內部的子句不允許歸結，S1'與S2'子句間的歸結必須是S中的最大文字方可進行。這樣所得的歸結式，仍按I來放入S或S2'。

語義歸結例子（2）歸結過程

(1)～P∨～Q∨R∈S2'

(2)P∨R∈S1'

(3)Q∨R∈S1'

(4)～R∈S2'

(5)～Q∨R(2)(1)歸結∈S2'

(6)～P∨R(3)(1)歸結∈S2'

(7)R(2)(6)歸結∈S1'

(8)R(3)(5)歸結∈S1'

(9)□(7)(4)歸結控制策略的方法(4) 線性歸結 <=>完備線性歸結策略首先從子句集中選取一個稱作頂子句的子句C0開始作歸結。歸結過程中所得到的歸結式Ci立即同另一子句Bi進行歸結得歸結式Ci+1。而Bi屬于S或是已出現(xiàn)的歸結式Cj(j<i)。即，如下圖所示歸結得到的新子句立即參加歸結。線性歸結是完備的，同樣，所有可歸結的謂詞公式都可以采用線性歸結策略達到加快歸結速度的目的。如果能搞找到一個較好的頂子句，可以式歸結順利進行。否則也可能事與愿違。

C0B0B1BnC1C2空線性歸結策略示意圖線性歸結例子S＝{P∨Q,～P∨Q,P∨～Q,～P∨～Q}

選取頂子句C0＝P∨Q。

線性歸結過程

(1)P∨Q

(2)～P∨Q

(3)P∨～Q

(4)～P∨～Q

(5)Q(1)(2)

(6)P(5)(3)

(7)～Q(6)(4)

(8)□(7)(5)

頂子句的選擇直接影響著歸結的效率。如可選得C0使S－{C0}是可滿足的?？刂撇呗缘姆椒?5) 單元歸結 => 完備

單元歸結策略要求在歸結過程中，每次歸結都有一個子句是單元子句（只含一個文字的子句）或單元因子。顯而易見，詞中方法可以簡單地削去另一個非單子句中的一個因子，使其長度減少，構成簡單化，歸結效率較高。初始子句集中沒有單元子句時，單元歸結策略無效。所以說“反之不成立”，即此問題不能采用單元歸結策略。

單元歸結例子S＝{P∨Q,～P∨R,～Q∨R,～R}

單元歸結過程

(1)P∨Q

(2)～P∨R

(3)～Q∨R

(4)～R

(5)～P(4)(2)

(6)～Q(4)(3)

(7)Q(5)(1)

(8)P(6)(1)

(9)R(7)(3)

(10)□(7)(6)在歸結過程中，對兩子句所做的每一次歸結，其中必須有一個是S的子句時，便稱作輸入歸結。這種歸結也是效率較高的。

單元歸結與輸入歸結是一致的。即有從S到□的輸入歸結的充分必要條件是有從S到□的單元歸結。它們都是不完備的歸結方法?？刂撇呗缘姆椒?6) 輸入歸結 => 完備

與單元歸結策略相似，輸入歸結策略要求在歸結過程中，每一次歸結的兩個子句中必須有一個是S的原始子句。這樣可以避免歸結出的不必要的新子句加入歸結，造成惡性循環(huán)?？梢詼p少不必要的歸結次數(shù)。如同單元歸結策略，不是所有的可歸結謂詞公式的最后結論都是可以從原始子句集中的得到的。簡單的例子，歸結結束時，即最后一個歸結式為空子句的條件是，參加歸結的雙方必須是兩個單元子句。原始子句集中沒有單元子句的謂詞公式一定不能采用輸入歸結策略。

輸入歸結例子S＝{P∨Q,～P∨R,～Q∨R,～R}

輸入歸結過程

(1)P∨Q

(2)～P∨R

(3)～Q∨R

(4)～R

(5)Q∨R(1)(2)

(6)R(3)(5)

(7)□(4)(6)

前兩個例子的子句集是相同的，分別采用了單元歸結和輸入歸結的推理過程。

用歸結反演求取問題的答案（1/4）歸結原理出了可用于定理證明外，還可用來求取問題答案，其思想與定理證明相似。其一般步驟為：(1)把問題的已知條件用謂詞公式表示出來，并化為相應的子句集；(2)把問題的目標的否定用謂詞公式表示出來，并化為子句集；(3)對目標否定子句集中的每個子句，構造該子句的重言式（即把該目標否定子句和此目標否定子句的否定之間再進行析取所得到的子句），用這些重言式代替相應的目標否定子句式，并把這些重言式加入到前提子句集中，得到一個新的子句集；(4)對這個新的子句集，應用歸結原理求出其證明樹，這時證明樹的根子句不為空，稱這個證明樹為修改的證明樹；(5)用修改證明樹的根子句作為回答語句，則答案就在此根子句中。用歸結反演求取問題的答案（2/4）下面再通過一個例子來說明如何求取問題的答案。

例已知：“張和李是同班同學，如果x和y是同班同學，則x的教室也是y的教室，現(xiàn)在張在302教室上課?！眴枺骸艾F(xiàn)在李在哪個教室上課？”解：首先定義謂詞：C(x,y)x和y是同班同學；At(x,u)x在u教室上課。把已知前提用謂詞公式表示如下：C(zhang,li)(?x)(?y)(?u)(C(x,y)∧At(x,u)→At(y,u))At(zhang,302)把目標的否定用謂詞公式表示如下：﹁(?v)At(li,v)用歸結反演求取問題的答案（3/4）把上述公式化為子句集：C(zhang,li)﹁C(x,y)∨﹁At(x,u)∨At(y,u)At(zhang,302)把目標的否定化成子句式，并用重言式﹁At(li,v)∨ANS(v)代替之。把此重言式加入前提子句集中，得到一個新的子句集，對這個新的子句集，應用歸結原理求出其證明樹。其求解過程如下圖所示。該證明樹的根子句就是所求的答案，即“李明在302教室”。用歸結反演求取問題的答案（4/4）﹁At(li,v)∨ANS(v)﹁C(x,y)∨﹁At(x,u)∨At(y,u)ANS(v)

∨﹁

C(x,li)∨﹁At(x,v)C(zhang,li)﹁At(zhang,v)∨ANS(v)At(zhang,302)ANS(302){li/y,v/u}{Zhang/x}{302/v}假設張被盜，公安局派出5個人去調查。案情分析時，偵查員A說：“趙與錢中至少有一個人作案”，偵查員B說：“錢與孫中至少有一個人作案”，偵查員C說：“孫與李中至少有一個人作案”，偵查員D說：“趙與孫中至少有一個人與此案無關”，偵查員E說：“錢與李中至少有一個人與此案無關”。如果這5個偵察員的話都是可信的，使用歸結演繹推理求出誰是盜竊犯。第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理3.4Herbrand定理問題： 一階邏輯公式的永真性（永假性）的判定是否能在有限步內完成？Herbrand定理1936年圖靈(Turing)和邱吉(Church)互相獨立地證明了：“沒有一般的方法使得在有限步內判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內判定它是永真（或永假）。對于非永真（或永假）的公式就不一定能在有限步內得到結論。判定的過程將可能是不停止的?！?/p>

Herbrand定理Herbrand的思想定義： 公式G永真：對于G的所有解釋，G都為真。思想：

尋找一個已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內停止。Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理（H域）基本方法：因為量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數(shù)是無限、不可數(shù)的。簡化討論域。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。此域稱為H域。

D域H域H域與D域關系示意圖H域例題設子句集S={P(x),Q(y,f(z,b)),R(a)}，求H域解：H0＝{a,b}為子句集中出現(xiàn)的常量H1＝{a,b,f(a,b),f(a,a),f(b,a),f(b,b)}H2＝{a,b,f(a,b),f(a,a),f(b,a),f(b,b)，f(a,f(a,b)),f(a,f(a,a)),f(a,f(b,a)),f(a,f(b,b)),f(b,f(a,b)),f(b,f(a,a)),f(b,f(b,a)),f(b,f(b,b)),f(f(a,b),f(a,b)),f(f(a,b),f(a,a)),f(f(a,b),f(b,a)),f(f(a,b),f(b,b)),f(f(a,a),f(a,b)),f(f(a,a),f(a,a)),f(f(a,a),f(b,a)),f(f(a,a),f(b,b)),f(f(b,a),f(a,b)),f(f(b,a),f(a,a)),f(f(b,a),f(b,a)),f(f(b,a),f(b,b)),f(f(b,b),f(a,b)),f(f(b,b),f(a,a)),f(f(b,b),f(b,a)),f(f(b,b),f(b,b))} ……… H∞=H1∪H2∪H3………Herbrand定理（H域）幾個基本概念f（tn）：f為子句集S中的所有函數(shù)變量。t1,t2,…tn為S的H域的元素。通過它們來討論永真性。原子集A：謂詞套上H域的元素組成的集合。如

A={所有形如P(t1,t2,…tn)的元素}

即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數(shù)的，因此，A也是可數(shù)的。原子集例題上例題的原子集為：A={

P(a),Q(a,a),R(a),P(b),Q(b,a), Q(b,b),Q(a,b),R(b),P(f(a,b)),Q(f(a,b),f(a,b)),R(f(a,b),P(f(a,a)),P(f(b,a)),P(f(b,b)),……)一旦原子集內真值確定好（規(guī)定好），則S在H上的真值可確定。成為可數(shù)問題。Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理（H解釋）解釋I：謂