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

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

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

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

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

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

“雪是白色”。

“假如頭痛且流涕，則有也許患了感冒”。2.1知識(shí)與知識(shí)表達(dá)概念

4第4頁(yè)2.1.1知識(shí)概念Feigenbaum以為知識(shí)是通過(guò)加工信息，它包括事實(shí)、信念和啟發(fā)式規(guī)則。Bernstein說(shuō)知識(shí)是由特定領(lǐng)域描述、關(guān)系和過(guò)程組成。Hayes-Roth以為知識(shí)是事實(shí)、信念和啟發(fā)式規(guī)則。知識(shí)庫(kù)觀點(diǎn)看，知識(shí)是某論域中所包括各有關(guān)方面、狀態(tài)一種符號(hào)表達(dá)。5第5頁(yè)2.1.1知識(shí)概念人工智能系統(tǒng)所關(guān)懷知識(shí)事實(shí)：是有關(guān)對(duì)象和物體知識(shí)。規(guī)則：是有關(guān)問(wèn)題中與事物行動(dòng)、動(dòng)作相聯(lián)系因果關(guān)系知識(shí)。元知識(shí)：是有關(guān)知識(shí)知識(shí)，是知識(shí)庫(kù)中高層知識(shí)。包括如何使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序構(gòu)造等。常識(shí)性知識(shí)：泛指普遍存在并且被普遍結(jié)識(shí)了客觀事實(shí)一類(lèi)知識(shí)。

2.1知識(shí)與知識(shí)表達(dá)概念

6第6頁(yè)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í)表達(dá)概念

7第7頁(yè)2.1.2知識(shí)特性不確定性*隨機(jī)性引發(fā)不確定性*

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

“假”

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

“假如頭痛且流涕，則有也許患了感冒”

小李很高2.1知識(shí)與知識(shí)表達(dá)概念

8第8頁(yè)2.1.2知識(shí)特性

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

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

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

2.2狀態(tài)空間法2.3問(wèn)題歸約法2.4謂詞邏輯法2.5語(yǔ)義網(wǎng)絡(luò)法2.6框架表達(dá)2.7本體技術(shù)2.8過(guò)程表達(dá)2.9小結(jié)19第19頁(yè)2.2狀態(tài)空間法

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

20第20頁(yè)2.2.1

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

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

2.1狀態(tài)空間法21第21頁(yè)2.2.1問(wèn)題狀態(tài)描述初始狀態(tài)：由問(wèn)題已知條件原始描述所組成狀態(tài)目標(biāo)狀態(tài)：?jiǎn)栴}處理時(shí)應(yīng)當(dāng)達(dá)到狀態(tài)算符：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)伎倆，操作符可為走步、過(guò)程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。狀態(tài)空間：一種表達(dá)該問(wèn)題所有也許狀態(tài)及其關(guān)系圖，包括三種說(shuō)明集合，即所有也許問(wèn)題初始狀態(tài)集合S、

操作符集合F以及目標(biāo)狀態(tài)集合G?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。2.2狀態(tài)空間法22第22頁(yè)狀態(tài)空間表達(dá)概念詳釋OriginalStateMiddleStateGoalState2.2狀態(tài)空間法對(duì)一種問(wèn)題狀態(tài)描述，必須確定3件事：該狀態(tài)描述方式，尤其是初始狀態(tài)描述；操作符集合及其對(duì)狀態(tài)描述作用；目標(biāo)狀態(tài)描述。例如：數(shù)碼難題。23第23頁(yè)例1:三數(shù)碼難題

（3puzzleproblem）123123123312312312初始棋局目標(biāo)棋局2.2狀態(tài)空間法24第24頁(yè)圖論基本概念有向圖途徑代價(jià)圖顯示說(shuō)明圖隱示說(shuō)明2.2.2狀態(tài)圖示法AB2.2狀態(tài)空間法25第25頁(yè)圖論基本概念有向圖(directedgraph)：節(jié)點(diǎn)(node)：圖形上匯合點(diǎn)，用來(lái)表達(dá)狀態(tài)、事件和時(shí)間關(guān)系匯合，也可用來(lái)批示通路匯合；后繼節(jié)點(diǎn)(descendantnode)與父輩節(jié)點(diǎn)(parentnode)：假如某條弧線(xiàn)從節(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)或祖先?；【€(xiàn)(arc)：節(jié)點(diǎn)間連接線(xiàn)；有向圖(directedgraph)：圖由節(jié)點(diǎn)（不一定是有限節(jié)點(diǎn)）集合構(gòu)。一對(duì)節(jié)點(diǎn)用弧線(xiàn)連接起來(lái)，從一種節(jié)點(diǎn)指向另一種節(jié)點(diǎn)。

