第5-6章 产生式系统

1第5章产生式系统1产生式知识表示方法由美国数学家E.Post于1943提出，具有和Turing机一样的表达能力。也有心理学家认为人脑对知识的存储就是产生式形式的。

产生式系统有悠久的历史。Post最早提出产生式系统并作为计算手段设计的Post系统，目的是为了构造一种形式化的计算工具，并证明它和图灵机有相同的计算能力。几乎同时，Chomsky在研究自然语言结构时，提出了文法分层的概念，并提出了文法的“重写规则”，即语言生成规则，实际上是特殊的产生式。221960年，Backus提出了著名的BNF（巴科斯范式），用以描述计算机语言的文法，后来发现，BNF范式实际上就是Chomsky的上下文无关文法。至此，产生式系统的应用范围大大扩展。

产生式表示方法容易描述事实、规则以及它们的不确定性度量。

35.1产生式规则3产生式规则是表示知识的一种方式，一般形式为：P

Q，或IfPthenQ。产生式的含义是：如果前提P被满足，则可推出结论Q或执行Q所规定的动作。例：1）IF动物会飞AND会下蛋THEN该动物是鸟。

2）如果炉温超过上限，则关闭阀门。

3）如果病人有红色斑点，且病人发烧，且病人是学龄儿童，则病人患的是水痘。产生式规则与逻辑蕴含式的区别与联系逻辑蕴含式是产生式，反之则不然。基于产生式的推理模式假言推理：45.2产生式系统45.2.1产生式系统的组成产生式规则库。用于描述相应领域内的知识的产生式规则的集合。规则库中的知识要求完整、一致、表达准确灵活、知识组织合理；推理机。又称控制系统，是一个程序模块，负责产生式系统的运行。如规则与事实的匹配、执行规则、停止控制等。55产生式规则与逻辑蕴含式的区别与联系逻辑蕴含式是产生式，反之则不然。产生式可以包括各种操作、规则、变换、算子、函数等等。产生式规则描述了事物之间的对应关系，包括因果关系和蕴含关系基于产生式的推理模式假言推理：可以把有前提条件的操作和逻辑推理统称为推理。上式构成基于产生式规则的一般推理模式。6产生式系统的组成产生式系统由三部分组成：产生式规则库、推理机、动态数据库。动态数据库。又称综合数据库。存放初始事实、数据、目标条件、中间结果和最后结果。产生式规则库动态数据库推理机675.2.2产生式系统的运行过程运行需要：规则库、初始事实（或数据）和目标条件。目标条件是系统正常结束的条件,也是系统的求解目标。78推理机的一次推理过程：把该规则的结论放入当前动态数据库，或执行规则所规定的动作从规则库中取一条规则，将其前提同当前动态数据库中的事实/数据进行模式匹配匹配成功否？NY89产生式推理可以在与或图的基础上进行

910产生式系统的控制策略（正向推理）10正向推理：从初始事实/数据出发，正向使用规则进行推理，朝目标方向前进。步1初始化动态数据库，将初始事实、数据置入动态数据库中。步2用动态数据库中的事实、数据匹配目标条件，若目标条件满足，则推理成功，结束。步3用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集。步4若待用规则集为空，则运行失败，退出。步5将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步2。11R1：若某动物有奶，则它是哺乳动物。R2：若某动物有毛发，则它是哺乳动物。R3：若某动物有羽毛，则它是鸟。R4：若某动物会飞且生蛋，则它是鸟。R5：若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。R6：若某动物是哺乳动物且吃肉，则它是食肉动物。R7：若某动物是哺乳动物且有蹄，则它是有蹄动物。R8：若某动物是有蹄动物且反刍食物，则它是偶蹄动物。11例1设动物分类的规则库为12R9：若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。R10：若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。R11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。R12：若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。R13：若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是鸵鸟。R14：若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。R15：若某动物是鸟且善飞且不怕风浪，则它是海燕。1213再给出初始事实：F1：某动物有毛发F2：吃肉F3：黄褐色F4：有黑色条纹目标条件为：该动物是什么？1314动物分类产生式系统14图5-4动物分类正向推理树15产生式系统的反向推理反向推理：从目标出发，反向使用规则进行推理，朝初始事实或数据方向前进。步1初始化动态数据库，将初始事实、数据置入动态数据库。将目标条件置入目标链。步2若目标链为空，则推理成功，结束。步3取出目标链中第一个目标，用动态数据库中的事实、数据同其匹配，若匹配成功，转步2。1516步4用规则库中各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步3。步5若该目标是初始目标，则推理失败，退出。步6将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3。1617动物分类产生式系统17图5-5动物分类反向推理树18冲突消解策略正向推理算法二：带冲突消解策略。步1初始化动态数据库，将初始事实、数据置入动态数据库中。步2用动态数据库中的事实、数据匹配目标条件，若目标条件满足，则推理成功，结束。步3用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集。步4若待用规则集为空，则运行失败，退出。步5用某种策略，从待用规则集中选取一条规则，将其结论加入动态数据库，或者执行其动作，撤消待用规则集，转步2。18195.5产生式系统的程序实现产生式规则的程序语言实现规则的前提部分可表示为

