1、*第3章經(jīng)典邏輯推理1根據(jù)經(jīng)典邏輯（命題邏輯和一階謂詞 邏輯）規(guī)則進(jìn)行的精確推理，或確定 性推理。?從一個(gè)或幾個(gè)已知的判斷 （前提）邏輯地推論岀 一個(gè)新的判斷（結(jié)論）的思維形式稱為推理， 這是事物的客觀聯(lián)系在意識(shí)中的反映。?人解決問題就是利用以往的知識(shí)，通過推理得 岀結(jié)論。?自動(dòng)推理的理論和技術(shù)是程序推導(dǎo)、程序正確 性證明、專家系統(tǒng)、智能機(jī)器人等研究領(lǐng)域的 重要基礎(chǔ)。?實(shí)現(xiàn)推理的程序稱為推理機(jī)。#1.演繹推理、歸納推理、默認(rèn)推理» 3.1.1推理方式及其分類1. 演繹推理、歸納推理、默認(rèn)推理2. 確定性推理、不確定性推理3. 單調(diào)推理、非單調(diào)推理4. 啟發(fā)式推理、非啟發(fā)式推理5. 基

2、于知識(shí)的推理、直覺推理演繹推理(deductive reasoning)從一般到個(gè)別例：1）足球運(yùn)動(dòng)員的身體都是強(qiáng)壯的。2）李波是一名足球運(yùn)動(dòng)員。3）所以，李波的身體是強(qiáng)壯的。 論式#納推理和演繹推理的區(qū)別第一，一個(gè)正確的演繹推理是不可能前提真而結(jié)論假的，但歸納推理卻有可能前提真而結(jié)論假。第二，演繹推理的結(jié)論不超岀前提，而歸納推理 的結(jié)論超出了前提。納推理（inductive reasoning）從個(gè)別到一般例：白菜能夠進(jìn)行光合作用，大豆能夠進(jìn)行光合作用， 水稻能夠進(jìn)行光合作用， 棉花能夠進(jìn)行光合作用， 柳樹能夠進(jìn)行光合咋用，#白菜、大豆、水稻、棉花、柳樹 都是 綠色植物。所以，所有綠色植物都

3、能進(jìn)行光合作用。第三，一個(gè)歸納推理增加或減少一些前提，會(huì)增 加或減少其結(jié)論為真的概率，而在演繹推理中 不會(huì)出現(xiàn)這種情況。卜歸納推理的強(qiáng)度對(duì)于歸納推理，人們關(guān)注的是推理的強(qiáng)度。 說一個(gè)歸納推理是強(qiáng)的，意思是說，如 果這個(gè)推理的前提是真的活，那么它的結(jié)論很 可能也是真的。歸納強(qiáng)度是一種前提對(duì)結(jié)論支持程度的 量度。另外，推理的結(jié)論很可能為真并不能保 證這個(gè)歸納推理是強(qiáng)的。例1:甲系的排球隊(duì)在過去幾年是全校冠軍隊(duì)。在今年的校內(nèi)各類排球比賽中，甲系排球 隊(duì)從未輸過一場(chǎng)。明天甲系排球隊(duì)與乙系排球隊(duì)比賽。因此，明天甲系排球隊(duì)將打敗乙系排球隊(duì)。 （這個(gè)推理是一個(gè)相當(dāng)強(qiáng)的推理，若補(bǔ)充以下兩 個(gè)前提：）甲系排球隊(duì)

4、所有主力隊(duì)員明天因故不能參 加比賽。甲系排球隊(duì)明天參賽的替補(bǔ)隊(duì)員最近一周 沒有訓(xùn)練。（這樣，原有的結(jié)論為真的概率大大地降低了。）2#例2 :某高校絕大部分的學(xué)生都能跳過2米的高 度，小劉的爺爺是某高校的學(xué)生，所以，小劉的爺爺也能跳過2米的高度。 （因?yàn)槠淝疤釋?duì)結(jié)論有強(qiáng)的支持，如果前提 是真的話，那么其結(jié)論 非常可能為真。）例3 :小學(xué)生李明在動(dòng)物園里觀察了 10只隅蹄動(dòng) 物，他發(fā)現(xiàn)這些動(dòng)物都是食草動(dòng)物，因此他得岀結(jié)論：所有偶蹄動(dòng)物都是食草 動(dòng)物。（盡管前提和結(jié)論都可能是真的，但這些 前提并沒有為結(jié)論提供多大的支持，因此這個(gè) 歸納推理是弱的。）?完全歸納推理（Complete induction

