2022/11/22鄭州大學(xué)振動(dòng)工程研究所第四章經(jīng)典邏輯推理為了使計(jì)算機(jī)具有智能僅僅擁有知識(shí)是不夠的，還需要讓它擁有思維能力，即能夠運(yùn)用知識(shí)進(jìn)行推理、求解問題。因此推理是人工智能的一個(gè)重要研究課題。接下來(lái)，我們將介紹關(guān)于推理的一般概念，然后介紹幾種推理方法。2022/11/22鄭州大學(xué)振動(dòng)工程研究所

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

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

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

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

2)高波是一名足球運(yùn)動(dòng)員；

3)所以，高波的身體是強(qiáng)壯的。2022/11/22鄭州大學(xué)振動(dòng)工程研究所歸納推理——?dú)w納推理是從足夠多的事例中歸納出一般性納論的推理過程，是一種從個(gè)別到一般的推理。歸納推理又分為完全歸納和不完全歸納兩種。完全歸納：指在進(jìn)行歸納時(shí)考察了相應(yīng)事物的全部對(duì)象，并根據(jù)這些對(duì)象是否都有某種屬性，從而推出這種事物是否具有這個(gè)屬性。不完全歸結(jié)：指只考察了相應(yīng)事物的部分對(duì)象，就得出了結(jié)論。2022/11/22鄭州大學(xué)振動(dòng)工程研究所默認(rèn)推理——又稱缺省推理，它是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。在默認(rèn)推理過程中，如果到某一時(shí)刻發(fā)現(xiàn)原先所作的默認(rèn)不正確，則就要撤銷所作默認(rèn)，以及由此默認(rèn)推出的所有結(jié)論，重新按新情況進(jìn)行推理。2、ACP規(guī)則解，問題轉(zhuǎn)化成證子句集合S={PQ，PQ，PQ，PQ}的不可滿足問題，用線形消解的圖解表示如下：子句集中各子句之間是合取關(guān)系。*設(shè)S是子句集，則按下述方法構(gòu)造的域H稱為是海伯倫域：?jiǎn)l(fā)式推理、非啟發(fā)式推理鄭州大學(xué)振動(dòng)工程研究所在與/或形正向演繹推理中，通常要求F規(guī)則具有如下的形式：若兩條規(guī)則均按匹配度匹配成功，則匹配度大的那條規(guī)則優(yōu)先啟用。鄭州大學(xué)振動(dòng)工程研究所鄭州大學(xué)振動(dòng)工程研究所但如果是公式集F的一個(gè)合一，若對(duì)任一個(gè)合一都存在一個(gè)代換使得：=·，則稱是一個(gè)最一般合一。逆向推理是以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理,又稱為目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理及后件推理等。求證小王喜歡ds這門課程。C2=QS如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對(duì)，則稱該子句為重言式，顯然重言式不會(huì)影響子句集合S的不可滿足性，所以，可以從子句集合中刪除。其中I(x)R(x)是目標(biāo)公式的否定得到的子句。2022/11/22鄭州大學(xué)振動(dòng)工程研究所Ⅱ.確定性推理，不確定性推理（按推理時(shí)所用知識(shí)的確定性來(lái)劃分）

確定性推理——

