人工智能及其應(yīng)用知識(shí)

1、第二章 知識(shí)表示 本章主要討論知識(shí)表示問(wèn)題，介紹7種知識(shí)表示方法：狀態(tài)空間法、問(wèn)題歸約法、謂詞演算法、語(yǔ)義網(wǎng)絡(luò)法、框架表示、本體技術(shù)、過(guò)程表示。掌握狀態(tài)空間法、問(wèn)題歸約法、謂詞演算法、語(yǔ)義網(wǎng)絡(luò)法的要點(diǎn)及其之間的關(guān)系，了解框架表示、本體技術(shù)、過(guò)程表示。 知識(shí)表示的基本概念知識(shí)表示的基本概念 v知識(shí)表示：研究用機(jī)器表示知識(shí)的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識(shí)的存儲(chǔ)又考慮知識(shí)的使用。v知識(shí)表示可看成是一組描述事物的約定，以把人類(lèi)知識(shí)表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。 人工智能系統(tǒng)所關(guān)心的知識(shí)人工智能系統(tǒng)所關(guān)心的知識(shí)v事實(shí)事實(shí) 有關(guān)問(wèn)題環(huán)境的一些事物的知識(shí)，常以有關(guān)問(wèn)題環(huán)

2、境的一些事物的知識(shí)，常以“是是”的形式出現(xiàn)。的形式出現(xiàn)。如事物的分類(lèi)、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀(guān)事實(shí)等。如雪是白如事物的分類(lèi)、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀(guān)事實(shí)等。如雪是白色的、鳥(niǎo)有翅膀、張三李四是好朋友、這輛車(chē)是張三的。色的、鳥(niǎo)有翅膀、張三李四是好朋友、這輛車(chē)是張三的。v規(guī)則規(guī)則 有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)，是動(dòng)態(tài)有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)，是動(dòng)態(tài)的，常以的，常以“如果如果那么那么”形式出現(xiàn)。形式出現(xiàn)。v控制控制 有關(guān)問(wèn)題的求解步驟、技巧性知識(shí)，告訴怎么做一件事。有關(guān)問(wèn)題的求解步驟、技巧性知識(shí)，告訴怎么做一件事。v元知識(shí)元知識(shí) 有關(guān)知識(shí)的知

3、識(shí)，是知識(shí)庫(kù)中的高層知識(shí)。包括怎樣使用規(guī)則、有關(guān)知識(shí)的知識(shí)，是知識(shí)庫(kù)中的高層知識(shí)。包括怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識(shí)。解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識(shí)。2.1 狀態(tài)空間法狀態(tài)空間法v問(wèn)題求解問(wèn)題求解v問(wèn)題求解(problem solving)是個(gè)大課題，它涉及歸約、推斷、決策、規(guī)劃、常識(shí)推理、定理證明和相關(guān)過(guò)程的核心概念。v在分析了人工智能研究中運(yùn)用的問(wèn)題求解方法之后，就會(huì)發(fā)現(xiàn)許多問(wèn)題求解方法是采用試探搜索方法的。也就是說(shuō)，這些方法是通過(guò)在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來(lái)求解問(wèn)題的。v狀態(tài)空間法：基于解答空間的問(wèn)題表示和求解方法，它是以狀態(tài)和算符(operator)為

4、基礎(chǔ)來(lái)表示和求解問(wèn)題的。 2.1 狀態(tài)空間法狀態(tài)空間法1.問(wèn)題求解技術(shù)兩個(gè)主要的方面問(wèn)題求解技術(shù)兩個(gè)主要的方面 (1) 問(wèn)題的表示：如果描述方法不對(duì)，對(duì)問(wèn)題求解會(huì)帶來(lái)很大的困難；(2) 求解的方法：采用試探搜索方法。 2.狀態(tài)空間法三要點(diǎn)狀態(tài)空間法三要點(diǎn) (1)狀態(tài)（state）(2)算符（operator）(3)狀態(tài)空間方法2.1 狀態(tài)空間法狀態(tài)空間法2.1.1 問(wèn)題狀態(tài)描述問(wèn)題狀態(tài)描述 1.定義定義 狀態(tài)狀態(tài)(state)(state)：為描述某類(lèi)不同事物間的差別而引入的一組最少變量：為描述某類(lèi)不同事物間的差別而引入的一組最少變量q q0 0，q q1 1，q qn n的有序集合，其矢量形

5、式如下：的有序集合，其矢量形式如下： Q=qQ=q0,0,q q1,1,q,qn n T T式中每個(gè)元素式中每個(gè)元素q qi i(i=0,1,n)(i=0,1,n)為集合的分量為集合的分量, ,稱(chēng)為狀態(tài)變量稱(chēng)為狀態(tài)變量, ,給定每個(gè)分量的一給定每個(gè)分量的一組值就得到一個(gè)具體的狀態(tài)組值就得到一個(gè)具體的狀態(tài), ,如如 Q Qk k=q=q0k,0k,q q1k,1k,q,qnknk T T 式中每個(gè)元素式中每個(gè)元素q qi i(i=0,1(i=0,1，n)n)為集合的分量，稱(chēng)為狀態(tài)變量。為集合的分量，稱(chēng)為狀態(tài)變量。 算符算符：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱(chēng)為操作符或算符。操：使問(wèn)題從一種

6、狀態(tài)變化為另一種狀態(tài)的手段稱(chēng)為操作符或算符。操作符可為走步、過(guò)程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。作符可為走步、過(guò)程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。問(wèn)題的狀態(tài)空間問(wèn)題的狀態(tài)空間(state space)(state space)：是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系：是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說(shuō)明的集合，即所有可能的問(wèn)題初始狀態(tài)集合的圖，它包含三種說(shuō)明的集合，即所有可能的問(wèn)題初始狀態(tài)集合S S、操作符、操作符集合集合F F以及目標(biāo)狀態(tài)集合以及目標(biāo)狀態(tài)集合G G?？砂褷顟B(tài)空間記為三元狀態(tài)。可把狀態(tài)空間記為三元狀態(tài)(S(S，F(xiàn) F，G)G)。2.1 狀態(tài)空間

7、法狀態(tài)空間法v2.狀態(tài)空間表示詳釋狀態(tài)空間表示詳釋讓我們先用數(shù)碼難題(puzzle problem)來(lái)說(shuō)明狀態(tài)空間表示的概念。由15個(gè)編有1至15并放在44方格棋盤(pán)上的可走動(dòng)的棋子組成。棋盤(pán)上總有一格是空的，以便可能讓空格周?chē)钠遄幼哌M(jìn)空格，這也可以理解為移動(dòng)空格。圖中繪出了兩種棋局，即初始棋局和目標(biāo)棋局，它們對(duì)應(yīng)于該下棋問(wèn)題的初始狀態(tài)和目標(biāo)狀態(tài)。如何把初始棋局變換為目標(biāo)棋局呢？問(wèn)題的解答就是某個(gè)合適的棋子走步序列，如左移棋子12，下移棋子15，右移棋子4，等等。2.1 狀態(tài)空間法狀態(tài)空間法v2.狀態(tài)空間表示詳釋狀態(tài)空間表示詳釋v狀態(tài)空間法：從某個(gè)初始狀態(tài)開(kāi)始，每次加一個(gè)操作符，遞增的建立起狀

