1、Artificial Intelligence (AI)人工智能人工智能主講：何春梅Email：xiaoxiao_第二章：知識表示方法第二章：知識表示方法預備知識預備知識v人類的智能活動過程主要是一個獲得并運用知識人類的智能活動過程主要是一個獲得并運用知識的過程的過程v按照符號主義的觀點，按照符號主義的觀點，知識是一切智能行為的基知識是一切智能行為的基礎礎，要使計算機具有智能，首先必須使它擁有知，要使計算機具有智能，首先必須使它擁有知識識知識表示方法知識的概念知識的概念知識是人們在改造客觀世界的知識是人們在改造客觀世界的實踐中積累起來的實踐中積累起來的認識認識和和經驗經驗認識：認識：包括對事物

2、現象、本質、屬性、狀態、聯系等包括對事物現象、本質、屬性、狀態、聯系等的認識的認識經驗：經驗：包括包括解決問題的微觀方法和宏觀方法解決問題的微觀方法和宏觀方法p微觀方法：微觀方法：如步驟、操作、規則、過程、技巧等如步驟、操作、規則、過程、技巧等p宏觀方法：宏觀方法：如戰略、戰術、計謀、策略等如戰略、戰術、計謀、策略等eg：“if 大雁向南飛，大雁向南飛，then 冬天就要來臨了。冬天就要來臨了。”這樣一條知識就是這樣一條知識就是人們經過長期的觀察，將人們經過長期的觀察，將“大雁向南飛大雁向南飛”與與“冬天來臨冬天來臨”這兩條信息這兩條信息關聯在一起。關聯在一起。“雪是白色的雪是白色的”反映雪與

3、顏色的一種關系。反映雪與顏色的一種關系。知識的概念知識的概念 數據：數據：是信息的載體，本身無確切含義。如：是信息的載體，本身無確切含義。如：水的溫度是水的溫度是100，木頭的長度是，木頭的長度是2米，大樓的高度是米，大樓的高度是100層層 信息：信息：是數據的關聯，賦予數據特定的含義，僅可理解為描是數據的關聯，賦予數據特定的含義，僅可理解為描述性知識。數據是沒有聯系的，孤立的，述性知識。數據是沒有聯系的，孤立的，只有當數據用來描只有當數據用來描述一個客觀事物和客觀事物的關系，形成有邏輯的數據流，述一個客觀事物和客觀事物的關系，形成有邏輯的數據流，他們才能被稱為信息他們才能被稱為信息。 知識：

4、知識：是對信息的關聯，或對已有知識的再認識。是對信息的關聯，或對已有知識的再認識。 如：西安如：西安7月月1日氣溫為日氣溫為30度，度，12月月1日氣溫為日氣溫為3度。度。 當對這類信息進行歸納和對比就會發現西安每年當對這類信息進行歸納和對比就會發現西安每年7月氣溫比月氣溫比較高，較高，12月氣溫比較低，形成了新知識。月氣溫比較低，形成了新知識。知識的劃分知識的劃分按知識的性質：按知識的性質：概念、命題、公理、定理、規則和方法概念、命題、公理、定理、規則和方法按知識的作用域：按知識的作用域：常識性知識，領域性知識常識性知識，領域性知識按知識的等級：按知識的等級：p零級知識：零級知識：事實性知識

5、。用于描述事物的概念、定義、屬性等；事實性知識。用于描述事物的概念、定義、屬性等； 或用于描述問題的狀態、環境、條件等。或用于描述問題的狀態、環境、條件等。p一級知識：一級知識：過程性知識。用于問題求解過程的操作、演算和行過程性知識。用于問題求解過程的操作、演算和行為的知識。為的知識。表示方式：產生式、謂詞、語義網絡等。表示方式：產生式、謂詞、語義網絡等。p二級知識：二級知識：控制性知識，元知識或超知識。是關于如何使用過控制性知識，元知識或超知識。是關于如何使用過程性知識的知識。程性知識的知識。例如：推理策略、搜索策略、不確定性的傳例如：推理策略、搜索策略、不確定性的傳播策略。播策略。 知識的

