人工智能第三章謂詞邏輯與歸結(jié)原理課件

謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)為了能夠像命題邏輯那樣進(jìn)行歸結(jié)，首先必須解決謂詞邏輯中的量詞問(wèn)題。

前束范式：如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)Skolem標(biāo)準(zhǔn)形 前束范式中消去所有的量詞。Skolem函數(shù)如果某個(gè)存在量詞是在其他任意量詞的轄域內(nèi)，就存在某種依賴關(guān)系，可以用一個(gè)函數(shù)描述這種依賴關(guān)系，叫做Skolem函數(shù)。謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)量詞消去原則：存在量詞。將該量詞約束的變量用任意常量（a，b等）或任意變量的函數(shù)（f(x)，g(y)等）代替。左邊有任意量詞的存在量詞，消去時(shí)該變量改寫(xiě)成為任意量詞的函數(shù)；如沒(méi)有，改寫(xiě)成為常量。任意量詞。簡(jiǎn)單地省略掉該量詞。謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)例:將下式化為Skolem標(biāo)準(zhǔn)形： ～((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)))第二步，～深入到量詞內(nèi)部，得：(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)∧(y)(～Q(y,b)∧～R(x))謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)第四步，變量易名，存在量詞左移，直至所有的量詞移到前面，得：

(x)(y)P(a,x,y)∧(y)(～Q(y,b)∧～R(x))

＝(x)(y)P(a,x,y)∧(z)(～Q(z,b)∧～R(x))

＝(x)(y)(z)(P(a,x,y)∧～Q(z,b)∧～R(x))由此得到前述范式謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)

第五步，消去存在量詞，略去任意量詞 消去(y)，因?yàn)樗筮呏挥?x)，所以使用x的函數(shù)f(x)代替，這樣得到：

(x)(z)(P(a,x,f(x))∧～Q(z,b)∧～R(x))

消去(z)，同理使用g(x)代替，這樣得到：

(x)(P(a,x,f(x))∧～Q(g(x),b)∧～R(x))

略去任意量詞，原式的Skolem標(biāo)準(zhǔn)形為：

P(a,x,f(x))∧～Q(g(x),b)∧～R(x)

謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)Skolem定理： 謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。注意：謂詞公式G的Skolem標(biāo)準(zhǔn)形同G并不等值。

謂詞歸結(jié)子句形子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。空子句：不含任何文字的子句。記作NIL或□子句集：所有子句的集合。對(duì)于任何一個(gè)謂詞公式G，都可以通過(guò)Skolem標(biāo)準(zhǔn)形，建立起一個(gè)子句集與之對(duì)應(yīng)。謂詞歸結(jié)子句形子句集S的求?。簩⒅^詞公式G轉(zhuǎn)換成前束范式；生成Skolem標(biāo)準(zhǔn)形；將各個(gè)子句提出，以“，”取代“Λ”，并表示為集合形式。謂詞歸結(jié)子句形

定理3.1謂詞公式G是不可滿足的，當(dāng)且僅當(dāng)其子句集

S是不可滿足的。G與S不等價(jià)，但在不可滿足的意義下是一致的。

注意：G真不一定S真，而S真必有G真。 即：S=>G謂詞歸結(jié)子句形定理3.1的推廣對(duì)于形如G=G1ΛG2ΛG3Λ…ΛGn

的謂詞公式G的子句集可以分解成幾個(gè)部分單獨(dú)處理。有

SG=S1US2US3U…USn

則SG

與S1US2US3U…USn在不可滿足的意義上是一致的。即SG

不可滿足<=>S1US2US3U…USn不可滿足。可以對(duì)一個(gè)復(fù)雜的謂詞公式分而治之。求取子句集例(1)例：對(duì)所有的x,y,z來(lái)說(shuō)，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個(gè)人都有父親，試問(wèn)對(duì)某個(gè)人來(lái)說(shuō)誰(shuí)是他的祖父？求：用一階邏輯表示這個(gè)問(wèn)題，并建立子句集。解：這里我們首先引入謂詞：

P(x,y)表示y是x的父親

Q(x,y)表示y是x的祖父

