1、第二章 知識表示方法2.1 狀態空間法2.2 問題歸約法2.3 謂詞邏輯法2.4 語義網絡法2.5 其他方法2.6 小結CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU22.1狀態空間法（State Space Representation）v問題求解技術主要是兩個方面：v問題的表示v求解的方法v狀態空間法v狀態（state）v算符（operator）v狀態空間方法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

2、UCSUCSUCSUCSUCSUCSUCSU32.1.1 問題狀態描述v定義v狀態：描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合。v算符：使問題從一種狀態變化為另一種狀態的手段稱為操作符或算符。v問題的狀態空間：是一個表示該問題全部可能狀態及其關系的圖，它包含三種說明的集合，即三元狀態（S，F，G）。其中所有可能的問題初始狀態集合S、操作符集合F以及目標狀態集合G。2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU42. 狀態空間表示概念詳

3、釋v例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU5例:三數碼難題123123123312312312初始棋局目標棋局2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU6CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC

4、SUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU7CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU8例：例：十五數碼難題v（15 puzzle problem）119415131275861321014123456789101112131415初始狀態初始狀態目標狀態目標狀態CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU9CSU

5、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU10CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU11CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU12v有向圖v路徑v代價v圖的顯示說明v圖的隱示說明2.1.2 狀態圖示法AB2.1 狀態空間法CSUCSUCS

6、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU132.1.3 狀態空間表示舉例v產生式系統（production system）v一個總數據庫：它含有與具體任務有關的信息隨著應用情況的不同，這些數據庫可能簡單，或許復雜。v一套規則：它對數據庫進行操作運算。每條規則由左部鑒別規則的適用性或先決條件以及右部描述規則應用時所完成的動作。v一個控制策略：它確定應該采用哪一條適用規則，而且當數據庫的終止條件滿足時，就停止計算。2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC

7、SUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU14 狀態空間表示舉例狀態空間表示舉例v例：猴子和香蕉問題2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU15解題過程1v用四元 表列（W,x,Y,z）來表示這個問題的狀態v其中，vW猴子的水平位置vx當猴子在箱子頂上時取x=1；否則取x=0vY箱子的水平位置vz當猴子摘到香蕉時取z=1；否則取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU

8、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU16解題過程2v這個問題的操作（算符）如下：v2 goto（U）表示猴子走到水平位置Uv或者用產生式規則表示為（W，0，Y，z） goto（U） （U，0，Y，z）2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU17vpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbox（V） （V，0，V，z）vclimbbox猴子爬上箱頂，即有（W，0

9、，W，z） climbbox （W，1，W，z）2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU18vgrasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1） v該初始狀態變換為目標狀態的操作序列為goto(b),pushbox(c),climbbox,grasp2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU1

