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

1、Artificial Intelligence (AI)人工智能人工智能主講：何春梅Email：xiaoxiao_第二章：知識(shí)表示方法第二章：知識(shí)表示方法預(yù)備知識(shí)預(yù)備知識(shí)v人類的智能活動(dòng)過(guò)程主要是一個(gè)獲得并運(yùn)用知識(shí)人類的智能活動(dòng)過(guò)程主要是一個(gè)獲得并運(yùn)用知識(shí)的過(guò)程的過(guò)程v按照符號(hào)主義的觀點(diǎn)，按照符號(hào)主義的觀點(diǎn)，知識(shí)是一切智能行為的基知識(shí)是一切智能行為的基礎(chǔ)礎(chǔ)，要使計(jì)算機(jī)具有智能，首先必須使它擁有知，要使計(jì)算機(jī)具有智能，首先必須使它擁有知識(shí)識(shí)知識(shí)表示方法知識(shí)的概念知識(shí)的概念知識(shí)是人們?cè)诟脑炜陀^世界的知識(shí)是人們?cè)诟脑炜陀^世界的實(shí)踐中積累起來(lái)的實(shí)踐中積累起來(lái)的認(rèn)識(shí)認(rèn)識(shí)和和經(jīng)驗(yàn)經(jīng)驗(yàn)認(rèn)識(shí)：認(rèn)識(shí)：包括對(duì)事物

2、現(xiàn)象、本質(zhì)、屬性、狀態(tài)、聯(lián)系等包括對(duì)事物現(xiàn)象、本質(zhì)、屬性、狀態(tài)、聯(lián)系等的認(rèn)識(shí)的認(rèn)識(shí)經(jīng)驗(yàn)：經(jīng)驗(yàn)：包括包括解決問(wèn)題的微觀方法和宏觀方法解決問(wèn)題的微觀方法和宏觀方法p微觀方法：微觀方法：如步驟、操作、規(guī)則、過(guò)程、技巧等如步驟、操作、規(guī)則、過(guò)程、技巧等p宏觀方法：宏觀方法：如戰(zhàn)略、戰(zhàn)術(shù)、計(jì)謀、策略等如戰(zhàn)略、戰(zhàn)術(shù)、計(jì)謀、策略等eg：“if 大雁向南飛，大雁向南飛，then 冬天就要來(lái)臨了。冬天就要來(lái)臨了?！边@樣一條知識(shí)就是這樣一條知識(shí)就是人們經(jīng)過(guò)長(zhǎng)期的觀察，將人們經(jīng)過(guò)長(zhǎng)期的觀察，將“大雁向南飛大雁向南飛”與與“冬天來(lái)臨冬天來(lái)臨”這兩條信息這兩條信息關(guān)聯(lián)在一起。關(guān)聯(lián)在一起?！把┦前咨难┦前咨摹狈从逞┡c

3、顏色的一種關(guān)系。反映雪與顏色的一種關(guān)系。知識(shí)的概念知識(shí)的概念 數(shù)據(jù)：數(shù)據(jù)：是信息的載體，本身無(wú)確切含義。如：是信息的載體，本身無(wú)確切含義。如：水的溫度是水的溫度是100，木頭的長(zhǎng)度是，木頭的長(zhǎng)度是2米，大樓的高度是米，大樓的高度是100層層 信息：信息：是數(shù)據(jù)的關(guān)聯(lián)，賦予數(shù)據(jù)特定的含義，僅可理解為描是數(shù)據(jù)的關(guān)聯(lián)，賦予數(shù)據(jù)特定的含義，僅可理解為描述性知識(shí)。數(shù)據(jù)是沒(méi)有聯(lián)系的，孤立的，述性知識(shí)。數(shù)據(jù)是沒(méi)有聯(lián)系的，孤立的，只有當(dāng)數(shù)據(jù)用來(lái)描只有當(dāng)數(shù)據(jù)用來(lái)描述一個(gè)客觀事物和客觀事物的關(guān)系，形成有邏輯的數(shù)據(jù)流，述一個(gè)客觀事物和客觀事物的關(guān)系，形成有邏輯的數(shù)據(jù)流，他們才能被稱為信息他們才能被稱為信息。 知識(shí)：

4、知識(shí)：是對(duì)信息的關(guān)聯(lián)，或?qū)σ延兄R(shí)的再認(rèn)識(shí)。是對(duì)信息的關(guān)聯(lián)，或?qū)σ延兄R(shí)的再認(rèn)識(shí)。 如：西安如：西安7月月1日氣溫為日氣溫為30度，度，12月月1日氣溫為日氣溫為3度。度。 當(dāng)對(duì)這類信息進(jìn)行歸納和對(duì)比就會(huì)發(fā)現(xiàn)西安每年當(dāng)對(duì)這類信息進(jìn)行歸納和對(duì)比就會(huì)發(fā)現(xiàn)西安每年7月氣溫比月氣溫比較高，較高，12月氣溫比較低，形成了新知識(shí)。月氣溫比較低，形成了新知識(shí)。知識(shí)的劃分知識(shí)的劃分按知識(shí)的性質(zhì)：按知識(shí)的性質(zhì)：概念、命題、公理、定理、規(guī)則和方法概念、命題、公理、定理、規(guī)則和方法按知識(shí)的作用域：按知識(shí)的作用域：常識(shí)性知識(shí)，領(lǐng)域性知識(shí)常識(shí)性知識(shí)，領(lǐng)域性知識(shí)按知識(shí)的等級(jí)：按知識(shí)的等級(jí)：p零級(jí)知識(shí)：零級(jí)知識(shí)：事實(shí)性知識(shí)

5、。用于描述事物的概念、定義、屬性等；事實(shí)性知識(shí)。用于描述事物的概念、定義、屬性等； 或用于描述問(wèn)題的狀態(tài)、環(huán)境、條件等?；蛴糜诿枋鰡?wèn)題的狀態(tài)、環(huán)境、條件等。p一級(jí)知識(shí)：一級(jí)知識(shí)：過(guò)程性知識(shí)。用于問(wèn)題求解過(guò)程的操作、演算和行過(guò)程性知識(shí)。用于問(wèn)題求解過(guò)程的操作、演算和行為的知識(shí)。為的知識(shí)。表示方式：產(chǎn)生式、謂詞、語(yǔ)義網(wǎng)絡(luò)等。表示方式：產(chǎn)生式、謂詞、語(yǔ)義網(wǎng)絡(luò)等。p二級(jí)知識(shí)：二級(jí)知識(shí)：控制性知識(shí)，元知識(shí)或超知識(shí)。是關(guān)于如何使用過(guò)控制性知識(shí)，元知識(shí)或超知識(shí)。是關(guān)于如何使用過(guò)程性知識(shí)的知識(shí)。程性知識(shí)的知識(shí)。例如：推理策略、搜索策略、不確定性的傳例如：推理策略、搜索策略、不確定性的傳播策略。播策略。 知識(shí)的

6、劃分知識(shí)的劃分按知識(shí)的層次：按知識(shí)的層次：p表層知識(shí)：表層知識(shí)：描述客觀事物的現(xiàn)象的知識(shí)。例如：感性、事實(shí)性描述客觀事物的現(xiàn)象的知識(shí)。例如：感性、事實(shí)性知識(shí)知識(shí)p深層知識(shí)：深層知識(shí)：描述客觀事物本質(zhì)、內(nèi)涵等的知識(shí)。例如：理論知描述客觀事物本質(zhì)、內(nèi)涵等的知識(shí)。例如：理論知識(shí)識(shí)按知識(shí)的確定性：按知識(shí)的確定性：p確定性知識(shí)：確定性知識(shí)：可以說(shuō)明其真值為真或?yàn)榧俚闹R(shí)可以說(shuō)明其真值為真或?yàn)榧俚闹R(shí)p不確定性知識(shí)：不確定性知識(shí)：包括不精確、模糊、不完備知識(shí)包括不精確、模糊、不完備知識(shí)l不精確：不精確：知識(shí)本身有真假，但由于認(rèn)識(shí)水平限制卻不能肯定知知識(shí)本身有真假，但由于認(rèn)識(shí)水平限制卻不能肯定知識(shí)的真假。識(shí)