ANS(x)表示問(wèn)題的解答求取子句集例(2)對(duì)于第一個(gè)條件，“如果y是x的父親，z又是y的父親，則z是x的祖父”，一階邏輯表達(dá)式如下：

A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對(duì)于第二個(gè)條件：“每個(gè)人都有父親”，一階邏輯表達(dá)式：

A2：(x)(y)P(x,y) SA2：P(x,f(x))對(duì)于結(jié)論：某個(gè)人是他的祖父

B：(x)(y)Q(x,y)

否定后得到子句：～((x)(y)Q(x,y))∨ANS(y) S～B：～Q(x,y)∨ANS(y)則得到的相應(yīng)的子句集為：{SA1，SA2，S～B}置換與合一一階謂詞邏輯得歸結(jié)比命題邏輯的歸結(jié)要復(fù)雜的多，其中一個(gè)原因就是謂詞邏輯公式中含有個(gè)體變量與函數(shù)。如P(x)∨Q(y)與~P(a)∨R(z)所以要考慮置換與合一。即對(duì)變量作適當(dāng)?shù)奶鎿Q。置換置換：可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去置換變量。定義： 置換是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的變量，t1,t2,…,tn是不同于xi的項(xiàng)（常量、變量、函數(shù)）；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，而且xi不能循環(huán)地出現(xiàn)在另一個(gè)ti中。例如：

{a/x，c/y，f(b)/z}是一個(gè)置換。

{g(y)/x，f(x)/y}不是一個(gè)置換。

置換的合成設(shè)＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,un/yn}，是兩個(gè)置換。 則與的合成也是一個(gè)置換，記作·。它是從集合

{t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,un/yn}

中刪去以下兩種元素：當(dāng)ti=xi時(shí)，刪去ti/xi(i=1,2,…,n);

當(dāng)yi{x1,x2,…,xn}時(shí)，刪去uj/yj

(j=1,2,…,m)

最后剩下的元素所構(gòu)成的集合。合成即是對(duì)ti先做置換然后再做置換置換的合成例：設(shè)：＝{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)的結(jié)果；y/y中的y是置換作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件i，需要?jiǎng)h除；a/x，b/y滿足定義中的條件ii，也需要?jiǎng)h除。最后得

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

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

最一般合一（mgu）設(shè)σ是謂詞公式集F的一個(gè)合一，如果對(duì)F的任意一個(gè)合一都存在一個(gè)置換λ，使得θ=σ.λ，則稱σ是一個(gè)最一般合一。最一般合一求取方法令W={F1,F2}令k=0,W0=W,σ0=ε如果Wk已合一，停止，σk=mgu,否則找Dk若Dk中存在元素vk和tk，其中，vk不出現(xiàn)在tk中，轉(zhuǎn)下一步，否則，不可合一。令σk+1=σk.{tk/vk},Wk+1=Wk{tk/vk}=Wσk+1K=k+1轉(zhuǎn)第3步。最一般合一（mgu）例：W={P(a,x,f(g(y))),P(z,f(a),f(u))},其中，F(xiàn)1＝P(a,x,f(g(y)))，F(xiàn)2＝P(z,f(a),f(u))求F1和F2的mgu解：由mgu算法(1)W={P(a,x,f(g(y))),P(z,f(a),f(u))}(2)W0=W,σ0=ε(3)W0未合一，從左到右找差異集，有D0={a,z}(4)取V0=z,t0＝a最一般合一（mgu）(5)令σ1=σ0.{t0/v0}={a/z}W1=W0σ1={P(a,x,f(g(y))),P(a,f(a),f(u))}(3)’W1未合一，找差異集，有D1={x,f(a)}(4)’取v1=x,t1＝f(a)(5)’令σ2=σ1.{t1/v1}={a/z,f(a)/x}W2=W1σ2={P(a,f(a),f(g(y))),P(a,f(a),f(u))}(3)’’W2未合一，找差異集，有D2={g(y),u}(4)’’取v2=u,t2＝g(y)最一般合一（mgu）(5)’’令σ3=σ2.{t2/v2}={a/z,f(a)/x,g(y)/u}W3=W2σ3={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))}(3)’’’W3已合一