指推理時(shí)所用的知識(shí)都是精確的，推出的結(jié)論也是確定的，其真值或?yàn)椤罢妗?，或?yàn)椤凹佟?，沒有第三種情況出現(xiàn)。下面將要討論的經(jīng)典邏輯推理就屬于這一類。不確定性推理——指推理時(shí)所用的知識(shí)不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于“真”和“假”之間，命題的外延模糊不清。2022/11/22鄭州大學(xué)振動(dòng)工程研究所Ⅲ.單調(diào)推理、非單調(diào)推理（按推理過程中推出的結(jié)論是否單調(diào)的增加來(lái)劃分）單調(diào)推理——指在推理過程中隨著推理的向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論呈單調(diào)增加的趨勢(shì)，并且越來(lái)越接近最終目標(biāo)，在推理過程中不會(huì)出現(xiàn)反復(fù)的情況，即不會(huì)由于新知識(shí)的加入而否定了前面推出的結(jié)論，使推理又退回到前面的一步。非單調(diào)推理——指在推理過程中由于新知識(shí)的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始。2022/11/22鄭州大學(xué)振動(dòng)工程研究所Ⅳ.啟發(fā)式推理、非啟發(fā)式推理（按推理中是否運(yùn)用與問題有關(guān)的啟發(fā)性知識(shí)分）啟發(fā)式推理——推理中運(yùn)用與問題有關(guān)的啟發(fā)性知識(shí)，即解決問題的策略、技巧、竅門，對(duì)解的特性及規(guī)律的估計(jì)等實(shí)踐經(jīng)驗(yàn)和知識(shí)，以加快推理過程、提高搜索效率、提高推理的準(zhǔn)確性，這種推理稱為啟發(fā)式推理。非啟發(fā)式推理——比如窮舉式推理等。2022/11/22鄭州大學(xué)振動(dòng)工程研究所Ⅴ.基于知識(shí)的推理、統(tǒng)計(jì)推理、直覺推理（從方法論的角度劃分）基于知識(shí)的推理——根據(jù)已掌握的事實(shí)，通過運(yùn)用知識(shí)進(jìn)行的推理。統(tǒng)計(jì)推理——根據(jù)對(duì)某事物的數(shù)據(jù)統(tǒng)計(jì)進(jìn)行的推理(相當(dāng)于歸納推理)。直覺推理——又稱常識(shí)性推理，是根據(jù)常識(shí)進(jìn)行的推理。2022/11/22鄭州大學(xué)振動(dòng)工程研究所推理的控制策略：推理的控制策略主要包括推理方向的控制策略、搜索的控制策略、沖突消解策略、求解策略及限制策略等。2022/11/22鄭州大學(xué)振動(dòng)工程研究所推理方向的控制策略則包括；正向推理、逆向推理、混合推理、雙向推理。正向推理：正向推理是以已知事實(shí)作為出發(fā)點(diǎn)的一種推理，又稱數(shù)據(jù)驅(qū)動(dòng)推理、前向鏈推理及前件推理等。根據(jù)已知的實(shí)事，在知識(shí)庫(kù)中查找當(dāng)前可用的知識(shí)，構(gòu)成可適用的知識(shí)集KS，再安照沖突消解策略從KS中選出一條知識(shí)進(jìn)行推理，并將推出的新實(shí)事加入到數(shù)據(jù)庫(kù)中作為下一步推理的實(shí)事……再查找，再推理，直到求得了所要求的解或者知識(shí)庫(kù)中沒有可用的知識(shí)為止。2022/11/22鄭州大學(xué)振動(dòng)工程研究所正向推理過程算法描述：開始把初始已知事實(shí)送入DBDB中包含問題的解？KB中有可適用知識(shí)？KS空？把KB中所有可適用知識(shí)都選出來(lái)送入KS推出的是新事實(shí)？按沖突消解策略從KS中選出一條知識(shí)進(jìn)行推理將該新事實(shí)加入到DB中成功，退出把用戶提供的新事實(shí)加入DB中用戶可補(bǔ)充新事實(shí)？失敗，退出YYYYYNNNNN2022/11/22鄭州大學(xué)振動(dòng)工程研究所逆向推理：逆向推理是以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理,又稱為目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理及后件推理等。逆向推理的基本思想：首先選定一個(gè)假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說(shuō)明原假設(shè)成立；若無(wú)論如何都找不到所需證據(jù)，說(shuō)明原假設(shè)不成立，此時(shí)需要另作新的假設(shè)，進(jìn)行一輪新的推理。2022/11/22鄭州大學(xué)振動(dòng)工程研究所逆向推理過程算法描述開始提出假設(shè)該假設(shè)在數(shù)據(jù)庫(kù)DB中？該假設(shè)是證據(jù)？在知識(shí)庫(kù)中找出所有能導(dǎo)出該假設(shè)的知識(shí)，形成適用知識(shí)集KS從KS中選出一條知識(shí)，并將該知識(shí)的一個(gè)運(yùn)用條件作為一個(gè)新的假設(shè)目標(biāo)。該假設(shè)成立詢問用戶有此事實(shí)？該假設(shè)成立，并將此事實(shí)存入數(shù)據(jù)庫(kù)還有假設(shè)？退出YYYYNNNN2022/11/22鄭州大學(xué)振動(dòng)工程研究所逆向推理：逆向推理的主要優(yōu)點(diǎn)：不必使用與目標(biāo)無(wú)關(guān)的知識(shí)，目的性強(qiáng)，同時(shí)還有利于向用戶提供解釋。主要缺點(diǎn)：初始目標(biāo)的選擇有盲目性，若不符合實(shí)際，就要多次提出假設(shè)，影響到系統(tǒng)效率。2022/11/22鄭州大學(xué)振動(dòng)工程研究所混合推理正、逆向推理存在的缺陷正向推理——具有盲目、效率低等缺點(diǎn)；逆向推理——若提出的假設(shè)目標(biāo)不符合事實(shí)，也會(huì)降低系統(tǒng)效率。為解決這些問題，可把正向推理與逆向推理結(jié)合起來(lái)，取長(zhǎng)補(bǔ)短；象這樣既有正向又有逆向的推理稱為混合推理?；旌贤评磉m應(yīng)于下列情況：1：已知的實(shí)事不夠充分2：?jiǎn)渭冇烧蛲评淼贸龅慕Y(jié)論可信度不高3：希望得到更多的結(jié)論2022/11/22鄭州大學(xué)振動(dòng)工程研究所混合推理的兩種情況先正向再逆向：先進(jìn)行正向推理，幫助選擇某個(gè)目標(biāo)，即從已知事實(shí)演繹出部分結(jié)果，然后再用逆向推理證實(shí)該目標(biāo)或提高其可信度。先逆向再正向：先假設(shè)一個(gè)目標(biāo)進(jìn)行逆向推理，然后再利用逆向推理中得到的信息進(jìn)行正向推理，以推出更多的結(jié)論。2022/11/22鄭州大學(xué)振動(dòng)工程研究所雙向推理雙向推理是指正向推理與逆向推理同時(shí)進(jìn)行，且在推理過程中的某一步驟上“碰頭”的一種推理方式?；舅枷耄阂环矫娓鶕?jù)已知事實(shí)進(jìn)行正向推理，但并不推到最終目標(biāo)；另一方面從某假設(shè)目標(biāo)出發(fā)進(jìn)行逆向推理，但并不推至原始事實(shí)，而是讓它們?cè)谥型鞠嘤?，即由正向推理所得的中間結(jié)論恰好是逆向推理此時(shí)所需要的證據(jù)，這時(shí)推理就可結(jié)束，逆向推理時(shí)所做的假設(shè)就是推理的最終結(jié)論。2022/11/22鄭州大學(xué)振動(dòng)工程研究所求解策略求解策略是指，推理是只求一個(gè)解，還是求所有解以及最優(yōu)解等。限制策略所謂限制策略是指為了防止無(wú)窮的推理過程，以及由于推理過長(zhǎng)增加時(shí)間及空間上的復(fù)雜度，可在控制策略中指定推理的限制條件，以對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)行限制。2022/11/22鄭州大學(xué)振動(dòng)工程研究所模式匹配所謂模式匹配是指對(duì)兩個(gè)知識(shí)模式（如謂詞公式、兩個(gè)框架片段或兩個(gè)語(yǔ)義網(wǎng)絡(luò)片段等）的比較與耦合，即檢查這兩個(gè)知識(shí)模式是否完全一致或近似一致。若完全一致或不完全一致但其相似程度在指定的范圍內(nèi),就稱它們是匹配的，否則為不可匹配。

