第四章經(jīng)典邏輯推理

1、 經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯的邏輯規(guī)則進(jìn)行的一種推理，又稱為機(jī)械-自動(dòng)定理證明，主要的方法有：主要的推理方法有：自然演繹推理歸結(jié)演繹推理與/或性推理嗆口小辣椒博客 第四章： 經(jīng)典邏輯推理其值只有真假是一種精確推理4.1 基本概念基本概念1 什么是推理什么是推理/理的基本概念理的基本概念 (1) 推理：按某種策略由已知判斷推出另一種判斷的思維過程 (2) 判斷分為已知判斷由已知判斷推出新判斷，推理的結(jié)論 (3) 在人工智能系統(tǒng)中，推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。4.1.2 推理的方法及其分類 1. 按照推理的邏輯基礎(chǔ)分類 可分為演繹推理演繹推理、歸納推理歸納推理和默認(rèn)推理默認(rèn)推理。（1）演繹推理

2、 演繹推理是從已知的一般性知識(shí)出發(fā)，推理出適合于某種個(gè)別情況的結(jié)論的過程。它是一種由一般到個(gè)別的推理方法。4.1 推理概述推理概述 1. 大前提 ：已知的一般性的知識(shí)或假設(shè)2. 小前提：具體情況或個(gè)別事實(shí)的判斷3. 結(jié)論：由大前提推出適合于小前提所示情況的判斷例如：所有的足球運(yùn)動(dòng)員的身體都是強(qiáng)壯的高波是一名足球運(yùn)動(dòng)員所以高波的身體是強(qiáng)壯的在任何情況下，由演繹推理推到出的結(jié)論都是蘊(yùn)含在大前提的一般性知識(shí)之中的。 3.1 推理概述推理概述 （2）歸納推理 歸納推理是從足夠的事例中歸納出一般性結(jié)論的推理過程，是一種由個(gè)別到一般的推理方法。其基本思想是：首先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的

3、正確性加以證明確認(rèn)，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。 歸納推理又可分為： 從特殊事例考察范圍看：完全歸納推理、不完全歸納推理； 從使用的方法看：枚舉歸納推理、類比歸納推理。歸納推理可以分為：1. 完全歸納推理：是指在進(jìn)行歸納時(shí)考察了事物的全部對(duì)象，并根據(jù)這些對(duì)象是否具有某些屬性，從而推出這個(gè)事物是否具有這個(gè)屬性。2. 不完全歸納推理：只考察了相應(yīng)事物的部分對(duì)象就得到了結(jié)論。 例如： 對(duì)某廠的每一個(gè)產(chǎn)品都進(jìn)行嚴(yán)格檢查，且都嚴(yán)格，則推到出改產(chǎn)生產(chǎn)的產(chǎn)品時(shí)合格的必然結(jié)論。 我們也可以抽查，隨機(jī)地抽查了部分產(chǎn)品，只要他們都合格，我們就說該廠的產(chǎn)品是合格的。（3）默認(rèn)推理 默認(rèn)推理又稱缺省推理，是

4、在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。也就是說，在進(jìn)行推理時(shí)，如果對(duì)某些證據(jù)不能證明其不成立的情況下，先假設(shè)它是成立的，并將它作為推理的依據(jù)進(jìn)行推理，但在推理過程中，當(dāng)由于新知識(shí)的加入或由于所推出的中間結(jié)論與已有知識(shí)發(fā)生矛盾時(shí)，就說明前面的有關(guān)證據(jù)的假設(shè)是不正確，這時(shí)就要撤消原來的假設(shè)以及由此假設(shè)所推出的所有結(jié)論，重新按新情況進(jìn)行推理4.1 推理概述推理概述 定理一：定理一： D 是 AB 中點(diǎn) DE / AC 求證： E 是 AC 中點(diǎn)定理二：定理二： D 是 AB 中點(diǎn) E 是 AC 中點(diǎn) 求證： DE / ACA, B, C 不共線A, B, C 可以共線無法證明A，B，

5、C共線 ，則默認(rèn)A，B，C是不共線的2. 按所用知識(shí)的確定性分類 按推理時(shí)所用知識(shí)的確定性來劃分，推理可分為確定性推理、不確定性推理。 1. 推理時(shí)所用的知識(shí)都是精確的，推出的結(jié)論也是正確的，其真值或?yàn)檎婊驗(yàn)榧佟?2. 不確定性推理：推理時(shí)所用的知識(shí)不都是精確的，推出的結(jié)論也不完全是肯定的，其真值位于真與假之間，命題的外延模糊不清。4.1 推理概述推理概述 3. 按推理過程的單調(diào)性 按照推理過程中所推出的結(jié)論是否單調(diào)地增加，或者說按照推理過程所得到的結(jié)論是否越來越接近最終目標(biāo)來分類，推理可分為單調(diào)推理與非單調(diào)推理。 1. 單調(diào)推理：在推理的過程中隨著推理的向前推進(jìn)以及新知識(shí)的加入，推出的結(jié)論呈