7、的真假。表示：用可信度、概率等描述表示：用可信度、概率等描述l模糊：模糊：知識(shí)本身的邊界就是不清楚的。知識(shí)本身的邊界就是不清楚的。例如：大，小等。表示：例如：大，小等。表示：用可能性、隸屬度來(lái)描述用可能性、隸屬度來(lái)描述l不完備：不完備：解決問(wèn)題時(shí)不具備解決該問(wèn)題的全部知識(shí)。解決問(wèn)題時(shí)不具備解決該問(wèn)題的全部知識(shí)。例如：醫(yī)例如：醫(yī)生看病生看病知識(shí)的劃分知識(shí)的劃分按人類的思維及認(rèn)識(shí)方法：按人類的思維及認(rèn)識(shí)方法：p邏輯性知識(shí)：邏輯性知識(shí)：是反映人類邏輯思維過(guò)程的知識(shí)，一般具有因果是反映人類邏輯思維過(guò)程的知識(shí)，一般具有因果關(guān)系或難以精確描述的特點(diǎn)，是人類的經(jīng)驗(yàn)性知識(shí)和直觀感覺(jué)；關(guān)系或難以精確描述的特點(diǎn)，

8、是人類的經(jīng)驗(yàn)性知識(shí)和直觀感覺(jué)；如：人的為人處事的經(jīng)驗(yàn)與風(fēng)格如：人的為人處事的經(jīng)驗(yàn)與風(fēng)格p形象性知識(shí)：形象性知識(shí)：通過(guò)事物的形象建立起來(lái)的知識(shí)。通過(guò)事物的形象建立起來(lái)的知識(shí)。如如: :什么是人？什么是人？按知識(shí)的獲取方式：按知識(shí)的獲取方式：p顯性知識(shí)：顯性知識(shí)：指可通過(guò)文字、語(yǔ)言、圖形、聲音等形式編碼記錄指可通過(guò)文字、語(yǔ)言、圖形、聲音等形式編碼記錄和傳播的知識(shí)；和傳播的知識(shí)；如：教材、音視頻光盤(pán)。如：教材、音視頻光盤(pán)。p隱性知識(shí)：隱性知識(shí)：指人們長(zhǎng)期實(shí)踐中積累獲得的知識(shí)，不易用顯性知指人們長(zhǎng)期實(shí)踐中積累獲得的知識(shí)，不易用顯性知識(shí)表達(dá)的知識(shí)。識(shí)表達(dá)的知識(shí)。如：每個(gè)人都有不同的審美觀。如：每個(gè)人都有

9、不同的審美觀。人工智能系統(tǒng)中的知識(shí)人工智能系統(tǒng)中的知識(shí)v 一個(gè)智能程序高水平的運(yùn)行需要有關(guān)的一個(gè)智能程序高水平的運(yùn)行需要有關(guān)的事實(shí)知識(shí)、規(guī)則知事實(shí)知識(shí)、規(guī)則知識(shí)、控制知識(shí)和元知識(shí)。識(shí)、控制知識(shí)和元知識(shí)。v 事實(shí)知識(shí)：事實(shí)知識(shí)：是有關(guān)問(wèn)題環(huán)境的一些事物的知識(shí)，常以是有關(guān)問(wèn)題環(huán)境的一些事物的知識(shí)，常以“是是”的形式出現(xiàn)。的形式出現(xiàn)。 如事物的分類、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等如事物的分類、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等 事實(shí)是靜態(tài)的為人們共享的可公開(kāi)獲得的公認(rèn)的知識(shí)，事實(shí)是靜態(tài)的為人們共享的可公開(kāi)獲得的公認(rèn)的知識(shí)，在知在知識(shí)庫(kù)中屬低層的知識(shí)。識(shí)庫(kù)中屬低層的知識(shí)。 如：雪是白色的、

10、鳥(niǎo)有翅膀、張三李四是好朋友、這輛車是如：雪是白色的、鳥(niǎo)有翅膀、張三李四是好朋友、這輛車是張三的張三的v 規(guī)則知識(shí)：規(guī)則知識(shí)：是有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因是有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)，是動(dòng)態(tài)的，常以果關(guān)系知識(shí)，是動(dòng)態(tài)的，常以“如果如果那么那么” 形式出現(xiàn)。形式出現(xiàn)。人工智能系統(tǒng)中的知識(shí)人工智能系統(tǒng)中的知識(shí)v 控制知識(shí)：控制知識(shí)：是有關(guān)問(wèn)題的求解步驟、技巧的知識(shí)，告訴人是有關(guān)問(wèn)題的求解步驟、技巧的知識(shí)，告訴人們?cè)趺醋鲆患?，也包括?dāng)有多個(gè)動(dòng)作同時(shí)被激活時(shí)應(yīng)選們?cè)趺醋鲆患?，也包括?dāng)有多個(gè)動(dòng)作同時(shí)被激活時(shí)應(yīng)選哪一個(gè)動(dòng)作來(lái)執(zhí)行的知識(shí)。哪一個(gè)動(dòng)作來(lái)執(zhí)行的知識(shí)?？刂浦R(shí)常

11、與程序結(jié)合在一起控制知識(shí)常與程序結(jié)合在一起出現(xiàn)，如一個(gè)問(wèn)題求解的算法可以看做是一種知識(shí)表示。出現(xiàn)，如一個(gè)問(wèn)題求解的算法可以看做是一種知識(shí)表示。v 元知識(shí)：元知識(shí)：是有關(guān)知識(shí)的知識(shí)，是是有關(guān)知識(shí)的知識(shí)，是知識(shí)庫(kù)中的高層知識(shí)知識(shí)庫(kù)中的高層知識(shí)。 包括怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等包括怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識(shí)。知識(shí)。 元知識(shí)與控制知識(shí)是有重迭的元知識(shí)與控制知識(shí)是有重迭的，對(duì)一個(gè)大的程序來(lái)說(shuō)，以元，對(duì)一個(gè)大的程序來(lái)說(shuō)，以元知識(shí)或說(shuō)元規(guī)則形式體現(xiàn)控制知識(shí)更為方便，因?yàn)橹R(shí)或說(shuō)元規(guī)則形式體現(xiàn)控制知識(shí)更為方便，因?yàn)樵R(shí)存元知識(shí)存于知識(shí)庫(kù)中，而控制知識(shí)常與程序結(jié)

12、合在一起出現(xiàn)，從而不于知識(shí)庫(kù)中，而控制知識(shí)常與程序結(jié)合在一起出現(xiàn)，從而不容易修改容易修改。 知識(shí)表示知識(shí)表示v 知識(shí)表示：知識(shí)表示：是研究用機(jī)器表示知識(shí)的可行性、有效性的一是研究用機(jī)器表示知識(shí)的可行性、有效性的一般方法，是一種般方法，是一種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與與控制結(jié)構(gòu)控制結(jié)構(gòu)的統(tǒng)一體，既考慮知的統(tǒng)一體，既考慮知識(shí)的識(shí)的存儲(chǔ)存儲(chǔ)又考慮知識(shí)的又考慮知識(shí)的使用使用。v 知識(shí)表示的要求：知識(shí)表示的要求：p 表示能力：表示能力：能否能否正確正確、有效有效地表示問(wèn)題。包括：表范圍的廣泛性、地表示問(wèn)題。包括：表范圍的廣泛性、領(lǐng)域知識(shí)表示的高效性、對(duì)非確定性知識(shí)表示的支持程度。領(lǐng)域知識(shí)表示的高效性、對(duì)非確定性

