第三章 確定性推理方法

第3章確定性推理方法知識(shí)智能？知識(shí)

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

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

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

(deductivereasoning):一般→個(gè)別

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

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

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

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

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

結(jié)論

A

成立

B

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

2.

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

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

X：會(huì)飛3.1.2推理方式及其分類

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

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

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

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

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

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

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

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

r1：腦膜炎

r2：肺炎

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

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

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

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

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

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

……..

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

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

雙向推理：正向推理與逆向推理同時(shí)進(jìn)行，且在推理過(guò)程中的某一步驟上“碰頭”的一種推理。已知事實(shí)假設(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沖突消解策略

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

定義1

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

Q

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

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

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

定義2

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

Q。常用的永真蘊(yùn)含式見(jiàn)P33（3）假言推理

（4）拒取式推理

（5）假言三段論

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

所有的人都是會(huì)死的，因?yàn)橹T葛亮是人，

Human（Zhugeliang）

所以諸葛亮是會(huì)死的。

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“如果下雨，則地下就濕”,“地上不濕”推出“沒(méi)有下雨”（1）如果下雨，則地上是濕的（P→Q

）；（2）沒(méi)有下雨（﹁P

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

）。

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

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

Q

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

P

）。

錯(cuò)誤2——肯定后件：P→Q,Q

P3.2自然演繹推理

例1已知事實(shí)：

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

EASY(x)：x

是容易的

LIKE(x,y)：x

喜歡y

C(x)：x是C

班的一門課程

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

(

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

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

C(ds)

LIKE(Wang,ds)

3.2自然演繹推理

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

(

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)點(diǎn)：表達(dá)定理證明過(guò)程自然，易理解。擁有豐富的推理規(guī)則，推理過(guò)程靈活。便于嵌入領(lǐng)域啟發(fā)式知識(shí)。3.2自然演繹推理缺點(diǎn)：易產(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é)反演求解問(wèn)題

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

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

例2

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

”和“

”符號(hào)

（2）把否定符號(hào)””

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

德.摩根律

量詞轉(zhuǎn)換律

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

（4）消去存在量詞

a.

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

b.

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

（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）消去蘊(yùn)含符號(hào)（2）把否定符號(hào)移到每個(gè)謂詞前面（3）變量標(biāo)準(zhǔn)化（4）消去存在量詞，例3

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

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

（7）略去全稱量詞

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

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

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

將下列謂詞公式化為子句集。解：（1）消去蘊(yùn)含符號(hào)（2）把否定符號(hào)移到每個(gè)謂詞前面（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é)反演求解問(wèn)題

定理：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é)原理思路：定理不可滿足

子句集不可滿足