σ3={a/z,f(a)/x,g(y)/u}便是F1和F2的mgu。算法的第(4)步，當(dāng)不存在vk或不存在tk或出現(xiàn)差異集為{x,f(x)},都會(huì)導(dǎo)致不可合一。此時(shí)，算法返回失敗。最一般合一（mgu）謂詞邏輯的歸結(jié)方法和命題邏輯基本相同，但在進(jìn)行歸結(jié)之前，應(yīng)采用最一般合一方法對(duì)待歸結(jié)的一對(duì)子句進(jìn)行置換。然后再判斷是否可以進(jìn)行歸結(jié)。歸結(jié)原理歸結(jié)時(shí)的注意事項(xiàng)：謂詞的一致性，P()與Q()，不可以常量的一致性，P(a,…)與P(b,….)，不可以。變量與函數(shù)，P(a,x,….)與P(x,f(x),…)，不可以；不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，P∨Q與～P∨～Q得空，不可以先進(jìn)行內(nèi)部簡(jiǎn)化再進(jìn)行置換與合并。

歸結(jié)原理歸結(jié)的過(guò)程寫(xiě)出謂詞關(guān)系公式→用反演法寫(xiě)出謂詞表達(dá)式→SKOLEM標(biāo)準(zhǔn)形→

求子句集S→對(duì)S中可歸結(jié)的子句做歸結(jié)→歸結(jié)式仍放入S中，反復(fù)歸結(jié)過(guò)程→得到空子句

命題得證。例題“快樂(lè)學(xué)生”問(wèn)題例：假設(shè)任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎(jiǎng)。求證：張是快樂(lè)的。

解：先將問(wèn)題用謂詞表示如下：R1:任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的(x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有考試”

(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))例題“快樂(lè)學(xué)生”問(wèn)題R3:“張不肯學(xué)習(xí)但他是幸運(yùn)的”

～Study(zhang)∧Lucky(zhang)R4:“任何幸運(yùn)的人都能獲獎(jiǎng)”

(x)(Luck(x)→Win(x,prize))結(jié)論：“張是快樂(lè)的”的否定～Happy(zhang)由R1及邏輯轉(zhuǎn)換公式: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)由結(jié)論：(7)～Happy(zhang) （結(jié)論的否定）(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)

第三章謂詞邏輯與歸結(jié)原理概述命題邏輯謂詞邏輯的歸結(jié)法歸結(jié)過(guò)程的控制策略Herbrand定理第三章謂詞邏輯與歸結(jié)原理概述命題邏輯謂詞邏輯的歸結(jié)法歸結(jié)過(guò)程的控制策略Herbrand定理歸結(jié)過(guò)程的控制策略要解決的問(wèn)題：歸結(jié)方法的知識(shí)爆炸?？刂撇呗缘哪康臍w結(jié)點(diǎn)盡量少控制策略的原則給出控制策略，以使僅對(duì)選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)?；蛘哒f(shuō)，少做些歸結(jié)仍能導(dǎo)出空子句。控制策略的方法(1)刪除策略歸類(lèi)：設(shè)有兩個(gè)子句C和D，若有置換使得C

D成立，則稱子句C把子句D歸類(lèi)。若對(duì)S使用歸結(jié)推理過(guò)程中，當(dāng)歸結(jié)式Cj是重言式和Cj被S中子句和子句集的歸結(jié)式Ci(i<j)所歸類(lèi)時(shí)，便將Cj刪除。這樣的推理過(guò)程便稱作使用了刪除策略的歸結(jié)過(guò)程?？刂撇呗缘姆椒?1)刪除策略如P(x)∨～P(x),P(x)∨Q(x)～P(x)P(x)歸類(lèi)P(y)∨Q(z)σ={y/x}純文字刪除。如果某文字L在子句集中不存在可與之互補(bǔ)的文字～L，則稱該文字為純文字。如S={P∨Q∨R,～Q∨R,Q,～R}盡管使用刪除策略的歸結(jié)，少做了歸結(jié)但不影響產(chǎn)生空子句，就是說(shuō)刪除策略的歸結(jié)推理是完備的?？刂撇呗缘姆椒?2)支撐集策略支撐集：設(shè)有不可滿足子句集S的子集T，如果S-T是可滿足的，則T是支撐集。

