礦大人工智能4

1、第四章 自動推理自動推理 2 2 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則表示事物間的啟發(fā)式關(guān)聯(lián)表示事物間的啟發(fā)式關(guān)聯(lián) P P Q Q 或或 IF P then QIF P then Q P P規(guī)則激活使用的條件規(guī)則激活使用的條件（或稱（或稱前提前提）；）； Q Q指示規(guī)則激活時應(yīng)該執(zhí)行的動作指示規(guī)則激活時應(yīng)該執(zhí)行的動作（或應(yīng)該得出的（或應(yīng)該得出的結(jié)論結(jié)論）。）。 * * 激活激活規(guī)則條件部分滿足規(guī)則條件部分滿足 規(guī)則分類規(guī)則分類( (規(guī)則右部的表示方式規(guī)則右部的表示方式) )條件條件- -動作型和前提動作型和前提- -結(jié)論型。結(jié)論型。 前提結(jié)論型規(guī)則前提結(jié)論型規(guī)則更接近于上一章中介紹的演繹推理規(guī)則更接近于上一章

2、中介紹的演繹推理規(guī)則 e.g. e.g. 若若 某動物是哺乳動物，且吃肉；某動物是哺乳動物，且吃肉； 則則 這種動物是食肉動物。這種動物是食肉動物。 或表示為更便于計算機(jī)操作的形式化方式：或表示為更便于計算機(jī)操作的形式化方式： （Mammal ?xMammal ?x） (Eat ?x Meat) (Eat ?x Meat) (Carnivore ?x)(Carnivore ?x) * * 模式變量模式變量可以視為隱含地受可以視為隱含地受全稱量詞全稱量詞約束約束 * *不要求遵從一階謂詞演算的表示形式不要求遵從一階謂詞演算的表示形式 * *規(guī)則前提規(guī)則前提匹配模式（即謂詞公式）、關(guān)系表達(dá)式和真值

3、函數(shù)的匹配模式（即謂詞公式）、關(guān)系表達(dá)式和真值函數(shù)的 任意與、或、非組合，任意與、或、非組合， * * 規(guī)則結(jié)論規(guī)則結(jié)論任意數(shù)據(jù)結(jié)構(gòu)（向量、數(shù)組、表格等）任意數(shù)據(jù)結(jié)構(gòu)（向量、數(shù)組、表格等） 產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng) 3 3 條件條件-動作型規(guī)則動作型規(guī)則左部類同于前提左部類同于前提-結(jié)論型規(guī)則，規(guī)則右部可結(jié)論型規(guī)則，規(guī)則右部可是是任意操作函數(shù)任意操作函數(shù)，不僅用于操作綜合數(shù)據(jù)庫也可是屏幕、圖像、，不僅用于操作綜合數(shù)據(jù)庫也可是屏幕、圖像、文件操作和用于執(zhí)行各種預(yù)定的計算功能。文件操作和用于執(zhí)行各種預(yù)定的計算功能。 例：例：x-1 1 null(y) = x:= 0 規(guī)則的前提或條件統(tǒng)稱規(guī)則的左部（或

4、前件），規(guī)則的結(jié)論和規(guī)則的前提或條件統(tǒng)稱規(guī)則的左部（或前件），規(guī)則的結(jié)論和動作也不加區(qū)分地統(tǒng)稱為規(guī)則的右部（或后件）。動作也不加區(qū)分地統(tǒng)稱為規(guī)則的右部（或后件）。4 4 產(chǎn)生式規(guī)則總結(jié)產(chǎn)生式規(guī)則總結(jié) := := | := | := AND (AND ). | OR (OR ). := (, .)【說明】：產(chǎn)生式又稱規(guī)則或產(chǎn)生式規(guī)則；“前提”：又稱條件、前提條件、前件、左部等；“結(jié)論”：又稱后件、右部等。5 53.2.1.2 產(chǎn)生式系統(tǒng)的組成產(chǎn)生式系統(tǒng)的組成產(chǎn)生式系統(tǒng)的三個組成部分：規(guī)則庫、綜合數(shù)據(jù)庫、規(guī)則庫、綜合數(shù)據(jù)庫、控制系統(tǒng)?？刂葡到y(tǒng)。1、規(guī)則庫 用于描述相應(yīng)領(lǐng)域內(nèi)知識的產(chǎn)生式集合。 在建

5、立規(guī)則庫時，應(yīng)注意如下問題： （1）有效地表達(dá)領(lǐng)域內(nèi)的過程性知識：包括規(guī)則的建立、不確定性知識的表示、推理鏈的形成、知識的完整性等。 （2）對知識進(jìn)行合理的組織與管理：目的是使得推理避免訪問與所求解的問題無關(guān)的知識，以提高問題求解效率。6 62 2、綜合數(shù)據(jù)庫、綜合數(shù)據(jù)庫 綜合數(shù)據(jù)庫又稱為綜合數(shù)據(jù)庫又稱為事實庫、上下文、黑板事實庫、上下文、黑板等。它是一個用于等。它是一個用于存存放問題求解過程中各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu)放問題求解過程中各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu)，例如：問題的初始，例如：問題的初始狀態(tài)、原始證據(jù)、推理中得到的中間結(jié)論、最終結(jié)論等。狀態(tài)、原始證據(jù)、推理中得到的中間結(jié)論、最終結(jié)論等。 綜合

6、數(shù)據(jù)庫的內(nèi)容是在不斷變化的，是綜合數(shù)據(jù)庫的內(nèi)容是在不斷變化的，是動態(tài)動態(tài)的的。 綜合數(shù)據(jù)庫中的綜合數(shù)據(jù)庫中的已知事實已知事實通常用通常用字符串、向量、集合、矩陣、表字符串、向量、集合、矩陣、表等數(shù)據(jù)結(jié)構(gòu)表示。等數(shù)據(jù)結(jié)構(gòu)表示。e.g.關(guān)于動物世界的產(chǎn)生式系統(tǒng)有如下綜合數(shù)據(jù)庫：關(guān)于動物世界的產(chǎn)生式系統(tǒng)有如下綜合數(shù)據(jù)庫： (Mammal Dog) (Eat Dog Meat)綜合數(shù)據(jù)庫可視為推理過程中間結(jié)果的綜合數(shù)據(jù)庫可視為推理過程中間結(jié)果的存貯池存貯池。隨著中間結(jié)果的。隨著中間結(jié)果的不斷加入，使綜合數(shù)據(jù)庫描述的問題狀態(tài)逐步轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)。不斷加入，使綜合數(shù)據(jù)庫描述的問題狀態(tài)逐步轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)。7

7、73 3、控制系統(tǒng)、控制系統(tǒng) 控制系統(tǒng)又稱控制系統(tǒng)又稱推理機(jī)構(gòu)推理機(jī)構(gòu)，由一組程序組成，負(fù)責(zé)，由一組程序組成，負(fù)責(zé)整個產(chǎn)生式系統(tǒng)的整個產(chǎn)生式系統(tǒng)的運(yùn)行運(yùn)行，實現(xiàn)對問題的求解。，實現(xiàn)對問題的求解。 控制系統(tǒng)的主要工作：控制系統(tǒng)的主要工作：1)按一定的策略從規(guī)則庫中按一定的策略從規(guī)則庫中選擇規(guī)則選擇規(guī)則，并與綜合數(shù)據(jù)，并與綜合數(shù)據(jù)庫中的已知事實庫中的已知事實進(jìn)行匹配進(jìn)行匹配。2)當(dāng)發(fā)生當(dāng)發(fā)生沖突沖突（即匹配成功的規(guī)則不止一條）時，調(diào)（即匹配成功的規(guī)則不止一條）時，調(diào)用相應(yīng)的沖突解決策略予以消解。用相應(yīng)的沖突解決策略予以消解。3)在執(zhí)行某條規(guī)則時，若該規(guī)則的右部是一個或多個在執(zhí)行某條規(guī)則時，若該規(guī)則

