1、12021-11-11第二章第二章 知識表示方法知識表示方法22021-11-112.1 知識與知識表示的概念知識與知識表示的概念第二章 知識表示方法 2.1 知識與知識表示的概念32021-11-11描述客觀世界描述客觀世界l人們對客觀世界的描述是通過數(shù)據(jù)和信息來實現(xiàn)的。l數(shù)據(jù)：指人們?yōu)榱嗣枋隹陀^世界中的具體事物而引人的一些數(shù)字、字符、文字等符號或符號的組合?！敖▏薄ⅰ?0”是兩個數(shù)據(jù)l信息：不同數(shù)據(jù)組成的一種結(jié)構(gòu)。建國50歲l信息是數(shù)據(jù)在特定場合下的含義，即數(shù)據(jù)的語義。相同的數(shù)據(jù)在不同場合會有不同的含義建國50歲；建國50周年l多數(shù)信息僅是對客觀事物的一般性描述，它還不是知識第二章 知識

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

3、示性與可利用性。 第二章 知識表示方法 2.1 知識與知識表示的概念62021-11-11知識表示知識表示l 知識表示實際上就是對知識的一種描述，即用一些約定的符號把知識編碼成一組計算機可以接受的數(shù)據(jù)結(jié)構(gòu)。l一般來說，同一知識可以有多種不同的表示形式，而不同表示形式所產(chǎn)生的效果又可能不一樣。l知識表示的要求表示能力可利用性可組織性與可維護性可實現(xiàn)性自然性與可理解性第二章 知識表示方法 2.1 知識與知識表示的概念72021-11-11幾種常用的知識表示方法幾種常用的知識表示方法n狀態(tài)空間法n問題歸約法n謂詞邏輯法n語義網(wǎng)絡(luò)表示法n框架表示法n過程表示n混合型知識表示方法n面向?qū)ο蟮谋硎痉椒╪規(guī)

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

5、1-11-11狀態(tài)空間法例狀態(tài)空間法例8數(shù)碼難題數(shù)碼難題第二章 知識表示方法 2.2狀態(tài)空間法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狀態(tài)描述狀態(tài)描述 l狀態(tài)（狀態(tài)（state

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

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

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