采用支撐集策略時(shí)，從開(kāi)始到得到空子句的整個(gè)歸結(jié)過(guò)程中，只選取不同時(shí)屬于S-T的子句，在其間進(jìn)行歸結(jié)。就是說(shuō)，至少有一個(gè)子句來(lái)自于支撐集T或由T導(dǎo)出的歸結(jié)式。

控制策略的方法(2)支撐集策略例如：A1ΛA2ΛA3Λ～B中的～B可以作為支撐集使用。要求每一次參加歸結(jié)的親本子句中，至少應(yīng)該有一個(gè)是由目標(biāo)公式的否定（～B）所得到的子句或者它們的后裔。支撐集策略的歸結(jié)是完備的。同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。問(wèn)題是如何尋找合適的支撐集。一個(gè)最容易找到的支撐集是目標(biāo)子句的非，即S～B。

ST可滿足支撐集示意圖控制策略的方法(2)支撐集策略例如：S(1)～I(xiàn)(X)∨R(X)目標(biāo)公式的否定得到的子句(2)I(a)(3)～R(Y)V～L(Y)(4)L(a)S1：(5)R(a)(1)與(2)歸結(jié)(6)～I(xiàn)(x)V～L(x)(1)與(3)歸結(jié)(7)～L(a)(2)與(6)歸結(jié)(8)NIL(4)與(7)歸結(jié)控制策略的方法(3)語(yǔ)義歸結(jié)策略語(yǔ)義歸結(jié)策略是將子句S按照一定的語(yǔ)義分成兩部分，約定每部分內(nèi)的子句間不允許作歸結(jié)。同時(shí)還引入了文字次序，約定歸結(jié)時(shí)其中的一個(gè)子句的被歸結(jié)文字只能是該子句中“最大”的文字。語(yǔ)義歸結(jié)策略的歸結(jié)是完備的。控制策略的方法(4)線性歸結(jié)線性歸結(jié)策略首先從子句集中選取一個(gè)稱作頂子句的子句C0開(kāi)始作歸結(jié)。歸結(jié)過(guò)程中所得到的歸結(jié)式Ci立即同另一子句Bi進(jìn)行歸結(jié)得歸結(jié)式Ci+1。而B(niǎo)i屬于S或是已出現(xiàn)的歸結(jié)式Cj(j<i)。即，如下圖所示歸結(jié)得到的新子句立即參加歸結(jié)。線性歸結(jié)是完備的。C0C1C2C3C4C5空線性歸結(jié)策略示意圖控制策略的方法(5)單元?dú)w結(jié)策略單元?dú)w結(jié)策略要求在歸結(jié)過(guò)程中，每次歸結(jié)都有一個(gè)子句是單元子句（只含一個(gè)文字的子句）或單元因子。顯而易見(jiàn)，此種方法可以簡(jiǎn)單地削去另一個(gè)非單子句中的一個(gè)因子，使其長(zhǎng)度減少，構(gòu)成簡(jiǎn)單化，歸結(jié)效率較高。初始子句集中沒(méi)有單元子句時(shí)，單元?dú)w結(jié)策略無(wú)效。所以說(shuō)“反之不成立”，即此問(wèn)題不能采用單元?dú)w結(jié)策略。控制策略的方法(6)輸入歸結(jié)策略與單元?dú)w結(jié)策略相似，輸入歸結(jié)策略要求在歸結(jié)過(guò)程中，每一次歸結(jié)的兩個(gè)子句中必須有一個(gè)是S的原始子句。這樣可以避免歸結(jié)出的不必要的新子句加入歸結(jié)，造成惡性循環(huán)?？梢詼p少不必要的歸結(jié)次數(shù)。如同單元?dú)w結(jié)策略，不是所有的可歸結(jié)謂詞公式的最后結(jié)論都是可以從原始子句集中的得到的。第三章謂詞邏輯與歸結(jié)原理概述命題邏輯謂詞邏輯的歸結(jié)法歸結(jié)過(guò)程的控制策略Herbrand定理第三章謂詞邏輯與歸結(jié)原理概述命題邏輯謂詞邏輯的歸結(jié)法歸結(jié)過(guò)程的控制策略Herbrand定理Herbrand定理問(wèn)題： 一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？Herbrand定理1936年圖靈(Turing)和邱吉(Church)互相獨(dú)立地證明了：“沒(méi)有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對(duì)于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。判定的過(guò)程將可能是不停止的?！?/p>