5、） 完全歸納推理是通過對(duì)一類事物中的每一對(duì) 象進(jìn)行研究，從而概括出關(guān)于這類對(duì)象的一 般性結(jié)論的推理形式。?不完全歸納推理（Incomplete induction） 通過考察一類事物的部分對(duì)象，從而得岀關(guān) 于這類對(duì)象的一般性結(jié)論。的推理形式，這 就是。#|_例結(jié)論：該廠生產(chǎn)的產(chǎn)品是合格的。若是普檢，則為完全歸納推理，屬于必 然性推理。若是抽檢，則為不完全歸納推理，屬于 非必然性推理。默認(rèn)推理是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具 備所進(jìn)行的缺省推理。例：在條件A已成立的情況下，若沒有足夠的 證據(jù)證明條件B不成立，則就默認(rèn)B是成立的, 并在此默認(rèn)的前提下進(jìn)行推理，推導(dǎo)岀某個(gè)結(jié) 論。F 2.確定

6、性推理、不確定性推理*?按推理時(shí)所用的知識(shí)是否精確，推出的 結(jié)論是否完全肯定來分類3. 單調(diào)推理、非單調(diào)推理=?按推出的結(jié)論是否單調(diào)地增加，或者說推出的結(jié)論是否越來越接近最終目標(biāo)分類3#?基于經(jīng)典邏輯的演繹推理屬于單調(diào)性推理。?經(jīng)典邏輯推理屬于確定性推理。?默認(rèn)推理是非單調(diào)推理。?不確定性推理分似然推理（概率論）和 近似推理（模糊邏輯）#4. 啟發(fā)式推理、非啟發(fā)式推理?按推理中是否運(yùn)用與問題有關(guān)的啟發(fā)性 知識(shí)分類。5.基于知識(shí)的推理、直覺推理從方法論的角度分類。?我們所討論的推理都屬于基于知識(shí)的推 理。?直覺推理又稱為常識(shí)性推理。#*_3.1.2推理的控制策略即求解問題的策略。1.推理方向?用

7、于確定推理的驅(qū)動(dòng)方式，分為正向推理、 逆向推理、混合推理及雙向推理四種。系統(tǒng)：知識(shí)庫(kù)+數(shù)據(jù)庫(kù)+推理機(jī)(1)正向推理 Forward Reasoning又稱為前向鏈推理、數(shù)據(jù)驅(qū)動(dòng)的推理、模式制導(dǎo)推理及前件推理等。?定義：從已知的數(shù)據(jù)/條件/中間結(jié)論出發(fā) 推導(dǎo)出新的結(jié)論。1. A ? G12. A'? G13. B ? G24. B'? G25. G1 & G2 ? G(2)反向推理 Backward Reasoning（3 ）混合推理又叫逆向鏈推理、目標(biāo)驅(qū)動(dòng)的推理、目 標(biāo)制導(dǎo)推理及后件推理等。?定義：從結(jié)論（目標(biāo)）出發(fā)推導(dǎo)結(jié)論 （目標(biāo)）的前提條件。1. G1 &

8、G2 ? G2. A ? G13. A'? G14. B ? G25. B'? G2既有正向又有逆向（不同時(shí)）的推理。用于：1 ）已知的事實(shí)不充分。2）由正向推理推出的結(jié)論可信度 不咼。3）希望得到更多的結(jié)論。4#（4 ）雙向推理正向推理與逆向推理 同時(shí)進(jìn)行。2.求解策略只求一個(gè)解，還是求所有解以及最優(yōu)解限制策略#對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn) 行限制。推理過程中若有多個(gè)知識(shí)匹配成功，即 發(fā)生了沖突，如何從中挑選一個(gè)知識(shí)用 于當(dāng)前的推理。?基本思想是對(duì)知識(shí)進(jìn)行排序。1 ）按針對(duì)性排序。2 ）按匹配度排序。3）根據(jù)領(lǐng)域問題的特點(diǎn)排序。5?確定性匹配是指兩個(gè)換后變式完全一致。齊

9、.3.1.3模式匹配及其變量代換3 ?模式匹配是指兩個(gè)知識(shí)模式(如兩個(gè)謂詞 公式、兩個(gè)框架片段或兩個(gè)語(yǔ)義網(wǎng)絡(luò)片段 等)的比較，檢查這兩個(gè)知識(shí)模式是否完 全一致或近似一致。?不確定性匹配是指兩個(gè)知識(shí)模式不完全 一致，但從總體上看，它們的相似程度 又落在規(guī)定的限度內(nèi)。6#?按匹配時(shí)兩個(gè)知識(shí)模式的相似程度劃分， 模式匹配可分為確定性匹配與不確定性匹 配。?無論是確定性匹配還是不確定性匹配， 在進(jìn)行匹配時(shí)一般都需要進(jìn)行變量的代 換。#*例:置換 substituti on#?用置換項(xiàng)代換變量即變量代換，使某些 變?cè)涣硗獾淖冊(cè)?、常量或函?shù)取代， 使之不再在公式中出現(xiàn)。?代換是形如t /X i，t 2/

