人工智能第二章-知識(shí)表示方法課件

第二章知識(shí)表示方法教材：蔡自興等《人工智能及其應(yīng)用》（第4版）清華大學(xué)出版社，2010.5華科大自動(dòng)化學(xué)院第二章知識(shí)表示方法教材：華科大自動(dòng)化學(xué)院第二章知識(shí)表示方法人類的智能活動(dòng)主要是獲得并運(yùn)用知識(shí)。知識(shí)是智能的基礎(chǔ)。為了使計(jì)算機(jī)具有智能，能模擬人類的智能行為，就必須使它具有知識(shí)。但知識(shí)需要用適當(dāng)?shù)哪Ｊ奖硎境鰜?lái)才能存儲(chǔ)到計(jì)算機(jī)中去，因此，知識(shí)的表示成為人工智能中一個(gè)十分重要的研究課題。本章將首先介紹知識(shí)與知識(shí)表示的概念，然后介紹狀態(tài)空間法、問題歸約法、謂詞邏輯法、語(yǔ)義網(wǎng)絡(luò)法、框架表示、本體技術(shù)、過程表示等當(dāng)前人工智能中應(yīng)用比較廣泛的知識(shí)表示方法，為后面介紹推理方法、專家系統(tǒng)等奠定基礎(chǔ)。2第二章知識(shí)表示方法人類的智能活動(dòng)主要是獲得并運(yùn)用知識(shí)。知識(shí)是第二章知識(shí)表示方法2.1知識(shí)與知識(shí)表示的概念

2.2狀態(tài)空間法2.3問題歸約法2.4謂詞邏輯法2.5語(yǔ)義網(wǎng)絡(luò)法2.6框架表示2.7本體技術(shù)2.8過程表示2.9小結(jié)3第二章知識(shí)表示方法2.1知識(shí)與知識(shí)表示的概念32.1.1知識(shí)的概念知識(shí)：在長(zhǎng)期的生活及社會(huì)實(shí)踐中、在科學(xué)研究及實(shí)驗(yàn)中積累起來(lái)的對(duì)客觀世界的認(rèn)識(shí)與經(jīng)驗(yàn)。知識(shí)：把有關(guān)信息關(guān)聯(lián)*在一起所形成的信息結(jié)構(gòu)。知識(shí)反映了客觀世界中事物之間的關(guān)系，不同事物或者相同事物間的不同關(guān)系形成了不同的知識(shí)*。

信息關(guān)聯(lián)形式：“如果……，則……”

如果大雁向南飛，則冬天就要來(lái)臨了。

——規(guī)則——事實(shí)例如：

“雪是白色的”。

“如果頭痛且流涕，則有可能患了感冒”。2.1知識(shí)與知識(shí)表示的概念

42.1.1知識(shí)的概念知識(shí)：在長(zhǎng)期的生活及社會(huì)實(shí)踐中、在科學(xué)2.1.1知識(shí)的概念Feigenbaum認(rèn)為知識(shí)是經(jīng)過加工的信息，它包括事實(shí)、信念和啟發(fā)式規(guī)則。Bernstein說(shuō)知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過程組成的。Hayes-Roth認(rèn)為知識(shí)是事實(shí)、信念和啟發(fā)式規(guī)則。知識(shí)庫(kù)觀點(diǎn)看，知識(shí)是某論域中所涉及的各有關(guān)方面、狀態(tài)的一種符號(hào)表示。52.1.1知識(shí)的概念Feigenbaum認(rèn)為知識(shí)是經(jīng)過加工2.1.1知識(shí)的概念人工智能系統(tǒng)所關(guān)心的知識(shí)事實(shí)：是關(guān)于對(duì)象和物體的知識(shí)。規(guī)則：是有關(guān)問題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系的知識(shí)。元知識(shí)：是有關(guān)知識(shí)的知識(shí)，是知識(shí)庫(kù)中的高層知識(shí)。包括怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等。常識(shí)性知識(shí)：泛指普遍存在而且被普遍認(rèn)識(shí)了的客觀事實(shí)一類知識(shí)。

2.1知識(shí)與知識(shí)表示的概念

62.1.1知識(shí)的概念人工智能系統(tǒng)所關(guān)心的知識(shí)2.1知識(shí)與知2.1.2知識(shí)的特性1.相對(duì)正確性任何知識(shí)都是在一定的條件及環(huán)境下產(chǎn)生的*，在這種條件及環(huán)境下才是正確的。1+1=2

（十進(jìn)制）1+1=10(二進(jìn)制）2.1知識(shí)與知識(shí)表示的概念

72.1.2知識(shí)的特性1.相對(duì)正確性1+1=2（十進(jìn)2.1.2知識(shí)的特性不確定性*隨機(jī)性引起的不確定性*

模糊性引起的不確定性*經(jīng)驗(yàn)引起的不確定性不完全性引起的不確定性(常識(shí)性？？）知識(shí)狀態(tài)：“真”

“假”

“真”與“假”之間的中間狀態(tài)

“如果頭痛且流涕，則有可能患了感冒”

小李很高2.1知識(shí)與知識(shí)表示的概念

82.1.2知識(shí)的特性不確定性*隨機(jī)性引起的不確定性*2.1.2知識(shí)的特性

可表示性與可利用性知識(shí)的可表示性:知識(shí)可以用適當(dāng)形式表示出來(lái)，如用語(yǔ)言、文字、圖形、神經(jīng)網(wǎng)絡(luò)等。知識(shí)的可利用性:知識(shí)可以被利用。2.1知識(shí)與知識(shí)表示的概念

92.1.2知識(shí)的特性可表示性與可利用性2.1知識(shí)與知識(shí)2.1.3知識(shí)的表示知識(shí)表示就是研究用機(jī)器表示上述這些知識(shí)的可行性、有效性的一般方法，可以看作是將知識(shí)符號(hào)化并輸入到計(jì)算機(jī)的過程和方法。知識(shí)表示=數(shù)據(jù)結(jié)構(gòu)+處理機(jī)制知識(shí)表示的觀點(diǎn)：陳述性過程性102.1.3知識(shí)的表示知識(shí)表示就是研究用機(jī)器表示上述這些知識(shí)2.1.3知識(shí)的表示陳述性知識(shí)表示和過程性知識(shí)表示各有優(yōu)缺點(diǎn)由于高級(jí)的智能行為似乎強(qiáng)烈地依賴于陳述性知識(shí)，因此AI的研究應(yīng)注重陳述性的開發(fā)。過程性知識(shí)的陳述化表示。以適當(dāng)方式將過程性知識(shí)和陳述性知識(shí)綜合，可以提高智能系統(tǒng)的性能。112.1.3知識(shí)的表示陳述性知識(shí)表示和過程性知識(shí)表示各有優(yōu)缺2.1.3知識(shí)的表示策略知識(shí)關(guān)于如何解決問題的政策方略，包括在什么時(shí)間、什么地點(diǎn)、由什么主體采取什么行動(dòng)、達(dá)到什么目標(biāo)、注意什么事項(xiàng)等等一整套完整而具體的行動(dòng)計(jì)劃規(guī)劃、行動(dòng)步驟、工作方式和工作方法。122.1.3知識(shí)的表示策略知識(shí)122.1.3知識(shí)的表示“智能”在給定的問題——問題環(huán)境——主體目的的條件下，有針對(duì)性地獲取問題——環(huán)境的信息，恰當(dāng)?shù)貙?duì)這些信息進(jìn)行處理以提煉知識(shí)達(dá)到認(rèn)知，在此基礎(chǔ)上，把已有的知識(shí)與主體的目的信息相結(jié)合，合理地產(chǎn)生解決問題的策略信息，并利用所得到的策略信息在給定的環(huán)境下成功地解決問題達(dá)到主體的目的。132.1.3知識(shí)的表示“智能”132.1.4智能中“信息-知識(shí)-策略”關(guān)系4個(gè)要素包括信息知識(shí)策略行為4個(gè)能力包括獲取有用信息的能力由信息生成知識(shí)(認(rèn)知)的能力由知識(shí)和目的生成策略(決策)的能力實(shí)施策略取得效果(施效)的能力142.1.4智能中“信息-知識(shí)-策略”關(guān)系4個(gè)要素包括142.1.4智能中“信息-知識(shí)-策略”關(guān)系信息、知識(shí)、智能之間的關(guān)系：信息是基本資源；知識(shí)是對(duì)信息進(jìn)行加工所得到的抽象化產(chǎn)物；策略是由客體信息和主體目標(biāo)演繹出來(lái)的智慧化身，智能是把信息資源加工成知識(shí)、進(jìn)而把知識(shí)激活成解決問題的策略并在策略信息引導(dǎo)下具體解決問題的全部能力。