8、態(tài)空間法：從某個(gè)初始狀態(tài)開(kāi)始，每次加一個(gè)操作符，遞增的建立起操作符的試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為止。操作符的試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為止。v尋找狀態(tài)空間的全部過(guò)程包括從舊的狀態(tài)描述產(chǎn)生新的狀態(tài)描述，以及尋找狀態(tài)空間的全部過(guò)程包括從舊的狀態(tài)描述產(chǎn)生新的狀態(tài)描述，以及此后檢驗(yàn)這些新的狀態(tài)描述，看是否達(dá)到了該目標(biāo)狀態(tài)。對(duì)于最優(yōu)化問(wèn)此后檢驗(yàn)這些新的狀態(tài)描述，看是否達(dá)到了該目標(biāo)狀態(tài)。對(duì)于最優(yōu)化問(wèn)題找到任一目標(biāo)狀態(tài)是不夠的，必須按某個(gè)準(zhǔn)則實(shí)現(xiàn)最優(yōu)化路徑。題找到任一目標(biāo)狀態(tài)是不夠的，必須按某個(gè)準(zhǔn)則實(shí)現(xiàn)最優(yōu)化路徑。P26v完成目標(biāo)狀態(tài)的三件事：完成目標(biāo)狀態(tài)的三件事：v狀態(tài)描述方式，特別是初始狀態(tài)描述；狀態(tài)描

9、述方式，特別是初始狀態(tài)描述；v操作符集合及其對(duì)狀態(tài)描述的作用；操作符集合及其對(duì)狀態(tài)描述的作用；v目標(biāo)狀態(tài)的特性。目標(biāo)狀態(tài)的特性。2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀態(tài)圖示法 為了對(duì)狀態(tài)空間圖有更深入的了解，這里介紹一下圖論中的幾個(gè)術(shù)語(yǔ)和了對(duì)狀態(tài)空間圖有更深入的了解，這里介紹一下圖論中的幾個(gè)術(shù)語(yǔ)和圖的正式表示法。圖的正式表示法。1.圖論中的幾個(gè)術(shù)語(yǔ)圖論中的幾個(gè)術(shù)語(yǔ)節(jié)點(diǎn)節(jié)點(diǎn)(node)：圖形上的匯合點(diǎn)，用來(lái)表示狀態(tài)、事件和時(shí)間關(guān)系的匯合，也圖形上的匯合點(diǎn)，用來(lái)表示狀態(tài)、事件和時(shí)間關(guān)系的匯合，也可用來(lái)指示通路的匯合；可用來(lái)指示通路的匯合； 弧線(xiàn)弧線(xiàn)(arc)：節(jié)點(diǎn)間的連接線(xiàn)；節(jié)點(diǎn)間

10、的連接線(xiàn)； 有向圖有向圖(directed graph)：一對(duì)節(jié)點(diǎn)用弧線(xiàn)連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向另一個(gè)一對(duì)節(jié)點(diǎn)用弧線(xiàn)連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)。 后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)(descendant node)與與父輩節(jié)點(diǎn)父輩節(jié)點(diǎn)(parent node)：如果某條弧線(xiàn)從節(jié)：如果某條弧線(xiàn)從節(jié)點(diǎn)點(diǎn)ni指向節(jié)點(diǎn)指向節(jié)點(diǎn)nj，那么節(jié)點(diǎn)，那么節(jié)點(diǎn)nj就叫做節(jié)點(diǎn)就叫做節(jié)點(diǎn)ni的后繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn)的后繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn)ni叫做叫做節(jié)點(diǎn)節(jié)點(diǎn)nj的父輩節(jié)點(diǎn)或祖先。的父輩節(jié)點(diǎn)或祖先。2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀態(tài)圖示法 1.圖論中的幾個(gè)術(shù)語(yǔ)圖論中的幾個(gè)術(shù)語(yǔ)路徑路徑：某個(gè)節(jié)點(diǎn)序列：

11、某個(gè)節(jié)點(diǎn)序列(n(ni1i1,n,ni2i2,n,nikik) )當(dāng)當(dāng)j=2j=2，3 3，k k時(shí)，如果對(duì)于每一個(gè)時(shí)，如果對(duì)于每一個(gè)n ni i，j-1j-1都有一個(gè)后繼節(jié)點(diǎn)都有一個(gè)后繼節(jié)點(diǎn)n nijij存在，那么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)存在，那么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)n ni1i1至節(jié)點(diǎn)至節(jié)點(diǎn)n nikik的長(zhǎng)度為的長(zhǎng)度為k k的路徑。的路徑。v代價(jià)代價(jià)：用：用c(nc(ni i,n,nj j) )來(lái)表示從節(jié)點(diǎn)來(lái)表示從節(jié)點(diǎn)n ni i指向節(jié)點(diǎn)指向節(jié)點(diǎn)n nj j的那段弧線(xiàn)的代價(jià)。兩節(jié)點(diǎn)間路的那段弧線(xiàn)的代價(jià)。兩節(jié)點(diǎn)間路徑的代價(jià)等于連接該路徑上各節(jié)點(diǎn)的所有弧線(xiàn)代價(jià)之和。徑的代價(jià)等于連接該

12、路徑上各節(jié)點(diǎn)的所有弧線(xiàn)代價(jià)之和。 顯式表示顯式表示：各節(jié)點(diǎn)及其具有代價(jià)的弧線(xiàn)由一張表明確給出。此表可能列出該：各節(jié)點(diǎn)及其具有代價(jià)的弧線(xiàn)由一張表明確給出。此表可能列出該圖中的每一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及連接弧線(xiàn)的代價(jià)。圖中的每一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及連接弧線(xiàn)的代價(jià)。 隱式表示隱式表示：節(jié)點(diǎn)的無(wú)限集合：節(jié)點(diǎn)的無(wú)限集合ssi i 作為起始節(jié)點(diǎn)是已知的。后繼節(jié)點(diǎn)算符作為起始節(jié)點(diǎn)是已知的。后繼節(jié)點(diǎn)算符也也是已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線(xiàn)是已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線(xiàn)的代價(jià)。的代價(jià)。 2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀

13、態(tài)圖示法 v2.2.圖的顯式和隱式表示圖的顯式和隱式表示 一個(gè)圖可由顯式說(shuō)明也可由隱式說(shuō)明。顯然，顯式說(shuō)明對(duì)于大型一個(gè)圖可由顯式說(shuō)明也可由隱式說(shuō)明。顯然，顯式說(shuō)明對(duì)于大型的圖是不切實(shí)際的，而對(duì)于具有無(wú)限節(jié)點(diǎn)集合的圖則是不可能的。的圖是不切實(shí)際的，而對(duì)于具有無(wú)限節(jié)點(diǎn)集合的圖則是不可能的。此外，引入后繼節(jié)點(diǎn)算符的概念是方便的。后繼節(jié)點(diǎn)算符此外，引入后繼節(jié)點(diǎn)算符的概念是方便的。后繼節(jié)點(diǎn)算符也是也是已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線(xiàn)的代價(jià)把后繼算符應(yīng)用于弧線(xiàn)的代價(jià)把后繼算符應(yīng)用于sisi的成員和它們的后繼節(jié)點(diǎn)以及

