人工智能期末復(fù)習(xí)

1、1.人工智能（學(xué)科）：Artificial Intelligence是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支。它的近期目標(biāo)在于研究用機(jī)器來(lái)模仿和執(zhí)行人腦的某些智能功能，并開(kāi)發(fā)相關(guān)的理論和技術(shù)。在人工智能中，重點(diǎn)關(guān)注兩個(gè)方面的內(nèi)容：?jiǎn)栴}的表示（知識(shí)的表示）：即要找到問(wèn)題的一種合適的表示方法在人工智能中，我們要涉及到：狀態(tài)空間法、問(wèn)題歸約法、謂詞邏輯法、樣本向量法問(wèn)題的求解：從問(wèn)題表示方法出發(fā)，找到一個(gè)合理的辦法來(lái)求解在人工智能中，常有的方法有：搜索法、推理法、計(jì)算方法2. 狀態(tài)空間法：從某一個(gè)初始狀態(tài)開(kāi)始，每次施加一個(gè)操作符，遞增地建立操作符序列，直到達(dá)到目標(biāo)狀態(tài)為止人工智能中，一種

2、最基本的求解方法就是試探搜索法，即，通過(guò)在某個(gè)可能的解空間（例如，所有可能的走法）中尋找一個(gè)解。這種基于解空間的問(wèn)題表示和求解方法就是狀態(tài)空間法，其基礎(chǔ)是狀態(tài)和算符（算子）狀態(tài)空間法表示問(wèn)題的關(guān)鍵：狀態(tài)與操作符狀態(tài)：為了描述某一類(lèi)不同事物間的差別而引入的一組最少變量的有序集合算符（操作符）：使問(wèn)題從一個(gè)狀態(tài)變換到另一狀態(tài)的手段用狀態(tài)空間法表達(dá)出原始問(wèn)題后，欲解問(wèn)題變成為：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的某一個(gè)操作符序列狀態(tài)空間法的求解過(guò)程：用有向圖來(lái)表示圖是由節(jié)點(diǎn)（不一定是有限個(gè)的節(jié)點(diǎn)）的集合構(gòu)成的注意：在圖論中，圖的定義中還包括邊的集合無(wú)向圖：一對(duì)節(jié)點(diǎn)可能互為后裔，邊用線(xiàn)段來(lái)表示有向圖：一對(duì)節(jié)點(diǎn)用

3、弧線(xiàn)連接起來(lái)，并且從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)對(duì)應(yīng)關(guān)系：當(dāng)用有向圖來(lái)表示狀態(tài)空間法時(shí)，對(duì)應(yīng)關(guān)系：圖中的一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于某一個(gè)狀態(tài)圖中的一個(gè)有向弧對(duì)應(yīng)于某一個(gè)算符狀態(tài)空間法的解：從初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列 圖中的解：從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑問(wèn)題：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的某個(gè)操作符序列轉(zhuǎn)化為尋找圖中初始節(jié)點(diǎn)（對(duì)應(yīng)初始狀態(tài)）到目標(biāo)節(jié)點(diǎn)（對(duì)應(yīng)于目標(biāo)狀態(tài)）的一條路徑求解思路：邊擴(kuò)展節(jié)點(diǎn)邊找解的搜索思想問(wèn)題的狀態(tài)空間：一個(gè)表示問(wèn)題全部可能狀態(tài)及其關(guān)系的圖，它包含了三個(gè)集合： 所有可能的問(wèn)題初始狀態(tài)集合S 操作符集合F 目標(biāo)狀態(tài)集合G狀態(tài)空間記作三元狀態(tài)（S, F, G）3. 代價(jià)g(n) ：從起始