信息、知識(shí)、智能關(guān)系，正好符合人類自身認(rèn)識(shí)世界和優(yōu)化世界活動(dòng)過程中由信息生成知識(shí)、由知識(shí)激活智能的過程總結(jié)：信息經(jīng)加工提煉而成知識(shí)，知識(shí)被目的激活而成智能。152.1.4智能中“信息-知識(shí)-策略”關(guān)系信息、知識(shí)、智能之間2.1.4智能中“信息-知識(shí)-策略”關(guān)系獲取信息的功能由感覺器官完成，傳遞信息的功能由神經(jīng)系統(tǒng)完成，處理信息和再生信息的功能由思維器官完成，施用信息的功能由效應(yīng)器官完成。162.1.4智能中“信息-知識(shí)-策略”關(guān)系獲取信息的功能由感2.1.5AI對(duì)知識(shí)表示方法的要求表示能力，要求能夠正確、有效地將問題求解所需要的各類知識(shí)都表示出來(lái)?？衫斫庑?，所表示的知識(shí)應(yīng)易懂、易讀。便于知識(shí)的獲取，使得智能系統(tǒng)能夠漸進(jìn)地增加知識(shí)，逐步進(jìn)化。便于搜索，表示知識(shí)的符號(hào)結(jié)構(gòu)和推理機(jī)制應(yīng)支持對(duì)知識(shí)庫(kù)的高效搜索，使得智能系統(tǒng)能夠迅速地感知事物之間的關(guān)系和變化；同時(shí)很快地從知識(shí)庫(kù)中找到有關(guān)的知識(shí)。便于推理，要能夠從己有的知識(shí)中推出需要的答案和結(jié)論。172.1.5AI對(duì)知識(shí)表示方法的要求表示能力，要求能夠正確、2.1.6知識(shí)的分類形態(tài)性知識(shí)、內(nèi)容性知識(shí)、效用性知識(shí)三者的綜合，構(gòu)成了知識(shí)的完整概念182.1.6知識(shí)的分類形態(tài)性知識(shí)、內(nèi)容性知識(shí)、效用性知識(shí)第二章知識(shí)表示方法2.1知識(shí)與知識(shí)表示的概念

2.2狀態(tài)空間法2.3問題歸約法2.4謂詞邏輯法2.5語(yǔ)義網(wǎng)絡(luò)法2.6框架表示2.7本體技術(shù)2.8過程表示2.9小結(jié)19第二章知識(shí)表示方法2.1知識(shí)與知識(shí)表示的概念192.2狀態(tài)空間法

（StateSpaceRepresentation）問題求解技術(shù)主要是兩個(gè)方面：?jiǎn)栴}的表示：同一問題有多種不同的表示求解的方法1：許多問題求解方法采用試探搜索方法狀態(tài)空間法：基于解答空間的問題表示和求解方法狀態(tài)（state）算符（operator）狀態(tài)空間方法2.2狀態(tài)空間法

202.2狀態(tài)空間法

（StateSpaceRepresen2.2.1

問題狀態(tài)描述狀態(tài)定義：描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合。其矢量形式如下：Q=［q0,q1,…,qn］T式中每個(gè)元素qi(i=0,1，…，n)為集合的分量，稱為狀態(tài)變量。給定每個(gè)分量的一組值就得到一個(gè)具體的狀態(tài)，如：

qk=［q０k,q1k,…,qnk］T

2.1狀態(tài)空間法212.2.1問題狀態(tài)描述狀態(tài)2.1狀態(tài)空間法212.2.1問題狀態(tài)描述初始狀態(tài)：由問題已知條件的原始描述所構(gòu)成的狀態(tài)目標(biāo)狀態(tài)：?jiǎn)栴}解決時(shí)應(yīng)該到達(dá)的狀態(tài)算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段，操作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。狀態(tài)空間：一個(gè)表示該問題全部可能狀態(tài)及其關(guān)系的圖，包含三種說(shuō)明的集合，即所有可能的問題初始狀態(tài)集合S、

操作符集合F以及目標(biāo)狀態(tài)集合G?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。2.2狀態(tài)空間法222.2.1問題狀態(tài)描述初始狀態(tài)：由問題已知條件的原始描述狀態(tài)空間表示概念詳釋OriginalStateMiddleStateGoalState2.2狀態(tài)空間法對(duì)一個(gè)問題的狀態(tài)描述，必須確定3件事：該狀態(tài)描述方式，特別是初始狀態(tài)描述；操作符集合及其對(duì)狀態(tài)描述的作用；目標(biāo)狀態(tài)的描述。例如：數(shù)碼難題。23狀態(tài)空間表示概念詳釋OriginalMiddleGoal2.例1:三數(shù)碼難題

（3puzzleproblem）123123123312312312初始棋局目標(biāo)棋局2.2狀態(tài)空間法24例1:三數(shù)碼難題

（3puzzleproblem）123圖論的基本概念有向圖路徑代價(jià)圖的顯示說(shuō)明圖的隱示說(shuō)明2.2.2狀態(tài)圖示法AB2.2狀態(tài)空間法25圖論的基本概念2.2.2狀態(tài)圖示法AB2.2狀態(tài)空間法2圖論的基本概念有向圖(directedgraph)：節(jié)點(diǎn)(node)：圖形上的匯合點(diǎn)，用來(lái)表示狀態(tài)、事件和時(shí)間關(guān)系的匯合，也可用來(lái)指示通路的匯合；后繼節(jié)點(diǎn)(descendantnode)與父輩節(jié)點(diǎn)(parentnode)：如果某條弧線從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj，那么節(jié)點(diǎn)nj就叫做節(jié)點(diǎn)ni的后繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn)ni叫做節(jié)點(diǎn)nj的父輩節(jié)點(diǎn)或祖先?；【€(arc)：節(jié)點(diǎn)間的連接線；有向圖(directedgraph)：圖由節(jié)點(diǎn)（不一定是有限的節(jié)點(diǎn)）的集合構(gòu)。一對(duì)節(jié)點(diǎn)用弧線連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)。

2.2狀態(tài)空間法

26圖論的基本概念有向圖(directedgraph)： 2.圖論的基本概念路徑：某個(gè)節(jié)點(diǎn)序列(n1,n2,…,nk)，當(dāng)j=2，3，…，k時(shí)，如果對(duì)于每一個(gè)nj-1都有一個(gè)后繼節(jié)點(diǎn)nj存在，那么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)n1至節(jié)點(diǎn)nk的長(zhǎng)度為k的路徑。如果從節(jié)點(diǎn)ni到節(jié)點(diǎn)nj存在有一條路經(jīng)，則稱nj是從ni可達(dá)到的節(jié)點(diǎn)。尋找從一種狀態(tài)變換成另一種狀態(tài)的某個(gè)算符序列問題等價(jià)于尋求圖的某一路徑問題。