2.2狀態(tài)空間法

26第26頁(yè)圖論基本概念途徑：某個(gè)節(jié)點(diǎn)序列(n1,n2,…,nk)，當(dāng)j=2，3，…，k時(shí)，假如對(duì)于每一種nj-1都有一種后繼節(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)，則稱(chēng)nj是從ni可達(dá)成節(jié)點(diǎn)。尋找從一種狀態(tài)變換成另一種狀態(tài)某個(gè)算符序列問(wèn)題等價(jià)于謀求圖某一途徑問(wèn)題。

2.2狀態(tài)空間法

27第27頁(yè)圖論基本概念代價(jià)：衡量狀態(tài)之間轉(zhuǎn)變所需時(shí)間、精力等量化值。用c(ni,nj)來(lái)表達(dá)從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj弧線(xiàn)代價(jià)。兩節(jié)點(diǎn)間途徑代價(jià)等于連接該途徑上各節(jié)點(diǎn)所有弧線(xiàn)代價(jià)之和。對(duì)于最優(yōu)化問(wèn)題，就要找兩節(jié)點(diǎn)間具有最小代價(jià)途徑。顯式表達(dá)：各節(jié)點(diǎn)及其具有代價(jià)弧線(xiàn)由一張表白確給出。此表也許列出該圖中每一節(jié)點(diǎn)、它后繼節(jié)點(diǎn)以及連接弧線(xiàn)代價(jià)。問(wèn)題：對(duì)于大型圖和具有沒(méi)有限節(jié)點(diǎn)集合圖不適用。

2.2狀態(tài)空間法

28第28頁(yè)圖論基本概念

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

29第29頁(yè)嘗試多種不一樣走步，直到偶爾得到目標(biāo)棋局為止。

1

2

3

8

4

7

6

5目標(biāo)狀態(tài)例2：九宮排序（八數(shù)碼問(wèn)題）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第30頁(yè)規(guī)則：假如針對(duì)每個(gè)數(shù)碼來(lái)要求規(guī)則(上下左右移動(dòng))，則需要8*4=32條規(guī)則，假如針對(duì)空格來(lái)要求規(guī)則，則只需要4條規(guī)則。R1：IF

空格上方有棋THEN

空格上移R2：IF

空格右方有棋THEN

空格右移R3：IF

空格下方有棋THEN

空格下移R4：IF

空格左方有棋THEN

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

31第31頁(yè)九宮排序（寬度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765125673123847658432第32頁(yè)九宮排序（深度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

83214765281437652831457612378465123847652836417528316754832147652837146528143765283145761238476523456789abcd133第33頁(yè)2.2.3狀態(tài)空間表達(dá)舉例產(chǎn)生式系統(tǒng)（productionsystem）一種總數(shù)據(jù)庫(kù)：它具有與詳細(xì)任務(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)作。一種控制策略：它確定應(yīng)當(dāng)采取哪一條適用規(guī)則，并且當(dāng)數(shù)據(jù)庫(kù)終止條件滿(mǎn)足時(shí)，就停頓計(jì)算。2.1狀態(tài)空間法34第34頁(yè)用顯式說(shuō)明（列表）表達(dá)狀態(tài)圖，表中放有旅行商通過(guò)都市，表中最后一種元素就是旅行商目前所在都市。初始數(shù)據(jù)庫(kù)：（A）目標(biāo)數(shù)據(jù)庫(kù)：（A,…….,A)規(guī)則：R1：IF

沒(méi)有去過(guò)B

THEN

下一步去BR2：IF

沒(méi)有去過(guò)C

THEN

下一步去CR3：IF

沒(méi)有去過(guò)D

THEN

下一步去DR4：IF

沒(méi)有去過(guò)E

THEN

下一步去ER5：IF

都去過(guò)了THEN

下一步去AA5722341

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

