第二章知识表示方法

1、第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结CSUCSUCSUCSUCSUCSUCSUCSUCSU22.1状态空间法（State Space Representation）v问题求解技术主要是两个方面：v问题的表示v求解的方法v状态空间法v状态（state）v算符（operator）v状态空间方法CSUCSUCSUCSUCSUCSUCSUCSUCSU32.1.1 问题状态描述v定义v状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。v算符：使问题从一种状态变化为另一种状态的手段称为操作符或算

2、符。v问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。其中所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU42. 状态空间表示概念详释v例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU5例:三数码难题123123123312312312初始棋局目标棋局2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU6CSUCSUC

3、SUCSUCSUCSUCSUCSUCSU7CSUCSUCSUCSUCSUCSUCSUCSUCSU8例：例：十五数码难题v（15 puzzle problem）119415131275861321014123456789101112131415初始状态初始状态目标状态目标状态CSUCSUCSUCSUCSUCSUCSUCSUCSU9CSUCSUCSUCSUCSUCSUCSUCSUCSU10CSUCSUCSUCSUCSUCSUCSUCSUCSU11CSUCSUCSUCSUCSUCSUCSUCSUCSU12v有向图v路径v代价v图的显示说明v图的隐示说明2.1.2 状态图示法AB2.1 状态空间法CS

4、UCSUCSUCSUCSUCSUCSUCSUCSU132.1.3 状态空间表示举例v产生式系统（production system）v一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。v一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。v一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU14 状态空间表示举例状态空间表示举例v例：猴子和香蕉问题2.1 状态空间法CSUCSUCSUCSUCS

5、UCSUCSUCSUCSU15解题过程1v用四元 表列（W,x,Y,z）来表示这个问题的状态v其中，vW猴子的水平位置vx当猴子在箱子顶上时取x=1；否则取x=0vY箱子的水平位置vz当猴子摘到香蕉时取z=1；否则取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSU16解题过程2v这个问题的操作（算符）如下：v2 goto（U）表示猴子走到水平位置Uv或者用产生式规则表示为（W，0，Y，z） goto（U） （U，0，Y，z）2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU17vpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbo

6、x（V） （V，0，V，z）vclimbbox猴子爬上箱顶，即有（W，0，W，z） climbbox （W，1，W，z）2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU18vgrasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1） v该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU19(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）目标状态目标状态

7、goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU202.2 问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题CSUCSUCSUCSUCSUCSUCSUCSUCSU21v 问题归约表示的组成部分：v一个初始问题描述；v一套把问题变换为子问题的操作符；v一套本原问题描述。v问题归约的实质：v从目标(要解决的问题)出发

8、逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU222.2.1 问题归约描述 （Problem Reduction Description）v梵塔难题123CBA2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU23v梵塔难题2.2.1 问题归约描述(a) 初始状态(b) 目标状态CSUCSUCSUCSUCSUCSUCSUCSUCSU24问题规约v原始问题归约（简化）为三个子问题1、移动A，B盘至柱子2的双圆盘难题2、移动圆盘C至柱子3的单圆盘问题3、移动A，B

9、盘至柱子3的双圆盘难题CSUCSUCSUCSUCSUCSUCSUCSUCSU25v归约过程CSUCSUCSUCSUCSUCSUCSUCSUCSU26解题过程（3个圆盘问题）1231231231231231231231232.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU27梵塔问题归约图（113） （123） （111） （113） （123） （122） （111） （333） （122） （322） （111） （122） （322） （333） （321） （331） （322） （321） （331） （333） 2.2 问题规约法CSUCSUCSUCSUCSUC

10、SUCSUCSUCSU28多圆盘梵塔难题演示2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU292.2.2与或图表示v1.与图、或图、与或图2.2 问题规约法ABCD与图ABC或图CSUCSUCSUCSUCSUCSUCSUCSUCSU302.2 问题规约法BCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSU312.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点 终叶节点：对应于原问题的本原节点。终叶节点：对应于原问题的本原节点。或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（或

11、节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。）。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和和 （D,E,F）各个结点之间用一端小圆弧连接标记）各个结点之间用一端小圆弧连接标记 CSUCSUCSUCSUCSUCSUCSUCSUCSU323.定义2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点CSUCSUCSUCSUCSUCSUCSUCSUCSU33v不可解节点的一般定义v没有后裔的非终叶节点为不可解节点。v全部后裔为不可解的非终叶节点且

12、含有或后继节点，此非终叶节点才是不可解的。v后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。v与或图构成规则2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU34v梵塔问题归约图（与或图与或图）CSUCSUCSUCSUCSUCSUCSUCSUCSU352.3 谓词逻辑法v逻辑语句v形式语言2.3.1 谓词演算v 1. 语法和语义v基本符号v谓词符号、变量符号、函数符号、 常量符号、括号和逗号v原子公式CSUCSUCSUCSUCSUCSUCSUCSUCSU362.3 谓词逻辑法1原子公式(atomic formulas)由若干谓词符号和项组成的

13、谓词演算。原子公式是谓词演算基本积木块。机器人(ROBOT)在号房间(r1)内的原子公式： CSUCSUCSUCSUCSUCSUCSUCSUCSU372.3 谓词逻辑法2“李的母亲和他的父亲结婚”这句话的原子公式表示如下： CSUCSUCSUCSUCSUCSUCSUCSUCSU38v连词和量词(Connective &Quantifiers)v连词v与及合取（conjunction)v或及析取（disjunction）v蕴涵（Implication）v非（Not）v量词v全称量词（Universal Quantifiers)v存在量词 (Existential Quantifiers)2.3