10、9(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目標狀態目標狀態goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉問題的狀態空間圖猴子和香蕉問題的狀態空間圖goto（U）U=V2.1 狀態空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU202.2 問題歸約法（Problem Reduction Representation）子問題子問題1子問題子

11、問題n原始問題原始問題子問題集本本原原問問題題CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU21v 問題歸約表示的組成部分：v一個初始問題描述；v一套把問題變換為子問題的操作符；v一套本原問題描述。v問題歸約的實質：v從目標(要解決的問題)出發逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。2.2 問題規約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC

12、SUCSUCSUCSUCSU222.2.1 問題歸約描述 （Problem Reduction Description）v梵塔難題123CBA2.2 問題規約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU23v梵塔難題2.2.1 問題歸約描述(a) 初始狀態(b) 目標狀態CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU24問題規約v原始問題歸約（簡化）為三個子問題

13、1、移動A，B盤至柱子2的雙圓盤難題2、移動圓盤C至柱子3的單圓盤問題3、移動A，B盤至柱子3的雙圓盤難題CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU25v歸約過程CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU26解題過程（3個圓盤問題）1231231231231231231231232.2 問題規約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC

14、SUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU27梵塔問題歸約圖（113） （123） （111） （113） （123） （122） （111） （333） （122） （322） （111） （122） （322） （333） （321） （331） （322） （321） （331） （333） 2.2 問題規約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU28多圓盤梵塔難題演示2.2 問題規約法CSUCSUCSUCS

15、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU292.2.2與或圖表示v1.與圖、或圖、與或圖2.2 問題規約法ABCD與圖ABC或圖CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU302.2 問題規約法BCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

16、UCSU312.一些關于與或圖的術語2.2 問題規約法HMBCDEFGAN父節點與節點弧線或節點子節點終葉節點 終葉節點：對應于原問題的本原節點。終葉節點：對應于原問題的本原節點。或節點：只要解決某個問題就可解決其父輩問題的節點集合，如（或節點：只要解決某個問題就可解決其父輩問題的節點集合，如（M，N，H）。）。與節點：只有解決所有子問題，才能解決其父輩問題的節點集合，如（與節點：只有解決所有子問題，才能解決其父輩問題的節點集合，如（B,C)和和 （D,E,F）各個結點之間用一端小圓弧連接標記）各個結點之間用一端小圓弧連接標記 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU

17、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU323.定義2.2 問題規約法與或圖例子與或圖例子ttttttttt（a）（b）有解節點無解節點終葉節點CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU33v不可解節點的一般定義v沒有后裔的非終葉節點為不可解節點。v全部后裔為不可解的非終葉節點且含有或后繼節點，此非終葉節點才是不可解的。v后裔至少有一個為不可解的非終葉節點且含有與后繼節點，此非終葉節點才是不可解的。v與或圖構成規則2.2

18、 問題規約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU34v梵塔問題歸約圖（與或圖與或圖）CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU352.3 謂詞邏輯法v邏輯語句v形式語言2.3.1 謂詞演算v 1. 語法和語義v基本符號v謂詞符號、變量符號、函數符號、 常量符號、括號和逗號v原子公式CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU

19、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU362.3 謂詞邏輯法1原子公式(atomic formulas)由若干謂詞符號和項組成的謂詞演算。原子公式是謂詞演算基本積木塊。機器人(ROBOT)在號房間(r1)內的原子公式： CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU372.3 謂詞邏輯法2“李的母親和他的父親結婚”這句話的原子公式表示如下： CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

20、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU38v連詞和量詞(Connective &Quantifiers)v連詞v與及合取（conjunction)v或及析取（disjunction）v蘊涵（Implication）v非（Not）v量詞v全稱量詞（Universal Quantifiers)v存在量詞 (Existential Quantifiers)2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU392.3 謂詞邏輯法(1)(1

21、)連詞連詞與與合取（合取（conjunctionconjunction）: :合取就是用連詞合取就是用連詞把幾個把幾個 公式連接起來而構成的公式。公式連接起來而構成的公式。(我喜愛音樂和繪畫。)LIKE(I，MUSIC)LIKE(I，PAINTING) (我喜愛音樂和繪畫。) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU40或析取（disjunction）:析取就是用連詞把幾個公式 連接起來而構成的公式。 PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOO

22、TBALL)(李力打籃球或踢足球。)(李力打籃球或踢足球。) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU41蘊涵蘊涵=表示表示如果如果-那么那么的語句的語句 RUNS(LIUHUA，FASTEST) WINS(LIUHUA，CHAMPION) (如果劉華跑得最快，那么他取得冠軍) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU42非（非（NOT） 表示否定，表示