35第35頁(yè)2.2.3狀態(tài)空間表達(dá)舉例產(chǎn)生式系統(tǒng)（productionsystem）數(shù)據(jù)庫(kù)（事實(shí)庫(kù)）：具有與詳細(xì)任務(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)當(dāng)采取哪一條適用規(guī)則，并且當(dāng)數(shù)據(jù)庫(kù)終止條件滿(mǎn)足時(shí)，就停頓計(jì)算。2.2狀態(tài)空間法36第36頁(yè)例4：猴子和香蕉問(wèn)題在一種房間內(nèi)有一只猴子（可把這只猴子看做一種機(jī)器人）、一種箱子和一束香蕉。香蕉掛在天花板下方，但猴子高度不足以遇到它。那么猴子如何才能摘到香蕉呢？2.2狀態(tài)空間法1.綜合數(shù)據(jù)庫(kù)：用一種四元表列(W,x,Y,z)來(lái)表達(dá)這個(gè)問(wèn)題狀態(tài)：W：猴子水平位置；X：當(dāng)猴子在箱子頂上時(shí)x=1；不然x=0；Y：箱子水平位置，Z：當(dāng)猴子摘到香蕉時(shí)z=1；不然z=037第37頁(yè)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）表達(dá)猴子走到水平位置（W，0，Y，z）goto（U）（U，0，Y，z）（1）2.規(guī)則庫(kù)這個(gè)問(wèn)題操作（算符）以及產(chǎn)生式規(guī)則表達(dá)如下：38第38頁(yè)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!求解成果：該初始狀態(tài)變換為目標(biāo)狀態(tài)操作序列{goto(b),pushbox(c),climbbox,grasp}狀態(tài)空間圖(求解過(guò)程1):39第39頁(yè)例5：設(shè)字符轉(zhuǎn)換規(guī)則A∧B→C，A∧C→D，B∧C→G，B∧E→F，D→E。目前已知：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第40頁(yè)1、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問(wèn)題狀態(tài)空間圖41第41頁(yè)N個(gè)傳教士，N個(gè)野人，一條船，可同步乘坐k個(gè)人乘渡。傳教士為安全起見(jiàn)，應(yīng)如何要求擺渡方案，使得任何時(shí)刻，當(dāng)傳教士與野人在同一地點(diǎn)(河兩岸以及船上)時(shí)，野人數(shù)目總是不超出傳教士數(shù)目。傳教士與野人均可擺渡。左岸右岸M30C30B10左岸右岸M03C03B01初始狀態(tài)目標(biāo)狀態(tài)例6：傳教士與野人問(wèn)題（M-C問(wèn)題）：以N=3(傳教士或野人數(shù))，k=2(每條船載人數(shù))為例求解。42第42頁(yè)求解過(guò)程如下：1.綜合數(shù)據(jù)庫(kù)用(m,c,b)表達(dá)左岸傳教士人數(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頁(yè)也能夠定義為：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第44頁(yè)6.繪制狀態(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)45第45頁(yè)2.3問(wèn)題歸約法

（ProblemReductionRepresentation）子問(wèn)題1子問(wèn)題n原始問(wèn)題子問(wèn)題集本原問(wèn)題問(wèn)題歸約是另一種基于狀態(tài)空間問(wèn)題描述與求解辦法。已知問(wèn)題描述，通過(guò)一系列變換把此問(wèn)題最后變?yōu)橐环N子問(wèn)題集合；這些子問(wèn)題解能夠直接得到，從而處理了初始問(wèn)題。46第46頁(yè)例1：假定會(huì)求矩形面積，目前要求如圖所示五邊形面積。II①②2III

③

3

I1求五邊形面積?

1面積?

2面積?