6、劃分知識的劃分按知識的層次：按知識的層次：p表層知識：表層知識：描述客觀事物的現象的知識。例如：感性、事實性描述客觀事物的現象的知識。例如：感性、事實性知識知識p深層知識：深層知識：描述客觀事物本質、內涵等的知識。例如：理論知描述客觀事物本質、內涵等的知識。例如：理論知識識按知識的確定性：按知識的確定性：p確定性知識：確定性知識：可以說明其真值為真或為假的知識可以說明其真值為真或為假的知識p不確定性知識：不確定性知識：包括不精確、模糊、不完備知識包括不精確、模糊、不完備知識l不精確：不精確：知識本身有真假，但由于認識水平限制卻不能肯定知知識本身有真假，但由于認識水平限制卻不能肯定知識的真假。識

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

8、是人類的經驗性知識和直觀感覺；如：人的為人處事的經驗與風格如：人的為人處事的經驗與風格p形象性知識：形象性知識：通過事物的形象建立起來的知識。通過事物的形象建立起來的知識。如如: :什么是人？什么是人？按知識的獲取方式：按知識的獲取方式：p顯性知識：顯性知識：指可通過文字、語言、圖形、聲音等形式編碼記錄指可通過文字、語言、圖形、聲音等形式編碼記錄和傳播的知識；和傳播的知識；如：教材、音視頻光盤。如：教材、音視頻光盤。p隱性知識：隱性知識：指人們長期實踐中積累獲得的知識，不易用顯性知指人們長期實踐中積累獲得的知識，不易用顯性知識表達的知識。識表達的知識。如：每個人都有不同的審美觀。如：每個人都有

9、不同的審美觀。人工智能系統中的知識人工智能系統中的知識v 一個智能程序高水平的運行需要有關的一個智能程序高水平的運行需要有關的事實知識、規則知事實知識、規則知識、控制知識和元知識。識、控制知識和元知識。v 事實知識：事實知識：是有關問題環境的一些事物的知識，常以是有關問題環境的一些事物的知識，常以“是是”的形式出現。的形式出現。 如事物的分類、屬性、事物間關系、科學事實、客觀事實等如事物的分類、屬性、事物間關系、科學事實、客觀事實等 事實是靜態的為人們共享的可公開獲得的公認的知識，事實是靜態的為人們共享的可公開獲得的公認的知識，在知在知識庫中屬低層的知識。識庫中屬低層的知識。 如：雪是白色的、

10、鳥有翅膀、張三李四是好朋友、這輛車是如：雪是白色的、鳥有翅膀、張三李四是好朋友、這輛車是張三的張三的v 規則知識：規則知識：是有關問題中與事物的行動、動作相聯系的因是有關問題中與事物的行動、動作相聯系的因果關系知識，是動態的，常以果關系知識，是動態的，常以“如果如果那么那么” 形式出現。形式出現。人工智能系統中的知識人工智能系統中的知識v 控制知識：控制知識：是有關問題的求解步驟、技巧的知識，告訴人是有關問題的求解步驟、技巧的知識，告訴人們怎么做一件事，也包括當有多個動作同時被激活時應選們怎么做一件事，也包括當有多個動作同時被激活時應選哪一個動作來執行的知識。哪一個動作來執行的知識。控制知識常

11、與程序結合在一起控制知識常與程序結合在一起出現，如一個問題求解的算法可以看做是一種知識表示。出現，如一個問題求解的算法可以看做是一種知識表示。v 元知識：元知識：是有關知識的知識，是是有關知識的知識，是知識庫中的高層知識知識庫中的高層知識。 包括怎樣使用規則、解釋規則、校驗規則、解釋程序結構等包括怎樣使用規則、解釋規則、校驗規則、解釋程序結構等知識。知識。 元知識與控制知識是有重迭的元知識與控制知識是有重迭的，對一個大的程序來說，以元，對一個大的程序來說，以元知識或說元規則形式體現控制知識更為方便，因為知識或說元規則形式體現控制知識更為方便，因為元知識存元知識存于知識庫中，而控制知識常與程序結

