華中科技大學人工智能第二章知識表示方法剖析

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

2、法 2.1 知識與知識表示的概念42022-6-27什么是知識什么是知識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 知識與知識表示的概念52022-6-27知識的屬性知識的屬性l真假性與相對性l不確定性l矛盾性和相客性。l可表示性與可利

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

4、 知識表示方法 2.1 知識與知識表示的概念82022-6-272.2 狀態(tài)空間法狀態(tài)空間法第二章 知識表示方法 2.2狀態(tài)空間法92022-6-27狀態(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)空間法102022-6-27狀態(tài)空

5、間法例狀態(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目標初始112022-6-27狀態(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)空間法122022-6-27操作描述操作描述l所謂操作操作，或稱為算子是引起狀態(tài)中的某分量發(fā)生改變，從而使問題由一個具體狀態(tài)A變化為另一具體狀態(tài)B的作用。使問題一種狀態(tài)變化為另一狀態(tài)的手段稱為操作符或算符操作符或算符。操作符可為走步、過程、規(guī)則、數(shù)學

7、算子、運算符號或邏輯符號等。 第二章 知識表示方法 2.2狀態(tài)空間法132022-6-27狀態(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)空間法142022-6-27狀態(tài)空間表示舉例：狀態(tài)空間表示舉例：猴子和香

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

9、法 2.1狀態(tài)空間法172022-6-27猴子摘香蕉問題猴子摘香蕉問題-初始與結(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)空間法182022-6-27猴子摘香蕉問題猴子摘香蕉問題-操作符集操作符集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, W, V, Y, z為變量第二章

10、 知識表示方法 2.1狀態(tài)空間法192022-6-27猴子摘香蕉問題猴子摘香蕉問題-狀態(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)202022-6-272.2 問題歸約法問題歸約法第二章 知識表示方法 2.2問題歸約法212022-6-27問題歸約法思想問題歸約法思想l問題歸約法問題歸約法是不同于狀態(tài)空間的人工智能中另一種

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

12、行問題歸約對梵塔難題進行問題歸約我們把原始難題規(guī)約為以下三個子難題： 移動圓盤A和B至柱子2的雙圓盤難題 移動圓盤C至柱子3的單圓盤難題 移動圓盤A和B至柱子3雙圓盤難題 第二章 知識表示方法 2.2問題歸約法242022-6-27梵塔難題的分解圖梵塔難題的分解圖第二章 知識表示方法 2.2問題歸約法AB123AB123C123C123AB123AB123252022-6-27問題歸約的表示問題歸約的表示l問題歸約表示也是一個三元組(S0,F,G):S0-一個初始問題描述,即要解決的問題(初始問題)；F-一套把問題變換為子問題的操作符（操作算子集）；G-一套本原問題描述，（可以容易得到解答的問

13、題）l問題歸約過程可以采用與或圖來表示第二章 知識表示方法 2.2問題歸約法262022-6-27問題歸約的與或圖表示問題歸約的與或圖表示基本概念基本概念l與或圖是一個超圖，節(jié)點間附有連接符。lK-連接符：.K個 由K-連接符連接的K個節(jié)點為 與節(jié)點K為1時為或節(jié)點 起始節(jié)點對應于原始問題的描述起始節(jié)點對應于原始問題的描述 子節(jié)點對應于子問題的描述子節(jié)點對應于子問題的描述第二章 知識表示方法 2.2問題歸約法272022-6-27梵塔難題的歸約圖梵塔難題的歸約圖第二章 知識表示方法 2.2問題歸約法(111)(333)(111)(122)(322)(333)(122)(322)(113)(12

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

15、少有一個子節(jié)點不能解時，該非終節(jié)點才是不能解節(jié)點。第二章 知識表示方法 2.2 問題歸約法302022-6-27一種問題歸約技術(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設f是關(guān)鍵算符，Gf是f適用的所有狀態(tài)的集合，gGf,則可以將問題歸約為（S,F,Gf）、 （g,f,f(g)）和（f(g),F,G）。而（g,f,f(g

16、)）是本原問題第二章 知識表示方法 2.2問題歸約法312022-6-27關(guān)鍵算符的辨別關(guān)鍵算符的辨別l許多問題往往無法辨別關(guān)鍵算符和知道它是決定性的步驟，只能推測某個算符子集合，其中某個算符是決定性的。l推測候選關(guān)鍵算符集合的方法之一是以“差別差別”為基礎l某個問題（S,F,G）的“差別差別”是指造成S的元不屬于G的那部分分量。l將能消去“差別”的算符或算符集合與相應的“差別差別”關(guān)聯(lián)起來，這些算符就是候選關(guān)鍵算符。第二章 知識表示方法 2.2問題歸約法322022-6-27歸約技術(shù)舉例歸約技術(shù)舉例-猴子和香蕉問題猴子和香蕉問題l前面已經(jīng)討論過的猴子和香蕉問題l其算符和適用條件f1:(W,0

17、,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問題歸約法332022-6-27猴子和香蕉問題的猴子和香蕉問題的歸約過程歸約過程(一一)l找差別： G=(c,1,c,1) 、S= (a,0,b,0) S與G的差別

18、在最后一個元素不是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問題歸約法342022-6-27猴子和香蕉問題的猴子和香蕉問題的歸約過程（二）歸約過程（二）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) f1 : goto(c) f3:climbboxl選用f2關(guān)鍵算符歸

19、約，得一對子問題: 1-1： (S,F,G f2) 和 1-2：(f2(S11),F,G f4) S11G f2第二章 知識表示方法 2.2問題歸約法352022-6-27猴子和香蕉問題的猴子和香蕉問題的歸約過程（三）歸約過程（三）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)過這樣反復遞歸重復，最終解答了初始問題第二章 知識表示方法 2.2問題歸約法362022-6-27猴子和香蕉問題的與或圖猴子和香

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

21、表示方法 2.3 謂詞邏輯法392022-6-27l邏輯推理根據(jù)命題的表現(xiàn)形式不同，分為命題邏輯和謂詞邏輯。l命題邏輯：把命題作為最基本的成分，只研究命題推理的規(guī)律。但它有較大的局限性，不適合于表達復雜的問題。l謂詞邏輯 ：把命題細分為謂詞、個體和量詞等。它是一種形式語言，將邏輯推理符號化 ，能表達豐富的內(nèi)容。命題邏輯和謂詞邏輯命題邏輯和謂詞邏輯第二章 知識表示方法 2.3 謂詞邏輯法402022-6-27l能夠判別真假的陳述句，稱做命題l陳述句的判斷為真或假，稱為命題的真值。l自然語言往往有歧義性，給問題研究帶來困難，人們將命題符號化，命題一般用大寫英文字母表示： P：北京是中國的首都l當P

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

23、22022-6-27l設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)。指派指派與與公式公式真值真值第二章 知識表示方法 2.3 謂詞邏輯法432022-6-27lA、B為命題公

24、式，若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 謂詞邏輯法442022-6-27l在謂詞邏輯中，將原子命題分解為謂詞與個體兩部分。l可以獨立存在的物體稱為個體。(它可以是抽象的，也可以是具

25、體的)l用來刻劃個體的性質(zhì)或關(guān)系的詞稱為謂詞?？虅澮粋€個體性質(zhì)的詞稱為一元謂詞；刻劃n個個體之間關(guān)系的詞稱為n元謂詞l用大寫字母表示謂詞，用小寫字母表示個體，如Q(a)l由n個個體和n元謂詞所組成的命題可表示為 G(a1,a2,an)謂詞謂詞第二章 知識表示方法 2.3 謂詞邏輯法452022-6-27謂詞表示舉例謂詞表示舉例l謂詞比命題更加細致地刻畫知識： 表達能力強l如：北京是個城市， City(北京)把城市這個概念分割出來。把“城市” 與“北京”兩個概念連接在一起，而且說明“北京”是“城市”的子概念。（有層） 謂詞可以代表變化的情況l如：City(北京),真。 City(煤球)，假第二章

26、 知識表示方法 2.3 謂詞邏輯法462022-6-27函函 數(shù)數(shù)l函數(shù)是實現(xiàn)同一個體域中從一個個體到另一個個體的映射。例如，“王宏的父親是教師”王宏是個體；王宏的父親也是個體謂詞表示為TEACHER（father(Wanghong)）father是函數(shù)； TEACHER是謂詞l函數(shù)與謂詞的區(qū)別謂詞實現(xiàn)的是從個體域中的個體到T或F的映射函數(shù)無所謂真假第二章 知識表示方法 2.3 謂詞邏輯法472022-6-27一階謂詞一階謂詞l 在謂詞P(x1,x2,xn)中，如果xi都是個體常量、變元或函數(shù)，稱它為一階謂詞。l如果某個xi本身又是一個一階謂詞，則稱它為二階謂詞。第二章 知識表示方法 2.3

27、謂詞邏輯法482022-6-27l量詞量詞就是在命題里表示數(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 謂詞邏輯法492022-6-27l連詞連詞： （與）、（或）、（蘊涵）、（或）（非）、（等價）。例如“我喜愛音樂和繪畫”可表示

28、成：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 謂詞邏輯法502022-6-27l項的遞歸定義項的遞歸定義：常量符號是項； 變量符號是項；如果f是n-元函數(shù)符號，t1，t2，. ，tn是項，則f（t1，t2，. ，t

29、n）也是項。l原子原子：如果P是n-謂詞，t1，t2，. ，tn是項，則P（t1，t2，.，tn）是一個原子。由若干謂詞符號和項組成。項與原子項與原子第二章 知識表示方法 2.3 謂詞邏輯法512022-6-27l設P(x1,x2,.,xn)為任意的n元謂詞，t1，t2，. ，tn為項。則lP（t1，t2，. ，tn）叫做原子原子謂詞謂詞公式公式。原子原子謂詞謂詞公式公式第二章 知識表示方法 2.3 謂詞邏輯法522022-6-27l有意義的符號序列是系統(tǒng)里的合式公式l用歸納法給出合式公式合式公式的遞歸定義： 原子謂詞公式是合式公式。 若A為合式公式，則A也是一個合式公式。 若A和B都是合式公

30、式，則（AB），（AB），（AB）和（AB）也都是合式公式。 若A是合式公式，x為A中的自由變元，則（x）A和（x）A都是合式公式。 1.只有有限次運用（1）至（4）構(gòu)成的符號串，才是合式公式。合合式式公式（謂詞公式）公式（謂詞公式）第二章 知識表示方法 2.3 謂詞邏輯法532022-6-27變量類型變量類型l約束變量約束變量：如果一個合式公式中某個變量是經(jīng)過量化的，這個變量叫約束變量。l自由變量自由變量：一個合式公式中沒被量化的變量叫自由變量。第二章 知識表示方法 2.3 謂詞邏輯法542022-6-27l否定之否定 （P） P PQ PQ 狄摩根定律 （PQ） PQ （PQ） PQ 分配

31、律 P（QR ） （PQ)(PR) P(QR) (PQ)(PR） 交換律 PQ QP PQ QP 合合式式公式等價關(guān)系公式等價關(guān)系第二章 知識表示方法 2.3 謂詞邏輯法552022-6-27n結(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) (x)P(x) (y)P(y) 合合式式公式等價關(guān)系（二）公式等價關(guān)系（二）第二章 知識表示方法 2.3 謂詞

32、邏輯法562022-6-27置換置換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置換滿足結(jié)合率：設L為合式公式，s1、s2為置換，則： (Ls1)s2=L(s1s2)l置換不滿足交換率：s1s2s2s1第二章 知識表示方法 2.3 謂詞邏輯法572022-6-27合一合一l兩個重要的邏輯推理規(guī)則：假言推理： P，PQ可產(chǎn)生Q全稱化推理： (x)P(x)可產(chǎn)生P(A) A為任意常量符號l合一：合一：尋找某個置換以使兩個合

33、式公式一致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 謂詞邏輯法582022-6-27合一者合一者l合一者：合一者：一個置換s作用于合式公式集Ei的每一個元素，記為Eis 。若E1s = E2s =，稱s為Ei 的合一者l最一般合一者：最一般合一者：對Ei的任一合一者s，存在Eis =Eigs，則g稱為最一般合一者。記為mgul設合式公式：P(x,f(y),B)、 P(x,f(B),B)、置換：s1= A/x,B/y、 s2= B/y l則：P(x,f(y),B)s1=

34、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 謂詞邏輯法592022-6-27等值的幾條規(guī)則等值的幾條規(guī)則l 1置換規(guī)則l 設P(A)是含公式A的公式，P(B)是用公式B取代P(A)中的A得到的公式，若AB，則砂P(A) P(B)。l 2約束變元換名規(guī)則l 將某量詞轄域中某個約束出現(xiàn)的個體變元及相應的指導變元，改成該量詞轄域中未曾出現(xiàn)過的個體變元，其余不變，所得公式與原公式等值。l 3自由變元代入規(guī)則l 對公式A中某自由出現(xiàn)的個體變元的

35、所有出現(xiàn)，用A中未曾出現(xiàn)過的個體變元符號代替，A中其余部分不變，所得公式與原公式等值。第二章 知識表示方法 2.3 謂詞邏輯法602022-6-27知識的知識的謂詞謂詞邏輯表示例邏輯表示例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) 。 第二章 知識表示方法 2.3 謂詞邏輯法612022-6-27前束范式前束范式l一個謂詞公式，若它的所有量詞均非否定的出現(xiàn)在

36、公式的最前面，且它們的轄域一直延伸到公式的末尾，則稱這種形式的公式為前束范式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 謂詞邏輯法622022-6-27謂詞演算的推理理淪謂詞演算的推理理淪l 如果A1 An B為永真式，則稱A1 ， ， An 可以推出Bl永真的蘊涵式稱為推理

37、定律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 謂詞邏輯法632022-6-27謂詞謂詞邏輯表示邏輯表示的主要優(yōu)點的主要優(yōu)點l (1)自然謂詞邏輯表示法接近于人們對問題的直觀理解，易于接受l(2)明確明確規(guī)定如何由簡單陳述句構(gòu)造復雜陳述句，如連接詞、量詞的用法與含義等。知識表示明確、易于理解l(3)精確謂詞公式的真值只有“真”與“假”，因此可用來表

38、示精確知識，并可保證經(jīng)演繹推理所得結(jié)論的精確性。l(4)靈活知識和處理知識的程序被有效分開。在表示知識時，無須考慮處理知識的細節(jié)。l(5)模塊化各條知識相對獨立，之間不直接發(fā)生聯(lián)系，知識維護比較容易第二章 知識表示方法 2.3 謂詞邏輯法642022-6-27邏輯表示邏輯表示的缺憾的缺憾邏輯所關(guān)心的主要問題是開發(fā)出具有合理而且完備的推理規(guī)則的形式表示語言。其結(jié)果是謂詞演算語義強調(diào)對合式公式的保持真值運算。邏輯中不考慮前提與結(jié)論間的特定關(guān)系把常識推理映射到形式邏輯時會產(chǎn)生許多問題例如，“如果某鳥是北美紅雀，則它是紅的”，將北美紅雀和紅色關(guān)聯(lián)起來了寫成謂詞演算的形式： x(cardinal(x)

39、red(x)經(jīng)等值運算得等價形式：x(red(x) cardinal(x)因此，有：“紙是白的而且也不是北美紅雀”可作為第二個表達式為真的證據(jù)，從而也是第一個表達式為真的證據(jù)結(jié)論：紙的白色性可作為“北美紅雀為紅色”的證據(jù)是不是很可笑？第二章 知識表示方法 2.3 謂詞邏輯法652022-6-272.4 語義網(wǎng)絡表示法語義網(wǎng)絡表示法第二章 知識表示方法 2.4 語義網(wǎng)絡表示法662022-6-27語義網(wǎng)絡表示法概述語義網(wǎng)絡表示法概述1968年Quillian的博士論文建議用一種語義網(wǎng)絡來描述人對事物的認知，實際上是對人腦功能的模擬。 語義網(wǎng)絡是知識的一種圖解表示。 它由“結(jié)點”和“弧線”組成，

40、“結(jié)點”表示實體、概念、事實等， “弧線”表示“結(jié)點”的關(guān)系。語義網(wǎng)絡含蓋了一類基于圖的表示例如： XIAOYANISAHAS-PARTSWALLOWWINGSBIRDISA第二章 知識表示方法 2.4 語義網(wǎng)絡表示法672022-6-27二元語義網(wǎng)絡的表示二元語義網(wǎng)絡的表示l語義網(wǎng)絡的“弧線”只能表示二元關(guān)系，要表示下例一樣的知識，提出了“結(jié)點”既可以表示實體或概念，也可以表示“事實“、”情況”和“動作”l例如，“小燕從春天到秋天占有一個巢”第二章 知識表示方法 2.4 語義網(wǎng)絡表示法682022-6-27語義網(wǎng)絡示例語義網(wǎng)絡示例XIAOYANISAISASWALLOWOWN-1BIRDIS

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

42、示法702022-6-27“合取合取”的語義網(wǎng)絡表示的語義網(wǎng)絡表示例如，表示John gave Mary the book這個事實：JOHNGIVERISAGIVEB23OBJECTMARYG1BOOKISARECIPIENT其中，G1為動作：給人東西；B23為給人的東西GIVER，ISA，OBJECT，RECIPIENT為“合取”第二章 知識表示方法 2.4 語義網(wǎng)絡表示法712022-6-27“析取析取”的語義網(wǎng)絡表示的語義網(wǎng)絡表示采用DIS標注來表示例如，表示：ISA(A,B) PART-OF(B,C)BDISCAISAPARTOF第二章 知識表示方法 2.4 語義網(wǎng)絡表示法722022

43、-6-27“否定否定”的語義網(wǎng)絡表示的語義網(wǎng)絡表示采用 或者NEG標注來表示例如，表示： (ISA(A,B) PART-OF(B,C)BNEGCAISAPARTOFBA ISA第二章 知識表示方法 2.4 語義網(wǎng)絡表示法732022-6-27“蘊涵蘊涵”的語義網(wǎng)絡表示的語義網(wǎng)絡表示l“蘊涵蘊涵”采用ANTE和CONSE標注來表示l例如，Every one who lives at 37 Maple Street is a programmerY是一個特定的地址事件；X是一個變量，表示與此事件有關(guān)的人們O(X,Y)是一個特定的職業(yè)事件，是一個SKOLEM函數(shù)XLOCO(X,Y)PROGRAMME

44、R37-MAPLEPROFESSIONWORKERYADDRESS ISAOCCUPATION ISAPERSONANTECONSE第二章 知識表示方法 2.4 語義網(wǎng)絡表示法742022-6-27“存在量化存在量化”的語義網(wǎng)絡表示的語義網(wǎng)絡表示l“存在量化存在量化”直接用ISA鏈表示l例如， The dog bit the postmanD是一個特定的狗；B是一個特定的咬人事件P是一個特定的郵遞員BPBITEVICTIMDDOG ISAPOSTMAN ISAASSAILANTISA第二章 知識表示方法 2.4 語義網(wǎng)絡表示法752022-6-27“全稱量化全稱量化”的語義網(wǎng)絡表示的語義網(wǎng)絡表

45、示l“全稱量化全稱量化” 用分割方法來表示:把語義網(wǎng)絡分割成空間分層集合，每個空間相應于一個或幾個變量的范圍。一個空間表示一個特定斷言，稱為FORM用代表全稱量詞的特殊鏈，表示全稱量化的變量特殊鏈以及空間分割FORM，一起表示了知識的“全稱量化全稱量化” 例如，Every dog has bitten every postman第二章 知識表示方法 2.4 語義網(wǎng)絡表示法762022-6-27“全稱量化全稱量化”的語義網(wǎng)絡表示例的語義網(wǎng)絡表示例GS是一個概念節(jié)點；表示具有全稱化的一般事件G是GS的的一個實例，是一個斷言BPGGSFORMDDOG ISAPOSTMAN ISAISAISABITE

46、第二章 知識表示方法 2.4 語義網(wǎng)絡表示法772022-6-27語義網(wǎng)絡的推理過程語義網(wǎng)絡的推理過程l語義網(wǎng)絡對所給定的表達結(jié)構(gòu)表示什么語義沒有統(tǒng)一的表示法l語義網(wǎng)絡的推理過程主要有兩種：繼承繼承推理匹配匹配推理l為了方便敘述，將鏈又稱為槽，鏈的尾部節(jié)點稱為值節(jié)點，表示該槽的值第二章 知識表示方法 2.4 語義網(wǎng)絡表示法782022-6-27繼承和匹配繼承和匹配l繼承繼承是把對事物的描寫從概念節(jié)點或類節(jié)點傳遞到實例節(jié)點l繼承繼承分為3種繼承過程：值繼承、“如果需要”繼承和“缺省繼承”l匹配匹配是在概念或類由幾部分組成時，實例的某部分與概念或類的某部分相匹配第二章 知識表示方法 2.4 語義網(wǎng)

47、絡表示法792022-6-27語義網(wǎng)絡推理中的語義網(wǎng)絡推理中的“值繼承值繼承” 雖然Brick12沒有槽Shape，但它是概念Brick的一個實例，因此，根據(jù)繼承關(guān)系知道，它有槽Shape，且其值為Rectangular.BrickRectangularBrick12Wedge18ISAAKOTriangularWedge ISAShapeAKOShapeBLOCK第二章 知識表示方法 2.4 語義網(wǎng)絡表示法802022-6-27語義網(wǎng)絡推理中的語義網(wǎng)絡推理中的“如果需要如果需要”繼承繼承l(wèi)如果不知道槽值，可利用已知信息進行計算得到。這種程序稱為“如果需要”程序。l為了讓槽有多個值，給槽增加“

48、側(cè)面”， “如果需要”程序放在“如果需要側(cè)面”中。l需要計算時，使用類中的程序。如Brick12的Weight槽沒有值，查找類中“如果需要” 程序，有則計算其值BrickBlock-Weight procedureBrick12？4400ISADensity400WeightWeight (if-needed)AKOVolumeBLOCK11第二章 知識表示方法 2.4 語義網(wǎng)絡表示法812022-6-27語義網(wǎng)絡推理中的語義網(wǎng)絡推理中的“缺省缺省”繼承繼承l(wèi)我們有時對假設不是很有把握，就用“可能”表示。對這種值稱為“缺省”值，放在槽的缺省（Default）側(cè)面中。l某個實例要得到“缺省”值，

49、則到類中去繼承。如Brick12沒有顏色的“缺省”值，到類Brick中繼承可得為RedBrickRedBrick12Wedge18ISAAKOBlueWedge ISAAKOColor(Default)BLOCKColor(Default)第二章 知識表示方法 2.4 語義網(wǎng)絡表示法822022-6-27語義網(wǎng)絡推理中的語義網(wǎng)絡推理中的“匹配匹配”過程（一）過程（一）l考察事物由幾部分組成時，繼承過程又是怎樣的呢？l如下圖，toyhouse77是toyhouse的實例，因此，繼承了全部的組成部分，用虛節(jié)點和虛鏈表示。l但如果實例中已確定了某些部分，該如何繼承呢？BrickWedgepartTo

50、y-housepartsupportpartToy-house77partsupport繼承繼承ISA第二章 知識表示方法 2.4 語義網(wǎng)絡表示法832022-6-27語義網(wǎng)絡推理中的語義網(wǎng)絡推理中的“匹配匹配”過程（二）過程（二）l如下圖，Structure35是toyhouse的實例，但它已確定了部分內(nèi)容，這時，將各部件與類中的部件進行匹配，找出對應的關(guān)系及其它要繼承的部分，用虛鏈表示。BrickWedgepartToy-housepartsupportpartStructure35partsupport匹配匹配ISA第二章 知識表示方法 2.4 語義網(wǎng)絡表示法842022-6-27語義網(wǎng)

51、絡的優(yōu)缺點語義網(wǎng)絡的優(yōu)缺點l語義網(wǎng)絡圖的好處是直觀、清晰l缺點是表達范圍有限。如，一旦有十個結(jié)點，而且各結(jié)點之間又有聯(lián)系，則這個網(wǎng)絡就很難辨請了。 第二章 知識表示方法 2.4 語義網(wǎng)絡表示法852022-6-272.5 框架表示法框架表示法第二章 知識表示方法 2.5 框架表示法862022-6-27框架理論框架理論l1975年 Minsky在論文中提出了框架理論。l認為人們在現(xiàn)實世界中對各種事物的認識都是以一種結(jié)構(gòu)化模式存儲在記憶中的l這種結(jié)構(gòu)化的模式在人們的大腦中形成了一種固定的框架l當人們面臨新的情況，就從記憶中找出一個合適的框架，并根據(jù)實際情況對其細節(jié)加以修改補充，從而形成對新觀察到

52、的事物的認識。l如一想到教室，頭腦中就產(chǎn)生一個房間，里面有桌子、椅子、黑板、門、窗等第二章 知識表示方法 2.5 框架表示法872022-6-27框框 架架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ù)元素稱為槽。第二章 知識表示方法 2.5 框架表示法882022-6-27框框 架架 系系 統(tǒng)統(tǒng)l人們常采用以往的經(jīng)驗去認識

53、新事物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 框架表示法892022-6-27框架系統(tǒng)與語義網(wǎng)絡的比較框架系統(tǒng)與語義網(wǎng)絡的比較l框架系統(tǒng)與語義的相同框架系統(tǒng)與語義的相同Minsky把框架系統(tǒng)描述為節(jié)點和關(guān)系的網(wǎng)絡框架系統(tǒng)可以用有向圖來表示l框架和語義網(wǎng)絡的區(qū)別框架和語義網(wǎng)絡

54、的區(qū)別語義網(wǎng)絡本質(zhì)上是一種二維知識表示方法，l網(wǎng)絡中，所有概念被表示為同一個層上的節(jié)點和邊。框架通過允許節(jié)點有結(jié)構(gòu)而增加了第三維信息通過框架更容易層次化的組織知識。l框架可以把對象看成是單一實體，用一個節(jié)點表示，也可以把實體中的某部分單獨拿出來，詳細描述，用另一個節(jié)點表示。第二章 知識表示方法 2.5 框架表示法902022-6-27框架的構(gòu)成框架的構(gòu)成l框架是由若干個結(jié)點和關(guān)系（統(tǒng)稱為槽）構(gòu)成的網(wǎng)絡。是語義網(wǎng)絡的一般化形式的一種結(jié)構(gòu)。同語義網(wǎng)絡沒有本質(zhì)的區(qū)別。l表示形式：由框架名、槽名、側(cè)面、值組成l對于復雜問題，需要使用多個框架，構(gòu)成框架系統(tǒng)l推理方法：沒有固定的推理機理。但和語義網(wǎng)絡一樣遵循匹配和繼承的原理。 第二章 知識表示方法 2.5 框架表示法912022-6-27簡單框架示例簡單框架示例lJOHNIsa: PERSONProfession: PROGRAMMERHeight: 1.8MWeight: 79kg第二章 知識表示方法 2.5 框架表示法922022-6-27立體視圖的框架系統(tǒng)表示立體視圖的框架系統(tǒng)表示E must-be : parallelogramFRAME ISA : Cube REGION : (A,E,B) ABEB must-be : parallelogramA must-be : paral