14、這些的成員和它們的后繼節(jié)點(diǎn)以及這些后繼節(jié)點(diǎn)的后繼節(jié)點(diǎn)，如此無(wú)限制地進(jìn)行下去，最后使得由后繼節(jié)點(diǎn)的后繼節(jié)點(diǎn)，如此無(wú)限制地進(jìn)行下去，最后使得由和和sisi所規(guī)定的隱式圖變?yōu)轱@示圖。所規(guī)定的隱式圖變?yōu)轱@示圖。v 問(wèn)題的表示對(duì)求解工作量有很大的影響。人們顯然希望有較小的問(wèn)題的表示對(duì)求解工作量有很大的影響。人們顯然希望有較小的狀態(tài)空間表示。許多似乎很難的問(wèn)題，當(dāng)表示適當(dāng)時(shí)就可能具有小而狀態(tài)空間表示。許多似乎很難的問(wèn)題，當(dāng)表示適當(dāng)時(shí)就可能具有小而簡(jiǎn)單的狀態(tài)空間。簡(jiǎn)單的狀態(tài)空間。 2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀態(tài)圖示法v根據(jù)問(wèn)題狀態(tài)、操作符和目標(biāo)條件選擇各種表示，是高效率問(wèn)題求解必根

15、據(jù)問(wèn)題狀態(tài)、操作符和目標(biāo)條件選擇各種表示，是高效率問(wèn)題求解必須的。須的。v各種問(wèn)題都可以用狀態(tài)空間加以表示，并用狀態(tài)空間搜索法來(lái)求解。各種問(wèn)題都可以用狀態(tài)空間加以表示，并用狀態(tài)空間搜索法來(lái)求解。2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀態(tài)圖示法 1.產(chǎn)生式系統(tǒng)（Production System） v一個(gè)總數(shù)據(jù)庫(kù)(global database)：它含有與具體任務(wù)有關(guān)的信息；隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫(kù)可能小得像數(shù)字矩陣那樣簡(jiǎn)單，或許大得如檢索文件結(jié)構(gòu)那么復(fù)雜。v一套規(guī)則：它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適用性或先決條件，右部描述規(guī)則應(yīng)用時(shí)所完成的

16、動(dòng)作。用規(guī)則來(lái)改變數(shù)據(jù)庫(kù)就象用算符來(lái)改變狀態(tài)一樣。v一個(gè)控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿(mǎn)足時(shí)，就停止計(jì)算?？刂撇呗杂煽刂葡到y(tǒng)選擇和確定。推銷(xiāo)員旅行問(wèn)題v總數(shù)據(jù)庫(kù)：到目前為止所訪(fǎng)問(wèn)的城市；v規(guī)則對(duì)應(yīng)于決策：即下一步走向城市，下一步走向城市，下一步走向城市，一條規(guī)則必須能把某個(gè)數(shù)據(jù)庫(kù)變?yōu)橐粋€(gè)合法數(shù)據(jù)庫(kù)，否則不適應(yīng)這個(gè)數(shù)據(jù)庫(kù)；v任一以為起點(diǎn)和終點(diǎn)，并出現(xiàn)所有其它城市的總數(shù)據(jù)庫(kù)，都滿(mǎn)足終止條件2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀態(tài)圖示法 2.2.狀態(tài)空間表示舉例狀態(tài)空間表示舉例例例2 2 猴子和香蕉問(wèn)題猴子和香蕉問(wèn)題(monkey and banana

17、 problem)(monkey and banana problem)在一個(gè)房間內(nèi)有一只猴子在一個(gè)房間內(nèi)有一只猴子( (可把這只猴子看做一個(gè)機(jī)器人可把這只猴子看做一個(gè)機(jī)器人) )、一個(gè)箱子和一束香蕉。、一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢呢? ?圖圖2.42.4表示出猴子、香蕉和箱子在房間內(nèi)的相對(duì)位置。表示出猴子、香蕉和箱子在房間內(nèi)的相對(duì)位置。 v猴子和香蕉猴子和香蕉. 用一個(gè)四元表列用一個(gè)四元表列(W,X,Y,Z)(W,X,Y,Z)來(lái)表示這個(gè)問(wèn)題來(lái)表示這個(gè)問(wèn)

18、題v 的狀態(tài)，的狀態(tài)， 其中其中 W W猴子的水平位置猴子的水平位置 X X當(dāng)猴子在箱子頂上時(shí)取當(dāng)猴子在箱子頂上時(shí)取X=1X=1；否則??；否則取X=0X=0 Y Y箱子的水平位置箱子的水平位置 Z Z當(dāng)猴子摘到香蕉時(shí)取當(dāng)猴子摘到香蕉時(shí)取Z=1Z=1；否則取；否則取Z=0 Z=0 圖圖 2.4 2.4 猴子和香蕉問(wèn)題猴子和香蕉問(wèn)題2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀態(tài)圖示法 這個(gè)問(wèn)題中的操作這個(gè)問(wèn)題中的操作( (算符算符) )如下：如下：(1) goto(U)猴子走到水平位置猴子走到水平位置U U，或者用產(chǎn)生式規(guī)則表示為：，或者用產(chǎn)生式規(guī)則表示為：v (W，0，Y，z)(U，0

19、，Y，z) (2.3)v 即應(yīng)用操作即應(yīng)用操作goto(U)，能把狀態(tài)，能把狀態(tài)(W，0，Y，z)變換為狀態(tài)變換為狀態(tài)(U，0，Y，z)。v(2) pushbox(V)猴子把箱子推到水平位置猴子把箱子推到水平位置V V，即有，即有 v (W，0，W，z) (V，0，V，z) (2.4) )v應(yīng)當(dāng)注意的是，要應(yīng)用算符應(yīng)當(dāng)注意的是，要應(yīng)用算符pushbox(V)，就要求產(chǎn)生式規(guī)則的左邊，就要求產(chǎn)生式規(guī)則的左邊，猴子與箱子必須在同一位置上，并且，猴子不是在箱子頂上。這種強(qiáng)猴子與箱子必須在同一位置上，并且，猴子不是在箱子頂上。這種強(qiáng)加于操作的適用性條件，叫做產(chǎn)生式規(guī)則的先決條件。加于操作的適用性條件，

20、叫做產(chǎn)生式規(guī)則的先決條件。2.1 狀態(tài)空間法狀態(tài)空間法v2.1.2 狀態(tài)圖示法狀態(tài)圖示法 這個(gè)問(wèn)題中的操作這個(gè)問(wèn)題中的操作( (算符算符) )如下：如下：(3) climbbox猴子爬上箱頂，即有猴子爬上箱頂，即有 v (W，0，W，z) (W，1，W，z) (2.5)在應(yīng)用算符在應(yīng)用算符climbboxclimbbox時(shí)也必須注意到，猴子和箱子應(yīng)當(dāng)在同一位置上，時(shí)也必須注意到，猴子和箱子應(yīng)當(dāng)在同一位置上，而且猴子不在箱頂上而且猴子不在箱頂上 。v(4) grasp(4) grasp猴子摘到香蕉，即有猴子摘到香蕉，即有 v (c,1,c,0) (c,1,c,0) (c,1,c,1) (2.6)

21、(c,1,c,1) (2.6)其中，其中，c c是香蕉正下方的地板位置，在應(yīng)用算符是香蕉正下方的地板位置，在應(yīng)用算符graspgrasp時(shí)，要求猴子和時(shí)，要求猴子和箱子都在位置箱子都在位置c c上，并且猴子已在箱子頂上上，并且猴子已在箱子頂上。2.1 狀態(tài)空間法狀態(tài)空間法v 對(duì)于規(guī)則對(duì)于規(guī)則(2)(2)，只有當(dāng)算符，只有當(dāng)算符pushbox(V)pushbox(V)v 的先決條件，即猴子與箱子在同一位的先決條件，即猴子與箱子在同一位v 置上而且猴子不在箱頂上這些條件得置上而且猴子不在箱頂上這些條件得v 到滿(mǎn)足時(shí)，算符到滿(mǎn)足時(shí)，算符pushbox(V)pushbox(V)才是適用才是適用v 的。