13、知識(shí)表示的支持程度。p 可利用性：可利用性：可利用這些知識(shí)可利用這些知識(shí)進(jìn)行有效推理進(jìn)行有效推理。包括：對(duì)推理的適應(yīng)。包括：對(duì)推理的適應(yīng)性，對(duì)高效算法的支持程度。性，對(duì)高效算法的支持程度。p 可實(shí)現(xiàn)性：可實(shí)現(xiàn)性：要便于計(jì)算機(jī)直接對(duì)其進(jìn)行處理要便于計(jì)算機(jī)直接對(duì)其進(jìn)行處理 p 可組織性：可組織性：可以按某種方式把知識(shí)組織成可以按某種方式把知識(shí)組織成某種知識(shí)結(jié)構(gòu)某種知識(shí)結(jié)構(gòu)p 可維護(hù)性：可維護(hù)性：便于對(duì)知識(shí)的增、刪、改等操作便于對(duì)知識(shí)的增、刪、改等操作p 自然性：自然性：符合人們的日常習(xí)慣符合人們的日常習(xí)慣p 可理解性：可理解性：知識(shí)應(yīng)易讀、易懂、易獲取等知識(shí)應(yīng)易讀、易懂、易獲取等 內(nèi)容提要1.1.

14、狀態(tài)空間法狀態(tài)空間法2.2.問(wèn)題歸約法問(wèn)題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法5.5.其他方法其他方法內(nèi)容提要1.1.狀態(tài)空間法狀態(tài)空間法2.2.問(wèn)題歸約法問(wèn)題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法5.5.其他方法其他方法狀態(tài)空間法v人工智能雖有多個(gè)研究領(lǐng)域，且每個(gè)研究領(lǐng)域又人工智能雖有多個(gè)研究領(lǐng)域，且每個(gè)研究領(lǐng)域又各有自己的規(guī)律和特點(diǎn)，但都可抽象為一個(gè)各有自己的規(guī)律和特點(diǎn)，但都可抽象為一個(gè)“問(wèn)問(wèn)題求解題求解”的過(guò)程。問(wèn)題求解過(guò)程實(shí)際上是一個(gè)的過(guò)程。問(wèn)題求解過(guò)程實(shí)際上是一個(gè)搜搜索索過(guò)程。過(guò)程。v 問(wèn)題求解技術(shù)主要是兩個(gè)方面：?jiǎn)栴}求解技術(shù)主要是兩

15、個(gè)方面： 問(wèn)題的表示問(wèn)題的表示 求解的方法求解的方法v 狀態(tài)空間法狀態(tài)空間法（State Space Representation）：）：狀態(tài)空間法是用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法。它是人狀態(tài)空間法是用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法。它是人工智能中最基本的形式化方法，用工智能中最基本的形式化方法，用“狀態(tài)（狀態(tài)（state）”和和“算符算符（operator）”來(lái)表示問(wèn)題。來(lái)表示問(wèn)題。狀態(tài)空間法v 狀態(tài)空間法的三要素狀態(tài)空間法的三要素p(1) 狀態(tài)（狀態(tài)（state）：）：描述某類不同事物間的差別而引入的一描述某類不同事物間的差別而引入的一組最少變量組最少變量 q0，q1，qn的有序集合

16、，是表示問(wèn)題解法中的有序集合，是表示問(wèn)題解法中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)。有序集合中每個(gè)元素每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)。有序集合中每個(gè)元素qi（i= 0,1,.,n）為集合的分量，稱為）為集合的分量，稱為狀態(tài)變量狀態(tài)變量。給定每個(gè)分量的一。給定每個(gè)分量的一組值就得到一個(gè)具體的狀態(tài)。組值就得到一個(gè)具體的狀態(tài)。p (2) 算符（算符（operator）：）：使問(wèn)題從一種狀態(tài)變化為另一種狀使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。態(tài)的手段稱為操作符或算符。p (3) 狀態(tài)空間方法：狀態(tài)空間方法：是是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖系的圖，它包含三種說(shuō)明

17、的集合，即三元狀態(tài)（，它包含三種說(shuō)明的集合，即三元狀態(tài)（S，F(xiàn)，G）。）。S：所有可能的問(wèn)題初始狀態(tài)集合；：所有可能的問(wèn)題初始狀態(tài)集合；F：操作符集合；：操作符集合；G：目：目標(biāo)狀態(tài)集合。標(biāo)狀態(tài)集合。狀態(tài)空間法v 狀態(tài)空間法舉例：狀態(tài)空間法舉例：下棋、迷宮及各種游戲。下棋、迷宮及各種游戲。十五數(shù)碼難題十五數(shù)碼難題(15 puzzle)(15 puzzle)：由由1515個(gè)編有個(gè)編有1 1至至1515并放在并放在4 44 4方格棋盤(pán)上的可走動(dòng)的棋子組成。方格棋盤(pán)上的可走動(dòng)的棋子組成。119415131275861321014123456789101112131415初始棋局初始棋局目標(biāo)棋局目標(biāo)棋

18、局十五數(shù)碼難題十五數(shù)碼難題11119 94 415151 13 312127 75 58 86 613132 21010141411119 915151 13 34 412127 75 58 86 613132 21010141411119 94 415151 13 312127 75 58 86 613132 21010141411119 94 415151 13 38 812127 75 56 613132 21010141411119 94 415151 13 312127 75 58 86 613132 2101014141 12 23 34 45 56 67 78 89 910101

19、1111212131314141515初始狀態(tài)初始狀態(tài)目標(biāo)狀態(tài)目標(biāo)狀態(tài)如何把初試棋局如何把初試棋局變成目標(biāo)棋局？變成目標(biāo)棋局？首先把適用的算符首先把適用的算符用于初始狀態(tài)，以產(chǎn)用于初始狀態(tài)，以產(chǎn)生新的狀態(tài)生新的狀態(tài)再把另一些適用算符再把另一些適用算符用于這些新的狀態(tài)；用于這些新的狀態(tài)；這樣繼續(xù)下去，直至這樣繼續(xù)下去，直至產(chǎn)生目標(biāo)狀態(tài)為止產(chǎn)生目標(biāo)狀態(tài)為止?fàn)顟B(tài)空間法v 問(wèn)題的表示對(duì)求解工作有很大影響。人們問(wèn)題的表示對(duì)求解工作有很大影響。人們希望有較小的狀希望有較小的狀態(tài)空間表示態(tài)空間表示。v 例如，對(duì)于十五數(shù)碼問(wèn)題：例如，對(duì)于十五數(shù)碼問(wèn)題：可以規(guī)定可以規(guī)定15460條規(guī)則條規(guī)則p “上移棋子上移棋

20、子1，下移棋子，下移棋子1，左移棋子，左移棋子1，右移棋子，右移棋子1”p “上移棋子上移棋子2，下移棋子，下移棋子2，左移棋子，左移棋子2，右移棋子，右移棋子2 ”p .如果用如果用“上下左右移動(dòng)空格上下左右移動(dòng)空格”，則只需，則只需4條規(guī)則。所以，條規(guī)則。所以，移動(dòng)空格是一種較好的表示。移動(dòng)空格是一種較好的表示。狀態(tài)空間法v 狀態(tài)空間法舉例：狀態(tài)空間法舉例：旅行商問(wèn)題旅行商問(wèn)題旅行商問(wèn)題旅行商問(wèn)題(Traveling Salesman Problem(Traveling Salesman Problem，TSP)TSP)：假定起始假定起始城市為城市為A狀態(tài)空間法旅行商問(wèn)題旅行商問(wèn)題(Tra

21、veling Salesman Problem(Traveling Salesman Problem，TSP)TSP)：算符的代價(jià)算符的代價(jià)狀態(tài)空間法v 狀態(tài)圖示法：狀態(tài)圖示法：狀態(tài)空間的圖示形式稱為狀態(tài)空間的圖示形式稱為狀態(tài)空間圖狀態(tài)空間圖。狀態(tài)。狀態(tài)圖中有幾個(gè)術(shù)語(yǔ)。圖中有幾個(gè)術(shù)語(yǔ)。 節(jié)點(diǎn)節(jié)點(diǎn)(Node)：圖形上的匯合點(diǎn)，用來(lái)表示圖形上的匯合點(diǎn)，用來(lái)表示狀態(tài)狀態(tài)、事件事件和和時(shí)間時(shí)間關(guān)系的匯合關(guān)系的匯合。 弧線弧線(Arc)：節(jié)點(diǎn)間的連接線，表示節(jié)點(diǎn)間的連接線，表示算符算符； 有向圖有向圖(Directed Graph)：一對(duì)節(jié)點(diǎn)用弧線連接起來(lái)，從一一對(duì)節(jié)點(diǎn)用弧線連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向另一

