人工智能第四章經(jīng)典邏輯推理課件

第4章經(jīng)典邏輯推理4.1推理的基本概念4.2自然演繹推理4.3歸結(jié)演繹推理4.4與/或形演繹推理1第4章經(jīng)典邏輯推理4.1推理的基本概念1第4章經(jīng)典邏輯推理

智能系統(tǒng)的推理過程實際上就是一種思維過程。即運用知識進行推理來求解問題。經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯（命題邏輯及一階謂詞邏輯）的邏輯規(guī)則進行的一種推理。由于這種推理是基于經(jīng)典邏輯的，其真值只有“真”和“假”兩種，因此它是一種精確推理，或稱為確定性推理。2第4章經(jīng)典邏輯推理智能系統(tǒng)的推理過程實際上就是一種思維過4.1推理的基本概念4.1.1推理方式及其分類4.1.2推理的控制策略4.1.3模式匹配及其變量代換34.1推理的基本概念4.1.1推理方式及其分類34.1.1推理方法及其分類1.按推理的邏輯基礎(chǔ)分類演繹推理歸納推理默認推理44.1.1推理方法及其分類1.按推理的邏輯基礎(chǔ)分類44.1.1推理方法及其分類（1）演繹推理演繹推理是從已知的一般性知識出發(fā)，去推出蘊含在這些已知知識中的適合于某種個別情況的結(jié)論。是一種由一般到個別的推理方法，其核心是三段論， 如假言推理、拒取式和假言三段論。

54.1.1推理方法及其分類（1）演繹推理5（1）演繹推理例：假言三段論 A→B，B→C?A→C 常用的三段論是由一個大前提、一個小前提和一個結(jié)論這三部分組成的。

大前提是已知的一般性知識或推理過程得到的判斷；小前提是關(guān)于某種具體情況或某個具體實例的判斷；結(jié)論是由大前提推出的，并且適合于小前提的判斷。4.1.1推理方法及其分類6（1）演繹推理4.1.1推理方法及其分類64.1.1推理方法及其分類（1）演繹推理例，有如下三個判斷：①計算機系的學(xué)生都會編程序；（一般性知識）②程強是計算機系的一位學(xué)生；（具體情況）③程強會編程序。（結(jié)論）

這是一個三段論推理。其中，①是大前提，②是小前提；③是經(jīng)演繹推出來的結(jié)論?？梢姡浣Y(jié)論是蘊含在大前提中的。74.1.1推理方法及其分類（1）演繹推理74.1.1推理方法及其分類（2）歸納推理 是一種由個別到一般的推理方法。從足夠多的事例中歸納出一般性結(jié)論的推理過程。例如，設(shè)有如下事例：王強是計算機系學(xué)生，他會編程序；高華是計算機系學(xué)生，她會編程序；…………當(dāng)這些具體事例足夠多時，就可歸納出一個一般性的知識：凡是計算機系的學(xué)生，就一定會編程序。84.1.1推理方法及其分類（2）歸納推理84.1.1推理方法及其分類演繹推理與歸納推理的區(qū)別

演繹推理是在已知領(lǐng)域內(nèi)的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結(jié)論的正確性。它所得出的結(jié)論實際上早已蘊含在一般性知識的前提中，演繹推理只不過是將已有事實揭露出來，因此它不能增殖新知識。歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的。這種由個別事物或現(xiàn)象推出一般性知識的過程，是增殖新知識的過程。94.1.1推理方法及其分類演繹推理與歸納推理的區(qū)別94.1.1推理方法及其分類（3）默認推理默認推理又稱為缺省推理，它是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進行的推理。

在默認推理過程中，如果某一時刻發(fā)現(xiàn)原先所作的默認不正確，則就要撤消所作的默認以及由此默認推出的結(jié)論，重新按新情況進行推理。104.1.1推理方法及其分類（3）默認推理104.1.1推理方法及其分類2.按推理時所用知識的確定性（1）確定性推理

確定性推理是指推理時所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或者為假，沒有第三種情況出現(xiàn)。（2）不確定性推理

不確定性推理是指推理時所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于真與假之間。（模糊集）114.1.1推理方法及其分類2.按推理時所用知識的確定性4.1.1推理方法及其分類3.按推理過程中結(jié)論的單調(diào)性（1）單調(diào)推理

單調(diào)推理是指在推理過程中隨著推理過程向前推進及新知識的進入，推出的結(jié)論呈單調(diào)增加的趨勢，并且越來越接近最終目標(biāo)，在推理過程中不會出現(xiàn)反復(fù)的情況，即不會由于新知識的加入否定了前面推出的結(jié)論，從而使推理又退回到前面的某一步。（2）非單調(diào)推理

非單調(diào)推理是指在推理過程中由于新知識的加入，不僅沒有加強已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始。124.1.1推理方法及其分類3.按推理過程中結(jié)論的單調(diào)性14.1.1推理方法及其分類4.按推理過程中用到啟發(fā)性知識（1）啟發(fā)式推理（2）非啟發(fā)式推理5.按方法論（1）基于知識的推理（2）直覺推理（常識性推理）6.按推理的簡繁程度（1）簡單推理（2）復(fù)合推理7.按結(jié)論是否具有必然性（1）必然性推理（2）或然性推理…………134.1.1推理方法及其分類4.按推理過程中用到啟發(fā)性知識4.1.2推理的控制策略推理的控制策略是指如何使用領(lǐng)域知識使推理過程盡快達到目標(biāo)的策略。推理方向搜索策略求解策略沖突消解限制策略144.1.2推理的控制策略推理的控制策略是指如何使用領(lǐng)域知1、推理方向——正向推理從已知事實出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅(qū)動推理或前向鏈推理。算法描述(1)把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫；(2)檢查綜合數(shù)據(jù)庫中是否包含了問題的解，若已包含，則求解結(jié)束，并成功推出；否則執(zhí)行下一步；(3)檢查知識庫中是否有可用知識，若有，形成當(dāng)前可用知識集，執(zhí)行下一步；否則轉(zhuǎn)(5)。(4)按照某種沖突消解策略，從當(dāng)前可用知識集中選出一條規(guī)則進行推理，并將推出的新事實加入綜合數(shù)據(jù)庫種，然后轉(zhuǎn)(2)。(5)詢問用戶是否可以進一步補充新的事實，若可補充，則將補充的新事實加入綜合數(shù)據(jù)庫中，然后轉(zhuǎn)(3)；否則表示無解，失敗退出。至于如何根據(jù)綜合數(shù)據(jù)庫中的事實到知識庫中選取可用知識，當(dāng)知識庫中有多條知識可用時應(yīng)該先使用那一條知識等。這些問題涉及到了知識的匹配方法和沖突消解策略，以后將會分別討論。其流程圖如下：151、推理方向——正向推理從已知事實出發(fā)、正向使用推理規(guī)則，把初始證據(jù)放入DBDB中有解嗎？KB中有可用知識嗎？

