1、12021-11-11第二章第二章 知識表示方法知識表示方法22021-11-112.1 知識與知識表示的概念知識與知識表示的概念第二章 知識表示方法 2.1 知識與知識表示的概念32021-11-11描述客觀世界描述客觀世界l人們對客觀世界的描述是通過數據和信息來實現的。l數據：指人們為了描述客觀世界中的具體事物而引人的一些數字、字符、文字等符號或符號的組合。“建國”、“50”是兩個數據l信息：不同數據組成的一種結構。建國50歲l信息是數據在特定場合下的含義，即數據的語義。相同的數據在不同場合會有不同的含義建國50歲；建國50周年l多數信息僅是對客觀事物的一般性描述，它還不是知識第二章 知識

2、表示方法 2.1 知識與知識表示的概念42021-11-11什么是知識什么是知識l知識是人們在改造客觀世界的實踐中積累起來的認識和經驗l知識是對信息進行智能性加工所形成的對客觀世界規律性的認識。l對信息的加工過程，是一種把信息關聯在一起的過程。因此，也可把有關信息關聯在一起所形成的信息結構稱為知識。例如，“如果如果他學過人工智能課程，則則他應該知道什么叫知識“。l知識還沒有一個統一的、嚴格的形式化定義。l一種定義：知識是經過處理、解釋、選擇和轉換的信息。第二章 知識表示方法 2.1 知識與知識表示的概念52021-11-11知識的屬性知識的屬性l真假性與相對性l不確定性l矛盾性和相客性。l可表

3、示性與可利用性。 第二章 知識表示方法 2.1 知識與知識表示的概念62021-11-11知識表示知識表示l 知識表示實際上就是對知識的一種描述，即用一些約定的符號把知識編碼成一組計算機可以接受的數據結構。l一般來說，同一知識可以有多種不同的表示形式，而不同表示形式所產生的效果又可能不一樣。l知識表示的要求表示能力可利用性可組織性與可維護性可實現性自然性與可理解性第二章 知識表示方法 2.1 知識與知識表示的概念72021-11-11幾種常用的知識表示方法幾種常用的知識表示方法n狀態空間法n問題歸約法n謂詞邏輯法n語義網絡表示法n框架表示法n過程表示n混合型知識表示方法n面向對象的表示方法n規

4、則表示法第二章 知識表示方法 2.1 知識與知識表示的概念82021-11-112.2 狀態空間法狀態空間法第二章 知識表示方法 2.2狀態空間法92021-11-11狀態空間法概述狀態空間法概述l為了問題求解，在狀態空間中從初始狀態開始，每次施加一個操作符，使狀態變成一個新狀態，直到達到目標狀態為止。得到的操操作符序列就是要求的解作符序列就是要求的解。這種基于解答空間的問題表示和求解方法就是狀態空間法。l采用狀態空間法必須確定三件事： 1. 狀態描述方式，特別是初始狀態描述； 2. 操作符集合及其對狀態描述的作用； 3. 目標狀態描述的特性。 第二章 知識表示方法 2.2狀態空間法10202

5、1-11-11狀態空間法例狀態空間法例8數碼難題數碼難題第二章 知識表示方法 2.2狀態空間法2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51 2 3 8 47 6 5目標初始112021-11-11狀態描述狀態描述 l狀態（狀態（state

6、）：是為描述某類不同事物間的差別而引入的一組最少變量q0，q1，. ，qn的有序集合,其矢量形式如下： Q=q0，q1，. ，qnT式中每個元素qi（i=0，1，. ，n）為集合的分量，稱為狀態變量。給定每個變量的一組值就得到一個具體的狀態，如 Qk=q0k，q1k，. ，qnkT我們用矢量來描述狀態，就如同用矢量來描述歐氏空間的點一樣。第二章 知識表示方法 2.2狀態空間法122021-11-11操作描述操作描述l所謂操作操作，或稱為算子是引起狀態中的某分量發生改變，從而使問題由一個具體狀態A變化為另一具體狀態B的作用。使問題一種狀態變化為另一狀態的手段稱為操作符或算符操作符或算符。操作符可

7、為走步、過程、規則、數學算子、運算符號或邏輯符號等。 第二章 知識表示方法 2.2狀態空間法132021-11-11狀態空間的表示狀態空間的表示l問題的狀態空間（問題的狀態空間（state spacestate space）：是一個表示該問題全部可能狀態及其關系的圖，它包括所有可能的問題初始狀態集合S、操作符集合F以及目標狀態集合G。l可把狀態空間記為三元狀態（S，F，G）。 l狀態空間的一個解是一個有限的操作算子序列，它使初始狀態轉化為目標狀態：S0-f1-S1-f2-.fk-G l狀態空間可用有向圖有向圖表示。 第二章 知識表示方法 2.2狀態空間法142021-11-11狀態空間表示舉例

