人工智能-推理技術(shù)-課件

人工智能ArtificialIntelligence(AI)1ppt課件第4章推理技術(shù)

4.1消解原理2ppt課件推理是如何進(jìn)行的？推理過(guò)程多種多樣例1：如果今天不下雨，我就去你家今天沒(méi)有下雨例2：小王說(shuō)他下午或者去圖書(shū)館或者在家休息小王沒(méi)去圖書(shū)館計(jì)算機(jī)如何選擇？3ppt課件

消解原理（歸結(jié)原理）魯濱遜美國(guó)數(shù)學(xué)家魯濱遜

提出消解原理（1965年） 基本的出發(fā)點(diǎn)：要證明一個(gè)命題為真都可以通過(guò)證明其否命題為假來(lái)得到 將多樣的推理規(guī)則簡(jiǎn)化為一個(gè)—消解4ppt課件什么叫消解PQ﹁PRQR消解式親本子句消解式是親本子句的邏輯結(jié)論消解只能在僅含否定和析取聯(lián)接詞的公式（子句）間進(jìn)行必須先把公式化成規(guī)范的形式（范式，子句集）析取聯(lián)接詞，類似“或”5ppt課件什么叫消解例1：小王說(shuō)他下午或者去圖書(shū)館或者在家休息小王沒(méi)去圖書(shū)館R—小王下午去圖書(shū)館S—小王下午在家休息RS﹁RS例2：如果今天不下雨，我就去你家﹁

P→Q今天沒(méi)有下雨 ﹁

PPQ6ppt課件含變量的消解例：蘇格拉底論斷凡人都會(huì)死. x(Man

(x)Mortal(x))蘇格拉底是人. Man

(Socrates)如何得到結(jié)論：蘇格拉底會(huì)死. Mortal(Socrates)要完成消解還面臨幾個(gè)問(wèn)題“”和“”必須消去Man

(x)Mortal(x)Man

(x)

Mortal“”怎么辦？化為子句集置換與合一如果能消去“”，Man

(x)

和Man

(Socrates)也不能構(gòu)成互補(bǔ)對(duì)，形式不一樣，怎么辦？7ppt課件相關(guān)概念文字：原子公式及其否定統(tǒng)稱為文字子句集(1)子句定義 任何文字的析取式稱為子句 不包含任何文字的子句稱為空子句（空子句是永假的） 由子句構(gòu)成的集合稱為子句集例：{P（x）∨Q(x),~P（x，f(x)）∨Q(x,g(x))}化子句集8ppt課件(2)謂詞演算公式化為子句式任何一個(gè)謂詞演算公式可以化為一個(gè)子句集合步驟：

1)消去蘊(yùn)涵符號(hào)用~A∨B代換A→B2)把非號(hào)~移入內(nèi)層P~x)

(=

x)P(~P~x)

(=

x)P(~Q~P~

Q)(P~Q~P~

Q)(P~"$$"ù=úú=ù9ppt課件3)對(duì)變量標(biāo)準(zhǔn)化改變變量名，使不同的變量不同名4)消去存在量詞(具體化Skolemnizing)，兩種情況：存在量詞不在全稱量詞的轄域內(nèi)——用新的個(gè)體常量替換受存在量詞約束的變?cè)嬖诹吭~在全稱量詞的轄域內(nèi)

Skolem函數(shù)，即具體化函數(shù)x)Q(x)(

x)P(x)($ú"y)Q(y)(

x)P(x)($ú")a(Q)x(P)x(ú"T)y(Q)y()x(P)x($ú")y,x,...,x,x(P)y)(x)...(x)(x(n21n21$""")x,...,x,x(f,x,...,x,x(P)x)...(x)(x()n21n21n21"""T)x,...,x,x(f,x,...,x,x(P)x)...(x)(x()n21n21n21"""T10ppt課件x

yzuvwA(x,y,z,u,v,w)(用a替代x，刪除x)=yzu

vwA(a,y,z,u,v,w)（用f(y,z)代替u，刪除u）=yzvwA(a,y,z,f(y,z),v,w)

（用h(y,z,v)代替w，刪除w）

=yzvA(a,y,z,f(y,z),v,h(y,z,v))例：求Skolem函數(shù)(斯柯倫范式)11ppt課件5)化為前束形式把全稱量詞提到最外層前束形:=(前綴){母式} ↑↑