9、猴子抓到了香蕉第二章 知識表示方法 2.1狀態(tài)空間法172021-11-11猴子摘香蕉問題猴子摘香蕉問題-初始與結(jié)束狀態(tài)初始與結(jié)束狀態(tài)1，初始狀態(tài)（c, 0, b, 0）2，結(jié)束狀態(tài)（c, 1, c, 1）第二章 知識表示方法 2.1狀態(tài)空間法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狀態(tài)空間法192021-11-11猴子摘香蕉問題猴子摘香蕉問題-狀態(tài)空間圖狀態(tài)空間圖第二章 知識表示方法 2.1狀態(tài)空間法(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、題歸約法是不同于狀態(tài)空間的人工智能中另一種問題描述和求解方法。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對梵塔難題進行問題歸約對梵塔難題進行問題歸約我們把原始難題規(guī)約為以下三個子難題： 移動圓盤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與或圖是一個超圖，節(jié)點間附有連接符。lK-連接符：.K個 由K-連接符連接的K個節(jié)點為 與節(jié)點K為1時為或節(jié)點 起始節(jié)點對應于原始問題的描述起始節(jié)點對應于原始問題的描述 子節(jié)點對應于子問題的描述子節(jié)點對應于子問題的描述第二章 知識表示方法 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能解節(jié)點能解節(jié)點l對應于本原問題的節(jié)點為終節(jié)點l終節(jié)點是能解節(jié)點l若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點至少有一能解時，該非終節(jié)點才能解。l若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。第二章 知識表示方法 2.2問題歸約法292021-11-11不能解節(jié)點不能解節(jié)點l沒有后裔的非終節(jié)點是不能解節(jié)點。l若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該

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

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

17、l前面已經(jīng)討論過的猴子和香蕉問題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應用關(guān)鍵算符和差別表示法的歸約過程如下第二章 知識表示方法 2.2問題歸約法332021-11-11猴子和香蕉問題的猴子和香蕉問題的歸約過程歸約過程(一一)l找差別：

18、 G=(c,1,c,1) 、S= (a,0,b,0) S與G的差別在最后一個元素不是1l關(guān)聯(lián)算符： f4 = grasp消去該差別 因此，與f4關(guān)聯(lián)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辨別出關(guān)聯(lián)算符： f2 :pushbox(c)

19、f1 : goto(c) f3:climbboxl選用f2關(guān)鍵算符歸約，得一對子問題: 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辨別出關(guān)聯(lián)算符： f1 : goto(b) l用f1關(guān)鍵算符歸約，發(fā)現(xiàn)是個本原問題: (S, f1,G f2) l經(jīng)過這樣反復遞歸重復，最終解答了初始問題第二章 知識表示方法

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

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

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

23、合合式式公式（命詞公式）公式（命詞公式）第二章 知識表示方法 2.3 謂詞邏輯法422021-11-11l設(shè)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結(jié)合律 (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用來刻劃個體的性質(zhì)或關(guān)系的詞稱為謂詞?？虅澮粋€個體性質(zhì)的詞稱為一元謂詞；刻劃n個個體之間關(guā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函函 數(shù)數(shù)l函數(shù)是實現(xiàn)同一個體域中從一個個體到另一個個體的映射。例如，“王宏的父親是教師”王宏是個體；王宏的父親也是個體謂詞表示為TEACHER（father(Wanghong)）father是函數(shù)； TEACHER是謂詞l函數(shù)與謂詞的區(qū)別謂詞實現(xiàn)的是從個體域中的個體到T或F的映射函數(shù)無所謂真假第二章 知識表示方法 2.3 謂詞邏輯法472021-11-11一階謂詞一階謂詞l 在謂詞P(x1,x2,xn)中，如果xi都是個體常量、變元或函數(shù)，稱它為

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

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

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

30、式公式的遞歸定義： 原子謂詞公式是合式公式。 若A為合式公式，則A也是一個合式公式。 若A和B都是合式公式，則（AB），（AB），（AB）和（AB）也都是合式公式。 若A是合式公式，x為A中的自由變元，則（x）A和（x）A都是合式公式。 1.只有有限次運用（1）至（4）構(gòu)成的符號串，才是合式公式。合合式式公式（謂詞公式）公式（謂詞公式）第二章 知識表示方法 2.3 謂詞邏輯法532021-11-11變量類型變量類型l約束變量約束變量：如果一個合式公式中某個變量是經(jīng)過量化的，這個變量叫約束變量。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 合合式式公式等價關(guān)系公式等價關(guān)系第二章 知識表示方法 2.3 謂詞邏輯法552021-11-11n結(jié)合律 (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) 合合式式公式等價關(guān)系（二）公式等價關(guān)系（二）第二章 知識表示方法 2.3 謂詞邏輯法562021-11-11置換置換l將合式公式中的變量變換成置換項。 一個置換s記為：s=z/x,A/y。表示用z置換x，用A置換y l設(shè)合式公式：P(x,f(y),B)、置換：s= z/x,A/y，則：P(x,f(y),B)s= P(z,f(A),B)l置換滿足結(jié)合率：設(shè)L為合式公式，s1、s2為置換，則： (Ls1)s2=L(s1s2)l置換不滿足交換率：s1s2s2s1第二章 知識表示方法 2.3 謂詞邏輯法572021-11-11合一合一l兩個重要的邏輯推理規(guī)則：假言推理：

33、 P，PQ可產(chǎn)生Q全稱化推理： (x)P(x)可產(chǎn)生P(A) A為任意常量符號l合一：合一：尋找某個置換以使兩個合式公式一致l設(shè)合式公式：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設(shè)合式公式：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等值的幾條規(guī)則等值的幾條規(guī)則l 1置換規(guī)則l 設(shè)P(A)是含公式A的公式，P(B)是用公式B取代P(A)中的A得到的公式，若AB，則砂P(A) P(B)。l 2約束變元換名規(guī)則l 將某量詞轄域中某個約束出現(xiàn)的個體變元及相應的指導變元，改成該量詞

35、轄域中未曾出現(xiàn)過的個體變元，其余不變，所得公式與原公式等值。l 3自由變元代入規(guī)則l 對公式A中某自由出現(xiàn)的個體變元的所有出現(xiàn)，用A中未曾出現(xiàn)過的個體變元符號代替，A中其余部分不變，所得公式與原公式等值。第二章 知識表示方法 2.3 謂詞邏輯法602021-11-11知識的知識的謂詞謂詞邏輯表示例邏輯表示例l若張英是張華的女兒且張華是王芳的兒子，則張英是王芳的孫女l設(shè) 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一個謂詞公式，若它的所有量詞均非否定的出現(xiàn)在公式的最前面，且它們的轄域一直延伸到公式的末尾，則稱這種形式的公式為前束范式l前束范式與原公式等值l例如：(x) (y)(P(x)Q(y) R(z)l設(shè)公式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命題邏輯的推理規(guī)則全部適用l推理規(guī)則l1 全稱量詞消去規(guī)則 xP(x) = P(y) ( xP(x) P(y)是永真式)l2全稱量詞引入規(guī)則 P(x) = yP(y) l3存在量詞引入規(guī)則 P(a) = xP(x)l4 存在量詞消去規(guī)則 xP(x) = P(a)第二章 知識表示方法 2.3 謂詞邏輯法632021-11-11謂詞謂詞邏輯表示邏輯表示的主要優(yōu)點的主要優(yōu)點l (1)自然謂詞邏輯表示法接近于人們對問題的直觀理解，易于接受l(2)明確明確規(guī)定如何由簡單陳述句

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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