4、節(jié)點(diǎn) S 到某一節(jié)點(diǎn) n 的路徑的實(shí)際代價(jià)估值函數(shù) f (n) ：從起始節(jié)點(diǎn)S、通過(guò)節(jié)點(diǎn)n、到達(dá)目標(biāo)節(jié)點(diǎn)G的最小代價(jià)的一個(gè)估計(jì)值 f ( n ) = g ( n ) + h ( n )利用圖論的技術(shù)，我們要解決兩個(gè)問(wèn)題：第一、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑。對(duì)應(yīng)于尋找初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列（能夠解決問(wèn)題）第二、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條代價(jià)最小的路徑。對(duì)應(yīng)于尋找將初始狀態(tài)變換到目標(biāo)狀態(tài)所用操作符代價(jià)之和最小的操作符序列（更好地解決問(wèn)題）4. 圖的搜索技術(shù)分：盲目搜索技術(shù)（寬度、深度、代價(jià)優(yōu)先搜索技術(shù)）啟發(fā)式搜索技術(shù)（有序搜索算法）差別：選取待擴(kuò)展節(jié)點(diǎn)的規(guī)則不同，并且可以O(shè)PEN表的

5、不同數(shù)據(jù)結(jié)構(gòu)來(lái)體現(xiàn)算法有解的終止條件不同圖搜索中的兩個(gè)重要記號(hào)（符號(hào)）：OPEN 表：存放待擴(kuò)展的節(jié)點(diǎn)CLOSED 表：存放已擴(kuò)展的節(jié)點(diǎn)注意：在與或樹(shù)搜索中也要用到這兩張表盲目搜索技術(shù)盲目搜索是指無(wú)問(wèn)題先驗(yàn)信息的搜索技術(shù)特點(diǎn)：OPEN表中節(jié)點(diǎn)的排列是人為規(guī)定的；一般只適合于求解比較簡(jiǎn)單的一些問(wèn)題寬度優(yōu)先：先擴(kuò)展出來(lái)的節(jié)點(diǎn)優(yōu)先（OPEN 為隊(duì)列），后繼節(jié)點(diǎn)有目標(biāo)節(jié)點(diǎn)結(jié)束OPEN 表是存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)上來(lái)說(shuō)，它是一個(gè)先進(jìn)先出的隊(duì)列CLOSED 表是存放已被擴(kuò)展過(guò)的節(jié)點(diǎn)（包括有后繼節(jié)點(diǎn)的非端節(jié)點(diǎn)和無(wú)后繼節(jié)點(diǎn)的端節(jié)點(diǎn)）,可以看成只進(jìn)不出的隊(duì)列深度優(yōu)先：后者擴(kuò)展出來(lái)的節(jié)點(diǎn)優(yōu)先（OPEN 為堆

6、棧） ，且有深度限制，后繼節(jié)點(diǎn)有目標(biāo)節(jié)點(diǎn)結(jié)束OPEN表是一個(gè)堆棧，后進(jìn)先出代價(jià)優(yōu)先（等代價(jià)）：到起始節(jié)點(diǎn)代價(jià)小的節(jié)點(diǎn)優(yōu)先（ OPEN 為線(xiàn)性表），具有最小代價(jià)的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)結(jié)束三種盲目搜索技術(shù)的比較主要差別：在于挑選要擴(kuò)展節(jié)點(diǎn)的規(guī)則不同寬度優(yōu)先搜索技術(shù)：先擴(kuò)展出來(lái)的節(jié)點(diǎn)隨后先擴(kuò)展，OPEN表是隊(duì)列深度優(yōu)先搜索技術(shù)：后擴(kuò)展出來(lái)的節(jié)點(diǎn)隨后先擴(kuò)展，OPEN表是堆棧等代價(jià)搜索技術(shù)：選取OPEN表中代價(jià)最小的節(jié)點(diǎn)先擴(kuò)展，OPEN表是線(xiàn)性表（以局部代價(jià)的遞增順序排列）寬度和深度優(yōu)先搜索的缺點(diǎn)：擴(kuò)展節(jié)點(diǎn)的順序是人為規(guī)定的，要擴(kuò)展節(jié)點(diǎn)的數(shù)目可能非常大，占用大量的計(jì)算時(shí)間和內(nèi)存空間，使得搜索效率低等代價(jià)搜索