2.2狀態(tài)空間法

27圖論的基本概念路徑：某個(gè)節(jié)點(diǎn)序列(n1,n2,…,nk)，當(dāng)圖論的基本概念代價(jià)：衡量狀態(tài)之間轉(zhuǎn)變所需的時(shí)間、精力等量化的值。用c(ni,nj)來(lái)表示從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj的弧線的代價(jià)。兩節(jié)點(diǎn)間路徑的代價(jià)等于連接該路徑上各節(jié)點(diǎn)的所有弧線代價(jià)之和。對(duì)于最優(yōu)化問題，就要找兩節(jié)點(diǎn)間具有最小代價(jià)的路徑。顯式表示：各節(jié)點(diǎn)及其具有代價(jià)的弧線由一張表明確給出。此表可能列出該圖中的每一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及連接弧線的代價(jià)。問題：對(duì)于大型圖和具有無(wú)限節(jié)點(diǎn)集合的圖不適用。

2.2狀態(tài)空間法

28圖論的基本概念代價(jià)：衡量狀態(tài)之間轉(zhuǎn)變所需的時(shí)間、精力等量化的圖論的基本概念

隱式表示：起始節(jié)點(diǎn)的無(wú)限集合{si}和后繼節(jié)點(diǎn)算符Γ是已知的。算符Γ能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線的代價(jià)。1節(jié)點(diǎn)擴(kuò)展：將后繼算符Γ應(yīng)用于節(jié)點(diǎn)的過程，就是擴(kuò)展一個(gè)節(jié)點(diǎn)的過程。問題求解：搜索某個(gè)狀態(tài)空間以求得算符序列的一個(gè)解答的過程，就對(duì)應(yīng)于使隱式圖足夠大一部分變?yōu)轱@示以便包含目標(biāo)節(jié)點(diǎn)的過程。優(yōu)化：?jiǎn)栴}的表示對(duì)求解工作量有很大的影響。優(yōu)化的問題表示使?fàn)顟B(tài)空間小而簡(jiǎn)單，從而便于求解。許多似乎很難的問題，當(dāng)表示適當(dāng)時(shí)就可能具有小而簡(jiǎn)單的狀態(tài)空間。2.2狀態(tài)空間法

29圖論的基本概念 隱式表示：起始節(jié)點(diǎn)的無(wú)限集合{si}和后繼節(jié)嘗試各種不同的走步，直到偶然得到目標(biāo)棋局為止。

1

2

3

8

4

7

6

5目標(biāo)狀態(tài)例2：九宮排序（八數(shù)碼問題）2.2狀態(tài)空間法

12

38

47

652

31

8

47

6

5初始狀態(tài)2

31

8

47

6

52

31

8

47

6

52

31

8

47

6

52

8

31

47

6

52

31

8

47652

341876530 123例2：九宮排序（八數(shù)碼問題）2.2狀態(tài)空間法規(guī)則：如果針對(duì)每個(gè)數(shù)碼來(lái)規(guī)定規(guī)則(上下左右移動(dòng))，則需要8*4=32條規(guī)則，如果針對(duì)空格來(lái)規(guī)定規(guī)則，則只需要4條規(guī)則。R1：IF

空格上方有棋THEN

空格上移R2：IF

空格右方有棋THEN

空格右移R3：IF

空格下方有棋THEN

空格下移R4：IF

空格左方有棋THEN

空格左移求解的方法：首先把適用的算符用于初始狀態(tài)，以產(chǎn)生新的狀態(tài)；然后，再把另一些適用算符用于這些新的狀態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標(biāo)狀態(tài)為止。2.2狀態(tài)空間法

31規(guī)則：如果針對(duì)每個(gè)數(shù)碼來(lái)規(guī)定規(guī)則(上下左右移動(dòng))，則需要8*九宮排序（寬度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765125673123847658432九宮排序（寬度優(yōu)先搜索）232九宮排序（深度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

83214765281437652831457612378465123847652836417528316754832147652837146528143765283145761238476523456789abcd133九宮排序（深度優(yōu)先搜索）2322.2.3狀態(tài)空間表示舉例產(chǎn)生式系統(tǒng)（productionsystem）一個(gè)總數(shù)據(jù)庫(kù)：它含有與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫(kù)可能簡(jiǎn)單，或許復(fù)雜。一套規(guī)則：它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時(shí)所完成的動(dòng)作。一個(gè)控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)算。2.1狀態(tài)空間法342.2.3狀態(tài)空間表示舉例產(chǎn)生式系統(tǒng)（production用顯式說(shuō)明（列表）表示狀態(tài)圖，表中放有旅行商經(jīng)過的城市，表中最后一個(gè)元素就是旅行商當(dāng)前所在的城市。初始數(shù)據(jù)庫(kù)：（A）目標(biāo)數(shù)據(jù)庫(kù)：（A,…….,A)規(guī)則：R1：IF

沒有去過B

THEN

下一步去BR2：IF

沒有去過C

THEN

下一步去CR3：IF

沒有去過D

THEN

下一步去DR4：IF

沒有去過E

THEN

下一步去ER5：IF

都去過了THEN

下一步去AA5722341

431BEDC例3：旅行商問題2.2狀態(tài)空間法

35用顯式說(shuō)明（列表）表示狀態(tài)圖，A572234131BEDC例2.2.3狀態(tài)空間表示舉例產(chǎn)生式系統(tǒng)（productionsystem）數(shù)據(jù)庫(kù)（事實(shí)庫(kù)）：含有與具體任務(wù)有關(guān)的信息,隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫(kù)可能簡(jiǎn)單，或許復(fù)雜。規(guī)則（知識(shí)庫(kù)）：它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左部鑒別規(guī)則的適用性或前提條件以及右部描述規(guī)則應(yīng)用時(shí)所完成的操作?？刂撇呗?：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)算。2.2狀態(tài)空間法362.2.3狀態(tài)空間表示舉例產(chǎn)生式系統(tǒng)（production例4：猴子和香蕉問題在一個(gè)房間內(nèi)有一只猴子（可把這只猴子看做一個(gè)機(jī)器人）、一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么猴子怎樣才能摘到香蕉呢？2.2狀態(tài)空間法1.綜合數(shù)據(jù)庫(kù)：用一個(gè)四元表列(W,x,Y,z)來(lái)表示這個(gè)問題的狀態(tài)：W：猴子的水平位置；X：當(dāng)猴子在箱子頂上時(shí)x=1；否則x=0；Y：箱子的水平位置，Z：當(dāng)猴子摘到香蕉時(shí)z=1；否則z=037例4：猴子和香蕉問題在一個(gè)房間內(nèi)有一只猴子（2.2狀態(tài)空間法pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）（2）climbbox猴子爬上箱頂，即有（W，0，W，z）climbbox（W，1，W，z）（3）grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）

（4）goto（U）表示猴子走到水平位置（W，0，Y，z）goto（U）（U，0，Y，z）（1）2.規(guī)則庫(kù)這個(gè)問題的操作（算符）以及產(chǎn)生式規(guī)則表示如下：382.2狀態(tài)空間法pushbox（V）猴子把箱子推到水平位置2.2狀態(tài)空間法3.控制策略試探性方式4.初始條件初始狀態(tài)為(a,0,b,0)5.結(jié)束條件達(dá)到狀態(tài)(c,1,c,1)abc(a,0,b,0)初始狀態(tài)

猴子香蕉箱子goto(b)

猴子香蕉箱子

(b,0,b,0)climbbox

pushbox(c)

(c,0,c,0)goto(U)goto(U)pushbox(V)

climbbox

(c,1,c,0)

grasp(c,1,c,1)目標(biāo)狀態(tài)

