工智能及專家系統(tǒng)敖志剛第4章邏輯的知識表示和推理

工智能及專家系統(tǒng)敖志剛第4章邏輯的知識表示和推理敖志剛

編制第4章邏輯的知識表示和推理

4．1命題與邏輯4．1．1命題與命題定律4．1．2謂詞邏輯4．2謂詞邏輯知識表示4．2．1謂詞邏輯知識表示方法4．2．2謂詞邏輯表示的優(yōu)缺點(diǎn)4．3邏輯推理的技術(shù)與算法4．3．1子句集及其化簡4．3．2置換與合一4．3．3魯濱遜消解(歸結(jié))原理第4章邏輯的知識表示和推理

4．1命題與邏輯

4.1.1

命題與命題定律命題、真命題、假命題、原子命題、不是命題。命題的表示——大寫A、B、C┈┈P、Q、R。2.聯(lián)結(jié)詞（Connectives）

①

否定或補(bǔ)的聯(lián)結(jié)詞用“～”表示②

合取用“∧”表示，③

析取用“∨”表示，④

單條件聯(lián)結(jié)詞用“→”⑤

雙條件聯(lián)結(jié)詞“”聯(lián)結(jié)詞運(yùn)算的先后次序?yàn)椤ⅰ?、∨、→、，同級?lián)結(jié)詞先出現(xiàn)先運(yùn)算3.定義真值指派：設(shè)一個由n個變元P1，P2，…，Pn組成的命題表達(dá)式A，則A的取值由這n個變元唯一確定。把變元的一組取值(T或F)叫做該表達(dá)式的一個真值指派。

真值表：真值表是由命題表達(dá)式所有的真值指派和對應(yīng)的表達(dá)式真值所組成的一張表。永真式永假式等價式：設(shè)P與Q是D上的兩個謂詞公式，若對D上的任意解釋，P與Q都有相同的真值，則稱P與Q在D上是等價的。如果D是任意非空個體域，則稱P與Q是等價的，記作P?Q。

永真蘊(yùn)含式：對謂詞公式P和Q，如果P→Q永真，則稱P永真蘊(yùn)含Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記作P?Q。4.真值表

PQ～PP∧QP∨QP→QPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT5.常用的等價命題定律⑴雙重否定律～～PP⑵交換律

①P∧QQ∧P

②P∨QQ∨P⑶結(jié)合律①（P∧Q）∧RP∧（Q∧R）②（P∨Q）∨RP∨（Q∨R）

5.常用的等價命題定律⑷分配律①P∧（Q∨R）（P∧Q）∨（P∧R）②P∨（Q∧R）（P∨Q）∧（P∨R）③P→（Q→R）（P→Q）→（P→R）⑸狄·摩根定律①～（P∧Q）～P∨～Q②

～（P∨Q）～P∧～Q⑹吸收律①P∧（P∨Q）P②P∨（P∧Q）P⑺聯(lián)結(jié)詞化規(guī)律①P→Q～P∨Q②PQ（P→Q）∧（Q→P）③PQ（P∧Q）∨（～P∧～Q）⑻變換等價式P（P∧Q）∨（P∧～Q）

5.常用的等價命題定律6.永真蘊(yùn)含式常用的永真蘊(yùn)含式如下：

(1)化簡式P∧Q?P，P∧Q?Q(2)附加式P?P∨Q，Q?P∨Q(3)析取三段論~P,P∨Q?Q(4)假言推理P,P→Q?Q(5)拒取式~Q,P→Q?P(6)假言三段論P(yáng)→Q,Q→R?P→R(7)二難推理P∨Q,P→R,Q→R?R(8)全稱固化(?x)P(x)?P(y)其中，y是個體域中任一個體，依此可消去謂詞公式中的全稱量詞

(9)存在固化(?x)P(x)?P(y)其中，y是個體域中某一個可以使P(y)為真的個體，依此可消去謂詞公式中的存在量詞。7.利用命題定律證明等價式邏輯推理的步驟：⑴利用聯(lián)結(jié)詞化規(guī)律化掉→、；⑵利用狄·摩根定律將～深入到變元；⑶利用分配律進(jìn)行變換。