条件1AND条件2AND…AND条件n或

条件1OR条件2OR…OR条件n规则的结论部分可表示为

断言1/动作1and断言2/动作2and…and断言n/动作n或断言1/动作1or断言2/动作2or…or断言n/动作n一般只考虑含有至多一个结论部分的产生式规则（类似于Horn子句逻辑）

条件1AND条件2AND…AND条件n

断言/动作1920产生式系统的程序实现产生式规则的具体表示方法可以使用If-Then规则，也可以使用多元组的形式表示，如二元组（<前件>，<后件>）可表示一个产生式规则。无论使用何种表示方式，必须与规则的解释程序（即推理机）相容。在Prolog中表示产生式规则，至少有两种形式：（1）、用Prolog的规则表示产生式规则；（2）、用Prolog的事实表示产生式规则。若用（1）表示产生式规则，则使用Prolog内部的推理机，无须自己编写推理机。若用（2）表示产生式规则，则须自己编写显式的推理机程序。2021产生式系统的程序实现例动物分类系统中的产生式规则可用Prolog语言中的规则表示为：

animal_is(“老虎”):-it_is(“食肉动物”),fact(“黄褐色”)，fact(“有黑色条纹”).it_is(“食肉动物”):-it_is1(“哺乳动物”),fact(“有爪”),fact(“有犬齿”),fact(“目盯前方”).2122产生式系统的程序实现it_is(“食肉动物”):-it_is1(“哺乳动物”),fact(“吃肉”).it_is1(“哺乳动物”):-fact(“有奶”).it_is1(“哺乳动物”):-fact(“有毛发”).2223产生式系统的程序实现上面的产生式规则也可以用Prolog中的事实表示为：rule([“食肉动物”,“黄褐色”，“有黑色条纹”],“老虎”).rule([“哺乳动物”,“有爪”,“有犬齿”,“目盯前方”],“食肉动物”).rule([“哺乳动物”,“吃肉”],“食肉动物”).rule([“有奶”],“哺乳动物”).rule([“有毛发”],“哺乳动物”).这种表示方法需要自己编写一个推理机程序。2324产生式系统的程序实现规则库的程序实现在Prolog中，如果用Prolog的规则表示产生式规则，规则库是程序的一部分，放在程序的clauses段。如果用事实表示产生式规则，则规则库用动态数据库或数据库文件实现。2425第6章知识表示6.1知识及其表示6.1.1知识的概念知识是人们对客观事物及其规律的认识及利用客观规律解决实际问题的方法和策略。就内容而言，知识可分为原理性知识和方法性知识。就形式而言，知识可分为显式知识和隐式知识。显式知识指可用语言、文字、符号、图形、声音等表示和处理的知识，可供他人直接识别。隐式知识是一种个体技能型的知识。就可靠性和严密性而言，知识又可分为理论知识和经验知识。2526知识表示是指面向计算机的知识描述和表达，是指把知识表示为计算机能存储、识别、处理和利用的形式的方法。知识表示是建立专家系统和各种知识系统的基础。提出了各种知识表示方法，如一阶谓词逻辑、产生式规则、框架、语义网络、对象、脚本、过程、神经网络等。知识表示可分为陈述表示和过程表示。陈述表示是把事物的属性、状态和关系逻辑描述出来，而过程表示则是把事物的行为和操作、解决问题的方法地和步骤具体地表示出来。也称为知识的动态表示或静态表示。266.1.2知识表示27如支持谓词逻辑的语言Prolog和Lisp，专门支持产生式规则的语言OPS5，专门支持框架的语言FRL，面向对象的语言Smalltalk,C++等。276.1.3知识表示的语言实现28第6章知识表示6.2.1.框架的概念

