第三章 確定性推理方法

第3章確定性推理方法知識智能？知識

推理智能！5個房間的問題（給福爾摩斯出的問題）5個不同顏色的房間，每間有個不同國籍的人，每人有自己喜歡的飲料，香煙和寵物，已知信息：1.英國人住在紅房間里；2.西班牙人有一條狗；3.挪威人住在左邊第一個房間里；4.黃房間的人在抽庫爾斯牌香煙；5.抽切斯菲爾德牌香煙的人是養(yǎng)了一只狐貍的人的鄰居；6.挪威人住在藍房間隔壁；7.抽溫斯頓牌香煙的人有一只蝸牛；8.抽幸運牌香煙的人喝橘子汁；9.烏克蘭人喝茶；10.日本人抽國會牌香煙；11.抽庫爾斯牌香煙的人的房間在有匹馬的房間隔壁；12.綠房間的人喝咖啡；13.中間房間的人喝牛奶14.綠房間的人在白房間的隔壁問題：哪個房間的人喝水？斑馬在哪個房間？房間號12345顏色國籍香煙飲料寵物3.挪威人住在左邊第一個房間6.挪威人住在藍房間旁邊13.中間房間的人喝牛奶挪威人藍色牛奶12.綠房間的人喝咖啡14.綠房間的人在白房間的隔壁綠色白色咖啡1.英國人住在紅色的房間紅色英國人黃色4.黃房間的人抽庫爾斯牌香煙11.抽庫爾斯牌煙的房間在有匹馬的房間的隔壁庫爾斯牌馬水2.西班牙人有一條狗8.抽幸運牌香煙的人喝橘子汁9.烏克蘭人喝茶10.日本人抽國會牌香煙橘子汁是誰喝的？橘子汁狗幸運牌西班牙人茶烏克蘭人日本人國會牌7.抽溫斯頓牌香煙的人有一只蝸牛溫斯頓蝸牛切斯菲爾德5.抽切斯菲爾德香煙的人的是養(yǎng)了一只狐貍的人的鄰居狐貍斑馬8.抽幸運牌香煙的人喝橘子汁9.烏克蘭人喝茶用Prolog語言編的程序，一秒鐘都不到就知道了答案,不過它的推理過程和人的完全不一樣；Prolog：ProgrammLogic(邏輯程序設(shè)計語言)推理方法：確定性推理：（演繹推理）（1）謂詞公式化為子句集（2）魯賓遜歸結(jié)原理（消解原理）（3）歸結(jié)反演機器證明歸結(jié)演繹推理第3章確定性推理方法3.1推理的基本概念

3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結(jié)原理3.6歸結(jié)反演3.7應(yīng)用歸結(jié)反演求解問題

3.1推理的基本概念3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略醫(yī)療專家系統(tǒng)3.1.1推理的定義知識專家的經(jīng)驗、醫(yī)學(xué)常識初始證據(jù)病人的癥狀、化驗結(jié)果證據(jù)中間結(jié)論推理：3.1推理的基本概念3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略（1）演繹推理

(deductivereasoning):一般→個別

三段論式（三段論法）足球運動員的身體都是強壯的；高波是一名足球運動員；所以，高波的身體是強壯的。3.1.2推理方式及其分類1.演繹推理、歸納推理、默認(rèn)推理（大前提）（小前提）（結(jié)論）3.1.2推理方式及其分類1.演繹推理、歸納推理、默認(rèn)推理（按推出結(jié)論的途徑）（2）歸納推理(inductivereasoning):個別→一般

完全歸納推理（必然性推理）

不完全歸納推理（非必然性推理）檢查全部產(chǎn)品合格該廠產(chǎn)品合格完全歸納推理檢查全部樣品合格該廠產(chǎn)品合格不完全歸納推理

3.1.2推理方式及其分類（3）默認(rèn)推理（defaultreasoning，缺省推理）

知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進行的推理。

結(jié)論

A

成立

B

成立？（在不能證明B不成立的情況下，默認(rèn)B成立）鳥籠要有蓋子制造鳥籠鳥會飛？（正常情況下默認(rèn)鳥會飛成立）1.演繹推理、歸納推理、默認(rèn)推理3.1.2推理方式及其分類

2.