22、這一操作算符的作用是猴子把箱的。這一操作算符的作用是猴子把箱v 子推到位置子推到位置V V。在這一表示中，目標(biāo)。在這一表示中，目標(biāo)v 狀態(tài)的集合可由任何最后元素為狀態(tài)的集合可由任何最后元素為1 1的的v 表列來(lái)描述。令初始狀態(tài)為表列來(lái)描述。令初始狀態(tài)為(a,0,b,0) (a,0,b,0) 這時(shí)，這時(shí)，goto(U)goto(U)是唯一適用的操作，是唯一適用的操作， v 并導(dǎo)致下一狀態(tài)并導(dǎo)致下一狀態(tài)(U,0,b,0)(U,0,b,0)。現(xiàn)在有?，F(xiàn)在有3 3v 個(gè)適用的操作，即個(gè)適用的操作，即goto(U)goto(U)， v pushbox(V)pushbox(V)和和climbbox(cli

23、mbbox(若若U=b)U=b)。猴猴子子和和香香蕉蕉問(wèn)問(wèn)題題的的狀狀態(tài)態(tài)空空間間圖圖 2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.1 問(wèn)題歸約描述問(wèn)題歸約描述先把問(wèn)題分解為子問(wèn)題和子-子問(wèn)題，然后解決較小的問(wèn)題。對(duì)該問(wèn)題的某個(gè)具體子集的解答就意味著對(duì)原始問(wèn)題的一個(gè)解答。問(wèn)題歸約表示的組成部分：v一個(gè)初始問(wèn)題描述；v一套把問(wèn)題變換為子問(wèn)題的操作符；v一套本原問(wèn)題描述。v問(wèn)題歸約的實(shí)質(zhì)：從目標(biāo)(要解決的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.1 問(wèn)題歸約描述問(wèn)題歸約描述v梵塔難題梵塔難題 有有3 3個(gè)柱

24、子個(gè)柱子(1(1，2 2和和3)3)和和3 3個(gè)不同尺寸的圓盤(pán)（個(gè)不同尺寸的圓盤(pán)（A A，B B和和C C）。在每個(gè)圓）。在每個(gè)圓盤(pán)的中心有一個(gè)孔，所以圓盤(pán)可以堆疊在柱子上。最初，盤(pán)的中心有一個(gè)孔，所以圓盤(pán)可以堆疊在柱子上。最初，3 3個(gè)圓盤(pán)都堆個(gè)圓盤(pán)都堆在柱子在柱子1 1上：最大的圓盤(pán)上：最大的圓盤(pán)C C在底部，最小的圓盤(pán)在底部，最小的圓盤(pán)A A在頂部。要求把所有圓在頂部。要求把所有圓盤(pán)都移到柱子盤(pán)都移到柱子3 3上，每次只許移動(dòng)一個(gè)，而且只能先搬動(dòng)柱子頂部的圓上，每次只許移動(dòng)一個(gè)，而且只能先搬動(dòng)柱子頂部的圓盤(pán)，還不許把尺寸較大的圓盤(pán)堆放在尺寸較小的圓盤(pán)上。這個(gè)問(wèn)題的初盤(pán)，還不許把尺寸較大的

25、圓盤(pán)堆放在尺寸較小的圓盤(pán)上。這個(gè)問(wèn)題的初始配置和目標(biāo)配置如圖始配置和目標(biāo)配置如圖2.62.6所示。所示。2.2 問(wèn)題歸約法問(wèn)題歸約法 v解題過(guò)程：解題過(guò)程：將原始問(wèn)題歸約為一個(gè)較簡(jiǎn)單問(wèn)題集合，要把所有圓盤(pán)都移至柱將原始問(wèn)題歸約為一個(gè)較簡(jiǎn)單問(wèn)題集合，要把所有圓盤(pán)都移至柱子子3 3，我們必須首先把圓盤(pán)，我們必須首先把圓盤(pán)C C移至柱子移至柱子3 3；而且在移動(dòng)圓盤(pán)；而且在移動(dòng)圓盤(pán)C C至柱子至柱子3 3之前，之前，要求柱子要求柱子3 3必須是空的。只有在移開(kāi)圓盤(pán)必須是空的。只有在移開(kāi)圓盤(pán)A A和和B B之后，才能移動(dòng)圓盤(pán)之后，才能移動(dòng)圓盤(pán)C C；而；而且圓盤(pán)且圓盤(pán)A A和和B B最好不要移至柱子最

26、好不要移至柱子3 3，否則就不能把圓盤(pán)，否則就不能把圓盤(pán)C C移至柱子移至柱子3 3。因此，。因此，首先應(yīng)該把圓盤(pán)首先應(yīng)該把圓盤(pán)A A和和B B移到柱子移到柱子2 2上。然后才能夠進(jìn)行關(guān)鍵的一步，把圓上。然后才能夠進(jìn)行關(guān)鍵的一步，把圓盤(pán)盤(pán)C C從柱子從柱子1 1移至柱子移至柱子3 3，并繼續(xù)解決難題的其余部分。，并繼續(xù)解決難題的其余部分。v將原始難題歸約（簡(jiǎn)化）為下列子難題：移動(dòng)圓盤(pán)將原始難題歸約（簡(jiǎn)化）為下列子難題：移動(dòng)圓盤(pán)A A和和B B至柱子至柱子2 2的的雙圓盤(pán)難題，如圖雙圓盤(pán)難題，如圖(a)(a)所示。所示。2.2 問(wèn)題歸約法問(wèn)題歸約法 v 圖 2.7 梵塔問(wèn)題解答(a) 圖 2.8

27、 梵塔問(wèn)題解答(b) 圖 2.9 梵塔問(wèn)題解答(c) 2.2 問(wèn)題歸約法問(wèn)題歸約法 v 梵塔問(wèn)題歸約圖：子問(wèn)題梵塔問(wèn)題歸約圖：子問(wèn)題2 2可作為本原問(wèn)題考慮，因?yàn)樗慕庵话勺鳛楸驹瓎?wèn)題考慮，因?yàn)樗慕庵话徊揭苿?dòng)。應(yīng)用一系列相似的推理，子問(wèn)題含一步移動(dòng)。應(yīng)用一系列相似的推理，子問(wèn)題1 1和子問(wèn)題和子問(wèn)題3 3也可被歸約為也可被歸約為本原問(wèn)題，如圖本原問(wèn)題，如圖2.102.10所示。這種圖式結(jié)構(gòu)，叫做與或圖所示。這種圖式結(jié)構(gòu)，叫做與或圖(AND/OR graph)(AND/OR graph)。它能有效地說(shuō)明如何由問(wèn)題歸約法求得問(wèn)題的解答。它能有效地說(shuō)明如何由問(wèn)題歸約法求得問(wèn)題的解答。v梵塔問(wèn)