7、技術(shù)的 缺點(diǎn)選取已經(jīng)搜索到的代價(jià)最小的節(jié)點(diǎn)來(lái)擴(kuò)展，但是沒(méi)有考慮目標(biāo)狀態(tài)，不知道離目標(biāo)狀態(tài)還有多遠(yuǎn)，還需要付出多大的代價(jià)啟發(fā)式搜索技術(shù)有序算法：估價(jià)函數(shù)值小的節(jié)點(diǎn)優(yōu)先有解的結(jié)束條件：具有最小估價(jià)函數(shù)值的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)啟發(fā)式搜索方法：利用啟發(fā)信息的搜索方法有序搜索：在搜索過(guò)程總是選擇“ 最有希望 ”的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展節(jié)點(diǎn)的搜索技術(shù)在搜索過(guò)程中，OPEN表中節(jié)點(diǎn)按照其估價(jià)函數(shù)值以遞增順序排列，選擇OPEN表中具有最小估價(jià)函數(shù)值的節(jié)點(diǎn)作為下一個(gè)待擴(kuò)展的節(jié)點(diǎn)，這種搜索方法稱(chēng)為有序搜索估價(jià)函數(shù)：用來(lái)估算節(jié)點(diǎn)“ 希望 ”程度的函數(shù)估價(jià)函數(shù)的基本特性：一般情況下，估計(jì)函數(shù)值越大，希望程度就越低根據(jù)搜索過(guò)程

8、、問(wèn)題的啟發(fā)信息來(lái)定義的，對(duì)搜索效率會(huì)產(chǎn)生較大的影響節(jié)點(diǎn) n 的估價(jià)函數(shù) f ( n ) 定義為從初始節(jié)點(diǎn)、經(jīng)過(guò) n 、到達(dá)目標(biāo)節(jié)點(diǎn)的路徑的最小代價(jià)的估計(jì)值，即 f ( n ) = g ( n ) + h ( n )g ( n ) 是從初始節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn) n 的實(shí)際代價(jià)h ( n ) 是從節(jié)點(diǎn) n 到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià)h ( n ) 體現(xiàn)出搜索過(guò)程中采用的啟發(fā)式信息（背景知識(shí)），稱(chēng)之為啟發(fā)函數(shù)g ( n ) 所占的比重越大，越趨向于寬度優(yōu)先或等代價(jià)搜索；反之，h ( n ) 的比重越大，表示啟發(fā)性能就越強(qiáng)例：八數(shù)碼問(wèn)題的估價(jià)函數(shù) f ( n )= g ( n ) + h ( n )

9、g ( n ) 定義為搜索樹(shù)中 n 的深度h ( n ) 可以定義成不同形式（節(jié)點(diǎn) n 的狀態(tài)與目標(biāo)狀態(tài)之間數(shù)字不在位的個(gè)數(shù)（錯(cuò)放棋子的個(gè)數(shù)，不算空格）5.問(wèn)題歸約法、與或樹(shù)搜索技術(shù)問(wèn)題歸約法：從已知問(wèn)題的描述出發(fā)，通過(guò)一系列變換或分解將問(wèn)題最終變?yōu)橐粋€(gè)子問(wèn)題集合，這些子問(wèn)題的解可以直接得到，從而解決初始問(wèn)題問(wèn)題歸約法表示問(wèn)題的關(guān)鍵：原始問(wèn)題描述、本原問(wèn)題描述、操作符操作符：將問(wèn)題轉(zhuǎn)換或分解為子問(wèn)題的手段本原問(wèn)題：一組可以直接得出答案的簡(jiǎn)單問(wèn)題問(wèn)題歸約法可以用一個(gè)三元組（S, O, P）來(lái)表示，其中： S：原始問(wèn)題，即要解決的問(wèn)題 P：本原問(wèn)題集，其中的每一個(gè)問(wèn)題是不用證明的或自然成立的，例如