Ha!Ha!求解結(jié)果：該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列{goto(b),pushbox(c),climbbox,grasp}狀態(tài)空間圖(求解過程1):392.2狀態(tài)空間法3.控制策略abc(a,0,b,0)初始狀例5：設(shè)字符轉(zhuǎn)換規(guī)則A∧B→C，A∧C→D，B∧C→G，B∧E→F，D→E?，F(xiàn)在已知：A和B，求：F。1.綜合數(shù)據(jù)庫(kù)3.控制策略{x}，其中x為字符順序排隊(duì)2.規(guī)則集(用產(chǎn)生式系統(tǒng)來(lái)描述）4.初始條件IFA∧BTHENC

{A，B}

IFA∧CTHEND

5.結(jié)束條件IFB∧CTHENG

F∈{x}IFB∧ETHENFIFDTHENE40例5：設(shè)字符轉(zhuǎn)換規(guī)則A∧B→C，A∧C→D，B∧C→G，B1、IF

A∧B

THEN

C2、IF

A∧C

THEN

D3、IF

B∧C

THEN

G4、IF

B∧E

THEN

F5、IF

D

THEN

E

初始條件{A，B}

結(jié)束條件F∈{x}

A,B,C,D（3）（5）（2）（3）

A,B

A,B,C（1）

A,B,C,D,G,E,F

A,B,C,D,G,E（4）

A,B,C,D,G（5）初始狀態(tài)例3問題的狀態(tài)空間圖411、IFA∧BTHENCA,B,C,D（3）（N個(gè)傳教士，N個(gè)野人，一條船，可同時(shí)乘坐k個(gè)人乘渡。傳教士為安全起見，應(yīng)如何規(guī)定擺渡方案，使得任何時(shí)刻，當(dāng)傳教士與野人在同一地點(diǎn)(河兩岸以及船上)時(shí)，野人數(shù)目總是不超過傳教士的數(shù)目。傳教士與野人均可擺渡。左岸右岸M30C30B10左岸右岸M03C03B01初始狀態(tài)目標(biāo)狀態(tài)例6：傳教士與野人問題（M-C問題）：以N=3(傳教士或野人數(shù))，k=2(每條船的載人數(shù))為例求解。42N個(gè)傳教士，N個(gè)野人，一條船，可同時(shí)乘坐k個(gè)人乘渡。傳教士為求解過程如下：1.綜合數(shù)據(jù)庫(kù)用(m,c,b)表示左岸傳教士人數(shù)、野人人數(shù)和船的狀態(tài)（b=0無(wú)船，b=1有船）：0≤m,c≤3,b∈{0,1}。2.規(guī)則集IF(m,c,1)THEN(m-1,c,0)

IF

(m,

c,

0)

THEN

(m+1,

c,

1)IF

(m,c,

1)

THEN

(m,

c-1,

0)

IF

(m,

c,

0)

THEN

(m,

c+1,

1)IF(m,c,1)THEN(m-1,c-1,0)

IF

(m,

c,

0)

THEN

(m+1,

c+1,

1)

IF

(m,c,

1)

THEN

(m-2,

c,

0)

IF(m,c,0)THEN(m+2,c,1)IF(m,c,1)THEN(m,c-2,0)

IF

(m,

c,

0)

THEN

(m,

c+2,

1)

太繁瑣！43求解過程如下：43也可以定義為：IF(m,c,1)∧(1≤i+j≤2)∧{(c-j≤m-i∨

m-i=0)∧(3-c+j≤3-m+i

∨3-m+i=0)}THEN(m-i,c-j,0)IF(m,c,0)∧(1≤i+j≤2)∧{(c+j≤m+i∨m+i=0)∧(3-c-j≤3-m-i

∨3-m-i=0)}THEN(m+i,c+j,0)3.控制策略

試探性方式4.初始條件

(3,3,1)5.結(jié)束條件

（0,0,0）44也可以定義為：446.繪制狀態(tài)空間圖(3,3,1)(2,2,0)(3,1,0)(0,2,1)(1,1,1)(0,3,1)(2,2,1)(3,1,1)(3,2,1)(3,0,0)(3,2,0)(0,0,0)(0,1,0)(0,2,0)(1,1,0)(1)IF(m,c,1)THEN(m-1,c,0)

(2)IF

(m,

c,

0)

THEN

(m+1,

c,

1)(3)IF

(m,

c,

1)

THEN

(m,

c-1,

0)

(4)IF

(m,

c,

0)

THEN

(m,

c+1,

1)(5)IF(m,c,1)THEN(m-1,c-1,0)

(6)IF

(m,

c,

0)

THEN

(m+1,c+1,1)

(7)IF

(m,

c,

1)

THEN

(m-2,

c,

0)

(8)IF(m,

c,0)THEN(m+2,c,1)(9)IF(m,c,1)THEN(m,c-2,0)(10)IF

(m,

c,

0)

THEN

(m,

c+2,

1)(3)(9)(9)(5)(7)(9)(7)(5)(9)(4)(2)(4)(6)(4)(6)(4)456.繪制狀態(tài)空間圖(3,3,1)(2,2,0)(3,1,02.3問題歸約法

（ProblemReductionRepresentation）子問題1子問題n原始問題子問題集本原問題問題歸約是另一種基于狀態(tài)空間的問題描述與求解方法。已知問題的描述，通過一系列變換把此問題最終變?yōu)橐粋€(gè)子問題集合；這些子問題的解可以直接得到，從而解決了初始問題。462.3問題歸約法

（ProblemReductionRe例1：假定會(huì)求矩形的面積，現(xiàn)在要求如圖所示的五邊形的面積。II①②2III

③

3

I1求五邊形面積?

1面積?

2面積?

3面積①面積②面積③面積I面積II面積III面積47例1：假定會(huì)求矩形的面積，現(xiàn)在要求如圖所示的五邊形的面積問題歸約表示的組成部分：一個(gè)初始問題描述；一套把問題變換為子問題的操作符；一套本原問題描述。問題歸約的實(shí)質(zhì)：從目標(biāo)(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個(gè)平凡的本原問題集合。2.3

問題規(guī)約法48問題歸約表示的組成部分：?jiǎn)栴}歸約的實(shí)質(zhì)：2.3問題規(guī)約法2.3.1問題歸約描述

（ProblemReductionDescription）1.梵塔難題12.3

問題規(guī)約法最初，全部3個(gè)圓從大B到小堆放在第1個(gè)柱子上，要求把所有圓盤從大到小堆放在第3個(gè)柱子上。每次只許移動(dòng)一個(gè)，并且只能先搬動(dòng)柱子頂上的圓盤，還不能把大的圓盤堆放在較小的圓盤上。CC

AB初始狀態(tài)

AB目標(biāo)狀態(tài)1

2

3492.3.1問題歸約描述

（ProblemReductio梵塔難題求解12.3

問題規(guī)約法把原始問題規(guī)約為一個(gè)較簡(jiǎn)單的問題集合：要把所有的圓盤移到柱子3，首先把圓盤C移至柱子3；而且在其之前，要求柱子3是空的。只有移開A、B之后，才能移動(dòng)C；且A、B最好不要移至柱子3，否則C不能移至柱子3。因此首先把A、B移至柱子2上。然后，把C從柱子1移至柱子3，并繼續(xù)解決難題的其他部分。CC

AB初始配置

AB目標(biāo)配置1

2

350梵塔難題求解12.3問題規(guī)約法把原始問題規(guī)約為一個(gè)較簡(jiǎn)單的C

ABC

AB（3,3,3）目標(biāo)配置C

ABC

AB子問題(1,1,1)初始配置C

AB(1,2,2)(3,2,2)