28、題歸約圖2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.1 問(wèn)題歸約描述問(wèn)題歸約描述v問(wèn)題歸約描述問(wèn)題歸約描述v問(wèn)題歸約方法應(yīng)用算符把問(wèn)題描述變換為子問(wèn)題描述，問(wèn)題描述可以用問(wèn)題歸約方法應(yīng)用算符把問(wèn)題描述變換為子問(wèn)題描述，問(wèn)題描述可以用多種數(shù)據(jù)結(jié)構(gòu)形式，包括表列、樹(shù)、字符串、矢量、數(shù)組等。梵塔問(wèn)題多種數(shù)據(jù)結(jié)構(gòu)形式，包括表列、樹(shù)、字符串、矢量、數(shù)組等。梵塔問(wèn)題采用包含兩個(gè)數(shù)列的表列來(lái)描述采用包含兩個(gè)數(shù)列的表列來(lái)描述,(113),(113),（333)333)表示把配置（表示把配置（113113）變）變換為配置（換為配置（333333）。）。v用狀態(tài)空間表示的三元組合（用狀態(tài)空間表示的三元組合（S S，F(xiàn)

29、 F，G G）來(lái)規(guī)定與描述問(wèn)題，有關(guān)子問(wèn)）來(lái)規(guī)定與描述問(wèn)題，有關(guān)子問(wèn)題可以當(dāng)作狀態(tài)空間中的兩個(gè)一定的題可以當(dāng)作狀態(tài)空間中的兩個(gè)一定的“腳踏石腳踏石”之間尋找路徑來(lái)辨別。之間尋找路徑來(lái)辨別。梵塔問(wèn)題中的子問(wèn)題梵塔問(wèn)題中的子問(wèn)題 （111111）=（122122） ， （122122）=（322322） ， （322322）=（333333） ，規(guī)定了最后的路徑將要通過(guò)，規(guī)定了最后的路徑將要通過(guò)“腳踏石腳踏石”狀態(tài)狀態(tài)（122122）和（）和（322322）。）。2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.2 與或圖表示與或圖表示 與圖、或圖、與或圖：與圖、或圖、與或圖：一般地，我們用一個(gè)類(lèi)似圖的結(jié)構(gòu)

30、來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合，這種結(jié)構(gòu)圖叫做問(wèn)題歸約圖，或叫與或圖。如下圖所示:v（引入附加節(jié)點(diǎn)使含有一個(gè)以上后繼問(wèn)題的每個(gè)集合能夠聚集在它們各自的父輩節(jié)點(diǎn)之下。）子問(wèn)題替換集合結(jié)構(gòu)圖子問(wèn)題替換集合結(jié)構(gòu)圖 與或圖與或圖 2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.2 問(wèn)題歸約描述問(wèn)題歸約描述一些關(guān)于與或圖的術(shù)語(yǔ)：一些關(guān)于與或圖的術(shù)語(yǔ)：v終葉節(jié)點(diǎn)終葉節(jié)點(diǎn)：對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。v或節(jié)點(diǎn)或節(jié)點(diǎn)：只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（M M，N N，H H）。）。v與節(jié)點(diǎn)與節(jié)點(diǎn)：只有解決所有子問(wèn)題，才能解決其

31、父輩問(wèn)題的節(jié)點(diǎn)集合，如只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（B,C)B,C)和（和（D,E,FD,E,F）各個(gè)結(jié)點(diǎn)之間用一端小圓弧連接標(biāo)記。）各個(gè)結(jié)點(diǎn)之間用一端小圓弧連接標(biāo)記。 2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.2 問(wèn)題歸約描述問(wèn)題歸約描述與或圖與或圖：由與節(jié)點(diǎn)及或節(jié)點(diǎn)組成的結(jié)構(gòu)圖。由與節(jié)點(diǎn)及或節(jié)點(diǎn)組成的結(jié)構(gòu)圖。v可解節(jié)點(diǎn)的一般定義：可解節(jié)點(diǎn)的一般定義： (1) 終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)( (因?yàn)樗驗(yàn)樗黺們與本原問(wèn)題相關(guān)連們與本原問(wèn)題相關(guān)連) )。v(2) (2) 如果某個(gè)非終葉節(jié)點(diǎn)含有或后如果某個(gè)非終葉節(jié)點(diǎn)含有或后v繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)繼節(jié)點(diǎn)，那么

32、只要當(dāng)其后繼節(jié)點(diǎn)v至少有一個(gè)是可解的時(shí)，此非終至少有一個(gè)是可解的時(shí)，此非終v葉節(jié)點(diǎn)才是可解的。葉節(jié)點(diǎn)才是可解的。v(3) (3) 如果某個(gè)非終葉節(jié)點(diǎn)含有與如果某個(gè)非終葉節(jié)點(diǎn)含有與v后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)v點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)v才是可解的。才是可解的。圖圖 2.15 與或圖例子與或圖例子 2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.22.2.2問(wèn)題歸約描述問(wèn)題歸約描述 不可解節(jié)點(diǎn)的一般定義不可解節(jié)點(diǎn)的一般定義: : (1) (1) 沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。 (2) (2) 如果某個(gè)非終葉

33、節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。 (3) (3) 如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.2 問(wèn)題歸約描述問(wèn)題歸約描述與或圖構(gòu)成規(guī)則與或圖構(gòu)成規(guī)則(1) (1) 與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集合。圖中所含起始與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一

34、問(wèn)題或問(wèn)題集合。圖中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題。節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題。v(2) (2) 對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒(méi)有后裔。對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒(méi)有后裔。v(3) (3) 對(duì)于把算符應(yīng)用于問(wèn)題對(duì)于把算符應(yīng)用于問(wèn)題A A的每種可能情況，都把問(wèn)題變換為一個(gè)子問(wèn)題集合；的每種可能情況，都把問(wèn)題變換為一個(gè)子問(wèn)題集合；有向弧線(xiàn)自有向弧線(xiàn)自A A 指向后繼節(jié)點(diǎn)表示所求得的子指向后繼節(jié)點(diǎn)表示所求得的子v問(wèn)題集合，如下圖所示，把問(wèn)題問(wèn)題集合，如下圖所示，把問(wèn)題A A歸約為歸約為3 3個(gè)不同個(gè)不同v的子問(wèn)題集合的子問(wèn)題集合N N，M M，H(H(或節(jié)點(diǎn)或節(jié)點(diǎn)) )。圖圖 2.16 與

35、或樹(shù)與或樹(shù)2.2 問(wèn)題歸約法問(wèn)題歸約法 v2.2.2 問(wèn)題歸約描述問(wèn)題歸約描述與或圖構(gòu)成規(guī)則與或圖構(gòu)成規(guī)則v(4) (4) 一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線(xiàn)從一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線(xiàn)從此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。由于只有當(dāng)集合中所有的項(xiàng)都有解此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。由于只有當(dāng)集合中所有的項(xiàng)都有解時(shí)，這個(gè)子問(wèn)題的集合才能獲得解答，所以這些子問(wèn)題節(jié)點(diǎn)叫做與節(jié)點(diǎn)。時(shí)，這個(gè)子問(wèn)題的集合才能獲得解答，所以這些子問(wèn)題節(jié)點(diǎn)叫做與節(jié)點(diǎn)。v(5) (5) 在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題A

36、 A，而且這個(gè)算符產(chǎn)生，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則v3 3和規(guī)則和規(guī)則4 4所產(chǎn)生的圖可以得到簡(jiǎn)化。所產(chǎn)生的圖可以得到簡(jiǎn)化。v 因此，代表子問(wèn)題集合的中間或節(jié)因此，代表子問(wèn)題集合的中間或節(jié)v點(diǎn)可以被略去，如右圖所示。點(diǎn)可以被略去，如右圖所示。 圖圖 2.16 與或樹(shù)與或樹(shù)2.3 謂詞邏輯法謂詞邏輯法 v2.3.1 謂詞演算（謂詞演算（Predicate Calculus）1.語(yǔ)法和語(yǔ)義語(yǔ)法和語(yǔ)義(Syntax & Semantics)謂詞邏輯的基本組成部分：謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)和常量謂詞邏輯的基本組成部分