6、單調(diào)增加的趨勢(shì)，并且越來越接近最終目標(biāo)，在推理的過程中不會(huì)出現(xiàn)反復(fù)情況。2. 非單調(diào)推理：在推理過程中由于新知識(shí)的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而否定了它，使得推理退回到前面的某一步，重新開始。 多是在知識(shí)不完全的情況下發(fā)生。 4. 啟發(fā)式推理、非啟發(fā)式推理 啟發(fā)性知識(shí)是指與問題有關(guān)且能加快推理進(jìn)程，求解問題最優(yōu)解的知識(shí)。5 5. 基于知識(shí)的推理，統(tǒng)計(jì)推理，直覺推理 1. 基于知識(shí)的推理：根據(jù)掌握的事實(shí)，通過運(yùn)用知識(shí)進(jìn)行推理，例如：醫(yī)生診斷疾病 2. 統(tǒng)計(jì)推理：根據(jù)對(duì)某事物的數(shù)據(jù)統(tǒng)計(jì)進(jìn)行推理。例如:對(duì)農(nóng)作物產(chǎn)量的統(tǒng)計(jì)，決定是否增產(chǎn)。 3. 直覺推理：根據(jù)常識(shí)進(jìn)行的推理。 例如：走路時(shí)重物落

7、下，躲閃。4.1.3 推理的控制策略 推理過程不僅依賴于所用的推理方法，同時(shí)也依賴于推理的控制策略?？刂撇呗园ㄍ评矸较?、搜索策略、沖突消解策略、求解策略、限制策略；而推理方法則是指在推理控制策略確定之后，在進(jìn)行具體推理時(shí)所要采取的匹配方法或不確定性傳遞算法等方法。 推理方向用來確定推理的驅(qū)動(dòng)方式，即是數(shù)據(jù)（證據(jù)）驅(qū)動(dòng)或是目標(biāo)驅(qū)動(dòng)。所謂數(shù)據(jù)驅(qū)動(dòng)即指推理過程從初始證據(jù)開始直到目標(biāo)結(jié)束，而目標(biāo)驅(qū)動(dòng)則是指推理過程從目標(biāo)開始進(jìn)行反向推理，直到出現(xiàn)與初始證據(jù)相吻合的結(jié)果。 按照對(duì)推理方向的控制，推理可分為正向推理、反向推理、混合推理及雙向推理四種情況。4.1 推理概述推理概述 推理的驅(qū)動(dòng)方式(1) 正向

8、推理：又稱數(shù)據(jù)驅(qū)動(dòng)推理，向前鏈推理，模式制導(dǎo)推理，前件推理基本思想：1. 從用戶提供的初始已知事實(shí)出發(fā)，在知識(shí)庫KB中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用的知識(shí)集KS2. 按某種沖突消解策略從KS中選出一條知識(shí)進(jìn)行推理，并將推出的新的事實(shí)加入到數(shù)據(jù)庫KB中，作為下一步推理的已知事實(shí)。正向推理逆向推理混合推理雙向推理要求數(shù)據(jù)庫知識(shí)庫狀態(tài)庫推理機(jī)3. 再在知識(shí)庫中選取可適用知識(shí)進(jìn)行推理，直到求解所要求的解惑知識(shí)庫中再無可用的知識(shí)為止。推理過程算法1. 將用戶提供的初始已知事實(shí)進(jìn)入數(shù)據(jù)庫DB中2. 檢查DB中是否已經(jīng)包含了該問題的解，若有，則求解結(jié)束，成功推出，否則執(zhí)行下一步。 3. 根據(jù)DB中的已知事

9、實(shí)，掃描知識(shí)庫KB，檢查KB中是否有可適用的知識(shí)，若有則轉(zhuǎn)到4， 否則到64. 把KB中所有的適用知識(shí)都選出來，構(gòu)成可適用的知識(shí)集KS5. 若KS不為空，則按某種沖突消解策略從中選出一條知識(shí)進(jìn)行推理，并將推出的新知識(shí)加入DB中，轉(zhuǎn)2；若KS空，轉(zhuǎn)6.6. 詢問用戶是否可進(jìn)一步補(bǔ)充新事實(shí)，若可以補(bǔ)充，則補(bǔ)充新的事實(shí)加入DB，然后轉(zhuǎn)3， 否則表示求解不出，失敗。 (2) 逆向推理： 又稱目標(biāo)驅(qū)動(dòng)推理，逆向鏈推理，目標(biāo)制導(dǎo)推理以及后件推理。1. 選定一個(gè)假設(shè)目標(biāo)2. 尋找支持該假設(shè)的證據(jù)，若所需要的證據(jù)都能找到，則說明原假設(shè)是成立的，若無論如何都找不到所需要的證據(jù)，則說明原假設(shè)不成立。 算法描述1.