22、個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)。 后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)(Descendant node)與父輩節(jié)點(diǎn)與父輩節(jié)點(diǎn)(Parent node)：如果如果某條弧線從節(jié)點(diǎn)某條弧線從節(jié)點(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)或祖先。狀態(tài)空間法v 狀態(tài)圖示法：狀態(tài)圖示法：狀態(tài)空間的圖示形式稱為狀態(tài)空間的圖示形式稱為狀態(tài)空間圖狀態(tài)空間圖。狀態(tài)。狀態(tài)圖中有幾個(gè)術(shù)語(yǔ)。圖中有幾個(gè)術(shù)語(yǔ)。 路徑路徑(Path)：某個(gè)節(jié)點(diǎn)序列某個(gè)節(jié)點(diǎn)序列(ni1,ni2,nik)當(dāng)當(dāng)j=2,3,k時(shí)，如時(shí)，如果對(duì)于

23、每一個(gè)果對(duì)于每一個(gè)ni,j-1都有一個(gè)后繼節(jié)點(diǎn)都有一個(gè)后繼節(jié)點(diǎn)nij存在，那么就把這個(gè)存在，那么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)ni1至節(jié)點(diǎn)至節(jié)點(diǎn)nik的長(zhǎng)度為的長(zhǎng)度為k的路徑。的路徑。 代價(jià)代價(jià)(Cost)：用用c(ni,nj)來(lái)表示從節(jié)點(diǎn)來(lái)表示從節(jié)點(diǎn)ni指向節(jié)點(diǎn)指向節(jié)點(diǎn)nj的的 那段弧那段弧線的代價(jià)。線的代價(jià)。兩節(jié)點(diǎn)間路徑的代價(jià)兩節(jié)點(diǎn)間路徑的代價(jià)等于連接該路徑上各節(jié)點(diǎn)的等于連接該路徑上各節(jié)點(diǎn)的所有弧線代價(jià)之和。所有弧線代價(jià)之和。 圖的顯示說(shuō)明圖的顯示說(shuō)明/隱示說(shuō)明：隱示說(shuō)明：指各節(jié)點(diǎn)及其具有代價(jià)的弧線可指各節(jié)點(diǎn)及其具有代價(jià)的弧線可以以/不可以由一張表明確給出。不可以由一張表明確

24、給出。顯然，顯示說(shuō)明對(duì)于大型的顯然，顯示說(shuō)明對(duì)于大型的圖是不切實(shí)際的，而對(duì)于具有無(wú)限節(jié)點(diǎn)集合的圖則是不可能圖是不切實(shí)際的，而對(duì)于具有無(wú)限節(jié)點(diǎn)集合的圖則是不可能的。的。狀態(tài)空間法v 各種問(wèn)題都可用狀態(tài)空間加以表示，并用各種問(wèn)題都可用狀態(tài)空間加以表示，并用狀態(tài)空間搜索法狀態(tài)空間搜索法來(lái)求解。下面簡(jiǎn)單介紹一種來(lái)求解。下面簡(jiǎn)單介紹一種產(chǎn)生式系統(tǒng)（產(chǎn)生式系統(tǒng)（production system）描述的搜索算法。）描述的搜索算法。v 產(chǎn)生式系統(tǒng)（產(chǎn)生式系統(tǒng)（production systemproduction system）由三部分組成：）由三部分組成：一個(gè)總數(shù)據(jù)庫(kù)：一個(gè)總數(shù)據(jù)庫(kù)：0 0級(jí)知識(shí)。它含有與

25、具體任務(wù)有關(guān)的信級(jí)知識(shí)。它含有與具體任務(wù)有關(guān)的信息。息。一套規(guī)則：一套規(guī)則：1 1級(jí)知識(shí)。它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。級(jí)知識(shí)。它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。一個(gè)控制策略（程序）：一個(gè)控制策略（程序）：2 2級(jí)知識(shí)。它確定應(yīng)該采用哪級(jí)知識(shí)。它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)算?？刂撇呗杂煽刂葡到y(tǒng)選擇和確定。停止計(jì)算?？刂撇呗杂煽刂葡到y(tǒng)選擇和確定。 狀態(tài)空間法v 狀態(tài)空間法舉例：狀態(tài)空間法舉例：猴子和香蕉問(wèn)題：猴子和香蕉問(wèn)題：在一個(gè)房間內(nèi)有一只猴子、一個(gè)箱在一個(gè)房間內(nèi)有一只猴子、一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高

26、度子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢? ?猴子和香蕉問(wèn)題v 解題過(guò)程解題過(guò)程 用一個(gè)四元表列（用一個(gè)四元表列（W，x，Y，z）來(lái)表示這個(gè)問(wèn)題狀態(tài)）來(lái)表示這個(gè)問(wèn)題狀態(tài)p W：猴子的水平位置；：猴子的水平位置；p x： 當(dāng)猴子在箱子頂上時(shí)取當(dāng)猴子在箱子頂上時(shí)取1；否則??；否則取0；p Y： 箱子的水平位置；箱子的水平位置；p z： 當(dāng)猴子摘到香蕉時(shí)取當(dāng)猴子摘到香蕉時(shí)取1；否則??；否則取0。p 初始狀態(tài)為初始狀態(tài)為(a,0,b,0) ，目標(biāo)狀態(tài)為，目標(biāo)狀態(tài)為(c,1,c,1) 這個(gè)問(wèn)題的操作（算符）如

27、下：這個(gè)問(wèn)題的操作（算符）如下：pgoto（U）表示猴子走到水平位置）表示猴子走到水平位置Uppushbox（V）猴子把箱子推到水平位置）猴子把箱子推到水平位置Vpclimbbox猴子爬上箱頂猴子爬上箱頂pgrasp猴子摘到香蕉猴子摘到香蕉猴子和香蕉問(wèn)題v 解題過(guò)程解題過(guò)程該初始狀態(tài)變換為目標(biāo)該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為：狀態(tài)的操作序列為：pStep1: goto(b)pStep2: pushbox(c)pStep3: climbboxpStep4: grasp猴子和香蕉問(wèn)題v 狀態(tài)空間圖狀態(tài)空間圖(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0

28、）（c，1，c，1）（a，0，b，0）目標(biāo)狀態(tài)目標(biāo)狀態(tài)goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）goto（U）U=VV=c，climbboxgrasp內(nèi)容提要1.1.狀態(tài)空間法狀態(tài)空間法2.2.問(wèn)題歸約法問(wèn)題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法5.5.其他方法其他方法問(wèn)題歸約法v 問(wèn)題歸約（問(wèn)題歸約（Problem Reduction） 是另外一種是另外一種基于狀態(tài)空間基于狀態(tài)空間的問(wèn)題描述與求解方法的問(wèn)題描述與求解方法 已知問(wèn)題的描述，通過(guò)一系列已知問(wèn)題的描述，通過(guò)一系列變換變換把此問(wèn)題變?yōu)橐粋€(gè)把此問(wèn)題變?yōu)橐粋€(gè)子問(wèn)題