37、：謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)和常量符號(hào)，并用圓括號(hào)、方括號(hào)、花括號(hào)和逗號(hào)隔開(kāi)，表示論域內(nèi)的關(guān)系。符號(hào)，并用圓括號(hào)、方括號(hào)、花括號(hào)和逗號(hào)隔開(kāi)，表示論域內(nèi)的關(guān)系。v原子公式原子公式(atomic formulas)(atomic formulas)由若干謂詞符號(hào)和項(xiàng)組成的謂詞演算。由若干謂詞符號(hào)和項(xiàng)組成的謂詞演算。原子公式是謂詞演算基本積木塊。原子公式是謂詞演算基本積木塊。v例如，要表示機(jī)器人例如，要表示機(jī)器人(ROBOT)(ROBOT)在號(hào)房間在號(hào)房間(r1)(r1)內(nèi)，如圖內(nèi)，如圖2.192.19所所示，可以應(yīng)用原子公式示，可以應(yīng)用原子公式: :2.3 謂詞邏輯法謂詞邏輯法 v2.3.1 謂

38、詞演算（謂詞演算（Predicate Calculus） 1.語(yǔ)法和語(yǔ)義語(yǔ)法和語(yǔ)義(Syntax & Semantics)當(dāng)機(jī)器人當(dāng)機(jī)器人ROBOT移到房間移到房間r2時(shí)，原子公式可以表示為：時(shí)，原子公式可以表示為：v INROOM (ROBOT, r2)v 這兩個(gè)原子公式的通用形式就是這兩個(gè)原子公式的通用形式就是v 又如又如,“李的母親和他的父親結(jié)婚李的母親和他的父親結(jié)婚”這句話(huà)的原子公式表示這句話(huà)的原子公式表示 v 如下：2.3 謂詞邏輯法謂詞邏輯法 v2.3.1 2.3.1 謂詞演算（謂詞演算（Predicate CalculusPredicate Calculus）2.2.連詞

39、和量詞連詞和量詞(Connective & Quantifiers) (Connective & Quantifiers) v(1) (1) 連詞連詞與與合?。ê先。╟onjunctionconjunction）合取就是用連詞）合取就是用連詞把幾個(gè)把幾個(gè)公式連接起來(lái)而構(gòu)成的公式。合取項(xiàng)是合取式的每個(gè)組成部公式連接起來(lái)而構(gòu)成的公式。合取項(xiàng)是合取式的每個(gè)組成部分。分。v例：例：LIKE(ILIKE(I，MUSIC)LIKE(IMUSIC)LIKE(I，PAINTING)PAINTING)v ( (我喜愛(ài)音樂(lè)和繪畫(huà)。我喜愛(ài)音樂(lè)和繪畫(huà)。) )v2.3 謂詞邏輯法謂詞邏輯法 v2.3.1

40、 2.3.1 謂詞演算（謂詞演算（Predicate CalculusPredicate Calculus）2.2.連詞和量詞連詞和量詞(Connective & Quantifiers) (Connective & Quantifiers) v或或析?。ㄎ鋈。╠isjunctiondisjunction） 析取就是用連詞析取就是用連詞把幾個(gè)公式連把幾個(gè)公式連接起來(lái)而構(gòu)成的公式。析取項(xiàng)是析取式的每個(gè)組成部分。接起來(lái)而構(gòu)成的公式。析取項(xiàng)是析取式的每個(gè)組成部分。 v例：例：PLAYS(LILIPLAYS(LILI，BASKETBALL)PLAYS(LILIBASKETBALL)PL

41、AYS(LILI，F(xiàn)OOTBALL)FOOTBALL)v ( (李力打籃球或踢足球。李力打籃球或踢足球。) ) 2.3 謂詞邏輯法謂詞邏輯法 v2.3.1 謂詞演算（謂詞演算（Predicate Calculus）2.連詞和量詞連詞和量詞(Connective & Quantifiers) v(1) (1) 連詞連詞蘊(yùn)涵蘊(yùn)涵=表示表示 如果如果- -那么那么 的語(yǔ)句。用連詞的語(yǔ)句。用連詞=連接兩個(gè)公式所構(gòu)連接兩個(gè)公式所構(gòu)成的公式叫做蘊(yùn)涵。成的公式叫做蘊(yùn)涵。 v IFIF = = THEN THEN v 前項(xiàng)前項(xiàng) 后項(xiàng)后項(xiàng)v ( (左式左式) ) ( (右式右式) )v例：例：RUNS(

42、LIUHUARUNS(LIUHUA，F(xiàn)ASTEST) = TWINS(LIUHUAFASTEST) = TWINS(LIUHUA，CHAMPION) CHAMPION) v( (如果劉華跑得最快，那么他取得冠軍如果劉華跑得最快，那么他取得冠軍) )v非（非（NOTNOT） 表示否定，、表示否定，、均可表示否定。均可表示否定。v例：例：INROOM(ROBOTINROOM(ROBOT，r2)r2)v ( (機(jī)器人不在機(jī)器人不在2 2號(hào)房間內(nèi)。號(hào)房間內(nèi)。) )2.3 謂詞邏輯法謂詞邏輯法 v2.3.1 2.3.1 謂詞演算（謂詞演算（Predicate CalculusPredicate Calc

43、ulus）2.2.連詞和量詞連詞和量詞(Connective & Quantifiers)(Connective & Quantifiers) v(2) (2) 量詞量詞 全稱(chēng)量詞全稱(chēng)量詞(Universal Quantifier)(Universal Quantifier)若一個(gè)原子公式若一個(gè)原子公式P(x)P(x)，對(duì)于所有可，對(duì)于所有可能變量能變量x x都具有都具有T T值，則用值，則用( x)P(x)( x)P(x)表示。表示。v例：例：( x)ROBOT(x) = COLOR(x,GRAY)( x)ROBOT(x) = COLOR(x,GRAY)v ( (所有的機(jī)器人

44、都是灰色的）所有的機(jī)器人都是灰色的）v( x)Student(x) = Uniform(x,Color) ( x)Student(x) = Uniform(x,Color) v( (所有學(xué)生都穿彩色制服所有學(xué)生都穿彩色制服) )2.3 謂詞邏輯法謂詞邏輯法 v2.3.1 2.3.1 謂詞演算（謂詞演算（Predicate CalculusPredicate Calculus）2.2.連詞和量詞連詞和量詞(Connective & Quantifiers)(Connective & Quantifiers) v(2) (2) 量詞量詞 v存在量詞存在量詞(Existential

45、Quantifier)(Existential Quantifier)若一個(gè)原子公式若一個(gè)原子公式P(x)P(x)，至少有一個(gè)變?cè)辽儆幸粋€(gè)變?cè)猉 X，可使，可使P(X)P(X)為為T(mén) T值，則用值，則用( x)P(x)( x)P(x)表示。表示。 v例：例：( x)INROOM(x,r1)( x)INROOM(x,r1)v(1(1號(hào)房間內(nèi)有個(gè)物體號(hào)房間內(nèi)有個(gè)物體) )v量化變?cè)炕冊(cè)?Quantified Variables)(Quantified Variables)被量化了的變?cè)涣炕说淖冊(cè)獂-x-約束變量。約束變量。2.3 謂詞邏輯法謂詞邏輯法 v2.3.2 謂詞公式（謂詞公式（