8.示例例4-1試證明：（P∧（P→Q））∨Q（P∧Q）∨（～P∧Q）例4-2證明等價式：（P→Q）∧（R→Q）（P∨R）→Q1．2謂詞邏輯

1.謂詞和個體個體是指可以獨(dú)立存在的事物，如花（桃花，玫瑰，犁花）、計算機(jī)、智能等等。謂詞是用來刻劃個體的性質(zhì)或關(guān)系的。例如張三和李四是工人。通常用大寫英文字母表示謂詞，用小寫英文字母表示個體。如果x的集合為a1，a2，…，an，則STUDENT（an）為真（T）。與一個個體相聯(lián)的謂詞叫一元謂詞，與多個個體相聯(lián)的謂詞叫多元謂詞。一個n元的謂詞?？杀硎緸镻（x1，x2，…，xn），一般來說，在多元謂詞中，個體間的次序不可隨意交換。

2.

量詞

首先來考察兩個謂詞P（x）：x2-1＝（x+1）（x–1）Q（x）：x+3＝１對于ｘ＝-２時為T。1．全稱量詞

通常把“所有”、“一切”、“任一”、“全體”、“凡是”等詞統(tǒng)稱為全稱量詞，記為；符號“”表示對于個體域中所有的個體x，p(x)謂詞均為T。2．存在量詞通常把“存在”、“有些”、“至少有一個”、“有的”等詞統(tǒng)稱為存在量詞，記為；符號“”表示對于個體域中存在某些個體x，Q(x)謂詞均為T。3.量詞的集合表示設(shè)個體域x是有限集合S：

S={a1，a2，…，an}由量詞的意義可知

A(a1)∧A(a2)∧…∧A(an)A(a1)∨A(a2)∨…∨A(an)4.量詞之間的關(guān)系對于二元謂詞P(x,y)，存在以下量化的可能：一般來講，量詞的先后次序不可交換。例如，x和y的個體域都是所有鞋子的集合，P(x,y)表示一只鞋子x可與另一只鞋子y配對，則表示“存在一只鞋子x，它可以與任何一只鞋子y配對”,這是不可能的，是個假命題。而表示“對任何一只鞋子y，總存在一些鞋子x可以與它配對”，這是真命題。3.含有量詞的等價式⑴量詞的轉(zhuǎn)換律①②⑵量詞的分配律①②③④3.含有量詞的等價式⑶量詞轄域擴(kuò)張及收縮律①②③④3.含有量詞的等價式⑷其他等價式①②③④⑤⑸量詞消去規(guī)則①②4.定理證明～(A(a1)∧A(a2)∧…∧A(an))

～A(a1)∨～A(a2)∨～A(an)(A(a1)∧B(a1))∧(A(a2)∧B(a2))∧…∧(A(an)∧B(an))(A(a1)∧A(a2)∧…∧A(an))∧(B(a1)∧B(a2)∧…∧B(an))5.謂詞表達(dá)式的范式⑴前束范式若有一謂詞表達(dá)式W，它的所有量詞均非否定地出現(xiàn)在表達(dá)式的前面，而它們的轄域?yàn)檎麄€表達(dá)式，則稱W為前束范式。前束范式的一般形式為：

例如就是一個前束范式。⑵Skolem范式在前束范式中，如果所有的存在量詞都出現(xiàn)在全稱量詞之前，則稱這種形式的范式表達(dá)式為Skolem范式。例如4．2謂詞邏輯知識表示

4．2．1謂詞邏輯知識表示方法

1.用謂詞邏輯表示簡單事實(shí)

RAINING；SUNNY；MAN（zhangsan）；INROOM（robot，room1）；MARRIED（father（lisi），mather（lisi））。2.聯(lián)結(jié)詞和量詞的應(yīng)用1、～I(xiàn)NROOM（robot，room2）；2．LIKE（i，music）∧LIKE（i，painting）；

LIVE(lisi,house1)∧COLOR(house1,yellow)；3．PLAY(lihao,basketball)∨PLAY(lihao,football)；4．OWNS(heming,book-1)→COLOR(book-1,blue);5．GRASP(i，you)GRASP(you，i)；6．COLOR(x,gray)〕;7.()INROOM(x，room-1)