10、 提出要求證的目標(biāo)（假設(shè)）2. 檢查該目標(biāo)是否已在數(shù)據(jù)庫中，若在，該目標(biāo)成立，成功推出推理。否則轉(zhuǎn) 33. 判斷目標(biāo)是否有證據(jù)，若有，則咨詢用戶，否則轉(zhuǎn) 44. 在知識(shí)庫中尋找有可能導(dǎo)出該目標(biāo)的知識(shí)，形成適用知識(shí)集合 KS，然后轉(zhuǎn)下一步 55從 KS 中選出一條知識(shí)，并將知識(shí)適用的條件作為新的假設(shè)目標(biāo)， 轉(zhuǎn) 2. 逆向推理的優(yōu)點(diǎn)：不必使用與目標(biāo)無關(guān)的知識(shí)，目的性強(qiáng)，便于向用戶提供解釋。逆向推理的缺點(diǎn)：初始目標(biāo)的選擇有盲目性，若不符合要求，就需要多次提出假設(shè)，影響到系統(tǒng)效率。 (3) 混合推理：既具有正向推理又具有逆向推理。什么時(shí)候用混合推理？1. 已知的事實(shí)不充分2. 由正向推理推出的結(jié)論可信

11、度不3. 希望得到更多的知識(shí)開始正向推理需要逆向推理？以正向推理所得到的結(jié)果作為假設(shè)進(jìn)行逆向推理還需要逆正？輸出結(jié)果開始逆向推理需要正向推理？進(jìn)行正向推理還需要逆向？輸出結(jié)果NYYYNY(4) 雙向推理：正向推理與逆向推理同時(shí)進(jìn)行基本思想：一方面根據(jù)已知事實(shí)進(jìn)行正向推理，單并不推到最終目標(biāo)；另一方面從假設(shè)目標(biāo)出發(fā)進(jìn)行逆向推理，單并不推到原始事實(shí)，而是讓他們中途相遇，即由正向推理所得到的中間結(jié)論恰好是逆向推理所要求的證據(jù)，這時(shí)推理可結(jié)束。 困難在于“碰頭”的判斷。 (5) 求解策略：是指推理只有一個(gè)解，還是求所有解以及最優(yōu)解等。 (6) 限制策略：為了防止無窮推理過程，以及由于推理過程太長(zhǎng)增加時(shí)

12、間以及空間的復(fù)雜性，可在控制策略中制定推理的限制條件， 以對(duì)推理的深度，寬度，時(shí)間，空間進(jìn)行限制。4. 模式匹配(1) 模式匹配：指對(duì)兩個(gè)指示模式（兩個(gè)謂詞公式，兩個(gè)框架片段，兩個(gè)語義網(wǎng)絡(luò)片段）的比較與耦合，如果兩者完全一致，或者雖不完全一致，但相似的程度在指定的限度內(nèi)，稱他們是可匹配的，否則稱不可匹配的。 (2) 確定性匹配：是指兩個(gè)指示模式完全一致，或經(jīng)過變量代換以后變得完全一致。 (3) 不確定性匹配：指兩個(gè)知識(shí)模式不完全一致，但從總體上看，它們的相似程度又落在規(guī)定的限度內(nèi)。 無論是確定性匹配還是不確定性匹配，在進(jìn)行匹配時(shí)都需啊要進(jìn)行變量代換。5 . 推理的沖突消解策略 推理過程中的沖突

13、消解策略，就是確定如何從多條匹配規(guī)則中選出一條規(guī)則作為啟用規(guī)則，將它用于當(dāng)前的推理。 目前已有的多種沖突消解策略的基本思想都是對(duì)匹配的知識(shí)或規(guī)則進(jìn)行排序，以決定匹配規(guī)則的優(yōu)先級(jí)別，優(yōu)先級(jí)高的規(guī)則將作為啟用規(guī)則。常用排序方法有如下幾種:(1)按針對(duì)性進(jìn)行排序：有限選用針對(duì)性較強(qiáng)的產(chǎn)生式規(guī)則，因?yàn)樗蟮臈l件較多，其結(jié)論一般更接近目標(biāo)。 (2)按已知事實(shí)的新鮮性排序：我們把數(shù)據(jù)庫中后生成的事實(shí)稱為新鮮的事實(shí)，后生成的事實(shí)比先生成的事實(shí)具有較大的新鮮性。(1)逐個(gè)比較，看A，和B誰的新鮮事實(shí)多(2)A和B中最新鮮的事實(shí)，看誰最新鮮(3)A和B中最不新鮮的事實(shí)，那個(gè)最不新鮮(3)按匹配度排序(1)當(dāng)兩

