經(jīng)典邏輯推理

經(jīng)典邏輯推理第一頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.1基本概念推理、推理方式及其分類運用已經(jīng)掌握的知識，找出其中蘊涵的事實，或歸納出新事實的過程稱為推理。推理有以下不同的方式：1.演繹推理、歸納推理、默認(rèn)推理2.確定性推理、不確定性推理3.單調(diào)推理、非單調(diào)推理4.啟發(fā)式推理、非啟發(fā)式推理5.基于知識的推理、統(tǒng)計推理、直覺推理第二頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所Ⅰ.演繹推理、歸結(jié)推理、默認(rèn)推理（從新判斷推出的途徑來劃分）演繹推理——從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程，即由一般性知識推出適合于某一具體情況的結(jié)論。這是一種從一般到個別的推理。演繹推理有多種形式，經(jīng)常用的是三段論式，它包括：

1)大前提，這是已知的一般性知識或假設(shè)；

2)小前提，這是關(guān)于所研究的具體情況或個別事實的判斷；

3)結(jié)論，這是由大前提推出的適合于小前提所示情況的新判斷。例如：1)足球運動員的身體都是強壯的；

2)高波是一名足球運動員；

3)所以，高波的身體是強壯的。第三頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所歸納推理——歸納推理是從足夠多的事例中歸納出一般性納論的推理過程，是一種從個別到一般的推理。歸納推理又分為完全歸納和不完全歸納兩種。完全歸納：指在進行歸納時考察了相應(yīng)事物的全部對象，并根據(jù)這些對象是否都有某種屬性，從而推出這種事物是否具有這個屬性。不完全歸結(jié)：指只考察了相應(yīng)事物的部分對象，就得出了結(jié)論。第四頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所默認(rèn)推理——又稱缺省推理，它是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進行的推理。在默認(rèn)推理過程中，如果到某一時刻發(fā)現(xiàn)原先所作的默認(rèn)不正確，則就要撤銷所作默認(rèn)，以及由此默認(rèn)推出的所有結(jié)論，重新按新情況進行推理。第五頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所Ⅱ.確定性推理，不確定性推理（按推理時所用知識的確定性來劃分）

確定性推理——