(3,3,3)上述分析允許把原始難題歸約（簡(jiǎn)化）為3個(gè)子難題：移動(dòng)圓盤A、B至柱子2的雙圓盤難題。移動(dòng)圓盤C至柱子3的單元盤難題。移到圓盤A、B至柱子3的雙圓盤難題。①②③51C AC A（3,3,3）目標(biāo)配置C AC A子(1,1,1梵塔問題歸約圖1（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

2.3

問題規(guī)約法將所有的子問題歸約為本原問題，最后畫出與或圖(AND/ORgraph)，來(lái)說(shuō)明如何由問題歸約法求得問題的解答。52梵塔問題歸約圖1（113）（123）（111）2.問題歸約描述問題歸約方法應(yīng)用算符來(lái)將問題描述變換為子為題描述。問題描述可以有各種數(shù)據(jù)結(jié)構(gòu)形式：表列、樹、字符串、矢量、數(shù)組等。對(duì)于梵塔難題，其子問題可以用一個(gè)包含兩個(gè)數(shù)列的表列來(lái)描述：[(113),(333)]表示把初始配置(1,1,3)變換為目標(biāo)配置(3,3,3)1。可以用狀態(tài)空間表示的三元組(S,F,G)來(lái)規(guī)定與描述問題。可將有關(guān)子問題當(dāng)作狀態(tài)空間中兩個(gè)一定的“腳踏石”之間尋找路徑的問題來(lái)處理。對(duì)于梵塔難題，子問題[(111)→(122)]，[(122)→(322)],[(322)→(333)]規(guī)定了最后解答路徑要通過的腳踏石狀態(tài)(122)和(322)。532.問題歸約描述問題歸約方法應(yīng)用算符來(lái)將問題描述變換為子為題問題歸約法與狀態(tài)空間法之間的不同點(diǎn)與關(guān)系：?jiǎn)栴}歸約可以應(yīng)用狀態(tài)、算符和目標(biāo)這些表示法來(lái)描述問題，這并不意味問題歸約和狀態(tài)空間法是一樣的。實(shí)際上，遞增狀態(tài)空間搜索應(yīng)用某個(gè)問題歸約的普通形式，而問題歸約法是比狀態(tài)空間法更普通的一種問題求解方法。把問題描述變換為一個(gè)歸約或后續(xù)問題描述的集合，這是由問題歸約算符進(jìn)行的。變換得到的所有后續(xù)問題的解就是父輩問題的一個(gè)解所用問題歸約的目的是最終產(chǎn)生具有明顯解答的本原問題。這些問題可能是能夠由狀態(tài)空間搜索中走動(dòng)一步來(lái)解決問題，或者可能是其他具有已知解答的更復(fù)雜的問題。本源問題除了對(duì)終止搜索過程起到明顯的作用外，有時(shí)還被用來(lái)限制歸約過程中產(chǎn)生后續(xù)問題的替代集合。154問題歸約法與狀態(tài)空間法之間的不同點(diǎn)與關(guān)系：542.2.2與或圖表示1.與圖、或圖、與或圖與或圖能夠方便的用一個(gè)類似于圖的結(jié)構(gòu)來(lái)表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖（與或圖）1。2.3

問題規(guī)約法ABCD與圖ABC或圖552.2.2與或圖表示1.與圖、或圖、與或圖2.3問題規(guī)約法2.3

問題規(guī)約法BCDEFGAHMBCDEFGAN圖2.6子問題替換集合結(jié)構(gòu)圖圖2.7一個(gè)與或圖562.3問題規(guī)約法BCDEFGAHMBCDEFGAN圖2.62.與或圖的術(shù)語(yǔ)2.3

問題規(guī)約法與或圖：1由與節(jié)點(diǎn)及或節(jié)點(diǎn)組成的結(jié)構(gòu)圖模擬問題歸約方法的相關(guān)結(jié)構(gòu)是一個(gè)與或圖在狀態(tài)空間搜索中，根本不出現(xiàn)任何與節(jié)點(diǎn)。是否存在與節(jié)點(diǎn)也就成為區(qū)別問題歸約和狀態(tài)空間兩種問題求解方法的主要依據(jù)。在描述與或圖時(shí)，仍然采用如父輩節(jié)點(diǎn)、后繼結(jié)點(diǎn)和連接兩節(jié)點(diǎn)的弧線等術(shù)語(yǔ)。572.與或圖的術(shù)語(yǔ)2.3問題規(guī)約法與或圖：1由與節(jié)點(diǎn)及或節(jié)點(diǎn)2.3

問題規(guī)約法HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn):只有解決所有子問題，才能解決其父輩問題的節(jié)點(diǎn)集合，各個(gè)結(jié)點(diǎn)之間用一段小圓弧連接標(biāo)記，如(B,C)和(D,E,F)?；【€或節(jié)點(diǎn):只要解決某個(gè)問題就可解決其父輩問題的節(jié)點(diǎn)集合，如(M,N,H)。子節(jié)點(diǎn)終葉節(jié)點(diǎn):對(duì)應(yīng)于本原問題的節(jié)點(diǎn)，它沒有后裔1。582.3問題規(guī)約法HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn):只有解2.3

問題規(guī)約法與或圖中一個(gè)可解節(jié)點(diǎn)的一般定義可歸納如下：終葉節(jié)點(diǎn)必然是可解節(jié)點(diǎn)(因?yàn)樗鼈兪潜驹瓎栴})。若某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，則只要當(dāng)其后繼節(jié)點(diǎn)有一個(gè)是可解時(shí)，此非終葉節(jié)點(diǎn)就是可解的。若某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，則只有當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。與或圖中不可解節(jié)點(diǎn)的一般定義可歸納如下：沒有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。若某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，則只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。若某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，則只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)就是不可解的。592.3問題規(guī)約法與或圖中一個(gè)可解節(jié)點(diǎn)的一般定義可歸納如下：與或圖的例子2.3

問題規(guī)約法圖2.8與或圖例子（顯式圖）ttttttttt（a）（b）有解節(jié)點(diǎn)(用小圓點(diǎn)表示）無(wú)解節(jié)點(diǎn)(用小圓點(diǎn)表示)終葉節(jié)點(diǎn)(用字母t表示)60與或圖的例子2.3問題規(guī)約法圖2.8與或圖例子（顯式圖）與或圖的構(gòu)成規(guī)則2.3

問題規(guī)約法與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問題或問題集合。與或圖中的起始節(jié)點(diǎn)對(duì)應(yīng)于原始問題。對(duì)應(yīng)于本源問題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒有后裔。對(duì)于把算符應(yīng)用于問題A的每種可能情況，都把問題變換為一個(gè)子問題集合；有向弧線自A指向后繼結(jié)點(diǎn)，表示所求得的子問題集合。對(duì)于與節(jié)點(diǎn)，需要用圓弧將有向弧線連接起來(lái)。而或節(jié)點(diǎn)不需要。代表子問題集合的中間或節(jié)點(diǎn)可以省略。備注：與狀態(tài)空間問題求解一樣，很少使用顯式圖來(lái)搜索，而是用由初始問題描述和消解算符所定義的隱式圖來(lái)搜索。這樣，一個(gè)問題求解時(shí)只要生成與或圖的足夠部分就可以了。61與或圖的構(gòu)成規(guī)則2.3問題規(guī)約法與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)(S,F,Gf)(S,F,G)({g},F,G)問題歸約機(jī)理關(guān)鍵算符：當(dāng)應(yīng)用某個(gè)算符是問題求解的決定性步驟時(shí)，就稱該算符為關(guān)鍵算符。當(dāng)確定下來(lái)某個(gè)關(guān)鍵算符時(shí)，可用它來(lái)確定問題歸約的過程。例2：假設(shè)一個(gè)狀態(tài)空間搜索問題有三元狀態(tài)(S,F,G)所規(guī)定。S為初始狀態(tài)，F(xiàn)為規(guī)則集，G為目標(biāo)狀態(tài)。設(shè)f是該問題的關(guān)鍵算符，則(S,F,G)的第一個(gè)后裔問題是去尋找一條通向適用狀態(tài)的路徑問題。設(shè)Gf表示f適用的所有狀態(tài)的集合，則得到原問題的子問題(S,F,Gf)