14、個(gè)模式的相似程度達(dá)到預(yù)先規(guī)定的值時(shí)候，我們就認(rèn)為它們是可可以匹配的哦(2)相似度又稱為匹配度。3.1 推理概述推理概述 (4) 根據(jù)領(lǐng)域問題的特點(diǎn)排序1.當(dāng)領(lǐng)域問題有固定的解題次序時(shí)，可按該次序排列相應(yīng)的知識(shí)， 排在前面的知識(shí)優(yōu)先被應(yīng)用。 2.當(dāng)一只某些產(chǎn)生式規(guī)則被應(yīng)用后會(huì)明顯有利于問題的求解時(shí)，就使這些產(chǎn)生式規(guī)則優(yōu)先被使用。(5) 按上下文限制排序：把產(chǎn)生規(guī)則按它們所描述的上下文分為若干組，在不同條件下只能從相應(yīng)的組中選取有關(guān)的產(chǎn)生式規(guī)則。 (6) 按冗余限制排序：一條產(chǎn)生式應(yīng)用后，產(chǎn)生的冗余知識(shí)越多，則產(chǎn)生式有限度越低。 (7)按條件個(gè)數(shù)排序：如果有多條件產(chǎn)生式規(guī)則生成相同的結(jié)論，則要求條

15、件少的產(chǎn)生式規(guī)則優(yōu)先。 4.2 自然演繹推理方法 自然演繹推理的概念 自然演繹推理是指從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過程。 假言三段論的基本形式為 PQ，QRPR 它表示如果謂詞公式PQ和QR均為真，則謂詞公式PR也為真。 假言推理可用下列形式表示 P，PQ Q它表示如果謂詞公式P和PQ都為真，則可推得Q為真結(jié)論。例如：如果“X是金屬，則X能導(dǎo)電”以及“銅是金屬”可以推出“銅能導(dǎo)電”的結(jié)論拒取式的一般形式為 PQ，Q P它表示如果謂詞公式PQ為真且Q為假，則可推得P為假的結(jié)論。例如，“如果下雨，則地上濕”以及“地上沒濕”可以推出“沒有下雨”2.4.2

16、 2.4.2 利用演繹推理解決問題利用演繹推理解決問題 在利用自然演繹推理方法求解問題時(shí)，一定要注意避免兩種類型的錯(cuò)誤：肯定后件的錯(cuò)誤和否定前件的錯(cuò)誤。 4.2 自然演繹推理方法 肯定后件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過肯定后件Q為真來推出前件P為真。這顯然是錯(cuò)誤的推理邏輯，因?yàn)楫?dāng) PQ及 Q為真時(shí)，前件 P既可能為真，也可能為假。 否定前件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過否定前件P來推出后件Q為假。這也是不允許的，因?yàn)楫?dāng)PQ及P為假時(shí)，后件Q既可能為真，也可能為假。 4.2 自然演繹推理方法 1. A2.B3.A-C4.BC -D5.D -Q證明：Q為真。A, A-C=CB, C = BC

17、BC = DD, D -Q = Q4.3 歸結(jié)推理方法 研究用計(jì)算機(jī)實(shí)現(xiàn)定理證明的機(jī)械化，已是人工智能研究的一個(gè)重要領(lǐng)域。對(duì)于定理證明問題，如果用一階謂詞邏輯表示的話，就是要求對(duì)前提P和結(jié)論Q證明PQ是永真的。然而，要證明這個(gè)謂詞公式的永真性，必須對(duì)所有個(gè)體域上的每一個(gè)解釋進(jìn)行驗(yàn)證，這是極其困難的。為了化簡(jiǎn)問題，和數(shù)學(xué)上常采用的方法一樣，我們考慮反證法。即，我們先否定邏輯結(jié)論Q，再由否定后的邏輯結(jié)論Q及前提條件P出發(fā)推出矛盾，即可證明原問題。1文字 ：原子謂詞公式及其否定定義4.5：任何文字的析取式稱為子句定義4.6: 不包含任何文字的子句稱為空子句，記為NIL；空子句是永假的。2.由子句構(gòu)成

