《人工智能與專家系統(tǒng)(第二版)》第4章 邏輯推理課件

人工智能與專家系統(tǒng)人工智能與專家系統(tǒng)第4章邏輯推理4.1推理的基本概念4.2歸結(jié)演繹推理4.4歸結(jié)反演的改進(jìn)策略4.3基于歸結(jié)反演的問題求解第4章邏輯推理4.1推理的基本概念4.2歸結(jié)演繹推理4.1推理的基本概念4.1.1推理方式及其分類4.1.2推理的控制策略4.1.3模式匹配及其變量代換4.1推理的基本概念4.1.1推理方式及其分類1演繹推理、歸納推理、默認(rèn)推理演繹推理:是從全稱判斷推導(dǎo)出特稱判斷的過程，即由一般性知識推理適合于某一具體情況的結(jié)論，是一種從一般到個(gè)別的推理。歸納推理:是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個(gè)別到一般的推理。默認(rèn)推理:是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理4.1.1推理方式及其分類1演繹推理、歸納推理、默認(rèn)推

2確定性推理、不確定性推理確定性推理:是指推理時(shí)所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或者為假。不確定性推理:是指推理時(shí)所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于真與假之間。2確定性推理、不確定性推理3單調(diào)推理、非單調(diào)推理單調(diào)推理:隨著推理過程向前推進(jìn)及新知識的進(jìn)入，推出的結(jié)論呈單調(diào)增加的趨勢。非單調(diào)推理:由于新知識的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要使得推理退回到前面的某一步，重新開始。3單調(diào)推理、非單調(diào)推理4啟發(fā)式推理、非啟發(fā)式推理啟發(fā)式推理:運(yùn)用與問題有關(guān)的啟發(fā)性知識，且能加快推理進(jìn)程的推理。5基于知識的推理、直覺推理基于知識的推理:根據(jù)已掌握的事實(shí)，通過運(yùn)用知識進(jìn)行推理。

直覺推理:根據(jù)常識進(jìn)行的推理。4啟發(fā)式推理、非啟發(fā)式推理4.1.2推理的控制策略1推理方向（1）正向推理（2）逆向推理（3）混合推理4.1.2推理的控制策略1推理方向2求解策略推理的求解策略:推理是只求一個(gè)解，還是求所有解以及最優(yōu)解等。3限制策略推理的限制策略:在控制策略中指定推理的限制條件，以對推理的深度、寬度、時(shí)間、空間等進(jìn)行限制。2求解策略4沖突消解策略在推理過程中，可能發(fā)生已知事實(shí)可與知識庫中的多個(gè)知識匹配成功；或者有多個(gè)已知事實(shí)可與知識庫中的多個(gè)知識匹配成功。稱這種情況為發(fā)生了沖突。沖突消解:需要按一定策略解決沖突，以便從中挑選一個(gè)知識用于當(dāng)前的推理，稱這一解決沖突的過程為沖突消解。解決沖突所用的方法稱為沖突消解策略。4沖突消解策略4.1.3模式匹配及其變量代換模式匹配:兩個(gè)知識模式（如兩個(gè)謂詞公式、兩個(gè)框架片斷等）比較，檢查這兩個(gè)知識模式是否完全一致或近似一致。如果兩者完全一致，或者雖不完全一致但其相似程度落在指定的限度內(nèi)，就稱它們是可匹配的，否則為不可匹配。

確定性匹配:兩個(gè)知識模式完全一致，或者經(jīng)過變量代換后變得完全一致。4.1.3模式匹配及其變量代換模式匹配:例:設(shè)有如下兩個(gè)知識模式：P1：Father（李四，李小四）andMan(李小四)P2：Father(x,y)andMan(y)

若用常量“李四”代換變量x，用常量“李小四”代換變量y，則P1與P2就變得完全一致。例:設(shè)有如下兩個(gè)知識模式：定義4.1

代換是形如

{t1/x1,t2/x2,…，tn/xn}的有限集合。其中t1,t2…tn是項(xiàng)；

x1,

x2…xn是互不相同的變元；

ti/xi表示用ti代換xi,不允許ti與xi相同，也不允許變元xi循環(huán)地出現(xiàn)在另一個(gè)tj中。定義4.1代換是形如定義4.2設(shè)θ={t1/x1,t2/x2,…，tn/xn}

λ={u1/y1,u2/y2,…，um/ym}是兩個(gè)代換，則此兩個(gè)代換的復(fù)合也是一個(gè)代換，它是從{t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…，um/ym}中刪去如下兩種元素：tiλ/xi當(dāng)tiλ=xiui/yi當(dāng)yi∈{x1,x2,…，xn}后剩下的元素所構(gòu)成的集合，記為定義4.2設(shè)定義4.3