3.謂詞邏輯的一般表示方法例4-4用謂詞邏輯表示“所有的整數(shù)不是偶數(shù)就是奇數(shù)”。定義謂詞:INTEGER(x):表示x是整數(shù)；EVEN(x):表示x是偶數(shù)；ODD(x):表示是奇數(shù)。該知識表示為:()(INTEGER(x)→EVEN(x)∨ODD(x))3.謂詞邏輯的一般表示方法例4-5用謂詞邏輯表示如下知識:“王宏是計算機(jī)系的一名學(xué)生”；“李明是王宏的同班同學(xué)”；“凡是計算機(jī)系的學(xué)生都喜歡編程序”。①首先定義謂詞:COMPUTER(x):表示x是計算機(jī)系的學(xué)生；CLASSMATE(x，y):表示x是y的同班同學(xué)；LIKE(x，y):表示x喜歡y。②用謂詞公式表示上述知識:COMPUTER(wanghong)；CLASSMATE(liming，wanghong)；()(COMPUTER(x)→LIKE(x，programing))。4.用謂詞邏輯表示狀態(tài)例4-6積木狀態(tài)問題：假如給定積木世界的一個狀態(tài)，桌子(Table)上放有三塊積木A、B和C，且B在A上，C放在A、B的左邊，如圖4-1所示。用謂詞邏輯給予描述這一積木世界問題的狀態(tài)。①先定義幾個謂詞:ON(x，y)：x在y上；

ONTABLE（x)：x在桌子上；

CLEAR（x)：x頂上是空的;RIGHT(x，y)：x在y的右邊。x，y的個體域都是A、B、CTableCAB圖4-1積木世界的一個狀態(tài)4.用謂詞邏輯表示狀態(tài)這個積木世界的狀態(tài)可以表示成:ON(B，A)；RIGHT(B，C)；RIGHT(AC)；ONTABLE(A)；ONTABLE(C)；CLEAR(C)；CLEAR(B)。顯然有以下關(guān)系：

()(CLEAR(x)～()ON(y，x))TableCAB圖4-1積木世界的一個狀態(tài)4.用謂詞邏輯表示狀態(tài)例4-6機(jī)器人移盒子問題：在一個包含有凹室(Alcove)的房間內(nèi)有兩張桌子A和B，一個機(jī)器人(Robot)和一個盒子(Box)，如圖4-2所示。我們的任務(wù)是讓機(jī)器人從凹室出發(fā)，把桌子A上的盒子移到桌子B上，然后回到凹室。試用謂詞邏輯描述這一行動過程。圖4-2機(jī)器人移盒子初始狀態(tài)Robot首先定義以下幾個謂詞:①TABLE(x)：X是桌子；②EMPTYHANDED(y)：y手中是空的；③AT(y，z)：y在z的附近；④HOLDS(y，w)：y手中拿著w；⑤ON(w，x)：w在x桌面上。其中x，y，z，w個體域分別是{a，b}，{robot}，{a，b，alcove}，{box}。

圖4-2機(jī)器人移盒子初始狀態(tài)Robotabalcove

box4.用謂詞邏輯表示狀態(tài)例4-6機(jī)器人移盒子問題：在一個包含有凹室(Alcove)的房間內(nèi)有兩張桌子A和B，一個機(jī)器人(Robot)和一個盒子(Box)，如圖4-2所示。我們的任務(wù)是讓機(jī)器人從凹室出發(fā)，把桌子A上的盒子移到桌子B上，然后回到凹室。試用謂詞邏輯描述這一行動過程。圖4-2機(jī)器人移盒子初始狀態(tài)Robot首先定義以下幾個謂詞:①TABLE(x)：X是桌子；②EMPTYHANDED(y)：y手中是空的；③AT(y，z)：y在z的附近；④HOLDS(y，w)：y手中拿著w；⑤ON(w，x)：w在x桌面上。其中x，y，z，w個體域分別是{a，b}，{robot}，{a，b，alcove}，{box}。