29、子問(wèn)題集合集合 這些子問(wèn)題的解可以這些子問(wèn)題的解可以直接得到（本原問(wèn)題）直接得到（本原問(wèn)題），從而解決了初，從而解決了初始問(wèn)題始問(wèn)題問(wèn)題歸約法v 問(wèn)題歸約法的組成部分問(wèn)題歸約法的組成部分一個(gè)初始問(wèn)題描述；一個(gè)初始問(wèn)題描述；一套把問(wèn)題變換為子問(wèn)題的一套把問(wèn)題變換為子問(wèn)題的操作符操作符；一套一套本原問(wèn)題本原問(wèn)題描述。描述。( (本原問(wèn)題本原問(wèn)題: :不能再分解或變換且不能再分解或變換且直接可解的子問(wèn)題直接可解的子問(wèn)題) )v 問(wèn)題歸約的實(shí)質(zhì)：?jiǎn)栴}歸約的實(shí)質(zhì)：從目標(biāo)（要解決的問(wèn)題）出發(fā)從目標(biāo)（要解決的問(wèn)題）出發(fā)逆向推理逆向推理，建立子問(wèn)題，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直到最后把初始問(wèn)題歸約為以及子

30、問(wèn)題的子問(wèn)題，直到最后把初始問(wèn)題歸約為一一個(gè)本原問(wèn)題集合個(gè)本原問(wèn)題集合。問(wèn)題歸約法v 問(wèn)題歸約法舉例：?jiǎn)栴}歸約法舉例：漢諾塔問(wèn)題（漢諾塔問(wèn)題（ Hanoi ） p 從從1移到移到3p 每次移動(dòng)一個(gè)盤(pán)子每次移動(dòng)一個(gè)盤(pán)子p 大盤(pán)在下小盤(pán)在上大盤(pán)在下小盤(pán)在上123CBA初始狀態(tài)（初始狀態(tài)（111）目標(biāo)狀態(tài)（目標(biāo)狀態(tài)（333）CBA漢諾塔問(wèn)題v 原始問(wèn)題可以歸約為下列原始問(wèn)題可以歸約為下列3 3個(gè)子問(wèn)題：個(gè)子問(wèn)題：子問(wèn)題子問(wèn)題1 1：子問(wèn)題子問(wèn)題2 2：子問(wèn)題子問(wèn)題3 3：漢諾塔問(wèn)題v 歸約過(guò)程（歸約過(guò)程（3 3個(gè)圓盤(pán)）個(gè)圓盤(pán)）漢諾塔問(wèn)題v 漢諾塔問(wèn)題歸約圖漢諾塔問(wèn)題歸約圖本原問(wèn)題本原問(wèn)題本原問(wèn)題本原

31、問(wèn)題與或圖與或圖CBA問(wèn)題歸約法v 與或圖表示：與或圖表示：用一個(gè)類似于圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為用一個(gè)類似于圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合。后繼問(wèn)題的替換集合。與圖：與圖：把一個(gè)復(fù)雜問(wèn)題把一個(gè)復(fù)雜問(wèn)題分解為若干個(gè)較為簡(jiǎn)單的分解為若干個(gè)較為簡(jiǎn)單的子問(wèn)題，形成子問(wèn)題，形成“與與”樹(shù)。樹(shù)。或圖：或圖：把原問(wèn)題變換為把原問(wèn)題變換為若干個(gè)較為容易求解的新若干個(gè)較為容易求解的新問(wèn)題，形成問(wèn)題，形成“或或”樹(shù)。樹(shù)。問(wèn)題歸約法v 與或圖表示：與或圖表示：BCDEFGAHMBCDEFGAN子問(wèn)題替代集合結(jié)構(gòu)圖子問(wèn)題替代集合結(jié)構(gòu)圖與或圖與或圖問(wèn)題歸約法v 一些關(guān)于與或圖的術(shù)語(yǔ)一些關(guān)于與或圖的術(shù)語(yǔ)起

32、始節(jié)點(diǎn)起始節(jié)點(diǎn)對(duì)應(yīng)于原對(duì)應(yīng)于原始問(wèn)題描始問(wèn)題描述述終葉節(jié)點(diǎn)對(duì)應(yīng)于本原問(wèn)題終葉節(jié)點(diǎn)對(duì)應(yīng)于本原問(wèn)題問(wèn)題歸約法v 與或圖的構(gòu)成規(guī)則與或圖的構(gòu)成規(guī)則 1 1）與或圖中的每個(gè)節(jié)點(diǎn)代表一）與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集合。個(gè)要解決的單一問(wèn)題或問(wèn)題集合。圖中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)圖中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題題A A。 2 2）對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)稱為）對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)稱為終葉節(jié)點(diǎn)，它沒(méi)有后繼節(jié)點(diǎn)。終葉節(jié)點(diǎn)，它沒(méi)有后繼節(jié)點(diǎn)。 3 3）對(duì)于把算符應(yīng)用于問(wèn)題）對(duì)于把算符應(yīng)用于問(wèn)題A A的每的每種可能情況，都把問(wèn)題變換為一種可能情況，都把問(wèn)題變換為一個(gè)子問(wèn)題集合；有向弧線自個(gè)子問(wèn)題集合；

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

34、個(gè)算符可應(yīng)用于問(wèn)題可應(yīng)用于問(wèn)題A A，而且這個(gè)算符產(chǎn)，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則合時(shí)，由上述規(guī)則3 3）和規(guī)則）和規(guī)則4 4）所產(chǎn)生的圖可以得到簡(jiǎn)化。所產(chǎn)生的圖可以得到簡(jiǎn)化。MDEFAADEF簡(jiǎn)化簡(jiǎn)化問(wèn)題歸約法v與或圖的搜索：與或圖的搜索：目的在于表明起始節(jié)點(diǎn)是有解的。目的在于表明起始節(jié)點(diǎn)是有解的。v可解節(jié)點(diǎn)可解節(jié)點(diǎn)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)（對(duì)應(yīng)于本原問(wèn)題）。終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)（對(duì)應(yīng)于本原問(wèn)題）。如果某個(gè)非終葉節(jié)點(diǎn)含有如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)或后繼節(jié)點(diǎn)，那么只要當(dāng)其后，那么只要當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解繼

35、節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。的。如果某個(gè)非終葉節(jié)點(diǎn)含有如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)與后繼節(jié)點(diǎn)，那么只有當(dāng)其后，那么只有當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。問(wèn)題歸約法v不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。 如果某個(gè)非終葉節(jié)點(diǎn)含有如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)或后繼節(jié)點(diǎn)，那么只有當(dāng)其，那么只有當(dāng)其全全部后裔為不可解時(shí)部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。，此非終葉節(jié)點(diǎn)才是不可解的。 如果某個(gè)非終葉節(jié)點(diǎn)含有如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)與后繼節(jié)點(diǎn)，那么只要

36、當(dāng)其，那么只要當(dāng)其后后裔至少有一個(gè)為不可解時(shí)裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。，此非終葉節(jié)點(diǎn)才是不可解的。v解樹(shù)解樹(shù)由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹(shù)稱為解樹(shù)。點(diǎn)為可解節(jié)點(diǎn)的子樹(shù)稱為解樹(shù)。解樹(shù)中一定包含初始節(jié)點(diǎn)，它對(duì)應(yīng)于原始問(wèn)題。解樹(shù)中一定包含初始節(jié)點(diǎn)，它對(duì)應(yīng)于原始問(wèn)題。問(wèn)題歸約法ttttttttt有解節(jié)點(diǎn)有解節(jié)點(diǎn)無(wú)解節(jié)點(diǎn)無(wú)解節(jié)點(diǎn)終葉節(jié)點(diǎn)終葉節(jié)點(diǎn)與或圖例子與或圖例子原始問(wèn)題原始問(wèn)題有一有一個(gè)以上的解個(gè)以上的解原始問(wèn)題原始問(wèn)題有有解解內(nèi)容提要1.1.狀態(tài)空間法狀態(tài)空間法2.2.問(wèn)題歸約法問(wèn)題歸約法3.