14、谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU392.3 谓词逻辑法连词连词与与合取（合取（conjunctionconjunction）: :合取就是用连词合取就是用连词把几个把几个 公式连接起来而构成的公式。公式连接起来而构成的公式。(我喜爱音乐和绘画。)LIKE(I，MUSIC)LIKE(I，PAINTING) (我喜爱音乐和绘画。) CSUCSUCSUCSUCSUCSUCSUCSUCSU40或析取（disjunction）:析取就是用连词把几个公式 连接起来而构成的公式。 PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL)(李力打篮球

15、或踢足球。)(李力打篮球或踢足球。) CSUCSUCSUCSUCSUCSUCSUCSUCSU41蕴涵蕴涵=表示表示如果如果-那么那么的语句的语句 RUNS(LIUHUA，FASTEST) WINS(LIUHUA，CHAMPION) (如果刘华跑得最快，那么他取得冠军) CSUCSUCSUCSUCSUCSUCSUCSUCSU42非（非（NOT） 表示否定，表示否定，、均可表示。INROOM(ROBOT，r2) (机器人不在2号房间内。) CSUCSUCSUCSUCSUCSUCSUCSUCSU43(2) 量词量词 全称量词全称量词(Universal Quantifier)若一个原子公式若一个原子

16、公式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) (所有学生都穿彩色制服) CSUCSUCSUCSUCSUCSUCSUCSUCSU44存在量词存在量词(Existential Quantifier)若一个原子公式P(x)，至少有一个变元X，可使P(X)为T值，则用( x)P(x

17、)表示。 ( x)INROOM(x,r1) (1号房间内有个物体) CSUCSUCSUCSUCSUCSUCSUCSUCSU452.3.2 谓词公式v原子公式的的定义：v用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。v分子谓词公式v可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU46v合适公式（WFF，well-formed formulas）v合适公式的递归定义v合适公式的性质v合适公

18、式的真值v等价（Equivalence)2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU47合适公式的真值：CSUCSUCSUCSUCSUCSUCSUCSUCSU482.3.3 置换与合一v置换v概念v假元推理v全称化推理v综合推理v定义v就是在该表达式中用置换项置换变量v性质v可结合的v不可交换的2.3 谓词逻辑法CSUCSUCSUCSUCSUCSUCSUCSUCSU49一个重要的推理规则是假元推理，这就是由合适公式W1和W1=W2产生合适公式W2的运算。另一个推理规则叫做全称化推理，它是由合适公式( x)W(x)产生合适公式W(A)，其中A为任意常量符号。CSUCS

19、UCSUCSUCSUCSUCSUCSUCSU50s1=z/x,w/y s2=A/y s3=q(z)/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) CSUCSUCSUCSUCSUCSUCSUCSUCSU51v合一（Unification)v合一：寻找项对变量的置换，以使两表达式一致。v可合一：如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。2.3 谓词逻辑法CSUCS

20、UCSUCSUCSUCSUCSUCSUCSU52Px,f(y),B, Px,f(B),B 的合一式为S=A/x, B/y最简单合一：g=B/yCSUCSUCSUCSUCSUCSUCSUCSUCSU532.4 语义网络法 （Semantic Network Representation）v语义网络的结构v定义v组成部分v词法v结构v过程v语义CSUCSUCSUCSUCSUCSUCSUCSUCSU54v表示占有关系和其它情况v例： 小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。v选择语义基元v试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。2.4 语义

21、网络法2.4. 1 二元语义网络的表示CSUCSUCSUCSUCSUCSUCSUCSUCSU552.4.1 二元语义网络的表示ComputerMicro-ComputerHard DiscMornitorCPURAMPC/XTMy-ComputerMePersonIS-PART-OFIS-PART-OFIS-PART-OFIS-PART-OFISAISAISAOWNERISA网络表示网络表示CSUCSUCSUCSUCSUCSUCSUCSUCSU562.4.2 多元语义网络的表示v谓词逻辑与语义网络等效LIMINGMANISAISA（LIMING，MAN）或）或 MAN（LIMING）（语义网络

22、）（语义网络）（谓词逻辑）（谓词逻辑）2.4 语义网络法CSUCSUCSUCSUCSUCSUCSUCSUCSU57v多元语义网络表示的实质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 语义网络法CSUCSUCSUCSUCSUCSUCSUCSUCSU582.4.3 连接词和量化的表示v合取v三元变为二元组合v析取v加注析取界限，并标记DIS，以免引起混淆。v否定v两种表示方式：或标注NEG界限。2.4 语义网络法CSUCSUCSUCSUCSUCSUCSUCSUCSU59v蕴涵v在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。ANTE和CONSE界限分别用来把与先决条件(antecedent)及与结果(consequence)相关的链联系在一起。v量化v存在量化ISA链