圖4-2機(jī)器人移盒子初始狀態(tài)Robotabalcove

box機(jī)器人問題的初始狀態(tài)和目標(biāo)狀態(tài)問題的初始狀態(tài)是下列問題的合取:AT(robot，alcove)EMPTYHANDED(robot)

ON(box，a)TABLE(a)TABLE(b)

問題的目標(biāo)狀態(tài)是下列問題的合取:AT(robot，alcove)EMPTYHANDED(robot)

ON(box，b)TABLE(a)TABLE(b)機(jī)器人的操作有三類①GOTO（x，y）：機(jī)器人從x處走到y(tǒng)處。條件：AT(robot，x)；動作:刪除:AT(robot，x)；添加:AT(robot，y)。②PICKUPBOX(x):機(jī)器人在x處拿起盒子。條件:ON(box，x)，TABLE(x)，AT(robot，x)，EMPTYHANDED(robot)；動作:刪除:EMPTYHANDED(robot)，ON(box，x)；添加:HOLDS(robot，box)。③SETDOWN(x):機(jī)器人在x處放下盒子。條件:AT(robot，x),TABLE(x)，HOLDS(robot，box)；動作:刪除:HOLDS(robot，box)；添加:EMPTYHANDED(robot)，ON(box，x)。機(jī)器人行動規(guī)劃問題的求解過程

狀態(tài)1：AT(robot，alcove),EMPTYHANDED(robot),ON(box，a),TABLE(a),TABLE(b)狀態(tài)2：AT(robot，a)，EMPTYHANDED(robot)，ON(box，a),TABLE(a),TABLE(b)狀態(tài)3：AT(robot，a)，HOLDS(robot，box)，TABLE(a)，TABLE(b)狀態(tài)4：AT(robot，b)，HOLDS(robot，box)，TABLE(a)，TABLE(b)狀態(tài)5：AT(robot，b),EMPTYHANDED(robot),ON(box，b),TABLE(a),TABLE(b)狀態(tài)6：AT(robot，alcove),EMPTYHANDED(robot),ON(box，b),TABLE(a),TABLE(b)圖4-3機(jī)器人行動規(guī)劃問題的求解過程目標(biāo)狀態(tài)初始狀態(tài)GOTO(x，y)用alcove代換x，a代換y用a代換xPICKUPBOX(x)用a代換x，b代換yGOTO(x，y)用b代換xSETDOWN(x)用b代換x，GOTO(x，y)alcove代換y5.邏輯表示與推理例4-7已知下面事實(shí)：試問馬科斯還活著嗎？⑴馬科斯是男人；⑵馬科斯是龐貝人；⑶馬科斯出生于公元40年；⑷所有的人都會死；⑸所有龐貝人都死于公元79年的火山爆發(fā)；⑹公元79年的火山爆發(fā)；⑺所有會死的人數(shù)不會超過150歲；⑻現(xiàn)在是2002年⑼活意即未死；⑽如果某人死了，那么他后來的任何時刻都死了。馬科斯問題的邏輯表示⑴MAN(marcus)；⑵POMPEIAN(marcus)；⑶BORN(marcus，40)；⑷()[MAN(x)→MORTAL(x))；⑸ERUPTED(volcano，79)∧()[POMPEIAN(x)→DIED(x，79)]；⑹ERUPTED(volcano，79)；⑺[MORTAL(x)∧BORN(x,t1)∧GT(T2-t1,150)→DEAD(x,t2)]⑻N(yùn)OW=2011；⑼ALIVE(x，t)～DEAD(x,t)；⑽[DEAD(x,t1)∧GT(t2，t1)→DEAD(x,t2)]馬科斯問題的證明過程

圖4-4證明馬科斯已死的過程～ALIVE(marcus，now)用9代換DEAD(marcus，now)用10代換DEAD(marcus,t1)∧GT(now，t1)用5代換ERUPTED(volcano，79)∧POMPEIAN(marcus)∧GT(now，79)用6、2代換GT(now，79)用8代換GT(2011，79)計算GTnil4．3邏輯推理的技術(shù)與算法