8、的右部是一個或多個結(jié)論，則結(jié)論，則把這些結(jié)論加到綜合數(shù)據(jù)庫中把這些結(jié)論加到綜合數(shù)據(jù)庫中；若規(guī)則的；若規(guī)則的右部是一個或多個操作，則右部是一個或多個操作，則執(zhí)行這些操作執(zhí)行這些操作。8 84)對于對于不確定性知識不確定性知識，在執(zhí)行每一條規(guī)則時，在執(zhí)行每一條規(guī)則時，還要按一定的算法計算結(jié)論的不確定性。還要按一定的算法計算結(jié)論的不確定性。5)隨時掌握結(jié)束產(chǎn)生式系統(tǒng)運(yùn)行的時機(jī)，以便隨時掌握結(jié)束產(chǎn)生式系統(tǒng)運(yùn)行的時機(jī)，以便在適當(dāng)?shù)臅r候停止系統(tǒng)的運(yùn)行在適當(dāng)?shù)臅r候停止系統(tǒng)的運(yùn)行。 9 9例如，在關(guān)于動物世界的產(chǎn)生式系統(tǒng)中，已建立規(guī)則庫，其包括上述形式例如，在關(guān)于動物世界的產(chǎn)生式系統(tǒng)中，已建立規(guī)則庫，其包括上

9、述形式化表示的規(guī)則；也建立了如上所述的綜合數(shù)據(jù)庫；化表示的規(guī)則；也建立了如上所述的綜合數(shù)據(jù)庫； 規(guī)則庫規(guī)則庫:（Mammal ?x）和（）和（Eat ?x Meat） 綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫:（Mammal Dog）和（）和（Eat Dog Meat） 結(jié)論（結(jié)論（Carnivore Dog）最后被插入綜合數(shù)據(jù)庫。）最后被插入綜合數(shù)據(jù)庫。 實際上產(chǎn)生式系統(tǒng)的控制機(jī)制就是實際上產(chǎn)生式系統(tǒng)的控制機(jī)制就是不斷地挑選可激活的規(guī)則對綜合數(shù)據(jù)不斷地挑選可激活的規(guī)則對綜合數(shù)據(jù)庫進(jìn)行操作，直至得到解答（綜合數(shù)據(jù)庫內(nèi)容轉(zhuǎn)變?yōu)槊枋隽四繕?biāo)狀態(tài)），庫進(jìn)行操作，直至得到解答（綜合數(shù)據(jù)庫內(nèi)容轉(zhuǎn)變?yōu)槊枋隽四繕?biāo)狀態(tài)），或失敗結(jié)

10、束?；蚴〗Y(jié)束。產(chǎn)生式系統(tǒng)的三大組成部分的相互關(guān)系圖：產(chǎn)生式系統(tǒng)的三大組成部分的相互關(guān)系圖：控制系統(tǒng)控制系統(tǒng)（推理機(jī)構(gòu)）（推理機(jī)構(gòu)）規(guī)則庫綜合數(shù)據(jù)庫10101）八數(shù)碼游戲）八數(shù)碼游戲首先，就以表示棋盤布局（問題狀態(tài)）的矩陣作為綜合數(shù)據(jù)首先，就以表示棋盤布局（問題狀態(tài)）的矩陣作為綜合數(shù)據(jù)庫內(nèi)容。然后定義一組產(chǎn)生式規(guī)則。鑒于改變棋盤布局的操庫內(nèi)容。然后定義一組產(chǎn)生式規(guī)則。鑒于改變棋盤布局的操作可以通過空格移動來實現(xiàn)，就建立作可以通過空格移動來實現(xiàn)，就建立4個個條件條件-動作型規(guī)則動作型規(guī)則來來為空格的左、上、右、下移動操作建立激活條件，設(shè)為空格的左、上、右、下移動操作建立激活條件，設(shè)Sij指示指示

11、矩陣第矩陣第i行第行第j列的數(shù)碼（列的數(shù)碼（1i,j3），），io、jo指示空格所在的行、指示空格所在的行、列數(shù)，則有：列數(shù)，則有：R1: jo -1 1 = Siojo := Sio(jo-1) Sio(jo-1) := 0 (空格左移空格左移)R2: io -1 1 = Siojo := S(io-1)jo S(io-1)jo := 0 (空格上移空格上移)R3: jo + 1 3 = Siojo := Sio(jo+1) Sio(jo+1) := 0 (空格右移空格右移)R4: io + 1 3 = Siojo := S(io+1)jo S(io+1)jo := 0 (空格下移空格下移)

12、應(yīng)用實例應(yīng)用實例 11112）傳教士與野人問題）傳教士與野人問題 把問題求解描述為由綜合數(shù)據(jù)庫和規(guī)則庫兩部分組成。綜合數(shù)據(jù)庫的內(nèi)容把問題求解描述為由綜合數(shù)據(jù)庫和規(guī)則庫兩部分組成。綜合數(shù)據(jù)庫的內(nèi)容就定義為三元組：就定義為三元組：（m，c，b）m、c和和b分別指示河左岸傳教士、野人人數(shù)和渡船是否在左岸。綜合數(shù)據(jù)分別指示河左岸傳教士、野人人數(shù)和渡船是否在左岸。綜合數(shù)據(jù)庫的初始化內(nèi)容是（庫的初始化內(nèi)容是（3，3，1），指示初始狀態(tài)；而推理結(jié)束（產(chǎn)生生系），指示初始狀態(tài)；而推理結(jié)束（產(chǎn)生生系統(tǒng)的運(yùn)行成功結(jié)束）時的內(nèi)容是（統(tǒng)的運(yùn)行成功結(jié)束）時的內(nèi)容是（0，0，0），指示目標(biāo)狀態(tài)。由于有），指示目標(biāo)狀態(tài)。由