。設(shè)狀態(tài)g∈Gf，則得到另一個(gè)子問題({g},F,{f(g)})。其中，f(g)表示把f應(yīng)用于g而得到的狀態(tài)，且f(g)∈G。因?yàn)檫@個(gè)問題僅僅由應(yīng)用關(guān)鍵算符f來(lái)解決，所以它是本原的。62(S,F,Gf)(S,F,G)({g},F,G)問題歸約機(jī)理例3.猴子和香蕉問題在一個(gè)房間內(nèi)有一只猴子（可把這只猴子看做一個(gè)機(jī)器人）、一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么猴子怎樣才能摘到香蕉呢？2.2狀態(tài)空間法1.綜合數(shù)據(jù)庫(kù)：用一個(gè)四元表列(W,x,Y,z)來(lái)表示這個(gè)問題的狀態(tài)：W：猴子的水平位置；X：當(dāng)猴子在箱子頂上時(shí)x=1；否則x=0；Y：箱子的水平位置，Z：當(dāng)猴子摘到香蕉時(shí)z=1；否則z=063例3.猴子和香蕉問題在一個(gè)房間內(nèi)有一只猴子（2.2狀態(tài)空間法pushbox（V）猴子把箱子推到水平位置V，即有f2：（W，0，W，z）pushbox(V)（V，0，V，z）（2）climbbox猴子爬上箱頂，即有f3：（W，0，W，z）climbbox（W，1，W，z）（3）grasp猴子摘到香蕉，即有

f4：（c，1，c，0）grasp（c，1，c，1）

（4）goto（U）表示猴子走到水平位置f1：W，0，Y，z）goto（U）（U，0，Y，z）（1）這個(gè)問題的操作（算符）以及產(chǎn)生式規(guī)則表示如下：令F={f1,f2,f3,f4}是4個(gè)算符的集合，G是滿足目標(biāo)條件的狀態(tài)集合。則初始問題為：({(a,0,b,0)},F,G)。642.2狀態(tài)空間法pushbox（V）猴子把箱子推到水平位置

關(guān)鍵算符是f4。假設(shè)Gf4是適用于算符f4的狀態(tài)集合，則初始問題變?yōu)椋?{(a,0,b,0)},Gf4)和(S1,

G)。這里S1=

(c,1,c,0),

S1必須是求解前一問題得到的狀態(tài)。【第一步】找關(guān)鍵算符【第二步】求解問題({(a,0,b,0)},Gf4)由(a,0,b,0)所描述的狀態(tài)不在Gf4中，因?yàn)椋孩傧渥硬辉赾處；②猴子不在c處；③猴子不在箱子上。則下列算符為該問題的關(guān)鍵算符：f2:pushbox(c)，f1:goto(c)，f3:climbbox應(yīng)用關(guān)鍵算符產(chǎn)生各歸約問題的子問題集合?！镜谌健肯冉鉀Q問題①，應(yīng)用f2使問題({(a,0,b,0)},

Gf4)變?yōu)閱栴}({(a,0,b,0)},

Gf2)和(S11,Gf4)，其中S11是應(yīng)用f2得到的狀態(tài)(c,0,c,0)。65關(guān)鍵算符是f4。假設(shè)Gf4是適用于算符f4的狀態(tài)集合，則計(jì)算({(a,0,b,0)},Gf2)問題的差別，此差別為猴子不在b處。則得到關(guān)鍵算符f1：goto(b)，應(yīng)用f1得到問題({(a,0,b,0)},Gf2)變?yōu)閱栴}({(a,0,b,0)},Gf1)和(S111,Gf2)。S111是應(yīng)用f1得到的狀態(tài)(b,0,b,0)。因?yàn)闋顟B(tài)(a,0,b,0)在規(guī)則f1的域內(nèi)，因此問題({(a,0,b,0)},Gf1)已是本原問題。因?yàn)闋顟B(tài)S111=(b,0,b,0)在規(guī)則f2的域內(nèi)，則問題({(b,0,b,0)},Gf2)也是本原問題，且問題①

的目標(biāo)狀態(tài)S11為(c,0,c,0)。至此，所有問題得到解決。最后畫出與或圖。66計(jì)算({(a,0,b,0)},Gf2)問題的差別，此差別為

(c,1,c,0)

?

(c,1,c,1)(a,0,b,0)

?

(c,0,c,0)(c,0,c,0)

?

(c,1,c,0)(a,0,b,0)

?

(c,1,c,1)

f4(a,0,b,0)

?

(c,1,c,0)

f2f3f1(a,0,b,0)

?

(b,0,b,0)(b,0,b,0)

?

(c,0,c,0)用問題歸約法求解猴子和香蕉問題的與或圖67(c,1,c,0)?(c,1,c,1)用要證的問題與已知規(guī)則的結(jié)論相匹配匹配操作：將其條件與要證問題的條件相比較若條件已存在，則為本原問題，該問題可解；若缺少條件，則將該條件作為要證的子問題，原問題的條件仍為新的子問題的條件，繼續(xù)歸約。如對(duì)一個(gè)問題同時(shí)有幾條本原問題描述可以匹配,則可以對(duì)該問題節(jié)點(diǎn)進(jìn)行或擴(kuò)展。歸約操作方法:68用要證的問題與已知規(guī)則的結(jié)論相匹配歸約操作方法:68例4：求證一個(gè)角的平分線上的點(diǎn)與該角的兩邊距離相等.已知：∠DBA=∠DBC，BA⊥AD,BC⊥CD，DB為一線段，?BAD和?BCD為三角形，試用問題歸約法證明：AD=CD。假設(shè)：已有的知識(shí)是:若兩個(gè)三角形有一個(gè)等長(zhǎng)邊，且相鄰兩個(gè)角相等,則兩個(gè)三角形全等。即：設(shè)?X1X2X3，?Y1Y2Y3，若：X3X1=Y3Y1,∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3,則：?X1X2X3??Y1Y2Y3此外，已有的知識(shí)還有：全等三角形的邊都等長(zhǎng)；兩線垂直，夾角為90度；三角形內(nèi)角和為180度，即：∠X1X2X3+∠X2X3X1+∠X3X1X2=180。或：∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3?∠X2X3X1=∠Y2Y3Y1ABCD69例4：求證一個(gè)角的平分線上的點(diǎn)與該角的兩邊距離相等.假設(shè)：已

練習(xí)-答案問題表示：∠DBA=∠DBC,BA⊥AD,BC⊥CD,?BAD,?BCD?AD=CDP1：∠X1=90o,∠X2=90o?∠X1=∠X2P2：?X1X2X3，?Y1Y2Y3，X3X1=Y3Y1，∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3??X1X2X3??Y1Y2Y3P3：X1X2⊥X2X3?∠X1X2X3=90oP4：?X1X2X3??Y1Y2Y3?X2X3=Y2Y3P5：?X1X2X3?∠X1X2X3+∠X2X3X1+∠X3X1X2=180oP6：?X1X2X3,?Y1Y2Y3,∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3?∠X2X3X1=∠Y2Y3Y1ABCD70 練習(xí)-答案ABCD70

BA⊥AD

?∠BAD=

90oBC⊥CD

?∠BCD=

90o

{S}?

AD=CD

P4{S}

?

?

BAD?

?

BCDP2∠BAD,∠BCD=

90o?∠BAD=

∠BCDDB=DB,

∠BDA=∠BDC,

∠DBA=

∠DBC?

?

BAD

?

?

BCD

{S}

?

∠BAD=