3面積①面積②面積③面積I面積II面積III面積47第47頁(yè)問(wèn)題歸約表達(dá)組成部分：一種初始問(wèn)題描述；一套把問(wèn)題變換為子問(wèn)題操作符；一套本原問(wèn)題描述。問(wèn)題歸約實(shí)質(zhì)：從目標(biāo)(要處理問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題子問(wèn)題，直至最后把初始問(wèn)題歸約為一種平凡本原問(wèn)題集合。2.3

問(wèn)題規(guī)約法48第48頁(yè)2.3.1問(wèn)題歸約描述

（ProblemReductionDescription）1.梵塔難題12.3

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

AB初始狀態(tài)

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

2

349第49頁(yè)梵塔難題求解12.3

問(wèn)題規(guī)約法把原始問(wèn)題規(guī)約為一種較簡(jiǎn)單問(wèn)題集合：要把所有圓盤(pán)移到柱子3，首先把圓盤(pán)C移至柱子3；并且在其之前，要求柱子3是空。只有移開(kāi)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第50頁(yè)C

ABC

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

ABC

AB子問(wèn)題(1,1,1)初始配備C

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

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

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

2.3

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

問(wèn)題規(guī)約法ABCD與圖ABC或圖55第55頁(yè)2.3

問(wèn)題規(guī)約法BCDEFGAHMBCDEFGAN圖2.6子問(wèn)題替代集合構(gòu)造圖圖2.7一種與或圖56第56頁(yè)2.與或圖術(shù)語(yǔ)2.3

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

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

問(wèn)題規(guī)約法與或圖中一種可解節(jié)點(diǎn)一般定義可歸納如下：終葉節(jié)點(diǎn)必然是可解節(jié)點(diǎn)(由于它們是本原問(wèn)題)。若某個(gè)非終葉節(jié)點(diǎn)具有或后繼節(jié)點(diǎn)，則只要當(dāng)其后繼節(jié)點(diǎn)有一種是可解時(shí)，此非終葉節(jié)點(diǎn)就是可解。若某個(gè)非終葉節(jié)點(diǎn)具有與后繼節(jié)點(diǎn)，則只有當(dāng)其后繼節(jié)點(diǎn)所有為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解。與或圖中不可解節(jié)點(diǎn)一般定義可歸納如下：沒(méi)有后裔非終葉節(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)其后裔最少有一種為不可解時(shí)，此非終葉節(jié)點(diǎn)就是不可解。59第59頁(yè)與或圖例子2.3

問(wèn)題規(guī)約法圖2.8與或圖例子（顯式圖）ttttttttt（a）（b）有解節(jié)點(diǎn)(用小圓點(diǎn)表達(dá)）無(wú)解節(jié)點(diǎn)(用小圓點(diǎn)表達(dá))終葉節(jié)點(diǎn)(用字母t表達(dá))60第60頁(yè)與或圖組成規(guī)則2.3

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

。設(shè)狀態(tài)g∈Gf，則得到另一種子問(wèn)題({g},F,{f(g)})。其中，f(g)表達(dá)把f應(yīng)用于g而得到狀態(tài)，且f(g)∈G。由于這個(gè)問(wèn)題僅僅由應(yīng)用關(guān)鍵算符f來(lái)解決，因此它是本原。62第62頁(yè)例3.猴子和香蕉問(wèn)題在一種房間內(nèi)有一只猴子（可把這只猴子看做一種機(jī)器人）、一種箱子和一束香蕉。香蕉掛在天花板下方，但猴子高度不足以遇到它。那么猴子如何才能摘到香蕉呢？2.2狀態(tài)空間法1.綜合數(shù)據(jù)庫(kù)：用一種四元表列(W,x,Y,z)來(lái)表達(dá)這個(gè)問(wèn)題狀態(tài)：W：猴子水平位置；X：當(dāng)猴子在箱子頂上時(shí)x=1；不然x=0；Y：箱子水平位置，Z：當(dāng)猴子摘到香蕉時(shí)z=1；不然z=063第63頁(yè)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）表達(dá)猴子走到水平位置f1：W，0，Y，z）goto（U）（U，0，Y，z）（1）這個(gè)問(wèn)題操作（算符）以及產(chǎn)生式規(guī)則表達(dá)如下：令F={f1,f2,f3,f4}是4個(gè)算符集合，G是滿(mǎn)足目標(biāo)條件狀態(tài)集合。則初始問(wèn)題為：({(a,0,b,0)},F,G)。64第64頁(yè)

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

G)。這里S1=

(c,1,c,0),

S1必須是求解前一問(wèn)題得到狀態(tài)?！镜谝徊健空谊P(guān)鍵算符【第二步】求解問(wèn)題({(a,0,b,0)},Gf4)由(a,0,b,0)所描述狀態(tài)不在Gf4中，由于：①箱子不在c處；②猴子不在c處；③猴子不在箱子上。則下列算符為該問(wèn)題關(guān)鍵算符：f2:pushbox(c)，f1:goto(c)，f3:climbbox應(yīng)用關(guān)鍵算符產(chǎn)生各歸約問(wèn)題子問(wèn)題集合?！镜谌健肯忍幚韱?wèn)題①，應(yīng)用f2使問(wèn)題({(a,0,b,0)},

Gf4)變?yōu)閱?wèn)題({(a,0,b,0)},

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

目標(biāo)狀態(tài)S11為(c,0,c,0)。至此，所有問(wèn)題得到處理。最后畫(huà)出與或圖。66第66頁(yè)

(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)用問(wèn)題歸約法求解猴子和香蕉問(wèn)題與或圖67第67頁(yè)用要證問(wèn)題與已知規(guī)則結(jié)論相匹配匹配操作：將其條件與要證問(wèn)題條件相比較若條件已存在，則為本原問(wèn)題，該問(wèn)題可解；若缺乏條件，則將該條件作為要證子問(wèn)題，原問(wèn)題條件仍為新子問(wèn)題條件，繼續(xù)歸約。如對(duì)一種問(wèn)題同步有幾條本原問(wèn)題描述能夠匹配,則能夠?qū)υ搯?wèn)題節(jié)點(diǎn)進(jìn)行或擴(kuò)展。歸約操作辦法:68第68頁(yè)例4：求證一種角平分線(xiàn)上點(diǎn)與該角兩邊距離相等.已知：∠DBA=∠DBC，BA⊥AD,BC⊥CD，DB為一線(xiàn)段，?BAD和?BCD為三角形，試用問(wèn)題歸約法證明：AD=CD。假設(shè)：已有知識(shí)是:若兩個(gè)三角形有一個(gè)等長(zhǎng)邊，且相鄰兩個(gè)角相等,則兩個(gè)三角形全等。即：設(shè)?X1X2X3，?Y1Y2Y3，若：X3X1=Y3Y1,∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3,則：?X1X2X3??Y1Y2Y3另外，已有知識(shí)尚有：全等三角形邊都等長(zhǎng)；兩線(xiàn)垂直，夾角為90度；三角形內(nèi)角和為180度，即：∠X1X2X3+∠X2X3X1+∠X3X1X2=180?；颍骸蟈3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3?∠X2X3X1=∠Y2Y3Y1ABCD69第69頁(yè)