4．3．1子句集及其化簡1.子句與子句集定義1：不含有任何聯(lián)接詞以及量詞的謂詞稱為原子謂詞。定義2：文字是原子謂詞及其否定形式的統(tǒng)稱。例如：P(x)、～P(x)、Q(x，y)、～Q(x，y)等都是文字。定義3：若P是原子謂詞，則稱P與～P為互補(bǔ)文字。定義4：若干個文字的一個析取式稱為一個子句，例如：P(x)∨(～Q(x))；P(x，f(x))∨Q(x，g(x))都是子句。定義5：由r個文字組成的子句叫r-文字子句。定義6：1-文字子句叫單元子句。定義7：不含任何文字的子句叫空子句，記為□或NIL，空子句是永假的，不可滿足的。定義8：所謂子句集是由子句或空子句構(gòu)成的一種集合。2.子句集的化簡⑴消去聯(lián)結(jié)詞“→”、“”。⑵縮小否定詞～的使用范圍。⑶變元適當(dāng)改名(標(biāo)準(zhǔn)化)。使量詞間不含同名指導(dǎo)變元和約束變元。⑷化為前束范式。⑸消去存在量詞。。①若存在量詞左邊沒有全稱量詞，只要用新的個體常量替換該存在量詞約束的變元，同時消去該存在量詞。②若存在量詞位于一個或多個全稱量詞的轄域內(nèi)(存在量詞在右邊)，則用這些全稱量詞指導(dǎo)變元的一個函數(shù)代替該存在量詞轄域中的相應(yīng)約束變元。⑹化為Skolem標(biāo)準(zhǔn)形。⑺消去所有全稱量詞。⑻消去合取詞，把母式用子句集的形式表示出來。⑼更換變元名稱，使子句間無同名變元。2.子句集的化簡（1/6）

在謂詞邏輯中，任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集。其化簡步驟如下：

(1)消去連接詞“→”和“?”反復(fù)使用如下等價公式：

P→Q?～P∨QP?Q?(P∧Q)∨(～P∧～Q)即可消去謂詞公式中的連接詞“→”和“?”。例如公式

(?x)((?y)P(x,y)→～(?y)(Q(x,y)→R(x,y)))經(jīng)等價變化后為

(?x)(～(?y)P(x,y)∨～(?y)(～Q(x,y)∨R(x,y)))(2)減少否定符號的轄域反復(fù)使用雙重否定率～(～P)?P摩根定律～(P∧Q)?～P∨～Q

～(P∨Q)?～P∧～Q量詞轉(zhuǎn)換率～(?x)P(x)?(?x)～P(x)

～(?x)P(x)?(?x)￢P(x)將每個否定符號“～”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。例如，上式經(jīng)等價變換后為

(?x)((?y)～P(x，y)∨(?y)(Q(x，y)∧～R(x，y)))2.子句集的化簡（2/6）

(3)對變元標(biāo)準(zhǔn)化在一個量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。例如，上式經(jīng)變換后為

(?x)((?y)～P(x，y)∨(?z)(Q(x，z)∧～R(x，z)))(4)化為前束范式化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。由于第(3)步已對變元進(jìn)行了標(biāo)準(zhǔn)化，每個量詞都有自己的變元，這就消除了任何由變元引起沖突的可能，因此這種移動是可行的。例如，上式化為前束范式后為

(?x)(?y)(?z)(～P(x，y)∨(Q(x，z)∧～R(x，z)))2.子句集的化簡（3/6）

(5)消去存在量詞消去存在量詞時，需要區(qū)分以下兩種情況：

若存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞），只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。

若存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如

