第二章知识表示方法

第二章知识表示方法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