形成可用知識集可用知識集空嗎？按照沖突消解策略從該知識集中選出一條知識進行推理

推出的是新事實嗎？

將新事實加入到DB把用戶補充的新事實加入到DB中

用戶可補充新事實嗎？

失敗退出

成功退出YNNYNNNYYY16把初始證據(jù)放入DBDB中有解嗎？KB中有可用知識嗎？1、推理方向——正向推理例請用正向推理完成以下問題的求解假設(shè)知識庫中包含有以下2條規(guī)則：r1：IFBTHENCr2：IFATHENB已知初始證據(jù)A，求證目標(biāo)C。解：本例的推理過程如下：推理開始前，綜合數(shù)據(jù)庫為空。推理開始后，先把A放入綜合數(shù)據(jù)庫，然后檢查綜合數(shù)據(jù)庫中是否含有該問題的解，回答為“N”。接著檢查知識庫中是否有可用知識，顯然r2可用，形成僅含r2的知識集。從該知識集中取出r2，推出新的實事B，將B加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標(biāo)C，回答為“N”。再檢查知識庫中是否有可用知識，此時由于B的加入使得r1為可用，形成僅含r1的知識集。從該知識集中取出r1，推出新的實事C，將C加入綜合數(shù)據(jù)庫，檢查綜合數(shù)據(jù)庫中是否含有目標(biāo)C，回答為“Y”。它說明綜合數(shù)據(jù)庫中已經(jīng)含有問題的解，推理成功結(jié)束，目標(biāo)C得證。171、推理方向——正向推理例請用正向推理完成以下問題的求正向推理的主要優(yōu)點比較直觀，允許用戶主動提供有用的事實信息，適合于診斷、設(shè)計、預(yù)測、監(jiān)控等領(lǐng)域的問題求解。正向推理的主要缺點推理無明確目標(biāo)，求解問題是可能會執(zhí)行許多與解無關(guān)的操作，導(dǎo)致推理效率較低。

1、推理方向——正向推理18正向推理的主要優(yōu)點1、推理方向——正向推理181、推理方向——逆向推理從某個假設(shè)目標(biāo)出發(fā)，逆向使用規(guī)則，亦稱為目標(biāo)驅(qū)動推理或逆向鏈推理。算法描述：(1)將要求證的目標(biāo)（稱為假設(shè)）構(gòu)成一個假設(shè)集；(2)從假設(shè)集中選出一個假設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫中，若在，則該假設(shè)成立，此時，若假設(shè)集為空，則成功退出，否則仍執(zhí)行(2)；若該假設(shè)不在數(shù)據(jù)庫中，則執(zhí)行下一步；(3)檢查該假設(shè)是否可由知識庫的某個知識導(dǎo)出，若不能由某個知識導(dǎo)出，則詢問用戶該假設(shè)是否為可由用戶證實的原始事實，若是，該假設(shè)成立，并將其放入綜合數(shù)據(jù)庫，再重新尋找新的假設(shè)，若不是，則轉(zhuǎn)(5)；若能由某個知識導(dǎo)出，則執(zhí)行下一步；(4)將知識庫中可以導(dǎo)出該假設(shè)的所有知識構(gòu)成一個可用知識集；(5)檢查可用知識集是否為空，若是，失敗退出；否則執(zhí)行下一步；(6)按沖突消解策略從可用知識集中取出一個知識，繼續(xù)；(7)將該知識的前提中的每個子條件都作為新的假設(shè)放入假設(shè)集，然后轉(zhuǎn)(2)。其流程圖如下：191、推理方向——逆向推理從某個假設(shè)目標(biāo)出發(fā)，逆向使用規(guī)則，初始化DB和假設(shè)集該假設(shè)是DB中的事實嗎？該假設(shè)能被KB中的知識導(dǎo)出嗎？從假設(shè)集中取出一個假設(shè)可用知識集空嗎？按照沖突消解策略從該知識集中選出一條知識將該知識前提中的每個子條件作為新的假設(shè)加入假設(shè)集該假設(shè)成立并放入DB還有新的假設(shè)嗎？失敗退出成功退出YNYYNNNNY將KB中所有能導(dǎo)出此假設(shè)的知識構(gòu)成一個可用知識集