10、公理、已知事實(shí)等 O：操作算子集，用于將問(wèn)題化為子問(wèn)題問(wèn)題歸約法的基本思路是：應(yīng)用一系列算符將原始問(wèn)題的描述變換或分解成為子問(wèn)題的描述問(wèn)題的描述可以采用各種數(shù)據(jù)結(jié)構(gòu)，如表、樹(shù)、矢量、數(shù)組等與或圖的特例：所有節(jié)點(diǎn)都是或節(jié)點(diǎn)，這時(shí)就是一般的圖，即狀態(tài)空間法用到的圖除了起始節(jié)點(diǎn)外，所有節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，此時(shí)稱(chēng)為與或樹(shù)，問(wèn)題歸約法的求解過(guò)程：用與或圖來(lái)表示“或節(jié)點(diǎn)”有解的條件是：只要有一個(gè)后繼節(jié)點(diǎn)可解“或節(jié)點(diǎn)”無(wú)解的條件是：所有后繼節(jié)點(diǎn)無(wú)解“與節(jié)點(diǎn)”有解的條件是：所有后繼節(jié)點(diǎn)有解“與節(jié)點(diǎn)”無(wú)解的條件是：只要有一個(gè)后繼節(jié)點(diǎn)無(wú)解判斷節(jié)點(diǎn)是否可解的方法：終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)無(wú)后繼節(jié)點(diǎn)的非終葉節(jié)點(diǎn)是不可解節(jié)點(diǎn)

11、用倒推的方法來(lái)逐步判斷其他節(jié)點(diǎn)是否可解與或圖有解的條件是：起始節(jié)點(diǎn)（根節(jié)點(diǎn)）可解（通過(guò)倒推來(lái)判斷）與或圖的解圖：由最少可解節(jié)點(diǎn)所構(gòu)成的子圖，這些可解節(jié)點(diǎn)能夠使問(wèn)題的起始節(jié)點(diǎn)可解與或樹(shù)：與或圖的特例，除了根節(jié)點(diǎn)外，任何一個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)與或圖：除了起始節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)允許有多個(gè)父節(jié)點(diǎn)與或樹(shù)的搜索技術(shù)：寬度優(yōu)先：先擴(kuò)展出來(lái)的節(jié)點(diǎn)優(yōu)先（OPEN表是隊(duì)列）深度優(yōu)先：后擴(kuò)展出來(lái)的節(jié)點(diǎn)優(yōu)先（OPEN表是堆棧），且有深度限制圖、與或樹(shù)的寬度、深度優(yōu)先搜索算法之間的差別：圖搜索技術(shù)是找到目標(biāo)節(jié)點(diǎn)或無(wú)法擴(kuò)展而結(jié)束算法與或樹(shù)搜索技術(shù)是找到終葉節(jié)點(diǎn)后通過(guò)倒推來(lái)判斷起始節(jié)點(diǎn)是否可解而結(jié)束算法6.博弈問(wèn)題的表達(dá)、博

12、弈樹(shù)的搜索技術(shù)雙人博弈問(wèn)題的特殊之處：棋局：相當(dāng)于狀態(tài)空間法中的狀態(tài)走棋：相當(dāng)于問(wèn)題歸約法的節(jié)點(diǎn)擴(kuò)展（生成或節(jié)點(diǎn)(自己)、與節(jié)點(diǎn)（別人）博弈樹(shù)是一棵特殊的與或樹(shù)，其節(jié)點(diǎn)對(duì)應(yīng)棋局（相當(dāng)于狀態(tài)），與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)博弈的特點(diǎn)：雙方的智能活動(dòng)，任何一方都不能單獨(dú)控制博弈過(guò)程，而是由雙方輪流實(shí)施其控制對(duì)策的過(guò)程博弈問(wèn)題（求解過(guò)程）的表示：用博弈樹(shù)來(lái)表示，它是一種特殊的與或樹(shù)。節(jié)點(diǎn)代表博弈的格局（即棋局），相當(dāng)于狀態(tài)空間中的狀態(tài)，反映了博弈的信息， 并且與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)博弈樹(shù)搜索的極大極小過(guò)程分成：寬度優(yōu)先擴(kuò)展節(jié)點(diǎn)（深度必為偶數(shù)），并計(jì)算最底層端節(jié)點(diǎn)的靜態(tài)估計(jì)函數(shù)值用倒推的方法（自己下