12、合在一起出現，從而不于知識庫中，而控制知識常與程序結合在一起出現，從而不容易修改容易修改。 知識表示知識表示v 知識表示：知識表示：是研究用機器表示知識的可行性、有效性的一是研究用機器表示知識的可行性、有效性的一般方法，是一種般方法，是一種數據結構數據結構與與控制結構控制結構的統一體，既考慮知的統一體，既考慮知識的識的存儲存儲又考慮知識的又考慮知識的使用使用。v 知識表示的要求：知識表示的要求：p 表示能力：表示能力：能否能否正確正確、有效有效地表示問題。包括：表范圍的廣泛性、地表示問題。包括：表范圍的廣泛性、領域知識表示的高效性、對非確定性知識表示的支持程度。領域知識表示的高效性、對非確定性

13、知識表示的支持程度。p 可利用性：可利用性：可利用這些知識可利用這些知識進行有效推理進行有效推理。包括：對推理的適應。包括：對推理的適應性，對高效算法的支持程度。性，對高效算法的支持程度。p 可實現性：可實現性：要便于計算機直接對其進行處理要便于計算機直接對其進行處理 p 可組織性：可組織性：可以按某種方式把知識組織成可以按某種方式把知識組織成某種知識結構某種知識結構p 可維護性：可維護性：便于對知識的增、刪、改等操作便于對知識的增、刪、改等操作p 自然性：自然性：符合人們的日常習慣符合人們的日常習慣p 可理解性：可理解性：知識應易讀、易懂、易獲取等知識應易讀、易懂、易獲取等 內容提要1.1.

14、狀態空間法狀態空間法2.2.問題歸約法問題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語義網絡法語義網絡法5.5.其他方法其他方法內容提要1.1.狀態空間法狀態空間法2.2.問題歸約法問題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語義網絡法語義網絡法5.5.其他方法其他方法狀態空間法v人工智能雖有多個研究領域，且每個研究領域又人工智能雖有多個研究領域，且每個研究領域又各有自己的規律和特點，但都可抽象為一個各有自己的規律和特點，但都可抽象為一個“問問題求解題求解”的過程。問題求解過程實際上是一個的過程。問題求解過程實際上是一個搜搜索索過程。過程。v 問題求解技術主要是兩個方面：問題求解技術主要是兩

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

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

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

18、局十五數碼難題十五數碼難題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初始狀態初始狀態目標狀態目標狀態如何把初試棋局如何把初試棋局變成目標棋局？變成目標棋局？首先把適用的算符首先把適用的算符用于初始狀態，以產用于初始狀態，以產生新的狀態生新的狀態再把另一些適用算符再把另一些適用算符用于這些新的狀態；用于這些新的狀態；這樣繼續下去，直至這樣繼續下去，直至產生目標狀態為止產生目標狀態為止狀態空間法v 問題的表示對求解工作有很大影響。人們問題的表示對求解工作有很大影響。人們希望有較小的狀希望有較小的狀態空間表示態空間表示。v 例如，對于十五數碼問題：例如，對于十五數碼問題：可以規定可以規定15460條規則條規則p “上移棋子上移棋

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

21、veling Salesman Problem(Traveling Salesman Problem，TSP)TSP)：算符的代價算符的代價狀態空間法v 狀態圖示法：狀態圖示法：狀態空間的圖示形式稱為狀態空間的圖示形式稱為狀態空間圖狀態空間圖。狀態。狀態圖中有幾個術語。圖中有幾個術語。 節點節點(Node)：圖形上的匯合點，用來表示圖形上的匯合點，用來表示狀態狀態、事件事件和和時間時間關系的匯合關系的匯合。 弧線弧線(Arc)：節點間的連接線，表示節點間的連接線，表示算符算符； 有向圖有向圖(Directed Graph)：一對節點用弧線連接起來，從一一對節點用弧線連接起來，從一個節點指向另一