詢問用戶有此事實嗎？該假設(shè)成立Y20初始化DB和假設(shè)集該假設(shè)是DB中的事實嗎？該假設(shè)能被KB中的1、推理方向——逆向推理例3.2用逆向推理完成以下問題的求解假設(shè)知識庫中包含有以下2條規(guī)則：r1：IFBTHENCr2：IFATHENB已知初始證據(jù)A，求證目標(biāo)C。推理開始前，綜合數(shù)據(jù)庫和假設(shè)集均為空。推理開始后，先將初始證據(jù)A和目標(biāo)C分別放入綜合數(shù)據(jù)庫和假設(shè)集，然后從假設(shè)集中取出一個假設(shè)C，查找C是否為綜合數(shù)據(jù)庫中的已知事實，回答為“N”。再檢查C是否能被知識庫中的知識所導(dǎo)出，發(fā)現(xiàn)C可由r1導(dǎo)出，于是r1被放入可用知識集。由于知識庫中只有r1可用，故可用知識集中僅含r1。接著從可用知識集中取出r1，將其前提條件B作為新的假設(shè)放入假設(shè)集。從假設(shè)集中取出B，檢查B是否為綜合數(shù)據(jù)庫中的實事，回答為“N”。再檢查B是否能被知識庫中的知識所導(dǎo)出，發(fā)現(xiàn)B可由r2導(dǎo)出，于是r2被放入可用知識集。由于知識庫中只有r2可用，故可用知識集中僅含r2。從可用知識集中取出r2，將其前提條件A作為新的假設(shè)放入假設(shè)集。然后從假設(shè)集中取出A，檢查A是否為綜合數(shù)據(jù)庫中的實事，回答為“Y”。他說明該假設(shè)成立，由于無新的假設(shè)，故推理過程成功結(jié)束，于是目標(biāo)C得證。211、推理方向——逆向推理例3.2用逆向推理完成以下問題1、推理方向——逆向推理逆向推理的主要優(yōu)點不必尋找和使用那些與假設(shè)目標(biāo)無關(guān)的信息和知識推理過程的目標(biāo)明確也有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。逆向推理的主要缺點當(dāng)用戶對解的情況認識不請時，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大，若選擇不好，可能需要多次提出假設(shè)，會影響系統(tǒng)效率。221、推理方向——逆向推理逆向推理的主要優(yōu)點221、推理方向——混合推理混合推理的概念把正向推理和逆向推理結(jié)合起來所進行的推理稱為混合推理。是一種解決較復(fù)雜問題的方法?；旌贤评淼膽?yīng)用環(huán)境已知事實不充分由正向推理得出的結(jié)論可信度不高希望得到更多的結(jié)論混合推理的方法1.先正向后逆向這種方法先進行正向推理，從已知事實出發(fā)推出部分結(jié)果，然后再用逆向推理對這些結(jié)果進行證實或提高它們的可信度。2.先逆向后正向這種方法先進行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，然后再用正向推理對這些中間假設(shè)進行證實。

3.雙向混合是指正向推理和逆向推理同時進行，使推理過程在中間的某一步結(jié)合起來。231、推理方向——混合推理混合推理的概念231、推理方向——雙向推理