8、：狀態空間表示舉例：猴子和香蕉猴子和香蕉l在一個房間內有一只猴子(可把猴子看成一個機器人)、一個箱子和一串香蕉。香蕉掛在天花板下方，但猴子高度不足以夠到它。那么猴子怎樣才能摘到香蕉呢？圖中示出了猴子、香蕉和箱子在房間內的相對位置。第二章 知識表示方法 2.1狀態空間法152021-11-11猴子摘香蕉問題圖示猴子摘香蕉問題圖示cba第二章 知識表示方法 2.1狀態空間法162021-11-11猴子摘香蕉問題猴子摘香蕉問題-綜合數據庫綜合數據庫（M, On, Box, H）其中：M：猴子的位置 On=0：猴子在地板上 On=1：猴子在箱子上 Box：箱子的位置 H=0：猴子沒有抓到香蕉 H=1：

9、猴子抓到了香蕉第二章 知識表示方法 2.1狀態空間法172021-11-11猴子摘香蕉問題猴子摘香蕉問題-初始與結束狀態初始與結束狀態1，初始狀態（c, 0, b, 0）2，結束狀態（c, 1, c, 1）第二章 知識表示方法 2.1狀態空間法182021-11-11猴子摘香蕉問題猴子摘香蕉問題-操作符集操作符集goto(U): (W, 0, Y, z,) (U, 0, Y, z)Pushbox(V): (W, 0, W, z) (V, 0, V, z)climbbox : (W, 0, W, z) (W, 1, W, z)grasp: (c, 1, c, 0) (c, 1, c, 1)其中U

10、, W, V, Y, z為變量第二章 知識表示方法 2.1狀態空間法192021-11-11猴子摘香蕉問題猴子摘香蕉問題-狀態空間圖狀態空間圖第二章 知識表示方法 2.1狀態空間法(a,0,b,0)(U,0,b,0)(b,1,b,0)(V,0,V,0)(U,0,V,0)(c,1,c,1)(c,1,c,0)goto(U)U=b,pushbox(V) U=b, climbbox V=c, climbboxgrasp goto(U)goto(U)202021-11-112.2 問題歸約法問題歸約法第二章 知識表示方法 2.2問題歸約法212021-11-11問題歸約法思想問題歸約法思想l問題歸約法問

11、題歸約法是不同于狀態空間的人工智能中另一種問題描述和求解方法。l它將要求解的問題分解成相對簡單的子問題；再將子問題分解成更加簡單的子問題，直至分解成一個本原問題集。（其中的每一個問題是不用證明的，自然成立的，如公理、已知的實事等） 第二章 知識表示方法 2.2問題歸約法222021-11-11梵塔難題梵塔難題 有3個柱子（1，2，3）和3個圓盤尺寸從小到大為A，B，C。最初，全部圓盤都堆在柱子1上，如圖1；要求把所有圓盤都挪到柱子3上如圖2。每次只允許移動一個，而且只能搬動柱子頂部的圓盤，還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。第二章 知識表示方法 2.2問題歸約法ABC123ABC12

12、3圖1圖2232021-11-11對梵塔難題進行問題歸約對梵塔難題進行問題歸約我們把原始難題規約為以下三個子難題： 移動圓盤A和B至柱子2的雙圓盤難題 移動圓盤C至柱子3的單圓盤難題 移動圓盤A和B至柱子3雙圓盤難題 第二章 知識表示方法 2.2問題歸約法242021-11-11梵塔難題的分解圖梵塔難題的分解圖第二章 知識表示方法 2.2問題歸約法AB123AB123C123C123AB123AB123252021-11-11問題歸約的表示問題歸約的表示l問題歸約表示也是一個三元組(S0,F,G):S0-一個初始問題描述,即要解決的問題(初始問題)；F-一套把問題變換為子問題的操作符（操作算子

13、集）；G-一套本原問題描述，（可以容易得到解答的問題）l問題歸約過程可以采用與或圖來表示第二章 知識表示方法 2.2問題歸約法262021-11-11問題歸約的與或圖表示問題歸約的與或圖表示基本概念基本概念l與或圖是一個超圖，節點間附有連接符。lK-連接符：.K個 由K-連接符連接的K個節點為 與節點K為1時為或節點 起始節點對應于原始問題的描述起始節點對應于原始問題的描述 子節點對應于子問題的描述子節點對應于子問題的描述第二章 知識表示方法 2.2問題歸約法272021-11-11梵塔難題的歸約圖梵塔難題的歸約圖第二章 知識表示方法 2.2問題歸約法(111)(333)(111)(122)(

14、322)(333)(122)(322)(113)(123)(123)(122)(111)(113)(321)(331)(331)(333)(322)(321)C在柱號A在柱號B在柱號282021-11-11能解節點能解節點l對應于本原問題的節點為終節點l終節點是能解節點l若非終節點有“或”子節點時，當且僅當其子節點至少有一能解時，該非終節點才能解。l若非終節點有“與”子節點時，當且僅當其子節點均能解時，該非終節點才能解。第二章 知識表示方法 2.2問題歸約法292021-11-11不能解節點不能解節點l沒有后裔的非終節點是不能解節點。l若非終節點有“或”子節點，當且僅當所有子節點均不能解時，該

