1、信息工程与自动化学院信息工程与自动化学院1信息工程与自动化学院信息工程与自动化学院2知识的表示知识的表示知识与知识表示基本概念知识与知识表示基本概念一阶谓词逻辑表示法一阶谓词逻辑表示法语义网络表示法语义网络表示法产生式规则表示法产生式规则表示法框架表示法框架表示法信息工程与自动化学院信息工程与自动化学院3l 了解知识、信息和数据的概念，以及它们之间的了解知识、信息和数据的概念，以及它们之间的关系。关系。l 了解知识的特性、分类及它们的表示方法。了解知识的特性、分类及它们的表示方法。l 掌握各种知识表示法表示知识的步骤和方法。掌握各种知识表示法表示知识的步骤和方法。 （重点：一阶谓词表示法（重点
2、：一阶谓词表示法、语义网络表示法、语义网络表示法）l 了解各种知识表示方法具体表示形式的优缺点及了解各种知识表示方法具体表示形式的优缺点及适宜的应用对象。适宜的应用对象。信息工程与自动化学院信息工程与自动化学院43.2 3.2 一阶谓词逻辑表示法一阶谓词逻辑表示法3.3 3.3 产生式表示法产生式表示法3.4 3.4 语义网络表示法语义网络表示法3.5 3.5 框架表示法框架表示法信息工程与自动化学院信息工程与自动化学院5v知识是人类智能的基础。知识是人类智能的基础。v智能活动过程主要是一个获取知识并运用知智能活动过程主要是一个获取知识并运用知识的过程。识的过程。v人工智能问题的求解也是以知识
3、为基础的，人工智能问题的求解也是以知识为基础的，知识的获取知识的获取、知识的表示知识的表示和和运用知识进行推运用知识进行推理理是人工智能学科研究的是人工智能学科研究的3个主要问题。个主要问题。信息工程与自动化学院信息工程与自动化学院6 “ “如何表示知识如何表示知识?”?” 怎样使机器能懂，能对之进行处理，并能以怎样使机器能懂，能对之进行处理，并能以一种人类能理解的方式将处理结果告诉人们。一种人类能理解的方式将处理结果告诉人们。 在在AIAI系统中，对知识要给出一个清晰简洁的系统中，对知识要给出一个清晰简洁的描述很困难。描述很困难。信息工程与自动化学院信息工程与自动化学院7 费根鲍姆费根鲍姆
4、知识是经过消减、塑造、解释和知识是经过消减、塑造、解释和 转换的信息。转换的信息。 Bernstein 知识是由特定领域的描述、关系知识是由特定领域的描述、关系 和过程组成的。和过程组成的。 Hayes-roth 知识是事实、信念和启发式规则。知识是事实、信念和启发式规则。 知识库观点知识库观点 知识是某领域中所涉及的各有关知识是某领域中所涉及的各有关 方面的一种符号表示。方面的一种符号表示。信息工程与自动化学院信息工程与自动化学院8知识的金字塔结构知识的金字塔结构元元知识知识知知 识识信信 息息数数 据据噪噪 声声信息工程与自动化学院信息工程与自动化学院9 数据数据 是记录信息的符号，是信息
5、的载体和表示。是记录信息的符号，是信息的载体和表示。 信息信息 是对数据的解释，是数据在具体的场合下是对数据的解释，是数据在具体的场合下 具体的含义。具体的含义。信息工程与自动化学院信息工程与自动化学院10u 相同的数据在不同的环境下表示不同的含义，相同的数据在不同的环境下表示不同的含义，蕴涵不同的信息；蕴涵不同的信息；u 并不是所有的数据都蕴涵着信息；并不是所有的数据都蕴涵着信息；u 不同格式的数据所蕴涵的信息量是不同的。不同格式的数据所蕴涵的信息量是不同的。信息工程与自动化学院信息工程与自动化学院11 一般把有关信息关联在一起所形成的信息结构一般把有关信息关联在一起所形成的信息结构称为称为
6、知识知识。 知识、数据、信息是知识、数据、信息是3个层次的概念。个层次的概念。有格式的数据有格式的数据信信 息息知知 识识抽抽 象象信息工程与自动化学院信息工程与自动化学院12【实例】知识的形成【实例】知识的形成137178766832525156430015信息工程与自动化学院信息工程与自动化学院13l 数据加工数据加工 将每两位数字分为一组；将每两位数字分为一组； 忽略那些小于忽略那些小于32的两位数；的两位数； 把余下的每组两位数用把余下的每组两位数用ASCII字符代替。字符代替。信息工程与自动化学院信息工程与自动化学院14l 加工后的信息加工后的信息GOLD 438+信息工程与自动化学
7、院信息工程与自动化学院15l 信息所表示的知识信息所表示的知识黄金价格为黄金价格为438438，并且在升值（，并且在升值（+ +）。）。信息工程与自动化学院信息工程与自动化学院16l 元知识元知识 所谓元知识，就是指使用知识的知识。所谓元知识，就是指使用知识的知识。如果：黄金价格低于如果：黄金价格低于500500 且价格正在上涨（且价格正在上涨（+ +）那么：购买黄金那么：购买黄金信息工程与自动化学院信息工程与自动化学院17知知 识识形式形式严密性严密性与可靠性与可靠性确定性确定性确切性确切性显式知识显式知识隐式知识隐式知识理论知识理论知识经验知识经验知识确定性知识确定性知识不确定知识不确定知
8、识 确切描述知识确切描述知识不确切描述知识不确切描述知识信息工程与自动化学院信息工程与自动化学院18 相对正确性相对正确性 不确定性不确定性 可表示性可表示性 可利用性可利用性 信息工程与自动化学院信息工程与自动化学院19 面向计算机的知识描述或表达形式和方法。面向计算机的知识描述或表达形式和方法。 知识表示的过程就是把知识编码成某种数据结构知识表示的过程就是把知识编码成某种数据结构的过程。的过程。 什么是知识表示？什么是知识表示？ 研究的主要内容研究的主要内容 表示观表示观 表示方法表示方法信息工程与自动化学院信息工程与自动化学院20 知识表示方法知识表示方法知识表示方法知识表示方法替代表示
9、替代表示直接表示直接表示局部表示局部表示分布表示分布表示陈述性表示陈述性表示过程性表示过程性表示状态空间表示状态空间表示与或图表示与或图表示语义网络表示语义网络表示框架表示框架表示谓词逻辑表示谓词逻辑表示产生式表示产生式表示信息工程与自动化学院信息工程与自动化学院21 表示知识的能力表示知识的能力 与推理方法的匹配与推理方法的匹配 知识和元知识的一致知识和元知识的一致 是否自然是否自然 过程性表示还是说明过程性表示还是说明 性表示性表示 是否加入启发信息是否加入启发信息 能否模块化能否模块化 能否表示不精确知识能否表示不精确知识 是否适于计算机处理是否适于计算机处理 是否有高效的算法是否有高效
10、的算法选取知识表示方法的影响因素：选取知识表示方法的影响因素：信息工程与自动化学院信息工程与自动化学院223.2 3.2 一阶谓词逻辑表示法一阶谓词逻辑表示法3.1 3.1 知识与知识表示知识与知识表示3.3 3.3 产生式表示法产生式表示法3.4 3.4 语义网络表示法语义网络表示法3.5 3.5 框架表示法框架表示法信息工程与自动化学院信息工程与自动化学院23 一阶谓词逻辑表示法是一种重要的知识表一阶谓词逻辑表示法是一种重要的知识表示方法，它以示方法，它以数理逻辑数理逻辑为基础，是到目前为止为基础，是到目前为止能够表达人类思维活动规律的一种最精确的形能够表达人类思维活动规律的一种最精确的形
11、式语言。式语言。信息工程与自动化学院信息工程与自动化学院24P（x1,x2,xn)谓词逻辑中的谓词逻辑中的n元元谓词谓词：谓词符号谓词符号（大写字母）（大写字母）参量（项参量（项/个体）个体）信息工程与自动化学院信息工程与自动化学院25f（x1,x2,xn) 为了表达个体之间的对应关系，引入为了表达个体之间的对应关系，引入n元个体函数，简称元个体函数，简称函数函数：函数符号函数符号（小写字母）（小写字母）个体变元个体变元信息工程与自动化学院信息工程与自动化学院26“所有所有”、“一切一切”、“任一任一”、“全体全体”、“凡凡是是”全称量词，记为全称量词，记为x“存在存在”、“有些有些”、“至少
12、有一个至少有一个”、“有有的的”存在量词，记为存在量词，记为x量量 词：词：信息工程与自动化学院信息工程与自动化学院27 (1) (1) 所有的人都是要死的。所有的人都是要死的。 (2) (2) 有的人活到有的人活到100100岁以上。岁以上。在个体域在个体域D D为人类集合时，可符号化为：为人类集合时，可符号化为：),()(xPx (1)(1) 其中其中P( (x) )表示表示 x 是要死的。是要死的。),()(xQx (2)(2) 其中其中Q( (x) )表示表示 x 活到活到100岁以上。岁以上。【实例】关于量词的使用【实例】关于量词的使用信息工程与自动化学院信息工程与自动化学院28u个
13、体变元的变化范围称为个体变元的变化范围称为个体域个体域（或论述域）。（或论述域）。u包揽一切事物的集合称为包揽一切事物的集合称为全总个体域全总个体域。 用谓词表示时，一般取全总个体域，然后再用谓词表示时，一般取全总个体域，然后再采取使用限定谓词的方法指出每个个体变元的采取使用限定谓词的方法指出每个个体变元的个体域。个体域。（1）对于全称量词：）对于全称量词：（2）对于存在量词：）对于存在量词：个体域：（教材个体域：（教材P96P96）)(xPx)(xPx蕴含式蕴含式合取项合取项信息工程与自动化学院信息工程与自动化学院29 紧接于量词之后被量词作用（即说明）的谓紧接于量词之后被量词作用（即说明）
14、的谓词公式称为该量词的辖域。词公式称为该量词的辖域。（1）对于全称量词：）对于全称量词：（2）对于存在量词：）对于存在量词：辖域：辖域： （教材（教材P97P97）),()(yxGxPx)()(xBxxP全称量词辖域全称量词辖域存在量词辖域存在量词辖域信息工程与自动化学院信息工程与自动化学院30 指导变元、约束变元、自由变元指导变元、约束变元、自由变元（教材（教材P97）l 指导变元指导变元：量词后面的变元称为量词的指导变元；：量词后面的变元称为量词的指导变元；l 约束变元约束变元：在一个量词的辖域中的与该量词的指导变元相：在一个量词的辖域中的与该量词的指导变元相同的变元称为约束变元；同的变元
15、称为约束变元；l 自由变元自由变元：其它的变元称为自由变元；：其它的变元称为自由变元；)(),(xQyxPx指导变元指导变元约束变元约束变元自由变元自由变元约束变元约束变元信息工程与自动化学院信息工程与自动化学院31【改名规则【改名规则】 一个变元在一个谓词公式中即可约束出现，又可自由一个变元在一个谓词公式中即可约束出现，又可自由出现，为了避免混淆，通常通过改名规则，使得一个谓词出现，为了避免混淆，通常通过改名规则，使得一个谓词公式中一个变元仅以一种形式出现。公式中一个变元仅以一种形式出现。【换名规则【换名规则】 在谓词公式中，将某量词辖域中出现的某个在谓词公式中，将某量词辖域中出现的某个约束
16、变元约束变元以及对应的以及对应的指导变元指导变元更改为本辖域中没有出现过的个体变更改为本辖域中没有出现过的个体变元符号，公式其它部分不变，谓词公式的等价性不变。元符号，公式其它部分不变，谓词公式的等价性不变。【代替规则【代替规则】 在谓词公式中，将某量词辖域中出现的某个在谓词公式中，将某量词辖域中出现的某个自由变元自由变元的所有出现用本辖域中未曾出现过的某个个体变元符号代的所有出现用本辖域中未曾出现过的某个个体变元符号代替，谓词公式的等价性不变。替，谓词公式的等价性不变。换名规则和代替规则是换名规则和代替规则是AI确定性推理的基础！确定性推理的基础！信息工程与自动化学院信息工程与自动化学院32
17、【改名规则的应用实例【改名规则的应用实例】),(),(zyxyQzyxxP),(),(),(),(zvxvQzyuuPzyxyQzyuuP利用换名规则：),(),(),(),(zyvyQzuxxPzyxyQzuxxP利用代替规则：信息工程与自动化学院信息工程与自动化学院33用谓词联接符号将一些谓词联接起来所形成的公式。用谓词联接符号将一些谓词联接起来所形成的公式。例如：例如： ISSTUDENT(ISSTUDENT(张三）张三） ISSTUDENT(ISSTUDENT(李四）李四）yx 谓词谓词联接符号联接符号信息工程与自动化学院信息工程与自动化学院34 ：合取（与）合取（与） ：析取（或）析
18、取（或）：等价（当且仅当）：等价（当且仅当）：蕴含（蕴含（IF THEN）：否定（非）否定（非） ( (或记为或记为) ) 常用的谓词联接符号：常用的谓词联接符号：信息工程与自动化学院信息工程与自动化学院35 ： “我喜欢音乐和绘画我喜欢音乐和绘画”，可表示为：可表示为： LIKE(I, Music) LIKE(I, Painting) ：“小张打篮球或踢足球小张打篮球或踢足球”，可表示为：，可表示为： PLAY(Zhang, Basketball ) PLAY(Zhang, football )：“机器人不在机器人不在2 2号房间号房间”，可表示为：可表示为： )2,(RRobotINROO
19、M【实例】联接符号的使用【实例】联接符号的使用信息工程与自动化学院信息工程与自动化学院36：“如果小王跑得最快，那么他获得冠军。如果小王跑得最快，那么他获得冠军。” RUN(Wang, Faster) WIN(Wang, Champion) ：“燕子飞回南方，春天来了。燕子飞回南方，春天来了。”，表示为：，表示为： FLY(Swallow, South) COME(Spring)信息工程与自动化学院信息工程与自动化学院37 在谓词前面加上量词，称作谓词中的所有在谓词前面加上量词，称作谓词中的所有个体个体变元被量化变元被量化。例如：例如：仅个体变元被量化的谓词称为仅个体变元被量化的谓词称为一阶谓
20、词一阶谓词；不仅个体变元被量化，函数符号和谓词符号也被量不仅个体变元被量化，函数符号和谓词符号也被量化的谓词称为化的谓词称为二阶谓词二阶谓词。)(xxA)(xxB)(xxPp信息工程与自动化学院信息工程与自动化学院38 谓词公式表示知识的步骤：谓词公式表示知识的步骤：定义谓词及个体，确定每个谓词及个体的确切定义谓词及个体，确定每个谓词及个体的确切含义；含义；根据所要表达的事物或概念，为每个谓词中的根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值；变元赋以特定的值；根据所要表达的知识的语义，用适当的联接符根据所要表达的知识的语义，用适当的联接符号将各个谓词联接起来，形成谓词公式。号将各个
21、谓词联接起来，形成谓词公式。信息工程与自动化学院信息工程与自动化学院39例例1 1：张三与李四打网球张三与李四打网球 (Zhang and Li play tennis)(Zhang and Li play tennis)解：解： 定义谓词：定义谓词： PLAYPLAY（x,y,zx,y,z): x): x和和y y进行运动进行运动z z 定义个体：定义个体： ZhangZhang（张三）；（张三）；LiLi（李四）；（李四）； tennistennis（乒乓球）（乒乓球） 将个体代入谓词中将个体代入谓词中 PLAY(Zhang,Li,tennisPLAY(Zhang,Li,tennis) )
22、【实例】【实例】 一阶谓词逻辑表示一阶谓词逻辑表示信息工程与自动化学院信息工程与自动化学院40例例2:2: (1) (1) 马科斯是男人。马科斯是男人。 (2) (2) 马科斯是庞贝人。马科斯是庞贝人。 (3) (3) 所有庞贝人都是罗马人。所有庞贝人都是罗马人。 (4) (4) 每个罗马人都有一个父亲。每个罗马人都有一个父亲。使用谓词逻辑表达为：使用谓词逻辑表达为： (1) MAN(Marcus(1) MAN(Marcus);); (2) POMPEIAN(Marcus (2) POMPEIAN(Marcus);); (3) (3) (4) (4) );()()(xROMANxPOMPEIA
23、Nx),()()()(yxFATHERxROMANyx信息工程与自动化学院信息工程与自动化学院41例例3 3： 有的人喜欢梅花，有的人喜欢菊花，有的人既有的人喜欢梅花，有的人喜欢菊花，有的人既 喜欢梅花又喜欢菊花。喜欢梅花又喜欢菊花。 定义谓词：定义谓词：LIKE( (x, , y): ): x喜欢喜欢y。 定义个体：定义个体：x：人：人 meihua: :梅花梅花 juhua: :菊花菊花 表示为：表示为：),(),()(),()(),()(juhuazLIKEmeihuazLIKEzjuhuayLIKEymeihuaxLIKEx信息工程与自动化学院信息工程与自动化学院42 喜欢玩篮球的人必
24、喜欢踢足球。喜欢玩篮球的人必喜欢踢足球。定义谓词：定义谓词： LIKEPLAY(x, y): x喜欢玩喜欢玩y。定义个体：定义个体： basketball:篮球篮球 football:足球足球表示为：表示为：),(),()(footballxLIKEPLAYbasketballxLIKEPLAYx信息工程与自动化学院信息工程与自动化学院43 要想出国留学，必须通过外语考试。要想出国留学，必须通过外语考试。定义谓词：定义谓词：PASS(x, y): x通过通过y EXAM(z):关于关于z的的考试考试 WANT(x, y): x想想到到y学习学习定义个体：定义个体：abroad:出国出国 Eng
25、lish:外语外语表示为：表示为：),()(,()(abroadxWANTEnglishEXAMxPASSx信息工程与自动化学院信息工程与自动化学院44 并不是所有的学生选修了历史和生物。并不是所有的学生选修了历史和生物。定义谓词：定义谓词：TAKES(x, y): 学生学生 x 选修了课程选修了课程 y STUDENT(x): x 是学生是学生定义个体：定义个体： H: 历史课程历史课程 B: 生物课程生物课程表示为：表示为：),(),()()(BxTAKESHxTAKESxSTUDENTx信息工程与自动化学院信息工程与自动化学院45 小张不肯学习但他是幸运的。小张不肯学习但他是幸运的。 所
26、有人都有饭吃。所有人都有饭吃。 他每天下午都去玩足球。他每天下午都去玩足球。信息工程与自动化学院信息工程与自动化学院46表示为：表示为： 定义谓词：定义谓词：HAVE( (x, , y):):x有有y； EATEAT（X X，Y Y）：）：x x吃吃y y。 定义谓词：定义谓词：PLAY( (z, , y, , x):):z 在在x时间玩时间玩y。)()(ZhangLUCKYZhangSTUDY),(),()(ricexEATricexHAVEx)(,()(xafternoonfootballhePLAYx信息工程与自动化学院信息工程与自动化学院47例例4: 4: 猴子摘香蕉问题猴子摘香蕉问题
27、 ?BAC信息工程与自动化学院信息工程与自动化学院48 定义谓词定义谓词: SITE(x, y): x在在y 处；处；HANG(x,yx):x悬挂在悬挂在y处处 On(x,y): x站在站在y上；上； HOLDS(y,w): y手里拿着手里拿着w 初始状态初始状态S0:),(),(),(),(),(0BananaMonkeyHOLDSBoxMonkeyONcBoxSITEbBananaHANGaMonkeySITES 目标状态目标状态Sg:),(),(),(),(),(BananaMonkeyHOLDSBoxMonkeyONbBoxSITEbBananaHANGbMonkeySITESg信息工
28、程与自动化学院信息工程与自动化学院49 猴子需要执行以下四个操作猴子需要执行以下四个操作: : GotoGoto( (u u, ,v v):): 猴子从猴子从 u u 走到走到 v v 处。处。 PushboxPushbox( (v v, ,w w):):猴子推着箱子从猴子推着箱子从v v 走到走到w w 处。处。 ClimbboxClimbbox: : 猴子爬上箱子。猴子爬上箱子。 Grasp:Grasp: 猴子摘到香蕉。猴子摘到香蕉。 猴子摘香蕉求解过程：猴子摘香蕉求解过程：GotoGoto( (u u, ,v v) )用用A A替换替换u u用用C C替换替换v v),(),(),(),
29、(),(0BananaMonkeyHOLDSBoxMonkeyONcBoxSITEbBananaHANGaMonkeySITES),(),(),(),(),(1BananaMonkeyHOLDSBoxMonkeyONcBoxSITEbBananaHANGcMonkeySITES信息工程与自动化学院信息工程与自动化学院50Pushbox(v, w)用用C替换替换v用用B替换替换w),(),(),(),(),(1BananaMonkeyHOLDSBoxMonkeyONcBoxSITEbBananaHANGcMonkeySITES),(),(),(),(),(2BananaMonkeyHOLDSBo
30、xMonkeyONbBoxSITEbBananaHANGbMonkeySITES信息工程与自动化学院信息工程与自动化学院51ClimbboxGrasp),(),(),(),(),(2BananaMonkeyHOLDSBoxMonkeyONbBoxSITEbBananaHANGbMonkeySITES),(),(),(),(),(3BananaMonkeyHOLDSBoxMonkeyONbBoxSITEbBananaHANGbMonkeySITES),(),(),(),(),(BananaMonkeyHOLDSBoxMonkeyONbBoxSITEbBananaHANGbMonkeySITESg
31、信息工程与自动化学院信息工程与自动化学院521.1.优点优点 严密性严密性。可以保证其演绎推理结果的正确性，。可以保证其演绎推理结果的正确性，可以较精确的表达知识。可以较精确的表达知识。 自然性自然性。谓词逻辑是一种接近于自然语言的。谓词逻辑是一种接近于自然语言的形式语言。形式语言。 通用性通用性。拥有通用的逻辑演算方法和推理的。拥有通用的逻辑演算方法和推理的规则。规则。 易于实现易于实现。用它表示的知识易于模块化，便。用它表示的知识易于模块化，便于知识的增删及修改，便于在计算机上实现。于知识的增删及修改，便于在计算机上实现。信息工程与自动化学院信息工程与自动化学院532.2.局限性局限性 效
32、率低效率低。由于推理是根据形式逻辑进行的，把推。由于推理是根据形式逻辑进行的，把推理演算与知识含义截然分开，抛弃了表达内容中所理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程太冗长，降低了含有的语义信息，往往使推理过程太冗长，降低了系统的效率。系统的效率。 灵活性差灵活性差。不便于表达和加入启发性知识及元知。不便于表达和加入启发性知识及元知识。识。 组合爆炸组合爆炸。在其推理过程中，随着事实数目的增。在其推理过程中，随着事实数目的增大及盲目的使用推例规则，有可能形成组合爆炸。大及盲目的使用推例规则，有可能形成组合爆炸。信息工程与自动化学院信息工程与自动化学院543.2
33、 3.2 一阶谓词逻辑表示法一阶谓词逻辑表示法3.1 3.1 知识与知识表示知识与知识表示3.3 3.3 产生式表示法产生式表示法3.4 3.4 语义网络表示法语义网络表示法3.5 3.5 框架表示法框架表示法信息工程与自动化学院信息工程与自动化学院55 19431943年年PostPost首先在一种计算形式体系首先在一种计算形式体系 中提出。中提出。 形式上很简单，但在一定意义上模仿形式上很简单，但在一定意义上模仿 了人类思考的过程。了人类思考的过程。 6060年代开始，成为年代开始，成为专家系统专家系统最基本的最基本的 知识表示方法。知识表示方法。信息工程与自动化学院信息工程与自动化学院5
34、6l 容易描述事实、规则以及它们的不确定性度量；容易描述事实、规则以及它们的不确定性度量；l 适合表示事实性知识和规则性知识；适合表示事实性知识和规则性知识；l 基本形式为：基本形式为： PQ 或者或者 IF P THEN Q前前 提提（可用的条件）（可用的条件）结结 论论（应该执行的操作）（应该执行的操作）信息工程与自动化学院信息工程与自动化学院57v 知识的产生式表示方法知识的产生式表示方法知知 识识规则性知识规则性知识事实性知识事实性知识确定性确定性不确定性不确定性确定性确定性不确定性不确定性P P Q Q 或者或者IF P THEN QIF P THEN QP P Q (CF) Q (
35、CF) 或者或者IF P THEN Q(CF)IF P THEN Q(CF)( (对象对象, ,属性属性, ,值）值） 或者或者( (关系关系, ,对象对象1,1,对象对象2 2）( (对象对象, ,属性属性, ,值值, ,可信度值）可信度值） 或者或者( (关系关系, ,对象对象1,1,对象对象2,2,可信度值）可信度值）信息工程与自动化学院信息工程与自动化学院58v 基本结构基本结构产生式规则库产生式规则库推推 理理 机机动态数据库动态数据库信息工程与自动化学院信息工程与自动化学院59l 产生式规则库产生式规则库 描述某领域内知识的产生式规则集合，是产生式描述某领域内知识的产生式规则集合，
36、是产生式系统进行问题求解的基础。系统进行问题求解的基础。l 推理机推理机 又称控制执行机构，它是一个程序模块，负责控又称控制执行机构，它是一个程序模块，负责控制和协调规则库与数据库的运行。包含了推理方制和协调规则库与数据库的运行。包含了推理方式和控制策略。式和控制策略。l 动态数据库动态数据库 又称为事实库，用于存放事实、中间结果和最后又称为事实库，用于存放事实、中间结果和最后结果等。结果等。信息工程与自动化学院信息工程与自动化学院60 规则描述事物间的因果关系。规则的产生式表规则描述事物间的因果关系。规则的产生式表示形式称为产生式规则，简称规则。示形式称为产生式规则，简称规则。v规则的一般形
37、式规则的一般形式 IF THEN IF THEN 或或 例如：例如： 所有人会死所有人会死甲是人甲是人甲会死甲会死信息工程与自动化学院信息工程与自动化学院61外部输入的初始事实放入综合数据库外部输入的初始事实放入综合数据库信息工程与自动化学院信息工程与自动化学院62l 正向推理正向推理l 反向推理反向推理l 双向推理双向推理事实事实/ /前提条件前提条件目标目标/ /结论结论目标目标/ /结论结论事实事实/ /前提条件前提条件目标目标/ /结论结论事实事实/ /前提条件前提条件信息工程与自动化学院信息工程与自动化学院63关于关于“老虎老虎”的正向推理树的正向推理树自底向上综合过程自底向上综合过
38、程 反向搜索反向搜索结论结论事实事实信息工程与自动化学院信息工程与自动化学院64自顶向下分析过程自顶向下分析过程 正向搜索正向搜索关于关于“老虎老虎”的反向推理树的反向推理树结论结论事实事实信息工程与自动化学院信息工程与自动化学院65例：例：设字符转换规则为：设字符转换规则为：ABC，ACD， BCG， BEF， DE。 已知已知A，B，求求F。描述：描述： (1) 综合数据库：综合数据库： x ，其中，其中 x 为字符。为字符。 (2) 规则集规则集: a. IF AB THEN C b. IF AC THEN D c. IF BC THEN G d. IF BE THEN F e. IF
39、D THEN E(3) 控制策略：控制策略：顺序排队顺序排队(4) 初始条件：初始条件： A, B (5) 结束条件：结束条件：F x 【实例【实例】信息工程与自动化学院信息工程与自动化学院66求解过程：求解过程：数据库数据库可触发规则可触发规则被触发规则被触发规则A,BA,B,CA,B,C,DA,B,C,D,GA,B,C,D,G,EA,B,C,D,G,E,F IF AB THEN C IF AC THEN D IF BC THEN G IF BE THEN F IF D THEN E信息工程与自动化学院信息工程与自动化学院67猴子摘香蕉问题猴子摘香蕉问题?CAB【产生式系统应用举例【产生式系
40、统应用举例】信息工程与自动化学院信息工程与自动化学院68求解：求解： (1) 综合数据库：综合数据库： (M, B, Box, On, H) M: 猴子的位置猴子的位置 B： 香蕉的位置香蕉的位置 Box: 箱子的位置箱子的位置 On=0: 猴子在地板上猴子在地板上 On=1: 猴子在箱子上猴子在箱子上 H=0: 猴子没有抓到香蕉猴子没有抓到香蕉 H=1: 猴子抓到了香蕉猴子抓到了香蕉 (2) 初始状态：初始状态： (A,C, B, 0, 0) 信息工程与自动化学院信息工程与自动化学院69 (3) 结束状态：结束状态： (x1, x2, x3, x4, 1) , 其中其中x1 x4为变量为变量
41、（M, B, Box, On, H）。）。 (4) 规则集：规则集： r1: IF (x, y, z, 0, 0) THEN (w, y, z, 0, 0) r2: IF (x, y, x, 0, 0) THEN (z, y, z, 0, 0) r3: IF (x, y, x, 0, 0) THEN (x, y, x, 1, 0) r4: IF (x, y, x, 1, 0) THEN (x, y, x, 0, 0) r5: IF (x, x, x, 1, 0) THEN (x, x, x, 1, 1) 其中，其中， x, y, z, w 为变量。为变量。信息工程与自动化学院信息工程与自动化学
42、院70解答：解答： 根据具体问题可将规则具体为：根据具体问题可将规则具体为：r1: IF (a, c, b, 0, 0) THEN (b, c, b, 0, 0)r1: IF (a, c, b, 0, 0) THEN (b, c, b, 0, 0)r2: IF (b, c, b, 0, 0) THEN (c, c, c, 0, 0)r2: IF (b, c, b, 0, 0) THEN (c, c, c, 0, 0)r3: IF (c ,c, c, 0, 0) THEN (c, c, c, 1, 0)r3: IF (c ,c, c, 0, 0) THEN (c, c, c, 1, 0)r4:
43、IF (b, c, b, 0, 0) THEN (b, c, b, 1, 0)r4: IF (b, c, b, 0, 0) THEN (b, c, b, 1, 0)r5: IF (c, c, c, 1, 0) THEN (c, c, c, 1, 1)r5: IF (c, c, c, 1, 0) THEN (c, c, c, 1, 1)在已知事实下，在已知事实下，r1r1r2r2r3r3r5,r5,可得到香蕉可得到香蕉信息工程与自动化学院信息工程与自动化学院71例例2：传教士与野人问题。传教士与野人问题。N个传教士，个传教士，N个野人，一个野人，一 条船，可同时乘坐条船，可同时乘坐k个人，要求在
44、任何时刻，在个人，要求在任何时刻，在 河的两岸，传教士的人数不能少于野人的人数。河的两岸，传教士的人数不能少于野人的人数。 问：如何过河？问：如何过河？(以以N=3，k=2为例求解。为例求解。)描述：描述：初始状态初始状态目标状态目标状态LRm30c30b10LRm03c03b01信息工程与自动化学院信息工程与自动化学院72 (1) 综合数据库：综合数据库： (m, c, b) 其中，其中，0m3，0c3，b 0, 1 (2) 初始状态：初始状态： (3, 3, 1) (3) 目标状态：目标状态： (0, 0, 0) (4) 规则集规则集IF (m, c, 1) THEN (m-1, c, 0
45、)IF (m, c, 1) THEN (m, c-1, 0)IF (m, c, 1) THEN (m-1, c-1, 0)IF (m, c, 1) THEN (m-2, c, 0)IF (m, c, 1) THEN (m, c-2, 0)信息工程与自动化学院信息工程与自动化学院73IF (m, c, 0) THEN (m+1, c, 1)IF (m, c, 0) THEN (m, c+1, 1)IF (m, c, 0) THEN (m+1, c+1, 1)IF (m, c, 0) THEN (m+2, c, 1)IF (m, c, 0) THEN (m, c+2, 1) (5) 控制策略：（略）控制策略：（略）信息工程与自动化学院信息工程与自动化学院74 数据驱动数据驱动 知识的无序性。知识的无序性。 控制策略与问题无关。控制策略与问题无关。 数据、知识和控制相互独立。数据、知识和控制相互独立。信息工程与自动化学院信息工程与自动化学院75 正向、逆向、双向产生式系统正向、逆向、双向产生式系统 可交换的产生式系统可交换的产生式系统 可分解的产生式系统可分解的产生式系统