46、Predicate Formulas）1.1.謂詞公式的定義謂詞公式的定義原子謂詞公式原子謂詞公式：用：用P(x1,x2,xn)P(x1,x2,xn)表示一個(gè)表示一個(gè)n n元謂詞公式，其中元謂詞公式，其中P P為為n n元元謂詞，謂詞，x1,x2,xnx1,x2,xn為客體變量或變?cè)Ｍǔ０褳榭腕w變量或變?cè)?。通常把P(x1,x2,xn)P(x1,x2,xn)叫做謂詞演算叫做謂詞演算的原子公式，或原子謂詞公式。的原子公式，或原子謂詞公式。 分子謂詞公式分子謂詞公式：可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它：可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。叫做分子謂詞公式

47、。合適公式合適公式(WFF,well-formed formulas)(WFF,well-formed formulas)的遞歸定義：的遞歸定義：(1) (1) 原子謂詞公式是合適公式。原子謂詞公式是合適公式。(2) (2) 若若A A為合適公式，則為合適公式，則A A也是一個(gè)合適公式。也是一個(gè)合適公式。(3) (3) 若若A A和和B B都是合適公式，則都是合適公式，則(AB),(AB),(A=B), (AB)(AB),(AB),(A=B), (AB)也都是也都是合適公式。合適公式。(4) (4) 若若A A是合適公式，是合適公式，x x為為A A中的自由變?cè)?，則中的自由變?cè)瑒t( x)A,

48、( x)A( x)A,( x)A都是合適公都是合適公式。式。(5) (5) 只有按上述規(guī)則只有按上述規(guī)則(1)(1)至至(4)(4)求得的那些公式，才是合適公式。求得的那些公式，才是合適公式。2.3 謂詞邏輯法謂詞邏輯法 v2.3.2 謂詞公式（謂詞公式（Predicate Formulas）1.謂詞公式的定義謂詞公式的定義v例題：v對(duì)于所有的x，如果x是整數(shù)，則x或?yàn)檎幕蛘邽樨?fù)的。v( x)(I(x)=(P(x)N(x)vI(x)表示x是整數(shù)，P(x)表示x是正數(shù)，N(x)表示x是負(fù)數(shù)。2.3 謂詞邏輯法謂詞邏輯法 v2.3.2 謂詞公式（謂詞公式（Predicate Formulas）2

49、.合適公式的性質(zhì)合適公式的性質(zhì)合適公式的真值：p36v表2-1 真值表2.3 謂詞邏輯法謂詞邏輯法 v2.3.3 置換與合一（置換與合一（Substitution & Unification）1.1.置換置換在謂詞邏輯中，有些推理規(guī)則可應(yīng)用于一定的合適公式和合適公在謂詞邏輯中，有些推理規(guī)則可應(yīng)用于一定的合適公式和合適公式集，以產(chǎn)生新的合適公式。一個(gè)重要的推理規(guī)則是假元推理，這就式集，以產(chǎn)生新的合適公式。一個(gè)重要的推理規(guī)則是假元推理，這就是由合適公式是由合適公式W1W1和和W1=W2W1=W2產(chǎn)生合適公式產(chǎn)生合適公式W2W2的運(yùn)算。另一個(gè)推理規(guī)則叫的運(yùn)算。另一個(gè)推理規(guī)則叫做全稱(chēng)化推理，它

50、是由合適公式做全稱(chēng)化推理，它是由合適公式( x)W(x)( x)W(x)產(chǎn)生合適公式產(chǎn)生合適公式W(A)W(A)，其中，其中A A為任意常量符號(hào)。為任意常量符號(hào)。假元推理：假元推理：vv 全稱(chēng)化推理：全稱(chēng)化推理：vv 綜合推理：綜合推理： v2.3 謂詞邏輯法謂詞邏輯法 v2.3.3 置換與合一（置換與合一（Substitution & Unification）1.1.置換置換置換：用項(xiàng)置換：用項(xiàng)(A)(A)替換函數(shù)表達(dá)式中的變量替換函數(shù)表達(dá)式中的變量(x)(x)，記為，記為ESES，即表示一，即表示一個(gè)表達(dá)式個(gè)表達(dá)式E(Expression)E(Expression)用一個(gè)置換用一個(gè)

51、置換S(Substitution)S(Substitution)而得到的表達(dá)式而得到的表達(dá)式的置換。的置換。例例1 1表達(dá)式表達(dá)式Px,f(y),BPx,f(y),B的的4 4個(gè)置換為個(gè)置換為 s1=z/x,w/ys1=z/x,w/ys2=A/ys2=A/y s3=q(z)/x,A/y s3=q(z)/x,A/y s4=c/x,A/y s4=c/x,A/yv我們用我們用EsEs來(lái)表示一個(gè)表達(dá)式來(lái)表示一個(gè)表達(dá)式E E用置換用置換s s所得到的表達(dá)式的置換。于是，所得到的表達(dá)式的置換。于是，我們可得到我們可得到Px,f(y),BPx,f(y),B的的4 4個(gè)置換的例，如下：個(gè)置換的例，如下：Px,

52、f(y),Bs1=Pz,f(w),BPx,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),BPx,f(y),Bs2=Px,f(A),B Px,f(y),Bs3=Pq(z),f(A),B Px,f(y),Bs3=Pq(z),f(A),BPx,f(y),Bs4=Pc,f(A),BPx,f(y),Bs4=Pc,f(A),B2.3 謂詞邏輯法謂詞邏輯法 v2.3.3 2.3.3 置換與合一（置換與合一（Substitution & UnificationSubstitution & Unification）2.2.性質(zhì)性質(zhì) v可結(jié)合律可結(jié)合律 (LS1)S2

53、=L(S1S2) (L(LS1)S2=L(S1S2) (L表示一表達(dá)式表示一表達(dá)式) )v (S1S2)S3=S1(S2S3) (S1S2)S3=S1(S2S3) v置換是可結(jié)合的。用置換是可結(jié)合的。用s1s2s1s2表示兩個(gè)置換表示兩個(gè)置換s1s1和和s2s2的合成。的合成。L L表示一表達(dá)表示一表達(dá)式，則有式，則有(Ls1)s2=L(s1s2)(Ls1)s2=L(s1s2)v以及以及(s1s2)s3=s1(s2s3)(s1s2)s3=s1(s2s3)即用即用s1s1和和s2s2相繼作用于表達(dá)式相繼作用于表達(dá)式L L是同用是同用s1s2s1s2作用于作用于L L一樣的。一樣的。一般說(shuō)來(lái)，置換

54、是不可交換的，即一般說(shuō)來(lái)，置換是不可交換的，即v s1s2s2s1s1s2s2s1v3.3.合一合一 (unification)P38(unification)P38v合一：尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致。合一：尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致?？珊弦唬喝绻粋€(gè)置換可合一：如果一個(gè)置換s s作用于表達(dá)式集作用于表達(dá)式集EiEi的每個(gè)元素，則我的每個(gè)元素，則我們用們用EisEis來(lái)表示置換例的集。我們稱(chēng)表達(dá)式集來(lái)表示置換例的集。我們稱(chēng)表達(dá)式集EiEi是可合一的。是可合一的。2.3 謂詞邏輯法謂詞邏輯法v2.3.3 2.3.3 置換與合一（置換與合一（Substitution &

55、 UnificationSubstitution & Unification）例:表達(dá)式集Px,f(y),B, Px,f(B),B的合一者為:s=A/x,B/y 因?yàn)镻x,f(y),Bs= Px,f(B),B=PA,f(B),B 即s使表達(dá)式成為單一形式: PA,f(B),B,但最簡(jiǎn)單的合一者為: s=B/Y 2.4 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法v語(yǔ)義網(wǎng)絡(luò)是語(yǔ)義網(wǎng)絡(luò)是19681968年年QuilianQuilian在研究人類(lèi)聯(lián)想記憶時(shí)提出的心理學(xué)模型，認(rèn)為在研究人類(lèi)聯(lián)想記憶時(shí)提出的心理學(xué)模型，認(rèn)為記憶是由概念間的聯(lián)系來(lái)實(shí)現(xiàn)的。記憶是由概念間的聯(lián)系來(lái)實(shí)現(xiàn)的。19721972年，年，Simmons

