.,1,第章經(jīng)典邏輯推理、基本概念、自然演繹推理、歸結(jié)演繹推理、與或形演繹推理,.,2,基本概念,何為推理？從已知的事實(shí)出發(fā)，不斷運(yùn)用已掌握的（知識(shí)庫(kù)中的）知識(shí)推出或歸納出新的事實(shí)（包括目標(biāo)結(jié)論）的過(guò)程稱(chēng)為推理。人工智能中推理是由程序?qū)崿F(xiàn)的，稱(chēng)這個(gè)程序?yàn)橥评頇C(jī)。,.,3,推理方式及其分類(lèi),人工智能作為對(duì)人類(lèi)智能的模擬，有多種推理方式。它們是：、演繹推理、歸納推理、默認(rèn)推理、確定性推理、不確定性推理、單調(diào)推理、非單調(diào)推理、啟發(fā)式推理、非啟發(fā)式推理、基于知識(shí)的推理、統(tǒng)計(jì)推理、直覺(jué)推理。分別解釋如下：,.,4,、演繹推理、歸納推理、默認(rèn)推理,所謂演繹推理是從全稱(chēng)判斷推導(dǎo)出特稱(chēng)判斷的過(guò)程，是從一般到個(gè)別的推理。經(jīng)常用的是三段論式，它包括：大前提：已知的一般性知識(shí)或假設(shè)；小前提：具體情況或個(gè)別事實(shí)；結(jié)論：由大前提推出的適合小前提所示情況的新判斷。,.,5,、演繹推理、歸納推理、默認(rèn)推理,例如有如下三個(gè)判斷：（）足球運(yùn)動(dòng)員的身體都是強(qiáng)壯的；（）高波是一名足球運(yùn)動(dòng)員；（）所以，高波的身體是強(qiáng)壯的。其中（）是大前提，（）是小前提（）是經(jīng)演繹推出的結(jié)論。只要大前提和小前提是正確的，那麼由它們推出的結(jié)論就是正確的。,.,6,、演繹推理、歸納推理、默認(rèn)推理,演繹推理是人工智能中的一種重要推理方式，目前研制成功的各類(lèi)智能系統(tǒng)中，大多是用演繹推理實(shí)現(xiàn)的。,.,7,、演繹推理、歸納推理、默認(rèn)推理,歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推理過(guò)程，是一種從個(gè)別到一般的推理。例如，某廠進(jìn)行產(chǎn)品質(zhì)量檢查，如果對(duì)每一件產(chǎn)品都進(jìn)行了檢查，并且都是合格的，則推導(dǎo)出結(jié)論：該廠生產(chǎn)的產(chǎn)品是合格的。并稱(chēng)這種推理為完全歸納推理。,.,8,、演繹推理、歸納推理、默認(rèn)推理,如果是隨機(jī)地抽查部分產(chǎn)品，并且它們是合格的，則得出結(jié)論該廠的產(chǎn)品是合格的，這種推理稱(chēng)為不完全歸納推理。默認(rèn)推理又稱(chēng)為缺省推理，它是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。例如，在條件已成立的情況下，如果沒(méi)有足夠的證據(jù)能證明條件不成立，則默認(rèn)成立，并在默認(rèn)前提下進(jìn)行推理，推導(dǎo),.,9,、演繹推理、歸納推理、默認(rèn)推理,出某個(gè)結(jié)論來(lái)。由于這種推理允許默認(rèn)某些條件是成立的，這就擺脫了需要知道全部有關(guān)事實(shí)才能進(jìn)行推理的要求，使得在知識(shí)不完全的情況下也能進(jìn)行推理。在默認(rèn)推理過(guò)程中，如果到某一時(shí)刻發(fā)現(xiàn)原先所做的默認(rèn)不正確，則可以撤消默認(rèn)推理和所推出的結(jié)論，并重新按新情況進(jìn)行推理。,.,10,、確定性推理、不確定性推理,所謂確定性推理是指推理時(shí)所用的知識(shí)都是精確的，推出的結(jié)論也是確定的，是真或者是假。經(jīng)典邏輯推理就屬于這一種。不確定性推理是指推理時(shí)所用的知識(shí)不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于真與假之間，命題的外延模糊不清。,.,11,、確定性推理、不確定性推理,這里，我們特別強(qiáng)調(diào)的是不確定性推理。因?yàn)?，人?lèi)思維活動(dòng)的特征經(jīng)常是在知識(shí)不完全的情況下進(jìn)行多方位的思考及推理的。因此，要使計(jì)算機(jī)模擬人類(lèi)的思維活動(dòng)，就必須使它具有不確定性推理的能力。,.,12,、單調(diào)推理、非單調(diào)推理,所謂單調(diào)推理是指在推理的過(guò)程中隨著推理的向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論是單調(diào)遞增的趨勢(shì)，并且越來(lái)越接近目標(biāo)，推理過(guò)程不會(huì)出現(xiàn)反復(fù)的情況，即不會(huì)因新知識(shí)的加入否定了前面推出的結(jié)論，從而使推理又退回到前面的某一步。經(jīng)典邏輯演繹推理屬于這一種。,.,13,、啟發(fā)式推理、非啟發(fā)式推理,若按推理中是否使用與問(wèn)題有關(guān)的啟發(fā)性知識(shí)，推理可分為啟發(fā)式推理和非啟發(fā)式推理。所謂啟發(fā)性知識(shí)是指與問(wèn)題有關(guān)并且能加快推理進(jìn)程、求得問(wèn)題最優(yōu)解的知識(shí)。,.,14,、基于知識(shí)的推理、統(tǒng)計(jì)推理、直覺(jué)推理,如果從方法論的角度來(lái)劃分，推理可分為基于知識(shí)的推理、統(tǒng)計(jì)推理和直覺(jué)推理。顧名思義，所謂基于知識(shí)的推理就是根據(jù)已掌握的事實(shí)，通過(guò)運(yùn)用知識(shí)進(jìn)行推理。統(tǒng)計(jì)推理是根據(jù)對(duì)某事物的數(shù)據(jù)統(tǒng)計(jì)進(jìn)行推理。例如，對(duì)農(nóng)作物的產(chǎn)量進(jìn)行統(tǒng)計(jì)，從而得出是否增產(chǎn)的結(jié)論，從而找,.,15,、基于知識(shí)的推理、統(tǒng)計(jì)推理、直覺(jué)推理,出增產(chǎn)和減產(chǎn)的原因。就是運(yùn)用了統(tǒng)計(jì)推理。直覺(jué)推理又稱(chēng)常識(shí)性推理，是根據(jù)常識(shí)進(jìn)行的推理。例如，當(dāng)你從某建筑物下走過(guò)時(shí)，猛然發(fā)現(xiàn)有一物體墜落，這時(shí)你立即就會(huì)意識(shí)到這有危險(xiǎn)，并立即躲開(kāi)，這就是使用了直覺(jué)推理。目前直覺(jué)推理在計(jì)算機(jī)上的實(shí)現(xiàn)還是一件很困難的工作。,.,16,推理的控制策略,推理的控制策略主要包括推理方向、搜索策略、沖突消解策略、求解策略及限制策略等。推理方向用于確定推理的驅(qū)動(dòng)方式，分為正向推理、逆鄉(xiāng)向推理、混合推理及雙向推理四種。,.,17,正向推理,正向推理也稱(chēng)數(shù)據(jù)驅(qū)動(dòng)推理，前向鏈推理、模式制導(dǎo)推理及前件推理等。正向推理過(guò)程的算法描述如下：、將用戶(hù)提供的初始已知事實(shí)送入數(shù)據(jù)庫(kù)DB;2、檢查數(shù)據(jù)庫(kù)DB中是否包含問(wèn)題的解，若有則求解結(jié)束，成功退出；否則執(zhí)行下一步；,.,18,正向推理,根據(jù)數(shù)據(jù)庫(kù)DB中的已知事實(shí)，掃描知識(shí)庫(kù)KB，檢查KB中是否有可適用的知識(shí)，若有則轉(zhuǎn)，否則轉(zhuǎn)；把KB中所有的適用知識(shí)都選出來(lái)，構(gòu)成可適用的知識(shí)集KS；若KS不空，則按某種沖突消解策略從中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入DB中，然后轉(zhuǎn)；若KS空，轉(zhuǎn)；,.,19,正向推理,詢(xún)問(wèn)用戶(hù)是否可以進(jìn)一步補(bǔ)充新的事實(shí)，若可補(bǔ)充，則將補(bǔ)充的事實(shí)加入DB中，轉(zhuǎn)，否則表示求不出解，失敗退出算法的流程示意圖如115的圖所示為了實(shí)現(xiàn)正向推理，還有很多實(shí)際問(wèn)題需要解決，后面將陸續(xù)介紹,.,20,逆向推理,逆向推理的思想是首先假設(shè)一個(gè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說(shuō)明假設(shè)是成立的；若實(shí)在找不到證據(jù)時(shí)，說(shuō)明原假設(shè)不成立，此時(shí)需另做假設(shè)推理過(guò)程的算法如下所示,.,21,逆向推理,提出要求證的目標(biāo)（假設(shè)目標(biāo)）；檢查該目標(biāo)是否已在數(shù)據(jù)庫(kù)中，若在，則該目標(biāo)成立，成功退出或者對(duì)下一目標(biāo)進(jìn)行檢驗(yàn)；否則，轉(zhuǎn)下一步；判斷該目標(biāo)是否是證據(jù)，即它是否是由用戶(hù)證實(shí)的原始事實(shí)，若是，則詢(xún)問(wèn)用戶(hù)；否則轉(zhuǎn)下一步在知識(shí)庫(kù)中找出所有能導(dǎo)出該目標(biāo)的知識(shí)，形成適用知識(shí)集KS，轉(zhuǎn)下一步；,.,22,逆向推理,從KS中選出一條知識(shí)，并將該知識(shí)的運(yùn)用條件作為新的假設(shè)目標(biāo)，然后轉(zhuǎn)算法的示意圖如116的圖所示,.,23,雙向推理,混合推理就是在推理過(guò)程中合理地使用正向推理和逆向推理混合推理的算法示意圖如P11的圖所示,.,24,求解策略和限制策略,所謂推理的求解策略是指只求一個(gè)解還是求所有解和最優(yōu)解等為了防止無(wú)窮的推理過(guò)程,以及由于推理過(guò)程太長(zhǎng)增加時(shí)間及空間的復(fù)雜性，可在控制策略中指定推理的限制條件，以對(duì)推理的深度、寬度、時(shí)間、空間等限制。,.,25,模式匹配,模式匹配是推理中必須進(jìn)行的一項(xiàng)重要工作，因?yàn)橹挥薪?jīng)過(guò)模式匹配才能從知識(shí)庫(kù)中選出當(dāng)前適用的知識(shí)，才能進(jìn)行推理。模式匹配可以有確定性匹配和不確定性匹配良種。所謂確定性匹配是指兩個(gè)模式完全一樣，或者通過(guò)代換后變得完全一致。所謂不確定性匹配是指兩個(gè)知識(shí)模式不完全一樣，但從總體上看它們的相似程度又落在規(guī)定的限度內(nèi)。無(wú)論是確定性匹配還是不確定性匹配都需要進(jìn)行變量的代換。,.,26,模式匹配,例如設(shè)有如下兩個(gè)知識(shí)模式：1:father(李四，李小四）andman(李小四)2:father(x,y)andman(y)若用李四代換x,用李小四代換y，則1與就變得完全一樣若用這兩個(gè)知識(shí)模式進(jìn)行匹配，則是確定性匹配，也稱(chēng)完全匹配或精確匹配,.,27,模式匹配,下面我們給出代換的概念：代換是形如t1/x1,t2/x2,tn/xn的有限集合。其中，t1，t2，,tn是項(xiàng)，x1.，x2,xn是互不相同的變?cè)?；ti/xi表示用項(xiàng)ti代換變量xi，不允許ti和xi相同，也不允許xi循環(huán)的出現(xiàn)在另一個(gè)tj中。,.,28,模式匹配,什麼是項(xiàng)呢？?？梢宰黜?xiàng)，變量也可以作項(xiàng)，函數(shù)表達(dá)式可以作項(xiàng)。,.,29,模式匹配,例如a/x,f(b)/y,w/z就是一個(gè)代換，但是g(y)/x,f(x)/y則不是一個(gè)代換，因?yàn)榇鷵Q的目的是使某些變?cè)涣硗獾淖冊(cè)?、常量、或函?shù)表達(dá)式取代，使之不再在公式中出現(xiàn)，而g(y)/x,f(x)/y在x與y之間出現(xiàn)了循環(huán)代換的情況，它既沒(méi)有消去x,也沒(méi)有消去y。,.,30,模式匹配,如果把它改為g(a)/x,f(x)/y就可以了，它將把公式中的x代換成g(a),y代換成f(g(a),從而消去了變量x和y。,.,31,模式匹配,下面給出一個(gè)公式的代換例式的概念：設(shè)F是一個(gè)公式，是一個(gè)代換，記F為公式F在下的代換例式，它是將公式F中的變量用中的項(xiàng)作代換的結(jié)果。例如有公式（x,y,f(y)和代換=a/x,b/y于是F=（a,b,f(b),.,32,模式匹配,下面給出復(fù)合代換的定義設(shè)有兩個(gè)代換和，其中=t1/x1,t2/x2,tn/xn=u1/y1,u2/y2,um/ym則此兩個(gè)代換的復(fù)合也是一個(gè)代換，它是從t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,um/ym中刪去如下兩種元素：ti/xi當(dāng)ti=xi時(shí)ui/yi當(dāng)yix1.，x2,xn時(shí)，后剩下的元素構(gòu)成的集合，記為。,.,33,模式匹配,例如設(shè)有如下代換：=f(y)/x,z/y=a/x,b/y,y/z求和解：我們先來(lái)求,.,34,模式匹配,=f(y)/x,z/y,a/x,b/y,y/z=f(b)/x,y/y,a/x,b/y,y/z去掉不合法的元素：y/y（條件）a/x,b/y（條件）于是f(b)/x,y/z,.,35,模式匹配,再來(lái)求，同樣先求a/x,b/y,y/z,f(y)/x,z/y=a/x,b/y,z/z,f(y)/x,z/y去掉不合法的元素z/z,f(y)/x,z/y得=a/x,b/y顯然代換的復(fù)合運(yùn)算是不可交換的。并且對(duì)任何代換存在空代換，并且,.,36,模式匹配,下面我們給出合一的概念：設(shè)有公式集F=F1，F(xiàn)2，,Fn,若存在一個(gè)代換使得F1=F2=Fn則稱(chēng)為公式集F的一個(gè)合一，且稱(chēng)F1，F(xiàn)2，,Fn是可合一的。,.,37,模式匹配,例如F=P（x,y),=a/x,g(a)/y求公式F在下的例式為F=P（a,g(a)對(duì)于公式集F=P（x,y，f(y),P(a,g(x),z)則=a/x,g(a)/y，f(g(a)/z是公式F的一個(gè)合一。,.,38,模式匹配,一個(gè)公式的合一一般是不唯一的。但如果是公式集F的一個(gè)合一，若對(duì)任一個(gè)合一都存在一個(gè)代換使得：=則稱(chēng)是一個(gè)最一般合一。,.,39,模式匹配,最一般合一是唯一的。若用最一般合一去代換那些可合一的謂詞公式，可使它們變成完全一致的公式。由此可知，為了使兩個(gè)知識(shí)模式匹配，可用其最一般合一對(duì)它們進(jìn)行代換。,.,40,模式匹配,為了求最一般合一要用到一個(gè)差異集（也有叫分歧集的）的概念。設(shè)有如下兩個(gè)謂詞公式F1：P(x,y,z)F2:P(x,f(a),h(b)分別從F1與F2的第一個(gè)符號(hào)開(kāi)始，逐個(gè)向右比較，此時(shí)發(fā)現(xiàn)F1中的y與F2中的f(a)不同，它們構(gòu)成了一個(gè)差異集：D1=y,f(a),.,41,模式匹配,當(dāng)繼續(xù)向右比較時(shí)，又發(fā)現(xiàn)F1中與F2中的h(b)不同，于是又得到一個(gè)差異集：D2=z,h(b)。下面給出求最一般合一的算法：（1）令K=0，F(xiàn)k=F,k=這里，F(xiàn)是欲求其最一般合一的公式集，是空代換，它表示不做代換。（2）若Fk只含一個(gè)表達(dá)式，則算法停，k就是所求最一般合一。,.,42,模式匹配,（3）找出Fk的差異集Dk。（4）若Dk中存在元素xk和tk,其中xk是變?cè)?，tk是項(xiàng),且xk不在tk中出現(xiàn)，則置：k+1=ktk/xkFk+1=Fktk/xkK=k+1轉(zhuǎn)（2）（5）算法停，F(xiàn)的最一般合一不存在。,.,43,模式匹配,例如，設(shè)F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一(1)令0=,F0=F,因F0中含有兩個(gè)表達(dá)式，所以0不是最一般合一。(2)差異集D0=a,z,(3)1=0a/z,F1=P(a,x,f(g(y),P(a,f(a),f(u),.,44,模式匹配,(4)D1=x,f(a)(5)2=1f(a)/x=a/z,f(a)/x,F2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u)。(6)D2=g(y),u。(7)3=2g(y)/u=a/z,f(a)/x,g(y)/u。,.,45,模式匹配,(8)F3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y)/u)=P(a,f(a),f(g(y)因?yàn)镕3只含一個(gè)表達(dá)式了，所以3就是最一般合一，即a/z,f(a)/x,g(y)/u是最一般合一。,.,46,沖突消解策略,接下來(lái)我們學(xué)習(xí)沖突消解方面的概念：在推理的過(guò)程中，系統(tǒng)不斷的用以知的事實(shí)與知識(shí)庫(kù)中的知識(shí)進(jìn)行匹配，此時(shí)可能發(fā)生如下三種情況：（1）已知事實(shí)不能與知識(shí)庫(kù)中的任何知識(shí)匹配成功。（2）已知事實(shí)恰好與知識(shí)庫(kù)中的一條知識(shí)匹配成功。,.,47,沖突消解策略,（3）已知事實(shí)可與知識(shí)庫(kù)中的多條知識(shí)匹配成功。以上三種情況中，第一種情況使得推理無(wú)法進(jìn)行下去，第三種情況則出現(xiàn)沖突，需要按一定的策略解決沖突。,.,48,沖突消解策略,目前解決沖突的策略有多種，其基本思想都是對(duì)知識(shí)進(jìn)行排序，常用的有以下幾種：1、按針對(duì)性排序設(shè)有如下兩條產(chǎn)生式規(guī)則：r1:IFA1andA2andAnTHENH1r2:IFB1andB2andBmTHENH2,.,49,沖突消解策略,如果存在最一般合一，使得r1中每一個(gè)Ai都可變成相應(yīng)的Bi，即r2中除了包含r1的全部條件A1,A2,An外，還包含其它條件，則稱(chēng)r2比r1有更大的針對(duì)性，r1比r2有更大的通用性。一般選用針對(duì)性較強(qiáng)的產(chǎn)生式規(guī)則。(即應(yīng)選用r2)因?yàn)樗蟮臈l件較多，其結(jié)論一般更接近目標(biāo)，一旦得到滿(mǎn)足，可縮短推理過(guò)程。,.,50,沖突消解策略,2、按已知事實(shí)的新鮮性排序在產(chǎn)生式系統(tǒng)推理過(guò)程中，每應(yīng)用一條產(chǎn)生式規(guī)則就會(huì)得到一個(gè)或多個(gè)結(jié)論，數(shù)據(jù)庫(kù)就會(huì)增加新的事實(shí)。把數(shù)據(jù)庫(kù)后生成的事實(shí)稱(chēng)為新鮮的事實(shí)，即后生成的事實(shí)比先生成的事實(shí)具有較大的新鮮性。設(shè)規(guī)則r1可與事實(shí)組A匹配成功，規(guī)則r2可與事實(shí)組B匹配成功，則A與B中哪一組新鮮與它匹配的產(chǎn)生式規(guī)則就先被應(yīng)用。,.,51,沖突消解策略,3、按匹配排序在不確定性匹配中，為了確定兩個(gè)知識(shí)模式是否可以匹配，需要計(jì)算這兩個(gè)模式的相似程度，當(dāng)其相似程度達(dá)到某個(gè)預(yù)定的值時(shí)，就認(rèn)為它們是可匹配的。若兩條規(guī)則均按匹配度匹配成功，則匹配度大的那條規(guī)則優(yōu)先啟用。,.,52,沖突消解策略,4、根據(jù)領(lǐng)域問(wèn)題的特點(diǎn)排序某些領(lǐng)域問(wèn)題可事先知道它的某些特性，可根據(jù)這些特性把知識(shí)排成固定的順序。先匹配成功的優(yōu)先啟用的原則。,.,53,沖突消解策略,5、按上下文限制排序把產(chǎn)生式規(guī)則按它們所描述的上下文分成若干組，在不同的條件下，只能從相應(yīng)的組中選取有關(guān)的產(chǎn)生式規(guī)則。這樣可以減少?zèng)_突的發(fā)生,.,54,沖突消解策略,6、按冗余限制排序若哪一條產(chǎn)生式規(guī)則被應(yīng)用后產(chǎn)生冗余知識(shí)，則就降低它被應(yīng)用的優(yōu)先級(jí)。7、按條件個(gè)數(shù)排序如果有多條產(chǎn)生式規(guī)則生成的結(jié)論相同，則要求條件少的產(chǎn)生式規(guī)則被優(yōu)先應(yīng)用。,.,55,4.2自然演繹推理,從一組已知的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯推理規(guī)則推出結(jié)論的過(guò)程稱(chēng)為自然演繹推理。其中，基本的推理規(guī)則是P規(guī)則、T規(guī)則、假言推理、拒取式推理等。假言推理的一般形式是P，PQQ拒取式的一般形式是PQ，QP,.,56,4.2自然演繹推理,以下是自然演繹推理的例子：例1：A，B，AC，BCD，DQQ1、AP規(guī)則2、ACP規(guī)則3、CT規(guī)則1和24、BP規(guī)則5、BCT規(guī)則3和4,.,57,4.2自然演繹推理,6、BCDP規(guī)則7、DT規(guī)則5和68、DQP規(guī)則9、QT規(guī)則7和8問(wèn)題得證,.,58,4.2自然演繹推理,例2設(shè)已知如下事實(shí)；（1）凡是容易的課程小王（Wang)都喜歡。（2）C班的課程都是容易的。（3）ds是C班的一門(mén)課程求證小王喜歡ds這門(mén)課程。,.,59,4.2自然演繹推理,證明：首先定義謂詞如下：Easy（x):x是容易的Like（x,y):x喜歡yC（x):x是C班的一門(mén)課程于是問(wèn)題可以表示成：,.,60,4.2自然演繹推理,x(Easy(x)Like(Wang,x)x(C(x)Easy(x)C(ds)Like（Wang,ds).,.,61,4.2自然演繹推理,1、x(Easy（x)Like（Wang,x)P規(guī)則2、Easy（ds)Like（Wang,ds)US規(guī)則和13、x(C（x)Easy（x)P規(guī)則4、C（ds)Easy（ds)US規(guī)則和35、C（ds)Like（Wang,ds)T規(guī)則2和46、C（ds)P規(guī)則7、Like（Wang,ds)T規(guī)則5和6即小王喜歡ds這門(mén)課程,.,62,4.2自然演繹推理,自然演繹推理的優(yōu)點(diǎn)是表達(dá)定理證明過(guò)程自然，容易理解，擁有豐富的推理規(guī)則，推理過(guò)程靈活，便于在推理過(guò)程中嵌入領(lǐng)域啟發(fā)知識(shí)。缺點(diǎn)是容易產(chǎn)生組合爆炸，推理過(guò)程中得到的中間結(jié)論一般呈指數(shù)形式遞增，這對(duì)于一個(gè)大型推理問(wèn)題是十分不利的，甚至是不可能實(shí)現(xiàn)的。,.,63,4.3歸結(jié)演繹推理,定理證明是人工智能的一個(gè)重要研究領(lǐng)域，這不僅僅是因?yàn)樵S多數(shù)學(xué)問(wèn)題要通過(guò)定理證明得以解決，很多非數(shù)學(xué)問(wèn)題（如醫(yī)療診斷、機(jī)器人規(guī)劃及難題求解等）也都?xì)w結(jié)為一個(gè)定理證明問(wèn)題。定理證明的實(shí)質(zhì)是對(duì)前提P和結(jié)論Q證明PQ的永真性。但是證明一個(gè)謂詞公式的永真性不像證明一個(gè)命題公式的永真性那麼簡(jiǎn)單，（它牽涉到謂詞變量、客體變量及函數(shù)符號(hào)）在某些情況下甚至是行不通的。,.,64,4.3歸結(jié)演繹推理,在這種情況下，人們提出了用反證法來(lái)解決問(wèn)題的思路。在這方面，海伯倫和魯賓遜都作出了杰出的貢獻(xiàn)。兩人的研究都是以子句集為背景展開(kāi)的。接下來(lái)，我們介紹這些概念。,.,65,4.3歸結(jié)演繹推理,子句：在謂詞邏輯中，稱(chēng)原子謂詞公式及其否定為文字；任何文字的析取式為子句。例如，P(x)Q(x),P(x,f(x)Q(x,g(x)都是子句。而P(x)、Q(x,g(x)、P(x,f(x)等都是文字。并把不包含任何文字的子句稱(chēng)為空子句。,.,66,4.3歸結(jié)演繹推理,由于空子句不包含任何文字，它不能被任何解釋所滿(mǎn)足，所以空子句是永假的，不可滿(mǎn)足的。由子句構(gòu)成的集合稱(chēng)為子句集。在謂詞邏輯中任何一個(gè)謂詞公式均可通過(guò)等價(jià)變換化為相應(yīng)的子句集。,.,67,4.3歸結(jié)演繹推理,化子句集的步驟如下：1、利用等價(jià)公式消去公式中的邏輯連接詞“”和“”：PQPQPQ（PQ）（PQ）,.,68,4.3歸結(jié)演繹推理,2、利用下列公式將否定符號(hào)“”深入到單個(gè)變?cè)癙P（PQ）PQ（PQ）PQ(x)P(x)P(x)P(x)P,.,69,4.3歸結(jié)演繹推理,3、重新命名變?cè)?，使不同量詞約束的變?cè)胁煌拿?、消去存在量詞。分兩種情況處理：一種情況是存在量詞不出現(xiàn)在全稱(chēng)量詞的轄域內(nèi)，此時(shí)只要用一個(gè)新的個(gè)體常量替換受該存在量詞約束的變?cè)涂上ゴ嬖诹吭~；另一種情況是存在量詞位于一個(gè)或多個(gè)全稱(chēng)量詞的轄域內(nèi)，例如（x1)（x2)(xn)(y)P(x1,x2,xn,y)此時(shí)需要用Skolem函數(shù)f(x1,x2,xn)替換受該存在量詞約束的變?cè)?，然后才能消去存在量詞。,.,70,4.3歸結(jié)演繹推理,5、把全稱(chēng)量詞全部移到公式的左邊。6、利用等價(jià)關(guān)系P(QR)=(PQ)(PR)把公式化為Skolem標(biāo)準(zhǔn)型。,.,71,4.3歸結(jié)演繹推理,Skolem標(biāo)準(zhǔn)型的一般形式是：（x1)（x2)(xn)M其中，M是子句的合取式，稱(chēng)為Skolem標(biāo)準(zhǔn)型的母式。7、消去全稱(chēng)量詞8、對(duì)變?cè)?，使不同子句中的變?cè)煌?.,72,4.3歸結(jié)演繹推理,9、消去合取連接詞，變?yōu)樽泳浼Ｗ泳浼懈髯泳渲g是合取關(guān)系。謂詞公式是不可滿(mǎn)足的，則其子句集合是不可滿(mǎn)足的，反之亦然。,.,73,海伯倫理論,如何證明一個(gè)子句集是不可滿(mǎn)足的呢？下面就海伯倫理論和魯賓遜的歸結(jié)原理進(jìn)行討論。一、海伯倫理論要判定一個(gè)子句集是否是不可滿(mǎn)足的，需要對(duì)子句集中的謂詞公式進(jìn)行判定，而謂詞公式的判定需要對(duì)個(gè)體域上的任何解釋進(jìn)行判定，這是很困難的。,.,74,海伯倫理論,海伯倫定義了一個(gè)特殊的域稱(chēng)為海伯倫域，在任何域上的判定，只要在海伯倫域上進(jìn)行即可。*設(shè)S是子句集，則按下述方法構(gòu)造的域H稱(chēng)為是海伯倫域：,.,75,海伯倫理論,1、令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則令H0=a，其中a為任意指定的一個(gè)個(gè)體常量。2、令Hi+1=HiS中所有n元函數(shù)f(x1,x2,xn)|xj(j=1,2,n)是Hi中的元素，其中，i=0,1,。下面通過(guò)例子來(lái)解釋這個(gè)定義。,.,76,海伯倫理論,例1求子句集S=P(x)Q(x),R(f(y)的H域。解：因?yàn)镾中沒(méi)有個(gè)體常量，所以指定a作為個(gè)體常量，于是得到：H0=a,H1=a,f(a),H2=a,f(a),f(f(a),H=a,f(a),f(f(a)，f(f(f(a),H=a,f(a),f(f(a),.,77,海伯倫理論,例2求子句集S=P(a),Q(b),R(f(x)的H域解：根據(jù)H域的定義得到：H0=a,bH1=a,b,f(a),f(b)H2=a,b,f(a),f(b),f(f(a),f(f(b),.,78,海伯倫理論,例3：求子句集S=P(x),Q(y)R(y)的H域。解：由于該子句集中既無(wú)個(gè)體常量，又無(wú)函數(shù)，所以可任意指定一個(gè)常量a作為個(gè)體常量，從而得到H0=H1=H=a有定理說(shuō)：子句集S是不可滿(mǎn)足的充要條件是S對(duì)H域上的一切解釋都為假。并且海伯倫證明了若子句集S在任何域D上的解釋能滿(mǎn)足S，則在H域上相應(yīng)的解釋也能滿(mǎn)足S。下面我們說(shuō)明，S在H域上解釋的定義：,.,79,海伯倫理論,子句集S在H域上的一個(gè)解釋滿(mǎn)足下列條件：1、在解釋I下，常量映射到自身；2、S中的任一個(gè)n元函數(shù)是HnH的映射。即，設(shè)h1,h2,hnH,則f(h1,h2,hn)H;,.,80,海伯倫理論,3、S中的任一n元謂詞是HnT，F(xiàn)的映射。即謂詞的真值可以指派T也可指派F。海伯倫在理論上證明了子句集不可滿(mǎn)足性的可行性及方法，但要在計(jì)算機(jī)上實(shí)現(xiàn)其證明過(guò)程還是很困難的。1965年魯賓遜提出了歸結(jié)原理，使機(jī)器證明成為現(xiàn)實(shí),.,81,魯賓遜歸結(jié)原理,歸結(jié)原理也稱(chēng)消解原理，是魯賓遜提出的一種證明子句不可滿(mǎn)足性，從而實(shí)現(xiàn)定理證明的一種理論及方法。由謂詞公式轉(zhuǎn)化為子句集的過(guò)程可以看出，在子句集中子句之間的關(guān)系是合取關(guān)系，其中只要有一個(gè)子句不可滿(mǎn)足，則子句集就不可滿(mǎn)足。前面，我們?cè)?jīng)說(shuō)過(guò)空子句是不可滿(mǎn)足的，即一個(gè)子句集中若含空子句，則它是不可滿(mǎn)足的。,.,82,魯賓遜歸結(jié)原理,歸結(jié)原理的基本思想就是檢查子句集中是否含空子句，若含，則子句集S不可滿(mǎn)足，或說(shuō)證明一個(gè)謂詞公式是永假的過(guò)程，就是歸結(jié)由此公式轉(zhuǎn)換成的子句集包含空子句的過(guò)程。,.,83,魯賓遜歸結(jié)原理,下面我們先來(lái)說(shuō)明命題邏輯中的歸結(jié)原理定義P是原子謂詞公式，則稱(chēng)P與P為互補(bǔ)文字。我們知道在命題邏輯中有公式：PQ,QRPR即PQ，QRPRc1c2c12,.,84,魯賓遜歸結(jié)原理,顯然上述公式向我們展示的是在子句c1中存在文字Q，在子句c2中存在Q的補(bǔ)文字Q，把這一對(duì)互補(bǔ)文字消去，剩下的文字析取起來(lái)就是子句c1和c2的邏輯結(jié)果c12。并稱(chēng)c12是c1和c2的歸結(jié)式，c1和c2則稱(chēng)為c12的親本子句。,.,85,魯賓遜歸結(jié)原理,例如：1、C1=PQRC2=QS它們的歸結(jié)式c12為PRS2、C1=PC2=P它們的歸結(jié)式c12為NIL即空子句。,.,86,魯賓遜歸結(jié)原理,3、C1=PQC2=QRC3=P它們的歸結(jié)式c123為R。其歸結(jié)過(guò)程可以用下面的一個(gè)樹(shù)形結(jié)構(gòu)很清楚的表現(xiàn)出來(lái)。,.,87,魯賓遜歸結(jié)原理,PQQRPRPR歸結(jié)過(guò)程的樹(shù)形表示圖,.,88,魯賓遜歸結(jié)原理,由命題邏輯中的歸結(jié)原理可以得出如下的推論：設(shè)c1與c2是子句集S中的兩個(gè)子句，c12是它們的歸結(jié)式,若用c12代替c1和c2后得到新子句集S1，則由S1的不可滿(mǎn)足性可以推出S的不可滿(mǎn)足性。這個(gè)定理告訴我們，證明子句集S的不可滿(mǎn)足性問(wèn)題，可以轉(zhuǎn)化成證子句集S1的不可滿(mǎn)足性問(wèn)，直到從子句集Sn中推出一個(gè)空子句來(lái)。,.,89,魯賓遜歸結(jié)原理,在謂詞邏輯中，由于子句中含有變?cè)?，所以不象命題邏輯中那樣可以直接消去互補(bǔ)文字，而先要用最一般合一對(duì)變?cè)M(jìn)行代換。然后才能進(jìn)行歸結(jié)。前面我們已經(jīng)介紹過(guò)最一般合一的概念，下面給出謂詞邏輯中二元?dú)w結(jié)式的概念。,.,90,魯賓遜歸結(jié)原理,設(shè)C1與C2是兩個(gè)沒(méi)有公共變量的子句，L1和L2分別是C1與C2中的文字，若是L1和L2的最一般合一，則稱(chēng)C12=（C1-L1）（C2-L2）為C1與C2的二元?dú)w結(jié)式，L1和L2稱(chēng)為歸結(jié)式上的文字。例子見(jiàn)P132頁(yè)的例4.10和例4.11。,.,91,魯賓遜歸結(jié)原理,例如設(shè)C1=P(a)Q(x)R(x)C2=P(y)Q(b)若選L1=P(a),L2=P(y),則=a/y是L1與L2的最一般合一于是有C12=(C1-L1)(C2-L2)=Q(x)R(x)Q(b)=Q(x),R(x),Q(b).,.,92,魯賓遜歸結(jié)原理,若選L1=Q(x),L2=Q(b),則=b/x是L1與L2的最一般合一于是有C12=(C1-L1)(C2-L2)=Q(x)R(x)Q(b)=P(a),R(b),P(y).,.,93,魯賓遜歸結(jié)原理,再例如設(shè)有如下子句：1=P(x)Q(a),2=P(b)R(x)由于1和2有相同的變?cè)环隙獨(dú)w結(jié)式中定義中對(duì)子句1和2的要求為了歸結(jié)的需要，要修改2中變?cè)拿?.,94,魯賓遜歸結(jié)原理,令2=P(b)R(y),此時(shí)，1=P(x),2=P(b),它們的最一般合一為b/x.于是有C12=(P(b),Q(a)P(b),)(P(b)R(y),-P(b)=Q(a),R(y).如果在參加歸結(jié)的子句內(nèi)部有可合一的文字，則在歸結(jié)之前應(yīng)先對(duì)這些文字合一，見(jiàn)下例：,.,95,魯賓遜歸結(jié)原理,設(shè)有子句：C1=P(x)P(f(a)Q(x)C2=P(y)R(b)由于在C1中有可合一文字P(x)和P(f(a)，若用它們的最一般合一f(a)/x進(jìn)行代換，得到C1=P(f(a)Q(f(a)此時(shí)可對(duì)C1和C2進(jìn)行歸結(jié)，從而的到C1和C2的二元?dú)w結(jié)式對(duì)C1和C2分別選1=P(f(a),2=P(y),它們的最一般合一是,.,96,魯賓遜歸結(jié)原理,f(a)/y于是可得它們的歸結(jié)式為：C12(b)Q(f(a)上例中稱(chēng)C1為C1因子，如果C1是一個(gè)單文字，則稱(chēng)它為C1的單元因子應(yīng)用因子的概念，可對(duì)謂詞邏輯中的歸結(jié)原理給出如下的定義,.,97,魯賓遜歸結(jié)原理,定義；子句1和的歸結(jié)式是下列二元?dú)w結(jié)式之一：(1)1和的二元?dú)w結(jié)式；(2)1和的因子2的二元?dú)w結(jié)式；(3)的因子11和的二元?dú)w結(jié)式；(4)1的因子11和的因子2的二元?dú)w結(jié)式；,.,98,魯賓遜歸結(jié)原理,在謂詞邏輯中仍然有，歸結(jié)式是它的親本子句的邏輯結(jié)果，用歸結(jié)式代替子句集中的親本子句所得到的新子句集仍然保持子句集的不可滿(mǎn)足性,.,99,歸結(jié)反演,歸結(jié)反演原理：欲證P1,P2,PnQ(1)P1P2,PnQT(2)(P1P2,Pn)QT(3)(P1P2,Pn)QF(4)我們的工作過(guò)程是從后向前進(jìn)行的，即證(4)就是證明了(3),證(3)就是證明了(2),證(2)就是證明了(1),.,100,歸結(jié)反演,在使用消解過(guò)程之前，我們必須把任一謂詞公式轉(zhuǎn)換成子句，下面給出轉(zhuǎn)化過(guò)程的步驟：（1）消去單條件運(yùn)算符號(hào)“”，應(yīng)用公式AB=AB（2）將否定符號(hào)深入到單個(gè)謂詞變?cè)那懊妫霉剑ˋB）=AB（AB）=AB(x)A(x)=(x)A(x)(x)A(x)=(x)A(x),.,101,歸結(jié)反演,(3)對(duì)變量標(biāo)準(zhǔn)化在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元（虛構(gòu)變量），它可以在該轄域內(nèi)處處統(tǒng)一地被另一個(gè)沒(méi)有出現(xiàn)過(guò)的任一變量所代替，而不改變公式的真值。合適公式中變量的標(biāo)準(zhǔn)化意味著對(duì)啞元改名以保證每個(gè)量詞有其自己唯一的啞元。例如把(x)（A(x)(x)（B（x）標(biāo)準(zhǔn)化為(x)（A(x)(y)（B（y）,.,102,歸結(jié)反演,(4)消去存在量詞在公式(x)(y)P(x,y)中，存在量詞是在全稱(chēng)量詞的轄域內(nèi)，我們?cè)试S所存在的x可能依賴(lài)于y值。令這種依賴(lài)關(guān)系明顯地由函數(shù)g（y）所定義，它把每個(gè)y值映射到存在的那個(gè)x。這種函數(shù)叫做skolem函數(shù)。如果用skolem函數(shù)代替存在的x，我們就可以消去全部存在量詞，并寫(xiě)成(y)(P(g(y),y),.,103,歸結(jié)反演,在公式(x)(y)P(x,y)中，存在量詞是在全稱(chēng)量詞的轄域內(nèi)，我們?cè)试S所存在的x可能依賴(lài)于y值。令這種依賴(lài)關(guān)系明顯地由函數(shù)g（y）所定義，它把每個(gè)y值映射到存在的那個(gè)x。這種函數(shù)叫做skolem函數(shù)。如果用skolem函數(shù)代替存在的x，我們就可以消去全部存在量詞，并寫(xiě)成(y)(P(g(y),y),.,104,歸結(jié)反演,從一個(gè)公式消去存在量詞的一般規(guī)則是以一個(gè)skolem函數(shù)代替每個(gè)出現(xiàn)的存在量詞的量化變量，而這個(gè)skolem函數(shù)的變量就是由那些全稱(chēng)量詞所約束的全稱(chēng)量詞量化變量，這些全稱(chēng)量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。skolem函數(shù)所使用的函數(shù)符號(hào)必須是新的，即不允許是公式中已經(jīng)出現(xiàn)過(guò)的函數(shù)符號(hào)。例如：(y)(x)P(x,y)被(y)(P(g(y),y)代替，其中g(shù)(y)為一skolem函數(shù)。,.,105,歸結(jié)反演,如果要消去的存在量詞不在任何一個(gè)全稱(chēng)量詞的轄域內(nèi)，那麼我們就用不含變量的skolem函數(shù)即常量。例如，(x)P(x)化為P(A)，其中常量符號(hào)A用來(lái)表示我們知道的存在實(shí)體。A必須是個(gè)新的常量符號(hào)，它未曾在公式中其它地方使用過(guò)。,.,106,歸結(jié)反演,（5）化為前束形到這一步已不留下任何存在量詞，而且，每個(gè)全稱(chēng)量詞都有自己的變量。把所有全稱(chēng)量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。所得公式稱(chēng)為前束形。,.,107,歸結(jié)反演,前束形公式由前綴和母式組成，前綴由全稱(chēng)量詞組成，母式由沒(méi)有量詞的公式組成，即前束形=（前綴）（母式）全稱(chēng)量詞串無(wú)量詞公式,.,108,歸結(jié)反演,（6）把母式化為合取范式任何母式都可寫(xiě)成由一些謂詞公式和（或）謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。我們可以反復(fù)應(yīng)用對(duì)的分配律，把任一母式化成合取范式。例如，A（BC）=（AB）（AC）,.,109,歸結(jié)反演,（7）消去全稱(chēng)量詞到了這一步，所有余下的量詞均被全稱(chēng)量詞量化了。同時(shí)，全稱(chēng)量詞的次序已經(jīng)不重要了。于是我們可以消去全稱(chēng)量詞。,.,110,歸結(jié)反演,（8）消去連接詞符號(hào)，用A，B代替AB。這樣反復(fù)代替的結(jié)果，最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。任一個(gè)只由文字的析取構(gòu)成的合式公式叫做一個(gè)子句。（9）更換變量名稱(chēng)可以更換變量符號(hào)的名稱(chēng)，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中。下面我們用例子來(lái)說(shuō)明化子句并進(jìn)行消解的過(guò)程：,.,111,歸結(jié)反演,例1試證：G是F1和F2的邏輯結(jié)論，其中F1：(x)(P(x)(y)(Q(y)L(x,y)F2：(x)(P(x)(y)(R(y)L(x,y)G：(x)(R(x)Q(x)(x)(P(x)(y)(Q(y)L(x,y),(x)(P(x)(y)(R(y)L(x,y)(x)(R(x)Q(x),.,112,歸結(jié)反演,證明：首先把F1，F(xiàn)2和G轉(zhuǎn)化成子句形：F1=(x)(P(x)(y)(Q(y)L(x,y)=(x)(P(x)(y)(Q(y)L(x,y)=(x)(y)(P(x)Q(y)L(x,y)=P(x)Q(y)L(x,y).,.,113,歸結(jié)反演,F2=(x)(P(x)(y)(R(y)L(x,y)=(x)(P(x)(y)(R(y)L(x,y)=(P(a)(y)(R(y)L(a,y)=(y)(P(a)(R(y)L(a,y)P(a),R(z)L(a,z),.,114,歸結(jié)反演,G=(x)(R(x)Q(x)=(x)(R(x)Q(x)=(R(x)Q(x)R(b),Q(b)得到子句集合如下：1.P(x)Q(y)L(x,y)2.P(a)3.R(z)L(a,z)S4.R(b)5.Q(b),.,115,歸結(jié)反演,6.Q(y)L(a,y)1和2及a/x7.L(a,b)5和6及b/y8.R(b)3和7及b/z9.4和8及=即S是不可滿(mǎn)足的，G是F1和F2的邏輯結(jié)論。,.,116,歸結(jié)反演,例2、已知：任何人的兄弟不是女性，任何人的姐妹必是女性，Mary是Bill的姐妹，試用歸結(jié)推理的方法證明Mary不是Tom的兄弟。解：為了求解此問(wèn)題首先定義如下謂詞：brother(x,y):x是y的兄弟；sister(x,y):x是y的姐妹；woman(x):x是女性。,.,117,歸結(jié)反演,于是問(wèn)題可以描述成：(x)(y)(brother(x,y)woman(x),(x)(y)(sister(x,y)woman(x),sister(Mary,Bill)brother(Mary,Tom),.,118,歸結(jié)反演,首先將前提和結(jié)論的否定轉(zhuǎn)換成子句形:(x)(y)(brother(x,y)woman(x)=brother(x,y)woman(x);(x)(y)(sister(x,y)woman(x)=sister(x,y)woman(x);brother(Mary,Tom)=brother(Mary,Tom);sister(Mary,Bill).,.,119,歸結(jié)反演,整理得子句集合S如下：1、sister(Mary,Bill)2、brother(Mary,Tom)S3、brother(x,y)woman(x)4、sister(z,w)woman(z),.,120,歸結(jié)反演,5、woman(Mary)和3及Mary/x,Tom/y6、woman(Mary)1和4及Mary/z,Bill/w7、5和6及空代換問(wèn)題得證.,.,121,歸結(jié)反演,例3、已知，John是賊。Paul喜歡酒（wine）,Paul也喜歡奶酪（cheese）。如果Paul喜歡某物則John也喜歡某物。如果某人是賊，并且他喜歡某物，則他很可能會(huì)偷竊該物。試用歸結(jié)推理的方法證明John可能偷竊了什麼？,.,122,歸結(jié)反演,解：為了求解該問(wèn)題定義如下謂詞：thief(x):x是賊like(x,y):某人x喜歡某物ymay-steal(x,y):某人x可能偷竊了某物y,.,123,歸結(jié)反演,于是問(wèn)題可以描述成：thief(John)，like(Paul，wine)，like(Paul，cheese)，(y)(like(Paul,y)like(John,y),(x)(thief(x)(y)(like(x,y)may-steal(x,y)may-steal(John,Z).,.,124,歸結(jié)反演,首先把前提和結(jié)論的否定轉(zhuǎn)換成子句形：(y)(like(Paul,y)like(John，y)=like(Paul，y)like(John，y);(x)(thief(x)(y)(like(x,y)may-steal(x,y)=thief(John)(y)(like(John,y)may-teal(John,y)=(y)(thief(John)(like(John,y)may-steal(John,y)）=thief(John)(like(John,y)may-steal(John,y).,.,125,may-steal(John,Z).整理得子句集合S為：1、thief(John)2、like(John,y)may-steal(John,y)3、like(Paul,wine)4、like(Paul,cheese)5、may-steal(John,Z)6、like(Paul，X)like(John，X)7、like(John,wine)3和6及wine/x8、may-steal(John,wine)2和7及wine/y9、5和8及問(wèn)題得證。,.,126,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,利用歸結(jié)原理還可以來(lái)求取問(wèn)題的答案，思想與定理證明類(lèi)似其求解步驟如下：、把已知前提用謂詞公式表示出來(lái)，并且化為相應(yīng)的子句集；、把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后把它否定并與謂詞ANSWER構(gòu)成析取式，ANSWER是一個(gè)為了求解問(wèn)題而專(zhuān)設(shè)的謂詞，其變?cè)仨毰c待求解問(wèn)題公式的變?cè)耆恢拢?.,127,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,、把析取式化為子句集，并且把該子句并入到子句集中，得到子句集合；、對(duì)應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)；、若得到歸結(jié)式ANSWER，則答案就在ANSWER中。,.,128,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,例：1:已知王（wang)先生是小李(li)的老師.2:小李與小張(zhang)是同班同學(xué)3:如果x與y是同班同學(xué)，則x的老師也是y的老師求小張的老師是誰(shuí)？,.,129,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,解：首先定義謂詞：T(x,y):x是y的老師C(x,y):x與y是同班同學(xué)把已知前提和待求解的問(wèn)題表示成謂詞公式：F1:T(wang,li)F2:C(li,zhang)F3:(x)(y)(z)(C(x,y)T(z,x)T(z,y).,.,130,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,G:(x)T(x,zhang)ANSWER(x)把上述公式化為子句集：（1）T(wang,li)（2）C(li,zhang)S（3）C(x,y)T(z,x)T(z,y).(4)T(u,zhang)ANSWER(u),.,131,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)：(5)C(li,y)T(z,y).(1)和(3)歸結(jié)(6)C(li,zhang)ANSWER(wang)(4),(5)(7)ANSWER(wang)(2)與(6)歸結(jié)其歸結(jié)樹(shù)如137的圖-9所示,.,132,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,例：設(shè),B,C三人中有人從不說(shuō)真話，也有人從不說(shuō)假話，某人向這三人分別提出同一個(gè)問(wèn)題：誰(shuí)是說(shuō)謊者？答：“和是說(shuō)謊者”；答：“和是說(shuō)謊者”；答：“和中至少有一個(gè)說(shuō)謊者”求誰(shuí)是誠(chéng)實(shí)的人，誰(shuí)是說(shuō)謊者？,.,133,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,解：令T(x):表示x說(shuō)真話如果說(shuō)的是真話，則有T(A)T(B)T(C)如果說(shuō)的是假話，則有T(A)(T(B)T(C)對(duì)和說(shuō)的話做相同的處理得：T()T()T(C)T()(T()T(C),.,134,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,T()(T()T(B)T(C)(T()T(B)把上面的公式化為子句集得：(1)T()T(B)(2)T()T(C)(3)T(B)T(C)(4)T()T()T(C)(5)T()T()T(B)(6)T()T(C),.,135,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,(7)T(B)T(C)下面首先求誰(shuí)是老實(shí)人把T(x)ANSWER(x)并入得1(8)T(x)ANSWER(x)在1上進(jìn)行歸結(jié)得(9)T(A)T(C)(1)和(7),.,136,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,(10)T(C)(6)和(9)(11)ANSWER(C)(8)和(10)及C/x即是老實(shí)人由于對(duì)1進(jìn)行歸結(jié)得不出ANSWER()和ANSWER()所以下面來(lái)證明和不是老實(shí)人設(shè)不是老實(shí)人，則有T()把它的否定并入中得2,.,137,應(yīng)用歸結(jié)原理求取問(wèn)題的答案,即2只比多了一個(gè)子句(8)(T()(9)T()T(C)(1)和(7)(10)T()(2)和(9)(11)NIL(8)和(10)所以不是老實(shí)人，同理可證不是老實(shí)人,.,138,歸結(jié)策略,實(shí)際用計(jì)算機(jī)進(jìn)行歸結(jié)時(shí)使用的是水平浸透法，即對(duì)中的每一對(duì)子句進(jìn)行比較，有歸結(jié)式即產(chǎn)生直到推出一個(gè)空子句從上面的例子我們可以看出影響歸結(jié)效率的重要因素是子句的數(shù)量和子句中文字的數(shù)量下面我們給出一些提高歸結(jié)效率的方法,.,139,歸結(jié)策略,要想提高消解效率，當(dāng)然是希望子句集合S中的子句越少越好，子句中的文字越少越好。為了提高消解效率，人們提出了很多控制策略，例如：刪除策略，線性歸結(jié)，單元?dú)w結(jié)，輸入歸結(jié)等。,.,140,刪除策略,所謂刪除策略是指，若子句集合S中有永真式則直接可以刪除，因?yàn)樗挥绊懽泳浼蟂的不可滿(mǎn)足性，此外被前面子句歸類(lèi)的子句也可以被刪除。下面給出歸類(lèi)的概念：設(shè)有兩個(gè)子句C和D，若有置換（或代換），使得CD成立，便說(shuō)子句C把子句D歸類(lèi)，或說(shuō)D被C歸類(lèi)，于是子句D可以從S中刪除。,.,141,刪除策略,其中：C表示子句C在代換下的例式，即將子句C中的變?cè)弥械捻?xiàng)代換所得的結(jié)果。例如C=p(x)D=p(a)Q(a)取=a/x于是有C=p(a)于是有p(a)p(a)，Q(a)其中逗號(hào)代表的是析取。,.,142,刪除策略,設(shè)子句序列C1，C2，Ck是從S推出Ck的演繹，若在演繹的過(guò)程中隨時(shí)刪除永真公式和被前面歸類(lèi)的子句，就