確定性推理、不確定性推理（按知識的確定性）似然推理近似推理或模糊推理不確定性推理（概率論）（模糊邏輯）（1）確定性推理：推理時所用的知識與證據(jù)都是確定的，推出的結(jié)論也是確定的，其真值或者為真或者為假。

（2）不確定性推理：推理時所用的知識與證據(jù)不都是確定的，推出的結(jié)論也是不確定的。X：鳥→

X：會飛3.1.2推理方式及其分類

3.單調(diào)推理、非單調(diào)推理（按靠近結(jié)論的方式）

（1）單調(diào)推理：隨著推理向前推進及新知識的加入，推出的結(jié)論越來越接近最終目標(biāo)。

（2）非單調(diào)推理：由于新知識的加入，不僅沒有加強已推出的結(jié)論，反而要否定它，使推理退回到前面的某一步，重新開始。

默認(rèn)推理是非單調(diào)推理

基于經(jīng)典邏輯的演繹推理

X：企鵝X：不會飛X：不會飛3.1.2推理方式及其分類4．啟發(fā)式推理、非啟發(fā)式推理（是否運用啟發(fā)式知識）

啟發(fā)性知識：與問題有關(guān)且能加快推理過程、提高搜索效率的知識。

目標(biāo)：在腦膜炎、肺炎、流感中選擇一個產(chǎn)生式規(guī)則

r1：腦膜炎

r2：肺炎

r3：流感啟發(fā)式知識：“腦膜炎危險”、“目前正在盛行流感”。3.1推理的基本概念3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略3.1.3推理的方向3.1.3推理的方向

正向推理（事實驅(qū)動推理）:已知事實→結(jié)論基本思想（1）從初始已知事實出發(fā)，在知識庫KB中找出當(dāng)前可適用的知識，構(gòu)成可適用知識集KS。（2）按某種沖突消解策略從KS中選出一條知識進行推理，并將推出的新事實加入到數(shù)據(jù)庫DB中作為下一步推理的已知事實，再在KB中選取可適用知識構(gòu)成KS。（3）重復(fù)（2），直到求得問題的解或KB中再無可適用的知識。1.正向推理3.1.3推理的方向

實現(xiàn)正向推理需要解決的問題：確定匹配（知識與已知事實）的方法。按什么策略搜索知識庫。沖突消解策略。正向推理簡單，易實現(xiàn)，但目的性不強，效率低。1.正向推理3.1.3推理的方向

逆向推理（目標(biāo)驅(qū)動推理）：以某個假設(shè)目標(biāo)作為出發(fā)點?；舅枷耄哼x定一個假設(shè)目標(biāo)。尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則原假設(shè)成立；若無論如何都找不到所需要的證據(jù)，說明原假設(shè)不成立的；為此需要另作新的假設(shè)。主要優(yōu)點：不必使用與目標(biāo)無關(guān)的知識，目的性強，同時它還有利于向用戶提供解釋。主要缺點：起始目標(biāo)的選擇有盲目性。2.逆向推理3.1.3推理的方向

逆向推理需要解決的問題：如何判斷一個假設(shè)是否是證據(jù)？當(dāng)導(dǎo)出假設(shè)的知識有多條時，如何確定先選哪一條？

一條知識的運用條件一般都有多個，當(dāng)其中的一個經(jīng)驗證成立后，如何自動地?fù)Q為對另一個的驗證？

……..

逆向推理：目的性強，利于向用戶提供解釋，但選擇初始目標(biāo)時具有盲目性，比正向推理復(fù)雜。2.逆向推理3.1.3推理的方向

正向推理:盲目、效率低。逆向推理:若提出的假設(shè)目標(biāo)不符合實際，會降低效率。正反向混合推理：（1）先正向后逆向：先進行正向推理，幫助選擇某個目標(biāo)，即從已知事實演繹出部分結(jié)果，然后再用逆向推理證實該目標(biāo)或提高其可信度；（2）先逆向后正向：先假設(shè)一個目標(biāo)進行逆向推理，然后再利用逆向推理中得到的信息進行正向推理，以推出更多的結(jié)論。3.混合推理

雙向推理：正向推理與逆向推理同時進行，且在推理過程中的某一步驟上“碰頭”的一種推理。已知事實假設(shè)目標(biāo)反向推理正向推理3.1.3推理的方向4.雙向推理中間結(jié)論證據(jù)3.1推理的基本概念3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略3.1.4沖突消解策略

