第三講 經(jīng)典邏輯推理

1、編輯ppt1第四章 經(jīng)典邏輯推理4.1 基本概念4.2 自然演繹推理4.3 歸結(jié)演繹推理4.4 與或形演繹推理編輯ppt2如何實(shí)現(xiàn)推理？邏輯方法是自動(dòng)證明中常用的方法如何進(jìn)行邏輯推理？推理的過(guò)程怎樣？怎么實(shí)現(xiàn)推理？編輯ppt3柯南的推理過(guò)程觀察結(jié)果n時(shí)鐘與分鐘重疊在一起n時(shí)間是六點(diǎn)半推理依據(jù)n正常的時(shí)鐘如果是六點(diǎn)半，那么時(shí)鐘與分鐘應(yīng)該是分開(kāi)的推理結(jié)果n有人故意移動(dòng)過(guò)時(shí)鐘人類(lèi)的推理可以理解語(yǔ)義人類(lèi)的推理可以理解語(yǔ)義機(jī)器如何進(jìn)行這樣類(lèi)似的推理？機(jī)器如何進(jìn)行這樣類(lèi)似的推理？需要將推理的過(guò)程和理解分開(kāi)，使其形式化需要將推理的過(guò)程和理解分開(kāi)，使其形式化w事實(shí)事實(shí)w規(guī)則規(guī)則w結(jié)論結(jié)論編輯ppt4推理的一般

2、形式已知事實(shí)：事實(shí)1，事實(shí)2，. 規(guī)則：如果 事實(shí)1 那么 結(jié)論1 如果 事實(shí)2 那么 結(jié)論2 .得到：結(jié)論1，結(jié)論2 將事實(shí)與規(guī)則借助一些符號(hào)符號(hào)來(lái)表示，推理過(guò)程就可以被形式化 P: 某已知事實(shí) P Q : 如果P，那么Q 結(jié)論：Q編輯ppt5符號(hào)與形式語(yǔ)言自然語(yǔ)言不適合計(jì)算機(jī)處理n她用紅紅色水彩筆寫(xiě)了個(gè)藍(lán)藍(lán)字。n小王不方便接電話，他方便去了。需要一種無(wú)歧義，方便存儲(chǔ)和表達(dá)的形式化符號(hào)表征體系n數(shù)理邏輯編輯ppt6符號(hào)與形式語(yǔ)言自然語(yǔ)言不適合計(jì)算機(jī)處理n她用紅紅色水彩筆寫(xiě)了個(gè)藍(lán)藍(lán)字。n小王不方便接電話，他方便去了。需要一種無(wú)歧義，方便存儲(chǔ)和表達(dá)的形式化符號(hào)表征體系n數(shù)理邏輯w命題邏輯w謂詞邏

3、輯編輯ppt7符號(hào)與形式語(yǔ)言自然語(yǔ)言不適合計(jì)算機(jī)處理n她用紅紅色水彩筆寫(xiě)了個(gè)藍(lán)藍(lán)字。n小王不方便接電話，他方便去了。需要一種無(wú)歧義，方便存儲(chǔ)和表達(dá)的形式化符號(hào)表征體系n數(shù)理邏輯w命題邏輯w謂詞邏輯 w如果不下雨，我就去你家玩P Q w今天沒(méi)有下雨 P w我去了你家 Qw凡人都會(huì)死 x(Man(x)Mortal(x)w 蘇格拉底是人 Man(Socrates)w 蘇格拉底會(huì)死 Mortal(Socrates)編輯ppt84.1 基本概念4.1.1 什么是推理什么是推理所謂推理就是按某種策略由已知判斷推所謂推理就是按某種策略由已知判斷推出另一個(gè)判斷的思維過(guò)程。出另一個(gè)判斷的思維過(guò)程。在人工智能中，

4、推理是由程序?qū)崿F(xiàn)的，在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱(chēng)為推理機(jī)。稱(chēng)為推理機(jī)。編輯ppt94.1.2 推理方式及其分類(lèi)1. 演繹推理、歸納推理、默認(rèn)推理演繹推理、歸納推理、默認(rèn)推理演繹推理：從一般到特殊。例如三段論。演繹推理：從一般到特殊。例如三段論。歸納推理：從個(gè)體到一般。歸納推理：從個(gè)體到一般。默認(rèn)推理：缺省推理，在知識(shí)不完全的情況下假設(shè)某默認(rèn)推理：缺省推理，在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。些條件已經(jīng)具備所進(jìn)行的推理。2. 確定性、不確定性推理確定性、不確定性推理3. 單調(diào)推理、非單調(diào)推理單調(diào)推理、非單調(diào)推理推出的結(jié)論是否單調(diào)增加推出的結(jié)論是否單調(diào)增加4. 啟發(fā)式、非

5、啟發(fā)式推理啟發(fā)式、非啟發(fā)式推理所謂啟發(fā)性知識(shí)是指與問(wèn)題有關(guān)且能加快推理進(jìn)程、所謂啟發(fā)性知識(shí)是指與問(wèn)題有關(guān)且能加快推理進(jìn)程、求得問(wèn)題最優(yōu)解的知識(shí)。求得問(wèn)題最優(yōu)解的知識(shí)。5. 基于知識(shí)的推理（專(zhuān)家系統(tǒng)）基于知識(shí)的推理（專(zhuān)家系統(tǒng)） 、統(tǒng)計(jì)推理、直覺(jué)推理、統(tǒng)計(jì)推理、直覺(jué)推理（常識(shí)性推理）（常識(shí)性推理）編輯ppt104.1.3 推理的控制策略推理的控制策略主要包括：推理方向、搜索策略、沖推理的控制策略主要包括：推理方向、搜索策略、沖突消解策略、求解策略及限制策略。突消解策略、求解策略及限制策略。1. 正向推理（數(shù)據(jù)驅(qū)動(dòng)推理）正向推理（數(shù)據(jù)驅(qū)動(dòng)推理）正向推理的基本思想是：從用戶提供的初始已知事實(shí)正向推理的

6、基本思想是：從用戶提供的初始已知事實(shí)出發(fā)，在知識(shí)庫(kù)出發(fā)，在知識(shí)庫(kù)KB中找出當(dāng)前可適用的知識(shí)，構(gòu)成可中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用的知識(shí)集適用的知識(shí)集KS，然后按某種沖突消解策略從，然后按某種沖突消解策略從KS中選中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入到數(shù)據(jù)出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入到數(shù)據(jù)庫(kù)庫(kù)DB中，作為下一步推理的已知事實(shí)。在此之后，再中，作為下一步推理的已知事實(shí)。在此之后，再在知識(shí)庫(kù)中選取可適用的知識(shí)進(jìn)行推理。如此重復(fù)進(jìn)在知識(shí)庫(kù)中選取可適用的知識(shí)進(jìn)行推理。如此重復(fù)進(jìn)行這一過(guò)程，直到求得所要求的解。行這一過(guò)程，直到求得所要求的解。編輯ppt11正向推理示意圖開(kāi)始退出把初