<框架名>

<槽名1><槽值1>|<侧面名11><侧面值111，侧面值112，…><侧面名12><侧面值121，侧面值122，…><槽名2><槽值2>|<侧面名21><侧面值211，侧面值212，…><侧面名22><侧面值221，侧面值222，…>………<槽名k><槽值k>|<侧面名k1><侧面值k11，侧面值k12，…><侧面名k2><侧面值k21，侧面值k22，…>296.2.1.框架的概念29

例6.1

下面是一个描述“教师”的框架：框架名:<教师>

类属:<知识分子>

工作:范围:(教学，科研)

缺省:教学性别:(男，女)

学历:(中师，高师)

类型:(<小学教师>，<中学教师>，<大学教师>)30306.2.1.框架的概念

例6.2

下面是一个描述“大学教师”的框架：框架名:<大学教师>

类属:<教师>

学历:(学士，硕士，博士)

专业:<学科专业>

职称:(助教，讲师，副教授，教授)

外语:语种:范围:(英，法，日，俄，德，…)

缺省:英水平:(优，良，中，差)

缺省:良3131

例6.3

描述一个具体教师的框架:

框架名:<教师-1>

类属:<大学教师>

姓名:李明性别:男年龄:25

职业:教师职称:助教专业:计算机应用部门:计算机系软件教研室工作:

参加工作时间:1995年8月工龄:当前年份-参加工作年份工资:<工资单>32框架之间的关系实例框架父框架和子框架框架的“继承”特性子框架从父框架继承某些槽值或侧面值。子框架可以覆盖父框架中已有的槽值或侧面值。一个框架的槽值可以是另外一个框架名。框架网络(框架系统)326.2.1.框架的概念33框架适合表达结构性的知识。框架的槽是对象的属性或状态；框架的槽值可以是对象的属性或状态值，也可以是运算式或规则，甚至动作或过程调用。336.2.2框架的表达能力346.2.2框架的表达能力例6.4

下面是关于房间的框架:

框架名:<房间>

墙数x1:

缺省:x1=4

条件:x1>0

窗数x2:

缺省:x2=2

条件:x2≥0

门数x3:

缺省:x3=1

条件:x3>03535

前墙:(墙框架(w1，d1))

后墙:(墙框架(w2，d2))

左墙:(墙框架(w3，d3))

右墙:(墙框架(w4，d4))

天花板:<天花板框架>

地板:<地板框架>

门:<门框架>

窗:<窗框架>

条件:w1+w2+w3+w4=x2

d1+d2+d3+d4=x3

类型:(<办公室>，<教室>，<会客室>，<卧室>，<厨房>，<仓库>，…)3636例6.5机器人纠纷问题的框架描述如图6-1所示。37产生式规则用框架表示

例如，产生式

如果头痛且发烧，则患感冒。用框架表示可为：

框架名：<诊断1>

前提：条件1:头痛条件2:发烧结论:患感冒3838基于框架的推理方法是继承。所谓继承，就是子框架可以拥有其父框架的槽及其槽值。实现继承的操作有匹配、搜索和填槽。匹配是问题框架同知识库中的框架的模式匹配。搜索就是沿着框架间的纵向和横向联系，在框架网络中进行查找。6.2.3基于框架的推理396.2.3基于框架的推理39问题框架框架名:〈教师-1〉姓名:李明性别:男年龄:25职称:助教专业:计算机应用部门:计算机系软件教研室外语水平：406.2.4框架的程序语言实现专用的框架表示语言FRL(FrameRepresentationLanguage)在Prolog中，用含结构或表的谓词实现框架。4041教师框架用Prolog语言表示frame(name("教师")，

kind_of("<知识分子>")，

work(scope("教学"，"科研")，default("教学"))，

sex("男"，"女")，

reco_of_f