18、的集合稱為子句集，謂詞公式構(gòu)成子句集的步驟：1. 利用等價(jià)關(guān)系消去謂詞公式中的 2. P Q = (P Q) v(P Q)4.3 歸結(jié)推理方法 2. 利用下列等價(jià)關(guān)系把“”移動(dòng)緊靠謂詞的位置上(P) = P;(PQ) = P v Q(PvQ) = P Q(forall x)P = (exists x)P3. 重新命名變?cè)?，使不同兩次元素的變?cè)胁煌拿? . 消去存在量詞5. 把全稱量詞移到公式的左邊6. 利用等價(jià)關(guān)系7. 消去全稱量詞8. 對(duì)變量更名9. 消去合取，留下析取 斯克林范式 從前束形范式中消去全部存在量詞所得到的公式即為Skolem范式，或稱Skolem標(biāo)準(zhǔn)型。例如，如果用f

19、(x)代替上面前束形范式中的y即得到Skolem范式：( x) ( z)(P(x)F(f(x), z)Q(f(x), z)Skolem標(biāo)準(zhǔn)型的一般形式是( x1)( x2)( xn)M(x1,x2,xn)其中，M(x1,x2,xn)是一個(gè)合取范式，稱為Skolem標(biāo)準(zhǔn)型的母式。3.5 歸結(jié)推理方法 將謂詞公式G化為Skolem標(biāo)準(zhǔn)型的步驟如下：（1） 消去謂詞公式G中的蘊(yùn)涵（）和雙條件符號(hào)（ ），以AB代替AB，以(AB)(AB)替換AB。（2） 減少否定符號(hào)（）的轄域，使否定符號(hào)“”最多只作用到一個(gè)謂詞上。（3） 重新命名變?cè)?，使所有的變?cè)拿志煌?，并且自由變?cè)凹s束變?cè)嗖煌?.5

20、 歸結(jié)推理方法 （4） 消去存在量詞。這里分兩種情況，一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，此時(shí)，只要用一個(gè)新的個(gè)體常量替換該存在量詞約束的變?cè)涂梢韵ゴ嬖诹吭~；另一種情況是，存在量詞位于一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，這時(shí)需要用一個(gè)Skolem函數(shù)替換存在量詞而將其消去。（5）把全稱量詞全部移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。（6）母式化為合取范式：任何母式都可以寫成由一些謂詞公式和謂詞公式否定的析取的有限集組成的合取。 需要指出的是，由于在化解過程中，消去存在量詞時(shí)作了一些替換，一般情況下，G的Skolem標(biāo)準(zhǔn)型與G并不等值。3.5 歸結(jié)推理方法 定理4

21、.1不可滿足意義下的一致性定理: 設(shè)有謂詞公式G，而其相應(yīng)的子句集為S，則G是不可滿足的充分必要條件是S是不可滿足的。 要再次強(qiáng)調(diào)：公式G與其子句集S并不等值，只是在不可滿足意義下等價(jià)。 相關(guān)的例子參見教材中的例3.94PP1P2Pn的子句集 當(dāng)PP1P2Pn時(shí)，若設(shè)P的子句集為SP，Pi的子句集為Si，則一般情況下，SP并不等于S1S2S3Sn，而是要比S1S2S3Sn復(fù)雜得多。但是，在不可滿足的意義下，子句集SP與S1S2S3Sn是一致的，即 SP不可滿足S1S2S3Sn不可滿足4.3 歸結(jié)推理方法 4.3.2 4.3.2 HerbrandHerbrand理論理論 1H域 定義3.20 設(shè)