7、始已知事實(shí)送入DBDB中包含問(wèn)題的解？KB中有可適用的知識(shí)？把KB中所有使用知識(shí)都選出來(lái)送入KSKS為空？按沖突消解策略從KS中選出一條知識(shí)進(jìn)行推理推出的是新事實(shí)？將該新事實(shí)加入DB中用戶可補(bǔ)充新事實(shí)？把用戶提供的新事實(shí)加入DB中YNNYNYNYNY成功失敗編輯ppt12 動(dòng)物識(shí)別的例子w已知事實(shí)：一動(dòng)物已知事實(shí)：一動(dòng)物有毛，吃草，黑條紋有毛，吃草，黑條紋nR1：動(dòng)物有毛：動(dòng)物有毛 哺乳類(lèi)哺乳類(lèi) nR2：動(dòng)物產(chǎn)奶：動(dòng)物產(chǎn)奶 哺乳類(lèi)哺乳類(lèi) nR3：哺乳類(lèi)：哺乳類(lèi) 吃肉吃肉 食肉類(lèi)食肉類(lèi) nR4：哺乳類(lèi)：哺乳類(lèi) 吃草吃草 有蹄類(lèi)有蹄類(lèi) nR5：食肉類(lèi)：食肉類(lèi) 黃褐色黃褐色 有斑點(diǎn)有斑點(diǎn) 獵狗獵狗

8、nR6：食肉類(lèi)：食肉類(lèi) 黃褐色黃褐色 黑條紋黑條紋 虎虎 nR7：有蹄類(lèi)：有蹄類(lèi) 長(zhǎng)脖長(zhǎng)脖 長(zhǎng)頸鹿長(zhǎng)頸鹿 nR8：有蹄類(lèi)：有蹄類(lèi) 黑條紋黑條紋 斑馬斑馬編輯ppt132 逆向推理逆向推理的基本思想是：首先選定一個(gè)逆向推理的基本思想是：首先選定一個(gè)假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說(shuō)明原假設(shè)若所需的證據(jù)都能找到，則說(shuō)明原假設(shè)是成立的；若找不到所需要的證據(jù)，則是成立的；若找不到所需要的證據(jù)，則說(shuō)明原假設(shè)不成立，此時(shí)需要另作新的說(shuō)明原假設(shè)不成立，此時(shí)需要另作新的假設(shè)。假設(shè)。編輯ppt14逆向推理示意圖開(kāi)始退出提出假設(shè)該假設(shè)在DB中？該假設(shè)

9、是證據(jù)？在KB中找出所有能導(dǎo)出該假設(shè)的知識(shí)送入KS有此事實(shí)？該假設(shè)成立該假設(shè)成立，并將此事實(shí)存入數(shù)據(jù)庫(kù)YNYNNNY從KS中選出一條知識(shí)，并將該知識(shí)的一個(gè)運(yùn)用條件作為新的假設(shè)目標(biāo)還有假設(shè)？詢(xún)問(wèn)用戶Y編輯ppt15動(dòng)物識(shí)別系統(tǒng) r1： if 該動(dòng)物有毛發(fā)該動(dòng)物有毛發(fā) then 該動(dòng)物是哺乳動(dòng)物該動(dòng)物是哺乳動(dòng)物 r2： if 該動(dòng)物有奶該動(dòng)物有奶 then 該動(dòng)物是哺乳動(dòng)物該動(dòng)物是哺乳動(dòng)物 r3： if 該動(dòng)物有羽毛該動(dòng)物有羽毛 then 該動(dòng)物是鳥(niǎo)該動(dòng)物是鳥(niǎo) r4： if 該該動(dòng)物會(huì)飛動(dòng)物會(huì)飛 and 會(huì)下蛋會(huì)下蛋 then 該動(dòng)物是鳥(niǎo)該動(dòng)物是鳥(niǎo) r5： if 該動(dòng)物吃肉該動(dòng)物吃肉 then 該

10、動(dòng)物是食肉動(dòng)物該動(dòng)物是食肉動(dòng)物 r6： if 該動(dòng)物有犬齒該動(dòng)物有犬齒 and 有爪有爪 and 眼盯前方眼盯前方 then 該動(dòng)物是食肉動(dòng)物該動(dòng)物是食肉動(dòng)物 r7： if 該動(dòng)物是哺乳動(dòng)物該動(dòng)物是哺乳動(dòng)物 and 有蹄有蹄 then 該動(dòng)物是有蹄類(lèi)動(dòng)物該動(dòng)物是有蹄類(lèi)動(dòng)物 r8： if 該動(dòng)物是哺乳動(dòng)物該動(dòng)物是哺乳動(dòng)物 and 是嚼反芻類(lèi)動(dòng)物是嚼反芻類(lèi)動(dòng)物 then 該動(dòng)物是有蹄類(lèi)動(dòng)物該動(dòng)物是有蹄類(lèi)動(dòng)物編輯ppt16 r9： if 該動(dòng)物是哺乳動(dòng)物該動(dòng)物是哺乳動(dòng)物 and 是食肉類(lèi)動(dòng)物是食肉類(lèi)動(dòng)物 and 是黃褐色是黃褐色 and 身上有暗斑點(diǎn)身上有暗斑點(diǎn) then 該動(dòng)物是金錢(qián)豹該動(dòng)物是金錢(qián)

11、豹 r10： if 該動(dòng)物是哺乳動(dòng)物該動(dòng)物是哺乳動(dòng)物 and 是食肉類(lèi)動(dòng)物是食肉類(lèi)動(dòng)物 and 是黃褐色是黃褐色 and 身上有黑色條紋身上有黑色條紋 then 該動(dòng)物是虎該動(dòng)物是虎 r11： if 該動(dòng)物是有蹄類(lèi)動(dòng)物該動(dòng)物是有蹄類(lèi)動(dòng)物 and 有長(zhǎng)脖子有長(zhǎng)脖子 and 有長(zhǎng)腿有長(zhǎng)腿 and 身上有暗斑點(diǎn)身上有暗斑點(diǎn) then 該動(dòng)物是長(zhǎng)頸鹿該動(dòng)物是長(zhǎng)頸鹿 r12： if 該動(dòng)物是有蹄類(lèi)動(dòng)物該動(dòng)物是有蹄類(lèi)動(dòng)物 and 身上有黑色條紋身上有黑色條紋 then 該動(dòng)物是斑馬該動(dòng)物是斑馬編輯ppt17 r13： if 該動(dòng)物是鳥(niǎo)該動(dòng)物是鳥(niǎo) and 有長(zhǎng)脖子有長(zhǎng)脖子 and 有長(zhǎng)腿有長(zhǎng)腿 and 不會(huì)

12、飛不會(huì)飛 then 該動(dòng)物是鴕鳥(niǎo)該動(dòng)物是鴕鳥(niǎo) r14： if 該動(dòng)物是鳥(niǎo)該動(dòng)物是鳥(niǎo) and 會(huì)游泳會(huì)游泳 and 不會(huì)飛不會(huì)飛 and 有黑白兩色有黑白兩色 then 該動(dòng)物是企鵝該動(dòng)物是企鵝 r15： if 該動(dòng)物是鳥(niǎo)該動(dòng)物是鳥(niǎo) and 善飛善飛 then 該動(dòng)物是信天翁該動(dòng)物是信天翁編輯ppt183. 混合推理混合推理先正向推理后逆向推理先正向推理后逆向推理先逆向推理后正向推理先逆向推理后正向推理4. 雙向推理雙向推理正向推理與逆向推理同時(shí)進(jìn)行，且在推理過(guò)程正向推理與逆向推理同時(shí)進(jìn)行，且在推理過(guò)程中的某一步上中的某一步上“碰頭碰頭”。5. 求解策略求解策略只求一個(gè)解，還是求所有解以及最優(yōu)解

