第三章知識處理

1、第三章 問題求解問題推理：在知識表達(dá)的基礎(chǔ)上，進(jìn)行機(jī)器思維，求解問題。是知識利用的基礎(chǔ)。推理技術(shù)：問題求解（從初始狀態(tài)到目標(biāo)狀態(tài)）的方法和途徑。與知識表達(dá)技術(shù)密切相關(guān)。圖搜索方法：基于圖的知識表達(dá)。從圖中相當(dāng)于初始狀態(tài)的出發(fā)到相當(dāng)于目標(biāo)狀態(tài)的終止節(jié)點(diǎn)的路線搜索過程。廣度優(yōu)先搜索，深度優(yōu)先搜索.邏輯論證法：基于謂詞邏輯或其他形式邏輯方法的知識表達(dá)。不確定性推理非單調(diào)推理推理方法：是否完備：推理算法：推理過程完備，能找到解。推理步驟：推理過程不完備，不一定能求解問題的解。是否加入啟發(fā)性知識：啟發(fā)推理：在推理過程中，運(yùn)用與問題有關(guān)的啟發(fā)性知識，即解決問題的策略、技巧、竅門，對解的特性及規(guī)律的估計(jì)等實(shí)

2、踐經(jīng)驗(yàn)和知識，加快推理過程，提高搜索效率； 非啟發(fā)推理：在問題求解的推理過程中，不運(yùn)用啟發(fā)性知識，只按一般的邏輯法則或控制性知識，進(jìn)行通用性的推理。3.1 一般搜索原理一 一般性圖搜索策略1 圖搜索：在圖中尋求從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。2 盲目搜索：無信息搜索，非啟發(fā)性搜索。3 搜索策略：（1）相關(guān)數(shù)據(jù)結(jié)構(gòu)及概念：OPEN表：用于存放剛生成的節(jié)點(diǎn)；CLOSED表：用于存放將要擴(kuò)展或已擴(kuò)展的節(jié)點(diǎn)；擴(kuò)展：用定義的算子或算符對節(jié)點(diǎn)進(jìn)行操作，生成子節(jié)點(diǎn)；指針：用以記錄子節(jié)點(diǎn)被擴(kuò)展的路徑，反向指向父節(jié)點(diǎn)；搜索圖：通過搜索所得的圖；搜索樹：由搜索圖中所有節(jié)點(diǎn)及反向指針?biāo)鶚?gòu)成的集合。（2）一般性圖搜索策略

3、開始OPEN空？OPEN表的第一個(gè)節(jié)點(diǎn)n從表中移出，放入CLOSED表n為目標(biāo)節(jié)點(diǎn)？N可擴(kuò)展？擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表，并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針失敗，退出成功，退出S0移入OPEN表YNYYNN不同的搜索方法不同在于：后繼節(jié)點(diǎn)不同的擴(kuò)充方式，對應(yīng)OPEN表不同的排列順序。n寬度優(yōu)先搜索搜索按層進(jìn)行，在對下一層節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。1234567擴(kuò)展出來的子節(jié)點(diǎn)放在OPEN表的尾部OPEN表 CLOSED表(1) (2)(3) (1) (3)(4)(5) (1)(2) (4)(5)(6)(7) (1)(2)(3)三 深度優(yōu)先搜索搜索按深度進(jìn)行，首先擴(kuò)展最新

4、產(chǎn)生的節(jié)點(diǎn)。OPEN表 CLOSED表 (1) (2)(3) (1) (4)(5)(3) (1)(2) (5)(3) (1)(2)(4)1234567擴(kuò)展出來的子節(jié)點(diǎn)放在OPEN表的頭部有界深度優(yōu)先搜索:深度優(yōu)先搜索不完備,可能陷入無限分支中,引入搜索深度界限。四 代價(jià)樹搜索1 代價(jià)樹：將搜索擴(kuò)展的代價(jià)考慮進(jìn)入。2 代價(jià)樹的廣度優(yōu)先搜索：總選擇代價(jià)最小的節(jié)點(diǎn)為待擴(kuò)展節(jié)點(diǎn)。3 代價(jià)樹的深度優(yōu)先搜索：從剛擴(kuò)展的子節(jié)點(diǎn)中選擇代價(jià)最小的為待擴(kuò)展節(jié)點(diǎn)。例：如圖五城市間的交通路線圖，A是出發(fā)地，E是目的地，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從A到E的最小費(fèi)用的交通路線。ABCDE432453AC