已知事實與知識的三種匹配情況：（1）恰好匹配成功（一對一）；（2）不能匹配成功；（3）多種匹配成功（一對多、多對一、多對多）沖突消解3.1.4沖突消解策略多種沖突消解策略：（1）按針對性排序（2）按已知事實的新鮮性排序（3）按匹配度排序（4）按條件個數(shù)排序（5）按上下文限制排序（6）按冗余限制排序（7）根據(jù)領(lǐng)域問題的特點排序r1:IFA1ANDA2THENH1r2:IFA1ANDA2ANDA3ANDA4THENH2第3章確定性推理方法3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結(jié)原理3.6歸結(jié)反演3.7應(yīng)用歸結(jié)反演求解問題27

定義1

設(shè)P與Q是兩個謂詞公式，D是它們共同的個體域，若對D上的任何一個解釋，P與Q都有相同的真值，則稱公式P和Q在D上是等價的。如果D是任意個體域，則稱P和Q是等價的，記為P

Q

。常用的等價式見P32（4）德.摩根律(De.Morgen)（8）連接詞化規(guī)律（蘊含、等價等值式）

（10）量詞轉(zhuǎn)換律

3.2自然演繹推理自然演繹推理：從一組已知為真的事實出發(fā)，運用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過程。28

定義2

對于謂詞公式P與Q，如果P→Q永真，則稱公式P永真蘊含Q，且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記為P

Q。常用的永真蘊含式見P33（3）假言推理

（4）拒取式推理

（5）假言三段論

3.2自然演繹推理29謂詞邏輯的其他推理規(guī)則1.P規(guī)則：在推理的任何步驟上都可引入前提。2.T規(guī)則：在推理過程中，如果前面步驟中有一個或多個公式永真蘊含公式S，則可把S引入推理過程中。3.CP規(guī)則：如果能從任意引入的命題R和前提集合中推出S來，則可從前提集合推出R→S來。3.2自然演繹推理30

所有的人都是會死的，因為諸葛亮是人，

Human（Zhugeliang）

所以諸葛亮是會死的。

Die（Zhugeliang）

{1}P規(guī)則

{2}Human（Zhugeliang）

P規(guī)則

{1,2}Die（Zhugeliang）

T規(guī)則

3.2自然演繹推理31謂詞邏輯的其他推理規(guī)則：4.反證法：P

Q

，當(dāng)且僅當(dāng)

P

Q

F，即Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)P

Q是不可滿足的。

定理：Q為P1,P2,…,Pn

的邏輯結(jié)論，當(dāng)且僅當(dāng)

P1

P2,

…

Pn

Q

是不可滿足的。3.2自然演繹推理推理規(guī)則：P規(guī)則、T規(guī)則、假言推理、拒取式推理

3.2自然演繹推理

假言推理：P,P→Q

Q

“如果x是金屬，則x能導(dǎo)電”

,“銅是金屬”推出“銅能導(dǎo)電”

拒取式推理：P→Q,﹁Q

﹁P“如果下雨，則地下就濕”,“地上不濕”推出“沒有下雨”（1）如果下雨，則地上是濕的（P→Q

）；（2）沒有下雨（﹁P

）；（3）所以，地上不濕（﹁Q

）。

3.2自然演繹推理錯誤1——否定前件：P→Q,﹁P﹁Q（1）如果行星系統(tǒng)是以太陽為中心的，則金星會顯示出位相變化（P→Q

）；（2）金星顯示出位相變化（

Q

）；（3）所以，行星系統(tǒng)是以太陽為中心（

P

）。

錯誤2——肯定后件：P→Q,Q

P3.2自然演繹推理

例1已知事實：

（1）凡是容易的課程小王(Wang)都喜歡；（2）C班的課程都是容易的；（3）ds是C班的一門課程。求證：小王喜歡ds這門課程。3.2自然演繹推理證明：定義謂詞：

EASY(x)：x

是容易的

LIKE(x,y)：x

喜歡y

C(x)：x是C

班的一門課程

已知事實和結(jié)論用謂詞公式表示：

(

x)(EASY(x)→LIKE(Wang,x))(

x)(C(x)→EASY(x))

C(ds)

LIKE(Wang,ds)

3.2自然演繹推理

應(yīng)用推理規(guī)則進行推理：