22、謂詞公式G的子句集為S，則按下述方法構(gòu)造的個(gè)體變?cè)騂。稱為公式G或子句集S的Herbrand域，簡(jiǎn)稱H域。（1） 令H0是S中所出現(xiàn)的常量的集合。若S中沒有常量出現(xiàn)，就任取一個(gè)常量aD，規(guī)定H0=a。（2） 令Hi+1=HiS中所有的形如f(t1,tn)的元素其中f(t1,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，而t1，tn是Hi中的元素。i=0，1，2，。 4.3 歸結(jié)推理方法 例4.10 求子句集ST(x)Q(z),R(f(y)的H域。解 此例中沒有個(gè)體常量，任意指定一個(gè)常量a作為個(gè)體常量；只有一個(gè)函數(shù)f(y)，有：H0=aH1=a,f(a)H2=a,f(a),f(f(a)H=a,f(a),f

23、(f(a),f(f(f(a),4.3 歸結(jié)推理方法 2原子集定義3.21 下列集合稱為子句集S的原子集： A所有形如P(t1, t2,tn)的元素其中，P(t1, t2,tn)是出現(xiàn)在S中的任一謂詞符號(hào)，而t1，t2，tn則是S的H域上的任意元素。3.5 歸結(jié)推理方法 定義3.22 將沒有變?cè)霈F(xiàn)的原子、文字、子句和子句集分別稱作基原子、基文字、基子句和基子句集。定義3.23 當(dāng)子句集S中的某個(gè)子句C中的所有變?cè)?hào)均以其H域中的元素替換時(shí)，所得到的基子句稱作C的一個(gè)基例。 例如，對(duì)于子句集 SP(a),P(x)P(f(x) 它的H域?yàn)閍,f(a),f(f(a),。 對(duì)于子句P(a)，因?yàn)槠渲?/p>

24、不含有變?cè)运咽腔泳?，而且aH，所以它也是基例。 3.5 歸結(jié)推理方法 3H域上的解釋定義3.24 如果子句集S的原子集為A，則對(duì)A中各元素的真假值的一個(gè)具體設(shè)定都是S的一個(gè)H解釋。可以證明，在給定域D上的任一個(gè)解釋I，總能在H域上構(gòu)造一個(gè)解釋I*與之對(duì)應(yīng)，使得如果D域上的解釋能滿足子句集S，則在H域的解釋I*也能滿足S（即若S|I=T，就有S|I*=T）。相關(guān)舉例參見教材3.5 歸結(jié)推理方法 定理3.3 設(shè)I是子句集S在域D上的一個(gè)解釋，則存在對(duì)應(yīng)于I的H域解釋I*，使得若有 S|I=T，就必有S|I*=T。定理3.4 子句集S不可滿足的充要條件是S對(duì)H域上的一切解釋都為假。 證明

25、充分性：若S在一般域D上是不可滿足的，必然在H域上是不可滿足的，從而對(duì)H域上的一切解釋都為假。必要性：若S在任一H解釋I*下均為假，必然會(huì)使S在D域上的每一個(gè)解釋為假。否則，如果存在一個(gè)解釋I0使S為真，那么依據(jù)定理3.3可知，一定可以在H域找到相對(duì)應(yīng)的一個(gè)解釋I*0使S為真。這與S在所有H解釋下均為假矛盾。3.5 歸結(jié)推理方法 定理3.5 子句集S不可滿足的充分必要條件是存在一個(gè)有限的不可滿足的基例集S。 該定理稱為Herbrand定理，下面給出它的簡(jiǎn)要證明。證明 充分性：設(shè)子句集S有一個(gè)不可滿足的基例集S，因?yàn)樗豢蓾M足，所以一定存在一個(gè)解釋I使S為假。根據(jù)H域上的解釋與D域上的解釋的對(duì)應(yīng)

26、關(guān)系，可知在D域上一定存在一個(gè)解釋使S不可滿足，從而證明了子句集S是不可滿足的。3.5 歸結(jié)推理方法 必要性：設(shè)子句集S不可滿足，由定理3.4可知，S對(duì)H域上的所有解釋均為假。這樣，就至少會(huì)存在一個(gè)S中的某子句Ci的基例Ci為假。既然至少有一個(gè)基例Ci為假，因而S的基例集S是不可滿足的。另外，由于S中的子句是有限的，而每個(gè)子句又由有限的文字組成，因而S的不可滿足的基例集也是有限的。3.5 歸結(jié)推理方法 3.5.3 3.5.3 歸結(jié)原理歸結(jié)原理定義3.25 若P是原子謂詞公式或原子命題，則稱P與P為互補(bǔ)文字。1命題邏輯中的歸結(jié)原理歸結(jié)與歸結(jié)式 定義3.26 設(shè)C1與C2是子句集中的任意兩個(gè)子句，

27、如果C1中的文字L1與C2中的文字L2互補(bǔ)，則從C1和C2中可以分別消去L1和L2，并將二子句中余下的部分做析取構(gòu)成一個(gè)新的子句C12，稱這一過程為歸結(jié)，所得到的子句C12稱為C1和C2的歸結(jié)式，而稱C1和C2為C12的親本子句。3.5 歸結(jié)推理方法 定理3.6 歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。推論 設(shè)C1和C2是子句集S上的子句，C12是C1和C2的歸結(jié)式。如果把C12加入子句集S后得到新子句集S1，則S1和S在不可滿足的意義下是等價(jià)的。即： S是不可滿足的 S1是不可滿足的 歸結(jié)推理過程歸結(jié)推理過程 子句集S不可滿足性的推理過程如下： (1) 對(duì)子句集S中的各子句間使用歸結(jié)推

28、理規(guī)則。 (2) 將歸結(jié)所得的歸結(jié)式放入子句集S中，得新子句集S。 (3) 檢查子句集S中是否有空子句(NIL),若有則停止推理;否則轉(zhuǎn)（4）。 (4) 置S=S，轉(zhuǎn)步驟（1）。3.5 歸結(jié)推理方法 2一階謂詞邏輯中的歸結(jié)原理下面是謂詞邏輯關(guān)于歸結(jié)的定義。定義定義3.273.27 設(shè)C1和C2是兩個(gè)沒有相同變?cè)淖泳?，L1 和L2分別是C1 和C2的文字，如果L1與 L2有mgu ，則把 C12 =( C1L1)(C2 L2)稱作子句C1 和C2的一個(gè)二元?dú)w結(jié)式，而L1 和L2是被歸結(jié)的文字。 為了說明的方便。將Ci和Li寫成集合形式， 如P(x)Q(y)P(x),Q(y)。在集合的表示下做減

