第2章知识表示

1、第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所22.1状态空间法（State Space Representation）v问题求解技术主要是两个方面：v问题的表示v求解的方法v状态空间法v状态（state）v算符（operator）v状态空间方法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所32.1.1 问题状态描述v定义

2、v状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。v算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。v问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所42. 状态空间表示概念详释v例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.1 状态空间法CISICCISICCISICCISICCISICCISICCIS

3、ICCISICCISIC中南大学 智能系统与智能软件研究所5例:三数码难题（3 puzzle problem）123123123312312312初始棋局目标棋局2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所6v有向图v路径v代价v图的显示说明v图的隐示说明2.1.2 状态图示法AB2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所72.1.3 状态空间表示举例v产生式系统（production system

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

5、中南大学 智能系统与智能软件研究所9解题过程v 用一个四元表列（W，x，Y，z）来表示这个问题状态.v这个问题的操作（算符）如下：v2 goto（U）表示猴子走到水平位置Uv或者用产生式规则表示为（W，0，Y，z） goto（U） （U，0，Y，z）2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所10vpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbox（V） （V，0，V，z）vclimbbox猴子爬上箱顶，即有（W，0，W，z） climbbox （W，1，W，z）

6、2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所11vgrasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1） v该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所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，

7、0）目标状态目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所13猴子和香蕉问题自动演示： 猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 状态空间法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所142.2 问题归约法（Problem

8、 Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所15v 问题归约表示的组成部分：v一个初始问题描述；v一套把问题变换为子问题的操作符；v一套本原问题描述。v问题归约的实质：v从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学

9、 智能系统与智能软件研究所162.2.1 问题归约描述 （Problem Reduction Description）v梵塔难题123CBA2.2 问题规约法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所17解题过程（3个圆盘问题）1231231231231231231231232.2 问题规约法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所18多圆盘梵塔难题演示2.2 问题规约法CISICCISICCISICCISICCISICCISIC

10、CISICCISICCISIC中南大学 智能系统与智能软件研究所192.2.2与或图表示v1.与图、或图、与或图2.2 问题规约法ABCD与图ABC或图CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所202.2 问题规约法BCDEFGAHMBCDEFGANCISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所212.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点CISICCISICCISICCISICC

11、ISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所223.定义2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所23v不可解节点的一般定义v没有后裔的非终叶节点为不可解节点。v全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。v后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。v与或图构成规则2.2 问题规约法CISICCISICCISICCISIC

12、CISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所24梵塔问题归约图（113） （123） （111） （113） （123） （122） （111） （333） （122） （322） （111） （122） （322） （333） （321） （331） （322） （321） （331） （333） 2.2 问题规约法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所252.3 谓词逻辑法v逻辑语句v形式语言2.3.1 谓词演算v 1. 语法和语义v基本符号v谓词符号、变量符号、函

13、数符号、 常量符号、括号和逗号v原子公式CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所26v连词和量词(Connective &Quantifiers)v连词v与及合取（conjunction)v或及析取（disjunction）v蕴涵（Implication）v非（Not）v量词v全称量词（Universal Quantifiers)v存在量词 (Existential Quantifiers)2.3 谓词逻辑法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大

14、学 智能系统与智能软件研究所272.3.2 谓词公式v原子公式的的定义：v用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。v分子谓词公式v可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。2.3 谓词逻辑法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所28v合适公式（WFF，well-formed formulas）v合适公式的递归定义v合适公式的性质v合适公式的真值v等价（Equi

15、valence)2.3 谓词逻辑法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所292.3.3 置换与合一v置换v概念v假元推理v全称化推理v综合推理v定义v就是在该表达式中用置换项置换变量v性质v可结合的v不可交换的2.3 谓词逻辑法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所30v合一（Unification)v合一：寻找项对变量的置换，以使两表达式一致。v可合一：如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换

16、例的集。我们称表达式集Ei是可合一的。2.3 谓词逻辑法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所312.4 语义网络法 （Semantic Network Representation）v语义网络的结构v定义v组成部分v词法v结构v过程v语义CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所32v表示占有关系和其它情况v例： 小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。v选择语义基元v试图用一组基元来表示知识，以便简化

17、表示，并可用简单的知识来表示更复杂的知识。2.4 语义网络法2.4. 1 二元语义网络的表示CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所332.4.2 多元语义网络的表示v谓词逻辑与语义网络等效LIMINGMANISAISA（LIMING，MAN）或）或 MAN（LIMING）（语义网络）（语义网络）（谓词逻辑）（谓词逻辑）2.4 语义网络法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所34v多元语义网络表示的实质v把多元关系转化为一组二

18、元关系的组合，或二元关系的合取。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 语义网络法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所352.4.3 连接词和量化的表示v合取v三元变为二元组合v析取v加注析取界限，并标记DIS，以免引起混淆。v否定v两种表示方式：或标注NEG界限。2.4 语义网络法CISICCISICCISICCISICCISICCISICCISICCISICCISIC中南大学 智能系统与智能软件研究所36v蕴涵v在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。ANTE和CONSE界限分别用来把与先决条件(antecedent)及与结果(consequence)相关的链联系在一起。v量化v存在量化ISA链v全称量化分割法2.4 语义网络法CISICCISICCISIC