13、的棋取大者，對(duì)手下的棋取小者）計(jì)算出其余各層節(jié)點(diǎn)的靜態(tài)估計(jì)函數(shù)值，最后決定走哪一步棋7.謂詞邏輯與推理數(shù)理邏輯（符號(hào)邏輯）是用數(shù)學(xué)方法研究形式邏輯的一個(gè)分支。它通過(guò)符號(hào)系統(tǒng)來(lái)表達(dá)客觀(guān)對(duì)象以及相關(guān)的邏輯推理。常用的是命題邏輯和謂詞邏輯數(shù)理邏輯的主要分支：邏輯演算(包括命題演算和謂詞演算)模型論證明論遞歸論公理化集合論數(shù)理邏輯和計(jì)算機(jī)科學(xué)有許多重合之處，兩者都屬于模擬人類(lèi)認(rèn)知機(jī)理的科學(xué)謂詞邏輯是數(shù)理邏輯的基本形式，是基于謂詞分析的一種形式化（數(shù)學(xué)）語(yǔ)言人工智能中的謂詞邏輯法是指用一階謂詞來(lái)描述問(wèn)題求解和定理證明（限于本課程）命題邏輯是研究命題及命題之間關(guān)系的符號(hào)邏輯系統(tǒng)。在命題邏輯中，表示單一意義

14、的命題，稱(chēng)之為原子命題。原子命題通過(guò) “聯(lián)結(jié)詞” 構(gòu)成 復(fù)合命題。五個(gè)聯(lián)結(jié)詞： “” 表示 “非”復(fù)合命題P為真，當(dāng)且僅當(dāng)P為假。 “” 表示 “合取”復(fù)合命題“PQ”為真，當(dāng)且僅當(dāng)P和Q都為真。 “” 表示 “析取”復(fù)合命題“PQ”為真，當(dāng)且僅當(dāng)P、Q兩者之一為真。 “” 表示 “蘊(yùn)含”復(fù)合命題“PQ”為假，當(dāng)且僅當(dāng)P為真且Q為假。 “” 表示 “等價(jià)” 復(fù)合命題“PQ”為真，當(dāng)且僅當(dāng)P、Q同時(shí)為真、或者同時(shí)為假。命題變?cè)河梅?hào)P、Q等表示的不具有固定、具體含義的命題。它可以表示具有“真”、“假”含義的各種命題。命題變?cè)梢岳寐?lián)結(jié)詞構(gòu)成所謂的合適公式。 合適公式的定義若P為原子命題，則P

15、為合適公式，稱(chēng)為原子公式。若P是合適公式，則P也是一個(gè)合適公式。若P和Q是合適公式，則PQ、 PQ 、PQ 、PQ都是合適公式。經(jīng)過(guò)有限次使用規(guī)則1、2、3，得到的由原子公式、聯(lián)結(jié)詞和園括號(hào)所組成的符號(hào)串，也是合適公式。對(duì)于合適公式，規(guī)定下列運(yùn)算優(yōu)先級(jí)： 邏輯聯(lián)結(jié)詞的運(yùn)算優(yōu)先次序?yàn)椋?、 、 同級(jí)聯(lián)結(jié)詞按出現(xiàn)順序優(yōu)先運(yùn)算謂詞演算1、語(yǔ)法與語(yǔ)義謂詞邏輯的基本組成部分謂詞變量函數(shù)常量園括號(hào)、方括號(hào)、花括號(hào)和逗號(hào)例“機(jī)器人（Robot）在第一個(gè)房間（Room1）內(nèi)”，可以表示為： INROOM（ROBOT，r1）其中 INROOM是謂詞 ROBOT和r1是常量謂詞公式的定義：利用連詞和量詞可以將原子