29、法或做并運(yùn)算，然后再寫成子句形，如集合運(yùn)算結(jié)果為P(x),Q(y)，可改寫為P(x)Q(y)。 3.5 歸結(jié)推理方法 在謂詞邏輯中，對(duì)子句進(jìn)行歸結(jié)推理時(shí)，要注意以下幾個(gè)問題：（1）若被歸結(jié)的子句C1 和C2中具有相同的變?cè)獣r(shí)，需要將其中一個(gè)子句的變?cè)?，否則可能無法做合一置換。從而沒有辦法進(jìn)行歸結(jié)。 （2）在求歸結(jié)式時(shí)，不能同時(shí)消去兩個(gè)互補(bǔ)文字對(duì)，消去兩個(gè)互補(bǔ)文字對(duì)所得的結(jié)果不是兩個(gè)親本子句的邏輯推論。（3）如果在參加歸結(jié)的子句內(nèi)含有可合一的文字，則在進(jìn)行歸結(jié)之前，應(yīng)對(duì)這些文字進(jìn)行合一，以實(shí)現(xiàn)這些子句內(nèi)部的化簡(jiǎn)。 3.5 歸結(jié)推理方法 應(yīng)用因子的概念，可對(duì)謂詞邏輯中的歸結(jié)原理定義如下。 定義