15、非終節點才是不能解節點。l若非終節點有“與”子節點時，當至少有一個子節點不能解時，該非終節點才是不能解節點。第二章 知識表示方法 2.2 問題歸約法302021-11-11一種問題歸約技術l要把三元狀態（S,F,G）規定的狀態空間搜索問題歸約為一些比較簡單的狀態空間搜索問題。l希望有一個狀態序列g1,g2,gn（稱為“路標”）,使得對（S,F,g1）、（g1,F,g2）、 （gn,F,G）這樣一些問題的求解，等價于求解原問題l如何找“路標”，尋找關鍵算符l將必須采用的、起決定性作用的算符稱為關鍵算符l設f是關鍵算符，Gf是f適用的所有狀態的集合，gGf,則可以將問題歸約為（S,F,Gf）、 （

16、g,f,f(g)）和（f(g),F,G）。而（g,f,f(g)）是本原問題第二章 知識表示方法 2.2問題歸約法312021-11-11關鍵算符的辨別關鍵算符的辨別l許多問題往往無法辨別關鍵算符和知道它是決定性的步驟，只能推測某個算符子集合，其中某個算符是決定性的。l推測候選關鍵算符集合的方法之一是以“差別差別”為基礎l某個問題（S,F,G）的“差別差別”是指造成S的元不屬于G的那部分分量。l將能消去“差別”的算符或算符集合與相應的“差別差別”關聯起來，這些算符就是候選關鍵算符。第二章 知識表示方法 2.2問題歸約法322021-11-11歸約技術舉例歸約技術舉例-猴子和香蕉問題猴子和香蕉問題

17、l前面已經討論過的猴子和香蕉問題l其算符和適用條件f1:(W,0,Y,z)-goto(U)-(U,0,Y,z)f2:(W,0,W,z)-pushbox(V)-(V,0,V,z)f3:(W,0,W,z)-climbbox-(W,1,W,z)f4:(c,1,c,0)-grasp-(c,1,c,1)l令F=f1, f2 , f3 , f4、G=(c,1,c,1) 、S= (a,0,b,0) l那么我們的初始問題就變成為：(S,F,G)l應用關鍵算符和差別表示法的歸約過程如下第二章 知識表示方法 2.2問題歸約法332021-11-11猴子和香蕉問題的猴子和香蕉問題的歸約過程歸約過程(一一)l找差別：

18、 G=(c,1,c,1) 、S= (a,0,b,0) S與G的差別在最后一個元素不是1l關聯算符： f4 = grasp消去該差別 因此，與f4關聯l用f4歸約，得一對子問題： (S,F,G f4) 和(S1, f4,G) S1G f4其中,(S1, f4,G)已是個本原問題第二章 知識表示方法 2.2問題歸約法342021-11-11猴子和香蕉問題的猴子和香蕉問題的歸約過程（二）歸約過程（二）l重復過程：為求解(S,F,G f4)，找差別： S =(a,0,b,0)與G f4 = (c,1,c,0) 箱子不在c處、猴子不在c處、猴子不在箱子上l辨別出關聯算符： f2 :pushbox(c)

19、f1 : goto(c) f3:climbboxl選用f2關鍵算符歸約，得一對子問題: 1-1： (S,F,G f2) 和 1-2：(f2(S11),F,G f4) S11G f2第二章 知識表示方法 2.2問題歸約法352021-11-11猴子和香蕉問題的猴子和香蕉問題的歸約過程（三）歸約過程（三）l重復過程：為求解(S,F,G f2)，找差別： S =(a,0,b,0)與G f2 = (b,0,b,0) 猴子不在b處l辨別出關聯算符： f1 : goto(b) l用f1關鍵算符歸約，發現是個本原問題: (S, f1,G f2) l經過這樣反復遞歸重復，最終解答了初始問題第二章 知識表示方法

20、 2.2問題歸約法362021-11-11猴子和香蕉問題的與或圖猴子和香蕉問題的與或圖第二章 知識表示方法 2.2問題歸約法372021-11-112.3 謂詞邏輯法謂詞邏輯法第二章 知識表示方法 2.3 謂詞邏輯法382021-11-11l謂詞邏輯表示法是一種基于數理邏輯的知識表示方式。l邏輯學的研究對象是思維，研究內容是思維的形式結構和推理規律。l數理邏輯用數學方法研究推理的規律l所渭數學方法，就是引入一套符號體系的方法，所以數理邏輯又稱符號邏輯。l通過概念對事物是否具有某種屬性進行肯定和否定的回答，這就是判斷；l由一個和幾個判斷推出另一個判斷的思維形式，就是推理。l數理邏輯的最基本內容：

21、命題邏輯與謂詞邏輯。謂詞邏輯表示的謂詞邏輯表示的邏輯基礎邏輯基礎第二章 知識表示方法 2.3 謂詞邏輯法392021-11-11l邏輯推理根據命題的表現形式不同，分為命題邏輯和謂詞邏輯。l命題邏輯：把命題作為最基本的成分，只研究命題推理的規律。但它有較大的局限性，不適合于表達復雜的問題。l謂詞邏輯 ：把命題細分為謂詞、個體和量詞等。它是一種形式語言，將邏輯推理符號化 ，能表達豐富的內容。命題邏輯和謂詞邏輯命題邏輯和謂詞邏輯第二章 知識表示方法 2.3 謂詞邏輯法402021-11-11l能夠判別真假的陳述句，稱做命題l陳述句的判斷為真或假，稱為命題的真值。l自然語言往往有歧義性，給問題研究帶來