設(shè)有公式集F={F1,F2,…,Fn},若存在一個(gè)代換λ使得F1λ=F2λ=…=Fnλ則稱λ為公式集F的一個(gè)合一，且稱F1,F2,…Fn是可合一的。定義4.3設(shè)有公式集F={F1,F2,…,定義4.4

設(shè)σ是公式集F的一個(gè)合一，如果對任一個(gè)合一θ都存在一個(gè)代換λ，使得θ=σ。λ則稱σ是公式集F的最一般合一(mgu)。

定義4.4設(shè)σ是公式集F的一個(gè)合一，差異集：設(shè)有如下兩個(gè)謂詞公式：F1：P（x,y,z）F2：P(x,f(A),h(B))分別從F1與F2的第一個(gè)符號開始比較，得到第一個(gè)差異集：D1={y,f(A)}當(dāng)繼續(xù)比較，又發(fā)現(xiàn)F1中的z與F2中的h(B)不同，則得到第二個(gè)差異集：D2={z,h(B)}差異集：設(shè)有如下兩個(gè)謂詞公式：求最一般合一算法:（1）初始化，令k=0,Fk=F,σk=Φ。其中，Φ是代換空集。（2）若Fk只含一個(gè)表達(dá)式，則算法停止，σk就是最一般合一；否則轉(zhuǎn)步驟（3）。（3）找出Fk的差異集Dk。（4）若Dk中存在變元xk和項(xiàng)tk，且xk不在tk中出現(xiàn)，則：σk+1=σk。{tk/xk

}Fk+1=Fk{tk/xk

}k=k+1轉(zhuǎn)步驟（2）；否則，算法終止，F(xiàn)的最一般合一不存在。求最一般合一算法:例4.1

設(shè)有公式集：F={P(A,x,f(g(y))),

P(z,f(z),f(u))}，求其最一般合一。解：初始化，令k=0，σ0=Φ，F(xiàn)0=F={P(A,x,f

(g(y))),P(z,f

(z),f(u))}Loop1：

F0含有2個(gè)表達(dá)式，故σ0不是最一般合一，F(xiàn)0的差異集D0={A，z}，可有代換A/z，σ1=σ0{A/z}={A/z}F1=F0{A/z}={P(A,x,f(g(y))),P(A,f(A),f(u))}例4.1設(shè)有公式集：F={P(A,x,f(gLoop2：

F1含有2個(gè)表達(dá)式，故σ1不是最一般合一，

F1的差異集D1={x，f(A)}，可有代換{f(A)/x}，σ2=σ1。{f(A)/x}={A/z}。{f(A)/x}={A/z,f(A)/x}F2=F1{f(A)/x}={P(A,f(A),f(g(y))),P(A,f(A),f(u))}Loop2：F1含有2個(gè)表達(dá)式，故σ1不是最一般合一，Loop3：F2的差異集D2={g(y)，u}，可有代換{g(y)/u}，

σ3=σ2。{g(y)/u}={A/z,f(A)/x}。{g(y)/u}={A/z,f(A)/x,g(y)/u}F3=F2{g(y)/u}={P(A,f(A),f(g(y))),P(A,f(A),f(g(y)))}={P(A,f(A),f(g(y)))}

Loop4：F3中只含有一個(gè)表達(dá)式，故算法成功終止。公式集F的最一般合一為σ3={A/z,f(A)/x,g(y)/u}Loop3：F2的差異集D2={g(y)，u}，可有代4.2歸結(jié)演繹推理

4.2.1謂詞公式化為子句集的方法

4.2.2歸結(jié)原理

4.2.3歸結(jié)反演4.2歸結(jié)演繹推理定理證明的實(shí)質(zhì)是對已知前提P和待證結(jié)論Q證明P→Q的永真性。應(yīng)用反證法的思想可把關(guān)于永真性的證明轉(zhuǎn)化為不可滿足性的證明，即證明P∧﹁Q是不可滿足的。定理證明的實(shí)質(zhì)是對已知前提P和待證4.2.1謂詞公式化為子句集的方法定義4.5在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱為文字。任何文字的析取式稱為子句。定義4.6

不包含任何文字的子句稱為空子句。由于空子句不含有文字，它不能被任何解釋滿足，所以空子句是永假的，不可滿足的。4.2.1謂詞公式化為子句集的方法定義4.5謂詞公式化成子句集的步驟:（1）消去蘊(yùn)涵連詞利用下述等價(jià)關(guān)系消去謂詞公式中的蘊(yùn)涵連詞“→”：P→QP∨Q謂詞公式化成子句集的步驟:（2）減小否定連詞的轄域利用下述等價(jià)關(guān)系把“﹁”移到緊靠謂詞的位置上：（2）減小否定連詞的轄域（3）約束變元標(biāo)準(zhǔn)化（4）消去存在量詞若存在量詞不在全稱量詞的轄域內(nèi)，則用一個(gè)個(gè)體常量替換受該存在量詞約束的變元。若存在量詞位于一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，則需要用Skolem函數(shù)f(x1,x2,…，xn)替換受該存在量詞約束的變元y。（3）約束變元標(biāo)準(zhǔn)化（5）組成全稱量詞前綴（6）利用等價(jià)關(guān)系把母式化為Skolem標(biāo)準(zhǔn)形：

（7）消去全稱量詞。（8）對變元更名，使不同子句中的變元不同名。（9）消去合取連詞，得到子句集。（5）組成全稱量詞前綴例4.2請將下述謂詞公式化為子句集：例4.2請將下述謂詞公式化為子句集：解：解：4.2.2歸結(jié)原理子句集中的子句之間是合取關(guān)系，其中只要有一個(gè)子句不可滿足，子句集就不可滿足?？兆泳涫遣豢蓾M足的。因此，若一個(gè)子句集中包含空子句，則這個(gè)子句集是不可滿足的。4.2.2歸結(jié)原理子句集中的子句之間是合取1.命題邏輯中的歸結(jié)原理定義4.7若P是原子謂詞公式，則稱P與﹁P為互補(bǔ)文字。

定義4.8設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將二個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。1.命題邏輯中的歸結(jié)原理定理4.2歸結(jié)式C12是其親本子句C1與C2的邏輯結(jié)論

。

推論4.1設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性，即S1的不可滿足性S的不可滿足性

定理4.2歸結(jié)式C12是其親本子句C1與C2的推論4.2設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若把C12加入S中，得到新子句集S2，則S與S2在不可滿足的意義上是等價(jià)的，即S2的不可滿足性S的不可滿足性推論4.2設(shè)C1與C2是子句集S中的兩2.謂詞邏輯中的歸結(jié)原理

在謂詞邏輯中，由于子句中含有變元，所以不可直接消去互補(bǔ)文字，先對變元代換，才能進(jìn)行歸結(jié)。例如：

用最一般合一：σ={A/x}對兩個(gè)子句分別進(jìn)行代換：C1σ=P(A)∨Q(A)C2σ=﹁P(A)∨R(y)得到歸結(jié)式：Q(A)∨R(y)2.謂詞邏輯中的歸結(jié)原理

定義4.9設(shè)C1與C2是兩個(gè)沒有相同變元的子句，L1和L2分別是C1和C2中的文字，若σ是L1和L2的最一般合一，則稱C12=(C1σ-{L1σ})∪(C2σ-{L2σ})為C1和C2的二元?dú)w結(jié)式，L1和L2稱為歸結(jié)式的文字。定義4.9設(shè)C1與C2是兩個(gè)沒有相同變元例4.3設(shè)C1=P(A)∨Q(x)∨R(x)，C2=P(y)∨Q(B)，給出C1和C2的歸結(jié)式。例4.3設(shè)C1=P(A)∨Q(x)∨R(x)，C2=P

上述歸結(jié)過程可以用歸結(jié)樹表示如圖4.1所示。

圖4.1例4.3的一種歸結(jié)樹上述歸結(jié)過程可以用歸結(jié)樹表示如圖4.1所示。

若選L1=﹁Q(x),L2=Q(B),σ={B/x},則可得：C12=({P(A),﹁Q(B),R(B)}-{﹁Q(B)})∪({﹁P(y),Q(B)}-{Q(B)})=({P(A),R(B)})∪({﹁P(y)})={P(A),R(B),﹁P(y)}=P(A)∨R(B)∨﹁P(y)若選L1=﹁Q(x),L2=Q(B上述歸結(jié)過程的歸結(jié)樹如圖4.2所示。圖4.2例4.3的另一種歸結(jié)樹上述歸結(jié)過程的歸結(jié)樹如圖4.2所示。4.2.3歸結(jié)反演應(yīng)用歸結(jié)原理證明結(jié)論為真的過程稱為歸結(jié)反演。設(shè)F為已知前提的公式集，Q為目標(biāo)公式（結(jié)論），用歸結(jié)反演證明Q為真的步驟：①否定Q，得到﹁Q；②把﹁Q并入到公式集F中，得到{F，﹁Q}；③把公式集{F，﹁Q}化為子句集S；④應(yīng)用歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時(shí)就證明了Q為真。4.2.3歸結(jié)反演應(yīng)用歸結(jié)原理證明結(jié)論為真的例4.6

已知求證：G是F的邏輯結(jié)論。例4.6已知證：首先把F和G化為子句集證：首先把F和G化為子句集圖4.4例4.6的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件例4.7

在第2章例2.4中曾經(jīng)得到如下公式：

自然數(shù)都是大于零的整數(shù)。所有整數(shù)不是偶數(shù)就是奇數(shù)。偶數(shù)除以２是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。例4.7在第2章例2.4中曾經(jīng)得到如下公式：證：首先把求證的問題用謂詞公式表示出來：把F1，F(xiàn)2，F(xiàn)3及G化成子句集：(1)﹁N(x)∨GZ(x)(2)﹁N(u)∨I(u)(3)﹁I(y)∨E(y)∨O(y)(4)﹁E(z)∨I(s(z))(5)N(t)(6)﹁O(t)(7)﹁I(s(t))證：首先把求證的問題用謂詞公式表示出來：圖4.5例4.7的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件4.3基于歸結(jié)反演的問題求解問題求解的步驟：①把已知前提用謂詞公式表示，并且化為相應(yīng)的子句集S。②把待求解的問題也用謂詞公式表示，把它的否定式與謂詞ANSWER構(gòu)成一個(gè)析取式，ANSWER的變元數(shù)量和變元名必須與問題公式的變元一致。4.3基于歸結(jié)反演的問題求解問題求解的步驟：③把此析取式化為子句集，并且把該子句集加入到子句集S中，得到子句集S。④對S應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。⑤若在歸結(jié)樹的根節(jié)點(diǎn)中僅得到歸結(jié)式ANSWER，則答案就在ANSWER中。③把此析取式化為子句集，并且把該例4.8

已知F1：王（Wang）先生是小李（Li）的老師。F2：小李與小張（Zhang）是同班同學(xué)。F3：如果x與y是同班同學(xué)，則x的老師也是y的老師。求：小張的老師是誰？例4.8已知解：1定義謂詞T(x,y)x是y的老師。C(x,y)x與y是同班同學(xué)。2謂詞公式表示目標(biāo)公式G的否定式與ANSWER的析取式為：解：1定義謂詞3化為子句集(1)T(Wang,Li)(2)C(Li,Zhang

)(3)﹁C(x,y)∨﹁T(z,x)∨T(x,y)(4)﹁T(u,Zhang

)∨ANSWER(u)3化為子句集圖4.6例4.8的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件例4.9設(shè)A，B，C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個(gè)問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個(gè)是說謊者”。求誰是老實(shí)人，誰是說謊者？例4.9設(shè)A，B，C三人中有人從不說解：1定義謂詞：

T(x)表示x說真話。2謂詞公式表示如果A說的是真話，則有：T(A)→﹁T(B)∧﹁T(C)如果A說的是假話，則有：﹁T(A)→T(B)∨T(C)對B和C說的話作相同的處理，可得：T(B)→﹁T(A)∧﹁T(C)

﹁T(B)→T(A)∨T(C)T(C)→T(A)∨﹁T(B)﹁T(C)→T(A)∧T(B)解：1定義謂詞：3化成子句集S(1)﹁T(A)∨﹁T(B)(2)﹁T(A)∨﹁T(C)(3)T(A)∨T(B)∨T(C)(4)﹁T(B)∨﹁T(C)(5)﹁T(C)∨﹁T(A)∨﹁T(B)(6)T(C)∨T(A)(7)T(C)∨T(B)求誰是老實(shí)人的目標(biāo)公式：(x)T(x)(8)﹁T(x)∨ANSWER(x)3化成子句集S

圖4.7求誰是老實(shí)人的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件證明A和B不是老實(shí)人：設(shè)A不是老實(shí)人，則有﹁T(A)，把它的否定式T(A)加入到S中，得到子句集S2。對S2歸結(jié)，從而證明了A不是老實(shí)人。同理，可證明B也不是老實(shí)人。證明A和B不是老實(shí)人：圖4.8例4.9證明A不是老實(shí)人的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件4.4歸結(jié)反演的改進(jìn)策略4.4.1刪除策略4.4.2限制策略4.4歸結(jié)反演的改進(jìn)策略4.4.1刪除策略1純文字刪除

如果某文字L在子句集中不存在可與之互補(bǔ)的文字L，則稱該文字為純文字。在歸結(jié)時(shí)純文字不可能被消去，因而用包含它的子句進(jìn)行歸結(jié)時(shí)不可能得到空子句。例如，設(shè)有子句集：S={P∨Q∨R,﹁Q∨R，Q,﹁R}其中，P是純文字，因此可將子句P∨Q∨R從S中刪去。4.4.1刪除策略1純文字刪除2重言式刪除

如果一個(gè)子句中同時(shí)包含互補(bǔ)文字時(shí)，則稱該子句為重言式。例如P(x)∨﹁P(x),P(x)∨Q(x)∨﹁P(x)都是重言式。重言式是真值為真的子句。對于一個(gè)子句集來說，增加或者刪去一個(gè)真值為真的子句都不會(huì)影響它的不可滿足性，因而可從子句集中刪去重言式。2重言式刪除3包孕刪除

設(shè)有子句C1和C2，如果存在一個(gè)代換σ，使得則稱C1包孕于C2。例如：P(x)包孕于P(y)∨Q(z)σ={y/x}或稱P(x)被P(y)∨Q(z)包孕把子句集中被包孕的子句刪去后，不會(huì)影響子句集的不可滿足性，可從子句集中刪去被其它子句包孕的子句。3包孕刪除4.4.2限制策略1支持集策略

支持集策略對參加歸結(jié)的子句提出了如下限制：每一次歸結(jié)時(shí)，親本子句中至少應(yīng)有一個(gè)是由目標(biāo)公式的否定所得到的子句，或者是它們的后裔。支持集策略是完備的。4.4.2限制策略1支持集策略例4.10設(shè)有初始子句集：S={﹁I(x)∨R(x),I(A),﹁R(y)∨﹁L(y),L(A)}其中﹁I(x)∨R(x)是目標(biāo)公式否定得到的子句。例4.10設(shè)有初始子句集：圖4.9支持集策略歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件2線性輸入策略

線性輸入策略對參加歸結(jié)的子句提出了如下限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是初始子句集中的子句。線性輸入策略是不完備的。2線性輸入策略例4.11

應(yīng)用線性輸入策略對例4.10的初始子句集進(jìn)行歸結(jié)。圖4.10線性輸入策略歸結(jié)樹例4.11應(yīng)用線性輸入策略對例4.10的初始子句集進(jìn)行3單文字子句策略3單文字子句策略如果一個(gè)子句只包含一個(gè)文字，則稱它為單文字子句。單文字子句策略要求參加歸結(jié)的兩個(gè)子句中必須有一個(gè)是單文字子句。單文字子句策略是不完備的。3單文字子句策略3單文字子句策略例4.12

對例4.10給出的初始子句集按單文字子句策略進(jìn)行歸結(jié)。圖4.11單文字子句策略的歸結(jié)樹例4.12對例4.10給出的初始子句集按單文字子句策略

5祖先過濾形策略

祖先過濾形策略要求兩個(gè)子句C1和C2滿足下述兩個(gè)條件中的任意一個(gè)條件：①C1與C2中至少有一個(gè)是初始子句集中的子句。②如果兩個(gè)子句都不是初始子句集中的子句，則一個(gè)應(yīng)是另一個(gè)的祖先。祖先過濾形策略是完備的。5祖先過濾形策略例4.13有子句集S={﹁P(x)∨Q(x),

﹁P(y)∨Q(y),P(u)∨Q(u),P(t)∨﹁Q(t)},用祖先過濾形策略進(jìn)行歸結(jié)。例4.13有子句集圖4.12祖先過濾形策略歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件人工智能與專家系統(tǒng)人工智能與專家系統(tǒng)第4章邏輯推理4.1推理的基本概念4.2歸結(jié)演繹推理4.4歸結(jié)反演的改進(jìn)策略4.3基于歸結(jié)反演的問題求解第4章邏輯推理4.1推理的基本概念4.2歸結(jié)演繹推理4.1推理的基本概念4.1.1推理方式及其分類4.1.2推理的控制策略4.1.3模式匹配及其變量代換4.1推理的基本概念4.1.1推理方式及其分類1演繹推理、歸納推理、默認(rèn)推理演繹推理:是從全稱判斷推導(dǎo)出特稱判斷的過程，即由一般性知識推理適合于某一具體情況的結(jié)論，是一種從一般到個(gè)別的推理。歸納推理:是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個(gè)別到一般的推理。默認(rèn)推理:是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理4.1.1推理方式及其分類1演繹推理、歸納推理、默認(rèn)推

2確定性推理、不確定性推理確定性推理:是指推理時(shí)所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或者為假。不確定性推理:是指推理時(shí)所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于真與假之間。2確定性推理、不確定性推理3單調(diào)推理、非單調(diào)推理單調(diào)推理:隨著推理過程向前推進(jìn)及新知識的進(jìn)入，推出的結(jié)論呈單調(diào)增加的趨勢。非單調(diào)推理:由于新知識的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要使得推理退回到前面的某一步，重新開始。3單調(diào)推理、非單調(diào)推理4啟發(fā)式推理、非啟發(fā)式推理啟發(fā)式推理:運(yùn)用與問題有關(guān)的啟發(fā)性知識，且能加快推理進(jìn)程的推理。5基于知識的推理、直覺推理基于知識的推理:根據(jù)已掌握的事實(shí)，通過運(yùn)用知識進(jìn)行推理。

直覺推理:根據(jù)常識進(jìn)行的推理。4啟發(fā)式推理、非啟發(fā)式推理4.1.2推理的控制策略1推理方向（1）正向推理（2）逆向推理（3）混合推理4.1.2推理的控制策略1推理方向2求解策略推理的求解策略:推理是只求一個(gè)解，還是求所有解以及最優(yōu)解等。3限制策略推理的限制策略:在控制策略中指定推理的限制條件，以對推理的深度、寬度、時(shí)間、空間等進(jìn)行限制。2求解策略4沖突消解策略在推理過程中，可能發(fā)生已知事實(shí)可與知識庫中的多個(gè)知識匹配成功；或者有多個(gè)已知事實(shí)可與知識庫中的多個(gè)知識匹配成功。稱這種情況為發(fā)生了沖突。沖突消解:需要按一定策略解決沖突，以便從中挑選一個(gè)知識用于當(dāng)前的推理，稱這一解決沖突的過程為沖突消解。解決沖突所用的方法稱為沖突消解策略。4沖突消解策略4.1.3模式匹配及其變量代換模式匹配:兩個(gè)知識模式（如兩個(gè)謂詞公式、兩個(gè)框架片斷等）比較，檢查這兩個(gè)知識模式是否完全一致或近似一致。如果兩者完全一致，或者雖不完全一致但其相似程度落在指定的限度內(nèi)，就稱它們是可匹配的，否則為不可匹配。

確定性匹配:兩個(gè)知識模式完全一致，或者經(jīng)過變量代換后變得完全一致。4.1.3模式匹配及其變量代換模式匹配:例:設(shè)有如下兩個(gè)知識模式：P1：Father（李四，李小四）andMan(李小四)P2：Father(x,y)andMan(y)

若用常量“李四”代換變量x，用常量“李小四”代換變量y，則P1與P2就變得完全一致。例:設(shè)有如下兩個(gè)知識模式：定義4.1

代換是形如

{t1/x1,t2/x2,…，tn/xn}的有限集合。其中t1,t2…tn是項(xiàng)；

x1,

x2…xn是互不相同的變元；

ti/xi表示用ti代換xi,不允許ti與xi相同，也不允許變元xi循環(huán)地出現(xiàn)在另一個(gè)tj中。定義4.1代換是形如定義4.2設(shè)θ={t1/x1,t2/x2,…，tn/xn}

λ={u1/y1,u2/y2,…，um/ym}是兩個(gè)代換，則此兩個(gè)代換的復(fù)合也是一個(gè)代換，它是從{t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…，um/ym}中刪去如下兩種元素：tiλ/xi當(dāng)tiλ=xiui/yi當(dāng)yi∈{x1,x2,…，xn}后剩下的元素所構(gòu)成的集合，記為定義4.2設(shè)定義4.3

設(shè)有公式集F={F1,F2,…,Fn},若存在一個(gè)代換λ使得F1λ=F2λ=…=Fnλ則稱λ為公式集F的一個(gè)合一，且稱F1,F2,…Fn是可合一的。定義4.3設(shè)有公式集F={F1,F2,…,定義4.4

設(shè)σ是公式集F的一個(gè)合一，如果對任一個(gè)合一θ都存在一個(gè)代換λ，使得θ=σ。λ則稱σ是公式集F的最一般合一(mgu)。

定義4.4設(shè)σ是公式集F的一個(gè)合一，差異集：設(shè)有如下兩個(gè)謂詞公式：F1：P（x,y,z）F2：P(x,f(A),h(B))分別從F1與F2的第一個(gè)符號開始比較，得到第一個(gè)差異集：D1={y,f(A)}當(dāng)繼續(xù)比較，又發(fā)現(xiàn)F1中的z與F2中的h(B)不同，則得到第二個(gè)差異集：D2={z,h(B)}差異集：設(shè)有如下兩個(gè)謂詞公式：求最一般合一算法:（1）初始化，令k=0,Fk=F,σk=Φ。其中，Φ是代換空集。（2）若Fk只含一個(gè)表達(dá)式，則算法停止，σk就是最一般合一；否則轉(zhuǎn)步驟（3）。（3）找出Fk的差異集Dk。（4）若Dk中存在變元xk和項(xiàng)tk，且xk不在tk中出現(xiàn)，則：σk+1=σk。{tk/xk

}Fk+1=Fk{tk/xk

}k=k+1轉(zhuǎn)步驟（2）；否則，算法終止，F(xiàn)的最一般合一不存在。求最一般合一算法:例4.1

設(shè)有公式集：F={P(A,x,f(g(y))),

P(z,f(z),f(u))}，求其最一般合一。解：初始化，令k=0，σ0=Φ，F(xiàn)0=F={P(A,x,f

(g(y))),P(z,f

(z),f(u))}Loop1：

F0含有2個(gè)表達(dá)式，故σ0不是最一般合一，F(xiàn)0的差異集D0={A，z}，可有代換A/z，σ1=σ0{A/z}={A/z}F1=F0{A/z}={P(A,x,f(g(y))),P(A,f(A),f(u))}例4.1設(shè)有公式集：F={P(A,x,f(gLoop2：

F1含有2個(gè)表達(dá)式，故σ1不是最一般合一，

F1的差異集D1={x，f(A)}，可有代換{f(A)/x}，σ2=σ1。{f(A)/x}={A/z}。{f(A)/x}={A/z,f(A)/x}F2=F1{f(A)/x}={P(A,f(A),f(g(y))),P(A,f(A),f(u))}Loop2：F1含有2個(gè)表達(dá)式，故σ1不是最一般合一，Loop3：F2的差異集D2={g(y)，u}，可有代換{g(y)/u}，

σ3=σ2。{g(y)/u}={A/z,f(A)/x}。{g(y)/u}={A/z,f(A)/x,g(y)/u}F3=F2{g(y)/u}={P(A,f(A),f(g(y))),P(A,f(A),f(g(y)))}={P(A,f(A),f(g(y)))}

Loop4：F3中只含有一個(gè)表達(dá)式，故算法成功終止。公式集F的最一般合一為σ3={A/z,f(A)/x,g(y)/u}Loop3：F2的差異集D2={g(y)，u}，可有代4.2歸結(jié)演繹推理

4.2.1謂詞公式化為子句集的方法

4.2.2歸結(jié)原理

4.2.3歸結(jié)反演4.2歸結(jié)演繹推理定理證明的實(shí)質(zhì)是對已知前提P和待證結(jié)論Q證明P→Q的永真性。應(yīng)用反證法的思想可把關(guān)于永真性的證明轉(zhuǎn)化為不可滿足性的證明，即證明P∧﹁Q是不可滿足的。定理證明的實(shí)質(zhì)是對已知前提P和待證4.2.1謂詞公式化為子句集的方法定義4.5在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱為文字。任何文字的析取式稱為子句。定義4.6

不包含任何文字的子句稱為空子句。由于空子句不含有文字，它不能被任何解釋滿足，所以空子句是永假的，不可滿足的。4.2.1謂詞公式化為子句集的方法定義4.5謂詞公式化成子句集的步驟:（1）消去蘊(yùn)涵連詞利用下述等價(jià)關(guān)系消去謂詞公式中的蘊(yùn)涵連詞“→”：P→QP∨Q謂詞公式化成子句集的步驟:（2）減小否定連詞的轄域利用下述等價(jià)關(guān)系把“﹁”移到緊靠謂詞的位置上：（2）減小否定連詞的轄域（3）約束變元標(biāo)準(zhǔn)化（4）消去存在量詞若存在量詞不在全稱量詞的轄域內(nèi)，則用一個(gè)個(gè)體常量替換受該存在量詞約束的變元。若存在量詞位于一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，則需要用Skolem函數(shù)f(x1,x2,…，xn)替換受該存在量詞約束的變元y。（3）約束變元標(biāo)準(zhǔn)化（5）組成全稱量詞前綴（6）利用等價(jià)關(guān)系把母式化為Skolem標(biāo)準(zhǔn)形：

（7）消去全稱量詞。（8）對變元更名，使不同子句中的變元不同名。（9）消去合取連詞，得到子句集。（5）組成全稱量詞前綴例4.2請將下述謂詞公式化為子句集：例4.2請將下述謂詞公式化為子句集：解：解：4.2.2歸結(jié)原理子句集中的子句之間是合取關(guān)系，其中只要有一個(gè)子句不可滿足，子句集就不可滿足?？兆泳涫遣豢蓾M足的。因此，若一個(gè)子句集中包含空子句，則這個(gè)子句集是不可滿足的。4.2.2歸結(jié)原理子句集中的子句之間是合取1.命題邏輯中的歸結(jié)原理定義4.7若P是原子謂詞公式，則稱P與﹁P為互補(bǔ)文字。

定義4.8設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將二個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。1.命題邏輯中的歸結(jié)原理定理4.2歸結(jié)式C12是其親本子句C1與C2的邏輯結(jié)論

。

推論4.1設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性，即S1的不可滿足性S的不可滿足性

定理4.2歸結(jié)式C12是其親本子句C1與C2的推論4.2設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若把C12加入S中，得到新子句集S2，則S與S2在不可滿足的意義上是等價(jià)的，即S2的不可滿足性S的不可滿足性推論4.2設(shè)C1與C2是子句集S中的兩2.謂詞邏輯中的歸結(jié)原理

在謂詞邏輯中，由于子句中含有變元，所以不可直接消去互補(bǔ)文字，先對變元代換，才能進(jìn)行歸結(jié)。例如：

用最一般合一：σ={A/x}對兩個(gè)子句分別進(jìn)行代換：C1σ=P(A)∨Q(A)C2σ=﹁P(A)∨R(y)得到歸結(jié)式：Q(A)∨R(y)2.謂詞邏輯中的歸結(jié)原理

定義4.9設(shè)C1與C2是兩個(gè)沒有相同變元的子句，L1和L2分別是C1和C2中的文字，若σ是L1和L2的最一般合一，則稱C12=(C1σ-{L1σ})∪(C2σ-{L2σ})為C1和C2的二元?dú)w結(jié)式，L1和L2稱為歸結(jié)式的文字。定義4.9設(shè)C1與C2是兩個(gè)沒有相同變元例4.3設(shè)C1=P(A)∨Q(x)∨R(x)，C2=P(y)∨Q(B)，給出C1和C2的歸結(jié)式。例4.3設(shè)C1=P(A)∨Q(x)∨R(x)，C2=P

上述歸結(jié)過程可以用歸結(jié)樹表示如圖4.1所示。

圖4.1例4.3的一種歸結(jié)樹上述歸結(jié)過程可以用歸結(jié)樹表示如圖4.1所示。

若選L1=﹁Q(x),L2=Q(B),σ={B/x},則可得：C12=({P(A),﹁Q(B),R(B)}-{﹁Q(B)})∪({﹁P(y),Q(B)}-{Q(B)})=({P(A),R(B)})∪({﹁P(y)})={P(A),R(B),﹁P(y)}=P(A)∨R(B)∨﹁P(y)若選L1=﹁Q(x),L2=Q(B上述歸結(jié)過程的歸結(jié)樹如圖4.2所示。圖4.2例4.3的另一種歸結(jié)樹上述歸結(jié)過程的歸結(jié)樹如圖4.2所示。4.2.3歸結(jié)反演應(yīng)用歸結(jié)原理證明結(jié)論為真的過程稱為歸結(jié)反演。設(shè)F為已知前提的公式集，Q為目標(biāo)公式（結(jié)論），用歸結(jié)反演證明Q為真的步驟：①否定Q，得到﹁Q；②把﹁Q并入到公式集F中，得到{F，﹁Q}；③把公式集{F，﹁Q}化為子句集S；④應(yīng)用歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時(shí)就證明了Q為真。4.2.3歸結(jié)反演應(yīng)用歸結(jié)原理證明結(jié)論為真的例4.6

已知求證：G是F的邏輯結(jié)論。例4.6已知證：首先把F和G化為子句集證：首先把F和G化為子句集圖4.4例4.6的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件例4.7

在第2章例2.4中曾經(jīng)得到如下公式：

自然數(shù)都是大于零的整數(shù)。所有整數(shù)不是偶數(shù)就是奇數(shù)。偶數(shù)除以２是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。例4.7在第2章例2.4中曾經(jīng)得到如下公式：證：首先把求證的問題用謂詞公式表示出來：把F1，F(xiàn)2，F(xiàn)3及G化成子句集：(1)﹁N(x)∨GZ(x)(2)﹁N(u)∨I(u)(3)﹁I(y)∨E(y)∨O(y)(4)﹁E(z)∨I(s(z))(5)N(t)(6)﹁O(t)(7)﹁I(s(t))證：首先把求證的問題用謂詞公式表示出來：圖4.5例4.7的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件4.3基于歸結(jié)反演的問題求解問題求解的步驟：①把已知前提用謂詞公式表示，并且化為相應(yīng)的子句集S。②把待求解的問題也用謂詞公式表示，把它的否定式與謂詞ANSWER構(gòu)成一個(gè)析取式，ANSWER的變元數(shù)量和變元名必須與問題公式的變元一致。4.3基于歸結(jié)反演的問題求解問題求解的步驟：③把此析取式化為子句集，并且把該子句集加入到子句集S中，得到子句集S。④對S應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。⑤若在歸結(jié)樹的根節(jié)點(diǎn)中僅得到歸結(jié)式ANSWER，則答案就在ANSWER中。③把此析取式化為子句集，并且把該例4.8

已知F1：王（Wang）先生是小李（Li）的老師。F2：小李與小張（Zhang）是同班同學(xué)。F3：如果x與y是同班同學(xué)，則x的老師也是y的老師。求：小張的老師是誰？例4.8已知解：1定義謂詞T(x,y)x是y的老師。C(x,y)x與y是同班同學(xué)。2謂詞公式表示目標(biāo)公式G的否定式與ANSWER的析取式為：解：1定義謂詞3化為子句集(1)T(Wang,Li)(2)C(Li,Zhang

)(3)﹁C(x,y)∨﹁T(z,x)∨T(x,y)(4)﹁T(u,Zhang

)∨ANSWER(u)3化為子句集圖4.6例4.8的歸結(jié)樹《人工智能與專家系統(tǒng)(第二版)》第4章邏輯推理課件例4.9設(shè)A，B，C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個(gè)問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個(gè)是說謊者”。求誰是老實(shí)人，誰是說謊者？例4.9設(shè)A，B，C三人中有人從不說解：1定義謂詞：

T(x)表示x說真話。2謂詞公式表示如果A說的是真話，則有：T(A)→﹁T(B)∧﹁T(C)如果A說的是假話，則有：﹁T(A)→T(B)∨T(C)對B和C說的話作相同的處理，可得：T(B)→﹁T(A)∧﹁T(C)

﹁T(B)→T(A)∨T(C)T(C)→T(A)∨﹁T(B)﹁T(C)→T(A)∧T(B)解：1定義謂詞：3化成子句集S(1)﹁T(A)∨﹁T(B)(2)﹁T(A)∨﹁T(C)(3)T(A)∨T(B)∨T(C)