第3章確定性推理

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

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

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

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

提示

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

歸結(jié)演繹推理03

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

（4）化為前束形

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

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

對(duì)子句集中的某些變?cè)匦旅?，使任意兩個(gè)子句中不出現(xiàn)相同的變?cè)?。?duì)于上例，可把子句集中第二個(gè)子句的變?cè)鹸更換為y，可得到

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

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

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

歸結(jié)過(guò)程的樹(shù)形表示

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

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

（2）在求歸結(jié)式時(shí)，不能同時(shí)消去兩個(gè)互補(bǔ)文字對(duì)，因?yàn)橄蓚€(gè)互補(bǔ)文字對(duì)所得的結(jié)果不是兩個(gè)親本子句的邏輯推論。（3）如果參加歸結(jié)的子句內(nèi)含有可合