10、X 2,t n/x n的有 限集合。其中t 1 ,t 2,t n是項(xiàng)；X1 ,x2 ,x n是互不相同的變?cè)籺 i/x i表 示用ti代換x,不允許t i與x相同，也不 允許變?cè)h(huán)地出現(xiàn)在另一個(gè)t j中。g(y)/x,f(x)/y不是一個(gè)代換。?代換是可結(jié)合的，但一般不可交換。?若用s1 os2表示兩個(gè)代換s1和s2的合成，L表 示一表達(dá)式，則(L s1)s2=L(s1 ° s2)(s1 ° s2) ° s3=s1 ° (s2 ° s3)si ° s2 工 s2° si#合uni ficati on*例如：表達(dá)式P【x,

11、 f(y),B對(duì)下列置換s = z x,w ys =A yS =g(z) x, A y將有結(jié)果：px, f (y),Bs = pz, f(w),Bpx,f(y),BS2= px, f(A),Bpx, f (y), Bs = pg(z), f(A),BW-?尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致, 叫做合一?設(shè)有公式集F= Fi ,F2,Fn，如果存在一個(gè) 置換s，使得F 1s =Es = =Fns則稱s為F的合一(者)，且稱F是可合一的。? 一個(gè)公式集的合一通常是不唯一的，而最簡(jiǎn) 單的合一是唯一的。*差異集設(shè)有如下兩個(gè)謂詞公式：Fi: P (x, y, z)F2 : P (x, f (a), h

12、 (b)逐個(gè)向右比較，構(gòu)成差異集U=y，f(a)D2=z，h (b)求最一般合一1 )令 k=0 , Fk=F， k= £F是欲求其最一般合一的公式集, 做代換。£是空代換，它表示不2)若Fk只含一個(gè)表達(dá)式，則算法停止，(T k就是最一般合一。3 )找出Fk的差異集Dk4 )護(hù)k中出素見k和t則其置：是變?cè)?，tk是項(xiàng)，且XkFk+1= Fkt k/ x kk=k+17然后轉(zhuǎn)2)5)算法終止，F(xiàn)的最一般合一不存在。#例:求最一般合一F=P(a,x,f(g(y),P(z,f(z),f(u)1) 令Fo=F,b 0= £，因F o中含有兩個(gè)表達(dá)式，所 以b °