指推理時所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或為“真”，或為“假”，沒有第三種情況出現(xiàn)。下面將要討論的經(jīng)典邏輯推理就屬于這一類。不確定性推理——指推理時所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于“真”和“假”之間，命題的外延模糊不清。第六頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所Ⅲ.單調(diào)推理、非單調(diào)推理（按推理過程中推出的結(jié)論是否單調(diào)的增加來劃分）單調(diào)推理——指在推理過程中隨著推理的向前推進及新知識的加入，推出的結(jié)論呈單調(diào)增加的趨勢，并且越來越接近最終目標(biāo)，在推理過程中不會出現(xiàn)反復(fù)的情況，即不會由于新知識的加入而否定了前面推出的結(jié)論，使推理又退回到前面的一步。非單調(diào)推理——指在推理過程中由于新知識的加入，不僅沒有加強已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始。第七頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所Ⅳ.啟發(fā)式推理、非啟發(fā)式推理（按推理中是否運用與問題有關(guān)的啟發(fā)性知識分）啟發(fā)式推理——推理中運用與問題有關(guān)的啟發(fā)性知識，即解決問題的策略、技巧、竅門，對解的特性及規(guī)律的估計等實踐經(jīng)驗和知識，以加快推理過程、提高搜索效率、提高推理的準(zhǔn)確性，這種推理稱為啟發(fā)式推理。非啟發(fā)式推理——比如窮舉式推理等。第八頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所Ⅴ.基于知識的推理、統(tǒng)計推理、直覺推理（從方法論的角度劃分）基于知識的推理——根據(jù)已掌握的事實，通過運用知識進行的推理。統(tǒng)計推理——根據(jù)對某事物的數(shù)據(jù)統(tǒng)計進行的推理(相當(dāng)于歸納推理)。直覺推理——又稱常識性推理，是根據(jù)常識進行的推理。第九頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.1基本概念推理的控制策略：推理的控制策略主要包括推理方向的控制策略、搜索的控制策略、沖突消解策略、求解策略及限制策略等。第十頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.1基本概念推理方向的控制策略則包括；正向推理、逆向推理、混合推理、雙向推理。正向推理：正向推理是以已知事實作為出發(fā)點的一種推理，又稱數(shù)據(jù)驅(qū)動推理、前向鏈推理及前件推理等。根據(jù)已知的實事，在知識庫中查找當(dāng)前可用的知識，構(gòu)成可適用的知識集KS，再安照沖突消解策略從KS中選出一條知識進行推理，并將推出的新實事加入到數(shù)據(jù)庫中作為下一步推理的實事……再查找，再推理，直到求得了所要求的解或者知識庫中沒有可用的知識為止。第十一頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所正向推理過程算法描述：開始把初始已知事實送入DBDB中包含問題的解？KB中有可適用知識？KS空？把KB中所有可適用知識都選出來送入KS推出的是新事實？按沖突消解策略從KS中選出一條知識進行推理將該新事實加入到DB中成功，退出把用戶提供的新事實加入DB中用戶可補充新事實？失敗，退出YYYYYNNNNN第十二頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所逆向推理：逆向推理是以某個假設(shè)目標(biāo)作為出發(fā)點的一種推理,又稱為目標(biāo)驅(qū)動推理、逆向鏈推理及后件推理等。逆向推理的基本思想：首先選定一個假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說明原假設(shè)成立；若無論如何都找不到所需證據(jù)，說明原假設(shè)不成立，此時需要另作新的假設(shè)，進行一輪新的推理。第十三頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所逆向推理過程算法描述開始提出假設(shè)該假設(shè)在數(shù)據(jù)庫DB中？該假設(shè)是證據(jù)？在知識庫中找出所有能導(dǎo)出該假設(shè)的知識，形成適用知識集KS從KS中選出一條知識，并將該知識的一個運用條件作為一個新的假設(shè)目標(biāo)。該假設(shè)成立詢問用戶有此事實？該假設(shè)成立，并將此事實存入數(shù)據(jù)庫還有假設(shè)？退出YYYYNNNN第十四頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所逆向推理：逆向推理的主要優(yōu)點：不必使用與目標(biāo)無關(guān)的知識，目的性強，同時還有利于向用戶提供解釋。主要缺點：初始目標(biāo)的選擇有盲目性，若不符合實際，就要多次提出假設(shè)，影響到系統(tǒng)效率。第十五頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所混合推理正、逆向推理存在的缺陷正向推理——具有盲目、效率低等缺點；逆向推理——若提出的假設(shè)目標(biāo)不符合事實，也會降低系統(tǒng)效率。為解決這些問題，可把正向推理與逆向推理結(jié)合起來，取長補短；象這樣既有正向又有逆向的推理稱為混合推理。混合推理適應(yīng)于下列情況：1：已知的實事不夠充分2：單純由正向推理得出的結(jié)論可信度不高3：希望得到更多的結(jié)論第十六頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所混合推理的兩種情況先正向再逆向：先進行正向推理，幫助選擇某個目標(biāo)，即從已知事實演繹出部分結(jié)果，然后再用逆向推理證實該目標(biāo)或提高其可信度。先逆向再正向：先假設(shè)一個目標(biāo)進行逆向推理，然后再利用逆向推理中得到的信息進行正向推理，以推出更多的結(jié)論。第十七頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所雙向推理雙向推理是指正向推理與逆向推理同時進行，且在推理過程中的某一步驟上“碰頭”的一種推理方式。基本思想：一方面根據(jù)已知事實進行正向推理，但并不推到最終目標(biāo)；另一方面從某假設(shè)目標(biāo)出發(fā)進行逆向推理，但并不推至原始事實，而是讓它們在中途相遇，即由正向推理所得的中間結(jié)論恰好是逆向推理此時所需要的證據(jù)，這時推理就可結(jié)束，逆向推理時所做的假設(shè)就是推理的最終結(jié)論。第十八頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所求解策略求解策略是指，推理是只求一個解，還是求所有解以及最優(yōu)解等。限制策略所謂限制策略是指為了防止無窮的推理過程，以及由于推理過長增加時間及空間上的復(fù)雜度，可在控制策略中指定推理的限制條件，以對推理的深度、寬度、時間、空間等進行限制。第十九頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所模式匹配所謂模式匹配是指對兩個知識模式（如謂詞公式、兩個框架片段或兩個語義網(wǎng)絡(luò)片段等）的比較與耦合，即檢查這兩個知識模式是否完全一致或近似一致。若完全一致或不完全一致但其相似程度在指定的范圍內(nèi),就稱它們是匹配的，否則為不可匹配。4.1基本概念第二十頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所模式匹配是推理中必須進行的一項重要工作，因為只有經(jīng)過模式匹配才能從知識庫中選出當(dāng)前適用的知識，才能進行推理。模式匹配可以有確定性匹配和不確定性匹配2種。確定性匹配是指兩個模式完全一樣，或者通過代換后變得完全一致。所謂不確定性匹配是指兩個知識模式不完全一樣，但從總體上看它們的相似程度又落在規(guī)定的限度內(nèi)。無論是確定性匹配還是不確定性匹配都需要進行變量的代換。第二十一頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所代換：代換是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，t1，t2，…,tn是項，x1.，x2,…,xn是互不相同的變元；ti/xi表示用項ti代換變量xi，不允許ti和xi相同，也不允許xi循環(huán)的出現(xiàn)在另一個tj中。例如{a/x,f(b)/y,w/z}就是一個代換第二十二頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所但是{g(y)/x,f(x)/y}則不是一個代換，因為代換的目的是使某些變元被另外的變元、常量、或函數(shù)表達式取代，使之不再在公式中出現(xiàn)，而{g(y)/x,f(x)/y}在x與y之間出現(xiàn)了循環(huán)代換的情況，它既沒有消去x,也沒有消去y。如果把它改為{g(a)/x,f(x)/y}就可以了，它將把公式中的x代換成g(a),y代換成f(g(a)),從而消去了變量x和y。第二十三頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所復(fù)合代換設(shè)有兩個代換和，其中