30、3.28 設(shè)C1和 C2是沒有相同變?cè)淖泳?，則下列四種二元?dú)w結(jié)式都叫做C1和C2的歸結(jié)式，仍記作C12。（1） C1與C2的二元?dú)w結(jié)式。（2） C1的因子C11與C2的二元?dú)w結(jié)式。（3） C1與C2的因子C22的二元?dú)w結(jié)式。（4） C1的因子C11與C2的因子C22的二元?dú)w結(jié)式。3.5 歸結(jié)推理方法 例例 設(shè)C1=P(a)Q(x)R(x)，C2 =P(y)Q(b)， 求其二元?dú)w結(jié)式。解解 若選L1=P(a)，L2=P(y)，則L1和L2的mgu是=a/y，于是由定義3.27得C1和C2 的二元?dú)w結(jié)式為C12 =( C1-L1)(C2 -L2)=(P(a),Q(x),R(x)-P(a)(P(a

31、),Q(b)-P(a)=(Q(x),R(x)(Q(b)=Q(x)R(x)Q(b) 若選L1=Q(x)，L2=Q(b)，則二者的mgu=b/x， C12 =P(a)R(b)P(y)3.5 歸結(jié)推理方法 3 3歸結(jié)原理的完備性歸結(jié)原理的完備性 對(duì)于一階謂詞邏輯，從不可滿足的意義上說，歸結(jié)原理是完備的。即若子句集是不可滿足的，則必存在一個(gè)從該子句集到空子句的歸結(jié)推理過程；反之，若從子句集到空子句存在一個(gè)歸結(jié)推理過程，則該子句集必是不可滿足的。 3.5 歸結(jié)推理方法 3.5.4 利用歸結(jié)原理進(jìn)行定理證明 應(yīng)用歸結(jié)原理進(jìn)行定理證明的步驟如下：應(yīng)用歸結(jié)原理進(jìn)行定理證明的步驟如下： 設(shè)要被證明的定理可用謂詞

32、公式表示為如下的形式： A1A2AnB(1) 首先否定結(jié)論B，并將否定后的公式B與前提公式集組成如下形式的謂詞公式： G= A1A2AnB(2) 求謂詞公式G的子句集S。(3) 應(yīng)用歸結(jié)原理，證明子句集S的不可滿足性，從而證明謂詞公式G的不可滿足性。這就說明對(duì)結(jié)論B的否定是錯(cuò)誤的，推斷出定理的成立。3.5 歸結(jié)推理方法 例例 已知：A: (x)( y)(P(x,y)Q(y)( y)(R(y)T(x,y)B: ( x)R(x)( x)( y)(P(x,y)Q(y)求證：B是A的邏輯結(jié)論。證明證明 首先將A和B化為子句集(1)P(x,y)Q(y) R(f(x)(2)P(x,y)Q(y) T(x,f

33、(x) /(1)(2)為A(3)R(z)(4)P(a，b)(5)Q(b) /(3)(4)(5)為B3.5 歸結(jié)推理方法 下面進(jìn)行歸結(jié)： （6） P(x,y)Q(y) （1）與（3）歸結(jié)，=f(x)/z （7） Q(b) （4）與（6）歸結(jié)，=a/x,b/y （8） NIL（空子句） （5）與（7）歸結(jié)所以B是A的邏輯結(jié)論。3.5 歸結(jié)推理方法 3.5.5 3.5.5 應(yīng)用歸結(jié)原理進(jìn)行問題求解應(yīng)用歸結(jié)原理進(jìn)行問題求解下面是利用歸結(jié)原理求取問題答案的步驟：（1）把已知前提條件用謂詞公式表示出來，并化成相應(yīng)的子句集，設(shè)該子句集的名字為S1。（2）把待求解的問題也用謂詞公式表示出來，然后將其否定，并與

34、一謂詞ANSWER構(gòu)成析取式。謂詞ANSWER是一個(gè)專為求解問題而設(shè)置的謂詞，其變量必須與問題公式的變量完全一致。（3）把問題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，并把該子句集與S1合并構(gòu)成子句集S。3.5 歸結(jié)推理方法 （4）對(duì)子句集S應(yīng)用謂詞歸結(jié)原理進(jìn)行歸結(jié)，在歸結(jié)的過程中，通過合一置換，改變ANSWER中的變?cè)?。?）如果得到歸結(jié)式ANSWER ，則問題的答案即在ANSWER謂詞中。3.5 歸結(jié)推理方法 例例 任何兄弟都有同一個(gè)父親，John和Peter是兄弟，且John的父親是David，問Peter的父親是誰？解解 第一步：將已知條件用謂詞公式表示出來，并化成子句集，那么要先

35、定義謂詞。（1） 定義謂詞：設(shè)Father(x,y)表示x是y的父親。Brother(x,y)表示x和y是兄弟。3.5 歸結(jié)推理方法 （2） 將已知事實(shí)用謂詞公式表示出來。 F1 ：任何兄弟都有同一個(gè)父親。 (x)(y)(z)(Brother(x,y)Father(z,x)Father(z,y) F2：John和Peter是兄弟。 Brother(John,Peter) F3： John的父親是David。 Father(David, John)（3） 將它們化成子句集得： S1=Brother(x,y)Father(z,x)Father(z,y), Brother(John,Peter),

36、Father(David,John)3.5 歸結(jié)推理方法 第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER作析取。 設(shè)Peter的父親是u，則有：Father(u,Peter)。 將其否定與ANSWER作析取，得： G：Father(u,Peter)ANSWER(u)3.5 歸結(jié)推理方法 第三步：將上述公式G化為子句集S2,并將S1和S2合并到S。 S2 =Father(u,Peter)ANSWER(u) S= S1S2將S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）Father

37、(David,John)。（4）Father(u,Peter)ANSWER(u)。3.5 歸結(jié)推理方法 第四步：應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)（5）Brother(John,y)Father(David,y) （1）與（3）歸結(jié) =David/z,John/x（6）Brother(John,Peter)ANSWER(David) （4）與（5）歸結(jié)=David/u,Peter/y（7）ANSWER(David) （2）與（6）歸結(jié)第五步：得到了歸結(jié)式ANSWER(David)，答案即在其中，所以u(píng)=David。即Peter的父親是David。3.5 歸結(jié)推理方法 3.6 歸結(jié)過程的控制策略歸結(jié)過程的控制策略 3.6.1 3.6.1 引入控制策略引入控制策略1引入控制策略的原因 對(duì)子句集S進(jìn)行歸結(jié)時(shí)，首先要從子句集中找出可進(jìn)行歸結(jié)的一對(duì)子句進(jìn)行歸結(jié)。由于事先并不知道子句集中的哪兩個(gè)子句可以進(jìn)行歸結(jié)，也不知道通過對(duì)哪些子句的歸結(jié)可盡快得到空子句，所以就必須對(duì)子句集中的所有子句逐一進(jìn)行比較，以對(duì)所有可能歸結(jié)的子句對(duì)進(jìn)行歸結(jié)，并將歸結(jié)式加入S中，再做第二層這樣的歸結(jié)，直到產(chǎn)生空子句