第3章確定性推理

人工智能原理篇確定性推理第三章本章導(dǎo)讀知識表示方法能夠?qū)⒅R以某種模式表示出來并存儲到計算機中，而計算機真正的智能是其具有思維能力，即能運用知識進行推理來求解問題。本章從推理的概念入手，介紹確定性推理的方式，包括自然演繹推理和歸結(jié)演繹推理。學(xué)習(xí)目標(biāo)熟悉推理的概念、方式及分類。理解推理方向和沖突消解策略。掌握自然演繹推理和歸結(jié)演繹推理的推理方法，并能夠使用它們求解問題。目錄

4推理概述自然演繹推理歸結(jié)演繹推理010203推理概述01推理的概念3.1.1推理是指從已知事實出發(fā)，按照某種策略，運用已掌握的知識，推導(dǎo)出其中蘊含的事實性結(jié)論或歸納出某些新的結(jié)論的過程。推理所用的事實可分為兩種，一種是推理前用戶提供的與求解問題有關(guān)的初始證據(jù)；另一種是推理過程中所得到的中間結(jié)論，這些中間結(jié)論可以作為進一步推理的證據(jù)。通常，智能系統(tǒng)的推理過程由推理機來完成。所謂推理機就是智能系統(tǒng)中用來實現(xiàn)推理的那些程序。1．按推理的邏輯基礎(chǔ)分類按推理的邏輯基礎(chǔ)分類，推理可分為演繹推理、歸納推理和默認推理。（1）演繹推理是從已知的一般性知識出發(fā)，推出蘊含在已知知識中的適合于某種個別情況的結(jié)論。它是一種從一般到個別的推理方式。演繹推理是人工智能系統(tǒng)中的一種重要的推理方式，它的一般模式是三段論式。三段論式包含3個部分，即大前提、小前提和結(jié)論。①大前提是已知的一般性知識或推理過程得到的判斷。②小前提是關(guān)于某種具體情況或某個別事實的判斷。③結(jié)論是由大前提推出的，并適合于小前提的新判斷。3.1.2推理方式及分類人類的智能活動有多種思維方式，相應(yīng)地，對人類智能進行模擬的人工智能也有多種推理方式。下面從不同的角度對推理方式進行分類。（2）歸納推理是從大量特殊事例出發(fā)，歸納出一般性結(jié)論的推理過程。它是一種由個別到一般的推理方式。對于歸納推理，按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理。①完全歸納推理是指在進行歸納時需要考察相應(yīng)事物的全部對象，并根據(jù)這些對象是否具有某種屬性，從而推出該類事物是否具有此屬性。例如，計算機質(zhì)量檢測時，如果對每一臺計算機都進行檢測，且質(zhì)量都合格，就可以推出“計算機質(zhì)量合格”的結(jié)論。②不完全歸納推理是指在進行歸納時只考察相應(yīng)事物的部分對象，就得出關(guān)于該事物的結(jié)論。例如，隨機抽取部分計算機進行質(zhì)量檢測，如果這部分計算機都合格，則可以推出“計算機質(zhì)量合格”的結(jié)論。知識庫演繹推理與歸納推理的區(qū)別如下：演繹推理是在已知領(lǐng)域內(nèi)的一般性知識的前提下，通過演繹證明一個結(jié)論的正確性或者求解一個具體問題。由演繹推理推出的結(jié)論實際上早已蘊含在一般性知識中。演繹推理只不過是將已有事實揭露出來，因此它不能增殖新知識。歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的，這種由個別事物或現(xiàn)象推出一般性知識的過程，是增殖新知識的過程。例如，一位計算機維修員從書本學(xué)習(xí)知識到通過大量實例積累經(jīng)驗，是一種歸納推理方式。計算機維修員運用這些一般性知識去維修計算機的過程則屬于演繹推理。（3）默認推理又稱為缺省推理，是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進行的推理。也就是說，在進行推理時，如果對某些證據(jù)不能證明其不成立的情況下，先假設(shè)它們是成立的，并將它們作為推理的依據(jù)進行推理。例如，要編制人工智能課程的測試題，但是不知道參加測試的計算機系學(xué)生是否都會編程，則默認計算機系學(xué)生都會編程，因此，可以推出“這份人工智能課程的測試題中可以含有編程題”。高手點撥在使用默認推理方式進行推理的過程中，如果加入的新知識或所推出的中間結(jié)論與已有知識發(fā)生矛盾，則說明前面有關(guān)證據(jù)的假設(shè)是不正確的，這時就需要撤銷原來的假設(shè)及由此假設(shè)所推出的所有結(jié)論，重新按照新情況進行推理。2．按推理時所用知識的確定性分類按推理時所用知識的確定性分類，推理可分為確定性推理和不確定性推理。（1）確定性推理是指推理時所使用的知識都是確定的，推出的結(jié)論也都是確定的，而且它們的真值非真即假，不會有第三種情況出現(xiàn)。（2）不確定性推理是指推理時所用的知識不都是確定的，推出的結(jié)論也是不確定的，它們的真值會位于真與假之間。添磚加瓦經(jīng)典邏輯推理是最先提出的一類推理方式，是根據(jù)經(jīng)典邏輯的規(guī)則進行的一種推理。經(jīng)典邏輯主要包括命題邏輯和一階謂詞邏輯，它們的真值都是確定的。因此，經(jīng)典邏輯推理是一種確定性推理。非經(jīng)典邏輯推理是基于非經(jīng)典邏輯的規(guī)則進行的一種推理。非經(jīng)典邏輯主要包括三值邏輯、多值邏輯和模糊邏輯等，它們的真值都是不確定的。因此，非經(jīng)典邏輯推理是一種不確定性推理。3．按推理過程中是否會出現(xiàn)反復(fù)的情況分類按推理過程中所推出的結(jié)論是否單調(diào)地增加，或者按推理過程所得到的結(jié)論是否越來越接近最終目標(biāo)分類，推理可分為單調(diào)推理和非單調(diào)推理。（1）單調(diào)推理是指在推理的過程中隨著推理的向前推進及新知識的加入，推出的結(jié)論呈單調(diào)增加的趨勢，并且結(jié)論越來越接近最終目標(biāo)。單調(diào)推理在推理的過程中不會出現(xiàn)反復(fù)的情況，如基于經(jīng)典邏輯的演繹推理。（2）非單調(diào)推理是指在推理過程中由于新知識的加入，不僅沒有加強已推出的結(jié)論，反而否定了它，使得推理退回到前面的某一步，然后重新開始推理。非單調(diào)推理一般在知識不完全的情況下發(fā)生，如默認推理。4．按推理過程中是否運用啟發(fā)性知識分類按推理過程中是否運用與問題有關(guān)的啟發(fā)性知識分類，推理可分為啟發(fā)式推理和非啟發(fā)式推理。（1）如果在推理過程中，運用了與問題有關(guān)的啟發(fā)性知識，如解決問題的策略、技巧及經(jīng)驗等，以加快推理過程，求得問題最優(yōu)解，則稱這種推理過程為啟發(fā)式推理。（2）如果在推理過程中，不運用啟發(fā)性知識，只按照一般的控制邏輯進行推理，則稱這種推理過程為非啟發(fā)式推理。推理方向用來確定推理的驅(qū)動方式，包括數(shù)據(jù)（證據(jù)）驅(qū)動和目標(biāo)驅(qū)動。所謂數(shù)據(jù)驅(qū)動是指推理過程從初始證據(jù)開始直到目標(biāo)結(jié)束；而目標(biāo)驅(qū)動則是指推理過程從目標(biāo)開始進行反向推理，直到出現(xiàn)與初始證據(jù)相吻合的結(jié)果。按照推理方向不同，推理可分為正向推理、逆向推理和混合推理。3.1.3推理方向正向推理是一種從已知事實出發(fā)，正向使用推理規(guī)則的推理方式，它是一種數(shù)據(jù)驅(qū)動的推理方式，又稱為前項鏈推理或自底向上推理。正向推理的基本思路如下。（1）從用戶提供的初始已知事實出發(fā)，在知識庫KB中找出當(dāng)前適用的知識，構(gòu)成知識集KS。（2）按某種沖突消解策略從KS中選出一條知識進行推理，并將推出的新事實加入數(shù)據(jù)庫DB中，作為下一步推理的已知事實。（3）在知識庫中選取可適用知識進行推理，如此重復(fù)這一過程，直到求得了問題的解或者知識庫中再無可適用的知識為止。1．正向推理正向推理的過程可用如左圖所示的算法描述。（1）將用戶提供的初始已知事實送入數(shù)據(jù)庫DB中。（2）檢查DB中是否已經(jīng)包含了該問題的解，若有，則求解結(jié)束，并成功退出，否則執(zhí)行下一步。（3）根據(jù)DB中的已知事實，掃描知識庫KB，檢查KB中是否含有可適用（即可與DB中已知事實匹配）的知識，若有則轉(zhuǎn)到（4），否則轉(zhuǎn)到（6）。（4）把KB中所有的適用知識都選出來，構(gòu)成可適用的知識集KS。（5）若KS不為空，則按某種沖突消解策略從中選出一條知識進行推理，并將推出的新知識加入DB中，然后轉(zhuǎn)到（2）；若KS為空，則轉(zhuǎn)到（6）。（6）詢問用戶是否可進一步補充新事實，若可以補充，則將補充的新事實加入DB中，然后轉(zhuǎn)到（3），否則表示求不出解，失敗退出。逆向推理是一種以某個假設(shè)為出發(fā)點，反向運用推理規(guī)則的推理方式，它是一種目標(biāo)驅(qū)動的推理方式，又稱為反向鏈推理或自頂向下推理。逆向推理的基本思路如下：（1）選定一個假設(shè)（目標(biāo)）。（2）尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則原假設(shè)成立；若無論如何都找不到所需要的證據(jù)，則說明原假設(shè)不成立，需要另作新的假設(shè)。2．逆向推理逆向推理的過程可用如左圖所示的算法描述。（1）提出要求證的假設(shè)。（2）檢查該假設(shè)是否已在數(shù)據(jù)庫DB中，若在，則該假設(shè)成立，退出推理或者對下一個假設(shè)進行驗證；否則，轉(zhuǎn)到下一步（3）。（3）判斷假設(shè)是否是證據(jù)，即它是否為應(yīng)由用戶證實的原始事實。若是，則咨詢用戶，否則，轉(zhuǎn)到（4）。（4）在知識庫KB中尋找有可能導(dǎo)出該假設(shè)的知識，形成適用的知識集合KS，然后轉(zhuǎn)到（5）。（5）從KS中選出一條知識，并將知識運用的條件作為新的假設(shè)，然后轉(zhuǎn)到（2）?；旌贤评硎前颜蛲评砗湍嫦蛲评斫Y(jié)合起來使用以解決較復(fù)雜問題的方法。當(dāng)問題中出現(xiàn)已知事實不充分、正向推理推出的結(jié)論可信度不高或用戶希望得到更多的結(jié)論等情況時，通常需要采用混合推理。混合推理分為3種類型，即先正向后逆向混合推理、先逆向后正向混合推理和雙向混合推理。（1）先正向后逆向混合推理是指先正向推理，從已知事實出發(fā)推出部分結(jié)論，然后再用逆向推理對這些結(jié)論進行證實或提高它們的可信度，其推理過程如圖所示。3．混合推理（2）先逆向后正向混合推理是指先逆向推理，從假設(shè)出發(fā)推出一些中間假設(shè)，然后再用正向推理對這些中間假設(shè)進行證實，其推理過程如圖所示。（3）雙向混合推理是指正向推理與逆向推理同時進行，并在推理過程中的某一步完美銜接在一起的推理。3．混合推理高手點撥雙向混合推理中，一方面根據(jù)已知事實進行正向推理，但并不能推導(dǎo)出最終目標(biāo)；另一方面從某假設(shè)出發(fā)進行逆向推理，但并不能推至原始事實，而是讓由正向推理所得到的中間結(jié)論恰好與逆向推理所要求的證據(jù)相遇，此時推理結(jié)束。逆向推理時所作的假設(shè)就是推理的最終結(jié)論。在推理過程中，系統(tǒng)要不斷地用自己當(dāng)前已知的事實與知識庫中的知識進行匹配，匹配過程中會出現(xiàn)3種情況。（1）已知事實不能與知識庫中的任何知識匹配成功。（2）已知事實恰好只與知識庫中的一個知識匹配成功。（3）已知事實可與知識庫中的多個知識匹配成功，或者有多個已知事實都可與知識庫中某一知識匹配成功，或者有多個已知事實可與知識庫中的多個知識匹配成功。3.1.4沖突消解策略如果推理過程中，出現(xiàn)情況（3），即不僅有知識匹配成功，而且有多個知識匹配成功，則稱為發(fā)生了沖突。按一定的策略從匹配成功的多個知識中選出一個知識用于當(dāng)前推理的過程稱為沖突消解。