={t1/x1,t2/x2,…,tn/xn}，

={u1/y1,u2/y2,…,um/ym}則和的復(fù)合也是一個代換，它的定義如下：先做代換：{t1

/x1,t2

/x2,…,tn

/xn，u1/y1,u2/y2,…,um/ym}（注：ti是用代換來替換ti中的項）若ti·=xi時，從上述集合中刪除

ti

/xi

若yi

{x1，x2,…,xn}

從上述集合中刪除ui/yi

刪除之后剩下的元素構(gòu)成的集合稱作與的乘積，記為·。第二十四頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所例如設(shè)有如下代換：={f(y)/x,z/y}，={a/x,b/y,y/z}現(xiàn)在來求·

先做代換：{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}滿足條件1滿足條件2對于Z，因為它不屬于xi，所以y/z就不能刪除第二十五頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所合一：尋找項對變量的代換以使兩表達式一致，就叫合一設(shè)有公式集F={F1，F(xiàn)2，…,Fn},若存在一個代換使得F1=F2=…=Fn，則稱為公式集F的一個合一代換，且稱F1，F(xiàn)2，…,Fn是可合一的。例如：對于公式集F={P(x,y，f(y)),P(a,g(x),z)}，則={a/x，g(a)/y，f(g(a))/z}是公式F的一個合一。(原因：將的代換關(guān)系帶入公式集，可知公式集中的2個公式是等價的。)第二十六頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所一個公式的合一一般不是唯一的。但如果是公式集F的一個合一，若對任一個合一都存在一個代換使得：=·