13、不是最一般合一。2) 差異集D o =a, z3) b 1= b oo a/z= a/z,F 1 =P(a,x,f(g(y),P(a,f(a),f(u)4) D =x, f (a)W5) b 2= b 1o f (a) /x= a/z , f (a) /x,F 2= F 1 f (a) /x=P(a, f(a) ,f(g(y),P(a,f(a),f(u)6) D =g(y) , u7) b 3= b 2° g (y) /u=a/z , f (a) /x , g (y) /u,F 3= F 2 g (y) /u=P(a, f(a) ,f(g(y)因F 3只含一個(gè)表達(dá)式，因此b 3就是最

14、一般合一。#已知如下事實(shí)：1) 如果是容易的課程小王就喜歡。2) C班的課程都是容易的。3) Ds是C班的一門課程。求證：小王喜歡Ds這門課程。簡(jiǎn)單置換即可自然演繹推理*_3.2自然演繹推理?從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏 輯的推理規(guī)則推岀結(jié)論的過程。常用：p規(guī)則一一在推理的任何步驟上都可引入前提。T規(guī)則一一在推理時(shí)，如果前面步驟中有一個(gè) 或多個(gè)公式永真蘊(yùn)涵公式S,則可把S引入推 理過程中。假言推理 P, P f Q ? Q拒取式推理P fQ ? n P#*_3.3歸結(jié)演繹推理自動(dòng)定理證明即證明P ? Q的永真性。 歸結(jié)原理使用反證法來證明語(yǔ)句。即歸 結(jié)是從結(jié)論的非，導(dǎo)出已知語(yǔ)句的矛

15、盾。 反證法，只要證明P An Q是不可滿足 的?？瓢?1謂詞公式化為子句集的方法?在謂詞邏輯中，把原子謂詞公式及其否 定統(tǒng)稱為文字。?任何文字的析取式稱為子句。?不包含任何文字的子句稱為空子句。一永假在謂詞邏輯中，任何一個(gè)謂詞公式都可通 過應(yīng)用等價(jià)關(guān)系及推理規(guī)則化成合取范 式，再化成相應(yīng)的子句集。一一消解8#步驟1 :消去蘊(yùn)涵f勺歸律：Pf Q? n P VQ例: ? x( ? yP(x,y) f n ? y(Q(x,y) f R(x,y)經(jīng)等價(jià)變換后變成?x( n ?yP(x,y) V n ?y( n Q(x,y) V R(x,y)步驟2 :將n ”移到緊靠謂詞的位置雙重否定律:n n P

16、 ?P狄.摩根律：nP VQ)? n P An QP AQ)? n P Vn Q量詞轉(zhuǎn)換律：n ?xP ?x( n P)n ?xP ?x( n P)上例：?x(?yn P(x,y) V?(Q(x,y) An R(x,y)#I步驟3 :變量標(biāo)準(zhǔn)化?重新命名變?cè)?，使不同量詞約束的變 元有不同的名字。上例：? x( ?yn P(x,y) V?(Q(x,z) An R(x,z)消去存在量詞?若存在量詞不在全稱量詞的轄域內(nèi)，則存在固化：？xP(x) ? P(c)?若存在量詞在一個(gè)或多個(gè)全稱量詞的轄 域內(nèi)，則用skolem函數(shù)f(x 1 ,x 2,x n)替 換約束變?cè)?上例：?x(n P(x,f(x

17、) VQ(x,g(x) An R(x,g(x)#步驟5 :化為前束式W-=?扌把把所有的量詞移到公式的左部?，F(xiàn)在已不留下任何存在量詞，而且每個(gè) 全稱量詞都有自己的變量。把所有的全 稱量詞移到公式的左部，并使每個(gè)量詞 的轄域包含這個(gè)量詞后面公式的整個(gè)部 分?x (P AQ) ? ?x P A?x Q詞轄域的擴(kuò)展和收縮a. ?XA(X)VP ? X(A(X) VP)b. ? XA(X) /P ? X(A(X) AP)c. ?XA(X) P ? X(A(X) VP)d. ?XA(X) A ? X(A(X) AP)這里P是不含自由變?cè)猉的謂詞公式。9#前束范式<)X步驟6 :化為標(biāo)準(zhǔn)形(前束范式

18、)利用分配律：P V ( Q AR ) ? ( PVQ) A (P VR)P A (Q VR) ? (P AQ) V ( P AR)?將母式寫成由一些謂詞公式和(或)謂 詞公式的否定的析取的有限集組成的合 取，即合取范式。(?Xi )( ?X2)(?Xn ) MM是子句的合取式(母式)W前束范式形象描述為：上例：?X( (n P(x,f(x)VQ(x,g(x) A(n P(x,f(x)VR(XQ(:#驟8 :消去合取符“步驟7 :消去全稱量詞到此，所有余下的量詞均被全稱量詞化 了。且全稱量詞的次序也不重要了。因 此，可以消去前綴中全部全稱量詞。在合取范式中，每一個(gè)合取元，取出成 為一個(gè)獨(dú)立句子

19、。用子句集來代替原來 子句的合取(A )。每個(gè)子句實(shí)際上 是文字的析取。即用子句集A , B代替(A AB)#上例：(n P(x,f(x)VQ(x,g(x) ) A(n P(x,f(x) Vn R(x,g(x)上例：n P(x,f(x)VQ(x,g(x) ,(n P(x,f(x) Vn R(x,g(x)#定理F步驟9 :更換變?cè)O(shè)有謂詞公式F,其標(biāo)準(zhǔn)形的子句集為 S，則F不可滿足的充要條件是S不可滿使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上 的子句中。上例：n P(x,f(x)VQ(x,g(x), (n P(y,f(y)vn R(y,g(y)練習(xí)：(?x)P(x) T (?y)P(y) T P(f(x,

20、 y) A (? y) Q( x, y) - P(y)10#» 333歸結(jié)原理?基本思想：檢查子句集s中是否包含空子 句，若包含，則S不可滿足；若不包含， 就在子句集中選擇合適的子句進(jìn)行歸 結(jié)，一旦通過歸結(jié)能推出空子句，就說 明子句集S是不可滿足的。(pA p) T空子句(矛盾)反證法定義?若P是原子謂詞公式，則稱P與n P為互 補(bǔ)文字。?歸結(jié)過程：對(duì)兩個(gè)稱為親本子句的子句進(jìn)行歸 結(jié)。以產(chǎn)生一個(gè)新子句。歸結(jié)時(shí)，消去 母子句中的互補(bǔ)文字，并將二個(gè)子句中 余下的部分析取，構(gòu)成歸結(jié)式。?歸結(jié)式是其親本子句的邏輯結(jié)論。#假言三段論推理(P T Q) A(Q t R) ? (P VQ) A(

21、Q VR)合取范式 t子句集P VQ,Q VR ?歸結(jié)tP VR (即P t R)假言推理P A(P T Q) ? P A( P VQ)T子句集 P,P VQ T歸結(jié)Q1.命題邏輯中的歸結(jié)原理對(duì)公理集F,對(duì)命題S的歸結(jié)：1、把F的所有命題轉(zhuǎn)換成 子句型。2、把否定S的結(jié)果轉(zhuǎn)換成子句型。3、重復(fù)下述歸結(jié)過程，直到找出一個(gè)矛盾或不 能再歸結(jié)：(1) 挑選兩個(gè)親本子句進(jìn)行歸結(jié)。(2) 若歸結(jié)式為空子句，則F A n S不可滿 足。否則將原歸結(jié)式加入到該過程中的現(xiàn)有 子句集。11從公理集:(3 )歸結(jié)過程pVq Vrr舉例:p, (p 人q) f r,(s Vt) f q, t證明結(jié)果r(1 )把公理

22、集轉(zhuǎn)換成子句型 (p Aq) f r ? (p Aq) Vr ? p V q Vr (s Vt) f q ? (s Vt) Vq ? (sAt) Vq ? (s Vq) A(t Vq)這個(gè)合取式分為兩個(gè)子句： s Vq, t Vq這樣子句集為：p, pV q Vr, s Vq, t Vq, t(2)證明命題的非為 r?最后得到空語(yǔ)句，是矛盾的，故可得岀結(jié)論: 從公理集中可以推出r。12#土 2 .謂詞邏輯中的歸結(jié)原理科例叩i、任何能閱讀的人都是識(shí)字的。謂詞邏輯歸結(jié)思想和命題邏輯歸結(jié)一 樣，只是在尋找互補(bǔ)文字時(shí)，要進(jìn)行合 一算法，進(jìn)行變量置換。設(shè)：能閱讀的人R(x)，識(shí)字的人L(x)， 有：？x

23、R(x) f L(x)2、海豚不能識(shí)字設(shè)：海豚為D(x)，有： ？xD(x) f L(x)3、某些海豚是有智力的設(shè)：智力為I(x)有:?xD(x) AI (x)4、證明命題：某些有智力者不能閱讀?xI(x) A R(x)#|_對(duì)各謂詞公式化成子句型1、？xR(x) f L(x)(1) 化去 f”： ?x R(x) VL(x)(2) 去掉?x：R(x) VL(x)2、?xD(x) f L(x) 同樣可得到子句型： D(x) V L(x)換元：D(y)VL(y)3、?xD(x) AI(x)得到子句型：D(A)、1(A)4、目標(biāo)子句取非為：?xI(x) AR(x) 變?yōu)椋?？xl(x) AR(x) 變

24、為：？xl(x)V R(x) 即：?x l(x) VR(x) 去掉？ x，有子句：l(x) VR(x)換元：|(z) VR(z) 力口入子句集，子句集有：R(x) VL(x) D(y)V L(y) D(A)、I (A) l(z) VR(z)13#'科岸.3.4歸結(jié)反演?應(yīng)用歸結(jié)原理證明結(jié)論為真的過程稱為歸 結(jié)反演。?將目標(biāo)的否定加入公式集，歸結(jié)的結(jié)果是空子句，弓I出矛盾證明此目標(biāo)是正確的。I(A) I(A)結(jié)：l(z) VR(z) R(x) VL(x)/zx I (z) VL(z)D(y)VL(y) / z yI (z)V D(z) D(A) z Az證明目標(biāo)正14#3.3.5基于歸結(jié)反演的問題求解現(xiàn)在要求一個(gè)問題的解答時(shí)，仍可用歸 結(jié)方法來實(shí)現(xiàn)。q I求取答案的歸結(jié)過程(i)把目標(biāo)公式的否定和目標(biāo)公式一起構(gòu)成一 個(gè)析取式加入到原始子句集中去。(2 )執(zhí)行和以前相同的歸結(jié)，直到在根部得到 某個(gè)字句為止。(3)用最后的字句作為該問題的回答。以上過程中，由于把目標(biāo)公式加入原始子 句集中，故