13、于有10個可能的操作算子，故而總共需設(shè)計個可能的操作算子，故而總共需設(shè)計10條規(guī)則去表示操作激活的條件，如條規(guī)則去表示操作激活的條件，如下下: ( L(m,c)和和 R(m,c)L(1,0): m 1 b = 1 = m := m - 1 b := 0;L(0,1): c 1 b = 1 = c := c - 1 b := 0;L(1,1): m 1 c 1b=1 = m := m -1c := c-1b := 0;L(2,0): m 2 b = 1 = m := m - 2 b := 0;L(0,2): c 2 b = 1 = c := c - 2 b := 0;R(1,0): m 2 b

14、= 0 = m := m + 1 b := 1;R(0,1): c 2 b = 0 = c := c + 1 b := 1;R(1,1): m 2 c 2b=0 = m := m +1c :=c+1b := 1;R(2,0): m 1 b = 0 = m := m + 2 b := 1;R(0,2): c 1 b = 0 = c := c + 2 b := 1. . .應(yīng)用實例應(yīng)用實例 在推理過程的每一問題狀態(tài)下都有可能激活多條規(guī)則。例如，初始狀態(tài)下，在推理過程的每一問題狀態(tài)下都有可能激活多條規(guī)則。例如，初始狀態(tài)下，由于由于m = c = 3和和b = 1,有有5條條L規(guī)則激活，但規(guī)則規(guī)則激活

15、，但規(guī)則L(1,0)和和L(2,0)不可取，因不可取，因為違反了傳教士的安全約束?？梢栽谄渌鼮檫`反了傳教士的安全約束?？梢栽谄渌?條激活規(guī)則中任選一條加以執(zhí)行條激活規(guī)則中任選一條加以執(zhí)行（執(zhí)行其右部）。若能提供啟發(fā)式函數(shù)，就可進(jìn)一步舍去規(guī)則（執(zhí)行其右部）。若能提供啟發(fā)式函數(shù)，就可進(jìn)一步舍去規(guī)則L(0,1) 此外，若在每一條規(guī)則的右部增加一個函數(shù)去顯示執(zhí)行的渡河操作，例如此外，若在每一條規(guī)則的右部增加一個函數(shù)去顯示執(zhí)行的渡河操作，例如write(L(1,0)（對應(yīng)于面向渡河操作（對應(yīng)于面向渡河操作L(1,0)的規(guī)則），和的規(guī)則），和write(R(1，0) （對應(yīng)于面向渡河操作（對應(yīng)于面向渡河操

16、作R(1,0)的規(guī)則）；并增加一條指示推理成功結(jié)束的規(guī)則）；并增加一條指示推理成功結(jié)束（到達(dá)目標(biāo)狀態(tài)）的規(guī)則：（到達(dá)目標(biāo)狀態(tài)）的規(guī)則：m = 0 c = 0 b = 0 = halt()；則產(chǎn)生式系統(tǒng)能在綜合數(shù)據(jù)庫的內(nèi)容變遷為表示了目標(biāo)狀態(tài)時成功結(jié)束推則產(chǎn)生式系統(tǒng)能在綜合數(shù)據(jù)庫的內(nèi)容變遷為表示了目標(biāo)狀態(tài)時成功結(jié)束推理，并顯示出使初始狀態(tài)變遷到目標(biāo)狀態(tài)的渡河操作（規(guī)則）序列。這里理，并顯示出使初始狀態(tài)變遷到目標(biāo)狀態(tài)的渡河操作（規(guī)則）序列。這里halt是一個指示推理結(jié)束的函數(shù)。是一個指示推理結(jié)束的函數(shù)。 12123)旅行商問題：一個在旅行商問題：一個在A城市工作的城市工作的推銷員需去幾個外地城市辦

17、理業(yè)推銷員需去幾個外地城市辦理業(yè)務(wù)，每個城市只允許去一次，遍務(wù)，每個城市只允許去一次，遍歷這些城市后返回歷這些城市后返回A城市；已知城市；已知各城市間的里程，要求尋找最短各城市間的里程，要求尋找最短的遍歷路線。的遍歷路線。首先令綜合數(shù)據(jù)庫的內(nèi)容表示為城首先令綜合數(shù)據(jù)庫的內(nèi)容表示為城市名列表，初始時該列表只包含城市名列表，初始時該列表只包含城市市A。設(shè)計真值函數(shù)。設(shè)計真值函數(shù)not-visit(x)指指示未訪問過城市示未訪問過城市x，真值函數(shù)，真值函數(shù)visit-all指示已遍歷各城市，操作函數(shù)指示已遍歷各城市，操作函數(shù)move(x)指示去城市指示去城市x并將并將x加進(jìn)城加進(jìn)城市名列表；則可以建

18、立下面二條規(guī)市名列表；則可以建立下面二條規(guī)則：則：R1: not-visit(x) move(x),R2: visit-all() move(A).由于有由于有4個外地城市，所以推理開始個外地城市，所以推理開始時相應(yīng)于規(guī)則時相應(yīng)于規(guī)則R1，有，有4條規(guī)則實例條規(guī)則實例激活，分別相應(yīng)于激活，分別相應(yīng)于x取值取值B、C、D、E。若以上、下。若以上、下2城市間路徑最城市間路徑最短作為沖突解決的依據(jù)，則相應(yīng)于短作為沖突解決的依據(jù)，則相應(yīng)于x := C的規(guī)則實例被選用，即推銷的規(guī)則實例被選用，即推銷員走向城市員走向城市C。依次，經(jīng)由推理，。依次，經(jīng)由推理，推銷員將相繼走向城市推銷員將相繼走向城市D、B、

19、E。接下去規(guī)則接下去規(guī)則R2激活，推銷員返回城激活，推銷員返回城市市A。13134）文法分析問題）文法分析問題 語言學(xué)的一個重要問題就是判定一個符號序列是否合法句，稱為文法語言學(xué)的一個重要問題就是判定一個符號序列是否合法句，稱為文法分析。文法分析可用產(chǎn)生式系統(tǒng)加以解決，下面就以英語為例。文法分析分析。文法分析可用產(chǎn)生式系統(tǒng)加以解決，下面就以英語為例。文法分析涉及到終結(jié)符和非終結(jié)符，前者就是英語單詞，如：涉及到終結(jié)符和非終結(jié)符，前者就是英語單詞，如：boy, football, place, plays, in, the后者則為文法分析的專用詞匯，如：后者則為文法分析的專用詞匯，如：S, N,

20、NP, P, PP, V, VP, DET 可以設(shè)計一組重寫規(guī)則作為產(chǎn)生式規(guī)則：可以設(shè)計一組重寫規(guī)則作為產(chǎn)生式規(guī)則：N NP /名詞就是名詞詞組；名詞就是名詞詞組；DET NP NP /冠詞加名詞詞組還是名詞詞組；冠詞加名詞詞組還是名詞詞組；P NP PP /介詞加名詞詞組構(gòu)成介詞詞組；介詞加名詞詞組構(gòu)成介詞詞組；NP PP NP /名詞詞組后跟介詞詞組仍是名詞詞組；名詞詞組后跟介詞詞組仍是名詞詞組；V NP PP VP /動詞詞組后跟名詞詞組和介詞詞組構(gòu)成謂語；動詞詞組后跟名詞詞組和介詞詞組構(gòu)成謂語；NP VP S /名詞詞組與謂語一起構(gòu)成句子；名詞詞組與謂語一起構(gòu)成句子；Boy NFoot

21、ball Nplace Nplays Nin Pthe DET若當(dāng)前要作文法分析的句子是：若當(dāng)前要作文法分析的句子是：the boy plays football in the place.則可以將該句子作為綜合數(shù)據(jù)庫的初始內(nèi)容，推理過程就是不斷地通過匹配（相則可以將該句子作為綜合數(shù)據(jù)庫的初始內(nèi)容，推理過程就是不斷地通過匹配（相同）比較，用激活規(guī)則的右部取代綜合數(shù)據(jù)庫中與規(guī)則左部匹配的內(nèi)容。例如，同）比較，用激活規(guī)則的右部取代綜合數(shù)據(jù)庫中與規(guī)則左部匹配的內(nèi)容。例如，可以先將該句子的所有單詞先替換為語法詞匯：可以先將該句子的所有單詞先替換為語法詞匯：DET N V N P DET N然后再作進(jìn)一

22、步的替代為：然后再作進(jìn)一步的替代為：NP V NP PP繼續(xù)通過激活規(guī)則去進(jìn)行符號重寫：繼續(xù)通過激活規(guī)則去進(jìn)行符號重寫：NP VP最后綜合數(shù)據(jù)庫只剩下符號最后綜合數(shù)據(jù)庫只剩下符號S（指示合法句），文法分析成功結(jié)束。（指示合法句），文法分析成功結(jié)束。1414 練習(xí)：練習(xí)：用產(chǎn)生式表示法設(shè)計求解如下所示二階梵塔問題的產(chǎn)生用產(chǎn)生式表示法設(shè)計求解如下所示二階梵塔問題的產(chǎn)生式系統(tǒng)，包括綜合數(shù)據(jù)庫、規(guī)則庫和沖突解法（不必設(shè)計控式系統(tǒng)，包括綜合數(shù)據(jù)庫、規(guī)則庫和沖突解法（不必設(shè)計控制系統(tǒng)）；并應(yīng)用回溯控制算法給出問題狀態(tài)的變遷過程。制系統(tǒng)）；并應(yīng)用回溯控制算法給出問題狀態(tài)的變遷過程。這個梵塔問題是這樣的：有三

23、個柱子和大、小二個盤子，這個梵塔問題是這樣的：有三個柱子和大、小二個盤子，盤子有中孔。初始狀態(tài)下二個盤子套在柱子盤子有中孔。初始狀態(tài)下二個盤子套在柱子1上，目標(biāo)狀態(tài)下上，目標(biāo)狀態(tài)下則都套到柱子則都套到柱子2上。搬動盤子應(yīng)遵從以下約束：上。搬動盤子應(yīng)遵從以下約束：大盤不能壓大盤不能壓在小盤上面，且每次只能搬一個盤子；在小盤上面，且每次只能搬一個盤子；優(yōu)先搬動套在序號優(yōu)先搬動套在序號小的柱子上的盤子；小的柱子上的盤子；放盤子到柱子的優(yōu)先順序遵從柱子序放盤子到柱子的優(yōu)先順序遵從柱子序號的右循環(huán)，即號的右循環(huán)，即1、2、3、1、2。15151 1） 問題表示：問題表示：（1 1） 綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫

24、DATA=LDATA=L，初始，初始L =L =（1 11 1），終態(tài)），終態(tài)L =L =（2 22 2）其中）其中L(1)L(1)指指示小盤位置，示小盤位置，L(2)L(2)指示大盤位置。指示大盤位置。 * */ /有兩種表示方法：面向盤子和面向柱子，由于盤子少就用有兩種表示方法：面向盤子和面向柱子，由于盤子少就用 面向盤子的表示。盤子的位置只可能為面向盤子的表示。盤子的位置只可能為1 1、2 2、3 3，分別指向，分別指向 3 3個柱子。個柱子。（2 2） 規(guī)則集（二條）：規(guī)則集（二條）： * */ /為大、小盤的搬動各設(shè)計一條規(guī)則為大、小盤的搬動各設(shè)計一條規(guī)則 if L(1) if L(

25、1) n, then L(1)=n; (1,2,3) n, then L(1)=n; (1,2,3) * */ /由于小盤必定在大盤上，所以任何場合均可搬動小盤。由于小盤必定在大盤上，所以任何場合均可搬動小盤。 if L(2) if L(2) L(1), L(1) L(1), L(1) n, L(2) n, L(2) n,then L(2)= n; n,then L(2)= n;(n=1,2,3)(n=1,2,3)* */ /僅小盤不在大盤上時可搬大盤，這時小盤必在另一柱子僅小盤不在大盤上時可搬大盤，這時小盤必在另一柱子 上，故大盤只能搬到剩下的無盤柱子上。上，故大盤只能搬到剩下的無盤柱子上。

26、（3 3）沖突解法）沖突解法 在數(shù)碼小的柱子上的盤優(yōu)先搬；在數(shù)碼小的柱子上的盤優(yōu)先搬；若數(shù)碼相同，則目的柱的優(yōu)先次序按（若數(shù)碼相同，則目的柱的優(yōu)先次序按（1 1、2 2、3 3）循環(huán)排）循環(huán)排 列。列。2 2） 基于回溯控制算法的問題狀態(tài)變遷過程：基于回溯控制算法的問題狀態(tài)變遷過程：2 2 3 3 3 32 2 3 3（1 11 1）-（2 12 1）-（2 32 3）-（3 33 3）-（1 31 3）-/ / / / 3 3（2 32 3）| |（3 33 3）| |（1 21 2）-（2 22 2） * */ /箭頭上面的數(shù)字指示在前一狀態(tài)下激活的規(guī)則例，箭頭上面的數(shù)字指示在前一狀態(tài)下激

27、活的規(guī)則例，/指示指示 不合法狀態(tài)，應(yīng)該回溯。不合法狀態(tài)，應(yīng)該回溯。1616 可以從不同的角度對產(chǎn)生式系統(tǒng)作分類可以從不同的角度對產(chǎn)生式系統(tǒng)作分類 按推理方向按推理方向正向、逆向和雙向產(chǎn)生式系統(tǒng)（前提正向、逆向和雙向產(chǎn)生式系統(tǒng)（前提-結(jié)論型）：結(jié)論型）： 正向產(chǎn)生式系統(tǒng)正向產(chǎn)生式系統(tǒng)這種系統(tǒng)通過檢查前提是否滿足當(dāng)前問題狀態(tài)（與綜這種系統(tǒng)通過檢查前提是否滿足當(dāng)前問題狀態(tài)（與綜合數(shù)據(jù)庫內(nèi)容匹配）來決定規(guī)則的激活，由此實現(xiàn)正向推理方式，并推動問合數(shù)據(jù)庫內(nèi)容匹配）來決定規(guī)則的激活，由此實現(xiàn)正向推理方式，并推動問題求解從初始狀態(tài)向目標(biāo)狀態(tài)逼近。以正向推理方式使用的規(guī)則稱為正向規(guī)題求解從初始狀態(tài)向目標(biāo)狀態(tài)

28、逼近。以正向推理方式使用的規(guī)則稱為正向規(guī)則，或則，或F規(guī)則（規(guī)則（Forward rule）。）。 逆向產(chǎn)生式系統(tǒng)逆向產(chǎn)生式系統(tǒng)這種系統(tǒng)通過檢查結(jié)論是否滿足當(dāng)前問題狀態(tài)來決定這種系統(tǒng)通過檢查結(jié)論是否滿足當(dāng)前問題狀態(tài)來決定規(guī)則的激活，由此實現(xiàn)逆向推理方式，并推動問題求解從目標(biāo)狀態(tài)向初始狀規(guī)則的激活，由此實現(xiàn)逆向推理方式，并推動問題求解從目標(biāo)狀態(tài)向初始狀態(tài)逼近。以逆向推理方式使用的規(guī)則稱為逆向規(guī)則，或態(tài)逼近。以逆向推理方式使用的規(guī)則稱為逆向規(guī)則，或B規(guī)則（規(guī)則（Backward rule）。）。 雙向產(chǎn)生式系統(tǒng)雙向產(chǎn)生式系統(tǒng)這種系統(tǒng)以雙向推理方式（正、逆向同時進(jìn)行）去求這種系統(tǒng)以雙向推理方式（正、

29、逆向同時進(jìn)行）去求解問題。雙向系統(tǒng)的綜合數(shù)據(jù)庫必須有兩套數(shù)據(jù)結(jié)構(gòu)，分別描述從初始狀態(tài)解問題。雙向系統(tǒng)的綜合數(shù)據(jù)庫必須有兩套數(shù)據(jù)結(jié)構(gòu)，分別描述從初始狀態(tài)出發(fā)推得的中間狀態(tài)出發(fā)推得的中間狀態(tài)正向狀態(tài)，和從目標(biāo)狀態(tài)出發(fā)推得的中間狀態(tài)正向狀態(tài)，和從目標(biāo)狀態(tài)出發(fā)推得的中間狀態(tài)逆向狀態(tài)。換言之，綜合數(shù)據(jù)庫逆向狀態(tài)。換言之，綜合數(shù)據(jù)庫 = 正向狀態(tài)描述正向狀態(tài)描述 + 逆向狀態(tài)描述，以便于逆向狀態(tài)描述，以便于F、B規(guī)則分別作用于不同的狀態(tài)描述。規(guī)則分別作用于不同的狀態(tài)描述。產(chǎn)生式系統(tǒng)的分類產(chǎn)生式系統(tǒng)的分類1717正向推理正向推理n從一組表示事實的謂詞或命題出發(fā)，使用一組從一組表示事實的謂詞或命題出發(fā)，使用一

30、組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立成立例：設(shè)有下列規(guī)則集合例：設(shè)有下列規(guī)則集合R1R3： R1：P1P2 R2：P2P3 R3：P3P4P2P3P1已知規(guī)則1規(guī)則2規(guī)則3P4推出1818逆向推理逆向推理n從表示目標(biāo)的謂詞或命題出發(fā)，使用一從表示目標(biāo)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實謂詞或命題成立，組產(chǎn)生式規(guī)則證明事實謂詞或命題成立，即首先提出一批假設(shè)目標(biāo)即首先提出一批假設(shè)目標(biāo)n以上述三條規(guī)則以上述三條規(guī)則R1R3，逆向推理過程，逆向推理過程如圖所示：如圖所示：P2P3P1事實規(guī)則1規(guī)則2規(guī)則3P4推出假設(shè)假設(shè)1919正、逆向推理比較

31、正、逆向推理比較 項項 目目 正向推理正向推理逆向推理逆向推理驅(qū)動方式驅(qū)動方式數(shù)據(jù)驅(qū)動數(shù)據(jù)驅(qū)動目標(biāo)驅(qū)動目標(biāo)驅(qū)動推理方法推理方法從一組數(shù)據(jù)出發(fā)向前推導(dǎo)結(jié)論從一組數(shù)據(jù)出發(fā)向前推導(dǎo)結(jié)論從可能的解出發(fā)向后推理驗證解答從可能的解出發(fā)向后推理驗證解答啟動方法啟動方法從一個事件啟動從一個事件啟動由詢問關(guān)于目標(biāo)狀態(tài)的一個問題啟動由詢問關(guān)于目標(biāo)狀態(tài)的一個問題啟動透明程度透明程度不能解釋其推理過程不能解釋其推理過程可解釋其推理過程可解釋其推理過程推理方向推理方向由底向上推理由底向上推理由頂向下推理由頂向下推理典型系統(tǒng)典型系統(tǒng)CLIPS，OPSPROLOG2020 雙向產(chǎn)生式系統(tǒng)雙向產(chǎn)生式系統(tǒng)這種系統(tǒng)以雙向推理方式

32、（正、逆向同時進(jìn)行）去求解問這種系統(tǒng)以雙向推理方式（正、逆向同時進(jìn)行）去求解問題。雙向系統(tǒng)的綜合數(shù)據(jù)庫必須有兩套數(shù)據(jù)結(jié)構(gòu)，分別描述從初始狀態(tài)出發(fā)題。雙向系統(tǒng)的綜合數(shù)據(jù)庫必須有兩套數(shù)據(jù)結(jié)構(gòu)，分別描述從初始狀態(tài)出發(fā)推得的中間狀態(tài)推得的中間狀態(tài)正向狀態(tài)，和從目標(biāo)狀態(tài)出發(fā)推得的中間狀態(tài)正向狀態(tài)，和從目標(biāo)狀態(tài)出發(fā)推得的中間狀態(tài)逆向逆向狀態(tài)。換言之，綜合數(shù)據(jù)庫狀態(tài)。換言之，綜合數(shù)據(jù)庫 = 正向狀態(tài)描述正向狀態(tài)描述 + 逆向狀態(tài)描述，以便于逆向狀態(tài)描述，以便于F、B規(guī)規(guī)則分別作用于不同的狀態(tài)描述。則分別作用于不同的狀態(tài)描述。 推理方向的選取推理方向的選取取決于問題的特征：取決于問題的特征： * 推理的分支因

33、素推理的分支因素每個識別每個識別-行動循環(huán)激活的規(guī)則數(shù)，行動循環(huán)激活的規(guī)則數(shù)， - 規(guī)則的激活檢查和啟發(fā)式評價的工作量。規(guī)則的激活檢查和啟發(fā)式評價的工作量。 * 雙向推理的不相交雙向推理的不相交問題本身的復(fù)雜性和關(guān)于規(guī)則選用的啟問題本身的復(fù)雜性和關(guān)于規(guī)則選用的啟 發(fā)式知識往往不完善發(fā)式知識往往不完善 2121 人的問題求解行為更像是一個人的問題求解行為更像是一個解答識別解答識別過程而非過程而非解答搜索解答搜索過程過程 識別解答或部分解答依賴于應(yīng)用領(lǐng)域特有的知識，識別解答或部分解答依賴于應(yīng)用領(lǐng)域特有的知識， 符號推理則成為基于知識來求解問題的主要手段。符號推理則成為基于知識來求解問題的主要手段。

34、 符號推理的重要方式是演繹推理符號推理的重要方式是演繹推理 它的基礎(chǔ)為謂詞演算它的基礎(chǔ)為謂詞演算一種一種形式語言形式語言 將各種陳述性（說明性）的描述以將各種陳述性（說明性）的描述以形式化形式化的方式表示，以便對它們的方式表示，以便對它們 作處理。作處理。 謂詞演算謂詞演算人工智能系統(tǒng)最常用的知識表示方法，人工智能系統(tǒng)最常用的知識表示方法， 廣泛地應(yīng)用于各種人工智能系統(tǒng)的設(shè)計。廣泛地應(yīng)用于各種人工智能系統(tǒng)的設(shè)計。 謂詞演算（或更廣義地，形式邏輯）是人工智能研究的重要基礎(chǔ)之一。謂詞演算（或更廣義地，形式邏輯）是人工智能研究的重要基礎(chǔ)之一。 主要內(nèi)容：主要內(nèi)容： 謂詞演算謂詞演算 H H域和海伯倫

35、定理域和海伯倫定理 歸結(jié)原理歸結(jié)原理 歸結(jié)反演歸結(jié)反演 基于歸結(jié)的演繹推理基于歸結(jié)的演繹推理 2222復(fù)合語句的真值表復(fù)合語句的真值表P Q PQPQP=Q PPQTTTTTFTFTTFTTFTFTFFFFFFFFTTT2323合適公式合適公式 用歸納法給出用歸納法給出合適公式合適公式的遞歸定義：的遞歸定義： 1. 1.原子謂詞公式是合適公式。原子謂詞公式是合適公式。 2.2.若若A A為合式公式，則為合式公式，則 A A也是一個合式公式。也是一個合式公式。 3.3.若若A A和和B B都是合式公式，則（都是合式公式，則（ABAB），（），（ABAB），（），（A AB B）和（和（A AB

36、B）也都是合適公式。）也都是合適公式。 4.4.若若A A是合式公式，是合式公式，x x為為A A中的自由變元，則（中的自由變元，則（ x x）A A和（和（ x x）A A都是合適公式。都是合適公式。 只有按上述（1）至（4）求得的那些公式，才是合適公式。 連詞優(yōu)先級別是連詞優(yōu)先級別是 ，、，、，但可通過括號改變優(yōu)先級。但可通過括號改變優(yōu)先級。 形式化表示符號推理所需的知識形式化表示符號推理所需的知識* * 所有人都喜歡一種游戲所有人都喜歡一種游戲* * （ x）（）（ y）Person(x) Game(y) Like(x,y) 24242 2）合適公式的解釋合適公式的解釋 命題解釋命題解釋

37、給命題中包含的各個原子公式指派真值（給命題中包含的各個原子公式指派真值（T或或F） 求出命題的真值（求出命題的真值（T T或或F F）依據(jù)連接原子公式的連詞的作用依據(jù)連接原子公式的連詞的作用 謂詞邏輯謂詞邏輯涉及變量和函數(shù)，不可能直接給原子公式指派真值涉及變量和函數(shù)，不可能直接給原子公式指派真值 定義一個擬觀察個體的定義一個擬觀察個體的可能論域可能論域， 確定原子公式中變量項和函數(shù)項在論域中的取值，確定原子公式中變量項和函數(shù)項在論域中的取值， 給原子公式指派真值。給原子公式指派真值。 例子例子合適公式（合適公式（ x x）（）（ y y）P(x) P(x) Q(f(x),y) Q(f(x),y

38、)的一個解釋的一個解釋 隨意隨意設(shè)定一個論域設(shè)定一個論域D=1D=1，22 對于對于x x的每個取值，可以指派的每個取值，可以指派f(1)=2, f(2)=2, P(1)=T, f(1)=2, f(2)=2, P(1)=T, P(2)=T P(2)=T； 對于對于f(x)f(x)和和y y的每個取值組合（只有的每個取值組合（只有2 2個：個：2 2，1 1； 2 2，2 2）指）指 派派Q(2,1)=T, Q(2,2)=FQ(2,1)=T, Q(2,2)=F。 這些指派就確定了該合適公式的一個解釋。這些指派就確定了該合適公式的一個解釋。 在這個解釋下，合適公式有真值在這個解釋下，合適公式有真值

39、T T。 2525合適公式的性質(zhì)合適公式的性質(zhì)合適公式等價關(guān)系合適公式等價關(guān)系: : 1. 1.否定之否定否定之否定 ( ( P) P) P P 2.2.蘊(yùn)涵式轉(zhuǎn)化蘊(yùn)涵式轉(zhuǎn)化 P PQQ PQPQ 3.3.狄摩根定律狄摩根定律 (PQ(PQ) ) PP QQ (PQ(PQ) ) PP QQ4.4.分配律分配律 P(QRP(QR) ) (PQ)(PR(PQ)(PR）P(QRP(QR) ) (PQ)(PR (PQ)(PR) )5. 5. 交換律交換律 PQPQ QP QPPQPQ QP QP 2626合適公式的性質(zhì)合適公式的性質(zhì)6. 6. 結(jié)合律結(jié)合律 (PQ)R(PQ)R P(QR P(QR）

40、(PQ)R(PQ)R P P（QRQR） 7. 7. 逆否律逆否律 P PQQ Q Q P P 8. 8. 量詞否定量詞否定 ( ( x)P(x) x)P(x) ( ( x x)( )( P(x)P(x) ( ( x x)P(x) )P(x) （ x)(x)( P(x)P(x)2727合適公式的性質(zhì)合適公式的性質(zhì)9.9.量詞分配量詞分配 ( ( x)P(x)Qx)P(x)Q(x) (x) ( ( x x)P(x)()P(x)( x x)Q(x)Q(x)( ( x x）P(x)QP(x)Q(x) (x) （ x x）P(x)(P(x)( x x)Q(x)Q(x)10.10.約束變量的虛元性約束變

41、量的虛元性( ( x x)P(x) )P(x) ( ( y y)P(y)P(y) ( ( x x)P(x) )P(x) ( ( y y)P(y)P(y)2828合適公式的標(biāo)準(zhǔn)化合適公式的標(biāo)準(zhǔn)化1)1) 標(biāo)準(zhǔn)化需求標(biāo)準(zhǔn)化需求 常見的基于謂詞演算的推理有常見的基于謂詞演算的推理有歸結(jié)反演歸結(jié)反演和和規(guī)則演繹規(guī)則演繹。 要求以所謂的要求以所謂的量詞前束范式量詞前束范式來表示合適公式，來表示合適公式， （Q Q1x11x1）（）（Q Q2x22x2）（Q Qkxkkxk ）M M M M稱為母式，不包括任何量詞，稱為母式，不包括任何量詞， 量詞前束，量詞前束，Q Qi i 可以是量詞符號可以是量詞符號

42、 或或 ，x xi i 是量詞的約束變量。是量詞的約束變量。 歸結(jié)反演要求母式歸結(jié)反演要求母式M M標(biāo)準(zhǔn)化為合取范式：標(biāo)準(zhǔn)化為合取范式： M = WM = W1 1WW2 2WWn n W Wi i = L = Li1i1LLi2i2LLimim (i=1,2, (i=1,2,n),n)L Lijij= = P Pijij | | P Pijij (j=1,2, (j=1,2,m),m)L Lijij稱為文字（稱為文字（LiteralLiteral）, ,只能是原子謂詞公式只能是原子謂詞公式P Pijij或其取反?；蚱淙》?。與合取范式對偶的是析取范式，定義如下：與合取范式對偶的是析取范式，定義

43、如下： M = WM = W1 1WW2 2WWn n W Wi i = L = Li1i1LLi2i2LLimim (i=1,2, (i=1,2,n) ,n) L Lijij= = P Pijij | | P Pijij (j=1,2, (j=1,2,m),m)2929前束范式前束范式例1：變公式（：變公式（ x）P（x）=（ x）Q（x）為前束范式為前束范式（ x）P（x）（ x）Q（x）（ x）（）（P（x）（ x）Q（x）（ x）（）（P（x）Q（x）為前束范式）為前束范式3030前束范式前束范式例例2：( x)( y)( z)(P(x，z)P(y，z)=( u)Q(x，y，u)x)(

44、 y)( z)(P(x，z)P(y，z)( u)Q(x，y，u)( x)( y)( z)( P(x，z)P(y，z)( u)Q(x，y，u)x)( y)( z)( u)( P(x，z)P(y，z)Q(x，y，u)3131史柯倫標(biāo)準(zhǔn)型及其構(gòu)造思想史柯倫標(biāo)準(zhǔn)型及其構(gòu)造思想n史柯倫（Skolem）標(biāo)準(zhǔn)型：海布蘭得：海布蘭得（Herbrand）定理是歸結(jié)原理的基礎(chǔ)。海）定理是歸結(jié)原理的基礎(chǔ)。海布蘭得定理證明的步驟實際上是反演法，布蘭得定理證明的步驟實際上是反演法，即不是證明一個公式是永真，而是證明該即不是證明一個公式是永真，而是證明該公式是否是公式是否是永假永假的。反演法利用了一個標(biāo)的。反演法利用了一

45、個標(biāo)準(zhǔn)型，這個標(biāo)準(zhǔn)型就是準(zhǔn)型，這個標(biāo)準(zhǔn)型就是Skolem標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)型。3232一階邏輯公式所對應(yīng)的一階邏輯公式所對應(yīng)的Skolem標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型基于如下思想來構(gòu)造：基于如下思想來構(gòu)造：1.一階邏輯的一個公式被變換為前束范式。其中前一階邏輯的一個公式被變換為前束范式。其中前束是一個束是一個存在量詞存在量詞或或全稱量詞全稱量詞的序列，母式中不的序列，母式中不在含有量詞。在含有量詞。 2.因為母式不含量詞，所以可以變換為因為母式不含量詞，所以可以變換為合取合取范式。范式。 3.通過使用通過使用Skolem函數(shù)，可以在前束中將存在量詞函數(shù)，可以在前束中將存在量詞消去，而不影響公式的永假性。消去，而不影

46、響公式的永假性。 3333Skolem標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型n通過變換通過變換消去存在量詞消去存在量詞所得到的公式稱為所得到的公式稱為Skolem標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型，而拿來代替存在量詞的變，而拿來代替存在量詞的變量的函數(shù)量的函數(shù)稱稱Skolem函數(shù)函數(shù)。無。無參參Skolem函函數(shù)有時數(shù)有時稱稱Skolem常量常量。 從一階邏輯的公式變換到從一階邏輯的公式變換到Skolem標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型不是不是等值變換，因為等值變換，因為Skolem標(biāo)準(zhǔn)型與原公標(biāo)準(zhǔn)型與原公式不等值。但它們保持永假性。式不等值。但它們保持永假性。 34342.2.合取范式的標(biāo)準(zhǔn)化過程合取范式的標(biāo)準(zhǔn)化過程n將合適公式化簡為標(biāo)準(zhǔn)的合取范式將合適公式

47、化簡為標(biāo)準(zhǔn)的合取范式, , 實際上就實際上就是應(yīng)用合適公式性質(zhì)將公式逐步轉(zhuǎn)化的過程是應(yīng)用合適公式性質(zhì)將公式逐步轉(zhuǎn)化的過程1. 消去蘊(yùn)涵符號消去蘊(yùn)涵符號 只應(yīng)用只應(yīng)用和和符號，以符號，以AB替換替換A=B。 2. 減少否定符號的轄域減少否定符號的轄域(內(nèi)移否定符號內(nèi)移否定符號) 每個否定符號每個否定符號最多只用到一個為此符號上，并反復(fù)最多只用到一個為此符號上，并反復(fù)應(yīng)用狄摩根律。如應(yīng)用狄摩根律。如以以AB 代替代替（AB）以以AB 代替代替（AB）以以A代替代替（A）以以( x)A代替代替（ x）A以以x)A代替代替（ x）A 35353. 對變量標(biāo)準(zhǔn)化對變量標(biāo)準(zhǔn)化(變量換名變量換名) 在任一量

48、詞轄域內(nèi)，受該量詞約束的變量為一在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元（虛構(gòu)變量），啞元（虛構(gòu)變量），它可以在該轄域內(nèi)處處統(tǒng)它可以在該轄域內(nèi)處處統(tǒng)一的被另一個沒有出現(xiàn)過的任意變量所代替一的被另一個沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。合適公式中變量的標(biāo)準(zhǔn)而不改變公式的真值。合適公式中變量的標(biāo)準(zhǔn)化意味著對啞元改名以保證每個化意味著對啞元改名以保證每個 量詞有其自己量詞有其自己唯一的啞元。如，把唯一的啞元。如，把( x)p(x)=（ x）Q（x）標(biāo)準(zhǔn)化而得到（標(biāo)準(zhǔn)化而得到（ x）p(x)=（ y）Q（y） 36364.消去消去存在量詞存在量詞(分分2種情況討論種情況討論) 在公式（

49、在公式（ y）（ x）P（x，y）中，存中，存在量詞是在量詞是在全稱量詞的轄域內(nèi)在全稱量詞的轄域內(nèi)，我們允許所，我們允許所存在的存在的x可能依賴于可能依賴于y值。值。 令這種依賴關(guān)系由令這種依賴關(guān)系由某個假設(shè)的函數(shù)某個假設(shè)的函數(shù)g（y）所定義，它把每個）所定義，它把每個y值值映射到存在的那個映射到存在的那個x。這種函數(shù)就是。這種函數(shù)就是Skolem函數(shù)函數(shù)。如果。如果用用Skolem函數(shù)代替存在的函數(shù)代替存在的x，我，我們就可以消去全部存在量詞們就可以消去全部存在量詞 （ y）Pg（y），），ySkolem函數(shù)的變量是由那些全稱量詞所約束函數(shù)的變量是由那些全稱量詞所約束的全稱量詞量化變量，這些

50、全稱量詞的轄域的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。包括要被消去的存在量詞的轄域在內(nèi)。Skolem函數(shù)所使用的函數(shù)符號必須是函數(shù)所使用的函數(shù)符號必須是新的新的，即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號。即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號。3737 如果要消去的存在量詞不在任何一個全稱量詞的如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi)，那么我們就用不含變量的轄域內(nèi)，那么我們就用不含變量的Skolem函數(shù)函數(shù)即即Skolem常量。例如，（常量。例如，（ x）P（x）化為）化為P（A），），其中常量符號其中常量符號A用來表示我們知道的存在實體。用來表示我們知道的存

51、在實體。A必須是個新的常量符號，它未曾在公式其他地方必須是個新的常量符號，它未曾在公式其他地方使用過。使用過。 5. 化為前束形化為前束形(全稱量詞前束化全稱量詞前束化)現(xiàn)在已不存在任何存在量詞，而且每個全稱量詞現(xiàn)在已不存在任何存在量詞，而且每個全稱量詞都有自己的變量，把所有全稱量詞移到公式的左都有自己的變量，把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括邊，并使每個量詞的轄域包括這個量詞后面公式這個量詞后面公式的整個部分的整個部分。所得公式就是前束形。前束形公式。所得公式就是前束形。前束形公式由全稱量詞串組成的前綴和不含量詞的母式組成。由全稱量詞串組成的前綴和不含量詞的母式組成。383

52、86. 把母式化為合取范式把母式化為合取范式 任何母式都可以寫成由一些謂詞公式和謂詞任何母式都可以寫成由一些謂詞公式和謂詞公式的否定的析取的有限集組成的合取。這種公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。反復(fù)應(yīng)用分配率，如把母式叫做合取范式。反復(fù)應(yīng)用分配率，如把ABC化為化為 ABC 7. 消去全稱量詞消去全稱量詞 所有余下的量詞均被全稱量詞量化了。全稱所有余下的量詞均被全稱量詞量化了。全稱量詞的次序也不重要了。因此，我們可以消去量詞的次序也不重要了。因此，我們可以消去全部全稱量詞全部全稱量詞。 注注:6和和7的次序可以顛倒的次序可以顛倒. 3939 定理的自動證明一般表示形式

53、為：定理的自動證明一般表示形式為：F1, F2,F1, F2, ,Fn ,Fn|= W|= W F1, F2,F1, F2, ,Fn ,Fn都是合適公式，都是合適公式， 公式間公式間隱含合取關(guān)系隱含合取關(guān)系，構(gòu)成一個公式集（也稱，構(gòu)成一個公式集（也稱公理集公理集或或事實集事實集），）， W W是待證明的一個合適公式（也稱為是待證明的一個合適公式（也稱為定理定理或目標(biāo)公式）或目標(biāo)公式）。 證明的方法可分二大類：證明的方法可分二大類： 演繹法演繹法直接證明直接證明F1F2F1F2FnFn W W為永真；從而，當(dāng)公式集為真時，為永真；從而，當(dāng)公式集為真時，定理定理W W成立。成立。 反證法反證法間接

54、證明間接證明 (F1F2(F1F2FnFn W) W)為永假。即證明為永假。即證明 F1F2F1F2FnFn W W的永假性，即的永假性，即F1, F2,F1, F2, ,Fn ,Fn W W 是一個矛盾集。是一個矛盾集。 海伯倫提出的海伯倫提出的H H域（海伯倫域）和海伯倫定理域（海伯倫域）和海伯倫定理為自動定理證明為自動定理證明奠定了理論基礎(chǔ)：奠定了理論基礎(chǔ)： 將合適公式標(biāo)準(zhǔn)化為將合適公式標(biāo)準(zhǔn)化為子句集子句集 引入引入H H域（即海伯倫域），從理論上給出了證明子句集域（即海伯倫域），從理論上給出了證明子句集( (從而合適公式從而合適公式) )永永假假( (即不可滿足即不可滿足) )的可行性

55、及方法。的可行性及方法。 魯賓遜提出的魯賓遜提出的歸結(jié)原理歸結(jié)原理使機(jī)器定理證明成為可能。使機(jī)器定理證明成為可能。 歸結(jié)演繹方法歸結(jié)演繹方法40401 1）子句和子句集）子句和子句集 子句子句僅由文字的僅由文字的析取析取構(gòu)成的合適公式（構(gòu)成的合適公式（文字文字：原子謂詞公式或：原子謂詞公式或其取反）。其取反）。 合取范式合取范式子句的合取子句的合取。 子句集子句集指示合取范式，子句間隱含合取關(guān)系指示合取范式，子句間隱含合取關(guān)系( (和合取范式一一對應(yīng)和合取范式一一對應(yīng)) )。 變量換名變量換名( (目的目的: :消除子句間不必要的交互作用消除子句間不必要的交互作用, ,使各子句都使用同使各子句

56、都使用同的變量的變量) ) P(A)P(y) Q(A,z)P(z,g(z) P(f(A,y) Q(A,z)P(z,g(z) 變成變成 P(A)P(y1) Q(A, z1 1)P)P(z(z1 1,g(z,g(z1 1) P(f(A, y2 2) Q(A, z2 2)P)P(z(z2 2,g(z,g(z2 2)子句子句4141 重要性質(zhì)重要性質(zhì)一個合適公式一個合適公式F F化簡為標(biāo)準(zhǔn)化的子句集化簡為標(biāo)準(zhǔn)化的子句集S S時，時， S S的不可的不可滿足滿足( (永假永假) )成為成為F F永假的充分必要條件永假的充分必要條件。 F F和和S S并非等價并非等價F F的化簡過程中，為消除存在量詞而引

57、入了的化簡過程中，為消除存在量詞而引入了SklemSklem函函數(shù)，使子句集數(shù)，使子句集S S只是只是F F的一個特例。的一個特例。 可以證明可以證明F F和和S S在永假性上等價在永假性上等價42421.消去蘊(yùn)涵符號2.減少否定符號的轄域3.對變量標(biāo)準(zhǔn)化4.消去存在量詞5.化為前束形6.把母式化為合取范式7.消去全稱量詞8.消去連詞符號9.更換變量名稱1.消去蘊(yùn)涵符號消去蘊(yùn)涵符號只應(yīng)用和符號，以AB替換A=B。2.減少否定符號的轄域減少否定符號的轄域 每個否定符號最多只用到一個謂詞符號上，并反復(fù)應(yīng)用狄摩根律。如以AB 代替（AB）以AB 代替（AB）以A代替（A）以(x) A代替（x）A以x

58、) A代替（x）A 3.對變量標(biāo)準(zhǔn)化對變量標(biāo)準(zhǔn)化 在任一量詞轄域內(nèi)，受該量詞約束的變量為 一 啞元（虛構(gòu)變量），它可以在該轄域內(nèi)處處統(tǒng)一的被另一個沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。合適公式中變量的標(biāo)準(zhǔn)化意味著對啞元改名以保證每個 量詞有其自己唯一的啞元。如，把(x)p(x)=(x)Q(x)標(biāo)準(zhǔn)化而得到（x）p(x)=(y)Q(y) 子句：文字的析取組成的公式。 如：（PQR）43431.消去蘊(yùn)涵符號2.減少否定符號的轄域3.對變量標(biāo)準(zhǔn)化4.消去存在量詞5.化為前束形6.把母式化為合取范式7.消去全稱量詞8.消去連詞符號9.更換變量名稱4.消去存在量詞消去存在量詞 在公式（y）（x

59、）P（x，y）中，存在量詞是在全稱量詞的轄域內(nèi)，我們允許所存在的x可能依賴于y值。 令這種依賴關(guān)系明顯地由函數(shù)g（y）所定義，它把每個y值映射到存在的那個x。 這種函數(shù)就是Skolem函數(shù)。如果用Skolem函數(shù)代替存在的x，我們就可以消去全部存在量詞 （y）Pg（y），ySkolem函數(shù)的變量是由那些全稱量詞所約束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。Skolem函數(shù)所使用的函數(shù)符號必須是新的。 如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi)，那么我們就用不含變量的Skolem函數(shù)即常量。例如，（x）P（x）化為P（A），其中常量符號A用來表示我們知道的存

60、在實體。44441.消去蘊(yùn)涵符號2.減少否定符號的轄域3.對變量標(biāo)準(zhǔn)化4.消去存在量詞5.化為前束形6.把母式化為合取范式7.消去全稱量詞8.消去連詞符號9.更換變量名稱5.化為前束形化為前束形現(xiàn)在已不存在任何存在量詞，而且每個全稱量詞都有自己的變量，把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱前束形。前束形公式由全稱量詞串組成的前綴和不含量詞的母式組成。 (x)(y)P(x) P(y)6.把母式化為合取范式把母式化為合取范式 任何母式都可以寫成由一些謂詞公式和謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。反復(fù)應(yīng)用分配率，如把ABC