16、（謂詞）公式組成復(fù)合謂詞公式，稱(chēng)之為分子謂詞公式、謂詞合適公式、謂詞公式、合適公式。對(duì)于命題合適公式和謂詞合適公式有下列等價(jià)關(guān)系：否定之否定： （P） 等價(jià)于 P PQ 等價(jià)于 PQ狄-摩根定律 （PQ）等價(jià)于 PQ （PQ）等價(jià)于 PQ分配律 P(QR) 等價(jià)于 (PQ)(PR) P(QR) 等價(jià)于 (PQ)(PR)交換律 PQ 等價(jià)于 QP PQ 等價(jià)于 QP結(jié)合律 (PQ)R 等價(jià)于 P(QR) (PQ)R 等價(jià)于 P(QR)逆否律 PQ 等價(jià)于 QP對(duì)于謂詞合適公式有下列等價(jià)關(guān)系： ($x)P(x) 等價(jià)于 (x)P(x) (x)P(x) 等價(jià)于 ($x)P(x) (x)P(x)Q(x

17、) 等價(jià)于 (x)P(x)(x)Q(x)($x)P(x)Q(x) 等價(jià)于 ($x)P(x) ($x)Q(x) (x)P(x) 等價(jià)于 (y)P(y) ($x)P(x) 等價(jià)于 ($y)P(y)置換：形如 t1 / v1 , , tn / vn 的集合，稱(chēng)為一個(gè)置換，其中 vi 是不同的變量，ti是與vi不同的項(xiàng)（包括變量，常量或函數(shù)）例或例子：設(shè) t1 / v1 , , tn / vn 為一個(gè)置換，E是一個(gè)原子謂詞公式。則E表示將E中的 vi 同時(shí)用 ti（i=1,n）代入后所得到的結(jié)果，E稱(chēng)為E的一個(gè)例子置換的合成：設(shè)有兩個(gè)置換t1 / x1, ,tn / xns1 / y1, ,sm /

18、ym則和的合成是如下置換： t1/x1, , tn/xn, s1/y1, , sm/ym 其中，對(duì)于任何 tj=xj 者消去，yj 是 x1,xn 之一者消去，記為如何求 ti :s1/y1 , , sm/ym如果 ti 出現(xiàn) y1, ., ym中的變量 yi ， 則用其對(duì)應(yīng)的項(xiàng) si 來(lái)代替。合一：設(shè) s 是一個(gè)置換， Ei 是表達(dá)式（原子謂詞公式）集合 。如果置換 s 使得 E1s=E2s=Eis=則我們稱(chēng)表達(dá)式集合 Ei 是可合一的，并稱(chēng) s為 Ei 的合一者最一般的合一者：如果 s 是 Ei 的任意一個(gè)合一者，又存在某一個(gè) s，使得 s = g s 或者 Ei s = Ei g s則稱(chēng)

19、 g 是 Ei 的最通用（最一般）的合一者，記作mgu分歧集（或不一致集合）設(shè)有一非空有限公式集合F=F1,Fn，從F中各個(gè)公式的第一個(gè)符號(hào)同時(shí)向右比較，直到發(fā)現(xiàn)第一個(gè)彼此不盡相同的符號(hào)為止，從F中的各個(gè)公式中取出那些以第一個(gè)不一致符號(hào)開(kāi)始的最大的子表達(dá)式為元素，組成一個(gè)集合D，稱(chēng)為F的分歧集（不一致集合）。 其中，F(xiàn) i ( i=1,n)是原子謂詞公式合一算法： 設(shè)F為非空有限表達(dá)式集合，則可以按下列步驟求出mgu：置k=0，F(xiàn)k=F,k=(空置換，即不含元素的置換)若Fk只有一個(gè)表達(dá)式，則算法終止，其中k就是要求的mgu找出Fk的分歧集Dk若Dk中存在元素ak和tk，其中ak是變?cè)瑃k是