(

x)（EASY(x)→LIKE(Wang,x))

EASY(z)→LIKE(Wang,z)全稱固化

(

x)(C(x)

EASY(x))

C(y)

EASY(y)

全稱固化

所以

C(ds),C(y)

EASY(y)

EASY(ds)

P規(guī)則及假言推理

所以

EASY(ds),

EASY(z)

LIKE(Wang，z)

LIKE(Wang,ds)

T規(guī)則及假言推理優(yōu)點：表達定理證明過程自然，易理解。擁有豐富的推理規(guī)則，推理過程靈活。便于嵌入領(lǐng)域啟發(fā)式知識。3.2自然演繹推理缺點：易產(chǎn)生組合爆炸，得到的中間結(jié)論一般呈指數(shù)形式遞增。歸結(jié)演繹推理第3章確定性推理方法3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結(jié)原理3.6歸結(jié)反演3.7應(yīng)用歸結(jié)反演求解問題

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

原子（atom）謂詞公式：一個不能再分解的命題。文字（literal）：原子謂詞公式及其否定。：正文字，：負(fù)文字。（封閉世界假設(shè)）子句（clause）：任何文字的析取式。任何文字本身也都是子句?？兆泳洌∟IL）：不包含任何文字的子句。子句集：由子句構(gòu)成的集合?？兆泳涫怯兰俚?，不可滿足的。3.3謂詞公式化為子句集的方法

例2

將下列謂詞公式化為子句集。解：（1）消去謂詞公式中的“

”和“

”符號

（2）把否定符號””

移到緊靠謂詞的位置上雙重否定律

德.摩根律

量詞轉(zhuǎn)換律

（3）變量標(biāo)準(zhǔn)化

（4）消去存在量詞

a.

存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)。

b.

存在量詞出現(xiàn)在一個或者多個全稱量詞的轄域內(nèi)。Skolem化：用Skolem函數(shù)代替每個存在量詞量化的變量的過程。

（5）化為前束形

前束形=（前綴）{母式}（前綴）：全稱量詞串。

{母式}：不含量詞的謂詞公式。

3.3謂詞公式化為子句集的方法3.3謂詞公式化為子句集的方法（6）化為Skolem標(biāo)準(zhǔn)形

Skolem標(biāo)準(zhǔn)形：M：子句的合取式，稱為Skolem標(biāo)準(zhǔn)形的母式。

（7）略去全稱量詞

（8）消去合取詞

（9）子句變量標(biāo)準(zhǔn)化

3.3謂詞公式化為子句集的方法例3

將下列謂詞公式化為子句集。解：（1）消去蘊含符號（2）把否定符號移到每個謂詞前面（3）變量標(biāo)準(zhǔn)化（4）消去存在量詞，例3

將下列謂詞公式化為子句集。（續(xù)）（5）化為前束形(沒變化)

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

（7）略去全稱量詞

（8）消去合取詞，把母式用子句集表示

（9）子句變量標(biāo)準(zhǔn)化

3.3謂詞公式化為子句集的方法3.3謂詞公式化為子句集的方法練習(xí):

將下列謂詞公式化為子句集。解：（1）消去蘊含符號（2）把否定符號移到每個謂詞前面（3）變量標(biāo)準(zhǔn)化（4）消去存在量詞，例3

將下列謂詞公式化為子句集。（續(xù)）（5）化為前束形

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

（7）略去全稱量詞

（8）消去合取詞，把母式用子句集表示

（9）子句變量標(biāo)準(zhǔn)化

3.3謂詞公式化為子句集的方法歸結(jié)演繹推理第3章確定性推理方法3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結(jié)原理3.6歸結(jié)反演3.7應(yīng)用歸結(jié)反演求解問題

定理：P

Q當(dāng)且僅當(dāng)P

Q

F即Q為P

的邏輯結(jié)論，當(dāng)且僅當(dāng)P

Q是不可滿足的。定理：Q為，，…，的邏輯結(jié)論，當(dāng)且僅當(dāng)是不可滿足的。3.5魯賓遜歸結(jié)原理定理:

謂詞公式不可滿足的充要條件是其子句集不可滿足。謂詞公式不可滿足性子句集不可滿足性？3.5魯賓遜歸結(jié)原理思路：定理不可滿足

子句集不可滿足