2022/11/22鄭州大學(xué)振動(dòng)工程研究所模式匹配是推理中必須進(jìn)行的一項(xiàng)重要工作，因?yàn)橹挥薪?jīng)過模式匹配才能從知識(shí)庫(kù)中選出當(dāng)前適用的知識(shí)，才能進(jìn)行推理。模式匹配可以有確定性匹配和不確定性匹配2種。確定性匹配是指兩個(gè)模式完全一樣，或者通過代換后變得完全一致。所謂不確定性匹配是指兩個(gè)知識(shí)模式不完全一樣，但從總體上看它們的相似程度又落在規(guī)定的限度內(nèi)。無(wú)論是確定性匹配還是不確定性匹配都需要進(jìn)行變量的代換。2022/11/22鄭州大學(xué)振動(dòng)工程研究所代換：代換是形如{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中。例如{a/x,f(b)/y,w/z}就是一個(gè)代換2022/11/22鄭州大學(xué)振動(dòng)工程研究所但是{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)代換的情況，它既沒有消去x,也沒有消去y。如果把它改為{g(a)/x,f(x)/y}就可以了，它將把公式中的x代換成g(a),y代換成f(g(a)),從而消去了變量x和y。2022/11/22鄭州大學(xué)振動(dòng)工程研究所復(fù)合代換設(shè)有兩個(gè)代換和，其中={t1/x1,t2/x2,…,tn/xn}，={u1/y1,u2/y2,…,um/ym}則和的復(fù)合也是一個(gè)代換，它的定義如下：先做代換：{t1

/x1,t2

/x2,…,tn

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

ti

/xi

若yi

{x1，x2,…,xn}

從上述集合中刪除ui/yi

刪除之后剩下的元素構(gòu)成的集合稱作與的乘積，記為·。2022/11/22鄭州大學(xué)振動(dòng)工程研究所例如設(shè)有如下代換：={f(y)/x,z/y}，={a/x,b/y,y/z}現(xiàn)在來(lái)求·

先做代換：{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對(duì)于Z，因?yàn)樗粚儆趚i，所以y/z就不能刪除2022/11/22鄭州大學(xué)振動(dòng)工程研究所合一：尋找項(xiàng)對(duì)變量的代換以使兩表達(dá)式一致，就叫合一設(shè)有公式集F={F1，F(xiàn)2，…,Fn},若存在一個(gè)代換使得F1=F2=…=Fn，則稱為公式集F的一個(gè)合一代換，且稱F1，F(xiàn)2，…,Fn是可合一的。例如：對(duì)于公式集F={P(x,y，f(y)),P(a,g(x),z)}，則={a/x，g(a)/y，f(g(a))/z}是公式F的一個(gè)合一。(原因：將的代換關(guān)系帶入公式集，可知公式集中的2個(gè)公式是等價(jià)的。)2022/11/22鄭州大學(xué)振動(dòng)工程研究所一個(gè)公式的合一一般不是唯一的。但如果是公式集F的一個(gè)合一，若對(duì)任一個(gè)合一都存在一個(gè)代換使得：=·

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

xk}Fk+1=Fk{tk/xk}k=k+1轉(zhuǎn)（2）（5）算法停，F(xiàn)的最一般合一不存在。2022/11/22鄭州大學(xué)振動(dòng)工程研究所沖突消解策略在推理的過程中，系統(tǒng)不斷的用已知的事實(shí)與知識(shí)庫(kù)中的知識(shí)進(jìn)行匹配，此時(shí)可能發(fā)生如下三種情況：（1）已知事實(shí)不能與知識(shí)庫(kù)中的任何知識(shí)匹配成功。（2）已知事實(shí)恰好與知識(shí)庫(kù)中的一條知識(shí)匹配成功。（3）已知事實(shí)可與知識(shí)庫(kù)中的多條知識(shí)匹配成功。第一種情況中,使得推理無(wú)法進(jìn)行下去,第二種情況恰好匹配,第三種情況則出現(xiàn)沖突，需要按一定的策略解決沖突。2022/11/22鄭州大學(xué)振動(dòng)工程研究所目前解決沖突的策略有多種，其基本思想都是對(duì)知識(shí)進(jìn)行排序，常用的有以下幾中：1、按針對(duì)性排序設(shè)有如下兩條產(chǎn)生式規(guī)則：r1:IFA1andA2and…AnTHENH1r2:IFB1andB2and…BmTHENH2如果存在最一般合一，使得r1中每一個(gè)Ai都可變成相應(yīng)的Bi，即r2中除了包含的r1全部條件A1,A2,…,An外，還包含其它條件，則稱r2比r1有更大的針對(duì)性，r1比r2有更大的通用性。2022/11/22鄭州大學(xué)振動(dòng)工程研究所上面的策略是優(yōu)先選用針對(duì)性較強(qiáng)的產(chǎn)生式規(guī)則。(即應(yīng)選用r2)因?yàn)樗蟮臈l件較多，其結(jié)論一般更接近目標(biāo)，一旦得到滿足，可縮短推理過程。2022/11/22鄭州大學(xué)振動(dòng)工程研究所2、按已知事實(shí)的新鮮性排序在產(chǎn)生式系統(tǒng)推理過程中，每應(yīng)用一條產(chǎn)生式規(guī)則就會(huì)得到一個(gè)或多個(gè)結(jié)論，數(shù)據(jù)庫(kù)就會(huì)增加新的事實(shí)。把數(shù)據(jù)庫(kù)后生成的事實(shí)稱為新鮮的事實(shí)，即后生成的事實(shí)比先生成的事實(shí)具有較大的新鮮性。設(shè)規(guī)則r1可與事實(shí)組A匹配成功，規(guī)則r2可與事實(shí)組B匹配成功，則A與B中哪一組新鮮與它匹配的產(chǎn)生式規(guī)則就先被應(yīng)用。2022/11/22鄭州大學(xué)振動(dòng)工程研究所3、按匹配度排序在不確定性匹配中，為了確定兩個(gè)知識(shí)模式是否可以匹配，需要計(jì)算這兩個(gè)模式的相似程度，當(dāng)其相似程度達(dá)到某個(gè)預(yù)定的值時(shí)，就認(rèn)為它們是可匹配的。若兩條規(guī)則均按匹配度匹配成功，則匹配度大的那條規(guī)則優(yōu)先啟用。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4、根據(jù)領(lǐng)域問題的特點(diǎn)排序某些領(lǐng)域問題可事先知道它的某些特性，可根據(jù)這些特性把知識(shí)排成固定的順序，按照領(lǐng)域知識(shí)特性決定匹配順序。2022/11/22鄭州大學(xué)振動(dòng)工程研究所5、按上下文限制排序把產(chǎn)生式規(guī)則按它們所描述的上下文分成若干組，在不同的條件下，只能從相應(yīng)的組中選取有關(guān)的產(chǎn)生式規(guī)則。這樣可以減少?zèng)_突的發(fā)生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)用。2022/11/22鄭州大學(xué)振動(dòng)工程研究所從一組已知的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。其中，基本的推理規(guī)則是P規(guī)則、T規(guī)則、假言推理、拒取式推理等。假言推理的一般形式是：P，PQQ拒取式的一般形式是PQ，QP以下是自然演繹推理的例子：2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.2自然演繹推理（續(xù)）例1：已知A，B，AC，BCD，DQ求證Q1、AP規(guī)則2、AC