正向推理與逆向推理同時進行，在推理過程中某一步驟上“碰頭”其基本思想是：一方面根據(jù)已知事實進行正向推理，但并不推到最終目標(biāo)；另一方面從某假設(shè)目標(biāo)出發(fā)進行逆向推理，但并不推至原始事實，而是讓它們在中途相遇，即由正向推理所得的中間結(jié)論恰好是逆向推理此時所要求的證據(jù)，這時推理就可結(jié)束，逆向推理的假設(shè)就是推理的最終結(jié)論。241、推理方向——雙向推理正向推理與逆向推理同時進行，在推理2.求解策略所謂推理的求解策略是指，推理是只求一個解，還是求所有解以及最優(yōu)解等。例如前述的正向推理只用于求一個解，只要略加修改就可用來求所有解。252.求解策略所謂推理的求解策略是指，推理是只求一個解，還是3.限制策略為了防止無窮的推理過程，以及由于推理過程太長從而增加時間及空間的復(fù)雜性，可在控制策略中指定推理的限制條件，以對推理的深度、寬度、時間、空間等進行限制。263.限制策略為了防止無窮的推理過程，以及由于推理過程太長在推理過程中，系統(tǒng)要不斷地用當(dāng)前已知的事實與知識庫中的知識進行匹配，此時可能發(fā)生有多個知識匹配成功，稱這種情況為發(fā)生了沖突。基本任務(wù)：解決沖突，選擇其中的一條規(guī)則來執(zhí)行?；舅枷耄簩χR進行排序按針對性排序按匹配度進行排序根據(jù)領(lǐng)域問題的特點進行排序4.沖突消解策略27在推理過程中，系統(tǒng)要不斷地用當(dāng)前已知的事實與知識庫中的知識進4.1.3模式匹配及其變量代換模式匹配是指兩個知識模式（如兩個謂詞公式、兩個框架片斷等）的比較，檢查這兩個知識模式是否完全一致或近似一致。如果兩者完全一致，或者雖不完全一致但其相似程度落在指定的限度內(nèi)，就稱它們是可匹配的，否則為不可匹配。按匹配時兩個知識模式的相似程度劃分，模式匹配可分為：確定性匹配不確定性匹配284.1.3模式匹配及其變量代換模式匹配是指兩個知識模式（4.1.3模式匹配及其變量代換確定性匹配是指兩個知識模式完全一致，或者經(jīng)過變量代換后變得完全一致。例如，設(shè)有如下兩個知識模式：P1：Father（李四，李小四）andMan(李小四)P2：Father(x,y)andMan(y)若用“李四”代換變量x，用“李小四”代換變量y，則P1與P2就變得完全一致。不確定性匹配是指兩個知識模式不完全一致，但從總體上看，它們的相似程度又落在規(guī)定的限度內(nèi)。294.1.3模式匹配及其變量代換確定性匹配是指兩個知識模式4.1.3模式匹配及其變量代換代換（置換）可簡單的理解為是在一個謂詞公式中用置換項去替換變量。定義3.1代換（置換）是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，t1,t2,…,tn是項；x1,x2,…,xn是互不相同的變元；ti/xi表示用ti替換xi。并且要求ti與xi不能相同，xi不能循環(huán)地出現(xiàn)在另一個ti中。304.1.3模式匹配及其變量代換代換（置換）可簡單的理解為4.1.3模式匹配及其變量代換例如，{a/x,c/y,f(b)/z}是一個置換。但{g(y)/x,f(x)/y}不是一個置換。原因是它在x與y之間出現(xiàn)了循環(huán)置換現(xiàn)象。即當(dāng)用g(y)置換x,用f(g(y))置換y時，既沒有消去x，也沒有消去y。若改為{g(a)/x,f(x)/y}即可，原因是用g(a)置換x，用f(g(a))置換y，則消去了x和y。通常，置換是用希臘字母θ、σ、α、λ等來表示的。314.1.3模式匹配及其變量代換例如，{a/x,c/y4.1.3模式匹配及其變量代換定義3.2設(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}中刪去以下兩種元素①當(dāng)tiλ=xi時，刪去tiλ/xi(i=1,2,…,n)；②當(dāng)yj∈{x1,x2,…,xn}時，刪去uj/yj(j=1,2,…,m)最后剩下的元素所構(gòu)成的集合。324.1.3模式匹配及其變量代換定義3.2設(shè)324.1.3模式匹配及其變量代換例設(shè)θ={f(y)/x,z/y}，λ={a/x,b/y,y/z}，求θ與λ的合成。解:先求出集合{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}={f(b)/x,y/y,a/x,b/y,y/z}其中，f(b)/x中的f(b)是置換λ作用于f(y)的結(jié)果；y/y中的y是置換λ作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件①，需要刪除；a/x和b/y滿足定義中的條件②，也需要刪除。最后得θ°λ={f(b)/x,y/z}334.1.3模式匹配及其變量代換例設(shè)θ={f(y)4.1.3模式匹配及其變量代換合一可理解為是尋找項對變量的置換，使兩個謂詞公式一致?？啥x為：定義3.3設(shè)有公式集F={F1,F2,…,Fn}，若存在一個置換θ，可使F1θ=F2θ=…=Fnθ，則稱θ是F的一個合一。稱F1,F2,…,Fn是可合一的。例如，設(shè)有公式集F={P(x,y,f(y)),P(a,g(x),z)}，則λ={a/x,g(a)/y,f(g(a))/z}是它的一個合一。一般來說，一個公式集的合一不是唯一的。344.1.3模式匹配及其變量代換合一可理解為是尋找項對變量4.1.3模式匹配及其變量代換定義3.4設(shè)σ是公式集F的一個合一，如果對F的任一個合一θ都存在一個置換λ，使得θ=σ°λ，則稱σ是一個最一般合一。（MostGeneralUnifier）一個公式集的最一般合一是唯一的。354.1.3模式匹配及其變量代換定義3.4設(shè)σ是公式集F4.1.3模式匹配及其變量代換差異集的概念。設(shè)有如下兩個謂詞公式：F1：P（x,y,z）F2：P(x,f(A),h(B)) 分別從F1與F2的第一個符號開始，逐個向右比較，此時發(fā)現(xiàn)F1與F2構(gòu)差異集：D1={y,f(A)}，D2={z,h(B)}364.1.3模式匹配及其變量代換差異集的概念。364.1.3模式匹配及其變量代換求最一般合一算法（1）初始化，令k=0,Fk=F,σk=Φ。其中，Φ是代換空集。（2）若Fk只含一個表達式，則算法停止，σk就是最一般合一；否則轉(zhuǎn)步驟（3）。（3）找出Fk的差異集Dk。（4）若Dk中存在變元xk和項tk，且xk不在tk中出現(xiàn)，則：σk+1=σо

{tk/xk}Fk+1=Fk

{tk/xk}k=k+1 轉(zhuǎn)步驟（2）；否則，算法終止，F(xiàn)的最一般合一不存在。374.1.3模式匹配及其變量代換求最一般合一算法374.1.3模式匹配及其變量代換例設(shè)有公式集F={P(A,x,f(g(y))),P(z,f(z),f(u))}求其最一般合一。

解：初始化，令k=0，σ0=ε，F(xiàn)0=F={P(A,x,f

(g(y))),P(z,f

(z),f(u))}384.1.3模式匹配及其變量代換例設(shè)有公式集384.1.3模式匹配及其變量代換Loop1：F0={P(A,x,f

(g(y))),P(z,f

(z),f(u))}含有2個表達式，故σ0不是最一般合一。 F0的差異集D0={A，z}，可有代換A/z，σ1=σ0°

{A/z}={A/z}

F1=F0{A/z}={P(A,x,f(g(y))),P(A,f(A),f(u))}

394.1.3模式匹配及其變量代換Loop1：F0={P4.1.3模式匹配及其變量代換Loop2：F1={P(A,x,

f(g(y))),P(A,f(A),

f(u))}含有2個表達式，故σ1不是最一般合一 F1的差異集D1={x，f(A)}，可有代換{f(A)/x}，

σ2=σ1

°{f(A)/x}={A/z}°{f(A)/x}={A/z,f(A)/x} F2=F1{f(A)/x}={P(A,f(A),f(g(y))), P(A,f(A),f(u))}404.1.3模式匹配及其變量代換Loop2：404.1.3模式匹配及其變量代換Loop3：F2={P(A,f(A),f(g(y))),P(A,f(A),f(u))}含有2個表達式，故σ2不是最一般合一 F2的差異集D2={g(y)，u}，可有代換 {g(y)/u}，

σ3=σ2

°{g(y)/u}={A/z,f(A)/x}°{g(y)/u}={A/z,f(A)/x,g(y)/u} F3=F2{g(y)/u}={P(A,f(A),f(g(y))),P(A,f(A),f(g(y)))}={P(A,f(A),f(g(y)))}414.1.3模式匹配及其變量代換Loop3：414.1.3模式匹配及其變量代換Loop4：F3中只含有一個表達式，故算法成功終止，σ3={A/z,f(A)/x,g(y)/u}，即為公式集F的最一般合一。424.1.3模式匹配及其變量代換Loop4：F3中只含有實驗二：

編程實現(xiàn)公式集的最一般合一求解可以輸入公式集，對不符合規(guī)范的公式集要報錯，符合規(guī)范的公式集進入求最一般合一步驟。如果有最一般合一，要求顯示每一步過程的差異集和代換，最后輸出解；如果沒有最一般合一，最后要作出判斷。43實驗二：

編程實現(xiàn)公式集的最一般合一求解可以輸入公式集，對不第4章經(jīng)典邏輯推理4.1推理的基本概念4.2自然演繹推理4.3歸結(jié)演繹推理4.4與/或形演繹推理44第4章經(jīng)典邏輯推理4.1推理的基本概念444.2自然演繹推理自然演繹推理從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。自然演繹推理最基本的推理規(guī)則是三段論推理，它包括：假言推理P,P→Q?Q拒取式﹁

Q,P→Q?﹁P假言三段論P→Q,Q→R?P→R例設(shè)已知如下事實：A,B,A→C,B∧C→D,D→Q求證：Q為真。

證明：因為A,A→C?C假言推理B,C?B∧C引入合取詞B∧C，B∧C→D?D假言推理D,D→Q?Q假言推理因此，Q為真454.2自然演繹推理自然演繹推理454.2自然演繹推理例設(shè)已知如下事實：(1)只要是需要編程序的課，王程都喜歡。(2)所有的程序設(shè)計語言課都是需要編程序的課。(3)C是一門程序設(shè)計語言課。求證：王程喜歡C這門課。證明：首先定義謂詞Prog(x)x是需要編程序的課。Like(x,y)x喜歡y。Lang(x)x是一門程序設(shè)計語言課把已知事實及待求解問題用謂詞公式表示如下：Prog(x)→Like(Wang,x)(?x)(Lang(x)→Prog(x))Lang(C)應(yīng)用推理規(guī)則進行推理：Lang(y)→Prog(y)全稱固化Lang(C)，Lang(y)→Prog(y)?Prog(C)假言推理{C/y}Prog(C),Prog(x)→Like(Wang,x)?Like(Wang,C)假言推理{C/x}因此，王程喜歡C這門課。464.2自然演繹推理例設(shè)已知如下事實：464.2自然演繹推理優(yōu)點：定理證明過程自然，易于理解，并且有豐富的推理規(guī)則可用。缺點：是容易產(chǎn)生知識爆炸，推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復(fù)雜問題的推理不利，甚至難以實現(xiàn)。

474.2自然演繹推理優(yōu)點：定理證明過程自然，易于第4章經(jīng)典邏輯推理4.1推理的基本概念4.2自然演繹推理4.3歸結(jié)演繹推理4.4與/或形演繹推理48第4章經(jīng)典邏輯推理4.1推理的基本概念484.3歸結(jié)演繹推理在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實質(zhì)，就是要對前提P和結(jié)論Q，證明P→Q永真。要證明P→Q永真，就是要證明P→Q在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。為此，人們進行了大量的探索，后來發(fā)現(xiàn)可以采用反證法的思想，把關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。即要證明P→Q永真，只要能夠證明P∧﹁Q是不可滿足的就可以了(原因是﹁(P→Q)?﹁(﹁P∨Q)?P∧﹁Q。這方面最有成效的工作就是魯賓遜歸結(jié)原理。它使定理證明的機械化成為現(xiàn)實。歸結(jié)演繹推理是一種基于魯賓遜（Robinson）歸結(jié)原理的機器推理技術(shù)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于1965年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏輯的“反證法”。494.3歸結(jié)演繹推理在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化4.3歸結(jié)演繹推理4.3.1謂詞公式化為子句集4.3.2歸結(jié)原理4.3.3歸結(jié)反演4.3.4基于歸結(jié)反演的問題求解4.3.5歸結(jié)反演策略504.3歸結(jié)演繹推理4.3.1謂詞公式化為子句集504.3.1謂詞公式化為子句集歸結(jié)原理是在子句集的基礎(chǔ)上討論問題的。因此，討論歸結(jié)演繹推理之前，需要先討論子句集的有關(guān)概念。子句和子句集定義3.5原子謂詞公式及其否定統(tǒng)稱為文字。例如，P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。定義3.6任何文字的析取式稱為子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。

定義3.7不含任何文字的子句稱為空子句。由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的。空子句可表示為NIL定義3.8由子句或空子句所構(gòu)成的集合稱為子句集。514.3.1謂詞公式化為子句集歸結(jié)原理是在子句集的基礎(chǔ)上討謂詞公式化成子句集的步驟如下：(1)消去連接詞“→”和“?”反復(fù)使用如下等價公式：P→Q?﹁P∨QP?Q?(P∧Q)∨(﹁P∧﹁Q)即可消去謂詞公式中的連接詞“→”和“?”。例如公式

(?x)((?y)P(x,y)→﹁(?y)(Q(x,y)→R(x,y)))經(jīng)等價變化后為

(?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))4.3.1謂詞公式化為子句集52謂詞公式化成子句集的步驟如下：4.3.1謂詞公式化為子句(2)減少否定符號的轄域反復(fù)使用雙重否定率﹁(﹁P)?P摩根定律﹁(P∧Q)?﹁P∨﹁Q﹁(P∨Q)?﹁P∧﹁Q量詞轉(zhuǎn)換率﹁(?x)P(x)?(?x)﹁P(x)﹁(?x)P(x)?(?x)￢P(x)將每個否定符號“﹁”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。上式經(jīng)等價變換后為

(?x)((?y)﹁P(x，y)∨(?y)(Q(x，y)∧﹁R(x，y)))4.3.1謂詞公式化為子句集53(2)減少否定符號的轄域4.3.1謂詞公式化為子句集5(3)對變元標(biāo)準(zhǔn)化在一個量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。例如，上式經(jīng)變換后為

(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))(4)化為前束范式化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。由于第(3)步已對變元進行了標(biāo)準(zhǔn)化，每個量詞都有自己的變元，這就消除了任何由變元引起沖突的可能，因此這種移動是可行的。例如，上式化為前束范式后為

(?x)(?y)(?z)(﹁P(x，y)∨(Q(x，z)∧﹁R(x，z)))4.3.1謂詞公式化為子句集54(3)對變元標(biāo)準(zhǔn)化4.3.1謂詞公式化為子句集54(5)消去存在量詞消去存在量詞時，需要區(qū)分以下兩種情況：若存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞），只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。若存在量詞位于一個或多個全稱量詞的轄域內(nèi)例如(?x1)…(?xn)(?y)P(x1，x2,…,xn,y)則需要用Skolem函數(shù)f(x1，x2,…,xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。例如，上步所得公式中存在量詞(?y)和(?z)都位于(?x)的轄域內(nèi)，因此都需要用Skolem函數(shù)來替換。設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為

(?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))4.3.1謂詞公式化為子句集55(5)消去存在量詞4.3.1謂詞公式化為子句集55(6)化為Skolem標(biāo)準(zhǔn)形Skolem標(biāo)準(zhǔn)形的一般形式為(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標(biāo)準(zhǔn)形的母式，它由子句的合取所構(gòu)成。把謂詞公式化為Skolem標(biāo)準(zhǔn)形需要使用以下等價關(guān)系P∨(Q∧R)?(P∨Q)∧(P∨R)例如，前面的公式化為Skolem標(biāo)準(zhǔn)形后為

(?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))(7)消去全稱量詞由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變元是被全稱量詞量化的。例如，上式消去全稱量詞后為(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))4.3.1謂詞公式化為子句集56(6)化為Skolem標(biāo)準(zhǔn)形4.3.1謂詞公式化為子句(8)消去合取詞在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。

例如，上式的子句集中包含以下兩個子句

﹁P(x,f(x))∨Q(x,g(x))﹁P(x,f(x))∨﹁R(x,g(x))(9)更換變量名稱對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相同的變量名。由于每一個子句都對應(yīng)著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實際上不存在任何關(guān)系。這樣，更換變量名是不會影響公式的真值的。例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集

﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))4.3.1謂詞公式化為子句集57(8)消去合取詞4.3.1謂詞公式化為子句集57在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不唯一的。這樣，當(dāng)原謂詞公式為非永假時，它與其標(biāo)準(zhǔn)子句集并不等價。但當(dāng)原謂詞公式為永假（或不可滿足）時，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。這個結(jié)論很重要，是歸結(jié)原理的主要依據(jù)，可用定理的形式來描述。定理3.1設(shè)有謂詞公式F，其標(biāo)準(zhǔn)子句集為S，則F為不可滿足的充要條件是S為不可滿足的。由此定理可知，為要證明一個謂詞公式是不可滿足的，只要證明相應(yīng)的子句集是不可滿足的就可以了。4.3.1謂詞公式化為子句集58在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)4.3.1謂詞公式化為子句集例請將下述謂詞公式化為子句集：(?x)((?y)P(x,y)→﹁(?y)(Q(x,y)→R(x,y)))解