22、困難，人們將命題符號化，命題一般用大寫英文字母表示： P：北京是中國的首都l當P表示確定的命題時，稱P為命題常元l當P表示任意的沒有賦予具體內容的抽象命題時，稱為命題變元。l命題變元不是命題l單個命題又稱原子命題l多個原子命題通過命題聯結詞構成的命題為復合命題。命題、命題變元命題、命題變元第二章 知識表示方法 2.3 謂詞邏輯法412021-11-11l用歸納法給出合式公式合式公式的遞歸定義： 命題變元是合式公式。 若A為合式公式，則A也是一個合式公式。 若A和B都是合式公式，則（AB），（AB），（AB）和（AB）也都是合式公式。 1.只有有限次運用（1）至（3）構成的符號串，才是合式公式。

23、合合式式公式（命詞公式）公式（命詞公式）第二章 知識表示方法 2.3 謂詞邏輯法422021-11-11l設P1，P2，Pn是公式A中的全部命題變元。給P1，P2，Pn各指定一個值，稱為對A的一 個指派或賦值。l若這組值使A的真值為真，則稱這組值為A的成真指派l若使A的真值為假，則稱這組值為A的成假指派。l命題公式A，若對它的任意一組指派，取值恒為真，則稱公式A為重言式(Tautobgy)，或永真式l若對它的任意一組指派，恒取值均為假，則稱A為矛盾式(Contradiction)，或永假式。l如果至少有一組指派使A的值為真，則稱公式A為可滿足式(Satisfiable)。指派指派與與公式公式真