練習(xí)-答案問(wèn)題表達(dá)：∠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第70頁(yè)

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第71頁(yè)問(wèn)題歸約法小結(jié)狀態(tài)空間法與問(wèn)題歸約法比較狀態(tài)空間——問(wèn)題空間狀態(tài)空間圖——與或圖操作——?dú)w約求解途徑——本原問(wèn)題歸約就是化簡(jiǎn)，即把復(fù)雜問(wèn)題分解為若干子問(wèn)題，且使得：每個(gè)子問(wèn)題比原問(wèn)題好解；這些子問(wèn)題處理了，原問(wèn)題就處理了問(wèn)題歸約法描述：用與或圖72第72頁(yè)2.4謂詞邏輯表達(dá)2.4謂詞邏輯法

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

謂詞邏輯是在命題邏輯基礎(chǔ)上發(fā)展起來(lái)，命題邏輯可看作是謂詞邏輯一種特殊形式。含糊邏輯邏輯典型邏輯（二值邏輯）非典型邏輯三值邏輯一階謂詞邏輯典型命題邏輯多值邏輯73第73頁(yè)2.4.1命題命題（proposition）：一種非真即假陳說(shuō)句。若命題意義為真*，稱(chēng)它真值為真，記為T(mén)。

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

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

例:1＋1＝10P：北京是中華人民共和國(guó)首都P：老李是小李爸爸P：李白是詩(shī)人Q：杜甫也是詩(shī)人74第74頁(yè)2.4.2謂詞命題邏輯（propositionallogic）能夠把客觀世界多種事實(shí)表達(dá)為命題邏輯。不過(guò)，它具有較大不足，不適合于表達(dá)比較復(fù)雜問(wèn)題。謂詞邏輯（predicatelogic）允許體現(xiàn)那些無(wú)法用命題邏輯體現(xiàn)事情。更詳細(xì)地說(shuō)，一階謂詞演算（firstorderpredicatecalculus）是一種形式語(yǔ)言，其主線(xiàn)目標(biāo)在于把數(shù)學(xué)中邏輯論證符號(hào)化。假如能夠采取數(shù)學(xué)演繹方式證明一種新語(yǔ)句是從那些已知正確語(yǔ)句導(dǎo)出，那么也就能斷定這個(gè)新語(yǔ)句也是正確。