Herbrand定理Herbrand的思想定義： 公式G永真：對(duì)于G的所有解釋?zhuān)珿都為真。思想：

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

D域H域H域與D域關(guān)系示意圖H域例題設(shè)子句集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域）幾個(gè)基本概念f（tn）：f為子句集S中的所有函數(shù)變量。t1,t2,…tn為S的H域的元素。通過(guò)它們來(lái)討論永真性。原子集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)),……)

一旦原子集內(nèi)真值確定好（規(guī)定好），則S在H上的真值可確定。成為可數(shù)問(wèn)題。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理Herbrand定理（H解釋?zhuān)┙忉孖：謂詞公式G在論域D上任何一組真值的指定稱為一個(gè)解釋。H解釋?zhuān)鹤泳浼疭在的H域上的解釋稱為H解釋。

問(wèn)題：對(duì)于所有的解釋?zhuān)羌俨趴膳卸?。因?yàn)樗薪忉尨砹怂械那闆r，如可窮舉，問(wèn)題便可解決。Herbrand定理（H解釋?zhuān)┤缦氯齻€(gè)定理保證了歸結(jié)法的正確性：定理1：

設(shè)I是S的論域D上的解釋?zhuān)嬖趯?duì)應(yīng)于I的H解釋I*，使得若有S|I=T，必有

S|I*=T。定理2： 子句集S是不可滿足的，當(dāng)且僅當(dāng)所有的S的H解釋下為假。定理3： 子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。Herbrand定理（H解釋?zhuān)┗齋中某子句中所有變?cè)?hào)均以S的H域中的元素代入時(shí)，所得的基子句C’稱為C的一個(gè)基例。若一個(gè)子句為假，則此解釋為假。一般來(lái)說(shuō)，D是無(wú)窮不可列的，因此，子句集S也是無(wú)窮不可列的。但S確定后H是無(wú)窮可列的。不過(guò)在H上證明S的不可滿足性仍然是不可能的。解決問(wèn)題的方法：語(yǔ)義樹(shù)Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理Herbrand定理（語(yǔ)義樹(shù)）構(gòu)成方法原子集中所有元素逐層添加的一棵二叉樹(shù)。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫(huà)完）。特點(diǎn)一般情況H是無(wú)限可數(shù)集，S的語(yǔ)義樹(shù)是無(wú)限樹(shù)。N0P(a)N12Q(a)P(f(a))N24N31N38無(wú)限語(yǔ)義樹(shù)N11~P(a)~Q(a)Q(a)~Q(a)~P(f(a))N21S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y))}

Herbrand定理（語(yǔ)義樹(shù)）意義SHA語(yǔ)義樹(shù)可以理解語(yǔ)義樹(shù)為H域的圖形解釋。目的：把每個(gè)解釋都攤開(kāi)。語(yǔ)義樹(shù)中包含原子集的全部元素。因此，語(yǔ)義樹(shù)是完全的。每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì)應(yīng)S的一個(gè)解釋?？梢酝ㄟ^(guò)對(duì)語(yǔ)義樹(shù)每一個(gè)分支來(lái)計(jì)算S的真值。如果每個(gè)基例都為假，則可認(rèn)為是不可滿足的。Herbrand定理（語(yǔ)義樹(shù)）幾個(gè)概念失敗結(jié)點(diǎn)： 當(dāng)（由上）延伸到點(diǎn)N時(shí)，I(N)已表明了S的某子句的某基例為假。但N以前尚不能判斷這個(gè)事實(shí)。就稱N為失敗結(jié)點(diǎn)。

封閉語(yǔ)義樹(shù)： 如果S的完全語(yǔ)義樹(shù)的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn)，就稱它是一棵封閉語(yǔ)義樹(shù)。N0P(a)N1,2Q(a)P(f(a))N2,4N3,1N3,8N1,1N4,2N4,1N2,1N3,2N2,2N3,6N4,9N4,10N4,13N4,14封閉語(yǔ)義樹(shù)Q(f(a))S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y))}

Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理Herbrand定理（結(jié)論）Herbrand定理：子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義數(shù)是棵有限封閉樹(shù)。