解決沖突時所用的策略稱為沖突消解策略。目前已有多種沖突消解策略，其基本思想都是對知識進行排序。常用的沖突消解策略有以下幾種。（1）按就近原則排序，即把最近使用過的規(guī)則賦予較高的優(yōu)先級。（2）按已知事實的新鮮性排序。一般認為新鮮事實是對舊知識的更新和改進，因此，后生成的事實比先生成的事實具有較高的優(yōu)先級。（3）按匹配度排序。在不確定性推理時，匹配度不僅可確定兩個知識模式是否可匹配，還可用于沖突消解。根據(jù)匹配程度來決定哪一個產(chǎn)生式規(guī)則優(yōu)先應(yīng)用。（4）按領(lǐng)域問題特點排序。該方法按照求解問題領(lǐng)域的特點將知識排成固定的次序。（5）按上下文限制排序，即將知識按照所描述的上下文分成若干組，在推理過程中根據(jù)當(dāng)前數(shù)據(jù)庫中的已知事實與上下文的匹配情況，確定選擇某組中的某條知識。（6）按條件個數(shù)排序。多條規(guī)則生成結(jié)論相同的情況下，由于條件個數(shù)較少的規(guī)則匹配所花費的時間較少而且容易實現(xiàn)，所以將條件少的規(guī)則賦予較高的優(yōu)先級，優(yōu)先啟用。（7）按規(guī)則的次序排序，即以知識庫中預(yù)先存入規(guī)則的排列順序作為知識排列的依據(jù)，排在前面的規(guī)則具有較高的優(yōu)先級。自然演繹推理02自然演繹推理是指從一組已知為真的事實出發(fā)，直接運用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過程。