∠BCD

P1,

P3{S}

?∠DBA=∠DBC

設(shè){S}={∠DBA=

∠DBC,

BA⊥AD,BC⊥CD,

?BAD,

?

BCD

}。

?

BAD

?

?

BCD

?

AD=CD{S}

?

∠BDA=

∠BDC

P6

ADC71 BA⊥AD?BC⊥CD? {S}?AD=CDP2∠B問題歸約法小結(jié)狀態(tài)空間法與問題歸約法的比較狀態(tài)空間——問題空間狀態(tài)空間圖——與或圖操作——?dú)w約求解路徑——本原問題歸約就是化簡(jiǎn)，即把復(fù)雜問題分解為若干子問題，且使得：每個(gè)子問題比原問題好解；這些子問題解決了，原問題就解決了問題歸約法的描述：用與或圖72問題歸約法小結(jié)狀態(tài)空間法與問題歸約法的比較722.4謂詞邏輯表示2.4謂詞邏輯法

人工智能中用到的邏輯可劃分為兩大類（如下圖所示）：經(jīng)典命題邏輯和一階謂詞邏輯（又稱為二值邏輯）1：任何一個(gè)命題的真值為“真”或“假”，兩者必居其一。非經(jīng)典邏輯：三值邏輯、多值邏輯、模糊邏輯等。

謂詞邏輯是在命題邏輯基礎(chǔ)上發(fā)展起來(lái)的，命題邏輯可看作是謂詞邏輯的一種特殊形式。模糊邏輯邏輯經(jīng)典邏輯（二值邏輯）非經(jīng)典邏輯三值邏輯一階謂詞邏輯經(jīng)典命題邏輯多值邏輯732.4謂詞邏輯表示2.4謂詞邏輯法

人工智能中用到的邏輯可2.4.1命題命題（proposition）：一個(gè)非真即假的陳述句。若命題的意義為真*，稱它的真值為真，記為T。

若命題的意義為假*，稱它的真值為假，記為F。一個(gè)命題可在一種條件下為真，在另一種條件下為假*。命題邏輯*：研究命題及命題之間關(guān)系的符號(hào)邏輯系統(tǒng)*。命題邏輯表示法：無(wú)法把它所描述的事物的結(jié)構(gòu)及邏輯特征反映出來(lái)*，也不能把不同事物間的共同特征表述出來(lái)*。例如：3<5

例如：太陽(yáng)從西邊升起

例:1＋1＝10P：北京是中華人民共和國(guó)的首都P：老李是小李的父親P：李白是詩(shī)人Q：杜甫也是詩(shī)人742.4.1命題命題（proposition）：一個(gè)非真即假的2.4.2謂詞命題邏輯（propositionallogic）能夠把客觀世界的各種事實(shí)表示為命題邏輯。但是，它具有較大的局限性，不適合于表示比較復(fù)雜的問題。謂詞邏輯（predicatelogic）允許表達(dá)那些無(wú)法用命題邏輯表達(dá)的事情。更具體地說(shuō)，一階謂詞演算（firstorderpredicatecalculus）是一種形式語(yǔ)言，其根本目的在于把數(shù)學(xué)中的邏輯論證符號(hào)化。如果能夠采用數(shù)學(xué)演繹的方式證明一個(gè)新語(yǔ)句是從那些已知正確的語(yǔ)句導(dǎo)出的，那么也就能斷定這個(gè)新語(yǔ)句也是正確的。

752.4.2謂詞命題邏輯（propositionallogi2.4.2謂詞謂詞邏輯的基本組成部分是謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)和常量符號(hào)，并用園括弧、方括弧、花括弧和逗號(hào)隔開，以表示論域內(nèi)的關(guān)系。一般，原子公式由若干謂詞符號(hào)和個(gè)體組成。謂詞的一般形式：P(x1,x2,…,xn)個(gè)體x1,x2,…,xn

：某個(gè)獨(dú)立存在的事物或者某個(gè)抽象的概念；謂詞名P：刻畫個(gè)體的性質(zhì)、狀態(tài)或個(gè)體間的關(guān)系。（1）個(gè)體是常量：一個(gè)或者一組指定的個(gè)體。

“老張是一個(gè)教師”：一元謂詞Teacher(Zhang)“5>3”：二元謂詞

Greater(5,3)“Smith作為一個(gè)工程師為IBM工作”：三元謂詞

Works(Smith,IBM,engineer)762.4.2謂詞謂詞邏輯的基本組成部分是謂詞符號(hào)、變量符號(hào)、函（2）個(gè)體是變?cè)ㄗ兞浚簺]有指定的一個(gè)或者一組個(gè)體。*“小李的父親是教師”：Teacher(father(Li))（3）個(gè)體是函數(shù)：一個(gè)個(gè)體到另一個(gè)個(gè)體的映射*?！皒<5”

：Less(x,5)

（4）個(gè)體是謂詞*Smith作為一個(gè)工程師為IBM工作”：二階謂詞Works(engineer(Smith),IBM)77（2）個(gè)體是變?cè)ㄗ兞浚簺]有指定的一個(gè)或者一組個(gè)體。*“小2.4.3謂詞公式PLF

1.連接詞（連詞）（1）﹁：“否定”（negation）或“非”*。（2）∨：“析取”（disjunction）——或*。（3）∧：“合取”（conjunction）——與*。“機(jī)器人不在2號(hào)房間”：﹁Inroom(robot,r2)“李明打籃球或踢足球”：Plays(Liming,basketball)∨

Plays(Liming,football)“我喜歡音樂和繪畫”：

Like(I,music)∧

Like(I,painting)782.4.3謂詞公式PLF1.連接詞（連詞）“機(jī)器人不在（4）→：“蘊(yùn)含”(implication)或“條件”(condition)*

表示“如果-那么”的語(yǔ)句。IF前項(xiàng)（左式）→THEN后項(xiàng)（右式）若后項(xiàng)取值為T，則不管前項(xiàng)值是否為T，蘊(yùn)涵均為T。若前項(xiàng)取值為F，則不管后項(xiàng)取值如何，蘊(yùn)涵均為T。否則，蘊(yùn)涵為F。一般地：P→Q:“P→Q為假，當(dāng)且僅當(dāng)P為真，Q為假”“如果劉華跑得最快，那么他取得冠軍?！保?/p>

RUNS(Liuhua，faster)→WINS(Liuhua，champion)“如果該書是何平的，那么它是藍(lán)色（封面）?！保?/p>

OWNS(HEPING，BOOK-1)

→COLOR(BOOK-1,BLUE)79（4）→：“蘊(yùn)含”(implication)或“條件”(c連接詞的謂詞邏輯真值表80連接詞的謂詞邏輯真值表802.4.3謂詞公式2.量詞（quantifier）（1）全稱量詞（universalquantifier）（?x）：“對(duì)個(gè)體域中的所有（或任一個(gè)）個(gè)體x

”?！八械臋C(jī)器人都是灰色的”：

(?x)[ROBOT(x)→

COLOR(x，GRAY)]（2）存在量詞（existentialquantifier）（彐

x）：“在個(gè)體域中存在個(gè)體

x

”。“1號(hào)房間有個(gè)物體”：（彐x）INROOM（x，r1）812.4.3謂詞公式2.量詞（quantifier）“所全稱量詞和存在量詞舉例：

(?x)(彐y)Friend(x,y)表示對(duì)于個(gè)體域中的任何個(gè)體x都存在個(gè)體y，x與y是朋友。

(彐x)(?y)Friend(x,y)表示在個(gè)體域中存在個(gè)體x，與個(gè)體域中的任何個(gè)體y都是朋友。

(彐x)(彐y)F(x,y)表示在個(gè)體域中存在個(gè)體x與個(gè)體y，x與y是朋友。

(?x)(?y)Friend(x,y)表示對(duì)于個(gè)體域中的任何兩個(gè)個(gè)體x和y，x與y都是朋友。

82全稱量詞和存在量詞舉例：82全稱量詞和存在量詞出現(xiàn)的次序?qū)⒂绊懨}的意思。例如：