13、。只求一個(gè)解，還是求所有解以及最優(yōu)解。6. 限制策略限制策略限制搜索的深度、寬度、時(shí)間、空間等等。限制搜索的深度、寬度、時(shí)間、空間等等。編輯ppt19所謂模式匹配是指對(duì)兩個(gè)知識(shí)模式所謂模式匹配是指對(duì)兩個(gè)知識(shí)模式(例如兩個(gè)謂詞公例如兩個(gè)謂詞公式、框架片斷、語(yǔ)義網(wǎng)絡(luò)片斷式、框架片斷、語(yǔ)義網(wǎng)絡(luò)片斷)進(jìn)行比較，檢查這兩進(jìn)行比較，檢查這兩個(gè)知識(shí)模式是否完全一致或者近似一致。個(gè)知識(shí)模式是否完全一致或者近似一致。模式匹配可分為確定性匹配與不確定性匹配。模式匹配可分為確定性匹配與不確定性匹配。確定性匹配是指兩個(gè)知識(shí)模式完全一致，或者經(jīng)過(guò)確定性匹配是指兩個(gè)知識(shí)模式完全一致，或者經(jīng)過(guò)變量代換后變得完全一致。變量代

14、換后變得完全一致。 知識(shí)：知識(shí)：IF father(x,y) and man(y) THEN son(y,x) 事實(shí)：事實(shí)：father(李四，李小四李四，李小四) and man(李小四李小四)不確定性匹配是指兩個(gè)知識(shí)模式不完全一致，但是不確定性匹配是指兩個(gè)知識(shí)模式不完全一致，但是它們的相似程度又在規(guī)定的限度內(nèi)。它們的相似程度又在規(guī)定的限度內(nèi)。4.1.4 模式匹配編輯ppt20變量代換定義4.1 代換是一個(gè)形如t1/x1,t2/x2,tn/xn的有限集合。 其中t1,t2,tn是項(xiàng)（常量、變量、函數(shù)）； x1,x2,xn是（某一公式中）互不相同的變?cè)?ti/xi表示用ti代換xi 不允許t

15、i與xi相同，也不允許變?cè)獂i循環(huán)地出現(xiàn)在另一個(gè)tj中。例如：a/x,f(b)/y,w/z是一個(gè)代換g(y)/x,f(x)/y不是代換g(a)/x,f(x)/y是代換編輯ppt21令= t1/x1,t2/x2,tn/xn為一個(gè)代換，F(xiàn)為表達(dá)式，則F表示對(duì)F用ti代換xi后得到的表達(dá)式。F稱(chēng)為F的特例。 規(guī)則: IF father(x,y) and man(y) THEN son(y,x)事實(shí): father(李四，李小四) and man(李小四) F=father(x,y) man(y) = 李四/X,李小四/Y F= father(李四，李小四) man(李小四) 結(jié)論: son(李小四,

16、李四)編輯ppt22代換的復(fù)合定義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)yix1,x2,xn后剩下的元素所構(gòu)成的集合，記為 。注： ti表示對(duì)ti運(yùn)用進(jìn)行代換。就是對(duì)一個(gè)公式F先運(yùn)用進(jìn)行代換，然后再運(yùn)用進(jìn)行代換：F（ ）=（F ）編輯ppt23代換的例子例如，設(shè)有代換= f(y)/x,z/w= a/x,b/y,w/z則=f(y)/x, z/w, a/x, b/y, w/z=f

17、(b)/x, w/w, a/x, b/y, w/z=f(b)/x, b/y, w/z編輯ppt24公式集的合一定義4.3 設(shè)有公式集F=F1,F2,Fn，若存在一個(gè)代換使得F1=F2=Fn則稱(chēng)為公式集F的一個(gè)合一，且稱(chēng)F1,F2,Fn是可合一的。例如，設(shè)有公式集F=P(x,y,f(y),P(a,g(x),z)則下式是它的一個(gè)合一：=a/x,g(a)/y,f(g(a)/z一個(gè)公式集的合一一般不唯一。編輯ppt25 最一般的合一定義4.4 設(shè)是公式集F的一個(gè)合一，如果對(duì)任一個(gè)合一都存在一個(gè)代換，使得=則稱(chēng)是一個(gè)最一般的合一。（1）代換過(guò)程是一個(gè)用項(xiàng)代替變?cè)倪^(guò)程，因此是一個(gè)從一般到特殊的過(guò)程。（2

18、） 最一般合一是唯一的。編輯ppt26求取最一般合一差異集：兩個(gè)公式中相同位置處不同符號(hào)的集合。例如：F1:P(x,y,z), F2:P(x,f(a),h(b)則D1=y,f(a), D2=z,h(b)求取最一般合一的算法：令k=0,Fk=F, k=。 是空代換。若Fk只含一個(gè)表達(dá)式，則算法停止，k就是最一般合一。找出Fk的差異集Dk。若Dk中存在元素xk和tk，其中xk是變?cè)?，tk是項(xiàng)，且xk不在tk中出現(xiàn)，則置：Fk+1=Fktk/xkK+1=ktk/xkk=k+1然后轉(zhuǎn)(2)。若不存在這樣的xk和tk則算法停止。1.算法終止，F(xiàn)的最一般合一不存在。編輯ppt27求取最一般合一的例子例如，

19、設(shè) F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一。令F0=F, 0=。 F0中有兩個(gè)表達(dá)式，所以0不是最一般合一。差異集：D0=a,z。代換： a/zF1= F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u) 。 1=0a/z=a/zD1=x,f(a) 。代換： f(a)/xF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u) 。 2=1f(a)/x=a/z,f(a)/x D2=g(y),u 。代換： g(y)/uF3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y) 。 3=2g(y)/u

20、=a/z,f(a)/x,g(y)/u 編輯ppt284.1.5 沖突消解策略沖突：多個(gè)知識(shí)都匹配成功。正向推理：n多條產(chǎn)生式前件都與已知事實(shí)匹配成功逆向推理：n多條規(guī)則后件都和同一個(gè)假設(shè)匹配成功沖突消解的基本思想都是對(duì)知識(shí)進(jìn)行排序。編輯ppt29幾種沖突消解策略按針對(duì)性排序優(yōu)先選用針對(duì)性強(qiáng)的產(chǎn)生式規(guī)則。按已知事實(shí)的新鮮性排序優(yōu)先選用與較多新事實(shí)匹配的規(guī)則。按匹配度排序在不確定性匹配中，計(jì)算兩個(gè)知識(shí)模式的相似度(匹配度)，并對(duì)其排序，相似度高的規(guī)則先推。按領(lǐng)域問(wèn)題特點(diǎn)排序按上下文限制排序把規(guī)則按照下上文分組，并只能選取組中的規(guī)則。按冗余限制排序冗余知識(shí)越少的規(guī)則先推。按條件個(gè)數(shù)排序條件少的規(guī)則先

21、推。編輯ppt304.2 自然演繹推理從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過(guò)程，稱(chēng)為自然演繹推理。其中，基本的推理規(guī)則是P規(guī)則、T規(guī)則、假言推理、拒取式推理等。假言推理的一般形式拒取式推理的一般形式,P PQQ,PQQP 編輯ppt31P規(guī)則：在推理的任何步驟都可以引入前提。T規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或者多個(gè)公式永真蘊(yùn)含公式S，則可把S引入推理過(guò)程中。編輯ppt324.3 歸結(jié)演繹推理定理證明即證明PQ(PQ)的永真性。根據(jù)反證法，只要證明其否定(PQ) 不可滿足性即可。海伯倫(Herbrand)定理為自動(dòng)定理證明奠定了理論基礎(chǔ)；魯濱遜(Robinson)提