75第75頁(yè)2.4.2謂詞謂詞邏輯基本組成部分是謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)和常量符號(hào)，并用園括弧、方括弧、花括弧和逗號(hào)隔開(kāi)，以表達(dá)論域內(nèi)關(guān)系。一般，原子公式由若干謂詞符號(hào)和個(gè)體組成。謂詞一般形式：P(x1,x2,…,xn)個(gè)體x1,x2,…,xn

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

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

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

Works(Smith,IBM,engineer)76第76頁(yè)（2）個(gè)體是變?cè)ㄗ兞浚簺](méi)有指定一種或者一組個(gè)體。*“小李爸爸是教師”：Teacher(father(Li))（3）個(gè)體是函數(shù)：一種個(gè)體到另一種個(gè)體映射*。“x<5”

：Less(x,5)

（4）個(gè)體是謂詞*Smith作為一種工程師為IBM工作”：二階謂詞Works(engineer(Smith),IBM)77第77頁(yè)2.4.3謂詞公式PLF

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

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

Like(I,music)∧

Like(I,painting)78第78頁(yè)（4）→：“蘊(yùn)含”(implication)或“條件”(condition)*

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

RUNS(Liuhua，faster)→WINS(Liuhua，champion)“假如該書(shū)是何平，那么它是藍(lán)色（封面）。”：

OWNS(HEPING，BOOK-1)

→COLOR(BOOK-1,BLUE)79第79頁(yè)連接詞謂詞邏輯真值表80第80頁(yè)2.4.3謂詞公式2.量詞（quantifier）（1）全稱(chēng)量詞（universalquantifier）（?x）：“對(duì)個(gè)體域中所有（或任一種）個(gè)體x

”。“所有機(jī)器人都是灰色”：

(?x)[ROBOT(x)→

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

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

x

”?！?號(hào)房間有個(gè)物體”：（彐x）INROOM（x，r1）81第81頁(yè)全稱(chēng)量詞和存在量詞舉例：

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

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

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

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

82第82頁(yè)全稱(chēng)量詞和存在量詞出現(xiàn)次序?qū)⒂绊懨}意思。例如：

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

Manager(y,x)):

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

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

Manager(y,x)):

“有一種人是所有雇員經(jīng)理。”83第83頁(yè)3.謂詞公式定義2.2可按下述規(guī)則得到謂詞演算謂詞公式（合式公式）：?jiǎn)蝹€(gè)謂詞是謂詞公式，稱(chēng)為原子謂詞公式。若A是謂詞公式，則﹁A也是謂詞公式。若A，B都是謂詞公式，則A∧B，A∨B，A→B，A

B也都是謂詞公式。若A是謂詞公式，則(?x)A，(彐(

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

﹁，∧，∨，→，

必須指出是，本課程所用到謂詞演算為一階謂詞演算，不允許對(duì)謂詞符號(hào)或函數(shù)進(jìn)行量化。例如在一階謂詞演算中，(?P)P(A)這樣某些公式就不是合式公式。84第84頁(yè)4．量詞轄域

量詞轄域：位于量詞背面單個(gè)謂詞或者用括弧括起來(lái)謂詞公式。約束變?cè)c自由變?cè)狠犛騼?nèi)與量詞中同名變?cè)Q(chēng)為約束變?cè)灰粯用冊(cè)Q(chēng)為自由變?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>

85第85頁(yè)例：對(duì)于所有x，假如x是整數(shù)，則x或?yàn)檎蛘邽樨?fù)。解：用I(x)表達(dá)“x是整數(shù)”，P(x)表達(dá)“x是正數(shù)”，N(x)表達(dá)“x是負(fù)數(shù)”。則得到：(?x)I(x)→P(x)∨N(x)例：通過(guò)兩個(gè)不一樣點(diǎn)a和b直線(xiàn)L1和L2是同始終線(xiàn)。解：用T(x)表達(dá)x是點(diǎn)，L(x)表達(dá)x是線(xiàn)；P(x,y,z)表達(dá)直線(xiàn)x通過(guò)點(diǎn)y和z。E(x,y)表達(dá)x和y是同始終線(xiàn)。則得到：T(a)∧T(b)∧L(L1)∧L(L2)∧P(L1,a,b)∧P(L2,a,b)→E(L1,L2)例：有些小孩長(zhǎng)高了。解：C(x)表達(dá)x是小孩，BH(x)表達(dá)x長(zhǎng)高了。則得到：(?x)(C(x)∧BH(x))