20、項(xiàng)，且ak不在tk中出現(xiàn)，則置： k+1=ktk/ak Fk+1=Fktk/ak k=k+1 然后轉(zhuǎn)向算法終止，F(xiàn)的mgu不存在合一算法的流程圖:謂詞公式化成子句集（九步） 消去“蘊(yùn)含”和“等價(jià)”連結(jié)詞 AB = ABAB = (AB)(B A) 減少“非”連結(jié)詞的轄域（將“”連結(jié)詞直接作用到原子公式前）(A) A(AB) = AB(AB) = AB($x)A(x) = (x)(A(x)(x)A(x) = ($x)(A(x) 對(duì)變量標(biāo)準(zhǔn)化（約束變?cè)拿? 對(duì)約束變?cè)拿沟盟械募s束變?cè)疾幌嗤?，保證每一個(gè)量詞都有自己唯一的約束變?cè)ゴ嬖诹吭~（引入斯科倫函數(shù)）化成前束范式: 將全稱(chēng)量詞

21、移到謂詞公式的左邊，使得每一個(gè)量詞的轄域包括該量詞后面的整個(gè)謂詞公式(x)A(x)R = (x) (A(x)R)(x)A(x)R = (x) (A(x)R)(1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z)(1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z)說(shuō)明：A(x), B(z), R中允許含有與x，z不同的自由變量將母式化成合取范式利用分配律將前束范式化成前束合取范式：P(QR) = (PQ)(PR) （析取合?。┫トQ(chēng)量詞消去合取連結(jié)詞母式為合取范式： A1 A2 An消去合取連結(jié)詞，得到子句集： A1 , A2, , An子句：基本式（

22、文字）的析?。ㄖ缓└淖兞棵?，得到子句集更改變?cè)沟靡粋€(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中，即不同的子句包含不同的約束變?cè)f(shuō)明：到現(xiàn)在為止，謂詞公式只包含三種連結(jié)詞“合取”：“析取” “非” 設(shè)，是一個(gè)謂詞公式，將量詞記作（即$或）如果中包含部分公式 (x)，則中變?cè)?x 的一切出現(xiàn)都稱(chēng)為 x 在 中的約束出現(xiàn)，相應(yīng)地稱(chēng) x 為約束變?cè)▎≡?、虛?gòu)變量、約束變量）中不在任何量詞作用域內(nèi)的變?cè)?x ，稱(chēng)為變?cè)?x 在 中的自由出現(xiàn)，相應(yīng)地稱(chēng) x 為自由變?cè)ㄗ杂勺兞浚┳泳浼庸降亩x：原子命題是原子公式如果t1,tn(n1)是項(xiàng)，P是謂詞，則P(t1,tn)是原子公式其它表達(dá)式都不是原

23、子公式子句的定義： 文字（或基本式）：“原子公式”或者“原子公式的非” 子句：一個(gè)或多個(gè)基本式的 析取子句形式的定義：一個(gè)謂詞公式具有形式： ( x1 )( xn )( c1c2cm )其中，ci ( i = 1, , m )為子句 x1, , xn 是子句中出現(xiàn)的約束變?cè)獎(jiǎng)t，稱(chēng)謂詞公式具有子句形式子句集的定義：(x1 )(xn )( c1c2cm )若謂詞公式 具有子句形式，記 S = ( c1 , c2 , , cm )則，稱(chēng) S 為謂詞公式的子句集消解式：設(shè)c1 , c2是兩個(gè)無(wú)公共變量的子句，令 c1= P(t11,t1n)P(tk1,tkn)c1 c2= P(t11,t1n)P(tm

24、1,tmn)c2說(shuō)明：謂詞符號(hào)相同，變?cè)煌?P(t11,t1n), , P(tk1,tkn), P(t11,t1n), , P(tm1,tmn) 有最一般的合一者（或一致置換）（mgu）則稱(chēng) c = ( c1 c2) 為c1 , c2的消解式消解演繹與消解反演設(shè)S是子句集，c是子句。若存在一個(gè)子句序列c1,cn滿(mǎn)足 cn = c 任意一個(gè) ci 或者屬于 S 或者它前面的子句 ck, cl ( ik , il )的消解式則稱(chēng) c1, , cn 是從子句集 S 到子句 c 的一個(gè)消解演繹當(dāng) c= 時(shí)的消解演繹稱(chēng)為（消解）反演反演的基本算法：把謂詞公式轉(zhuǎn)化為子句集S（所有子句的變量名不同）如空

