第二讲 产生式系统
2.2.1 产生式系统 1．序
1943年，Post首先提出了产生式系统。到目前为止，人工智能（AI）领域中的产生式系统，无论在理论上还是在应用上都经历了很大发展，所以现今AI中的产生式系统已与1943年Post提出的产生式系统有很大不同。 ? 因果关系
自然界各个知识元（事实，断言，证据，命题，?）之间存在着大量的因果关系，或者说前提和结论关系，用产生式（或称规则）表示这些关系是非常方便的： “模式——动作”对偶 “条件——结论”对偶
? 产生式系统
把一组领域相关的产生式（或称规则）放在一起，让它们互相配合、协同动作，一个产生式生成的结论一般可供另一个（或一些）产生式作为前提或前提的一部分来使用，以这种方式求得问题之解决，这样的一组产生式被称为产生式系统。
例如: IF A THEN B ; IF B and C THEN X
第 1 页
? 产生式系统的历史
a. 1943年，Post第一个提出产生式系统并把它用作计算手段。其目的是构造一种形式化的计算工具，并证明了它与图灵机具有同样的计算能力。
b. 1950年，Markov提出了一种匹配算法，利用一组确定的规则不断置换字符串中的子串从而把它改造成一个新的字符串，其思想与Post类似。
c. （大约在）1950年，Chomsky为研究自然语言结构提出了文法分层概念，每层文法有一种特定的“重写规则”，也就是语言生成规则。这种“重写规则”，就是特殊的产生式。
上面b和c所给出的系统其计算能力都与图灵机等价。
d. 1960年，Backus （译名为：巴克斯或巴科斯）提出了著名的BNF，即巴科斯范式，用以描写计算机语言的文法，首先用来描写ALGOL 60语言。不久即发现，BNF范式基本上是 Chomsky的分层系统中的上下文无关文法。由于和计算机语言挂上了钩，产生式系统的应用范围大大拓广了。
2．产生式系统 ? 产生式系统的构成 △ 一组规则
每条规则分为左部（或称前提、前件）和右部（或称结论、动作、后件）。通常左部表示条件，核查左部条件是否得到满足一般采用匹配方法，即查看数据基DB（Data Base）中是否存在左部所指明的情况，
第 2 页
若存在则认为匹配成功，否则认为匹配失败。一般说来，匹配成功则执行右部所规定的动作，例如：添加、修改和删除等。 △ 数据基
DB中存放的数据既是产生式作用的对象，又是构成产生式（或称规则）的基本元素。
△ 一个推理程序（Engine）
它负责整个产生式系统的运行，包括：规则左部与DB匹配；从匹配成功的规则中，选出一条将在下一步执行的规则R*，执行R*右部规定的动作；掌握时间结束产生式系统的运行。 ? 产生式系统的特点 △ 相对固定的格式
任何产生式都由左部（LHS）和右部（RHS）组成，左部匹配，右部动作。匹配提供的信息只有两种，成功或失败。 △ 知识的模块化 a. 知识元
知识元（或曰事实，证据，断言，…）是不能分解的最小知识片,知识元集 = 知识库（KB）中所有产生式包含的知识元的集合； b．规则
每条规则（或称每个产生式）指明了知识元之间的关系，每条规则都是由知识元和逻辑运算符组成的。规则（也称为知识片）存于KB中，规则间不能直接相互作用。 c．元知识
还有如何使用规则的知识（例如，规则匹配的先后次序，匹配冲突
第 3 页
消解（即解决）等），我们称其为元知识（用于控制的元知识），元知识也可以模块化并表成元规则，但只有少数产生式系统才能做到这一点。
△ KB的flexible
知识的模块化，KB与推理机分离，使KB的扩充、修改变得十分容易。但维持KB的一致性、无矛盾性、完备性不是一件容易的事情。 △ 相互影响的间接性
产生式系统一般采用“数据驱动”（也称为正向推理，前向链推理），控制流是看不见的，一条规则的调用对其它规则之影响不是直接传送过去的，而是通过修改DB而间接实现的。 △ 机器可读性 A．机器识别产生式
语法检查和某种程度上的语义检查。语法检查包括矛盾、冗余、循环链等检验，例如， A→B，A→?B（矛盾），A∨B→C，A→C（冗余）, A→B, B→C, C→A,（循环）等。语义检查则涉及产生式系统的具体领域。
B．推理结论解释
机器可读性的另一种含义是对产生式系统推出的结论进行解释。
3．非确定性匹配 △ 部分匹配
…… 此处隐藏225字 ……
?1??2??3?能，第2对括号中共有
?8??8??8??8??8??8??8????????????????????? = 247 ?2??3??4??5??6??7??8?种可能，第3对括号中有7种可能（同第一对括号），故总的组合数为
12103种，即例1要变成标准产生式，则需变成12103个产生式，
这样做即不直观，又不经济，部分匹配的意义之一于此可见。 规则压缩：（把多条规则压缩成一条规则）直观易于理解。 扩大了产生式系统的求解能力。 △ 加权方法
上例中的方法有些缺点，即每一组症状中的各个症状间须是平等的。如果在同一组症状中，有些比较重要，有些则不那么重要，那么应如何解决呢？在每一症状后加一个参数权。
第 5 页