第二章知識表示方法2.1狀態空間法2.2問題歸約法2.3謂詞邏輯法2.4語義網絡法2.5其他方法2.6小結22.1狀態空間法

（StateSpaceRepresentation）問題求解技術主要是兩個方面：問題的表示求解的方法狀態空間法狀態（state）算符（operator）狀態空間方法32.1.1

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

狀態空間表示概念詳釋例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState2.1狀態空間法5例:三數碼難題

123123123312312312初始棋局目標棋局2.1狀態空間法678例：十五數碼難題（15puzzleproblem）初始狀態目標狀態9101112有向圖路徑代價圖的顯示說明圖的隱示說明2.1.2狀態圖示法AB2.1狀態空間法132.1.3狀態空間表示舉例產生式系統（productionsystem）一個總數據庫：它含有與具體任務有關的信息隨著應用情況的不同，這些數據庫可能簡單，或許復雜。一套規則：它對數據庫進行操作運算。每條規則由左部鑒別規則的適用性或先決條件以及右部描述規則應用時所完成的動作。一個控制策略：它確定應該采用哪一條適用規則，而且當數據庫的終止條件滿足時，就停止計算。2.1狀態空間法14

狀態空間表示舉例例：猴子和香蕉問題2.1狀態空間法15解題過程1用四元表列（W,x,Y,z）來表示這個問題的狀態其中，

W－猴子的水平位置

x－當猴子在箱子頂上時取x=1；否則取x=0

Y－箱子的水平位置

z－當猴子摘到香蕉時取z=1；否則取z=016解題過程2這個問題的操作（算符）如下：2goto（U）表示猴子走到水平位置U或者用產生式規則表示為 （W，0，Y，z）goto（U）（U，0，Y，z）2.1狀態空間法17pushbox（V）猴子把箱子推到水平位置V，即有

（W，0，W，z）pushbox（V）（V，0，V，z）climbbox猴子爬上箱頂，即有

（W，0，W，z）climbbox（W，1，W，z）2.1狀態空間法18grasp猴子摘到香蕉，即有

（c，1，c，0）grasp（c，1，c，1）

該初始狀態變換為目標狀態的操作序列為

{goto(b),pushbox(c),climbbox,grasp}2.1狀態空間法19(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狀態空間法202.2問題歸約法

（ProblemReductionRepresentation）子問題1子問題n原始問題子問題集本原問題21

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

（ProblemReductionDescription）梵塔難題123CBA2.2問題規約法23梵塔難題2.2.1問題歸約描述(a)初始狀態(b)目標狀態24問題規約原始問題歸約（簡化）為三個子問題

1、移動A，B盤至柱子2的雙圓盤難題

2、移動圓盤C至柱子3的單圓盤問題

3、移動A，B盤至柱子3的雙圓盤難題25歸約過程26解題過程（3個圓盤問題）1231231231231231231231232.2問題規約法27梵塔問題歸約圖（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

2.2問題規約法28多圓盤梵塔難題演示2.2問題規約法292.2.2與或圖表示1.與圖、或圖、與或圖2.2問題規約法ABCD與圖ABC或圖302.2問題規約法BCDEFGAHMBCDEFGAN312.一些關于與或圖的術語2.2問題規約法HMBCDEFGAN父節點與節點弧線或節點子節點終葉節點

終葉節點：對應于原問題的本原節點。

或節點：只要解決某個問題就可解決其父輩問題的節點集合，如（M，N，H）。

與節點：只有解決所有子問題，才能解決其父輩問題的節點集合，如（B,C)和（D,E,F）各個結點之間用一端小圓弧連接標記323.定義2.2問題規約法與或圖例子ttttttttt（a）（b）有解節點無解節點終葉節點33不可解節點的一般定義沒有后裔的非終葉節點為不可解節點。全部后裔為不可解的非終葉節點且含有或后繼節點，此非終葉節點才是不可解的。后裔至少有一個為不可解的非終葉節點且含有與后繼節點，此非終葉節點才是不可解的。與或圖構成規則2.2問題規約法34梵塔問題歸約圖（與或圖）352.3謂詞邏輯法邏輯語句形式語言2.3.1謂詞演算

1.語法和語義基本符號謂詞符號、變量符號、函數符號、常量符號、括號和逗號原子公式362.3謂詞邏輯法1原子公式(atomicformulas)由若干謂詞符號和項組成的謂詞演算。原子公式是謂詞演算基本積木塊。

機器人(ROBOT)在１號房間(r1)內的原子公式：

372.3謂詞邏輯法2“李的母親和他的父親結婚”這句話的原子公式表示如下：