(?x)((?y)P(x,y)→﹁(?y)(Q(x,y)→R(x,y)))(?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))

(?x)((?y)﹁P(x，y)∨(?y)(Q(x，y)∧﹁R(x，y)))

(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))

(?x)(?y)(?z)(﹁P(x，y)∨(Q(x，z)∧﹁R(x，z)))(?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))594.3.1謂詞公式化為子句集例請將下述謂詞公式化為子4.3.1謂詞公式化為子句集

(?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))

(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))

(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))消去合取詞后，上式就變?yōu)橄率鲎泳浼?/p>

﹁P(x,f(x))∨Q(x,g(x)) ﹁P(y,f(y))∨R(y,g(y))604.3.1謂詞公式化為子句集 (?x)((﹁P(x,f4.3.2歸結(jié)原理魯濱遜歸結(jié)原理基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴充的子句集S‘。然后設(shè)法檢驗子句集S’是否含有空子句，若含有空子句，則表明S‘是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。魯濱遜（Robinson）歸結(jié)原理包括命題邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理614.3.2歸結(jié)原理魯濱遜歸結(jié)原理基本思想61一、命題邏輯的歸結(jié)原理

歸結(jié)推理的核心是求兩個子句的歸結(jié)式(1)歸結(jié)式的定義及性質(zhì)定義3.9若P是原子謂詞公式，則稱P與﹁P為互補文字。定義3.10設(shè)C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個新的子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。4.3.2歸結(jié)原理62一、命題邏輯的歸結(jié)原理4.3.2歸結(jié)原理62例3.5設(shè)C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=P，L2=﹁P，通過歸結(jié)可以得到C12=Q∨R∨S例3.6設(shè)C1=﹁Q，C2=Q，求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=﹁Q，L2=Q，通過歸結(jié)可以得到C12=NIL4.3.2歸結(jié)原理63例3.5設(shè)C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的例3.7設(shè)C1=﹁P∨Q

，C2=﹁Q，C3=P，求C1、C2、C3的歸結(jié)式C123。

解：若先對C1、C2歸結(jié)，可得到C12=﹁P然后再對C12和C3歸結(jié)，得到C123=NIL如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即其歸結(jié)過程是不唯一的。其歸結(jié)過程可用右圖來表示，該樹稱為歸結(jié)樹。﹁P∨Q﹁Q﹁PPNIL﹁P∨QPQ﹁QNIL4.3.2歸結(jié)原理64例3.7設(shè)C1=﹁P∨Q，﹁P∨Q﹁定理3.2歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。

證明：（按定義）設(shè)C1=L∨C1’，C2=﹁L∨C2’關(guān)于解釋I為真，則只需證明C12=C1’∨C2’關(guān)于解釋I也為真。對于解釋I，L和﹁L中必有一個為假。

若L為假，則必有C1'為真，不然就會使C1為假，這將與前提假設(shè)C1為真矛盾，因此只能有C1'為真。同理，若﹁L為假，則必有C2'為真。因此，必有C12=C1'∨C2'關(guān)于解釋I也為真。即C12是C1和C2的邏輯結(jié)論。4.3.2歸結(jié)原理65定理3.2歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。上述定理是歸結(jié)原理中的一個重要定理，由它可得到以下兩個推論：推論1：設(shè)C1和C2是子句集S中的兩個子句，C12是C1和C2的歸結(jié)式，若用C12代替C1和C2后得到新的子句集S1，則由S1的不可滿足性可以推出原子句集S的不可滿足性。即：

S1的不可滿足性?S的不可滿足性推論2：設(shè)C1和C2是子句集S中的兩個子句，C12是C1和C2的歸結(jié)式，若把C12加入S中得到新的子句集S2，則S與S2的不可滿足性是等價的。即：

S2的不可滿足性?S的不可滿足性4.3.2歸結(jié)原理66上述定理是歸結(jié)原理中的一個重要定理，由它可得到以下兩個推論：上述兩個推論說明，為證明子句集S的不可滿足性，只要對其中可進行歸結(jié)的子句進行歸結(jié)，并把歸結(jié)式加入到子句集S中，或者用歸結(jié)式代替他的親本子句，然后對新的子句集證明其不可滿足性就可以了。如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集S是不可滿足的結(jié)論。在命題邏輯中，對不可滿足的子句集S，其歸結(jié)原理是完備的。這種不可滿足性可用如下定理描述：定理3.3

子句集S是不可滿足的，當(dāng)且僅當(dāng)存在一個從S到空子句的歸結(jié)過程。4.3.2歸結(jié)原理67上述兩個推論說明，為證明子句集S的不可滿足性，只要對其中可進二、謂詞邏輯的歸結(jié)原理

在謂詞邏輯中，由于子句集中的謂詞一般都含有變元，因此不能象命題邏輯那樣直接消去互補文字。而需要先用一個最一般合一對變元進行代換，然后才能進行歸結(jié)?？梢?，謂詞邏輯的歸結(jié)要比命題邏輯的歸結(jié)麻煩一些。謂詞邏輯的歸結(jié)原理謂詞邏輯中的歸結(jié)式可用如下定義來描述：

定義3.11設(shè)C1和C2是兩個沒有公共變元的子句，L1和L2分別是C1和C2中的文字。如果L1和L2存在最一般合一σ，則稱C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})為C1和C2的二元歸結(jié)式，而L1和L2為歸結(jié)式上的文字。4.3.2歸結(jié)原理68二、謂詞邏輯的歸結(jié)原理4.3.2歸結(jié)原理68

例3.8設(shè)C1=P(a)∨R(x)，C2=﹁P(y)∨Q(b)，求C12

解：取L1=P(a),L2=﹁P(y)，則L1和L2的最一般合一是σ={a/y}。根據(jù)定義3.20,可得C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})=({P(a),R(x)}-{P(a)})∪({﹁P(a),Q(b)}-{﹁P(a)})=({R(x)})∪({Q(b)})={R(x),Q(b)}=R(x)∨Q(b)4.3.2歸結(jié)原理69例3.8設(shè)C1=P(a)∨R(x)，C2=﹁P(y例3.9設(shè)C1=P(x)∨Q(a)，C2=﹁P(b)∨R(x)，求C12解：由于C1和C2有相同的變元x，不符合定義3.20的要求。為了進行歸結(jié)，需要修改C2中變元的名字，令C2=﹁P(b)∨R(y)。此時L1=P(x),L2=﹁P(b)，L1和L2的最一般合一是σ={b/x}。則有C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})=({P(b),Q(a)}-{P(b)})∪({﹁P(b),R(y)}-{﹁P(b)})=({Q(a)})∪({R(y)})={Q(a),R(y)}=Q(a)∨R(y)4.3.2歸結(jié)原理70例3.9設(shè)C1=P(x)∨Q(a)，C2=﹁P(b)∨R(

對以上討論做以下兩點說明:

(1)這里之所以使用集合符號和集合的運算，目的是為了說明問題的方便。即先將子句Ciσ和Liσ寫成集合的形式，在集合表示下做減法和并集運算，然后再寫成子句集的形式。

(2)定義中還要求C1和C2無公共變元，這也是合理的。例如C1=P(x)，C2=﹁P(f(x))，而S={C1,C2}是不可滿足的。但由于C1和C2的變元相同，就無法合一了。沒有歸結(jié)式，就不能用歸結(jié)法證明S的不可滿足性，這就限制了歸結(jié)法的使用范圍。如果對C1或C2的變元進行換名，便可通過合一，對C1和C2進行歸結(jié)。如上例，若先對C2進行換名，即C2=﹁P(f(y))，則可對C1和C2進行歸結(jié)，得到一個空子句，從而證明了S是不可滿足的。事實上，在由公式集化為子句集的過程中，最后一步就是做換名處理。因此，定義中假設(shè)C1和C2沒有相同變元是可以的。4.3.2歸結(jié)原理71對以上討論做以下兩點說明:4.3.2歸結(jié)原理4.3.3歸結(jié)反演一、命題邏輯的歸結(jié)反演

歸結(jié)原理：假設(shè)F為已知前提，G為欲證明的結(jié)論，歸結(jié)原理把證明G為F的邏輯結(jié)論轉(zhuǎn)化為證明F∧﹁G為不可滿足。再根據(jù)定理3.1，在不可滿足的意義上，公式集F∧﹁G與其子句集是等價的，即把公式集上的不可滿足轉(zhuǎn)化為子句集上的不可滿足。應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。

在命題邏輯中，已知F，證明G為真的歸結(jié)反演過程如下：①否定目標(biāo)公式G，得﹁G;②把﹁G并入到公式集F中，得到{F，﹁G}；③把{F，﹁G}化為子句集S。④應(yīng)用歸結(jié)原理對子句集S中的子句進行歸結(jié)，并把每次得到的歸結(jié)式并入S中。如此反復(fù)進行，若出現(xiàn)空子句，則停止歸結(jié)，此時就證明了G為真。724.3.3歸結(jié)反演一、命題邏輯的歸結(jié)反演72例設(shè)已知的公式集為{P,(P∧Q)→R,(S∨T)→Q,T}，求證結(jié)論R。

解：假設(shè)結(jié)論R為假,將﹁R加入公式集，并化為子句集S={P,﹁P∨﹁Q∨R,﹁S∨Q,﹁T∨Q,T,﹁R}其歸結(jié)過程如右圖的歸結(jié)演繹樹所示。該樹根為空子句。其含義為：先假設(shè)子句集S中的所有子句均為真，即原公式集為真,﹁R也為真；然后利用歸結(jié)原理，對子句集進行歸結(jié)，并把所得的歸結(jié)式并入子句集中；重復(fù)這一過程，最后歸結(jié)出了空子句。根據(jù)歸結(jié)原理的完備性，可知子句集S是不可滿足的，即開始時假設(shè)﹁R為真是錯誤的，這就證明了R為真。

﹁P∨﹁Q∨R﹁R﹁P∨﹁QP﹁Q﹁T∨Q﹁TTNIL4.3.3歸結(jié)反演73例設(shè)已知的公式集為﹁P∨﹁Q∨R﹁R﹁P∨﹁QP﹁Q4.3.3歸結(jié)反演二、謂詞邏輯的歸結(jié)反演謂詞邏輯的歸結(jié)反演過程與命題邏輯的歸結(jié)反演過程相比，其步驟基本相同，但每步的處理對象不同。例如，在步驟(3)化簡子句集時，謂詞邏輯需要把由謂詞構(gòu)成的公式集化為子句集；在步驟(4)按歸結(jié)原理進行歸結(jié)時，謂詞邏輯的歸結(jié)原理需要考慮兩個親本子句的最一般合一。744.3.3歸結(jié)反演二、謂詞邏輯的歸結(jié)反演744.3.3歸結(jié)反演例

F:(?x)((?y)(A(x,y)∧B(y))→(?y)(C(y)∧D(x,y)))G:﹁(?x)C(x)→(?x)(?y)(A(x,y)→﹁B(y))證明:G是F的邏輯結(jié)論。先把G否定，并放入F中，得到的{F,﹁G}為{(?x)((?y)(A(x,y)∧B(y))→(?y)(C(y)∧D(x,y))),﹁(﹁(?x)C(x)→(?x)(?y)(A(x,y)→﹁B(y)))}754.3.3歸結(jié)反演例75再把{F,﹁G}化成子句集，得到(1)﹁A(x,y)∨﹁B(y)∨C(f(x))(2)﹁A(u,v)∨﹁B(v)∨D(u,f(u))(3)﹁C(z)(4)A(m,n)(5)B(k)其中，(1)、(2)是由F化出的兩個子句，(3)、(4)、(5)是由﹁G化出的3個子句。最后應(yīng)用謂詞邏輯的歸結(jié)原理對上述子句集進行歸結(jié)，其過程為(6)﹁A(x,y)∨﹁B(y)由(1)和(3)歸結(jié)，取σ={f(x)/z}(7)﹁B(n)由(4)和(6)歸結(jié)，取σ={m/x,n/y}(8)NIL由(5)和(7)歸結(jié)，取σ={n/k}因此，G是F的邏輯結(jié)論。4.3.3歸結(jié)反演76再把{F,﹁G}化成子句集，得到4.3.3歸結(jié)反4.3.3歸結(jié)反演上述歸結(jié)過程可用如下歸結(jié)樹來表示﹁A(x,y)∨﹁B(y)∨C(f(x))﹁C(z)﹁A(x,y)∨﹁B(y)A(m,n)﹁B(n)B(k)NIL{f(x)/z}{m/x,n/y}{n/k}774.3.3歸結(jié)反演上述歸結(jié)過程可用如下歸結(jié)樹來表示﹁A(為了進一步加深對謂詞邏輯歸結(jié)的理解，下面再給出一個經(jīng)典的歸結(jié)問題例“快樂學(xué)生”問題假設(shè)：任何通過計算機考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運的人都可以通過所有考試，張不肯學(xué)習(xí)但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。解：先定義謂詞：Pass(x,y)x可以通過y考試Win(x,prize)x能獲得獎勵Study(x)x肯學(xué)習(xí)Happy(x)x是快樂的Lucky(x)x是幸運的4.3.3歸結(jié)反演78為了進一步加深對謂詞邏輯歸結(jié)的理解，下面再給出一個經(jīng)典的歸結(jié)4.3.3歸結(jié)反演再將問題用謂詞表示如下：“任何通過計算機考試并獎的人都是快樂的”(?x)(Pass(x,computer)∧Win(x,prize)→Happy(x))“任何肯學(xué)習(xí)或幸運的人都可以通過所有考試”(?x)(?y)(Study(x)∨Lucky(x)→Pass(x,y))“張不肯學(xué)習(xí)但他是幸運的”﹁Study(zhang)∧Lucky(zhang)“任何幸運的人都能獲獎”(?x)(Lucky(x)→Win(x,prize))結(jié)論“張是快樂的”的否定﹁Happy(zhang)794.3.3歸結(jié)反演再將問題用謂詞表示如下：794.3.3歸結(jié)反演將上述謂詞公式轉(zhuǎn)化為子句集如下：(1)﹁Pass(x,computer)∨﹁Win(x,prize)∨Happy(x)(2)﹁Study(y)∨Pass(y,z)(3)﹁Lucky(u)∨Pass(u,v)(4)﹁Study(zhang)(5)Lucky(zhang)(6)﹁Lucky(w)∨Win(w,prize)(7)﹁Happy(zhang)(結(jié)論的否定)804.3.3歸結(jié)反演將上述謂詞公式轉(zhuǎn)化為子句集如下：804.3.3歸結(jié)反演

﹁Pass(x,computer)∨﹁Win(x,prize)∨Happy(x)﹁Lucky(w)∨Win(w,prize)﹁Pass(w,Computer)∨Happy(w)∨﹁Lucky(w)﹁Happy(zhang)Lucky(zhang)﹁Pass(zhang,Computer)∨﹁Lucky(zhang)﹁Pass(zhang,Computer)﹁Lucky(u)∨Pass(u,v)﹁Lucky(zhang)Lucky(zhang)NIL{w/x}{zhang/w}{zhang/u,computer/v}814.3.3歸結(jié)反演﹁Pass(x,computer)∨4.3.3歸結(jié)反演例“激動人心的生活”問題假設(shè)：所有不貧窮并且聰明的人都是快樂的，那些看書的人是聰明的。李明能看書且不貧窮，快樂的人過著激動人心的生活。求證：李明過著激動人心的生活。解：先定義謂詞：Poor(x)x是貧窮的Smart(x)x是聰明的Happy(x)x是快樂的Read(x)x能看書Exciting(x)x過著激動人心的生活824.3.3歸結(jié)反演例“激動人心的生活”問題824.3.3歸結(jié)反演再將問題用謂詞表示如下：“所有不貧窮并且聰明的人都是快樂的”(?x)((﹁Poor(x)∧Smart(x))→Happy(x))“那些看書的人是聰明的”(?y)(Read(y)→Smart(y))“李明能看書且不貧窮”Read(Liming)∧﹁Poor(Liming)“快樂的人過著激動人心的生活”(?z)(Happy(z)→Exciting(z))目標(biāo)“李明過著激動人心的生活”的否定﹁Exciting(Liming)834.3.3歸結(jié)反演再將問題用謂詞表示如下：834.3.3歸結(jié)反演將上述謂詞公式轉(zhuǎn)化為子句集如下：(1)Poor(x)∨﹁Smart(x)∨Happy(x)(2)﹁Read(y)∨Smart(y)(3)Read(Liming)(4)﹁Poor(Liming)(5)﹁Happy(z)∨Exciting(z)(6)﹁Exciting(Liming)(結(jié)論的否定)844.3.3歸結(jié)反演將上述謂詞公式轉(zhuǎn)化為子句集如下：844.3.3歸結(jié)