全稱量詞串無(wú)量詞公式6)把母式化為合取范式7)消去全稱量詞8)消去連詞符號(hào)∧，寫(xiě)成子句集9)變量分離標(biāo)準(zhǔn)化 改變變量名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中12ppt課件(x)A(x)

(x)B(x)=～(x)A(x)∨(x)B(x)（消去“蘊(yùn)含”）=(x)(～A(x))∨(x)B(x)（“非”直接作用謂詞符號(hào)）=(

x)(～A(x))∨(z)B(z)(改名)=～A(a)∨B(b)（消去存在量詞）子句集={～A(a)∨B(b)}例1：仔細(xì)分析量詞的轄域13ppt課件(x)(y)((z)(A(x,z)∧A(y,z))(u)B(x,y,u))=(x)(y)(～((z)(A(x,z)∧A(y,z)))∨(u)B(x,y,u))=(x)(y)((z)(～A(x,z)∨～A(y,z))∨(u)B(x,y,u))=(x)(y)((z)(～A(x,z)∨～A(y,z))∨B(x,y,f(x,y))=(x)(y)(z)(～A(x,z)∨～A(y,z)∨B(x,y,f(x,y)))子句例2：14ppt課件((x)P(x)∨(y)Q(y))

(x)R(x)=～((x)P(x)∨(y)Q(y))∨(x)R(x)=(～(x)P(x)∧～(y)Q(y))∨(x)R(x)=((x)(～P(x))∧(y)(～Q(y)))∨(x)R(x)=((x)(～P(x))∧(y)(～Q(y)))∨(z)R(z)(改名)例3：15ppt課件＝((～P(a))∧(y)(～Q(y)))∨(z)R(z)（消去存在量詞）＝(y)(z)((～P(a)∧～Q(y))∨R(z))（化成前束范式）＝

(y)(z)((～P(a)∨R(z))∧(～Q(y)∨R(z)))(化成前束合取范式)子句集={～P(a)∨R(z)

,～Q(y)∨R(x)

}=((x)(～P(x))∧(y)(～Q(y)))∨(z)R(z)16ppt課件例4：將謂詞公式化成子句集①消去“蘊(yùn)含”符號(hào)17ppt課件②“非”直接作用到謂詞符號(hào)18ppt課件③約束變量改名后面的y改成w19ppt課件④引入斯科倫函數(shù)消去存在量詞斯科倫函數(shù)

w=g(x)20ppt課件⑤化成前束范式21ppt課件⑥化成前束合取范式分配律：P∨(Q∧R)=(P∨Q)∧(P∨R)注：使用分配律兩次22ppt課件⑦消去全稱量詞或者前束23ppt課件⑧消去合取符號(hào)，得到子句24ppt課件⑨變量改名，使得變量不相同，得到子句集25ppt課件消解式的定義命題邏輯的消解式設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱這一過(guò)程為消解，稱C12為C1和C2的消解式，C1，C2為C12的親本子句例：子句C1=P∨C1'C2=~P∨C2' 消解式C12=C1'∨C2'一階謂詞邏輯的消解式設(shè)C1與C2是兩個(gè)沒(méi)有相同變?cè)淖泳洌琇1和L2分別是C1和C2中的文字，若σ是L1和~L2的最一般合一者，則稱

C12=(C1σ-{L1σ})∪(C2σ-{L2σ})為C1和C2的二元消解式，L1和L2為消解式上的文字26ppt課件設(shè)c1=P(x)∨Q(x),c2=～P(a)∨R(y){P(x),P(a)}的最一般的合一者為{a/x}c’1=Q(x)c’2=R(y)則c1,c2的消解式為