38連詞和量詞(Connective&Quantifiers)連詞與及合取（conjunction)或及析取（disjunction）蘊涵（Implication）非（Not）量詞全稱量詞（UniversalQuantifiers)存在量詞

(ExistentialQuantifiers)2.3謂詞邏輯法392.3謂詞邏輯法連詞

與·合取（conjunction）:合取就是用連詞∧把幾個公式連接起來而構成的公式。(我喜愛音樂和繪畫。)LIKE(I，MUSIC)∧LIKE(I，PAINTING)

(我喜愛音樂和繪畫。)

40或·析取（disjunction）:析取就是用連詞∨把幾個公式連接起來而構成的公式。

PLAYS(LILI，BASKETBALL)∨PLAYS(LILI，FOOTBALL)(李力打籃球或踢足球。)(李力打籃球或踢足球。)

41蘊涵"=>"表示"如果-那么"的語句RUNS(LIUHUA，FASTEST)WINS(LIUHUA，CHAMPION)

(如果劉華跑得最快，那么他取得冠軍)

42非（NOT）表示否定，～、┑均可表示。

～INROOM(ROBOT，r2)

(機器人不在2號房間內。)

43(2)量詞

全稱量詞(UniversalQuantifier)若一個原子公式P(x)，對于所有可能變量x都具有T值，則用(

x)P(x)表示。

(所有的機器人都是灰色的）(

x)[Student(x)=>Uniform(x,Color)](所有學生都穿彩色制服)(

x)[ROBOT(x)=>COLOR(x,GRAY)](所有的機器人都是灰色的）

(

x)[Student(x)=>Uniform(x,Color)](所有學生都穿彩色制服)

44存在量詞(ExistentialQuantifier)

若一個原子公式P(x)，至少有一個變元X，可使P(X)為T值，則用(

x)P(x)表示。(

x)INROOM(x,r1)(1號房間內有個物體)

452.3.2謂詞公式原子公式的的定義：用P(x1，x2，…，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,…，xn為客體變量或變元。通常把P(x1,x2,…,xn)叫做謂詞演算的原子公式，或原子謂詞公式。分子謂詞公式可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。2.3謂詞邏輯法46合適公式（WFF，well-formedformulas）合適公式的遞歸定義合適公式的性質合適公式的真值等價（Equivalence)2.3謂詞邏輯法47合適公式的真值：

482.3.3置換與合一置換概念假元推理全稱化推理綜合推理定義就是在該表達式中用置換項置換變量性質可結合的不可交換的2.3謂詞邏輯法49一個重要的推理規則是假元推理，這就是由合適公式W1和W1=>W2產生合適公式W2的運算。另一個推理規則叫做全稱化推理，它是由合適公式(

x)W(x)產生合適公式W(A)，其中A為任意常量符號。

50s1={z/x,w/y}

s2={A/y}s3={q(z)/x,A/y}s4={c/x,A/y}P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]

P[x,f(y),B]s3=P[q(z),f(A),B]

P[x,f(y),B]s4=P[c,f(A),B]2)

51合一（Unification)合一：尋找項對變量的置換，以使兩表達式一致。可合一：如果一個置換s作用于表達式集{Ei}的每個元素，則我們用{Ei}s來表示置換例的集。我們稱表達式集{Ei}是可合一的。2.3謂詞邏輯法52P[x,f(y),B],P[x,f(B),B]的合一式為S={A/x,B/y}最簡單合一：g={B/y}532.4語義網絡法

（SemanticNetworkRepresentation）語義網絡的結構定義組成部分詞法結構過程語義54表示占有關系和其它情況例：小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個。選擇語義基元試圖用一組基元來表示知識，以便簡化表示，并可用簡單的知識來表示更復雜的知識。2.4語義網絡法2.4.1二元語義網絡的表示552.4.1二元語義網絡的表示網絡表示562.4.2多元語義網絡的表示謂詞邏輯與語義網絡等效LIMINGMANISAISA（LIMING，MAN）或MAN（LIMING）（語義網絡）（謂詞邏輯）2.4語義網絡法57多元語義網絡表示的實質把多元關系轉化為一組二元關系的組合，或二元關系的合取。R(X1，X2，…，Xn)R12(X1，X2)∧R13(X1，X3)∧…∧R1n(X1，Xn)......Rn-1n(Xn-1，Xn)可轉換為2.4語義網絡法582.4.3連接詞和量化的表示合取三元變為二元組合析取加注析取界限，并標記DIS，以免引起混淆。否定兩種表示方式：～或標注NEG界限。2.4語義網絡法59蘊涵在語義網絡中可用標注ANTE和CONSE界限來表示蘊涵關系。ANTE和CONSE界限分別用來把與先決條件(antec