22、出的歸結(jié)原理使機(jī)器定理證明成為現(xiàn)實(shí)。編輯ppt334.3.1 子句w在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱(chēng)為文字。如：P(x)， P(x,f(x)， Q(x,g(x)定義4.5： 任何文字的析取式稱(chēng)為子句。 例如： P(x)Q(x), P(x,f(x)Q(x,g(x)定義4.6： 不包含任何文字的子句稱(chēng)為空子句。 編輯ppt34 子句集(1) 合取范式：C1 C2 C3 Cn(2) 子句集: S= C1 ,C2 ,C3 ,Cn(3)任何謂詞公式F都可通過(guò)等價(jià)關(guān)系及推理規(guī)則化為相應(yīng)的子句集S。編輯ppt35把謂詞公式化成子句集的步驟(1)1. 利用等價(jià)關(guān)系消去“”和“”例如公式可等價(jià)變換成2.

23、 利用等價(jià)關(guān)系把“”移到緊靠謂詞的位置上上式經(jīng)等價(jià)變換后3. 重新命名變?cè)?，使不同量詞約束的變?cè)胁煌拿稚鲜浇?jīng)變換后()() ( , )()( ( , )( , )xy P x yy Q x yR x y ()( () ( , )()( , )( , )xy P x yyQ x yR x y ()()( , ) ()( ( , )( , )xyP x yy Q x yR x y ()()( , ) ()( ( , )( , )xyP x yz Q x zR x z 編輯ppt36把謂詞公式化成子句集的步驟(2)4. 消去存在量詞a.存在量詞不出現(xiàn)在全稱(chēng)量詞的轄域內(nèi)，則只要用一個(gè)新的個(gè)體常量

24、替換受該量詞約束的變?cè)?。b.存在量詞位于一個(gè)或者多個(gè)全稱(chēng)量詞的轄域內(nèi)，此時(shí)要用Skolem函數(shù)f(x1,x2,xn)替換受該存在量詞約束的變?cè)?。上式中存在量詞(y)及(z)都位于(x)的轄域內(nèi)，所以需要用Skolem函數(shù)替換，設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后得到5. 把全稱(chēng)量詞全部移到公式的左邊()( , ( ) ( ( , ( )( , ( )xP x f xQ x g xR x g x()()( , ) ()( ( , )( , )xyP x yz Q x zR x z 編輯ppt37把謂詞公式化成子句集的步驟(3)6. 利用等價(jià)關(guān)系把公式化為Skolem標(biāo)

25、準(zhǔn)形Skolem標(biāo)準(zhǔn)形的一般形式是其中，M是子句的合取式，稱(chēng)為Skolem標(biāo)準(zhǔn)形的母式。上式化為Skolem標(biāo)準(zhǔn)形后得到7. 消去全稱(chēng)量詞8. 對(duì)變?cè)?，使不同子句中的變?cè)煌鲜交癁?. 消去合取詞，就得到子句集()() ()PQ RP QP R12()()()nxxx M()( , ( )( , ( ) ( , ( )( , ( )xP x f xQ x g xP x f xR x g x ( , ( )( , ( ) ( , ( )( , ( )P x f xQ x g xP y f yR y g y ( , ( )( , ( )( , ( )( , ( )P x f xQ x g

26、xP y f yR y g y編輯ppt38 子句集的性質(zhì)（1）子句集中子句之間是合取關(guān)系。（2）子句集中的變?cè)苋Q(chēng)量詞的約束。編輯ppt39 子句集的意義子句集S的不可滿足性：對(duì)于任意論域中的任意一個(gè)解釋?zhuān)琒中的子句不能同時(shí)取得真值T。定理4.1 設(shè)有謂詞公式F，其子句集為S，則F不可滿足的充要條件是S不可滿足。要證明PQ永真，只需證明公式F=(PQ)永假，即S不可滿足。編輯ppt404.3.2 Herbrand理論為了判斷子句集的不可滿足性，需要對(duì)所有可能論域上的所有解釋進(jìn)行判定。只有當(dāng)子句集對(duì)任何非空個(gè)體域上的任何一個(gè)解釋都是不可滿足的，才可斷定該子句集是不可滿足的。海伯倫構(gòu)造了一個(gè)特

27、殊的論域(海伯倫域)，并證明只要對(duì)這個(gè)特殊域上的一切解釋進(jìn)行判定，就可知子句集是否不可滿足。編輯ppt41海伯倫域定義4.7 設(shè)S為子句集，則按下述方法構(gòu)造的域H稱(chēng)為海伯倫域，記為H域。(1)令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則令H0a，其中a為任意指定的一個(gè)個(gè)體常量。(2)令Hi+1=HiS中所有n元函數(shù)f(x1,xn)|xj(j=1,n)是Hi中的元素，其中i=0,1,2,。例4.3 求子句集S=P(x)Q(x),R(f(y)的H域。解：此例中沒(méi)有個(gè)體常量，任意指定一個(gè)常量a作為個(gè)體常量，得到H0=aH1=a,f(a)H2=a,f(a),f(f(a)H3=a,f(a),

28、f(f(a),f(f(f(a)H=a,f(a),f(f(a),f(f(f(a),編輯ppt42為研究子句集的永假性，引入H域上的原子謂詞公式實(shí)例集A:A=所有出現(xiàn)于S中原子謂詞公式的實(shí)例n若原子公式是命題（不包含變量），則其實(shí)例就是其本身；n若原子公式形如P(t1, t2, tm), ti是變量（i=1，2，m）,則其實(shí)例通過(guò)讓ti=kiH(即H)來(lái)形成（i=1，2，m）。例如，對(duì)于上述例4.3，有： A=P(a), Q(f(a), Q(f(f(a),編輯ppt43我們稱(chēng)A中的元素為基原子，進(jìn)而A也稱(chēng)為基原子集。鑒于這些元素都是原子命題，只要給它們每個(gè)指派一個(gè)真值（T或F），就可建立子句集在H

29、域上的一個(gè)解釋?zhuān)洖镮*。就以基原子自身指示取真值T，前面加取反符號(hào)指示取真值F, 則對(duì)于上述第一例，有 I*1 = P(a), Q(f(a), Q(f(f(a), I*2 = P(a), Q(f(a), Q(f(f(a), 一個(gè)子句集的基原子有無(wú)限多個(gè)，它在一個(gè)子句集的基原子有無(wú)限多個(gè)，它在H域上的解域上的解釋也有無(wú)限多個(gè)。釋也有無(wú)限多個(gè)。編輯ppt44在H域上進(jìn)行解釋的意義意義：對(duì)于S任意可能論域D上的任意一個(gè)解釋I，總存在H域上的一個(gè)解釋I與它對(duì)應(yīng)，且子句集在這兩個(gè)解釋下具有相同的真值。定理4.2 子句集S不可滿足的充要條件是S對(duì)H域上一切解釋都為假。編輯ppt454.3.3 魯濱遜歸結(jié)

30、原理 魯濱遜歸結(jié)原理的基本思想：檢查子句集S中是否包含空子句。若包含，則S不可滿足；若不包含，就在子句集中選擇合適的子句進(jìn)行歸結(jié)，一旦通過(guò)歸結(jié)能推出空子句，就說(shuō)明子句集S是不可滿足的。 子句集S的不可滿足性：對(duì)于任意論域中的任意一個(gè)解釋?zhuān)琒中的子句不能同時(shí)取得真值T。一旦S中包含空子句，則S必不可滿足。編輯ppt46命題邏輯中的歸結(jié)原理定義4.9 若P是原子謂詞公式，則稱(chēng)P與P為互補(bǔ)文字。在命題邏輯中，P為命題。定義4.10 設(shè)C1與C2是子句集中的任意兩個(gè)子句。如果C1中的文字L1與C2中文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，

31、則稱(chēng)這一過(guò)程為歸結(jié)。稱(chēng)C12為C1和C2的歸結(jié)式，C1和C2為C12的親本子句。例4.9 設(shè)C1=PQ, C2=QR, C3=PC1與C2歸結(jié)得到：C12=PRC12與C3歸結(jié)得到：C123=R編輯ppt47定理4.4 C12是其親本子句C1與C2的邏輯結(jié)論。證明：設(shè)C1=LC1, C2=LC2, 則C12=C1C2111222() ()1212() ()12121212121212CCLCLCL CLCCCCLLCCLLCCCCCCCCCCC 由假言三段論編輯ppt48推論1 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式。若用C12代替C1和C2后得到新子句集S1，則由S1的不可

32、滿足性可推出原子句集S的不可滿足性，即S1的不可滿足性S的不可滿足性推論2 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式。若把C12加入S中得到新子句集S2，則S與S2在不可滿足的意義上是等價(jià)的，即S2的不可滿足性S的不可滿足性編輯ppt49推論1及推論2保證了我們可以用歸結(jié)的方法來(lái)證明子句集S的不可滿足性。為了要證明子句集S的不可滿足性，只要對(duì)其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子句集S，或者用歸結(jié)式替換它的親本子句，然后對(duì)新子句集(S1或者S2)證明不可滿足性就可以了。如果經(jīng)過(guò)歸結(jié)能得到空子句，則立即可得原子句集S是不可滿足的結(jié)論。在命題邏輯中，對(duì)不可滿足的子句集S，歸

33、結(jié)原理是完備的。即，若子句集不可滿足，則必然存在一個(gè)從S到空子句的歸結(jié)演繹；若存在一個(gè)從S到空子句的歸結(jié)演繹，則S一定是不可滿足的。編輯ppt50謂詞邏輯中的歸結(jié)原理在謂詞邏輯中，由于子句中含有變?cè)?，所以不能像命題邏輯那樣直接消去互補(bǔ)文字，而需要先用最一般合一對(duì)變?cè)M(jìn)行代換，然后才能進(jìn)行歸結(jié)。例如,設(shè)有兩個(gè)子句C1=P(x)Q(x), C2= P(a)R(y)由于P(x)與P(a)不同，所以C1與C2不能直接進(jìn)行歸結(jié)。但是若用最一般合一=a/x對(duì)兩個(gè)子句分別進(jìn)行代換：C1 =P(a)Q(a)C2 = P(a)R(y)就可對(duì)它們進(jìn)行歸結(jié)，得到歸結(jié)式：Q(a)R(y)編輯ppt51二元?dú)w結(jié)式的定義

34、定義4.11 設(shè)C1與C2是兩個(gè)沒(méi)有相同變?cè)淖泳?，L1和L2分別是C1和C2中的文字。若是L1和L2的最一般合一，則稱(chēng)C12=(C1-L1)(C2-L2)為C1和C2的二元?dú)w結(jié)式，L1和L2稱(chēng)為歸結(jié)式上的文字。例4.10 設(shè)C1=P(a)Q(x)R(x), C2=P(y)Q(b)若選L1=P(a),L2=P(y)，則有：L1=P(a), L2=P(y)，=a/y就是L1與L2的最一般合一。可得：C12=(C1-L1)(C2-L2)= Q(x)R(x)Q(b)編輯ppt52若子句C含有可合一的文字，則在進(jìn)行歸結(jié)之前應(yīng)先對(duì)這些文字進(jìn)行合一。記其最一般的合一為，稱(chēng)C子句C的因子。 C1=P(x)V

35、P(f(a)VQ(x), C2= P(y) VR(b) = f(a)/x C1=P(f(a) VQ(f(a) C12 = Q(f(a) VR(b) 編輯ppt53定義4.12 子句C1和C2的歸結(jié)式是下列二元?dú)w結(jié)式之一：nC1與C2的二元?dú)w結(jié)式；nC1與C2的因子C22的二元?dú)w結(jié)式；nC1的因子C11與C2的二元?dú)w結(jié)式；nC1的因子C11與C2的因子C22的二元?dú)w結(jié)式。對(duì)于一階謂詞邏輯歸結(jié)原理也是完備的。即，若子句集S不可滿足，則必然存在一個(gè)從S到空子句的歸結(jié)演繹；若存在一個(gè)從S到空子句的歸結(jié)演繹，則S一定是不可滿足的。編輯ppt544.3.4 歸結(jié)反演如欲證明Q為P1,P2,Pn的邏輯結(jié)論，

36、只需證(P1P2Pn)Q是不可滿足的，或證明其子句集是不可滿足的。而子句集的不可滿足性可用歸結(jié)原理來(lái)證明。應(yīng)用歸結(jié)原理證明定理的過(guò)程稱(chēng)為歸結(jié)反演。設(shè)F為已知前提的公式集，Q為目標(biāo)公式(結(jié)論)，用歸結(jié)反演證明Q為真的步驟是：否定Q，得到Q；把Q并入到公式集F中，得到F, Q;把公式集F, Q化為子句集S；1.應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時(shí)就證明了Q為真。編輯ppt55歸結(jié)反演的例子例4.12 已知求證：G是F的邏輯結(jié)論。證明：首先把F和G化為子句集：然后進(jìn)行歸結(jié)：(6)A(x,y)B(y)由(1)與(3)

37、歸結(jié)，f(x)/z(7)B(b)由(4)與(6)歸結(jié)，a/x,b/y(8)NIL由(5)與(7)歸結(jié)所以G是F的邏輯結(jié)論。上述歸結(jié)過(guò)程如右圖歸結(jié)樹(shù)所示。: ()()( ( , )( )()( ( )( , ):() ( )()()( ( , )( )Fxy A x yB yy C yD x yGx C xxy A x yB y ( , )( )( ( ),( , )( )( , ( )( ), ( , ), ( )FA x yB yC f xA x yB yD x f xGC zA a b B b A(x,y)B(y)C(f(x)A(x,y)B(y)B(b)NILC(z)A(a,b)B(b)編

38、輯ppt56假設(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)人心的生活編輯ppt57問(wèn)題謂詞表示：n “所有不貧窮并且聰明的人都是快樂(lè)的” (x)(Poor(x)Smart(x)Happy(x)n“那些看書(shū)的人是聰明的” (y) (Read(y) Smart(y)n“李明能看書(shū)且不貧窮” Read(Liming)Poor(Liming)n“

39、快樂(lè)的人過(guò)著激動(dòng)人心的生活” (z) (Happy(z)Exciting(z)n目標(biāo)“李明過(guò)著激動(dòng)人心的生活”的否定 Exciting(Liming)編輯ppt58將上述謂詞公式轉(zhuǎn)化為子句集如下： (1) Poor(x)Smart(x)Happy(x) (2) Read(y)Smart(y) (3) Read(Liming) (4) Poor(Liming) (5) Happy(z)Exciting(z) (6) Exciting(Liming) (結(jié)論的否定)編輯ppt59 Exciting(Liming) Happy(z)Exciting(z)Happy(Liming)Happy(x)Sm

40、art(x)Happy(x)Poor(Liming)Smart(Liming)Read(y)Smart(y )Poor(Liming)Read(Liming)Poor(Liming)Read(Liming)Read(Liming) NILLiming/zLiming/xLiming/y編輯ppt604.3.5 應(yīng)用歸結(jié)原理求取問(wèn)題的答案求解的步驟：把已知前提用謂詞公式表示出來(lái)，并且化為相應(yīng)的子句集。設(shè)該子句集的名字為S。把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后把它否定并與謂詞Answer構(gòu)成析取式。Answer是一個(gè)為了求解問(wèn)題而專(zhuān)設(shè)的謂詞。把此析取式化為子句集，并且把該子句集并入到子句集S中

41、，得到子句集S。對(duì)S應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。1.若得到歸結(jié)式Answer，則答案就在Answer中。編輯ppt61用歸結(jié)原理求解問(wèn)題的例子(1)例4.16 設(shè)A,B,C三人中有人從不說(shuō)真話，也有人從不說(shuō)假話。某人向這三人分別提出同一個(gè)問(wèn)題：誰(shuí)是說(shuō)謊者？A答：“B和C都是說(shuō)謊者”；B答：“A和C都是說(shuō)謊者”；C答：“A和B中至少有一個(gè)是說(shuō)謊者”。求誰(shuí)是老實(shí)人，誰(shuí)是說(shuō)謊者？解：設(shè)用T(x)表示x說(shuō)真話。 T(C)T(A)T(B) T(C)T(A)T(B) T(A)T(B)T(C) T(A)T(B)T(C) T(B)T(A)T(C) T(B)T(A)T(C) T(C)T(A)T(B) T(C)T(A)

42、T(B)編輯ppt62用歸結(jié)原理求解問(wèn)題的例子(2)把上述公式化成子句集，得到S：(1)T(A)T(B)(2)T(A)T(C)(3)T(C)T(A)T(B)(4)T(B)T(C)(5)T(C)T(A)T(B)(6) T(A)T(C)(7)T(B)T(C)下面先求誰(shuí)是老實(shí)人。把T(x)Ansewer(x)并入S得到S1。即多一個(gè)子句：(8)T(x)Ansewer(x)應(yīng)用歸結(jié)原理對(duì)S1進(jìn)行歸結(jié)：(9)T(A)T(C)(1)和(7)歸結(jié)(10)T(C) (6)和(9)歸結(jié)(11)Ansewer(C) (8)和(10)歸結(jié)所以C是老實(shí)人，即C從不說(shuō)假話。編輯ppt63(1)T(A)T(B)(2)T(

43、A)T(C)(3)T(C)T(A)T(B)(4)T(B)T(C)(5)T(C)T(A)T(B)(6) T(A)T(C)(7)T(B)T(C)下面證明A不是老實(shí)人，即證明T(A)。對(duì)T(A)進(jìn)行否定，并入S中，得到子句集S2，即S2比S多如下子句：(8)(T(A), 即T(A)應(yīng)用歸結(jié)原理對(duì)S2進(jìn)行歸結(jié)：(9)T(A)T(C) (1)和(7)歸結(jié)(10)T(A) (2)和(9)歸結(jié)(11)NIL (8)和(10)歸結(jié)所以A不是老實(shí)人。同樣可以證明B也不是老實(shí)人。編輯ppt64歸結(jié)時(shí)，并不要求把子句集中所有的子句都用到。在歸結(jié)過(guò)程中，一個(gè)子句可以多次被用來(lái)進(jìn)行歸結(jié)。編輯ppt654.3.6 歸結(jié)策

44、略歸結(jié)策略可分為兩大類(lèi)：一類(lèi)是刪除策略；刪除某些無(wú)用的子句來(lái)縮小歸結(jié)的范圍。一類(lèi)是限制策略。通過(guò)對(duì)參加歸結(jié)的子句進(jìn)行種種限制，盡可能減小歸結(jié)的盲目性，使其盡快地歸結(jié)出空子句。歸結(jié)的一般過(guò)程設(shè)有子句集S=C1,C2,C3,C4，則對(duì)此子句集歸結(jié)的一般過(guò)程是：S內(nèi)任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第一級(jí)歸結(jié)式，記為S1。把S與S1內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第二級(jí)歸結(jié)式，記為S2。S和S1內(nèi)的子句與S2內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第三級(jí)歸結(jié)式，記為S3。如此繼續(xù)，直到出現(xiàn)了空子句或者不能再繼續(xù)歸結(jié)為止。編輯ppt66一個(gè)歸結(jié)的例子例4.17

45、設(shè)有子句集S=P, R,PQ,QR。歸結(jié)過(guò)程為：S: (1)P(2)R(3)PQ(4)QRS1: (5)Q (1)與(3)歸結(jié)(6)Q (2)與(4)歸結(jié)(7)PR (3)與(4)歸結(jié)S2: (8)R (1)與(7)歸結(jié)(9)P (2)與(7)歸結(jié)(10)P (3)與(6)歸結(jié)(11)R (4)與(5)歸結(jié)S3: (12) NIL (1)與(9)歸結(jié)編輯ppt67刪除策略純文字刪除法如果某文字L在子句集中不存在可與之互補(bǔ)的文字L，則稱(chēng)該文字為純文字。包含純文字的子句可以刪除。重言式刪除法如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對(duì)，則該字句稱(chēng)為重言式。重言式是永遠(yuǎn)為真的子句，可以刪除。編輯ppt68支持集

46、策略對(duì)參加歸結(jié)的子句提出如下限制：每一次歸結(jié)時(shí)，親本子句中至少有一個(gè)是由目標(biāo)公式的否定所得到的子句，或者是它的后裔?？梢宰C明，支持集策略是完備的。例4.18 設(shè)有子句集S=I(x)R(x),I(a),R(y)L(y),L(a)其中I(x)R(x)是目標(biāo)公式否定后得到的子句。用支持集策略進(jìn)行歸結(jié)的過(guò)程是：S:(1) I(x)R(x)(2) I(a)(3) R(y)L(y)(4) L(a)S1:(5) R(a) (1)與(2)歸結(jié)(6) I(x)L(x) (1)與(3)歸結(jié)S2:(7) L(a) (2)與(6)歸結(jié)(8) L(a) (3)與(5)歸結(jié)(9) I(a) (4)與(6)歸結(jié)S3:(10

47、)NIL (2)與(9)歸結(jié)編輯ppt69支持集策略示例I(x)R(x)I(a)R(y)L(y)L(a)R(a)L(a)I(x)L(x)L(a)I(a)NIL12345678910編輯ppt70線性輸入策略限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是初始子句集中的子句。線性輸入策略可限制生成歸結(jié)式的數(shù)量，具有簡(jiǎn)單、高效的優(yōu)點(diǎn)。但是它是不完備的。I(x)R(x)I(a)R(y)L(y)L(a)R(a)L(a)I(x)L(x)L(a)I(a)NIL123456981112R(a)I(a)710編輯ppt71單文字子句策略如果一個(gè)子句只包含一個(gè)文字，則稱(chēng)它為單文字子句。限制：參加歸結(jié)的兩個(gè)子句中必須至

48、少有一個(gè)是單文字子句。用單文字子句策略歸結(jié)時(shí)，歸結(jié)式比親本子句含有較少的文字，這有利于朝著空子句的方向前進(jìn)，因此它有較高的歸結(jié)效率。但是，這種歸結(jié)策略是不完備的。當(dāng)初始子句集中不包含單文字子句時(shí)，歸結(jié)就無(wú)法進(jìn)行。編輯ppt72祖先過(guò)濾策略該策略與線性策略比較相似，但放寬了限制。當(dāng)對(duì)兩個(gè)子句C1和C2進(jìn)行歸結(jié)時(shí)，只要它們滿足下述任一個(gè)條件就可以歸結(jié)。C1和C2中至少有一個(gè)是初始子句集中的子句。C1和C2中一個(gè)是另外一個(gè)的祖先子句。1.祖先過(guò)濾策略是完備的。編輯ppt73優(yōu)點(diǎn)：簡(jiǎn)單，便于在計(jì)算機(jī)上實(shí)現(xiàn)。缺點(diǎn)：必須把邏輯公式化成子句集。不便于閱讀與理解。P(x)Q(x)沒(méi)有P(x)Q(x)直觀?？赡?/p>

49、丟失控制信息。下列邏輯公式：(AB)C A(BC)(AC)B B(AC)(CB)A C(BA)化成子句后都是: ABC歸結(jié)演繹推理的特點(diǎn)編輯ppt744.4 與/或形演繹推理歸結(jié)演繹推理要求把有關(guān)問(wèn)題的知識(shí)及目標(biāo)的否定都化成子句形式，然后通過(guò)歸結(jié)進(jìn)行演繹推理，其推理規(guī)則只有一條，即歸結(jié)規(guī)則；與/或形演繹推理不再把有關(guān)知識(shí)轉(zhuǎn)化成子句集，而把領(lǐng)域知識(shí)及已知事實(shí)分別用蘊(yùn)含式及與/或形表示出來(lái)，然后通過(guò)運(yùn)用蘊(yùn)含式進(jìn)行演繹推理，從而證明某個(gè)目標(biāo)公式。編輯ppt75基于規(guī)則的演繹推理規(guī)則規(guī)則是一種比較接近于人們習(xí)慣的問(wèn)題描述方式是一種比較接近于人們習(xí)慣的問(wèn)題描述方式，用蘊(yùn)含式（，用蘊(yùn)含式（“If Then

50、”規(guī)則）按照這種問(wèn)題描規(guī)則）按照這種問(wèn)題描述方式進(jìn)行求解的系統(tǒng)稱(chēng)為述方式進(jìn)行求解的系統(tǒng)稱(chēng)為基于規(guī)則的系統(tǒng)基于規(guī)則的系統(tǒng)，或，或者叫做者叫做規(guī)則演繹系統(tǒng)規(guī)則演繹系統(tǒng)。規(guī)則正向演繹系統(tǒng)規(guī)則正向演繹系統(tǒng)規(guī)則逆向演繹系統(tǒng)規(guī)則逆向演繹系統(tǒng)規(guī)則雙向演繹系統(tǒng)規(guī)則雙向演繹系統(tǒng)編輯ppt76規(guī)則正向演繹系統(tǒng)規(guī)則正向演繹系統(tǒng)是從已知事實(shí)出發(fā)，正向使規(guī)則正向演繹系統(tǒng)是從已知事實(shí)出發(fā)，正向使用規(guī)則（蘊(yùn)含式）直接進(jìn)行演繹，直至到達(dá)目用規(guī)則（蘊(yùn)含式）直接進(jìn)行演繹，直至到達(dá)目標(biāo)為止。標(biāo)為止。在規(guī)則正向演繹系統(tǒng)中，對(duì)已知在規(guī)則正向演繹系統(tǒng)中，對(duì)已知事實(shí)事實(shí)和和規(guī)則規(guī)則都都有一定的要求，如果不是所要求的形式，需要有一定的要求，

51、如果不是所要求的形式，需要進(jìn)行變換。進(jìn)行變換。在基于規(guī)則的正向演繹系統(tǒng)中，把在基于規(guī)則的正向演繹系統(tǒng)中，把事實(shí)事實(shí)表示為表示為非蘊(yùn)含形式非蘊(yùn)含形式的的與與或形或形，作為系統(tǒng)的總數(shù)據(jù)庫(kù)，作為系統(tǒng)的總數(shù)據(jù)庫(kù)把一個(gè)公式化為與或形的步驟與化為子句集類(lèi)似，把一個(gè)公式化為與或形的步驟與化為子句集類(lèi)似，只是不必把只是不必把公式化為子句的合取形式，也不能消去公式中的合取。公式化為子句的合取形式，也不能消去公式中的合取。編輯ppt77規(guī)則正向演繹系統(tǒng)(1) 利用利用 “PQPQ”，消去蘊(yùn)含符號(hào)；，消去蘊(yùn)含符號(hào)； (2) 利用狄利用狄.摩根定律及量詞轉(zhuǎn)換率把摩根定律及量詞轉(zhuǎn)換率把“”移到緊靠謂詞的位移到緊靠謂詞的

52、位置，直到否定符號(hào)的轄域最多只含一個(gè)謂詞為止；置，直到否定符號(hào)的轄域最多只含一個(gè)謂詞為止；(3)重新命名變?cè)怪匦旅冊(cè)?，使不同量詞約束的變?cè)胁煌拿植煌吭~約束的變?cè)胁煌拿郑?4)對(duì)存在量詞量化的變量用對(duì)存在量詞量化的變量用skolem函數(shù)代替；函數(shù)代替；(5) 消去全稱(chēng)量詞，且消去全稱(chēng)量詞，且使各主要合取式中的變?cè)哂胁煌淖兪垢髦饕先∈街械淖冊(cè)哂胁煌淖兞棵棵＞庉媝pt78規(guī)則正向演繹系統(tǒng)有如下表達(dá)式有如下表達(dá)式 (x) (y)(Q(y, x)(R(y)P(y)S(x, y)可把它轉(zhuǎn)化為：可把它轉(zhuǎn)化為： Q(z, a)( ( R(y)P(y) )S(a, y) )這

53、就是這就是與與/或形表示或形表示。事實(shí)表達(dá)式的事實(shí)表達(dá)式的與與/或形或形可用一棵可用一棵與與/或圖或圖表示出來(lái)。表示出來(lái)。編輯ppt79規(guī)則正向演繹系統(tǒng)Q(z, a)(R(y)P(y)S(a, y)的與的與/或圖表示或圖表示如下：如下：w Q(z, a)(R(y)P(y)S(a, y)wQ(z, a)w(R(y)P(y)S(a, y)wR(y)P(y)w S(a, y)wR(y)wP(y)編輯ppt80規(guī)則正向演繹系統(tǒng)當(dāng)某表達(dá)式為當(dāng)某表達(dá)式為k個(gè)子表達(dá)式的析?。簜€(gè)子表達(dá)式的析?。篍1E2Ek，其中的每個(gè)子表達(dá)式，其中的每個(gè)子表達(dá)式Ei均被表示為均被表示為E1E2Ek的的后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)，并由一

54、個(gè)，并由一個(gè)k線連接符線連接符（即圖中的半圓?。磮D中的半圓弧）將這些后繼節(jié)點(diǎn)都連接到其父節(jié)點(diǎn)，即）將這些后繼節(jié)點(diǎn)都連接到其父節(jié)點(diǎn)，即表示成與的表示成與的關(guān)系關(guān)系。當(dāng)某表達(dá)式為當(dāng)某表達(dá)式為k個(gè)子表達(dá)式的合?。簜€(gè)子表達(dá)式的合取：E1E2Ek，其中的每個(gè)子表達(dá)式，其中的每個(gè)子表達(dá)式Ei均被表示為均被表示為E1E2Ek的一個(gè)單一的后繼節(jié)點(diǎn)，無(wú)需用連接符連接，即的一個(gè)單一的后繼節(jié)點(diǎn)，無(wú)需用連接符連接，即表示表示成或的關(guān)系成或的關(guān)系。這樣，與這樣，與/或圖的或圖的根節(jié)點(diǎn)根節(jié)點(diǎn)就是整個(gè)事實(shí)表達(dá)式，就是整個(gè)事實(shí)表達(dá)式，葉節(jié)葉節(jié)點(diǎn)點(diǎn)均為事實(shí)表達(dá)式中的一個(gè)均為事實(shí)表達(dá)式中的一個(gè)文字文字。編輯ppt81規(guī)則正向演

55、繹系統(tǒng)有了與有了與/或圖的表示，就可以求出其或圖的表示，就可以求出其解樹(shù)（結(jié)束于文解樹(shù)（結(jié)束于文字節(jié)點(diǎn)上的子樹(shù)）集字節(jié)點(diǎn)上的子樹(shù)）集?？梢园l(fā)現(xiàn)，事實(shí)表達(dá)式的子句?？梢园l(fā)現(xiàn)，事實(shí)表達(dá)式的子句集與解樹(shù)集之間存在著一一對(duì)應(yīng)關(guān)系，即集與解樹(shù)集之間存在著一一對(duì)應(yīng)關(guān)系，即解樹(shù)集中的解樹(shù)集中的每個(gè)解樹(shù)都對(duì)應(yīng)著子句集中的一個(gè)子句每個(gè)解樹(shù)都對(duì)應(yīng)著子句集中的一個(gè)子句。解樹(shù)集中每個(gè)解樹(shù)的端節(jié)點(diǎn)上的文字的析取就是子句解樹(shù)集中每個(gè)解樹(shù)的端節(jié)點(diǎn)上的文字的析取就是子句集中的一個(gè)子句。集中的一個(gè)子句。上圖所示的與上圖所示的與/或圖有或圖有3個(gè)解樹(shù)，分別對(duì)應(yīng)這以個(gè)解樹(shù)，分別對(duì)應(yīng)這以下下3個(gè)子句：個(gè)子句： Q(z, a) R(y

56、) S(a, y) P(y) S(a, y)編輯ppt82規(guī)則正向演繹系統(tǒng)為簡(jiǎn)化演繹過(guò)程，通常要求規(guī)則具有如下形式：為簡(jiǎn)化演繹過(guò)程，通常要求規(guī)則具有如下形式： LW其中，其中，L為為單文字單文字，W為為與與/或形公式或形公式。假定出現(xiàn)在蘊(yùn)含式中的任何變量全都受假定出現(xiàn)在蘊(yùn)含式中的任何變量全都受全稱(chēng)量詞的全稱(chēng)量詞的約束約束，并且這些變量已經(jīng)被換名，使得他們，并且這些變量已經(jīng)被換名，使得他們與事實(shí)與事實(shí)公式和其他規(guī)則中的變量不同公式和其他規(guī)則中的變量不同。如果領(lǐng)域知識(shí)的規(guī)則表示形式與上述要求不同，則如果領(lǐng)域知識(shí)的規(guī)則表示形式與上述要求不同，則應(yīng)應(yīng)將它轉(zhuǎn)換成要求的形式。將它轉(zhuǎn)換成要求的形式。編輯pp

57、t83規(guī)則正向演繹系統(tǒng)(1) 暫時(shí)消去蘊(yùn)含符號(hào)暫時(shí)消去蘊(yùn)含符號(hào)“”。設(shè)有如下公式：。設(shè)有如下公式： (x)(y) ( z)P(x, y,z)(u)Q(x, u) 運(yùn)用等價(jià)關(guān)系運(yùn)用等價(jià)關(guān)系“PQPQ”，可將上式變?yōu)椋?，可將上式變?yōu)椋?(x)( y) (z)P(x, y,z)(u)Q(x, u)(2) 把否定符號(hào)把否定符號(hào)“”移到緊靠謂詞的位置上，使其作移到緊靠謂詞的位置上，使其作用域僅限于單個(gè)謂詞。通過(guò)使用狄用域僅限于單個(gè)謂詞。通過(guò)使用狄.摩根定律及量詞轉(zhuǎn)摩根定律及量詞轉(zhuǎn)換率可把上式轉(zhuǎn)換為：換率可把上式轉(zhuǎn)換為： ( x)( (y) (z)P(x, y,z) (u)Q(x, u)編輯ppt84規(guī)則

58、正向演繹系統(tǒng)(3) 引入引入Skolem函數(shù)，消去存在量詞。消去存在量函數(shù)，消去存在量詞。消去存在量詞后，上式可變?yōu)椋涸~后，上式可變?yōu)椋?( x)( (y) (P(x, y,f(x,y)(u)Q(x, u)(4)把所有全稱(chēng)量詞移至前面化成前束式，消去全部把所有全稱(chēng)量詞移至前面化成前束式，消去全部全稱(chēng)量詞。消去全稱(chēng)量詞后，上式變?yōu)椋喝Q(chēng)量詞。消去全稱(chēng)量詞后，上式變?yōu)椋?P(x, y,f(x,y)Q(x, u) 此公式中的變?cè)急灰暈槭苋Q(chēng)量詞約束的變?cè)?。此公式中的變?cè)急灰暈槭苋Q(chēng)量詞約束的變?cè)?5) 恢復(fù)蘊(yùn)含式表示。利用等價(jià)關(guān)系恢復(fù)蘊(yùn)含式表示。利用等價(jià)關(guān)系“PQPQ”將上式變?yōu)椋簩⑸鲜阶優(yōu)椋?/p>

59、 P(x, y,f(x,y)Q(x, u)編輯ppt85規(guī)則正向演繹系統(tǒng)在上述對(duì)規(guī)則的要求中，在上述對(duì)規(guī)則的要求中，之所以限制其前件為單文字之所以限制其前件為單文字，是因?yàn)?，是因?yàn)樵谶M(jìn)行正向演繹推理時(shí)要用規(guī)則作用于表示在進(jìn)行正向演繹推理時(shí)要用規(guī)則作用于表示事實(shí)的與事實(shí)的與/或樹(shù)，而該與或樹(shù)，而該與/或樹(shù)的葉節(jié)點(diǎn)都是單文字，這或樹(shù)的葉節(jié)點(diǎn)都是單文字，這樣就可用規(guī)則的前件與葉節(jié)點(diǎn)進(jìn)行簡(jiǎn)單匹配。樣就可用規(guī)則的前件與葉節(jié)點(diǎn)進(jìn)行簡(jiǎn)單匹配。對(duì)非單文字情況，若形式為對(duì)非單文字情況，若形式為L(zhǎng)1L2W，則可將其轉(zhuǎn)，則可將其轉(zhuǎn)換成與之等價(jià)的兩個(gè)規(guī)則換成與之等價(jià)的兩個(gè)規(guī)則L1W與與 L2W進(jìn)行處理。進(jìn)行處理。與與

60、/或樹(shù)正向演繹系統(tǒng)要求目標(biāo)公式用或樹(shù)正向演繹系統(tǒng)要求目標(biāo)公式用子句形子句形表示。表示。如果目標(biāo)公式不是子句形，則需要化成子句形。如果目標(biāo)公式不是子句形，則需要化成子句形。編輯ppt86規(guī)則正向演繹系統(tǒng)規(guī)則正向演繹推理過(guò)程是從已知事實(shí)出發(fā)，不斷運(yùn)規(guī)則正向演繹推理過(guò)程是從已知事實(shí)出發(fā)，不斷運(yùn)用規(guī)則，推出欲證明目標(biāo)公式的過(guò)程。用規(guī)則，推出欲證明目標(biāo)公式的過(guò)程。先用與先用與/或樹(shù)把已知事實(shí)表示出來(lái)，然后再用規(guī)則的或樹(shù)把已知事實(shí)表示出來(lái)，然后再用規(guī)則的前件和與前件和與/或樹(shù)的或樹(shù)的葉節(jié)點(diǎn)進(jìn)行匹配葉節(jié)點(diǎn)進(jìn)行匹配，并通過(guò)一個(gè)匹配，并通過(guò)一個(gè)匹配弧把匹配成功的規(guī)則加入到與弧把匹配成功的規(guī)則加入到與/或樹(shù)中，依