5、1B1D1E2B2D2E1C2E3E434234545233.2 啟發(fā)式搜索一 思想找到一種有效的方法處理節(jié)點(diǎn)（排列待擴(kuò)展節(jié)點(diǎn)），利用問題本身的特性進(jìn)行擴(kuò)展，提高搜索效率。有信息搜索。有序搜索：選擇最有希望的節(jié)點(diǎn)作為待擴(kuò)展節(jié)點(diǎn)。通過定義某一衡量標(biāo)準(zhǔn)決定希望程度。n估價(jià)函數(shù)估算節(jié)點(diǎn)希望的量度。一般形式為：f (x) = g (x) + h (x)f 為估價(jià)函數(shù)，f (x)表示節(jié)點(diǎn)x的估價(jià)函數(shù)值。g (x)表示從初始節(jié)點(diǎn)到x已實(shí)際付出的代價(jià)；h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)，利用問題本身的信息進(jìn)行估價(jià)。寬度優(yōu)先：深度小者優(yōu)先；深度優(yōu)先：深度深者優(yōu)先；代價(jià)優(yōu)先：代價(jià)小者優(yōu)先。局部擇優(yōu)搜索（深度

6、）：對新擴(kuò)展的節(jié)點(diǎn)按代價(jià)大小重排；全局擇優(yōu)搜索（廣度）：對OPEN表中所有節(jié)點(diǎn)按代價(jià)大小重排。對于f的選擇，沒有適用的準(zhǔn)確的希望量度，則：（1）時(shí)間和空間之間的折衷；（2）保證有一個(gè)最優(yōu)解或任意解。解的三種情況：（1）求得最優(yōu)（最小代價(jià)）解答；（2）適當(dāng)?shù)乃阉髡业胶玫?，而非最?yōu)。但優(yōu)與最優(yōu)很難界定。（3）找到一個(gè)解即可。2 8 31 6 47 51 2 38 47 6 5例：八數(shù)碼棋，定義估價(jià)函數(shù)：f (n) = d(n) + w(n)d(n) 為搜索樹中節(jié)點(diǎn)n的深度；w(n)用以計(jì)算節(jié)點(diǎn)n對應(yīng)于目標(biāo)狀態(tài)錯(cuò)放的棋子數(shù)。2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7

7、 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)1234561 2 38 47 6 5nA*算法A*算法：選擇一個(gè)特定的估價(jià)函數(shù)f(n)，定義為通過節(jié)點(diǎn)n的一條最小代價(jià)路徑的代價(jià)的一個(gè)估計(jì)。先定義： f *(n) = g *(n)

8、 + h *(n),其中： g *(n) 為從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的一條最優(yōu)路徑的代價(jià)； h *(n)為從n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)。定義估價(jià)函數(shù)： f (n) = g (n) + h (n)其中g(shù)是對g*的估計(jì)，h是對h*的估計(jì)。g(n)可以是實(shí)際值，而h(n)則依賴有關(guān)問題的領(lǐng)域的啟發(fā)信息，h叫啟發(fā)函數(shù)。A*算法定義：（1）估價(jià)函數(shù)依據(jù)f (x) = g (x) + h (x)進(jìn)行；（2）h(x)=h*(x), h(x)為h*(x)的下界；（3）利用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，為A*算法。A*算法的一些特性：（1） A*算法能在有限步內(nèi)終止，并能找到最優(yōu)解；（2）在滿足h(

9、x)=h*(x)的前提下，h(x)的值越大越好。 f 1(x) = g 1(x) + h 1(x) f 2(x) = g 2(x) + h 2(x) A1* ， A2*分別是以f 1(x) ，f 2(x) 為估價(jià)函數(shù)的A*算法，且對所有的非目標(biāo)節(jié)點(diǎn)有h 1(x)=深度界限，則標(biāo)示節(jié)點(diǎn)n為不可解節(jié)點(diǎn)。四 與或樹的有序搜索依據(jù)代價(jià)決定搜索路線。1 代價(jià)計(jì)算（1）x為終葉節(jié)點(diǎn)，h(x) = 0;（2）x不可擴(kuò)展，且為非終葉節(jié)點(diǎn)h(x) = （3）x后繼節(jié)點(diǎn)（y1,y2,yn)為或邏輯, 則h(x) =minc (x,yi)+h(yi) （4）x后繼節(jié)點(diǎn)（y1,y2,yn)為與邏輯，則h(x) = (

10、 c (x,yi)+h(yi)或h(x) = maxc (x,yi)+h(yi) ABCDEFGHI J L NM 222224311311最大法： h左（A)=6 h右（A)=7求和法： h左（A)=9 h右（A)=82 希望樹最優(yōu)解樹：代價(jià)最小的解樹。希望樹T：在擴(kuò)展搜索求解中，有可能成為最優(yōu)解樹一部分的待擴(kuò)展樹，當(dāng)前代價(jià)最小的解樹。T包含： （1）初始節(jié)點(diǎn)； （2）節(jié)點(diǎn)x在T中，其或后繼節(jié)點(diǎn)中代價(jià)值最小的節(jié)點(diǎn)也在T中； （3）節(jié)點(diǎn)x在T中，其所有與后繼節(jié)點(diǎn)也在T中；3 有序搜索過程（1）找到希望樹T；（2）擴(kuò)展其端節(jié)點(diǎn)n，n為可解節(jié)點(diǎn)，進(jìn)行可解標(biāo)識；不可解，則進(jìn)行不可解標(biāo)識；（3）重新計(jì)