37、3.謂詞邏輯法謂詞邏輯法4.4.語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法5.5.其他方法其他方法謂詞邏輯法v命題邏輯與謂詞邏輯命題邏輯與謂詞邏輯v命題命題v命題邏輯的局限性命題邏輯的局限性v謂詞謂詞謂詞邏輯法v命題邏輯與謂詞邏輯命題邏輯與謂詞邏輯命題邏輯與謂詞邏輯是最先用于人工智能的兩種邏輯，命題邏輯與謂詞邏輯是最先用于人工智能的兩種邏輯，對(duì)于知識(shí)的形式化表示，特別是定理的證明發(fā)揮了重對(duì)于知識(shí)的形式化表示，特別是定理的證明發(fā)揮了重要作用要作用雖然命題邏輯能把客觀世界的各種事實(shí)表示為邏輯命雖然命題邏輯能把客觀世界的各種事實(shí)表示為邏輯命題，但它具有較大局限性。命題邏輯只能進(jìn)行命題間題，但它具有較大局限性。命題邏輯只能

38、進(jìn)行命題間關(guān)系關(guān)系的推理，無(wú)法解決與的推理，無(wú)法解決與命題結(jié)構(gòu)命題結(jié)構(gòu)和和成分成分有關(guān)的推理有關(guān)的推理問(wèn)題，問(wèn)題，不適合表示較復(fù)雜的問(wèn)題不適合表示較復(fù)雜的問(wèn)題。謂詞邏輯是在命題邏輯的基礎(chǔ)上發(fā)展而來(lái)的，命題邏謂詞邏輯是在命題邏輯的基礎(chǔ)上發(fā)展而來(lái)的，命題邏輯可看作是謂詞邏輯的一種特殊形式。輯可看作是謂詞邏輯的一種特殊形式。謂詞邏輯法v命題命題命題是具有真假意義的語(yǔ)句。命題是具有真假意義的語(yǔ)句。命題代表人們進(jìn)行思維時(shí)的一種判斷，若命題的意義命題代表人們進(jìn)行思維時(shí)的一種判斷，若命題的意義為真，稱它的真值為為真，稱它的真值為“真真”，記作，記作“T”；若命題的意；若命題的意義為假，稱它的真值為義為假，稱

39、它的真值為“假假”，記作，記作“F”。例如：。例如：p“西安是陜西省省會(huì)西安是陜西省省會(huì)”“”“10大于大于6”是真值為是真值為“T”的命題；的命題；p“月亮是方的月亮是方的”“”“煤炭是白的煤炭是白的”是真值為是真值為“F”的命題；的命題；一個(gè)命題不能同時(shí)即為真又為假，但可以在一定條件一個(gè)命題不能同時(shí)即為真又為假，但可以在一定條件下為真，在另一種條件下為假。例如：下為真，在另一種條件下為假。例如：p“1+1=10”1+1=10”在二進(jìn)制情況下為真，十進(jìn)制情況下為假。在二進(jìn)制情況下為真，十進(jìn)制情況下為假。謂詞邏輯法v命題命題無(wú)真假意義的語(yǔ)句，如感嘆句、疑問(wèn)句等，不是命題。無(wú)真假意義的語(yǔ)句，如感

40、嘆句、疑問(wèn)句等，不是命題。通常用大寫(xiě)英文字母表示一個(gè)命題，例如：通常用大寫(xiě)英文字母表示一個(gè)命題，例如： p P P：西安是座古老的城市：西安是座古老的城市v命題邏輯的局限性？命題邏輯的局限性？客觀事物的結(jié)構(gòu)及邏輯特征？客觀事物的結(jié)構(gòu)及邏輯特征？不同事物間的共同特征？不同事物間的共同特征？謂詞邏輯法v命題邏輯的局限性？命題邏輯的局限性？命題這種表示方法無(wú)法反映它所描述的客觀事物的結(jié)命題這種表示方法無(wú)法反映它所描述的客觀事物的結(jié)構(gòu)及邏輯特征，也不能表述不同事物間的共同特征。構(gòu)及邏輯特征，也不能表述不同事物間的共同特征。例如：例如：用字母用字母P P表示表示“小張是老張的兒子小張是老張的兒子”這一命

41、題，這一命題，則無(wú)法表述出老張與小張是父子關(guān)系。則無(wú)法表述出老張與小張是父子關(guān)系。例如：例如：“張三是學(xué)生張三是學(xué)生”，“李四是學(xué)生李四是學(xué)生”這兩個(gè)命題，這兩個(gè)命題，用命題邏輯表示時(shí)，無(wú)法把兩者的共同特征用命題邏輯表示時(shí)，無(wú)法把兩者的共同特征“都是學(xué)都是學(xué)生生”形式的表示出來(lái)。形式的表示出來(lái)?？煞裼每煞裼?Student（“張三張三”），）， Student（“李四李四”）表示上述命題？表示上述命題？謂詞邏輯謂詞邏輯謂詞邏輯法v謂詞謂詞在謂詞邏輯中，命題是用形如在謂詞邏輯中，命題是用形如P(x1,x2,xn)的謂詞來(lái)表的謂詞來(lái)表述的。一個(gè)謂詞可分為述的。一個(gè)謂詞可分為謂詞名謂詞名與與個(gè)體個(gè)體

42、兩個(gè)部分。兩個(gè)部分。個(gè)體：個(gè)體： 是命題的主語(yǔ)，表示獨(dú)立存在的事物或某個(gè)抽是命題的主語(yǔ)，表示獨(dú)立存在的事物或某個(gè)抽象的概念象的概念p “x1,x2,xn”是個(gè)體，一般用小寫(xiě)字母表示是個(gè)體，一般用小寫(xiě)字母表示p 個(gè)體可以是個(gè)體常量、變?cè)蚝瘮?shù)個(gè)體可以是個(gè)體常量、變?cè)蚝瘮?shù)謂詞名：謂詞名：表示個(gè)體的性質(zhì)、狀態(tài)或個(gè)體之間的關(guān)系表示個(gè)體的性質(zhì)、狀態(tài)或個(gè)體之間的關(guān)系p “P”是謂詞名，一般用大寫(xiě)字母表示是謂詞名，一般用大寫(xiě)字母表示p 稱稱P 是一個(gè)是一個(gè)n元謂詞。元謂詞。謂詞邏輯法v謂詞謂詞命題命題“張三是學(xué)生張三是學(xué)生” ，用謂詞可表示為：，用謂詞可表示為：Student（“張張三三”）。其中，）。其

43、中， Student是謂詞名，是謂詞名，“張三張三”是個(gè)體，是個(gè)體， Student刻畫(huà)了刻畫(huà)了“張三張三”是學(xué)生這一特征。是學(xué)生這一特征。在謂詞中，個(gè)體可以是常量、變?cè)蚝瘮?shù)。在謂詞中，個(gè)體可以是常量、變?cè)蚝瘮?shù)。例如例如：命題：命題“x10”可表示為可表示為more（x,10），其中），其中x是變?cè)?。是變?cè)?。又如命題又如命題“小張的父親是老師小張的父親是老師”，可表示為，可表示為T(mén)eacher（father（Zhang），其中），其中 father（Zhang）是函數(shù)。）是函數(shù)。當(dāng)謂詞的變?cè)加锰囟ǖ膫€(gè)體取代時(shí)，謂詞就具有一個(gè)確當(dāng)謂詞的變?cè)加锰囟ǖ膫€(gè)體取代時(shí)，謂詞就具有一個(gè)確定的真值定的

44、真值“T”或或 “F” 。謂詞邏輯法v謂詞謂詞在在n元謂詞元謂詞 P(x1,x2,xn)中，若每個(gè)個(gè)體均為常量、變中，若每個(gè)個(gè)體均為常量、變?cè)蚝瘮?shù)，則稱它為元或函數(shù)，則稱它為一階謂詞一階謂詞。如果某個(gè)個(gè)體本身又是一個(gè)一階謂詞，則稱它為如果某個(gè)個(gè)體本身又是一個(gè)一階謂詞，則稱它為二階二階謂詞謂詞，如此類推。，如此類推。個(gè)體變?cè)娜≈捣秶Q為個(gè)體變?cè)娜≈捣秶Q為個(gè)體域個(gè)體域。個(gè)體域可以是有限。個(gè)體域可以是有限的，也可以是無(wú)限的。例如用的，也可以是無(wú)限的。例如用I(x)表示表示“x是整數(shù)是整數(shù)”，則個(gè)體域?yàn)樗姓麛?shù)，是無(wú)限的。則個(gè)體域?yàn)樗姓麛?shù)，是無(wú)限的。謂詞與函數(shù)不同謂詞與函數(shù)不同，謂詞的真值是