，則稱是一個最一般合一。最一般合一是唯一的。若用最一般合一去代換那些可合一的謂詞公式，可使它們變成完全一致的公式。由此可知，為了使兩個知識模式匹配，可用其最一般合一對它們進行代換。為了求最一般合一要用到一個差異集（也叫分歧集）的概念。第二十七頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所設(shè)有如下兩個謂詞公式F1：P(x,y,z)，F(xiàn)2:P(x,f(a),h(b))分別從F1與F2的第一個符號開始，逐個向右比較，此時發(fā)現(xiàn)F1中的y與F2中的f(a)不同,它們構(gòu)成了一個差異集：D1={y,f(a)}當(dāng)繼續(xù)向右比較時，又發(fā)現(xiàn)F1中與F2中的h(b)不同，于是又得到一個差異集：D2={z,h(b)}。第二十八頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所下面給出求最一般合一的算法：（1）令k=0,Fk=F,k=。這里，F(xiàn)是欲求其最一般合一的公式集，是空代換,它表示不做代換。（2）若Fk只含一個表達式，則算法停，k就是所求最一般合一。（3）找出Fk的差異集Dk。（4）若Dk中存在元素xk和tk,其中xk是變元，tk是項,且xk不在tk中出現(xiàn)，則置：k+1=k·{tk/

xk}Fk+1=Fk{tk/xk}k=k+1轉(zhuǎn)（2）（5）算法停，F(xiàn)的最一般合一不存在。第二十九頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.1基本概念沖突消解策略在推理的過程中，系統(tǒng)不斷的用已知的事實與知識庫中的知識進行匹配，此時可能發(fā)生如下三種情況：（1）已知事實不能與知識庫中的任何知識匹配成功。（2）已知事實恰好與知識庫中的一條知識匹配成功。（3）已知事實可與知識庫中的多條知識匹配成功。第一種情況中,使得推理無法進行下去,第二種情況恰好匹配,第三種情況則出現(xiàn)沖突，需要按一定的策略解決沖突。第三十頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.1基本概念目前解決沖突的策略有多種，其基本思想都是對知識進行排序，常用的有以下幾中：1、按針對性排序設(shè)有如下兩條產(chǎn)生式規(guī)則：r1:IFA1andA2and…AnTHENH1r2:IFB1andB2and…BmTHENH2如果存在最一般合一，使得r1中每一個Ai都可變成相應(yīng)的Bi

，即r2中除了包含的r1全部條件A1,A2,…,An外，還包含其它條件，則稱r2

比r1有更大的針對性，r1

比r2

有更大的通用性。第三十一頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.1基本概念上面的策略是優(yōu)先選用針對性較強的產(chǎn)生式規(guī)則。(即應(yīng)選用r2)因為它要求的條件較多，其結(jié)論一般更接近目標(biāo)，一旦得到滿足，可縮短推理過程。第三十二頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.1基本概念2、按已知事實的新鮮性排序在產(chǎn)生式系統(tǒng)推理過程中，每應(yīng)用一條產(chǎn)生式規(guī)則就會得到一個或多個結(jié)論，數(shù)據(jù)庫就會增加新的事實。把數(shù)據(jù)庫后生成的事實稱為新鮮的事實，即后生成的事實比先生成的事實具有較大的新鮮性。設(shè)規(guī)則r1可與事實組A匹配成功，規(guī)則r2可與事實組B匹配成功，則A與B中哪一組新鮮與它匹配的產(chǎn)生式規(guī)則就先被應(yīng)用。第三十三頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所3、按匹配度排序在不確定性匹配中，為了確定兩個知識模式是否可以匹配，需要計算這兩個模式的相似程度，當(dāng)其相似程度達到某個預(yù)定的值時，就認(rèn)為它們是可匹配的。若兩條規(guī)則均按匹配度匹配成功，則匹配度大的那條規(guī)則優(yōu)先啟用。第三十四頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4、根據(jù)領(lǐng)域問題的特點排序某些領(lǐng)域問題可事先知道它的某些特性，可根據(jù)這些特性把知識排成固定的順序，按照領(lǐng)域知識特性決定匹配順序。第三十五頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所5、按上下文限制排序把產(chǎn)生式規(guī)則按它們所描述的上下文分成若干組，在不同的條件下，只能從相應(yīng)的組中選取有關(guān)的產(chǎn)生式規(guī)則。這樣可以減少沖突的發(fā)生6、按冗余限制排序若哪一條產(chǎn)生式規(guī)則被應(yīng)用后產(chǎn)生冗余知識，則就降低它被應(yīng)用的優(yōu)先級。7、按條件個數(shù)排序如果有多條產(chǎn)生式規(guī)則生成的結(jié)論相同，則要求條件少的產(chǎn)生式規(guī)則被優(yōu)先應(yīng)用。第三十六頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.2自然演繹推理從一組已知的事實出發(fā)，直接運用經(jīng)典邏輯推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。其中，基本的推理規(guī)則是P規(guī)則、T規(guī)則、假言推理、拒取式推理等。假言推理的一般形式是：P，PQQ拒取式的一般形式是PQ，QP以下是自然演繹推理的例子：第三十七頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.2自然演繹推理（續(xù)）例1：已知A，B，AC，BCD，DQ求證Q1、AP規(guī)則2、ACP規(guī)則3、CT規(guī)則1和24、BP規(guī)則5、BCT規(guī)則3和46、BCDP規(guī)則7、DT規(guī)則5和68、DQP規(guī)則9、QT規(guī)則7和8問題得證P規(guī)則：在推理的任何步驟上都可引入前題T規(guī)則：在推理時，如果前面步驟中有一個或多個永真蘊涵公式S，則可把S引入推理過程。第三十八頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.2自然演繹推理（續(xù)）例2設(shè)已知如下事實；（1）凡是容易的課程小王（Wang)都喜歡。（2）C班的課程都是容易的。（3）ds是C班的一門課程求證小王喜歡ds這門課程。證明：首先定義謂詞如下：EASY(x):x是容易的LIKE(x,y):x喜歡yC(x):x是C班的一門課程于是問題可以表示成：第三十九頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.2自然演繹推理（續(xù)）已知：x(EASY(x)LIKE(Wang,x))x(C(x)EASY(x))C(ds)求證：LIKE(Wang,ds)證明：1、x(C(x)EASY(x))P規(guī)則2、C(ds)EASY(ds)T規(guī)則13、x(EASY(x)LIKE(Wang,x))P規(guī)則4、EASY(ds)LIKE(Wang,ds)T規(guī)則和35、LIKE(Wang,ds)得證第四十頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所