c=Q(a)∨R(y)例：27ppt課件怎么利用消解原理進(jìn)行證明？消解反演通俗的說(shuō)就是“反證法”要證命題A恒為真，等價(jià)于證﹁A恒為假證明過(guò)程否定結(jié)論R，得﹁R；把﹁R添加到已知前提集合F中去；把新產(chǎn)生的集合｛﹁R，F(xiàn)｝化成范式；應(yīng)用消解原理，不斷求消解式，直到得到一個(gè)表示矛盾的空子句28ppt課件從父子句求消解式的若干例子1、假言推理2、合并29ppt課件3、重言式5、鏈?zhǔn)剑ㄈ握摚?、空子句（矛盾）30ppt課件例：設(shè)子句集為S={P∨Q,～P∨Q,P∨～Q,～P∨～Q}求S的一個(gè)反演31ppt課件S的一個(gè)反演為：①P∨Q(S)②～P∨Q(S)③P∨～Q(S)④～P∨～Q(S)⑤Q①②⑥～Q③④⑦φ⑤⑥⑤P①③⑥～P②④⑦φ⑤⑥S的另一個(gè)反演為：32ppt課件含有變量的消解式（謂詞情況）先求最一般的合一者mgu，再求消解式例

置換33ppt課件例例34ppt課件設(shè)有公式集：F1:(x)(C(x)(W(x)∧R(x))F2:(x)(C(x)∧O(x))L:(x)(O(x)∧R(x))試證：L是F1，F(xiàn)2的邏輯結(jié)果，即F1∧F2L消解反演示例35ppt課件利用消解原理來(lái)構(gòu)造F1∧F2∧～L的一個(gè)反演

首先分別求出F1，F(xiàn)2和～L的子句集證明：36ppt課件(x)(C(x)(W(x)∧R(x))=(x)(～C(x)∨(W(x)∧R(x))=(x)((～C(x)∨W(x))∧(～C(x)∨R(x)))子句集={～C(x)∨W(x),～C(x)∨R(x)}(未改名)F1的前束合取范式與子句集：37ppt課件(x)(C(x)∧O(x))=(C(a)∧O(a))子句集={C(a),O(a)}F2的前束合取范式和子句集：38ppt課件～(x)(O(x)∧R(x))=(x)(～O(x)∨～R(x))子句集={～O(x)∨～R(x)}～L的前束范式和子句集：39ppt課件構(gòu)成子句集（注意改名）{～C(x)∨W(x),

～C(y)∨R(y),C(a)，O(a),

～O(z)∨～R(z)}40ppt課件①～C(x)∨W(x)②～C(y)∨R(y)③C(a)④O(a)⑤～O(z)∨～R(z)證明過(guò)程：41ppt課件⑥

R(a)②③，mgu={a/y}

⑦～R(a)④⑤mgu={a/z}

⑧φ⑥⑦②～C(y)∨R(y)③C(a)④O(a)⑤～O(z)∨～R(z)42ppt課件 假設(shè)：所有不貧窮并且聰明的人都是快樂(lè)的，那些看書(shū)的人是聰明的。李明能看書(shū)且不貧窮，快樂(lè)的人過(guò)著激動(dòng)人心的生活。求證：李明過(guò)著激動(dòng)人心的生活。解：先定義謂詞：

Poor(x)x是貧窮的

Smart(x)x是聰明的

Happy(x)x是快樂(lè)的

Read(x)x能看書(shū)

Exciting(x)x過(guò)著激動(dòng)人心的生活消解反演示例—“激動(dòng)人心的生活”問(wèn)題43ppt課件消解反演示例—“激動(dòng)人心的生活”問(wèn)題問(wèn)題謂詞表示：

“所有不貧窮并且聰明的人都是快樂(lè)的”

(?x)((~Poor(x)∧Smart(x))→Happy(x))“那些看書(shū)的人是聰明的”

(?y)(Read(y)→Smart(y))“李明能看書(shū)且不貧窮”

Read(Liming)∧~Poor(Liming)“快樂(lè)的人過(guò)著激動(dòng)人心的生活”

(?z)(Happy(z)→Exciting(z))目標(biāo)“李明過(guò)著激動(dòng)人心的生活”的否定

~Exciting(Liming)44ppt課件消解反演示例—“激動(dòng)人心的生活”問(wèn)題將上述謂詞公式轉(zhuǎn)化為子句集如下：

(1)Poor(x)∨~Smart(x)∨Happy(x)(2)~Read