子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。

Herbrand定理（結(jié)論）定理的意義Herbrand定理已將證明問(wèn)題轉(zhuǎn)化成了命題邏輯問(wèn)題。由此定理保證，可以放心的用機(jī)器來(lái)實(shí)現(xiàn)自動(dòng)推理了。（歸結(jié)原理）注意Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)論。但是

Herbrand定理（結(jié)論）仍存在的問(wèn)題：基例集序列元素的數(shù)目隨子句集的元素?cái)?shù)目成指數(shù)地增加。因此，Herbrand定理是30年代提出的，始終沒(méi)有顯著的成績(jī)。直至1965年Robinson提出了歸結(jié)原理。歸結(jié)原理與Herbrand定理歸結(jié)過(guò)程是語(yǔ)義樹(shù)的倒塌過(guò)程最后歸結(jié)出空，就是剩一個(gè)根節(jié)點(diǎn)，就說(shuō)明語(yǔ)義樹(shù)是有限封閉的，證明結(jié)束。習(xí)題：設(shè)已知：

(1)能閱讀者是識(shí)字的；

(2)海豚不識(shí)字；

(3)有些海豚是很聰明的。試證明：有些聰明者并不能閱讀。證首先，定義如下謂詞：

R(x)：x能閱讀。

L(x)：x識(shí)字。

I(x)：x是聰明的。

D(x)：x是海豚。然后把上述各語(yǔ)句翻譯為謂詞公式：(1)x(R(x)→L(x))(2)x(D(x)→﹁

L(x))已知條件(3)x(D(x)∧I(x))(4)x(I(x)∧﹁R(x))需證結(jié)論

求題設(shè)與結(jié)論否定的子句集，得(1)﹁

R(x)∨L(x)(2)﹁

D(y)∨﹁

L(y)(3)D(a)(4)I(a)(5)﹁

I(z)∨R(z)歸結(jié)得

(6)R(a)(5)，(4)，{a/z}(7)L(a)(6)，(1)，{a/x}(8)﹁

D(a)(7),(2),{a/y}(9)□(8),(3)1.假設(shè)：所有不貧窮且聰明的人都快樂(lè)。那些看書(shū)的人是聰明的。李明能看書(shū)且不貧窮?？鞓?lè)的人過(guò)著激動(dòng)人心的生活。求證：李明過(guò)著激動(dòng)人心的生活給定謂詞：某人x貧窮,Poor(x);某人x聰明,Smart(x);某人x,快樂(lè)happy(x);某人x讀書(shū),Read(x);某人x過(guò)著激動(dòng)人心的生活,Exciting(x)。證明：由前提：所有不貧窮且聰明的人都快樂(lè)(x)(～Poor(x)∧Smart(x)→happy(x))那些看書(shū)的人是聰明的(x)(Read(x)→Smart(x))李明能看書(shū)且不貧窮Read(LM)∧～Poor(LM)快樂(lè)的人過(guò)著激動(dòng)人心的生活(x)(happy(x)→Exciting(x))由結(jié)論的否定～Exciting(LM)子句集：S={Poor(x)∨～Smart(x)∨happy(x),～Read(y)∨Smart(y)，

Read(LM),～Poor(LM)，～happy(z)∨Exciting(z)，～Exciting(LM)}學(xué)科前沿講座人工智能——皇帝的新腦還是人類(lèi)的終結(jié)

一、關(guān)于人工智能

一、關(guān)于人工智能從數(shù)值計(jì)算文字、圖像等多媒體信息處理初步實(shí)現(xiàn)了Leibniz提出的“將人的思維機(jī)器化”的思想讓機(jī)器擁有人的心智——成為計(jì)算機(jī)專(zhuān)家夢(mèng)寐以求的理想！1956年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父)等在美國(guó)達(dá)德茅斯大學(xué)召開(kāi)第一屆人工智能學(xué)術(shù)會(huì)議。 會(huì)上首次使用“人工智能”這一術(shù)語(yǔ)。 標(biāo)志著人工智能學(xué)科的誕生。一、關(guān)于人工智能1950年，W.格雷.瓦爾特，可以自己充