第二章 知识表示方法
2.1 状态空间法
2.2 问题归约法
2.3 谓词逻辑法
2.4 语义网络法
2.5 其他方法
2.6 小结
2
2.1状态空间法
（ State Space Representation）
?问题求解技术主要是两个方面：
?问题的表示
?求解的方法
?状态空间法
?状态 （ state）
?算符 （ operator）
?状态空间方法
3
2.1.1 问题状态描述
?定义
?状态,描述某类不同事物间的差别而引入的
一组最少变量 q0,q1,…,qn的有序集合。
?算符,使问题从一种状态变化为另一种状态
的手段称为操作符或算符。
?问题的状态空间,是一个表示该问题全部可
能状态及其关系的图，它包含三种说明的集
合，即三元状态 （ S,F,G） 。
2.1 状态空间法
4
2,状态空间表示概念详释
?例如下棋、迷宫及各种游戏。
Original
State
Middle
State
Goal
State
2.1 状态空间法
5
例,三数码难题
（ 3 puzzle problem）
12
3
1
2 3
1
2 3
31
2
31
2
3
1 2
初始棋局 目标棋局
2.1 状态空间法
6
?有向图
?路径
?代价
?图的显示说明
?图的隐示说明
2.1.2 状态图示法
A B
2.1 状态空间法
7
2.1.3 状态空间表示举例
?产生式系统 （ production system）
?一个总数据库,它含有与具体任务有关的信息随着应
用情况的不同，这些数据库可能简单，或许复杂 。
?一套规则,它对数据库进行操作运算。每条规则由左部
鉴别规则的适用性或先决条件以及右部描述规则应用时
所完成的动作。
?一个控制策略,它确定应该采用哪一条适用规则，而
且当数据库的终止条件满足时，就停止计算。
2.1 状态空间法
8
状态空间表示举例
?例：猴子和香蕉问题
2.1 状态空间法
9
解题过程
? 用一个四元表列 （ W,x,Y,z） 来表示
这个问题状态,
?这个问题的操作（算符）如下：
?2 goto（ U）表示猴子走到水平位臵 U
?或者用产生式规则表示为
（ W,0,Y,z） goto（ U） （ U,0,Y,z）
2.1 状态空间法
10
?pushbox（ V） 猴子把箱子推到水平位臵 V，
即有
（ W,0,W,z） pushbox（ V） （ V,0,V,z）
?climbbox猴子爬上箱顶，即有
（ W,0,W,z） climbbox （ W,1,W,z）
2.1 状态空间法
11
?grasp猴子摘到香蕉，即有
（ c,1,c,0） grasp （ c,1,c,1）
?该初始状态变换为目标状态的操作序列为
{goto(b),pushbox(c),climbbox,grasp}
2.1 状态空间法
12
(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,climbbox
goto（ U）
U=bpushbox（ V）
猴子和香蕉问题的状态空间图
goto（ U）
U=V
2.1 状态空间法
13
猴子和香蕉问题自动演示：
?
猴子
香蕉
箱子
猴子
香蕉
箱子
?
Ha!Ha!
2.1 状态空间法
14
2.2 问题归约法
（ Problem Reduction Representation）
子问题 1
子问题 n
原始问题 子问题集
本
原
问
题
15
? 问题归约表示的组成部分：
?一个初始问题描述；
?一套把问题变换为子问题的操作符；
?一套本原问题描述。
?问题归约的实质：
?从目标 (要解决的问题 )出发逆向推理，建立子问
题以及子问题的子问题，直至最后把初始问题归
约为一个平凡的本原问题集合。
2.2 问题规约法
16
2.2.1 问题归约描述
（ Problem Reduction Description）
? 梵塔难题
1 2 3
CB
A
2.2 问题规约法
17
解题过程（ 3个圆盘问题）
1 2 3
1 2 3 1 2 3
1 2 3
1 2 3 1 2 3
1 2 3
1 2 3
2.2 问题规约法
18
多圆盘梵塔难题演示
2.2 问题规约法
19
2.2.2与或图表示
?1.与图、或图、与或图
2.2 问题规约法
A
B C D
与图
A
B C
或图
20
2.2 问题规约法
B C
D E F
G
A
HM
B C
D E F G
A
N
21
2.一些关于与或图的术语
2.2 问题规约法
HM
B C
D E F G
A
N
父节
点
与节
点
弧线
或节
点 子节
点
终叶节
点
22
3.定义
2.2 问题规约法
与或图例子
t
t
t
t
t
t
t
t
t（ a） （ b）
有解节点
无解节点 终叶节点
23
?不可解节点的一般定义
?没有后裔的非终叶节点为不可解节点。
?全部后裔为不可解的非终叶节点且含有或后
继节点，此非终叶节点才是不可解的。
?后裔至少有一个为不可解的非终叶节点且含
有与后继节点，此非终叶节点才是不可解的。
?与或图构成规则
2.2 问题规约法
24
梵塔问题归约图
（ 113） （ 123）?（ 111） （ 113）? （ 123） （ 122）?
（ 111） （ 333）?
（ 122） （ 322）?（ 111） （ 122）? （ 322） （ 333）?
（ 321） （ 331）?（ 322） （ 321）? （ 331） （ 333）?
2.2 问题规约法
25
2.3 谓词逻辑法
?逻辑语句
?形式语言
2.3.1 谓词演算
? 1,语法和语义
?基本符号
?谓词符号、变量符号、函数符号,常量
符号、括号和逗号
?原子公式
26
?连词和量词 (Connective &Quantifiers)
?连词
?与及合取 （ conjunction)
?或及析取 （ disjunction）
?蕴涵 （ Implication）
?非 （ Not）
?量词
?全称量词 （ Universal Quantifiers)
?存在量词 (Existential Quantifiers)
2.3 谓词逻辑法
27
2.3.2 谓词公式
?原子公式的的定义：
?用 P(x1,x2,…, xn)表示一个 n元谓词公式，
其中 P为 n元谓词,x1,x2,…, xn为客体变量或
变元。通常把 P(x1,x2,…,x n)叫做谓词演算的
原子公式，或原子谓词公式。
?分子谓词公式
?可以用连词把原子谓词公式组成复合谓词公
式，并把它叫做分子谓词公式。
2.3 谓词逻辑法
28
?合适公式 （ WFF,well-formed formulas）
?合适公式的递归定义
?合适公式的性质
?合适公式的真值
?等价（ Equivalence)
2.3 谓词逻辑法
29
2.3.3 臵换与合一
?臵换
?概念
?假元推理
?全称化推理
?综合推理
?定义
?就是在该表达式中用臵换项臵换变量
?性质
?可结合的
?不可交换的
2.3 谓词逻辑法
30
?合一（ Unification)
?合一：寻找项对变量的臵换，以使两表
达式一致。
?可合一：如果一个臵换 s作用于表达式集
{Ei}的每个元素，则我们用 {Ei} s来表示
臵换例的集。我们称表达式集 {Ei}是可合
一的。
2.3 谓词逻辑法
31
2.4 语义网络法
（ Semantic Network Representation）
?语义网络的结构
?定义
?组成部分
?词法
?结构
?过程
?语义
32
?表示占有关系和其它情况
?例,小燕是一只燕子，燕子是鸟；巢 -1是
小燕的巢，巢 -1是巢中的一个。
?选择语义基元
?试图用一组基元来表示知识，以便简化
表示，并可用简单的知识来表示更复杂
的知识。
2.4 语义网络法
2.4,1 二元语义网络的表示
33
2.4.2 多元语义网络的表示
?谓词逻辑与语义网络等效
LIMING MAN
ISA
ISA（ LIMING,MAN）或 MAN（ LIMING）
（语义网络）
（谓词逻辑）
2.4 语义网络法
34
?多元语义网络表示的实质
?把多元关系转化为一组二元关系的组合，或
二元关系的合取。
R(X1,X2,…,Xn)
R12(X1,X2)∧R 13(X1,X3)∧ …∧ R 1n(X1,Xn)
......
Rn-1 n(Xn-1,Xn)
可转换为
2.4 语义网络法
35
2.4.3 连接词和量化的表示
?合取
?三元变为二元组合
?析取
?加注析取界限，并标记 DIS，以免引起混淆。
?否定
?两种表示方式：～或标注 NEG界限。
2.4 语义网络法
36
?蕴涵
?在语义网络中可用标注 ANTE和 CONSE界限
来表示蕴涵关系。 ANTE和 CONSE界限分别
用来把与先决条件 (antecedent)及与结果
(consequence)相关的链联系在一起。
?量化
?存在量化 — ISA链
?全称量化 — 分割法
2.4 语义网络法
37
2.5其他方法（ Others)
?框架（ Frame）表示
?框架是一种结构化表示法，通常采用语义网络
中的节点 -槽 -值表示结构。
?剧本（ Script）表示
?剧本是框架的一种特殊形式，它用一组槽来描
述某些事件的发生序列。
?过程（ Procedure）表示
?过程式表示就是将有关某一问题领 域的知识，
连同如何使用这些知识的方法，均隐式地表达
为一个求解问题的过程。
38
2.6 小结（ Summary）
?本章所讨论的 知识表示问题 是人工智
能研究的核心问题之一。知识表示方
法很多，本章介绍了其中的 7种，有 图
示法 和 公式法, 陈述式表示 和 过程式
表示 等。
39
方法 初始问题 算符 目标 结果
状态
空间法
归约法
谓词
逻辑法
语义
网络法
状态
结点
合适公式
结点
算符
弧
子句集
（ set of clause）置换合一
消解反演
链
目标状态
结点
根结点
目标网络
解答路径
（ path）
解答树
（ tree）
nil
语义网络
知识表示方法间的关系
2.1 状态空间法
2.2 问题归约法
2.3 谓词逻辑法
2.4 语义网络法
2.5 其他方法
2.6 小结
2
2.1状态空间法
（ State Space Representation）
?问题求解技术主要是两个方面：
?问题的表示
?求解的方法
?状态空间法
?状态 （ state）
?算符 （ operator）
?状态空间方法
3
2.1.1 问题状态描述
?定义
?状态,描述某类不同事物间的差别而引入的
一组最少变量 q0,q1,…,qn的有序集合。
?算符,使问题从一种状态变化为另一种状态
的手段称为操作符或算符。
?问题的状态空间,是一个表示该问题全部可
能状态及其关系的图，它包含三种说明的集
合，即三元状态 （ S,F,G） 。
2.1 状态空间法
4
2,状态空间表示概念详释
?例如下棋、迷宫及各种游戏。
Original
State
Middle
State
Goal
State
2.1 状态空间法
5
例,三数码难题
（ 3 puzzle problem）
12
3
1
2 3
1
2 3
31
2
31
2
3
1 2
初始棋局 目标棋局
2.1 状态空间法
6
?有向图
?路径
?代价
?图的显示说明
?图的隐示说明
2.1.2 状态图示法
A B
2.1 状态空间法
7
2.1.3 状态空间表示举例
?产生式系统 （ production system）
?一个总数据库,它含有与具体任务有关的信息随着应
用情况的不同，这些数据库可能简单，或许复杂 。
?一套规则,它对数据库进行操作运算。每条规则由左部
鉴别规则的适用性或先决条件以及右部描述规则应用时
所完成的动作。
?一个控制策略,它确定应该采用哪一条适用规则，而
且当数据库的终止条件满足时，就停止计算。
2.1 状态空间法
8
状态空间表示举例
?例：猴子和香蕉问题
2.1 状态空间法
9
解题过程
? 用一个四元表列 （ W,x,Y,z） 来表示
这个问题状态,
?这个问题的操作（算符）如下：
?2 goto（ U）表示猴子走到水平位臵 U
?或者用产生式规则表示为
（ W,0,Y,z） goto（ U） （ U,0,Y,z）
2.1 状态空间法
10
?pushbox（ V） 猴子把箱子推到水平位臵 V，
即有
（ W,0,W,z） pushbox（ V） （ V,0,V,z）
?climbbox猴子爬上箱顶，即有
（ W,0,W,z） climbbox （ W,1,W,z）
2.1 状态空间法
11
?grasp猴子摘到香蕉，即有
（ c,1,c,0） grasp （ c,1,c,1）
?该初始状态变换为目标状态的操作序列为
{goto(b),pushbox(c),climbbox,grasp}
2.1 状态空间法
12
(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,climbbox
goto（ U）
U=bpushbox（ V）
猴子和香蕉问题的状态空间图
goto（ U）
U=V
2.1 状态空间法
13
猴子和香蕉问题自动演示：
?
猴子
香蕉
箱子
猴子
香蕉
箱子
?
Ha!Ha!
2.1 状态空间法
14
2.2 问题归约法
（ Problem Reduction Representation）
子问题 1
子问题 n
原始问题 子问题集
本
原
问
题
15
? 问题归约表示的组成部分：
?一个初始问题描述；
?一套把问题变换为子问题的操作符；
?一套本原问题描述。
?问题归约的实质：
?从目标 (要解决的问题 )出发逆向推理，建立子问
题以及子问题的子问题，直至最后把初始问题归
约为一个平凡的本原问题集合。
2.2 问题规约法
16
2.2.1 问题归约描述
（ Problem Reduction Description）
? 梵塔难题
1 2 3
CB
A
2.2 问题规约法
17
解题过程（ 3个圆盘问题）
1 2 3
1 2 3 1 2 3
1 2 3
1 2 3 1 2 3
1 2 3
1 2 3
2.2 问题规约法
18
多圆盘梵塔难题演示
2.2 问题规约法
19
2.2.2与或图表示
?1.与图、或图、与或图
2.2 问题规约法
A
B C D
与图
A
B C
或图
20
2.2 问题规约法
B C
D E F
G
A
HM
B C
D E F G
A
N
21
2.一些关于与或图的术语
2.2 问题规约法
HM
B C
D E F G
A
N
父节
点
与节
点
弧线
或节
点 子节
点
终叶节
点
22
3.定义
2.2 问题规约法
与或图例子
t
t
t
t
t
t
t
t
t（ a） （ b）
有解节点
无解节点 终叶节点
23
?不可解节点的一般定义
?没有后裔的非终叶节点为不可解节点。
?全部后裔为不可解的非终叶节点且含有或后
继节点，此非终叶节点才是不可解的。
?后裔至少有一个为不可解的非终叶节点且含
有与后继节点，此非终叶节点才是不可解的。
?与或图构成规则
2.2 问题规约法
24
梵塔问题归约图
（ 113） （ 123）?（ 111） （ 113）? （ 123） （ 122）?
（ 111） （ 333）?
（ 122） （ 322）?（ 111） （ 122）? （ 322） （ 333）?
（ 321） （ 331）?（ 322） （ 321）? （ 331） （ 333）?
2.2 问题规约法
25
2.3 谓词逻辑法
?逻辑语句
?形式语言
2.3.1 谓词演算
? 1,语法和语义
?基本符号
?谓词符号、变量符号、函数符号,常量
符号、括号和逗号
?原子公式
26
?连词和量词 (Connective &Quantifiers)
?连词
?与及合取 （ conjunction)
?或及析取 （ disjunction）
?蕴涵 （ Implication）
?非 （ Not）
?量词
?全称量词 （ Universal Quantifiers)
?存在量词 (Existential Quantifiers)
2.3 谓词逻辑法
27
2.3.2 谓词公式
?原子公式的的定义：
?用 P(x1,x2,…, xn)表示一个 n元谓词公式，
其中 P为 n元谓词,x1,x2,…, xn为客体变量或
变元。通常把 P(x1,x2,…,x n)叫做谓词演算的
原子公式，或原子谓词公式。
?分子谓词公式
?可以用连词把原子谓词公式组成复合谓词公
式，并把它叫做分子谓词公式。
2.3 谓词逻辑法
28
?合适公式 （ WFF,well-formed formulas）
?合适公式的递归定义
?合适公式的性质
?合适公式的真值
?等价（ Equivalence)
2.3 谓词逻辑法
29
2.3.3 臵换与合一
?臵换
?概念
?假元推理
?全称化推理
?综合推理
?定义
?就是在该表达式中用臵换项臵换变量
?性质
?可结合的
?不可交换的
2.3 谓词逻辑法
30
?合一（ Unification)
?合一：寻找项对变量的臵换，以使两表
达式一致。
?可合一：如果一个臵换 s作用于表达式集
{Ei}的每个元素，则我们用 {Ei} s来表示
臵换例的集。我们称表达式集 {Ei}是可合
一的。
2.3 谓词逻辑法
31
2.4 语义网络法
（ Semantic Network Representation）
?语义网络的结构
?定义
?组成部分
?词法
?结构
?过程
?语义
32
?表示占有关系和其它情况
?例,小燕是一只燕子，燕子是鸟；巢 -1是
小燕的巢，巢 -1是巢中的一个。
?选择语义基元
?试图用一组基元来表示知识，以便简化
表示，并可用简单的知识来表示更复杂
的知识。
2.4 语义网络法
2.4,1 二元语义网络的表示
33
2.4.2 多元语义网络的表示
?谓词逻辑与语义网络等效
LIMING MAN
ISA
ISA（ LIMING,MAN）或 MAN（ LIMING）
（语义网络）
（谓词逻辑）
2.4 语义网络法
34
?多元语义网络表示的实质
?把多元关系转化为一组二元关系的组合，或
二元关系的合取。
R(X1,X2,…,Xn)
R12(X1,X2)∧R 13(X1,X3)∧ …∧ R 1n(X1,Xn)
......
Rn-1 n(Xn-1,Xn)
可转换为
2.4 语义网络法
35
2.4.3 连接词和量化的表示
?合取
?三元变为二元组合
?析取
?加注析取界限，并标记 DIS，以免引起混淆。
?否定
?两种表示方式：～或标注 NEG界限。
2.4 语义网络法
36
?蕴涵
?在语义网络中可用标注 ANTE和 CONSE界限
来表示蕴涵关系。 ANTE和 CONSE界限分别
用来把与先决条件 (antecedent)及与结果
(consequence)相关的链联系在一起。
?量化
?存在量化 — ISA链
?全称量化 — 分割法
2.4 语义网络法
37
2.5其他方法（ Others)
?框架（ Frame）表示
?框架是一种结构化表示法，通常采用语义网络
中的节点 -槽 -值表示结构。
?剧本（ Script）表示
?剧本是框架的一种特殊形式，它用一组槽来描
述某些事件的发生序列。
?过程（ Procedure）表示
?过程式表示就是将有关某一问题领 域的知识，
连同如何使用这些知识的方法，均隐式地表达
为一个求解问题的过程。
38
2.6 小结（ Summary）
?本章所讨论的 知识表示问题 是人工智
能研究的核心问题之一。知识表示方
法很多，本章介绍了其中的 7种，有 图
示法 和 公式法, 陈述式表示 和 过程式
表示 等。
39
方法 初始问题 算符 目标 结果
状态
空间法
归约法
谓词
逻辑法
语义
网络法
状态
结点
合适公式
结点
算符
弧
子句集
（ set of clause）置换合一
消解反演
链
目标状态
结点
根结点
目标网络
解答路径
（ path）
解答树
（ tree）
nil
语义网络
知识表示方法间的关系