45、，謂詞的真值是 “T”或或 “F”，而函數(shù)，而函數(shù)的值是個(gè)體域中的一個(gè)個(gè)體，無(wú)真值可言。的值是個(gè)體域中的一個(gè)個(gè)體，無(wú)真值可言。謂詞邏輯法v謂詞演算謂詞演算謂詞邏輯語(yǔ)言的語(yǔ)法和語(yǔ)義謂詞邏輯語(yǔ)言的語(yǔ)法和語(yǔ)義p謂詞邏輯語(yǔ)言的基本符號(hào)：謂詞邏輯語(yǔ)言的基本符號(hào)：- 謂詞符號(hào)謂詞符號(hào)- 變量符號(hào)變量符號(hào)- 函數(shù)符號(hào)函數(shù)符號(hào)- 常量符號(hào)常量符號(hào)- 括號(hào)和逗號(hào)括號(hào)和逗號(hào)謂詞邏輯法v謂詞演算謂詞演算謂詞邏輯語(yǔ)言的語(yǔ)法和語(yǔ)義謂詞邏輯語(yǔ)言的語(yǔ)法和語(yǔ)義p原子公式：原子公式：原子公式由若干謂詞符號(hào)和項(xiàng)組成原子公式由若干謂詞符號(hào)和項(xiàng)組成. .謂詞符號(hào)謂詞符號(hào)規(guī)定定義域內(nèi)的一個(gè)相應(yīng)關(guān)系規(guī)定定義域內(nèi)的一個(gè)相應(yīng)關(guān)系. .常量符

46、號(hào)常量符號(hào)是最簡(jiǎn)單的項(xiàng)，表示論域內(nèi)的物體或?qū)嶓w是最簡(jiǎn)單的項(xiàng)，表示論域內(nèi)的物體或?qū)嶓w. .變量符號(hào)變量符號(hào)也是項(xiàng)，不明確涉及是哪一個(gè)實(shí)體也是項(xiàng)，不明確涉及是哪一個(gè)實(shí)體. .函數(shù)符號(hào)函數(shù)符號(hào)表示論域內(nèi)的函數(shù)，是從論域內(nèi)的一個(gè)實(shí)體表示論域內(nèi)的函數(shù)，是從論域內(nèi)的一個(gè)實(shí)體到另外一個(gè)實(shí)體的映射到另外一個(gè)實(shí)體的映射. .例如：原子公式例如：原子公式 Married father(LI) , Married father(LI) , mother(LI) mother(LI) 表示表示“李（李（LILI）的父親和他的母親結(jié)婚）的父親和他的母親結(jié)婚”謂詞邏輯法連詞和量詞連詞和量詞p連詞連詞合?。汉先。悍?hào)符號(hào)“

47、 ” ”， 表示所連結(jié)的兩個(gè)命題之間表示所連結(jié)的兩個(gè)命題之間具有具有“與與”的關(guān)系。的關(guān)系。析?。何鋈。?符號(hào)符號(hào)“ ”“ ”，表示所連結(jié)的兩個(gè)命題之間，表示所連結(jié)的兩個(gè)命題之間具有具有“或或”的關(guān)系。的關(guān)系。蘊(yùn)涵：蘊(yùn)涵：符號(hào)符號(hào)“ ”“ ”，表示，表示“若若則則”的語(yǔ)義。的語(yǔ)義。PQPQ讀作讀作“如果如果P P，則，則Q”Q”其中其中P P稱為條件的前件，稱為條件的前件，Q Q稱稱為條件的后件。為條件的后件。非：非：符號(hào)符號(hào)“ ” ”，表示對(duì)其后面的命題的否定。，表示對(duì)其后面的命題的否定。雙條件：雙條件：符號(hào)符號(hào)“ ” ”，表示，表示“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”的語(yǔ)義。的語(yǔ)義。 P PQ Q讀作讀作

48、“P P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”Q”。謂詞邏輯法連詞和量詞連詞和量詞p量詞量詞全稱量詞：全稱量詞：符號(hào)符號(hào)“ ”，意思是意思是“所有的所有的”、“任一個(gè)任一個(gè)”。 x x讀作讀作“對(duì)一切對(duì)一切x”,x”,或或“對(duì)每一對(duì)每一x”x”，或，或“對(duì)任一對(duì)任一x”x”。命題命題( ( x)P(x)x)P(x)為真，當(dāng)且僅當(dāng)對(duì)論域中的所為真，當(dāng)且僅當(dāng)對(duì)論域中的所有有x x，都有，都有P(x)P(x)為真。為真。命題命題( ( x)P(x)x)P(x)為假，當(dāng)且僅當(dāng)至少存在論域?yàn)榧?，?dāng)且僅當(dāng)至少存在論域中的一個(gè)中的一個(gè)x x，使得，使得P(x)P(x)為假。為假。謂詞邏輯法連詞和量詞連詞和量詞p量詞量詞存在量

49、詞：存在量詞：符號(hào)符號(hào)“ ”，意思是意思是“至少有至少有”、“存在存在” ” 。 x x讀作讀作“存在一個(gè)存在一個(gè)x”,x”,或或“對(duì)某些對(duì)某些x”x”，或，或“至少有一至少有一x”x”。命題命題( ( x)P(x)x)P(x)為真，當(dāng)且僅當(dāng)至少存在論域?yàn)檎?，?dāng)且僅當(dāng)至少存在論域中的一個(gè)中的一個(gè)x x，使得，使得P(x)P(x)為真。為真。命題命題( ( x)P(x) x)P(x)為假，當(dāng)且僅當(dāng)對(duì)論域中的所為假，當(dāng)且僅當(dāng)對(duì)論域中的所有有x x，都有，都有P(x)P(x)為假為假 。謂詞邏輯法v謂詞公式謂詞公式原子謂詞公式：原子謂詞公式：p是由謂詞符號(hào)和若干項(xiàng)組成的謂詞演算。是由謂詞符號(hào)和若干項(xiàng)

50、組成的謂詞演算。p若若t1,t2,tn是項(xiàng)，是項(xiàng)，P是謂詞，則稱是謂詞，則稱P(t1,t2,tn)為原子謂詞公式。為原子謂詞公式。分子謂詞公式：分子謂詞公式：p可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。子謂詞公式。謂詞邏輯法v謂詞公式謂詞公式合式公式（合式公式（WFF，Well-formed Formulas）：）：通常把通常把合合式公式式公式叫做叫做謂詞公式謂詞公式，遞歸定義如下：，遞歸定義如下：p(1) 原子謂詞公式是合式公式原子謂詞公式是合式公式p(2) 若若A為合式公式，則為合式公式，則 A也是一個(gè)合式公式也

51、是一個(gè)合式公式p(3) 若若A,B是合式公式，則是合式公式，則AB，AB，AB，AB也都是合式公式也都是合式公式p(4) 若若A是合式公式，是合式公式，x為為A中的自由變?cè)?，則中的自由變?cè)?，則 ( x)A和和( x)A都是合式公式都是合式公式p(5) 只有按上述規(guī)則只有按上述規(guī)則(1)至至(4)求得的那些公式，才是合式求得的那些公式，才是合式公式。公式。謂詞邏輯法v謂詞公式謂詞公式用謂詞公式表示知識(shí)時(shí)，需要首先用謂詞公式表示知識(shí)時(shí)，需要首先定義謂詞定義謂詞，然后再，然后再用用連接詞連接詞把有關(guān)的謂詞連接起來(lái)，形成一個(gè)謂詞公式把有關(guān)的謂詞連接起來(lái)，形成一個(gè)謂詞公式表達(dá)一個(gè)完整的意義。表達(dá)一個(gè)完整