(?x)(彐y)(Employee(x)→

Manager(y,x)):

“每個(gè)雇員都有一個(gè)經(jīng)理?！?/p>

(彐y)(?x)(Employee(x)→

Manager(y,x)):

“有一個(gè)人是所有雇員的經(jīng)理?！?3全稱量詞和存在量詞出現(xiàn)的次序?qū)⒂绊懨}的意思。(?x)(3.謂詞公式定義2.2可按下述規(guī)則得到謂詞演算的謂詞公式（合式公式）：?jiǎn)蝹€(gè)謂詞是謂詞公式，稱為原子謂詞公式。若A是謂詞公式，則﹁A也是謂詞公式。若A，B都是謂詞公式，則A∧B，A∨B，A→B，AB也都是謂詞公式。若A是謂詞公式，則(?x)A，(彐(

x)A也是謂詞公式。有限步應(yīng)用（1）－（4）生成的公式也是謂詞公式。*1連接詞的優(yōu)先級(jí)別從高到低排列：

﹁，∧，∨，→，

必須指出的是，本課程所用到謂詞演算為一階謂詞演算，不允許對(duì)謂詞符號(hào)或函數(shù)進(jìn)行量化。例如在一階謂詞演算中，(?P)P(A)這樣一些公式就不是合式公式。843.謂詞公式單個(gè)謂詞是謂詞公式，稱為原子謂詞公式。連接4．量詞的轄域

量詞的轄域：位于量詞后面的單個(gè)謂詞或者用括弧括起來(lái)的謂詞公式。約束變?cè)c自由變?cè)狠犛騼?nèi)與量詞中同名的變?cè)Q為約束變?cè)?，不同名的變?cè)Q為自由變?cè)?。例如?/p>

(彐x)(P(x,y)→Q(x,y))∨R(x,y)(P(x,y)→

Q(x,y))：(彐x)的轄域，轄域內(nèi)的變?cè)獂是受（彐x）約束的變?cè)?，R(x,y)中的x是自由變?cè)?。公式中的所有y都是自由變?cè)?/p>

854．量詞的轄域例如：85例：對(duì)于所有的x，如果x是整數(shù)，則x或?yàn)檎幕蛘邽樨?fù)的。解：用I(x)表示“x是整數(shù)”，P(x)表示“x是正數(shù)”，N(x)表示“x是負(fù)數(shù)”。則得到：(?x)I(x)→P(x)∨N(x)例：通過兩個(gè)不同點(diǎn)a和b的直線L1和L2是同一直線。解：用T(x)表示x是點(diǎn)，L(x)表示x是線；P(x,y,z)表示直線x經(jīng)過點(diǎn)y和z。E(x,y)表示x和y是同一直線。則得到：T(a)∧T(b)∧L(L1)∧L(L2)∧P(L1,a,b)∧P(L2,a,b)→E(L1,L2)例：有些小孩長(zhǎng)高了。解：C(x)表示x是小孩，BH(x)表示x長(zhǎng)高了。則得到：(?x)(C(x)∧BH(x))

等價(jià)于：~[(?x)(C(x)∧~BH(x))]86例：對(duì)于所有的x，如果x是整數(shù)，則x或?yàn)檎幕蛘邽樨?fù)的。86例：“至少有一偶數(shù)是素?cái)?shù)”。解：用A(x)表示x是偶數(shù)，B(x)表示x是素?cái)?shù)。則：

(?x)(A(x)∧B(x))例：“至少有一偶數(shù)并且至少有一素?cái)?shù)”。

(?x)A(x)∧(?x)B(x)例：用謂詞演算來(lái)表示下面英文句子：*1

Foreverysetx,thereisasety,suchthatthecardinalityofythe

is

greaterthanthecardinalityofx.CARD(y,v)CARD(x,u)G(v,u)?x{SET(x)→(?y)(?u)(?v)[SET(y)∧CARD(x,u)∧CARD(y,v)∧G(v,u)]}?xSET(x)?ySET(y)87例：“至少有一偶數(shù)是素?cái)?shù)”。CARD(y,v)CARD(x,例：凡是人都要學(xué)習(xí)。(?x)(HUMAN(x)→NEED-STUDY(x))例：有一個(gè)人的兄弟是老師。

(?x)TEACHER(brother(x))例：“小孩都要長(zhǎng)高”與“有個(gè)小孩長(zhǎng)高了”不一樣：一個(gè)表示一種結(jié)論或觀點(diǎn)，包含著條件和結(jié)論；一個(gè)表示事實(shí)。

(?x)(CHILD(x)→GROW-UP(x))(?x)(CHILD(x)∧GROW-UP(x))注意：①事實(shí)不能表示成推理。

②變量和函數(shù)一般用小寫字母表示。88例：凡是人都要學(xué)習(xí)。882.4.4謂詞公式的性質(zhì)1.謂詞公式的解釋謂詞公式在個(gè)體域上的解釋：個(gè)體域中的實(shí)體對(duì)謂詞演算表達(dá)式中的每個(gè)常量、變量、謂詞和函數(shù)符號(hào)的指派*。Friends(george,x)Friends(george,susie)TFriends(george,kate)F對(duì)于每一個(gè)解釋，謂詞公式都可求出一個(gè)真值（T或F）。892.4.4謂詞公式的性質(zhì)1.謂詞公式的解釋Friends2.謂詞公式的永真性、可滿足性、不可滿足性

2.謂詞公式的永真性、可滿足性、不可滿足性

定義2.5對(duì)于謂詞公式P，如果至少存在一個(gè)解釋使得P在此解釋下的真值為T，則稱P是可滿足的，否則，則稱P是不可滿足的。

定義2.4如果謂詞公式P對(duì)個(gè)體域D上的任何一個(gè)解釋都取得真值F，則稱P在D上是永假的；如果P在每個(gè)非空個(gè)體域上均永假，則稱P永假。

定義2.3如果謂詞公式P對(duì)個(gè)體域D上的任何一個(gè)解釋都取得真值T，則稱P在D上是永真的；如果P在每個(gè)非空個(gè)體域上均永真，則稱P永真。902.謂詞公式的永真性、可滿足性、不可滿足性2.謂詞公式3.謂詞公式的等價(jià)性定義2.6設(shè)P與Q是兩個(gè)謂詞公式，D是共同的個(gè)體域，若對(duì)D上的任一解釋，P與Q都有相同的真值，則稱公式P和Q在D上是等價(jià)的。如果D是任意個(gè)體域，則稱P和Q是等價(jià)的，記為P?Q

。

（3）德.摩根律(De.Morgen)又叫反演律

﹁

(P∧Q)?﹁

P∨﹁Q;﹁

(P∨Q)?﹁

P∧﹁Q（2）連接詞化歸律和(7)逆否律P→Q?﹁

P∨Q；P→Q?﹁

P→﹁Q（8）量詞轉(zhuǎn)換律

?(?x)P(x)?(?x)(?P(x))；?(?x)(P(x)?(?x)(?P(x))注：P38、P39其他等價(jià)式。3.謂詞公式的等價(jià)性913.謂詞公式的等價(jià)性定義2.6設(shè)P與Q是兩個(gè)謂詞公式，D

4.謂詞公式的永真蘊(yùn)含定義2.7對(duì)于謂詞公式P與Q，如果P→Q永真，則稱公式P永真蘊(yùn)含Q，且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記為P?Q。（1）假言（或假元）推理：P,P→Q?Q（2）拒取式推理：﹁Q,P→Q?﹁