56、Simmons首先將語(yǔ)義網(wǎng)絡(luò)表示法用于首先將語(yǔ)義網(wǎng)絡(luò)表示法用于自然語(yǔ)言理解系統(tǒng)。自然語(yǔ)言理解系統(tǒng)。語(yǔ)義網(wǎng)絡(luò)的結(jié)構(gòu)：語(yǔ)義網(wǎng)絡(luò)是知識(shí)的一種語(yǔ)義網(wǎng)絡(luò)的結(jié)構(gòu)：語(yǔ)義網(wǎng)絡(luò)是知識(shí)的一種圖解表示圖解表示，它由節(jié)點(diǎn)和弧線(xiàn)或鏈，它由節(jié)點(diǎn)和弧線(xiàn)或鏈線(xiàn)組成。節(jié)點(diǎn)用于表示實(shí)體、概念和情況等，弧線(xiàn)用于表示節(jié)點(diǎn)間的關(guān)系。組線(xiàn)組成。節(jié)點(diǎn)用于表示實(shí)體、概念和情況等，弧線(xiàn)用于表示節(jié)點(diǎn)間的關(guān)系。組成部分成部分: :v1 1 詞法部分：決定表示詞匯表中允許有哪些符號(hào)，它涉及各個(gè)節(jié)點(diǎn)和弧線(xiàn)。詞法部分：決定表示詞匯表中允許有哪些符號(hào)，它涉及各個(gè)節(jié)點(diǎn)和弧線(xiàn)。v2 2 結(jié)構(gòu)部分：敘述符號(hào)排列的約束條件，指定各弧線(xiàn)連接的節(jié)點(diǎn)對(duì)。結(jié)構(gòu)部分：敘述

57、符號(hào)排列的約束條件，指定各弧線(xiàn)連接的節(jié)點(diǎn)對(duì)。v3 3 過(guò)程部分：說(shuō)明訪(fǎng)問(wèn)過(guò)程，這些過(guò)程能用來(lái)建立和修正描述，以及回答過(guò)程部分：說(shuō)明訪(fǎng)問(wèn)過(guò)程，這些過(guò)程能用來(lái)建立和修正描述，以及回答相關(guān)問(wèn)題。相關(guān)問(wèn)題。 v4 4 語(yǔ)義部分：確定與描述相關(guān)的語(yǔ)義部分：確定與描述相關(guān)的( (聯(lián)想聯(lián)想) )意義的方法即確定有關(guān)節(jié)點(diǎn)的排列意義的方法即確定有關(guān)節(jié)點(diǎn)的排列及其占有物和對(duì)應(yīng)弧線(xiàn)。及其占有物和對(duì)應(yīng)弧線(xiàn)。2.4 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法v2.4.1 二元語(yǔ)義網(wǎng)絡(luò)的表示二元語(yǔ)義網(wǎng)絡(luò)的表示 (Representation of Two-Element Semantic Network)1.表示簡(jiǎn)單的事實(shí)表示簡(jiǎn)單的事實(shí) 例例

58、1. 所有的燕子都是鳥(niǎo)所有的燕子都是鳥(niǎo) 2.4 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法v2.4.1 二元語(yǔ)義網(wǎng)絡(luò)的表示二元語(yǔ)義網(wǎng)絡(luò)的表示 (Representation of Two-Element Semantic Network)2.2.表示占有關(guān)系和其它情況表示占有關(guān)系和其它情況 P40P40v 例2. 小燕是一只燕子，燕子是鳥(niǎo)；巢-1是小燕的巢，巢-1是巢中的一個(gè)。 3.3.選擇語(yǔ)義基元選擇語(yǔ)義基元 試圖用一組基元來(lái)表示知識(shí)，以便簡(jiǎn)化表示，并可用簡(jiǎn)單的知識(shí)來(lái)表示更復(fù)雜的知識(shí)。 2.4 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法例3.我椅子的顏色是咖啡色的；椅子包套是皮革；椅子是一種家具；椅子是座位的一部分；椅子的所有者是X；

59、X是個(gè)人，如下圖所示：2.4 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法2.4.2 多元語(yǔ)義網(wǎng)絡(luò)的表示多元語(yǔ)義網(wǎng)絡(luò)的表示 語(yǔ)義網(wǎng)絡(luò)是一種網(wǎng)絡(luò)結(jié)構(gòu)。節(jié)點(diǎn)之間以鏈相連。多元語(yǔ)義網(wǎng)絡(luò)表示的實(shí)質(zhì)：把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。如果所要表示的知識(shí)是一元關(guān)系，例如，要表示李明是一個(gè)人，這在謂詞邏輯中可表示為MAN(LIMING)。用語(yǔ)義網(wǎng)絡(luò)，這就可以表示為:與這樣的表示法相等效的關(guān)系在謂詞邏輯中表示為ISA(LIMING，MAN)。這說(shuō)明語(yǔ)義網(wǎng)絡(luò)可以毫無(wú)困難地表示一元關(guān)系。 2.4 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法 例如：要表達(dá)北京大學(xué)例如：要表達(dá)北京大學(xué)(BEIJING University,(BEIJING U

60、niversity,簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)BU)BU)和清華大學(xué)和清華大學(xué)(TSINGHUA(TSINGHUA University, University,簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)TU)TU)兩校籃球隊(duì)在北大進(jìn)行的一場(chǎng)比賽的比分是兩?；@球隊(duì)在北大進(jìn)行的一場(chǎng)比賽的比分是8585比比8989。 若用謂詞邏輯可表示為若用謂詞邏輯可表示為SCORE(BUSCORE(BU，TUTU，(85-89)(85-89)。這個(gè)表示式中包含。這個(gè)表示式中包含3 3項(xiàng)，而項(xiàng)，而語(yǔ)義網(wǎng)絡(luò)從本質(zhì)上來(lái)說(shuō)，只能表示二元關(guān)系。解決這個(gè)矛盾的一種方法是把這個(gè)多語(yǔ)義網(wǎng)絡(luò)從本質(zhì)上來(lái)說(shuō)，只能表示二元關(guān)系。解決這個(gè)矛盾的一種方法是把這個(gè)多元關(guān)系轉(zhuǎn)化成一組二元關(guān)系的組合，或二元關(guān)系的合取。元關(guān)系轉(zhuǎn)化成一組二元關(guān)系的組合，或二元關(guān)系的合取。 具體來(lái)說(shuō)，多元關(guān)系具體來(lái)說(shuō)，多元關(guān)系R(X1R(