P規(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ī)則：在推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)永真蘊(yùn)涵公式S，則可把S引入推理過程。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.2自然演繹推理（續(xù)）例2設(shè)已知如下事實(shí)；（1）凡是容易的課程小王（Wang)都喜歡。（2）C班的課程都是容易的。（3）ds是C班的一門課程求證小王喜歡ds這門課程。證明：首先定義謂詞如下：EASY(x):x是容易的LIKE(x,y):x喜歡yC(x):x是C班的一門課程于是問題可以表示成：2022/11/22鄭州大學(xué)振動(dòng)工程研究所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)得證2022/11/22鄭州大學(xué)振動(dòng)工程研究所

4.2自然演繹推理（續(xù)）自然演繹推理的優(yōu)點(diǎn)是表達(dá)定理證明過程自然，容易理解，擁有豐富的推理規(guī)則，推理過程靈活，便于在推理過程中嵌入領(lǐng)域啟發(fā)知識(shí)。缺點(diǎn)是容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一般呈指數(shù)形式遞增，這對(duì)于一個(gè)大型推理問題是十分不利的，甚至是不可能實(shí)現(xiàn)的。2022/11/22鄭州大學(xué)振動(dòng)工程研究所以下還有的推理方法：歸結(jié)演繹推理與/或形演繹推理自己看書2022/11/22鄭州大學(xué)振動(dòng)工程研究所定理證明是人工智能的一個(gè)重要研究領(lǐng)域，這不僅僅是因?yàn)樵S多數(shù)學(xué)問題要通過定理證明得以解決，很多非數(shù)學(xué)問題（如醫(yī)療診斷、機(jī)器人規(guī)劃及難題求解等）也都?xì)w結(jié)為一個(gè)定理證明問題。定理證明的實(shí)質(zhì)是對(duì)前提P和結(jié)論Q證明PQ的永真性。但是證明一個(gè)謂詞公式的永真性不像證明一個(gè)命題公式的永真性那麼簡(jiǎn)單，（它牽涉到謂詞變量、客體變量及函數(shù)符號(hào)）在某些情況下甚至是行不通的。在這種情況下，人們提出了用反證法來(lái)解決問題的思路。在這方面，海伯倫和魯賓遜都作出了杰出的貢獻(xiàn)。兩人的研究都是以子句集為背景展開的。接下來(lái)，我們介紹這些概念。2022/11/22鄭州大學(xué)振動(dòng)工程研究所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)成的集合稱為子句集。在謂詞邏輯中任何一個(gè)謂詞公式均可通過等價(jià)變換化為相應(yīng)的子句集。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理（續(xù)）化子句集的步驟如下：1、利用等價(jià)公式消去公式中的邏輯連接詞“”和“”：PQPQPQ（PQ）（PQ）2、利用下列公式將否定符號(hào)“”深入到單個(gè)變?cè)癙P（PQ）PQ（PQ）PQ(x)P(x)P(x)P(x)P2022/11/22鄭州大學(xué)振動(dòng)工程研究所3、重新命名變?cè)?，使不同量詞約束的變?cè)胁煌拿?、消去存在量詞。分兩種情況處理：一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，此時(shí)只要用一個(gè)新的個(gè)體常量替換受該存在量詞約束的變?cè)涂上ゴ嬖诹吭~；另一種情況是存在量詞位于一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，例如（x1)（x2)…(xn)(y)P(x1,x2,…,xn,y)此時(shí)需要用Skolem函數(shù)f(x1,x2,…,xn)替換受該存在量詞約束的變?cè)?，然后才能消去存在量詞。5、把全稱量詞全部移到公式的左邊。6、利用等價(jià)關(guān)系P（QR）=（PQ）（PR）把公式化為Skolem標(biāo)準(zhǔn)型。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理（續(xù)）Skolem標(biāo)準(zhǔn)型的一般形式是：（x1)（x2)…(xn)M其中，M是子句的合取式，稱為Skolem標(biāo)準(zhǔn)型的母式。7、消去全稱量詞8、對(duì)變?cè)?，使不同子句中的變?cè)煌?、消去合取連接詞，變?yōu)樽泳浼?。子句集中各子句之間是合取關(guān)系。謂詞公式是不可滿足的，則其子句集合是不可滿足的，反之亦然。2022/11/22鄭州大學(xué)振動(dòng)工程研究所