11、算代價(jià)，回到（1）。ABCDEFG1111113332HIJKLM1111113222h左（A）=9*h右（A）=8h（A）=8h(F) = 7h(C) = 11*h左（A）=9*h右（A）=12h（A）=9五 博弈樹的啟發(fā)式搜索1 博弈：智能性的競爭活動(dòng)?！岸肆愫?，非偶然，全信息”二人零和：得分函數(shù)之和為零，三種結(jié)局，我勝、我敗、平局；非偶然：雙方皆可根據(jù)全信息進(jìn)行分析，選取勝數(shù)最大的方案；全信息：當(dāng)前格局及過去，雙方皆知。2 博弈樹：描述此類過程的與或樹（始終站在某一方的立場上）（1）初始格局：初始節(jié)點(diǎn)；（2）與或節(jié)點(diǎn)交替出現(xiàn)；（3）我方擴(kuò)展節(jié)點(diǎn)-或關(guān)系（可選擇一個(gè)值大的）敵方擴(kuò)展節(jié)點(diǎn)-

12、與關(guān)系（對方可能選擇對我方最不利的方案）雙方輪流；（4）使我方獲勝的節(jié)點(diǎn)：終葉節(jié)點(diǎn)，可解節(jié)點(diǎn)；使隊(duì)方獲勝的節(jié)點(diǎn)：不可解節(jié)點(diǎn)。選出對自己最為有利的方案（樹）。3 極大極小分析法基本思想：預(yù)先生成一定深度博弈樹；定義估價(jià)函數(shù)，計(jì)算端節(jié)點(diǎn)的值（得分），靜態(tài)估值，再（倒推）計(jì)算出父節(jié)點(diǎn)的倒推值；根據(jù)值選定合適的分支擴(kuò)展一定的深度。例：一字棋。A、B對弈，先使自己的棋子成一線者為勝。A方：我方，先走。定義估價(jià)函數(shù)：e(p) = 棋局P上A方有可能成一線的數(shù)目棋局P上B方有可能成一線的數(shù)目A必勝的棋局P,e (P)= +；A必負(fù)的棋局P,e (P)= ；每次擴(kuò)展兩步。baaaababababa baba