23、否定，、均可表示。INROOM(ROBOT，r2) (機器人不在2號房間內。) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU43(2) 量詞量詞 全稱量詞全稱量詞(Universal Quantifier)若一個原子公式若一個原子公式P(x)，對于所有可能變量對于所有可能變量x都具有都具有T值，則用值，則用( x)P(x)表示。(所有的機器人都是灰色的）( x)Student(x) = Uniform(x,Color) (所有學生都穿彩色制服)( x)ROBOT(x) = CO

24、LOR(x,GRAY) (所有的機器人都是灰色的） ( x)Student(x) = Uniform(x,Color) (所有學生都穿彩色制服) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU44存在量詞存在量詞(Existential Quantifier)若一個原子公式P(x)，至少有一個變元X，可使P(X)為T值，則用( x)P(x)表示。 ( x)INROOM(x,r1) (1號房間內有個物體) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

25、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU452.3.2 謂詞公式v原子公式的的定義：v用P(x1，x2，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,，xn為客體變量或變元。通常把P(x1,x2,xn)叫做謂詞演算的原子公式，或原子謂詞公式。v分子謂詞公式v可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU46v合適公式（WFF，well-fo

26、rmed formulas）v合適公式的遞歸定義v合適公式的性質v合適公式的真值v等價（Equivalence)2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU47合適公式的真值：CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU482.3.3 置換與合一v置換v概念v假元推理v全稱化推理v綜合推理v定義v就是在該表達式中用置換項置換變量v性質v可結合的

27、v不可交換的2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU49一個重要的推理規則是假元推理，這就是由合適公式W1和W1=W2產生合適公式W2的運算。另一個推理規則叫做全稱化推理，它是由合適公式( x)W(x)產生合適公式W(A)，其中A為任意常量符號。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU50s1=z/x,w/y s2=A/y s3=q(z

28、)/x,A/y s4=c/x,A/y Px,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),B Px,f(y),Bs3=Pq(z),f(A),B Px,f(y),Bs4=Pc,f(A),B2) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU51v合一（Unification)v合一：尋找項對變量的置換，以使兩表達式一致。v可合一：如果一個置換s作用于表達式集Ei的每個元素，則我們用Ei s來表示置換例的集。我們稱表達式集Ei是可合一的。2.3 謂詞邏輯

29、法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU52Px,f(y),B, Px,f(B),B 的合一式為S=A/x, B/y最簡單合一：g=B/yCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU532.4 語義網絡法 （Semantic Network Representation）v語義網絡的結構v定義v組成部分v詞法v結構v過程v語義CSUCSUCSUCSUCSU

30、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU54v表示占有關系和其它情況v例： 小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個。v選擇語義基元v試圖用一組基元來表示知識，以便簡化表示，并可用簡單的知識來表示更復雜的知識。2.4 語義網絡法2.4. 1 二元語義網絡的表示CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU552.4.1 二元語義網絡的表示ComputerMicro-C

31、omputerHard DiscMornitorCPURAMPC/XTMy-ComputerMePersonIS-PART-OFIS-PART-OFIS-PART-OFIS-PART-OFISAISAISAOWNERISA網絡表示網絡表示CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU562.4.2 多元語義網絡的表示v謂詞邏輯與語義網絡等效LIMINGMANISAISA（LIMING，MAN）或）或 MAN（LIMING）（語義網絡）（語義網絡）（謂詞邏輯）（謂詞邏輯）2.4 語

32、義網絡法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU57v多元語義網絡表示的實質v把多元關系轉化為一組二元關系的組合，或二元關系的合取。R(XR(X1 1，X X2 2，X Xn n) )R R1212(X(X1 1，X X2 2)R)R1313(X(X1 1，X X3 3) R R1n1n(X(X1 1，X Xn n) ). R Rn-1 nn-1 n(X(Xn-1n-1，X Xn n) )可轉換為可轉換為2.4 語義網絡法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU582.4.3 連接詞和量化的表示v合取v三元變為二元組合v析取v加注析取界限，并標記DIS，以免引起混淆。v否定v兩種表示方式：或標注NEG界限。2.4 語義網絡法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU59v蘊涵v在語義網絡中可用標注ANTE和CONSE界限來表示蘊涵關系。AN