22、個節點。個節點指向另一個節點。 后繼節點后繼節點(Descendant node)與父輩節點與父輩節點(Parent node)：如果如果某條弧線從節點某條弧線從節點ni指向節點指向節點nj，那么節點，那么節點nj就叫做節點就叫做節點ni的的后后繼節點或后裔繼節點或后裔，而節點，而節點ni叫做節點叫做節點nj的的父輩節點或祖先父輩節點或祖先。狀態空間法v 狀態圖示法：狀態圖示法：狀態空間的圖示形式稱為狀態空間的圖示形式稱為狀態空間圖狀態空間圖。狀態。狀態圖中有幾個術語。圖中有幾個術語。 路徑路徑(Path)：某個節點序列某個節點序列(ni1,ni2,nik)當當j=2,3,k時，如時，如果對于

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

24、給出。顯然，顯示說明對于大型的顯然，顯示說明對于大型的圖是不切實際的，而對于具有無限節點集合的圖則是不可能圖是不切實際的，而對于具有無限節點集合的圖則是不可能的。的。狀態空間法v 各種問題都可用狀態空間加以表示，并用各種問題都可用狀態空間加以表示，并用狀態空間搜索法狀態空間搜索法來求解。下面簡單介紹一種來求解。下面簡單介紹一種產生式系統（產生式系統（production system）描述的搜索算法。）描述的搜索算法。v 產生式系統（產生式系統（production systemproduction system）由三部分組成：）由三部分組成：一個總數據庫：一個總數據庫：0 0級知識。它含有與

25、具體任務有關的信級知識。它含有與具體任務有關的信息。息。一套規則：一套規則：1 1級知識。它對數據庫進行操作運算。級知識。它對數據庫進行操作運算。一個控制策略（程序）：一個控制策略（程序）：2 2級知識。它確定應該采用哪級知識。它確定應該采用哪一條適用規則，而且當數據庫的終止條件滿足時，就一條適用規則，而且當數據庫的終止條件滿足時，就停止計算。控制策略由控制系統選擇和確定。停止計算。控制策略由控制系統選擇和確定。 狀態空間法v 狀態空間法舉例：狀態空間法舉例：猴子和香蕉問題：猴子和香蕉問題：在一個房間內有一只猴子、一個箱在一個房間內有一只猴子、一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高

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