(?x1)…(?xn)(?y)P(x1，x2,…,xn,y)則需要用Skolem函數(shù)f(x1，x2,…,xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。例如，上步所得公式中存在量詞(?y)和(?z)都位于(?x)的轄域內(nèi)，因此都需要用Skolem函數(shù)來替換。設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為

(?x)(～P(x,f(x))∨(Q(x,g(x))∧～R(x,g(x))))2.子句集的化簡（4/6）

(6)化為Skolem標(biāo)準(zhǔn)形

Skolem標(biāo)準(zhǔn)形的一般形式為

(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標(biāo)準(zhǔn)形的母式，它由子句的合取所構(gòu)成。把謂詞公式化為Skolem標(biāo)準(zhǔn)形需要使用以下等價關(guān)系

P∨(Q∧R)?(P∨Q)∧(P∨R)例如，前面的公式化為Skolem標(biāo)準(zhǔn)形后為

(?x)((～P(x,f(x))∨Q(x,g(x))∧(～P(x,f(x))∨～R(x,g(x))))(7)消去全稱量詞由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變元是被全稱量詞量化的。例如，上式消去全稱量詞后為

(～P(x,f(x))∨Q(x,g(x))∧(～P(x,f(x))∨～R(x,g(x)))2.子句集的化簡（5/6）

(8)消去合取詞在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。例如，上式的子句集中包含以下兩個子句～P(x,f(x))∨Q(x,g(x))

～P(x,f(x))∨～R(x,g(x))(9)更換變量名稱對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相同的變量名。由于每一個子句都對應(yīng)著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實(shí)際上不存在任何關(guān)系。這樣，更換變量名是不會影響公式的真值的。例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集～P(x,f(x))∨Q(x,g(x))

～P(y,f(y))∨～R(y,g(y))2.子句集的化簡（6/6）將邏輯表達(dá)式化成子句集例4-8求下列謂詞表達(dá)式的子句集。解：利用上述步驟，按以下步驟進(jìn)行求解：⑴消去：⑵否定深入：⑶變元改名：⑷化為前束范式：⑸消去存在量詞：將邏輯表達(dá)式化成子句集⑹化為Skolem標(biāo)準(zhǔn)形：⑺消去全稱量詞：⑻消去合取詞：⑼更換變元名稱：4．3．2置換與合一

1.置換置換是在一個謂詞表達(dá)式中用置換項(xiàng)去替換變量，其一般形式為有限集合{t1/x1，t2/x2，…，tn/xn}。其中xi是變量，ti是不同于xi的項(xiàng)，可以是常量、函數(shù)，或者其他的變量。xi≠xj(i≠j│i，j∈1，2，…，n)，ti/xi表示用ti替換xi，xi不能循環(huán)地出現(xiàn)在另一個ti中。例如{a/x，b/y，f(c)/z}是一個置換，而{g(y)/x，f(x)/y}就不是一個置換，原因是它在x和y之間出現(xiàn)了循環(huán)置換現(xiàn)象。通常置換用希臘字母θ、σ、α、λ表示。置換的例示在謂詞表達(dá)式W=P[x，f(y)，B]中，若用置換θ={t1/x1，t2/x2，…，tn/xn}，把W中所有的xi全部換成ti(i=1，2，…，n)，記為Wθ，所得結(jié)果稱為W在置換θ下的例示。表4-4四種不同的例示序號置換置換的例示①θ1=｛z/x，w/y｝Wθ1=P[x，f(y)，B]θ1=P[z，f(w)，B]②θ2=｛A/y｝Wθ2=P[x，f(y)，B]θ2=P[x，f(A)，B]③θ3=｛g(z)/x，A/y｝Wθ3=P[x，f(y)，B]θ3=P[g(z)，f(A)，B]④θ4=｛c/x，A/y｝Wθ4=P[x，f(y)，B]θ4=P[c，f(A)，B]復(fù)合置換若有兩個置換θ={t1/x1，t2/x2，…，tn/xn}，λ={u1/y1，u2/y2，…，um/ym}。①當(dāng)tiλ=xi時，刪去tiλ/xi(i=1，2，…，n)；②當(dāng)yi∈{x1，x2，…，xn}時，刪去uj/yj(i=1，2，…，m)；稱集合{t1λ/x1，t2λ/x2，…，tnλ/xn，u1/y1，u2/y2，…，um/ym}最后所剩下的元素為置換θ與λ的復(fù)合置換，記為θ?λ。復(fù)合置換舉例例4-9設(shè)θ={f(y)/x，z/y}，λ={a/x，b/y，y/z}，求θ?λ。解：∵θ?λ={t1λ/x1，t2λ/x2，u1/y1，u2/y2，…，u3/y3}={f(b/y)/x，(y/z)/y，a/x，b/y，y/z}={f(b)/x，y/y，a/x，b/y，y/z}其中y/y滿足條件①，a/x、b/y滿足條件②給予刪除。從而得到：θ?λ={f(b)/x，y/z}一般情況下復(fù)合置換是不可交換的，即θ?λ≠λ?θ。2.合一合一是通過對項(xiàng)進(jìn)行置換，使兩個謂詞表達(dá)式達(dá)到一致的過程，通過合一，可把若干表達(dá)式合為一個表達(dá)式。合一的一般定義為：設(shè)W={W1，W2，…，Wn}，若存在一個置換θ，可使W1θ=W2θ=…=Wnθ，則稱θ是W的一個合一，稱W是可以合一的。一般一個表達(dá)式集的合一不唯一。若σ是表達(dá)式集W的一個合一，如果對W的任意一個合一θ，都存在一個置換λ，使得θ=σ?λ，則稱σ為W的最一般合一。一個表達(dá)式集的最一般合一是唯一的。例如

W={P(u，y，g(y))，p(x，f(u)，z)}有一個最一般合一：σ={u/x，f(u)/y，g(f(u))/z}；例如θ={a/x，f(a)/y，g(f(a))/z，a/u}，存在一個置換：λ={a/u}，使得θ=σ?λ。4．3．3魯濱遜消解(歸結(jié))原理1.命題邏輯的消解原理命題邏輯的消解原理因?yàn)镻→Q，Q→RP→R，即(～P∨Q)∧(～Q∨R)(～P∨R)，也就是說由C1∨L和～L∨C2可以推出C1∨C2來?；舅枷胱⒁庖韵聝蓚€關(guān)鍵第一，子句集中的子句之間是合取關(guān)系。因此，子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的；第二，空子句是不可滿足的。因此，一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。魯濱遜歸結(jié)原理基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴(kuò)充的子句集S'。然后設(shè)法檢驗(yàn)子句集S'是否含有空子句，若含有空子句，則表明S'是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進(jìn)行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。魯濱遜歸結(jié)原理包括命題邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理定義設(shè)C1、C2是命題邏輯中的任意兩個子句，如果C1中文字L1與C2中文字L2互補(bǔ)，那么可以從C1和C2中分別消去L1和L2，并將余下的兩個子句析取構(gòu)成一個新的子句C12，則稱這一過程為消解(歸結(jié))，稱C1和C2為C12的親本子句，稱C12為C1和C2的消解式。即：C12=(C1-{L1})∨(C2-{L2})。若C1=P∨R，C2=～P∨Q，則C12=R∨Q；若C1=～P∨Q∨R，C2=～Q∨S，則C12=～P∨R∨S；若C1=P∨Q，C2=P∨R，則C12

不存在；若C1=～P∨Q，C2=～Q，C3=P，則C12=～P，C123=NIL(□)；定理和推論定理消解式C12是其親本子句C1和C2的邏輯結(jié)論。推論如果C1和C2是子句集S的兩個子句，C12為C1和C2的消解式，則①若用C12代替C1和C2，所得的新子句集S1保持著原子句集S的不可滿足性。即：

S1不可滿足S不可滿足②若把C12加入S中得到新的子句集S2，則S與S2的不可滿足性是等價的。即：

S2不可滿足S不可滿足消解舉例例4-10證明S={P∨Q,～P∨Q，P∨～Q，～P∨～Q}是不可滿足的子句集。證明①P∨Q②～P∨Q③

P∨～Q④～P∨～Q⑤Q(由①，②式)⑥～Q(由③，④式)⑦□(由⑤，⑥式)所以S是不可滿足的

QP∨Q～P∨QP∨～Q～P∨～Q圖4-5消解演繹樹～Q□消解過程已知子句集E，證明G為真的過程如下：①否定結(jié)論G為～G；②把～G并入到E中，得到{E，～G}；③把{E，～G}化為子句集S；④對S中的子句進(jìn)行消解，并把每次得到的消解式并入S中，力圖推導(dǎo)出一個表示矛盾的空子句NIL。如此反復(fù)進(jìn)行，若出現(xiàn)空子句，則停止消解，這樣就證明了G為真。求證結(jié)論為真示例例4-11若已知子句集為{P，(P∧Q)→R，T→Q，T}，求證結(jié)論為R。證明：否定結(jié)論R為～R，將～R加入子句集，并化為新子句集：S={P，～P∨～Q∨R，～T∨Q，T，～R}出現(xiàn)空子句，因此命題R得證。～R～P∨～Q∨R□～P∨～Q～Q～T圖4-6消解反演樹P～T∨QT2.謂詞邏輯中的消解謂詞邏輯子句集中的謂詞一般都含有變元，因而需要先用一個最一般合一對變元進(jìn)行替換，然后才能進(jìn)行消解。定義設(shè)C1和C2是兩個沒有公共變元的子句，L1、L2

分別是C1、C2中的兩個文字，如果L1和～L2存在一個最一般合一σ，則稱

C12=(C1σ—{L1σ})∪(C2σ—{L2σ})為C1和C2的二元消解式，而L1和L2為消解式上的文字。二元消解式舉例例4-12設(shè)C1=P(x)∨Q(x)，C2=～P(a)∨R(x)，求C12。選L1=P(x)，L2=～P(a)，可得L1、L2的最一般合一為：σ={a/x}。從而C12=(C1σ—{L1σ})∪(C2σ—{L2σ})=({P(a),Q(a)}—{P(a)})∪({～P(a),R(y)}—{～P(a)}={Q(a)}∪{R(y)}=Q(a)∨R(y)

二元消解式的幾種情況定義若C1和C2是無公共變元的子句，C1、C2的消解式C12是下列二元消解式之一。C1和C2的二元消解式；C1和C2的因子C2σ的二元消解式；C1的因子C1σ和C2的二元消解式；C1的因子C1σ和C2的因子C2σ的二元消解式。定理與舉例定理謂詞邏輯中的消解式C12是其親本子句C1和C2的邏輯結(jié)論。例4-13如果有C1=P(x)∨P(f(y))∨R(g(y))，C2=～P(f(g(a)))∨Q(b)，求C12。解：對C1取最一般合一σ={f(y)/x}，得C1的因子C1σ=P(f(y))∨R(g(y))；P(f(y))和～P(f(g(a)))的最一般合一是θ={g(a)/y}，所以得到C1和C2的二元消解式：C12=R(g(g(a)))∨Q(b)證明邏輯結(jié)論成立舉例例4-14求證G是F1和F2的邏輯結(jié)論。

F1：(x)(P(x)→(x)(Q(y)→～L(x，y)))F2：(x)(P(x)∧(y)(R(y)→L(x，y)))

G：(x)(R(x)→～Q(x))證明：首先將F1、F2和～G化成Skolem范式，利用量詞消去規(guī)則，并改名得：①～P(x)∨～Q(y)∨～L(x，y)(由F1)②P(a)③～R(z)∨L(a，z)④R(b)⑤Q(b)⑥L(a，b)(由③，④式，取σ1={b/z})⑦～Q(y)∨～L(a，y)(由①，②式，取σ2={a/x})⑧～Q(b)(由⑥，⑦式，取σ3={b/y})⑨□(由⑤，⑧式)因此,G是F1和F2的邏輯結(jié)論。(由F2)(～G)經(jīng)典的消解問題1例4-14“快樂學(xué)生”問題?，F(xiàn)假設(shè)：任何通過計算機(jī)考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運(yùn)的人都可通過所有考試，張三不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎。試證明張三是快樂的。解：先定義謂詞：①PASS(x,y)：x可以通過y考試；②WIN(x,award)：x能獲得獎勵；③STUDY(x)：x肯學(xué)習(xí)；④ENJOYMENT(x)：x是快樂的；⑤LUCKY(x)：x是幸運(yùn)的。經(jīng)典的消解問題1⑴任何通過計算機(jī)考試并獲獎的人都是快樂的；(x)((PASS(x，computer)∧WIN(x，award))→ENJOYMENT(x))⑵任何肯學(xué)習(xí)或幸運(yùn)的人都可通過