4.2自然演繹推理（續(xù)）自然演繹推理的優(yōu)點是表達定理證明過程自然，容易理解，擁有豐富的推理規(guī)則，推理過程靈活，便于在推理過程中嵌入領(lǐng)域啟發(fā)知識。缺點是容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一般呈指數(shù)形式遞增，這對于一個大型推理問題是十分不利的，甚至是不可能實現(xiàn)的。第四十一頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所以下還有的推理方法：歸結(jié)演繹推理與/或形演繹推理自己看書第四十二頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理定理證明是人工智能的一個重要研究領(lǐng)域，這不僅僅是因為許多數(shù)學(xué)問題要通過定理證明得以解決，很多非數(shù)學(xué)問題（如醫(yī)療診斷、機器人規(guī)劃及難題求解等）也都歸結(jié)為一個定理證明問題。定理證明的實質(zhì)是對前提P和結(jié)論Q證明PQ的永真性。但是證明一個謂詞公式的永真性不像證明一個命題公式的永真性那麼簡單，（它牽涉到謂詞變量、客體變量及函數(shù)符號）在某些情況下甚至是行不通的。在這種情況下，人們提出了用反證法來解決問題的思路。在這方面，海伯倫和魯賓遜都作出了杰出的貢獻。兩人的研究都是以子句集為背景展開的。接下來，我們介紹這些概念。第四十三頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理（續(xù)）子句：在謂詞邏輯中，稱原子謂詞公式及其否定為文字；任何文字的析取式為子句。例如，P（x)Q(x),P(x,f(x))Q(x,g(x))都是子句。而P（x)