24、值真值第二章 知識表示方法 2.3 謂詞邏輯法432021-11-11lA、B為命題公式，若AB為重言式，則稱A與B等價l一組基本等價式：l否定之否定 （P） P l蘊含等值式 PQ PQ PQ Q P l狄摩根定律 (PQ)PQ (PQ)PQ l分配律 P（QR ） （PQ)(PR) P(QR) (PQ)(PR） l交換律 PQ QP PQ QP l結合律 (PQ)R P(QR） l (PQ)R P(QR ） l逆否律 PQ QP 1.吸收律 P（QP ） P ， P(QP) P 命題公式命題公式的等價的等價第二章 知識表示方法 2.3 謂詞邏輯法442021-11-11l在謂詞邏輯中，將原

25、子命題分解為謂詞與個體兩部分。l可以獨立存在的物體稱為個體。(它可以是抽象的，也可以是具體的)l用來刻劃個體的性質或關系的詞稱為謂詞。刻劃一個個體性質的詞稱為一元謂詞；刻劃n個個體之間關系的詞稱為n元謂詞l用大寫字母表示謂詞，用小寫字母表示個體，如Q(a)l由n個個體和n元謂詞所組成的命題可表示為 G(a1,a2,an)謂詞謂詞第二章 知識表示方法 2.3 謂詞邏輯法452021-11-11謂詞表示舉例謂詞表示舉例l謂詞比命題更加細致地刻畫知識： 表達能力強l如：北京是個城市， City(北京)把城市這個概念分割出來。把“城市” 與“北京”兩個概念連接在一起，而且說明“北京”是“城市”的子概念

26、。（有層） 謂詞可以代表變化的情況l如：City(北京),真。 City(煤球)，假第二章 知識表示方法 2.3 謂詞邏輯法462021-11-11函函 數數l函數是實現同一個體域中從一個個體到另一個個體的映射。例如，“王宏的父親是教師”王宏是個體；王宏的父親也是個體謂詞表示為TEACHER（father(Wanghong)）father是函數； TEACHER是謂詞l函數與謂詞的區別謂詞實現的是從個體域中的個體到T或F的映射函數無所謂真假第二章 知識表示方法 2.3 謂詞邏輯法472021-11-11一階謂詞一階謂詞l 在謂詞P(x1,x2,xn)中，如果xi都是個體常量、變元或函數，稱它為

27、一階謂詞。l如果某個xi本身又是一個一階謂詞，則稱它為二階謂詞。第二章 知識表示方法 2.3 謂詞邏輯法482021-11-11l量詞量詞就是在命題里表示數量的詞。它分為：全稱量詞全稱量詞： 一個原子公式P（x），對于所有可能的變量x都具有值T，這個特性可由全稱量詞（x）來表示。存在量詞存在量詞： 如果至少有一個x值可使P（x）為T，這個特性可由存在量詞（x）來表示。 l例如，句子“所有的機器人是灰色的”可表示為（x）ROBOT（X） COLOR（x，GRAY） 句子“1號房間內有個物體”可表示為（x）INROOM（x，r1）量詞量詞第二章 知識表示方法 2.3 謂詞邏輯法492021-11-

28、11l連詞連詞： （與）、（或）、（蘊涵）、（或）（非）、（等價）。例如“我喜愛音樂和繪畫”可表示成：LIKE（I，MUSIC）LIKE（I，PAINTING） “李明打籃球或踢足球”可表示為：PLAYS（LIMING，BASKETBALL）PLAYS（LIMING，FOOTBALL） “如果該書是何平的，那么它是蘭色封面的”，可表示為：OWNS（HEPING，BOOK-1）=COLOR(BOOK-1,BLUE) 子句“機器人不在2號房間內”可表示為： INROOM（ROBOT，r2） 連詞連詞第二章 知識表示方法 2.3 謂詞邏輯法502021-11-11l項的遞歸定義項的遞歸定義：常量符號

29、是項； 變量符號是項；如果f是n-元函數符號，t1，t2，. ，tn是項，則f（t1，t2，. ，tn）也是項。l原子原子：如果P是n-謂詞，t1，t2，. ，tn是項，則P（t1，t2，.，tn）是一個原子。由若干謂詞符號和項組成。項與原子項與原子第二章 知識表示方法 2.3 謂詞邏輯法512021-11-11l設P(x1,x2,.,xn)為任意的n元謂詞，t1，t2，. ，tn為項。則lP（t1，t2，. ，tn）叫做原子原子謂詞謂詞公式公式。原子原子謂詞謂詞公式公式第二章 知識表示方法 2.3 謂詞邏輯法522021-11-11l有意義的符號序列是系統里的合式公式l用歸納法給出合式公式合

30、式公式的遞歸定義： 原子謂詞公式是合式公式。 若A為合式公式，則A也是一個合式公式。 若A和B都是合式公式，則（AB），（AB），（AB）和（AB）也都是合式公式。 若A是合式公式，x為A中的自由變元，則（x）A和（x）A都是合式公式。 1.只有有限次運用（1）至（4）構成的符號串，才是合式公式。合合式式公式（謂詞公式）公式（謂詞公式）第二章 知識表示方法 2.3 謂詞邏輯法532021-11-11變量類型變量類型l約束變量約束變量：如果一個合式公式中某個變量是經過量化的，這個變量叫約束變量。l自由變量自由變量：一個合式公式中沒被量化的變量叫自由變量。第二章 知識表示方法 2.3 謂詞邏輯法5

31、42021-11-11l否定之否定 （P） P PQ PQ 狄摩根定律 （PQ） PQ （PQ） PQ 分配律 P（QR ） （PQ)(PR) P(QR) (PQ)(PR） 交換律 PQ QP PQ QP 合合式式公式等價關系公式等價關系第二章 知識表示方法 2.3 謂詞邏輯法552021-11-11n結合律 (PQ)R P(QR） (PQ)R P(QR ） n逆否律 PQ QP n (x)P(x) (x)P(x) (x)P(x) (x)P(x) n (x)P(x)Q(x) (x)P(x)(x)Q(x) (x)P(x)Q(x) (x)P(x)(x)Q(x) n (x)P(x) (y)P(y)

32、(x)P(x) (y)P(y) 合合式式公式等價關系（二）公式等價關系（二）第二章 知識表示方法 2.3 謂詞邏輯法562021-11-11置換置換l將合式公式中的變量變換成置換項。 一個置換s記為：s=z/x,A/y。表示用z置換x，用A置換y l設合式公式：P(x,f(y),B)、置換：s= z/x,A/y，則：P(x,f(y),B)s= P(z,f(A),B)l置換滿足結合率：設L為合式公式，s1、s2為置換，則： (Ls1)s2=L(s1s2)l置換不滿足交換率：s1s2s2s1第二章 知識表示方法 2.3 謂詞邏輯法572021-11-11合一合一l兩個重要的邏輯推理規則：假言推理：

33、 P，PQ可產生Q全稱化推理： (x)P(x)可產生P(A) A為任意常量符號l合一：合一：尋找某個置換以使兩個合式公式一致l設合式公式：P(x,f(y),B)、 P(x,f(B),B)、置換：s= B/y，則：P(x,f(y),B)s= P(z,f(B),B)第二章 知識表示方法 2.3 謂詞邏輯法582021-11-11合一者合一者l合一者：合一者：一個置換s作用于合式公式集Ei的每一個元素，記為Eis 。若E1s = E2s =，稱s為Ei 的合一者l最一般合一者：最一般合一者：對Ei的任一合一者s，存在Eis =Eigs，則g稱為最一般合一者。記為mgul設合式公式：P(x,f(y),

34、B)、 P(x,f(B),B)、置換：s1= A/x,B/y、 s2= B/y l則：P(x,f(y),B)s1= P(x,f(B),B)s1= P(A,f(B),B)l則：P(x,f(y),B)s2= P(x,f(B),B)s2= P(x,f(B),B)ls1為合一者， s2為最一般合一者第二章 知識表示方法 2.3 謂詞邏輯法592021-11-11等值的幾條規則等值的幾條規則l 1置換規則l 設P(A)是含公式A的公式，P(B)是用公式B取代P(A)中的A得到的公式，若AB，則砂P(A) P(B)。l 2約束變元換名規則l 將某量詞轄域中某個約束出現的個體變元及相應的指導變元，改成該量詞

35、轄域中未曾出現過的個體變元，其余不變，所得公式與原公式等值。l 3自由變元代入規則l 對公式A中某自由出現的個體變元的所有出現，用A中未曾出現過的個體變元符號代替，A中其余部分不變，所得公式與原公式等值。第二章 知識表示方法 2.3 謂詞邏輯法602021-11-11知識的知識的謂詞謂詞邏輯表示例邏輯表示例l若張英是張華的女兒且張華是王芳的兒子，則張英是王芳的孫女l設 D(x,y)：x是y的女兒。l S(x,y)：x是y的兒子l G(x,y)：x是y的孫女l M(x)：x是人la：張英b：張華c：王芳l原命題可表示為：l(M(a)M(b)M(c)D(a,b)S(b,c) G(a,c) 。 第二

36、章 知識表示方法 2.3 謂詞邏輯法612021-11-11前束范式前束范式l一個謂詞公式，若它的所有量詞均非否定的出現在公式的最前面，且它們的轄域一直延伸到公式的末尾，則稱這種形式的公式為前束范式l前束范式與原公式等值l例如：(x) (y)(P(x)Q(y) R(z)l設公式A是一前束范式，若A的尾部具有形式： (A11 A1N1) (Am1 AmNm ）其中Aij是原子謂詞公式或其否定，則稱A是前束合取范式l若A的尾部具有形式 ：(A11 A1N1) (Am1 AmNm ）其中Aij是原子謂詞公式或其否定，則稱A是前束析取范式第二章 知識表示方法 2.3 謂詞邏輯法622021-11-11

37、謂詞演算的推理理淪謂詞演算的推理理淪l 如果A1 An B為永真式，則稱A1 ， ， An 可以推出Bl永真的蘊涵式稱為推理定律l命題邏輯的推理規則全部適用l推理規則l1 全稱量詞消去規則 xP(x) = P(y) ( xP(x) P(y)是永真式)l2全稱量詞引入規則 P(x) = yP(y) l3存在量詞引入規則 P(a) = xP(x)l4 存在量詞消去規則 xP(x) = P(a)第二章 知識表示方法 2.3 謂詞邏輯法632021-11-11謂詞謂詞邏輯表示邏輯表示的主要優點的主要優點l (1)自然謂詞邏輯表示法接近于人們對問題的直觀理解，易于接受l(2)明確明確規定如何由簡單陳述句

38、構造復雜陳述句，如連接詞、量詞的用法與含義等。知識表示明確、易于理解l(3)精確謂詞公式的真值只有“真”與“假”，因此可用來表示精確知識，并可保證經演繹推理所得結論的精確性。l(4)靈活知識和處理知識的程序被有效分開。在表示知識時，無須考慮處理知識的細節。l(5)模塊化各條知識相對獨立，之間不直接發生聯系，知識維護比較容易第二章 知識表示方法 2.3 謂詞邏輯法642021-11-11邏輯表示邏輯表示的缺憾的缺憾邏輯所關心的主要問題是開發出具有合理而且完備的推理規則的形式表示語言。其結果是謂詞演算語義強調對合式公式的保持真值運算。邏輯中不考慮前提與結論間的特定關系把常識推理映射到形式邏輯時會產

39、生許多問題例如，“如果某鳥是北美紅雀，則它是紅的”，將北美紅雀和紅色關聯起來了寫成謂詞演算的形式： x(cardinal(x) red(x)經等值運算得等價形式：x(red(x) cardinal(x)因此，有：“紙是白的而且也不是北美紅雀”可作為第二個表達式為真的證據，從而也是第一個表達式為真的證據結論：紙的白色性可作為“北美紅雀為紅色”的證據是不是很可笑？第二章 知識表示方法 2.3 謂詞邏輯法652021-11-112.4 語義網絡表示法語義網絡表示法第二章 知識表示方法 2.4 語義網絡表示法662021-11-11語義網絡表示法概述語義網絡表示法概述1968年Quillian的博士論

40、文建議用一種語義網絡來描述人對事物的認知，實際上是對人腦功能的模擬。 語義網絡是知識的一種圖解表示。 它由“結點”和“弧線”組成， “結點”表示實體、概念、事實等， “弧線”表示“結點”的關系。語義網絡含蓋了一類基于圖的表示例如： XIAOYANISAHAS-PARTSWALLOWWINGSBIRDISA第二章 知識表示方法 2.4 語義網絡表示法672021-11-11二元語義網絡的表示二元語義網絡的表示l語義網絡的“弧線”只能表示二元關系，要表示下例一樣的知識，提出了“結點”既可以表示實體或概念，也可以表示“事實“、”情況”和“動作”l例如，“小燕從春天到秋天占有一個巢”第二章 知識表示方

41、法 2.4 語義網絡表示法682021-11-11語義網絡示例語義網絡示例XIAOYANISAISASWALLOWOWN-1BIRDISASITUATIONOWNERSHIPFALLSPRINGNEST-1TIMENESTISAISAISAOWNEESTARTENDISAOWNER第二章 知識表示方法 2.4 語義網絡表示法692021-11-11多元語義網絡多元語義網絡l從本質上講，節點間的連接是二元關系，因此，語義網絡本質上只能表示二元關系。若要表示多元關系，則要把多元關系轉換成一組二元關系的組合。l例如，三條線a，b，c組成一個三角型，是一個三元關系triangle(a,b,c)，可轉換

42、成一組二元關系的組合：CAT(a,b) CAT(b,c) CAT(c,a) 其中CAT表示串行連接第二章 知識表示方法 2.4 語義網絡表示法702021-11-11“合取合取”的語義網絡表示的語義網絡表示例如，表示John gave Mary the book這個事實：JOHNGIVERISAGIVEB23OBJECTMARYG1BOOKISARECIPIENT其中，G1為動作：給人東西；B23為給人的東西GIVER，ISA，OBJECT，RECIPIENT為“合取”第二章 知識表示方法 2.4 語義網絡表示法712021-11-11“析取析取”的語義網絡表示的語義網絡表示采用DIS標注來表

43、示例如，表示：ISA(A,B) PART-OF(B,C)BDISCAISAPARTOF第二章 知識表示方法 2.4 語義網絡表示法722021-11-11“否定否定”的語義網絡表示的語義網絡表示采用 或者NEG標注來表示例如，表示： (ISA(A,B) PART-OF(B,C)BNEGCAISAPARTOFBA ISA第二章 知識表示方法 2.4 語義網絡表示法732021-11-11“蘊涵蘊涵”的語義網絡表示的語義網絡表示l“蘊涵蘊涵”采用ANTE和CONSE標注來表示l例如，Every one who lives at 37 Maple Street is a programmerY是一個

44、特定的地址事件；X是一個變量，表示與此事件有關的人們O(X,Y)是一個特定的職業事件，是一個SKOLEM函數XLOCO(X,Y)PROGRAMMER37-MAPLEPROFESSIONWORKERYADDRESS ISAOCCUPATION ISAPERSONANTECONSE第二章 知識表示方法 2.4 語義網絡表示法742021-11-11“存在量化存在量化”的語義網絡表示的語義網絡表示l“存在量化存在量化”直接用ISA鏈表示l例如， The dog bit the postmanD是一個特定的狗；B是一個特定的咬人事件P是一個特定的郵遞員BPBITEVICTIMDDOG ISAPOSTM

45、AN ISAASSAILANTISA第二章 知識表示方法 2.4 語義網絡表示法752021-11-11“全稱量化全稱量化”的語義網絡表示的語義網絡表示l“全稱量化全稱量化” 用分割方法來表示:把語義網絡分割成空間分層集合，每個空間相應于一個或幾個變量的范圍。一個空間表示一個特定斷言，稱為FORM用代表全稱量詞的特殊鏈，表示全稱量化的變量特殊鏈以及空間分割FORM，一起表示了知識的“全稱量化全稱量化” 例如，Every dog has bitten every postman第二章 知識表示方法 2.4 語義網絡表示法762021-11-11“全稱量化全稱量化”的語義網絡表示例的語義網絡表示例

46、GS是一個概念節點；表示具有全稱化的一般事件G是GS的的一個實例，是一個斷言BPGGSFORMDDOG ISAPOSTMAN ISAISAISABITE第二章 知識表示方法 2.4 語義網絡表示法772021-11-11語義網絡的推理過程語義網絡的推理過程l語義網絡對所給定的表達結構表示什么語義沒有統一的表示法l語義網絡的推理過程主要有兩種：繼承繼承推理匹配匹配推理l為了方便敘述，將鏈又稱為槽，鏈的尾部節點稱為值節點，表示該槽的值第二章 知識表示方法 2.4 語義網絡表示法782021-11-11繼承和匹配繼承和匹配l繼承繼承是把對事物的描寫從概念節點或類節點傳遞到實例節點l繼承繼承分為3種繼

47、承過程：值繼承、“如果需要”繼承和“缺省繼承”l匹配匹配是在概念或類由幾部分組成時，實例的某部分與概念或類的某部分相匹配第二章 知識表示方法 2.4 語義網絡表示法792021-11-11語義網絡推理中的語義網絡推理中的“值繼承值繼承” 雖然Brick12沒有槽Shape，但它是概念Brick的一個實例，因此，根據繼承關系知道，它有槽Shape，且其值為Rectangular.BrickRectangularBrick12Wedge18ISAAKOTriangularWedge ISAShapeAKOShapeBLOCK第二章 知識表示方法 2.4 語義網絡表示法802021-11-11語義網

48、絡推理中的語義網絡推理中的“如果需要如果需要”繼承繼承l如果不知道槽值，可利用已知信息進行計算得到。這種程序稱為“如果需要”程序。l為了讓槽有多個值，給槽增加“側面”， “如果需要”程序放在“如果需要側面”中。l需要計算時，使用類中的程序。如Brick12的Weight槽沒有值，查找類中“如果需要” 程序，有則計算其值BrickBlock-Weight procedureBrick12？4400ISADensity400WeightWeight (if-needed)AKOVolumeBLOCK11第二章 知識表示方法 2.4 語義網絡表示法812021-11-11語義網絡推理中的語義網絡推理

49、中的“缺省缺省”繼承繼承l我們有時對假設不是很有把握，就用“可能”表示。對這種值稱為“缺省”值，放在槽的缺省（Default）側面中。l某個實例要得到“缺省”值，則到類中去繼承。如Brick12沒有顏色的“缺省”值，到類Brick中繼承可得為RedBrickRedBrick12Wedge18ISAAKOBlueWedge ISAAKOColor(Default)BLOCKColor(Default)第二章 知識表示方法 2.4 語義網絡表示法822021-11-11語義網絡推理中的語義網絡推理中的“匹配匹配”過程（一）過程（一）l考察事物由幾部分組成時，繼承過程又是怎樣的呢？l如下圖，toyh

50、ouse77是toyhouse的實例，因此，繼承了全部的組成部分，用虛節點和虛鏈表示。l但如果實例中已確定了某些部分，該如何繼承呢？BrickWedgepartToy-housepartsupportpartToy-house77partsupport繼承繼承ISA第二章 知識表示方法 2.4 語義網絡表示法832021-11-11語義網絡推理中的語義網絡推理中的“匹配匹配”過程（二）過程（二）l如下圖，Structure35是toyhouse的實例，但它已確定了部分內容，這時，將各部件與類中的部件進行匹配，找出對應的關系及其它要繼承的部分，用虛鏈表示。BrickWedgepartToy-ho

51、usepartsupportpartStructure35partsupport匹配匹配ISA第二章 知識表示方法 2.4 語義網絡表示法842021-11-11語義網絡的優缺點語義網絡的優缺點l語義網絡圖的好處是直觀、清晰l缺點是表達范圍有限。如，一旦有十個結點，而且各結點之間又有聯系，則這個網絡就很難辨請了。 第二章 知識表示方法 2.4 語義網絡表示法852021-11-112.5 框架表示法框架表示法第二章 知識表示方法 2.5 框架表示法862021-11-11框架理論框架理論l1975年 Minsky在論文中提出了框架理論。l認為人們在現實世界中對各種事物的認識都是以一種結構化模式

52、存儲在記憶中的l這種結構化的模式在人們的大腦中形成了一種固定的框架l當人們面臨新的情況，就從記憶中找出一個合適的框架，并根據實際情況對其細節加以修改補充，從而形成對新觀察到的事物的認識。l如一想到教室，頭腦中就產生一個房間，里面有桌子、椅子、黑板、門、窗等第二章 知識表示方法 2.5 框架表示法872021-11-11框框 架架l人們常采用以往的經驗去認識新事物l人們根據經驗和認識形成對某一事物的概念模型l概念模型通過通用數據結構存儲起來，也稱為知識結構l把新的數據加入到知識結構中便形成了一個具體的描述l這樣的知識結構稱為框架，框架是知識的基本單位。l把觀察或認識到的具體細節填入后，就得到了該

53、框架的一個具體實例，稱為實例框架。l需要填充的數據元素稱為槽。第二章 知識表示方法 2.5 框架表示法882021-11-11框框 架架 系系 統統l人們常采用以往的經驗去認識新事物l人們根據經驗和認識形成對某一事物的概念模型l概念模型通過通用數據結構存儲起來，也稱為知識結構l把新的數據加入到知識結構中便形成了一個具體的描述l這樣的知識結構稱為框架，框架是知識的基本單位。l把觀察或認識到的具體細節填入后，就得到了該框架的一個具體實例，稱為實例框架。l需要填充的數據元素稱為槽。l把一組有關的框架連接起來形成框架系統第二章 知識表示方法 2.5 框架表示法892021-11-11框架系統與語義網絡

54、的比較框架系統與語義網絡的比較l框架系統與語義的相同框架系統與語義的相同Minsky把框架系統描述為節點和關系的網絡框架系統可以用有向圖來表示l框架和語義網絡的區別框架和語義網絡的區別語義網絡本質上是一種二維知識表示方法，l網絡中，所有概念被表示為同一個層上的節點和邊。框架通過允許節點有結構而增加了第三維信息通過框架更容易層次化的組織知識。l框架可以把對象看成是單一實體，用一個節點表示，也可以把實體中的某部分單獨拿出來，詳細描述，用另一個節點表示。第二章 知識表示方法 2.5 框架表示法902021-11-11框架的構成框架的構成l框架是由若干個結點和關系（統稱為槽）構成的網絡。是語義網絡的一

55、般化形式的一種結構。同語義網絡沒有本質的區別。l表示形式：由框架名、槽名、側面、值組成l對于復雜問題，需要使用多個框架，構成框架系統l推理方法：沒有固定的推理機理。但和語義網絡一樣遵循匹配和繼承的原理。 第二章 知識表示方法 2.5 框架表示法912021-11-11簡單框架示例簡單框架示例lJOHNIsa: PERSONProfession: PROGRAMMERHeight: 1.8MWeight: 79kg第二章 知識表示方法 2.5 框架表示法922021-11-11立體視圖的框架系統表示立體視圖的框架系統表示E must-be : parallelogramFRAME ISA : Cube REGION : (A,E,B) ABEB must-be : parallelogramA must-be : parall