4.3歸結(jié)演繹推理（續(xù)）如何證明一個(gè)子句集是不可滿足的呢？下面就海伯倫理論和魯賓遜的歸結(jié)原理進(jìn)行討論。一、海伯倫理論要判定一個(gè)子句集是否是不可滿足的，需要對(duì)子句集中的謂詞公式進(jìn)行判定，而謂詞公式的判定需要對(duì)個(gè)體域上的任何解釋進(jìn)行判定，這是很困難的。海伯倫定義了一個(gè)特殊的域稱為海伯倫域，在任何域上的判定，只要在海伯倫域上進(jìn)行即可。*設(shè)S是子句集，則按下述方法構(gòu)造的域H稱為是海伯倫域：2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理（續(xù)）1、令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則令H0=[a}，其中a為任意指定的一個(gè)個(gè)體常量。2、令Hi+1=Hi{S中所有n元函數(shù)f(x1,x2,…,xn)|xj(j=1,2,…,n)是Hi中的元素}，其中，i=0,1,…。下面通過例子來(lái)解釋這個(gè)定義。例1求子句集S={P(x)Q(x),R(f(y))}的H域。解：因?yàn)镾中沒有個(gè)體常量，所以指定a作為個(gè)體常量，于是得到：H0={a},H1={a,f(a)},H2={a,f(a),f(f(a))},…,H={a,f(a),f(f(a)),…}2022/11/22鄭州大學(xué)振動(dòng)工程研究所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域。解：由于該子句集中既無(wú)個(gè)體常量，又無(wú)函數(shù)，所以可任意指定一個(gè)常量a作為個(gè)體常量，從而得到H0=H1=…=H={a}有定理說(shuō)：子句集S是不可滿足的充要條件是S對(duì)H域上的一切解釋都為假。并且海伯倫證明了若子句集S在任何域D上的解釋能滿足S，則在H域上相應(yīng)的解釋也能滿足S。下面我們說(shuō)明，S在H域上解釋的定義：9、消去合取連接詞，變?yōu)樽泳浼?。鄭州大學(xué)振動(dòng)工程研究所在不確定性匹配中，為了確定兩個(gè)知識(shí)模式是否可以匹配，需要計(jì)算這兩個(gè)模式的相似程度，當(dāng)其相似程度達(dá)到某個(gè)預(yù)定的值時(shí)，就認(rèn)為它們是可匹配的。將該知識(shí)的一個(gè)運(yùn)用條件混合推理適應(yīng)于下列情況：并稱c12是c1和c2的歸結(jié)式，c1和c2則稱為c12的親本子句。(u)(~P(x,y,f(x,y))Q(x,u))而P（x)、Q(x,g(x))、P(x,f(x))等都是文字。8、DQP規(guī)則鄭州大學(xué)振動(dòng)工程研究所（PQ）PQ鄭州大學(xué)振動(dòng)工程研究所并把不包含任何文字的子句稱為空子句。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）子句集S在H域上的一個(gè)解釋滿足下列條件：1、在解釋I下，常量映射到自身；2、S中的任一個(gè)n元函數(shù)是HnH的映射。即，設(shè)h1,h2,…,hnH,則f(h1,h2,…,hn)H;3、S中的任一n元謂詞是Hn{T，F(xiàn)}的映射。即謂詞的真值可以指派T也可指派F。海伯倫在理論上證明了子句集不可滿足性的可行性及方法，但要在計(jì)算機(jī)上實(shí)現(xiàn)其證明過程還是很困難的。1965年魯賓遜提出了歸結(jié)原理，使機(jī)器證明成為現(xiàn)實(shí)2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）*魯賓遜歸結(jié)原理歸結(jié)原理也稱消解原理，是魯賓遜提出的一種證明子句不可滿足性，從而實(shí)現(xiàn)定理證明的一種理論及方法。由謂詞公式轉(zhuǎn)化為子句集的過程可以看出，在子句集中子句之間的關(guān)系是合取關(guān)系，其中只要有一個(gè)子句不可滿足，則子句集就不可滿足。前面，我們?cè)?jīng)說(shuō)過空子句是不可滿足的，即一個(gè)子句集中若含空子句，則它是不可滿足的。歸結(jié)原理的基本思想就是檢查子句集中是否含空子句，若含則子句集S不可滿足，或說(shuō)證明一個(gè)謂詞公式是永假的過程，就是歸結(jié)由此公式轉(zhuǎn)換成的子句集包含空子句的過程。2022/11/22鄭州大學(xué)振動(dòng)工程研究所