27、下：這個問題的操作（算符）如下：pgoto（U）表示猴子走到水平位置）表示猴子走到水平位置Uppushbox（V）猴子把箱子推到水平位置）猴子把箱子推到水平位置Vpclimbbox猴子爬上箱頂猴子爬上箱頂pgrasp猴子摘到香蕉猴子摘到香蕉猴子和香蕉問題v 解題過程解題過程該初始狀態變換為目標該初始狀態變換為目標狀態的操作序列為：狀態的操作序列為：pStep1: goto(b)pStep2: pushbox(c)pStep3: climbboxpStep4: grasp猴子和香蕉問題v 狀態空間圖狀態空間圖(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）目標狀態目標狀態goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）goto（U）U=VV=c，climbboxgrasp內容提要1.1.狀態空間法狀態空間法2.2.問題歸約法問題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語義網絡法語義網絡法5.5.其他方法其他方法問題歸約法v 問題歸約（問題歸約（Problem Reduction） 是另外一種是另外一種基于狀態空間基于狀態空間的問題描述與求解方法的問題描述與求解方法 已知問題的描述，通過一系列已知問題的描述，通過一系列變換變換把此問題變為一個把此問題變為一個子問題

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

30、問題的子問題，直到最后把初始問題歸約為一一個本原問題集合個本原問題集合。問題歸約法v 問題歸約法舉例：問題歸約法舉例：漢諾塔問題（漢諾塔問題（ Hanoi ） p 從從1移到移到3p 每次移動一個盤子每次移動一個盤子p 大盤在下小盤在上大盤在下小盤在上123CBA初始狀態（初始狀態（111）目標狀態（目標狀態（333）CBA漢諾塔問題v 原始問題可以歸約為下列原始問題可以歸約為下列3 3個子問題：個子問題：子問題子問題1 1：子問題子問題2 2：子問題子問題3 3：漢諾塔問題v 歸約過程（歸約過程（3 3個圓盤）個圓盤）漢諾塔問題v 漢諾塔問題歸約圖漢諾塔問題歸約圖本原問題本原問題本原問題本原

31、問題與或圖與或圖CBA問題歸約法v 與或圖表示：與或圖表示：用一個類似于圖的結構來表示把問題歸約為用一個類似于圖的結構來表示把問題歸約為后繼問題的替換集合。后繼問題的替換集合。與圖：與圖：把一個復雜問題把一個復雜問題分解為若干個較為簡單的分解為若干個較為簡單的子問題，形成子問題，形成“與與”樹。樹。或圖：或圖：把原問題變換為把原問題變換為若干個較為容易求解的新若干個較為容易求解的新問題，形成問題，形成“或或”樹。樹。問題歸約法v 與或圖表示：與或圖表示：BCDEFGAHMBCDEFGAN子問題替代集合結構圖子問題替代集合結構圖與或圖與或圖問題歸約法v 一些關于與或圖的術語一些關于與或圖的術語起

32、始節點起始節點對應于原對應于原始問題描始問題描述述終葉節點對應于本原問題終葉節點對應于本原問題問題歸約法v 與或圖的構成規則與或圖的構成規則 1 1）與或圖中的每個節點代表一）與或圖中的每個節點代表一個要解決的單一問題或問題集合。個要解決的單一問題或問題集合。圖中所含起始節點對應于原始問圖中所含起始節點對應于原始問題題A A。 2 2）對應于本原問題的節點稱為）對應于本原問題的節點稱為終葉節點，它沒有后繼節點。終葉節點，它沒有后繼節點。 3 3）對于把算符應用于問題）對于把算符應用于問題A A的每的每種可能情況，都把問題變換為一種可能情況，都把問題變換為一個子問題集合；有向弧線自個子問題集合；

33、有向弧線自A A指指向后繼節點表示所求得的子問題向后繼節點表示所求得的子問題集合。集合。HMBCDEFGAN37問題歸約法v 與或圖的構成規則與或圖的構成規則 4 4）一般對于代表兩個或兩個以上）一般對于代表兩個或兩個以上子問題集合的每個節點，有向弧子問題集合的每個節點，有向弧線從此節點指向次子問題集合中線從此節點指向次子問題集合中的各個節點。由于只有當集合中的各個節點。由于只有當集合中所有項都有解時，這個子問題的所有項都有解時，這個子問題的集合才能獲得解答，所以這些子集合才能獲得解答，所以這些子問題節點叫做與節點。問題節點叫做與節點。 5 5）特殊情況下，當只有一個算符）特殊情況下，當只有一

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

35、節點至少有一個是可解的時，此非終葉節點才是可解的。的。如果某個非終葉節點含有如果某個非終葉節點含有與后繼節點與后繼節點，那么只有當其后，那么只有當其后繼節點全部為可解時，此非終葉節點才是可解的。繼節點全部為可解時，此非終葉節點才是可解的。問題歸約法v不可解節點不可解節點沒有后裔的非終葉節點為不可解節點。沒有后裔的非終葉節點為不可解節點。 如果某個非終葉節點含有如果某個非終葉節點含有或后繼節點或后繼節點，那么只有當其，那么只有當其全全部后裔為不可解時部后裔為不可解時，此非終葉節點才是不可解的。，此非終葉節點才是不可解的。 如果某個非終葉節點含有如果某個非終葉節點含有與后繼節點與后繼節點，那么只要

36、當其，那么只要當其后后裔至少有一個為不可解時裔至少有一個為不可解時，此非終葉節點才是不可解的。，此非終葉節點才是不可解的。v解樹解樹由可解節點所構成，并且由這些可解節點可推出初始節由可解節點所構成，并且由這些可解節點可推出初始節點為可解節點的子樹稱為解樹。點為可解節點的子樹稱為解樹。解樹中一定包含初始節點，它對應于原始問題。解樹中一定包含初始節點，它對應于原始問題。問題歸約法ttttttttt有解節點有解節點無解節點無解節點終葉節點終葉節點與或圖例子與或圖例子原始問題原始問題有一有一個以上的解個以上的解原始問題原始問題有有解解內容提要1.1.狀態空間法狀態空間法2.2.問題歸約法問題歸約法3.

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

38、進行命題間關系關系的推理，無法解決與的推理，無法解決與命題結構命題結構和和成分成分有關的推理有關的推理問題，問題，不適合表示較復雜的問題不適合表示較復雜的問題。謂詞邏輯是在命題邏輯的基礎上發展而來的，命題邏謂詞邏輯是在命題邏輯的基礎上發展而來的，命題邏輯可看作是謂詞邏輯的一種特殊形式。輯可看作是謂詞邏輯的一種特殊形式。謂詞邏輯法v命題命題命題是具有真假意義的語句。命題是具有真假意義的語句。命題代表人們進行思維時的一種判斷，若命題的意義命題代表人們進行思維時的一種判斷，若命題的意義為真，稱它的真值為為真，稱它的真值為“真真”，記作，記作“T”；若命題的意；若命題的意義為假，稱它的真值為義為假，稱

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

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

41、題，這一命題，則無法表述出老張與小張是父子關系。則無法表述出老張與小張是父子關系。例如：例如：“張三是學生張三是學生”，“李四是學生李四是學生”這兩個命題，這兩個命題，用命題邏輯表示時，無法把兩者的共同特征用命題邏輯表示時，無法把兩者的共同特征“都是學都是學生生”形式的表示出來。形式的表示出來。可否用可否用 Student（“張三張三”），）， Student（“李四李四”）表示上述命題？表示上述命題？謂詞邏輯謂詞邏輯謂詞邏輯法v謂詞謂詞在謂詞邏輯中，命題是用形如在謂詞邏輯中，命題是用形如P(x1,x2,xn)的謂詞來表的謂詞來表述的。一個謂詞可分為述的。一個謂詞可分為謂詞名謂詞名與與個體個體

42、兩個部分。兩個部分。個體：個體： 是命題的主語，表示獨立存在的事物或某個抽是命題的主語，表示獨立存在的事物或某個抽象的概念象的概念p “x1,x2,xn”是個體，一般用小寫字母表示是個體，一般用小寫字母表示p 個體可以是個體常量、變元或函數個體可以是個體常量、變元或函數謂詞名：謂詞名：表示個體的性質、狀態或個體之間的關系表示個體的性質、狀態或個體之間的關系p “P”是謂詞名，一般用大寫字母表示是謂詞名，一般用大寫字母表示p 稱稱P 是一個是一個n元謂詞。元謂詞。謂詞邏輯法v謂詞謂詞命題命題“張三是學生張三是學生” ，用謂詞可表示為：，用謂詞可表示為：Student（“張張三三”）。其中，）。其

43、中， Student是謂詞名，是謂詞名，“張三張三”是個體，是個體， Student刻畫了刻畫了“張三張三”是學生這一特征。是學生這一特征。在謂詞中，個體可以是常量、變元或函數。在謂詞中，個體可以是常量、變元或函數。例如例如：命題：命題“x10”可表示為可表示為more（x,10），其中），其中x是變元。是變元。又如命題又如命題“小張的父親是老師小張的父親是老師”，可表示為，可表示為Teacher（father（Zhang），其中），其中 father（Zhang）是函數。）是函數。當謂詞的變元都用特定的個體取代時，謂詞就具有一個確當謂詞的變元都用特定的個體取代時，謂詞就具有一個確定的真值定的

44、真值“T”或或 “F” 。謂詞邏輯法v謂詞謂詞在在n元謂詞元謂詞 P(x1,x2,xn)中，若每個個體均為常量、變中，若每個個體均為常量、變元或函數，則稱它為元或函數，則稱它為一階謂詞一階謂詞。如果某個個體本身又是一個一階謂詞，則稱它為如果某個個體本身又是一個一階謂詞，則稱它為二階二階謂詞謂詞，如此類推。，如此類推。個體變元的取值范圍稱為個體變元的取值范圍稱為個體域個體域。個體域可以是有限。個體域可以是有限的，也可以是無限的。例如用的，也可以是無限的。例如用I(x)表示表示“x是整數是整數”，則個體域為所有整數，是無限的。則個體域為所有整數，是無限的。謂詞與函數不同謂詞與函數不同，謂詞的真值是

45、，謂詞的真值是 “T”或或 “F”，而函數，而函數的值是個體域中的一個個體，無真值可言。的值是個體域中的一個個體，無真值可言。謂詞邏輯法v謂詞演算謂詞演算謂詞邏輯語言的語法和語義謂詞邏輯語言的語法和語義p謂詞邏輯語言的基本符號：謂詞邏輯語言的基本符號：- 謂詞符號謂詞符號- 變量符號變量符號- 函數符號函數符號- 常量符號常量符號- 括號和逗號括號和逗號謂詞邏輯法v謂詞演算謂詞演算謂詞邏輯語言的語法和語義謂詞邏輯語言的語法和語義p原子公式：原子公式：原子公式由若干謂詞符號和項組成原子公式由若干謂詞符號和項組成. .謂詞符號謂詞符號規定定義域內的一個相應關系規定定義域內的一個相應關系. .常量符

46、號常量符號是最簡單的項，表示論域內的物體或實體是最簡單的項，表示論域內的物體或實體. .變量符號變量符號也是項，不明確涉及是哪一個實體也是項，不明確涉及是哪一個實體. .函數符號函數符號表示論域內的函數，是從論域內的一個實體表示論域內的函數，是從論域內的一個實體到另外一個實體的映射到另外一個實體的映射. .例如：原子公式例如：原子公式 Married father(LI) , Married father(LI) , mother(LI) mother(LI) 表示表示“李（李（LILI）的父親和他的母親結婚）的父親和他的母親結婚”謂詞邏輯法連詞和量詞連詞和量詞p連詞連詞合取：合取：符號符號“

47、 ” ”， 表示所連結的兩個命題之間表示所連結的兩個命題之間具有具有“與與”的關系。的關系。析取：析取： 符號符號“ ”“ ”，表示所連結的兩個命題之間，表示所連結的兩個命題之間具有具有“或或”的關系。的關系。蘊涵：蘊涵：符號符號“ ”“ ”，表示，表示“若若則則”的語義。的語義。PQPQ讀作讀作“如果如果P P，則，則Q”Q”其中其中P P稱為條件的前件，稱為條件的前件，Q Q稱稱為條件的后件。為條件的后件。非：非：符號符號“ ” ”，表示對其后面的命題的否定。，表示對其后面的命題的否定。雙條件：雙條件：符號符號“ ” ”，表示，表示“當且僅當當且僅當”的語義。的語義。 P PQ Q讀作讀作

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

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

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

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

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

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

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

55、PQPQPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT謂詞邏輯法v合式公式的性質合式公式的性質如果兩個合式公式，無論如何解釋，其真值表都是相如果兩個合式公式，無論如何解釋，其真值表都是相同的，那么我們就稱此兩合式公式是同的，那么我們就稱此兩合式公式是等價的等價的。應用上述真值表可以確立下列等價關系：應用上述真值表可以確立下列等價關系：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）結合律：）結合律： 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此外還可以確立下列等價關系：此外還可以確立下列等價關系

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 推理規則：推理規則：用合式公式的集合產生新的合式公式用合式公式的集合產生新的合式公式 假元推理：假元推理： 全稱化推理：全稱化推理： 綜合推理：綜合推理：由合式公式由合式公式W1和和W1 W2產生合式公式產生

58、合式公式W2 W(A)( x) W(x) 任意常量任意常量A W2(A) W1(A)( x) W1(x) W2(x)尋找尋找A對對x的的置置換換，使，使W1(A)與與W1(x)一致一致謂詞邏輯法v置換與合一置換與合一置換（置換（SubstitutionSubstitution）p置換的定義：置換的定義：置換是用置換是用變元、常量、函數變元、常量、函數來替換來替換變變元元，使該變元不在公式中出現使該變元不在公式中出現。p置換是形如置換是形如 t1/x1, t2/x2, ， tn/xn的有限集合。的有限集合。 t1，t2， ， tn是項是項 x1，x2， ， xn是互不相同的變元是互不相同的變元

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

60、個置換如下： 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置換是可結合的置換是可結合的用用s1s2表示兩個置換表示兩個置換s1和和s2的的合成合成，L表示一個表達表示一個表達式，則有式，則有 （Ls1）s2 = L（s1s2 ） 即用即用s1和和s2相繼作用于表達式相繼作用于表達式L是與用是與用s1s2作用于