等價(jià)于：~[(?x)(C(x)∧~BH(x))]86第86頁(yè)例：“最少有一偶數(shù)是素?cái)?shù)”。解：用A(x)表達(dá)x是偶數(shù)，B(x)表達(dá)x是素?cái)?shù)。則：

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

(?x)A(x)∧(?x)B(x)例：用謂詞演算來(lái)表達(dá)下面英文句子：*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第87頁(yè)例：凡是人都要學(xué)習(xí)。(?x)(HUMAN(x)→NEED-STUDY(x))例：有一種人弟兄是老師。

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

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

②變量和函數(shù)一般用小寫(xiě)字母表達(dá)。88第88頁(yè)2.4.4謂詞公式性質(zhì)1.謂詞公式解釋謂詞公式在個(gè)體域上解釋?zhuān)簜€(gè)體域中實(shí)體對(duì)謂詞演算體現(xiàn)式中每個(gè)常量、變量、謂詞和函數(shù)符號(hào)指派*。Friends(george,x)Friends(george,susie)TFriends(george,kate)F對(duì)于每一種解釋?zhuān)^詞公式都可求出一種真值（T或F）。89第89頁(yè)2.謂詞公式永真性、可滿(mǎn)足性、不可滿(mǎn)足性

2.謂詞公式永真性、可滿(mǎn)足性、不可滿(mǎn)足性

定義2.5對(duì)于謂詞公式P，假如最少存在一種解釋使得P在此解釋下真值為T(mén)，則稱(chēng)P是可滿(mǎn)足，不然，則稱(chēng)P是不可滿(mǎn)足。

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

定義2.3假如謂詞公式P對(duì)個(gè)體域D上任何一種解釋都取得真值T，則稱(chēng)P在D上是永真；假如P在每個(gè)非空個(gè)體域上均永真，則稱(chēng)P永真。90第90頁(yè)3.謂詞公式等價(jià)性定義2.6設(shè)P與Q是兩個(gè)謂詞公式，D是共同個(gè)體域，若對(duì)D上任一解釋?zhuān)琍與Q都有相同真值，則稱(chēng)公式P和Q在D上是等價(jià)。假如D是任意個(gè)體域，則稱(chēng)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à)性91第91頁(yè)

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

（3）假言三段論:P→Q,Q→R?P→R（4）全稱(chēng)固化（或全稱(chēng)化推理）:(?x)P(x)?P(y)

（5）存在固化:(?x)P(x)?P(y)92第92頁(yè)(1)假言推理假言推理是根據(jù)假言命題邏輯性質(zhì)進(jìn)行推理。分為充足條件假言推理，必要條件假言推理和充足必要條件假言推理三種。充足條件假言推理是根據(jù)充足條件假言命題邏輯性質(zhì)進(jìn)行推理。充足條件假言推理有兩條規(guī)則：規(guī)則1：肯定前件，就要肯定后件；否認(rèn)前件，不能否認(rèn)后件。規(guī)則2：否認(rèn)后件，就要否認(rèn)前件；肯定后件，不能肯定前件。93第93頁(yè)根據(jù)規(guī)則，充足條件假言推理有兩個(gè)正確形式：

（1）肯定前件式

假如P，那么QP___________

因此，Q（2）否認(rèn)后件式假如P，那么Q非Q___________因此，非P例子：94第94頁(yè)充足條件假言推理假如誰(shuí)驕傲自滿(mǎn)，那么他就要落后；小張驕傲自滿(mǎn)，因此，小張肯定要落后。假如誰(shuí)得了肺炎，他就一定要發(fā)熱；小李沒(méi)發(fā)熱，因此，小李沒(méi)患肺炎。例1和例2都是充足條件假言推理，前者是肯定前件式；后者是否認(rèn)后件式。兩個(gè)推理都符合推理規(guī)則，因此，都是正確。

根據(jù)規(guī)則，充足條件假言推理否認(rèn)前件式和肯定后件式都是無(wú)效。