25、子句成為子句集的子句，則算法結(jié)束在子句集中選取兩個(gè)不同的可以消解的子句ci , cj計(jì)算 ci , cj 的消解式 rij 把 rij 加到子句集中，形成新的子句集S轉(zhuǎn)到給定一個(gè)公式集 S（前提條件）和目標(biāo)公式 L（結(jié)論），通過(guò)反演來(lái)求證目標(biāo)公式 L，其證明過(guò)程為：否定 L ，得到 L把 L 加到 S 中把新形成的集合 S ， L 化為子句集（各自化成子句集，變量改名）應(yīng)用消解原理，導(dǎo)出一個(gè)表示矛盾的空子句原子公式：原子命題（0元謂詞）和謂詞基本式：原子公式或原子公式的非正基本式：不帶“非號(hào)”的原子公式負(fù)基本式：帶“非號(hào)”的原子公式Horn子句及Horn子句集：Horn子句：最多只含有一個(gè)正基

26、本式的子句（只含一個(gè)正基本式或者不含正基本式）Horn子句集：每一個(gè)子句均為Horn子句的子句集8.Prolog語(yǔ)言是：以一階謂詞邏輯的Horn 子句集為語(yǔ)法，以Robinson的消解原理為工具，加上深度優(yōu)先的控制策略而形成的人工智能通用程序設(shè)計(jì)語(yǔ)言Prolog中的語(yǔ)句分成三種形式：事實(shí)： P. （含義：無(wú)條件成立，恒為真 ）規(guī)則： P :- P1, P2, , Pn. （含義：若P1, , Pn均為真時(shí)，則P為真 ）問(wèn)題（目標(biāo)）：?- Q1, Q2, ,Qm . （含義：Q1, , Qm 同時(shí)為真嗎？）Visual Prolog 程序的基本結(jié)構(gòu)：domains（域段，說(shuō)明變量類(lèi)型，無(wú)句號(hào)、可

27、以缺省）predicates. （謂詞段，說(shuō)明謂詞，無(wú)句號(hào)）clauses. （子句段，程序主體，必須有句號(hào)）goal （目標(biāo)段，表達(dá)目標(biāo)或問(wèn)題，必須有句號(hào)）Prolog的程序主要分為兩部分： 前提部分：所有事實(shí)和規(guī)則 問(wèn)題部分：目標(biāo)子句序列第四部分 人工神經(jīng)網(wǎng)絡(luò)計(jì)算智能是一種智力方式的低層認(rèn)知，它與人工智能的區(qū)別是認(rèn)知層次從中層下降至低層。中層系統(tǒng)含有知識(shí)，低層系統(tǒng)則沒(méi)有知識(shí)計(jì)算智能系統(tǒng)：系統(tǒng)只涉及數(shù)值（低層）數(shù)據(jù)，含有模式識(shí)別部分，不應(yīng)用人工智能意義上的知識(shí)，而且具有下列特點(diǎn)：計(jì)算適應(yīng)性、計(jì)算容錯(cuò)性、接近人的速度、誤差率與人相近神經(jīng)元的動(dòng)作或工作原理： 求加權(quán)和 與閾值比較 用激活函數(shù)得到