4.3歸結(jié)演繹推理(續(xù)）下面我們先來(lái)說(shuō)明命題邏輯中的歸結(jié)原理定義P是原子謂詞公式，則稱P與P為互補(bǔ)文字。我們知道在命題邏輯中有公式：PQ,QRPR即PQ，QRPR

c1c2c12顯然上述公式向我們展示的是在子句c1

中存在文字Q，在子句c2中存在Q的補(bǔ)文字Q，把這一對(duì)互補(bǔ)文字消去，剩下的文字析取起來(lái)就是子句

c1和c2的邏輯結(jié)果c12。并稱c12是c1和c2的歸結(jié)式，c1和c2則稱為c12的親本子句。2022/11/22鄭州大學(xué)振動(dòng)工程研究所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é)過程可以用下面的一個(gè)樹形結(jié)構(gòu)很清楚的表現(xiàn)出來(lái)。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）

PQQR

PRP

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

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

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

，…,Pn的公式集，Q為目標(biāo)公式，歸結(jié)反演的過程：是把{F，Q}，化為子句集S，對(duì)S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式并入S中，若出現(xiàn)空子句，則停止歸結(jié)，即證明Q為真。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）下面我們用例子來(lái)說(shuō)明這個(gè)過程見P134從上面的例子可以看出歸結(jié)過程關(guān)鍵的是從子句集中找出可進(jìn)行歸結(jié)的一對(duì)子句。機(jī)器上用的是水平浸透法，這一過程可能產(chǎn)生大量無(wú)用子句，造成時(shí)間和空間的浪費(fèi)。因此，如何提高消解效率就變成一個(gè)重要的研究課題。下面提出的都是一些有效的方法：1、刪除策略從水平浸透法的本質(zhì)可以看出，提高消解效率的要害是使子句集合中子句的數(shù)量越少越好，子句中文字的數(shù)量越少越好。刪除策略正是從這一點(diǎn)考慮提出的。幾種刪除方法如下：2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）（1）純文字刪除法如果某文字L在子句集中不存在可與之互補(bǔ)的文字L，則稱該文字是為純文字。顯然在歸結(jié)時(shí)純文字不可能消去，因此，包含它的子句進(jìn)行歸結(jié)時(shí)不可能得到空子句，即這樣的子句對(duì)歸結(jié)是無(wú)意義的，所以，這樣的子句從子句集中刪除。（請(qǐng)給出純文字刪除的算法實(shí)現(xiàn)）（2）重言式刪除法如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對(duì)，則稱該子句為重言式，顯然重言式不會(huì)影響子句集合S的不可滿足性，所以，可以從子句集合中刪除。（給出檢查一個(gè)公式是否是重言式的算法實(shí)現(xiàn)）（3）包孕刪除法（被歸類的子句可以刪除）設(shè)有子句C1和C2，如果存在代換，使得C1C2，則稱C1包孕于C2或說(shuō)C2包孕C1，包的子句可以刪除，即2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）子句C2可以刪除。（想一想它的原理是什麼？P（PQ）=P）2、支持集策略每次歸結(jié)時(shí)，親本子句中至少應(yīng)有一個(gè)是由目標(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é)正向推理、逆向推理、混合推理、雙向推理。主要缺點(diǎn)：初始目標(biāo)的選擇有盲目性，若不符合實(shí)際，就要多次提出假設(shè)，影響到系統(tǒng)效率。（注：ti是用代換來(lái)替換ti中的項(xiàng)）2、C(ds)EASY(ds)T規(guī)則1鄭州大學(xué)振動(dòng)工程研究所而P（x)、Q(x,g(x))、P(x,f(x))等都是文字。鄭州大學(xué)振動(dòng)工程研究所另一方面從某假設(shè)目標(biāo)出發(fā)進(jìn)行逆向推理，但并不推至原始事實(shí)，而是讓它們?cè)谥型鞠嘤?，即由正向推理所得的中間結(jié)論恰好是逆向推理此時(shí)所需要的證據(jù)，這時(shí)推理就可結(jié)束，逆向推理時(shí)所做的假設(shè)就是推理的最終結(jié)論。C2=QR用支持集歸結(jié)的過程是：1、在解釋I下，常量映射到自身；若用最一般合一去代換那些可合一的謂詞公式，可使它們變成完全一致的公式。鄭州大學(xué)振動(dòng)工程研究所3、x(EASY(x)LIKE(Wang,x))P規(guī)則即謂詞的真值可以指派T也可指派F。*設(shè)S是子句集，則按下述方法構(gòu)造的域H稱為是海伯倫域：*設(shè)S是子句集，則按下述方法構(gòu)造的域H稱為是海伯倫域：2022/11/22鄭州大學(xué)振動(dòng)工程研究所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頁(yè)的圖4-10來(lái)描述。3、線性輸入策略線性歸結(jié)是這樣一種歸結(jié)，首先從子句集中選取一個(gè)稱為頂子句的子句C0

開始做歸結(jié)，其次是歸結(jié)過程中所得到的歸結(jié)式Ci立即同另一子句Bi進(jìn)行歸結(jié)得歸結(jié)式Ci+1。而BiSCk(k<i)(已出現(xiàn)過的歸結(jié)式）。這里關(guān)鍵的問題是頂子句的選擇，一般選擇結(jié)論的否定作為頂子句。2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）例如：證明PQ，PQ，PQPQ解，問題轉(zhuǎn)化成證子句集合S={PQ，PQ，PQ，PQ}的不可滿足問題，用線形消解的圖解表示如下：2022/11/22鄭州大學(xué)振動(dòng)工程研究所4.3歸結(jié)演繹推理(續(xù)）4、單文字子句策略如果一個(gè)子句只包含一個(gè)文字，則稱它為單文字子句。單文字子句策略要求參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是單文字子句。例子見P142頁(yè)的例4.20.但單文字策略是不完備的，即當(dāng)子句集合中不存在單文字子句時(shí)，不能使用單文字子句策略。5、祖先過濾形策略該策略與線性