例子：95第95頁(yè)假如降落物體不受外力影響，那么，它不會(huì)變化降落方向；這個(gè)物體受到了外力影響，因此，它會(huì)變化降落方向。假如趙某是走私犯，那么，他應(yīng)受法律制裁；經(jīng)查明，趙某確實(shí)受到了法律制裁，因此，趙某是走私犯。

上例都是不正確充足條件假言推理，由于：例1：違反了“否認(rèn)前件，不能否認(rèn)后件”規(guī)則；例2：違反了“肯定后件，不能肯定前件”規(guī)則。96第96頁(yè)(2)假言三段論在邏輯中，假言三段論是服從下列形式有效論證:

P→Q.Q→R.因此,P→R.換句話(huà)說(shuō)，這種論證陳說(shuō)假如第一種蘊(yùn)涵第二個(gè)，并且第二個(gè)蘊(yùn)涵第三個(gè)，則第一種蘊(yùn)涵第三個(gè)。例子：假如我不能起床，則我不能上班。假如我不能上班，則我不能得到報(bào)酬。因此，假如我不能起床，則我不能得到報(bào)酬。

97第97頁(yè)(3)全稱(chēng)固化（或全稱(chēng)化推理）(?x)P(x)?P(y)其中，y是個(gè)體域中任一種體，利用此永真蘊(yùn)涵式可消去公式中全稱(chēng)量詞。(4)存在固化

(?x)P(x)?P(y)

其中，y是個(gè)體域中某一種可使P(y)為真?zhèn)€體，利用此永真蘊(yùn)涵式可消去公式中存在量詞。98第98頁(yè)2.4.4謂詞公式性質(zhì)5.謂詞邏輯其他推理規(guī)則P規(guī)則：在推理任何步驟上都可引入前提。T規(guī)則：在推理過(guò)程中，假如前面步驟中有一種或多種公式永真蘊(yùn)含公式S，則可把S引入推理過(guò)程中。CP規(guī)則：假如能從任意引入命題R和前提集合中推出S來(lái)，則可從前提集合推出R→S來(lái)。反證法：

定理：Q為P1,P2,…,Pn邏輯結(jié)論，當(dāng)且僅當(dāng)(P1

∧

P2∧,…,∧Pn)∧﹁Q是不可滿(mǎn)足。99第99頁(yè)例：所有人都是會(huì)死，?x(Human(x)→Die(x))

由于諸葛亮是人，

Human（Zhugeliang）因此諸葛亮是會(huì)死。

Die（Zhugeliang）

{1}?x(Human(x)→Die(x))

P規(guī)則

{2}Human（Zhugeliang）

P規(guī)則{1,2}Die（Zhugeliang）

T規(guī)則

100第100頁(yè)2.4.4置換與合一在謂詞邏輯中，有些推理規(guī)則可應(yīng)用于一定合式公式和合式公式集，以產(chǎn)生新合式公式。一種主要推理規(guī)則是假元推理：W1,W1

→W2

?W2；全稱(chēng)化推理：(?x)W(x)?W(A)

；同步應(yīng)用假言推理和全稱(chēng)化推理。1.置換運(yùn)算：有體現(xiàn)式E和置換S={t1/x1,t2/x2,……,tn/xn}，用ES表達(dá)以項(xiàng)ti

(i=1,…,n)置換體現(xiàn)式E中出現(xiàn)變量xi。其中：每個(gè)xi都是變量，且xi≠xj(i≠j)。每個(gè)ti都是項(xiàng),且ti中不能出現(xiàn)xi。置換運(yùn)算規(guī)則：E中變量xi(i=1,…,n)均用ti置換。對(duì)所有變量只能一次同步置換完成。101第101頁(yè)例：體現(xiàn)式P[x,f(y),B]2個(gè)置換為：s1={z/x,w/y}，s2={A/y},則

P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]例：P[x,f(y),B]2個(gè)置換為：s3={q(z)/x,A/y},s4={c/x,A/y}，則P[x,f(y),B]s3=P[q(z),f(A),B]P[x,f(y),B]s4=P[c,f(A),B]性質(zhì)：①置換是可結(jié)合。用s1?s2表達(dá)兩個(gè)置換s1和s2合成，L表達(dá)某一體現(xiàn)式，則：(Ls1)s2=L(s1?s2)。并且(s1?s2)?s3=