3.2.1推理規(guī)則的一般形式自然演繹推理中的推理規(guī)則有假言推理、拒取式推理、三段論式推理等。

提示

利用自然演繹推理方法求解問題的一般步驟如下：（1）根據(jù)已知事實和待求解問題定義謂詞。（2）將已知事實和待求解問題用謂詞公式表示。（3）使用推理規(guī)則進行推理。3.2.2利用自然演繹推理解決問題現(xiàn)有已知事實，小李喜歡所有編程課；所有的程序設(shè)計語言課都是編程課；Python是一門程序設(shè)計語言課。請求證：小李喜歡Python這門課。3.2.3案例：個人喜好

歸結(jié)演繹推理03

3.3.1子句集由子句構(gòu)成的集合稱為子句集。2．謂詞公式化為子句集的基本步驟在謂詞邏輯中，任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集，從而能夠比較容易地判斷謂詞公式的不可滿足性。

（4）化為前束形

前束形就是指把所有量詞都移動到公式的前面，即前束形=（前綴）{母式}其中，（前綴）是量詞串，{母式}是不含量詞的謂詞公式?；癁榍笆蔚姆椒ㄊ前阉辛吭~都移到公式的左邊，并且在移動時不能改變量詞的相對順序。

（8）消去合取詞，把母式用子句集表示。對于上例有{?P(x，f(x))∨R(x，f(x))，?Q(x，f(x))∨R(x，f(x))}（9）子句變元標(biāo)準(zhǔn)化