、Q(x,g(x))、P(x,f(x))等都是文字。并把不包含任何文字的子句稱為空子句。由于空子句不包含任何文字，它不能被任何解釋所滿足，所以空子句是永假的，不可滿足的。由子句構(gòu)成的集合稱為子句集。在謂詞邏輯中任何一個謂詞公式均可通過等價變換化為相應(yīng)的子句集。第四十四頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理（續(xù)）化子句集的步驟如下：1、利用等價公式消去公式中的邏輯連接詞“”和“”：PQPQPQ（PQ）（PQ）2、利用下列公式將否定符號“”深入到單個變元前PP（PQ）PQ（PQ）PQ(x)P(x)P(x)P(x)P第四十五頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所3、重新命名變元名，使不同量詞約束的變元有不同的名字4、消去存在量詞。分兩種情況處理：一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，此時只要用一個新的個體常量替換受該存在量詞約束的變元就可消去存在量詞；另一種情況是存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如（x1)（x2)…(xn)(y)P(x1,x2,…,xn,y)此時需要用Skolem函數(shù)f(x1,x2,…,xn)替換受該存在量詞約束的變元，然后才能消去存在量詞。5、把全稱量詞全部移到公式的左邊。6、利用等價關(guān)系P（QR）=（PQ）（PR）把公式化為Skolem標(biāo)準(zhǔn)型。第四十六頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理（續(xù)）Skolem標(biāo)準(zhǔn)型的一般形式是：（x1)（x2)…(xn)M其中，M是子句的合取式，稱為Skolem標(biāo)準(zhǔn)型的母式。7、消去全稱量詞8、對變元更名，使不同子句中的變元不同名。9、消去合取連接詞，變?yōu)樽泳浼Ｗ泳浼懈髯泳渲g是合取關(guān)系。謂詞公式是不可滿足的，則其子句集合是不可滿足的，反之亦然。第四十七頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所

4.3歸結(jié)演繹推理（續(xù)）如何證明一個子句集是不可滿足的呢？下面就海伯倫理論和魯賓遜的歸結(jié)原理進行討論。一、海伯倫理論要判定一個子句集是否是不可滿足的，需要對子句集中的謂詞公式進行判定，而謂詞公式的判定需要對個體域上的任何解釋進行判定，這是很困難的。海伯倫定義了一個特殊的域稱為海伯倫域，在任何域上的判定，只要在海伯倫域上進行即可。*設(shè)S是子句集，則按下述方法構(gòu)造的域H稱為是海伯倫域：第四十八頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理（續(xù)）1、令H0是S中所有個體常量的集合，若S中不包含個體常量，則令H0=[a}，其中a為任意指定的一個個體常量。2、令Hi+1=Hi{S中所有n元函數(shù)f(x1,x2,…,xn)|xj(j=1,2,…,n)是Hi中的元素}，其中，i=0,1,…。下面通過例子來解釋這個定義。例1求子句集S={P(x)Q(x),R(f(y))}的H域。解：因為S中沒有個體常量，所以指定a作為個體常量，于是得到：H0={a},H1={a,f(a)},H2={a,f(a),f(f(a))},…,H={a,f(a),f(f(a)),…}第四十九頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）例2求子句集S=[P(a),Q(b),R(f(x))}的H域解：根據(jù)H域的定義得到：H0={a,b}H1={a,b,f(a),f(b)}┇

例3：求子句集S={P(x),Q(y)R(y)}的H域。解：由于該子句集中既無個體常量，又無函數(shù)，所以可任意指定一個常量a作為個體常量，從而得到H0=H1=…=H={a}有定理說：子句集S是不可滿足的充要條件是S對H域上的一切解釋都為假。并且海伯倫證明了若子句集S在任何域D上的解釋能滿足S，則在H域上相應(yīng)的解釋也能滿足S。下面我們說明，S在H域上解釋的定義：第五十頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）子句集S在H域上的一個解釋滿足下列條件：1、在解釋I下，常量映射到自身；2、S中的任一個n元函數(shù)是HnH的映射。即，設(shè)h1,h2,…,hnH,則f(h1,h2,…,hn)H;3、S中的任一n元謂詞是Hn{T，F(xiàn)}的映射。即謂詞的真值可以指派T也可指派F。海伯倫在理論上證明了子句集不可滿足性的可行性及方法，但要在計算機上實現(xiàn)其證明過程還是很困難的。1965年魯賓遜提出了歸結(jié)原理，使機器證明成為現(xiàn)實第五十一頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）*魯賓遜歸結(jié)原理歸結(jié)原理也稱消解原理，是魯賓遜提出的一種證明子句不可滿足性，從而實現(xiàn)定理證明的一種理論及方法。由謂詞公式轉(zhuǎn)化為子句集的過程可以看出，在子句集中子句之間的關(guān)系是合取關(guān)系，其中只要有一個子句不可滿足，則子句集就不可滿足。前面，我們曾經(jīng)說過空子句是不可滿足的，即一個子句集中若含空子句，則它是不可滿足的。歸結(jié)原理的基本思想就是檢查子句集中是否含空子句，若含則子句集S不可滿足，或說證明一個謂詞公式是永假的過程，就是歸結(jié)由此公式轉(zhuǎn)換成的子句集包含空子句的過程。第五十二頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所