13、bababaabab101-10-1-1-20012-1-2114 - 剪枝技術(shù)基本思想：根據(jù)倒推值的計(jì)算方法，或中取大，與中取小，在擴(kuò)展和計(jì)算過程中，能剪掉不必要的分枝，提高效率。定義： 值：有或后繼的節(jié)點(diǎn)，取當(dāng)前子節(jié)點(diǎn)中的最大倒推值為其下界，稱為值。節(jié)點(diǎn)倒推值= ； 值：有與后繼的節(jié)點(diǎn)，取當(dāng)前子節(jié)點(diǎn)中的最小倒推值為其上界，稱為值。節(jié)點(diǎn)倒推值Q PQ （2）減少否定的轄域： P Q (PQ) P Q (P Q) ( P ) P x ( P ) (x)P (x) ( P ) (x )P （3）變量標(biāo)準(zhǔn)化：使不同變量約束的變元具有不同的名字； x (P(x) ) x (Q(x) x (P(x)

14、) y(Q(y)（4）消去存在量詞：兩種情況： a) 若存在量詞不在任何全稱量詞的轄域內(nèi)，則化為一常量； x (Q(x)- Q (A) b)出現(xiàn)在某一全稱量詞內(nèi)，以斯克林函數(shù)代替每個(gè)出現(xiàn)的存在量詞的量化變量，函數(shù)中的變量由那些全稱量詞所約束的全稱量詞量化： y (x P(x, y) ) - y ( P(g(y), y) ) (5) 化為前束形，即將全稱量詞移到前面：前束形 = （前綴） （母式） 全稱量詞串 無量詞公式(6) 將母式化為合取范式，重新分配：P （Q W） （P Q） （P W）(7) 消去全稱量詞；(8) 消去合??；P1 P2 Pn - P1 , P2, , Pn(9) 更換變

15、量名稱，使不同的子句中變量不同名。以上所得即為子句形式。例： (x) P(x) (y) P(y) P( f (x, y) (y)Q(x,y) P(y) 消去蘊(yùn)涵：(x) P(x) (y) P(y) P( f (x, y) (y) Q(x,y) P(y) 減少否定轄域：(x) P(x) (y) P(y) P( f (x, y) (y )Q(x,y) P(y) 變量：(x) P(x) (y) P(y) P( f (x, y) (w)Q(x,w) P(w) 存在量詞：(x) P(x) (y) P(y) P( f (x, y) Q(x,g(x) P(g(x) 全稱量詞：(x) (y) P(x) P(y

16、) P( f (x, y) Q(x,g(x) P(g(x) 消去合取：(x) (y) P(x) P(y) P( f (x, y) P(x) （ Q(x,g(x) P(g(x) (x) (y) P(x) P(y) P( f (x, y) P(x) Q(x,g(x) P(x) P(g(x) 更換變量名，變?yōu)樽泳湫问剑?P (x1) P (y1) P ( f (x1, y1) P (x2) Q(x2,g (x2) ) P (x3) P(g (x3) ) 四 歸結(jié)演繹推理1 歸結(jié)：命題：C1、C2是子句集S中的任兩子句，C1中文字L1與C2中文字L2互補(bǔ)（L1， L1），從C1，C2中分別消去L1，L

17、2，剩下的部分析取，構(gòu)成新子句C12，此過程稱為歸結(jié)。C1：L1 L2C2： L1 L3C12：L2 L3謂詞邏輯：C1,C2是兩個(gè)沒有相同變元的子句，L1，L2分別為C1，C2中的文字，若 是L1， L2的最一般合一，則：C12=（C1 -L1 （C2 -L2 ）為C1，C2的二元?dú)w結(jié)式。例：C1=P(a) Q(x) R(x)C2= P(y) Q(b) C12 = Q(x) R(x) Q(b) = a / yC12= P(a) R(b) P(y) = b / x2 歸結(jié)原理定理：（1）C1、C2是子句集S中的兩子句，C12是其歸結(jié)式，若將C12加入S中，得到新子句集S2，S與S2在不可滿足的

18、意義上等價(jià)：S2的不可滿足性 S的不可滿足性（2） C1、C2是子句集S中的兩子句，C12是其歸結(jié)式，若用C12代替C1和C2后得到新子句集S1，則：S1不可滿足性 S不可滿足性3 歸結(jié)反演方法將永真性的證明轉(zhuǎn)化為不可滿足性：將P Q轉(zhuǎn)化為 P Q不可滿足。（永真：如果謂詞公式P對個(gè)體域D上的任何一個(gè)解釋都取得真值T，則稱P在D上是永真的； 不可滿足：若P對D上的任何一個(gè)解釋都為假，則P在D上是永假的。）對于一階謂詞邏輯，若子句集是不可滿足的，則必存在一個(gè)從該子句集到空子句集的歸結(jié)演繹；若從子句集存在一個(gè)到空子句集的演繹，則該子句集是不可滿足的。4 歸結(jié)反演證明 a) 基本過程：已知：條件公式

19、集P，求證：目標(biāo)公式L將P化為子句集S；否定L為L，化為子句集L；將L添加到S中，得到子句集S；對S做歸結(jié)過程，每次得到的歸結(jié)式并入S中，反復(fù)直至推出一個(gè)空子句。b) 例：某公司招聘工作人員，A、B、C三人應(yīng)試，經(jīng)面試后，決定： （1）三人中至少錄取一人； （2）若錄取A而不錄取B，則一定錄取C； （3）若錄取B，則一定錄取C；則公司一定錄取C。解：定義謂詞邏輯來表達(dá)問題。P(x)：表示公司錄取C，則用謂詞公式來表達(dá)問題和結(jié)論：（1）P(A) P(B) P(C)（2）P(A) P(B) P(C)（3）P(B) P(C)L：P(C)化為子句集的形式：（1） P(A) P(B) P(C)（2） P

20、(A) P(B) P(C)（3） P(B) P(C)（4） P(C)進(jìn)行歸結(jié)過程： （5） P(B) （3）（4）（6） P(A) P(C)（2）（5）（7） P(B) P(C)（1）（6）（8）P (C)（3）（7）（9）NIL（4）（8） P(B) P(C) P(C) P(A) P(B) P(C)P(B) P(A) P(C)P(A) P(B) P(C)P(B) P(C) P(B) P(C)P(C) P(C)NIL歸結(jié)樹5 歸結(jié)反演求解 a) 基本過程 已知：條件公式集P，求解：目標(biāo)公式L將P化為子句集S；否定L為L，將L Answer化為子句集S（Answer中的變元與L中的變元一致） ；

21、將L添加到S中，得到子句集S；對S做歸結(jié)過程，每次得到的歸結(jié)式并入S中，反復(fù)直至歸結(jié)出歸結(jié)式Answer。L Answer：目標(biāo)公式和目標(biāo)公式的否定，重言式。b) 例： 已知： （1）王是李的老師； （2）李和張是同班同學(xué)； （3）若X與Y是同班同學(xué)，則X的老師也是Y的老師； 求：張的老師是誰？解：定義謂詞邏輯表達(dá)問題：T(x , y): x是y的老師；C(x , y): x與y是同班同學(xué)；（1）T(wang, li)（2）C(li, zhang)（3） C(x, y) T(z , x)T(z , y)（4）T(u, zhang)化為子句形式，并變換目標(biāo)子句：（1）T(wang, li)（2）

22、C(li, zhang)（3） C(x, y) T(z , x) T(z , y)（4） T(u, zhang) Answer(u)進(jìn)行歸結(jié)過程：（5） C(li, y) T(wang , y) (1) (3) (wang/z,li/x)（6） C(li, zhang) Answer(wang)(4) (5) (wang/u, zhang/y)（7）Anwser (wang) (2) (6)歸結(jié)出的歸結(jié)式Answer中包含問題的解答，為：王是張的老師。T(wang, li) C(x, y) T(z , x) T(z , y) T(u, zhang) Answer(u) C(li, y) T(w

23、ang , y) C(li, zhang) Answer(wang)C(li, zhang)Answer(wang)wang/z,li/xwang/u, zhang/ywang/u, zhang/y歸結(jié)樹6 歸結(jié)策略 a) 歸結(jié)一般過程：從初試子句集開始，每兩個(gè)子句間進(jìn)行比較和歸結(jié)；產(chǎn)生的歸結(jié)式加入原子句集中，與原來子句及新的子句間兩兩比較歸結(jié)；如此一級一級，直到產(chǎn)生空子句。缺點(diǎn)：效率不高，產(chǎn)生許多無用和重復(fù)的子句。b) 處理策略：（1）刪除策略：純文字，單一文字；重言式；包含刪除，（C1 C2,稱C1包含于C2，把子句集中包含的子句刪除，不影響子句集的不可滿足性）；（2）支持集策略（完備）：

24、每一次歸結(jié)時(shí)，親本子句（父子句）中至少應(yīng)有一個(gè)是由目標(biāo)公式的否定所得的子句或是其后繼。（3）線性輸入（不完備）：參加歸結(jié)的兩子句必須至少一個(gè)是初始子句中的一個(gè)；（4）單文字子句（不完備）參加歸結(jié)的兩個(gè)子句必須至少有一個(gè)是單文字子句；（5）祖先過濾形策略（完備）：參加歸結(jié)的兩子句滿足以下兩條件之一：C1、C2至少有一個(gè)為初始子句；一個(gè)是另一個(gè)的祖先。練習(xí)：設(shè)A，B，C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個(gè)問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個(gè)是說謊者”。求：誰說真話，誰說謊？某處被盜，五個(gè)偵察員去調(diào)查。研究

25、案情時(shí)，A說：“趙與錢中至少有一人作案”，B說：“錢與孫中至少有一個(gè)作案”，C說：“孫與李中至少有一人作案”，D說：“趙與孫中至少有一人與此案無關(guān)”，E說：“錢與李中至少有一人與此案無關(guān)”。如果這五個(gè)偵察員說的都可信，試用歸結(jié)演繹推理求出誰是盜竊犯。 3.7 與或形演繹推理已知事實(shí)、規(guī)則，求取目標(biāo)；正向推理：從事實(shí)或狀況向目標(biāo)或動(dòng)作進(jìn)行操作；逆向推理：從目標(biāo)向事實(shí)或狀況進(jìn)行操作。一 與或形正向推理1 事實(shí)表達(dá)式與或形變換在系統(tǒng)中，將事實(shí)轉(zhuǎn)化為與或形。步驟：（1）消去蘊(yùn)涵；（2）減少否定轄域；（3）量詞變換，存在量詞；（4）主要合取式的變量不同名；（5）刪去全稱量詞。例：x y Q(y, x)

26、(R(y) P(y) S(x, y) 變換為： Q(z, a) R(y) P(y) S(a, y) 2 與或圖表示事實(shí)表達(dá)式 （1）方法析?。河肒線連接符來分解析取式，連接到父輩節(jié)點(diǎn)；合?。簡尉€連接符連接到父輩節(jié)點(diǎn)上；性質(zhì)：讀取葉節(jié)點(diǎn)上的析取，可以構(gòu)成表達(dá)式的子句集。例：Q(z, a) R(y) P(y) S(x, y) Q(z, a) R(y) P(y) S(x, y) R(y) P(y) S(x, y) R(y) P(y)讀取子句：Q( z,a )S(x, y) R(y) S(x, y) P(y)3 與或圖的F規(guī)則變換 在正向推理中，把允許用作規(guī)則推理的公式類型限制為： L W 其中L是單

27、文字，W為與或形的公式，而且規(guī)則中都為全稱量化于整個(gè)蘊(yùn)涵式。F規(guī)則變換步驟：（1）消去蘊(yùn)涵；（2）減少否定轄域；（3）量詞變換，存在量詞；（4）刪去全稱量詞；（5）再轉(zhuǎn)換為蘊(yùn)涵的形式。目標(biāo)公式：轉(zhuǎn)換為子句的形式。推理過程：（1）將事實(shí)轉(zhuǎn)換成與或樹的形式；（2）將F規(guī)則運(yùn)用到與或樹上：將L與其能合一的葉節(jié)點(diǎn)相匹配，擴(kuò)展與或樹，將W作為新的節(jié)點(diǎn)擴(kuò)展；（3）重復(fù)（2），直到產(chǎn)生一個(gè)含有以目標(biāo)節(jié)點(diǎn)為終止節(jié)點(diǎn)的一致解圖。例： 已知事實(shí)： P(a) (Q (a) R(a) ) F規(guī)則：r1: P(x) S(x) r2: Q(y) N(y)求證： S(a) N(a) P(a) (Q (a) R(a) ) P

28、(a)Q (a) R(a) Q (a) R(a) S(a)N(a) P(x) a/xQ(y) a/y讀取子句：S(a) N(a)S(a) R(a) r1: P(x) S(x) r2: Q(y) N(y)例：公司招聘（1）P(A) P(B) P(C)（2）P(A) P(B) P(C) P(A) P(B) P(C) （3）P(B) P(C)P(A) P(B) P(C)P(A)P(B)P(C)P(A)P(B)P(C)P(B)P(C)P(B)P(C)二 與或形逆向推理1 目標(biāo)表達(dá)式的與或形與正向推理的事實(shí)變換類似，有一點(diǎn)區(qū)別：用斯柯林涵數(shù)消去存在量詞中的全稱量詞，并使各主要析取式具有不同變元。例：yx

29、 Q(y, x) (R(y) P(y) S(x, y) 變換為： Q(z, f(z) R(y) P(y) S(f(y), y) 2 目標(biāo)表達(dá)式與或圖表示合?。河肒線連接符來分解合取式，連接到父輩節(jié)點(diǎn)；析取：單線連接符連接到父輩節(jié)點(diǎn)上；性質(zhì)：讀取葉節(jié)點(diǎn)上的析取，可以構(gòu)成目標(biāo)表達(dá)式表達(dá)式的子句集。目標(biāo)表達(dá)式表達(dá)式的子句集：合取的析取式。Q(z, f(z) R(y) P(y) S(f(y), y) Q(z, f(z) R(y) P(y) S(f(y), y) R(y) P(y) S(f(y), y) R(y) P(y)讀取子句：Q( z,f(z) )S(f(y), y) R(y) S(f(y), y

30、) P(y)3 B規(guī)則的表示形式在逆向推理中，把允許用作規(guī)則推理的公式類型限制為： W L 其中L是單文字，W為與或形的公式。B規(guī)則變換步驟：（1）消去蘊(yùn)涵；（2）減少否定轄域；（3）量詞變換，全稱量詞；（4）刪去存在量詞；（5）再轉(zhuǎn)換為蘊(yùn)涵的形式。4 事實(shí)表達(dá)式 為文字的合取式，能單獨(dú)起作用。推理過程：（1）將目標(biāo)轉(zhuǎn)換成與或樹的形式；（2）將B規(guī)則運(yùn)用到與或樹上：將L與其能合一的葉節(jié)點(diǎn)相匹配，擴(kuò)展與或樹，將W作為新的節(jié)點(diǎn)擴(kuò)展；（3）重復(fù)（2），直到產(chǎn)生一個(gè)含有以事實(shí)節(jié)點(diǎn)為終止節(jié)點(diǎn)的一致解圖。例：同學(xué)老師問題。已知：（1）T(wang, li)（2）C(li, zhang)（3） C(x, y

31、) T(z , x)T(z , y)求證目標(biāo)：T(wang, zhang)T(wang,zhang)T(z,y)C(x, zhang)T(wang, x)C(Li, zhang)T(wang, Li)Wang/z,zhang/yLi/xLi/x三 雙向推理1 單向的局限性：正向：事實(shí)無限制，而目標(biāo)為文字析取組成的表達(dá)式；逆向：事實(shí)為文字合取組成的表達(dá)式，而目標(biāo)無限制。 雙向建立在以上二者結(jié)合的基礎(chǔ)之上，由表示事實(shí)和表示目標(biāo)的兩個(gè)與或圖結(jié)構(gòu)組成，這樣目標(biāo)和事實(shí)均不受限制。2 關(guān)鍵問題：終止條件的判定，即涉及到兩個(gè)圖結(jié)構(gòu)之間的適當(dāng)交接處。3 結(jié)束判定：CANCEL定義：設(shè)若（n , m）中有一個(gè)為

32、事實(shí)節(jié)點(diǎn)，另一個(gè)為目標(biāo)節(jié)點(diǎn)，且若(n, m )都由可以合一的文字標(biāo)記，或者n有K線連接符接至一個(gè)后繼節(jié)點(diǎn)集合Si，使得此集合中每個(gè)元Cancel（Si, m）都成立，那么稱這兩個(gè)節(jié)點(diǎn)n和m互相抵消即Cancel。事實(shí)圖的根節(jié)點(diǎn)和目標(biāo)圖的根節(jié)點(diǎn)可互相CANCEL時(shí)，即得一解。 P(f(y) R(f(y) S(y) Q(f(y), y) P(f(y) R(f(y) S(y) Q(f(y), y) R(f(y) S(y)Q(f(y), y) R(f(y) S(y) R(v) S(A) Q(v, A) Q(v, A) R(v) S(A) R(v) S(A)f(y)/vA/yf(y)/vA/y四 置換一

33、致性 在推理過程中，要求所用的置換具有一致性。 定義：設(shè)置換集合 =1， 2， n，其中i=ti1/xi1,tim/xim,置換為一致的充要條件為如下兩元組：T=t11,t12,t1m, t21, , t2m, .tnmX=x11,x12,x1m, x21, , x2m, .xnm可合一。例：（1） 1=x/y, 2=y/zT=x,yX=y,z（2） 1=a/x, 2=b/xT=a,bX=x,x3.8 不確定性推理n基本概念1 不確定推理：根據(jù)不確定的初始條件，運(yùn)用不確定性的知識，得到近似合理的不確定性結(jié)論的過程。2 基本問題（1）證據(jù)/條件不確定性：用戶提供，中間結(jié)論；（2）知識/規(guī)則不確定

34、性：條件和結(jié)論之間的一種關(guān)系，專家給出；（3）表示：一般以一定取值范圍表示-1,1；表示方法要直觀、表達(dá)充分、便于推理；（4）計(jì)算推理：不確定性推理模型選擇（數(shù)值、非數(shù)值；概率、模糊理論）；匹配；多個(gè)證據(jù)組合；傳遞算法?？尚哦确椒尚哦龋河靡员硎臼挛餅檎娴目上嘈懦潭?。可信度方法是結(jié)合概率論，基于可信度的不確定性表示方法。知識/規(guī)則的不確定性表示：IF E THEN H： E為條件，H為結(jié)論。CF（H，E）表示規(guī)則/知識的可信度-1，1，表示E為真時(shí)，對結(jié)論H為真的支持程度。再引入： MB（H，E）：表示因條件/證據(jù)E，使H為真的信任增長度； MD（H，E）：表示因條件/證據(jù)E，使H為真的不信任

35、增長度；有：（1） P(H/E) 0 ，E削弱H；（2） P(H/E) P (H)，則MD(H,E) = 0，MB(H,E) 0， E支持H ；（3） P(H/E)= P (H)，則MD(H,E) = 0，MB(H,E) = 0， E與H無關(guān)。 1 PH=1MB（H，E）= max P(H/E), P(H) P(H) 1 P(H)1 PH=0MD（H，E）= min P(H/E), P(H) P(H) P(H)定義：CF（H，E）=MB（H，E）MD（H，E）有：（1）CF（H，E）0，表示E以CF（H，E）的可信度支持H；（2）CF（H，E）0 (b) CF(H,E1)+CF(H,E2) +

36、CF(H,E1)*CF(H,E2) CF(H,E1),CF(H,E2)0 (c) CF(H,E1)+CF(H,E2) CF(H,E1),CF(H,E2)異號1 min|CF(H,E1)|, |CF(H, E2)|例：已知： rule1 ：if E1 then A with CF=0.9 rule2 ：if E2 then A with CF=0.7rule3 ：if E3 then A with CF= 0.8rule4 ：if E4 and E5 then E1 with CF=0.7 rule5 ：if E6 and (E7 or E8) then E2 with CF=1 CF(E3)=

37、0.3, CF(E4)=0.9, CF(E5)=0.6, CF(E6)=0.7, CF(E7)= 0.3, CF(E8)=0.3, 求CF（A）？解： （1）畫出對應(yīng)的與或圖。0.9AE1E2E3E4E5E6E7E8-0.30.80.70.60.310.70.90.7-0.8（2）根據(jù)CF模型進(jìn)行計(jì)算CF(E1) = min(CF(E4),CF(E5)*CF(r4) =0.6*0.7=0.42CF(A,E1)=CF(E1)*CF(r1)=0.42*0.9=0.378同理：CF(A,E2)=(0.7*1)*0.7=0.49CF(A,E3)=0.3*( 0.8)= 0.24CF(A,E1&E2)

38、= 0.49+0.378 0.49*0.378=0.68CF(A,E1&E2&E3)=(0.68 0.24)/1 0.24=0.583.9 非單調(diào)推理一 基本概念1 單調(diào)推理：已知為真的命題數(shù)目隨時(shí)間而增加，新的命題（真命題）不會導(dǎo)致前面已知為真或已被證明的命題無效。 基于以上特點(diǎn)的系統(tǒng)是單調(diào)的，有以下優(yōu)點(diǎn)：（1）當(dāng)加入新的命題時(shí)，不必檢查新命題與原有知識間的不相容性；（2）對每一個(gè)已證明的命題，不必保留一個(gè)命題表，不存在某些命題被取消的危險(xiǎn)。2 非單調(diào)推理：隨著時(shí)間的推移和推理的進(jìn)行，推出的結(jié)論或證明為真的命題并不單調(diào)增加。非單調(diào)性推理研究四個(gè)代表性的理論或系統(tǒng)：（1）賴特（Reiter)的

39、缺省理論；（2）麥克德莫特（MeDermott）的界限理論；（3） J.麥卡錫(MeCarthy)的界限理論；（4）多伊爾(Doyle)的正確性維持系統(tǒng)。非單調(diào)邏輯適合于如下幾種環(huán)境： （1）當(dāng)知識不完備時(shí)，不得不做出缺省的假設(shè)，但當(dāng)獲得更多的知識時(shí)，該缺省假設(shè)可能是不成立的； （2）當(dāng)情景發(fā)生變化時(shí)，原先的結(jié)論可能不再成立； （3）在問題求解時(shí)，有時(shí)需要作出臨時(shí)的假設(shè)，隨著問題的解決，這些假設(shè)可能不再成立。缺省推理1 知識工程涉及到的各種形式的缺省推理，即是在沒有證據(jù)可以證明A不存在的情況下，就承認(rèn)A的存在。2 缺乏信息時(shí)的幾種假設(shè)： （1）若X不知道，那么得結(jié)論Y； （2）若X不能被證明，

40、那么得結(jié)論Y； （3）若X不能在某個(gè)給定的時(shí)間被證明，那么得結(jié)論Y。非單調(diào)推理系統(tǒng)TMSTMS正確性維持系統(tǒng)是1979年由Doyle建立的，是一個(gè)已經(jīng)實(shí)現(xiàn)的非單調(diào)推理系統(tǒng)1 結(jié)點(diǎn)及狀態(tài)TMS中每個(gè)命題（規(guī)則）稱為結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)有IN或OUT兩種狀態(tài)：IN表示相信為真；OUT狀態(tài)表示不相信為真。支持表SL（Support-List justification)支持表證實(shí)的格式如下：命題/結(jié)點(diǎn)（SL（IN表）（OUT表）表示出結(jié)點(diǎn)對其它結(jié)點(diǎn)的依賴性。當(dāng)且僅當(dāng)IN表中每個(gè)結(jié)點(diǎn)為IN和OUT表中每個(gè)結(jié)點(diǎn)為OUT，證實(shí)才為有效的。SL為空，稱為前提證實(shí)，總為有效；具有非空IN表和非空OUT表的證實(shí)表達(dá)了一般的推理。條件證明證實(shí)CP ( Condition-Proof justification)其形式為