對子句集中的某些變元重新命名，使任意兩個子句中不出現(xiàn)相同的變元名。對于上例，可把子句集中第二個子句的變元名x更換為y，可得到

顯然，在子句集中各子句之間是合取關(guān)系。

添磚加瓦謂詞公式可以化為相應(yīng)的子句集，定理“謂詞公式不可滿足的重要條件是其子句集不可滿足”表明了兩者之間的不可滿足性是等價的。由此定理可知，要證明一個謂詞公式是不可滿足的，只要證明相應(yīng)的子句集是不可滿足的就可以了。

對謂詞公式的不可滿足性分析可以轉(zhuǎn)化為對其子句集的不可滿足性分析。為了判定子句集的不可滿足性，就需要對子句集中的子句進行判定。對于不可滿足性，子句與子句集之間具有以下聯(lián)系。（1）由謂詞公式化為子句集的過程可知，子句集中子句之間是合取關(guān)系。因此，子句集中只要有一個子句為不可滿足的，則整個子句集就是不可滿足的。（2）空子句是不可滿足的。因此，一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。3.3.2歸結(jié)原理

歸結(jié)過程的樹形表示

學(xué)有所獲由上述推論可得到下列結(jié)論。（1）為證明子句集的不可滿足性，只要對其中可進行歸結(jié)的子句進行歸結(jié)，并把歸結(jié)式加入子句集中，或者用歸結(jié)式代替它的親本子句，然后證明新子句集的不可滿足性就可以了。（2）如果歸結(jié)過程中得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集是不可滿足的。2．謂詞邏輯歸結(jié)原理在謂詞邏輯中，由于子句集中的謂詞一般都含有變元，因此不能像命題邏輯那樣直接消去互補文字，而需要先用最一般合一對變元進行置換，然后才能進行歸結(jié)。

可見謂詞邏輯的歸結(jié)要比命題邏輯的歸結(jié)更麻煩。

（2）在求歸結(jié)式時，不能同時消去兩個互補文字對，因為消去兩個互補文字對所得的結(jié)果不是兩個親本子句的邏輯推論。（3）如果參加歸結(jié)的子句內(nèi)含有可合