4.3歸結(jié)演繹推理(續(xù)）下面我們先來說明命題邏輯中的歸結(jié)原理定義P是原子謂詞公式，則稱P與P為互補文字。我們知道在命題邏輯中有公式：PQ,QRPR即PQ，QRPRc1c2c12顯然上述公式向我們展示的是在子句c1

中存在文字Q，在子句c2中存在Q的補文字Q，把這一對互補文字消去，剩下的文字析取起來就是子句

c1和c2的邏輯結(jié)果c12。并稱c12是c1和c2的歸結(jié)式，c1和c2則稱為c12的親本子句。第五十三頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）

例如：1、C1=PQRC2=QS它們的歸結(jié)式c12為PRS2、C1=PC2=P它們的歸結(jié)式c12為NIL即空子句。3、C1=PQC2=QRC3=P它們的歸結(jié)式c123為R。其歸結(jié)過程可以用下面的一個樹形結(jié)構(gòu)很清楚的表現(xiàn)出來。第五十四頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）

PQQRPRPR

歸結(jié)過程的樹形表示圖第五十五頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）由命題邏輯中的歸結(jié)原理可以得出如下的推論：設(shè)c1與c2是子句集S中的兩個子句，c12是它們的歸結(jié)式,若用c12代替c1和c2后得到新子句集S1，則由S1的不可滿足性可以推出S的不可滿足性。這個定理告訴我們，證明子句集S的不可滿足性問題，可以轉(zhuǎn)化成證子句集S1的不可滿足性問題，…直到從子句集Sn

中推出一個空子句來。第五十六頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）謂詞邏輯中的歸結(jié)原理在謂詞邏輯中，由于子句中含有變元，所以不象命題邏輯中那樣可以直接消去互補文字，而先要用最一般合一對變元進行代換。然后才能進行歸結(jié)。前面我們已經(jīng)介紹過最一般合一的概念，下面給出謂詞邏輯中二元歸結(jié)式的概念。*設(shè)C1與C2是兩個沒有公共變量的子句，L1和L2分別是C1與C2中的文字，若是L1和L2的最一般合一，則稱C12=（C1-{L1}）（C2-{L2}）為C1與C2的二元歸結(jié)式，L1和L2稱為歸結(jié)式上的文字。例子見P132頁的例4.10和例4.11。第五十七頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）在謂詞邏輯中二元歸結(jié)式可能是下列情形之一：C1和C2的二元歸結(jié)式；C1和C2的因子C22的二元歸結(jié)式；C1的因子C11和C2的二元歸結(jié)式；C1的因子C11和C2的因子C22的二元歸結(jié)式。下面我們介紹歸結(jié)反演證明子句集不可滿足的過程：設(shè)有如下的定理證明問題：P1，P2，…,PnQ第五十八頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）根據(jù)定義即證：P1P2，…,PnQT（1）即證（P1P2，…,Pn）QT（2）即證（（P1P2，…,Pn）Q）F（3）即證P1P2，…,Pn

QF（4）我們的工作現(xiàn)在是反向進行，即從證（4）（3）（2）（1）問題得證。設(shè)F為已知前提P1P2

，…,Pn的公式集，Q為目標(biāo)公式，歸結(jié)反演的過程：是把{F，Q}，化為子句集S，對S中的子句進行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式并入S中，若出現(xiàn)空子句，則停止歸結(jié)，即證明Q為真。第五十九頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）下面我們用例子來說明這個過程見P134頁的例4.12~例4.16從上面的例子可以看出歸結(jié)過程關(guān)鍵的是從子句集中找出可進行歸結(jié)的一對子句。機器上用的是水平浸透法，這一過程可能產(chǎn)生大量無用子句，造成時間和空間的浪費。因此，如何提高消解效率就變成一個重要的研究課題。下面提出的都是一些有效的方法：1、刪除策略從水平浸透法的本質(zhì)可以看出，提高消解效率的要害是使子句集合中子句的數(shù)量越少越好，子句中文字的數(shù)量越少越好。刪除策略正是從這一點考慮提出的。幾種刪除方法如下：第六十頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）（1）純文字刪除法如果某文字L在子句集中不存在可與之互補的文字L，則稱該文字是為純文字。顯然在歸結(jié)時純文字不可能消去，因此，包含它的子句進行歸結(jié)時不可能得到空子句，即這樣的子句對歸結(jié)是無意義的，所以，這樣的子句從子句集中刪除。（請給出純文字刪除的算法實現(xiàn)）（2）重言式刪除法如果一個子句中同時包含互補文字對，則稱該子句為重言式，顯然重言式不會影響子句集合S的不可滿足性，所以，可以從子句集合中刪除。（給出檢查一個公式是否是重言式的算法實現(xiàn)）（3）包孕刪除法（被歸類的子句可以刪除）設(shè)有子句C1和C2，如果存在代換，使得C1C2，則稱C1包孕于C2或說C2包孕C1，包的子句可以刪除，即第六十一頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）子句C2可以刪除。（想一想它的原理是什麼？P（PQ）=P）2、支持集策略每次歸結(jié)時，親本子句中至少應(yīng)有一個是由目標(biāo)公式的否定所得到的子句，或者是它們的后裔。例如有子句集合S={I(x)R(x),I(a),R(y)L(y),L(a)}其中I(x)R(x)是目標(biāo)公式的否定得到的子句。用支持集歸結(jié)的過程是：S:（1）I(x)R(x)(2)I(a)(3)R(y)L(y)(4)L(a)S1(5)R(a)(1)與（2）歸結(jié)第六十二頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）(6)I(x)L(x)S2(1)與（3）歸結(jié)

S2:

(7)L(a)(2)與（6）歸結(jié)

(8)L(a)(3)與（5）歸結(jié)

(9)I(a)(4)與（6）歸結(jié)

S3:(10)NIL(2)與（9）歸結(jié)上述歸結(jié)過程可以用P141頁的圖4-10來描述。3、線性輸入策略線性歸結(jié)是這樣一種歸結(jié)，首先從子句集中選取一個稱為頂子句的子句C0

開始做歸結(jié)，其次是歸結(jié)過程中所得到的歸結(jié)式Ci立即同另一子句Bi進行歸結(jié)得歸結(jié)式Ci+1。而BiSCk(k<i)(已出現(xiàn)過的歸結(jié)式）。這里關(guān)鍵的問題是頂子句的選擇，一般選擇結(jié)論的否定作為頂子句。第六十三頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）例如：證明PQ，PQ，PQPQ解，問題轉(zhuǎn)化成證子句集合S={PQ，PQ，PQ，PQ}的不可滿足問題，用線形消解的圖解表示如下：第六十四頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4.3歸結(jié)演繹推理(續(xù)）4、單文字子句策略如果一個子句只包含一個文字，則稱它為單文字子句。單文字子句策略要求參加歸結(jié)的兩個子句中必須至少有一個是單文字子句。例子見P142頁的例4.20.但單文字策略是不完備的，即當(dāng)子句集合中不存在單文字子句時，不能使用單文字子句策略。5、祖先過濾形策略該策略與線性輸入策略比較相似，它要求對兩個子句進行消解時，只要它們滿足下面兩個條件之一就可進行歸結(jié)。（1）C1與C2中至少有一個是初始子句集中的子句。

（2）如果兩個子句都不是初始子句集中的子句，則一個應(yīng)是另一個的祖先。所謂C1是C2的祖先是指C2是由C1和其它子句消解得到的消解式。第六十五頁，共七十三頁，編輯于2023年，星期一2023/6/5鄭州大學(xué)振動工程研究所4