52、的意義。 例例1：設(shè)有下列知識(shí)設(shè)有下列知識(shí) 劉歡比他父親出名。劉歡比他父親出名。 高揚(yáng)是計(jì)算機(jī)系的一名學(xué)生，但他不喜歡編程高揚(yáng)是計(jì)算機(jī)系的一名學(xué)生，但他不喜歡編程 。 任何整數(shù)或者為正或者為負(fù)。任何整數(shù)或者為正或者為負(fù)。為了用謂詞公式表示上述知識(shí)，首先需要定義謂詞：為了用謂詞公式表示上述知識(shí)，首先需要定義謂詞： FAMOUS (x, y) : x比比y出名出名 COMPUTER ( x ) : x 是計(jì)算機(jī)系的是計(jì)算機(jī)系的 LIKE (x, y ) : x 喜歡喜歡 y謂詞邏輯法 I(x)表示表示“x是整數(shù)是整數(shù)” P(x)表示表示“x是正數(shù)是正數(shù)” N(x)表示表示“x是負(fù)數(shù)是負(fù)數(shù)” 此時(shí)可

53、用謂詞公式把上述知識(shí)表示為此時(shí)可用謂詞公式把上述知識(shí)表示為: 劉歡比他父親出名劉歡比他父親出名: FAMOUS ( liuhuan, father ( liuhuan ) 高揚(yáng)是計(jì)算機(jī)系的一名學(xué)生，但他不喜歡編程高揚(yáng)是計(jì)算機(jī)系的一名學(xué)生，但他不喜歡編程 : COMPUTER(gaoyang)LIKE(gaoyang, programing) 任何整數(shù)或者為正或者為負(fù)任何整數(shù)或者為正或者為負(fù): ( x)(I(x) (P(x) N(x)謂詞邏輯法v謂詞公式謂詞公式例例2：用謂詞邏輯描述右圖中的房子的概念用謂詞邏輯描述右圖中的房子的概念p個(gè)體個(gè)體 ：A , Bp謂詞謂詞 ：SUPPORT( x,y

54、)：表示：表示 x 被被 y支撐著支撐著 WEDGE ( x )：表示：表示 x 是楔形塊是楔形塊 BRICK( y )：表示：表示 y 是長(zhǎng)方塊是長(zhǎng)方塊 p其中其中 x , y是個(gè)體變?cè)?，它們的個(gè)體域是個(gè)體變?cè)?，它們的個(gè)體域A,Bp房子的概念可以表示成一組合式謂詞公式的合取式：房子的概念可以表示成一組合式謂詞公式的合取式： SUPPORT(A,B) WEDGE( A ) BRICK( B )謂詞邏輯法v合式公式的性質(zhì)合式公式的性質(zhì)若若P、Q是兩個(gè)合式公式，則由這兩個(gè)合式公式所組成是兩個(gè)合式公式，則由這兩個(gè)合式公式所組成的復(fù)合表達(dá)式可由下列真值表給出。的復(fù)合表達(dá)式可由下列真值表給出。PQPPQ

55、PQPQPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT謂詞邏輯法v合式公式的性質(zhì)合式公式的性質(zhì)如果兩個(gè)合式公式，無(wú)論如何解釋，其真值表都是相如果兩個(gè)合式公式，無(wú)論如何解釋，其真值表都是相同的，那么我們就稱此兩合式公式是同的，那么我們就稱此兩合式公式是等價(jià)的等價(jià)的。應(yīng)用上述真值表可以確立下列等價(jià)關(guān)系：應(yīng)用上述真值表可以確立下列等價(jià)關(guān)系：p（1）否定之否定：）否定之否定： ( P ) = Pp（2）( P Q ) = ( P Q ) 或者或者 ( P Q ) = ( P Q ）p（3）狄）狄 摩根定律：摩根定律： ( P Q ) = P Q ( P Q ) = P Q謂詞邏輯法p（4

56、）分配律：）分配律： P ( Q R ) = ( P Q ) ( P R ) P ( Q R ) = ( P Q ) ( P R )p（5）交換律：）交換律： P Q = Q P P Q = Q Pp（6）結(jié)合律：）結(jié)合律： P ( Q R ) = ( P Q ) R P ( Q R ) = ( P Q ) Rp（7）逆否率：）逆否率： ( P Q ) = ( Q P ) 謂詞邏輯法p（8）泛界律：）泛界律： P F = P , P T = P P F = F , P T = T p（9）互余律：）互余律： P P = T, P P = F此外還可以確立下列等價(jià)關(guān)系：此外還可以確立下列等價(jià)關(guān)系

57、：p ( x) P(x) = ( x) P(x) p ( x) P(x) = ( x) P(x) p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x)p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x) p ( x) P(x) = ( y) P(y) p ( x) P(x) = ( y) P(y) 謂詞邏輯法v置換與合一置換與合一置換置換p 推理規(guī)則：推理規(guī)則：用合式公式的集合產(chǎn)生新的合式公式用合式公式的集合產(chǎn)生新的合式公式 假元推理：假元推理： 全稱化推理：全稱化推理： 綜合推理：綜合推理：由合式公式由合式公式W1和和W1 W2產(chǎn)生合式公式產(chǎn)生

58、合式公式W2 W(A)( x) W(x) 任意常量任意常量A W2(A) W1(A)( x) W1(x) W2(x)尋找尋找A對(duì)對(duì)x的的置置換換，使，使W1(A)與與W1(x)一致一致謂詞邏輯法v置換與合一置換與合一置換（置換（SubstitutionSubstitution）p置換的定義：置換的定義：置換是用置換是用變?cè)?、常量、函?shù)變?cè)?、常量、函?shù)來(lái)替換來(lái)替換變變?cè)?，使該變?cè)辉诠街谐霈F(xiàn)使該變?cè)辉诠街谐霈F(xiàn)。p置換是形如置換是形如 t1/x1, t2/x2, ， tn/xn的有限集合。的有限集合。 t1，t2， ， tn是項(xiàng)是項(xiàng) x1，x2， ， xn是互不相同的變?cè)腔ゲ幌嗤淖冊(cè)?

59、ti/xi表示用表示用ti項(xiàng)替換變?cè)?xiàng)替換變?cè)獂i，不允許，不允許ti和和xi相同，也相同，也不允許變?cè)辉试S變?cè)獂i循環(huán)地出現(xiàn)在另一個(gè)循環(huán)地出現(xiàn)在另一個(gè)tj中中謂詞邏輯法v置換與合一置換與合一置換（置換（SubstitutionSubstitution）p例例2.2（P37），表達(dá)式），表達(dá)式 Px, f(y), B的的4個(gè)置換為個(gè)置換為 s1= z/x, w/y； s2= A/y；s3= q(z)/x , A/y； s4= c/x , A/y 用用Es表示一個(gè)表達(dá)式表示一個(gè)表達(dá)式E用置換用置換s所得到的表達(dá)式的置所得到的表達(dá)式的置換。于是，換。于是，Px, f(y), B的的4個(gè)置換如下：

60、個(gè)置換如下： Px, f(y), B s1 = Pz, f(w), B Px, f(y), B s2 = Px, f(A), B Px, f(y), B s3 = Pq(z), f(A), B Px, f(y), B s4 = Pc, f(A), B 謂詞邏輯法v置換與合一置換與合一置換（置換（SubstitutionSubstitution）p置換是可結(jié)合的置換是可結(jié)合的用用s1s2表示兩個(gè)置換表示兩個(gè)置換s1和和s2的的合成合成，L表示一個(gè)表達(dá)表示一個(gè)表達(dá)式，則有式，則有 （Ls1）s2 = L（s1s2 ） 即用即用s1和和s2相繼作用于表達(dá)式相繼作用于表達(dá)式L是與用是與用s1s2作用于