五章节产生式系统Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope有生命必有希望有生命必有希望 第五章第五章 产生式系统产生式系统 产生式系统的体系结构是产生式系统的体系结构是 实现图搜实现图搜索的理想程序结构，产生式已是人工智能索的理想程序结构，产生式已是人工智能系统的一种最典型最普遍的结构形式系统的一种最典型最普遍的结构形式 许多专家系统和机器学习系统都是用许多专家系统和机器学习系统都是用产生式系统实现的从结构形式上看很多产生式系统实现的从结构形式上看很多人工智能系统都是产生式系统人工智能系统都是产生式系统7/25/20242 第五章第五章 产生式系统产生式系统产生式表示方法产生式表示方法产生式系统基本原理产生式系统基本原理产生式系统与图搜索产生式系统与图搜索产生式系统应用产生式系统应用7/25/20243 产生式表示法产生式表示法产生式产生式产生式一词是从波斯特机中借用来的波斯产生式一词是从波斯特机中借用来的波斯特机是一种自动机，它是根据串替换规则提特机是一种自动机，它是根据串替换规则提出的一种计算模型。
其中的每一条规则就叫出的一种计算模型其中的每一条规则就叫一个一个产生式产生式也称产生式规则产生式规则，简称，简称规则规则这里产生式就是前面讨论过的操作、逻辑蕴这里产生式就是前面讨论过的操作、逻辑蕴含式、推理规则以及各种关系（包含经验性含式、推理规则以及各种关系（包含经验性联想）的一种逻辑抽象联想）的一种逻辑抽象 7/25/20244 产生式表示法产生式表示法产生式的产生式的一般形式一般形式为：为：前件前件后件（情况后件（情况行为）行为）前件是前提，规则的执行条件前件是前提，规则的执行条件 后件是结论或动作，规则体后件是结论或动作，规则体产生式规则的产生式规则的语义语义：如果前提满足，则可得结论或：如果前提满足，则可得结论或者执行相应的者执行相应的动作动作，即后件由前件触发即后件由前件触发从基本事实到结论之间的复杂推理可以借助中从基本事实到结论之间的复杂推理可以借助中间结论形成小型简单产生式间结论形成小型简单产生式7/25/20245 产生式表示法产生式表示法例：一条知识的原始形态是例：一条知识的原始形态是 R: ( (A R: ( (A B) B) (C (C D)) D)) ((E ((E F) F) G)=>S G)=>S 引入中间结论引入中间结论S1S1，，S2S2，形成一些小型的产生式，形成一些小型的产生式: : R1 R1：： A A B =>S1 B =>S1 R2 R2：： C C D =>S1 D =>S1 R3 R3：： E E F =>S2 F =>S2 R4 R4：： S1 S1 G G =>S=>S R5: S1 R5: S1 S2 S2 =>S=>S7/25/20246 产生式表示法产生式表示法给定一组事实之后可用给定一组事实之后可用匹配技术匹配技术寻找可用产生寻找可用产生式，其基本思想是将已知事实代入产生式的前式，其基本思想是将已知事实代入产生式的前件，若前件为真，则该件，若前件为真，则该产生式是可用产生式是可用的。
的提高提高匹配效率匹配效率的方法的方法索引匹配为状态建立可用产生式索引表，减少可索引匹配为状态建立可用产生式索引表，减少可用产生式搜索范围用产生式搜索范围分层匹配将产生式分成若干层或组，按一定特征分层匹配将产生式分成若干层或组，按一定特征进行分层搜索进行分层搜索过滤匹配边匹配边过滤匹配边匹配边 按某些附加特征或参数对可按某些附加特征或参数对可用产生式进行精选用产生式进行精选7/25/20247 产生式表示法产生式表示法如果一组事实可以同时使几个产生式前提为真，如果一组事实可以同时使几个产生式前提为真，常用以下方法进行选择（常用以下方法进行选择（冲突消解策略冲突消解策略）：）：将所有产生式排序，选最早匹配成功的一个，不管将所有产生式排序，选最早匹配成功的一个，不管其余的产生式；其余的产生式；在所有匹配成功的产生式中取最强的，即前提条件在所有匹配成功的产生式中取最强的，即前提条件最多或情况元素最多者；最多或情况元素最多者；最近用过的产生式优先（或反之）；最近用过的产生式优先（或反之）；给情况元素以不同的优先权；给情况元素以不同的优先权；使用估计函数使用估计函数f(x)f(x)排序；排序；利用上下文限制。
利用上下文限制7/25/20248 产生式表示法产生式表示法在产生式系统中，从前提到结论通常也是一棵在产生式系统中，从前提到结论通常也是一棵与或树合取，与节点合取，与节点：一个产生式的前提包含了几个事实，：一个产生式的前提包含了几个事实，那么它的结论对应这些事实的合取那么它的结论对应这些事实的合取析取，或节点析取，或节点：一个结论可以由多个产生式得到，：一个结论可以由多个产生式得到，则这个结论对应这些产生式的析取则这个结论对应这些产生式的析取每个产生式系统每个产生式系统都隐含着许多这样的与或树都隐含着许多这样的与或树7/25/20249 产生式表示法产生式表示法F1P1F3F4F5F6BCDAP2P3P4P5F2事实事实中介事实中介事实B、、C、、D产生式规则产生式规则P1、、P2、、P3、、P4、、P5结论结论7/25/202410 产生式表示法产生式表示法（例）（例）例例 三个聪明人问题古代有个国王想知道他三个聪明人问题古代有个国王想知道他的三个大王中谁最聪明，就在他们每个人前额的三个大王中谁最聪明，就在他们每个人前额上都画了一个点，他们都能看到别人点的颜色，上都画了一个点，他们都能看到别人点的颜色，但看不到别人点的颜色。
国王说，你们中间至但看不到别人点的颜色国王说，你们中间至少有一个人的点式白色的于是重复地问他们：少有一个人的点式白色的于是重复地问他们：““谁知道自己点地颜色？谁知道自己点地颜色？””三位大臣们三位大臣们头两次头两次都回答说不知道都回答说不知道题目要求证明下一次他们全要求证明下一次他们全都会说都会说““知道知道””，并且所有的点都是白色并且所有的点都是白色7/25/202411 产生式表示法产生式表示法（例）（例）分析分析：： 这类问题的这类问题的特点特点是有有限个受试者，每个是有有限个受试者，每个人对问题都只有部分了解，无法直接求解但人对问题都只有部分了解，无法直接求解但在推理过程中每个人又可以从别人那里获得新在推理过程中每个人又可以从别人那里获得新的知识，重新进行推理可以的知识，重新进行推理可以用产生式来表达用产生式来表达推理过程中所用到的各种知识推理过程中所用到的各种知识7/25/202412 产生式表示法产生式表示法（例）（例）状态集合表示：状态集合表示： 用用x x1 1,x,x2 2,x,x3 3表示三个人点的颜色，表示三个人点的颜色，1 1表示白色，表示白色，0 0表示非白色。
表示非白色 X X＝＝(x(x1 1,x,x2 2,x,x3 3) )表示颜色分布状态表示颜色分布状态 全部可能的状态集合全部可能的状态集合( (可能界可能界PWPW0 0) )：：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}(1,1,0),(1,1,1)} 实际给定的状态为实际给定的状态为现实界现实界X X0 0 ＝＝(x(x1010,x,x2020,x,x3030) ) 用排除法找到用排除法找到X X0 0 7/25/202413 产生式表示法产生式表示法（例）（例）排除过程：排除过程：第一次，大臣只知道至少有一个人是白点，排除第一次，大臣只知道至少有一个人是白点，排除X X0 0＝＝{(0,0,0)}{(0,0,0)}状态这时如果有人看到两个非白点，根据排除的这时如果有人看到两个非白点，根据排除的状态可推知自己是白点。
状态可推知自己是白点第二次大臣根据没有一个人知道自己点颜色的事实推知至少第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点排除两人为白点排除{(0,0,1)(0,1,0)(1,0,0)}{(0,0,1)(0,1,0)(1,0,0)}状态这时如果这时如果有人看到一个非白点，根据排除后得到的状态可推知自己的有人看到一个非白点，根据排除后得到的状态可推知自己的点是白的点是白的第三次，大臣们根据仍无人知道自己点颜色的新事实推知没第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现，即有一个非白点出现，即X0X0＝＝{(1,1,1)}{(1,1,1)}于是三人都知道自己于是三人都知道自己点的颜色是白的点的颜色是白的7/25/202414 产生式表示法产生式表示法（例）（例）引入中介状态并定义下述符号：引入中介状态并定义下述符号： S Si i—— i—— i大臣看到的非白点数；大臣看到的非白点数； W Wi i—— i—— i大臣猜出自己点的颜色否如果他宣布已大臣猜出自己点的颜色否如果他宣布已知道自己点的颜色，为知道自己点的颜色，为1 1，否则为，否则为0 0；； n——X n——X0 0中白点的个数。
中白点的个数 7/25/202415 产生式表示法产生式表示法（例）（例）(1)((1)(已知已知) )(n>=1) <=>X(n>=1) <=>X0 0 ＝＝ { { (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}；；(2)(2)( (有人看见两个非白点有人看见两个非白点) )(n>=1) (n>=1) (S(Si i=2) =2) =>(W=>(Wi i=1),(i=1,2,3,=1),(i=1,2,3,下同下同) )；；(3)( (3)( i ) i ) (W(Wi i=1) =1) (n>=1) => (n=1) (n>=1) => (n=1) ；；(4) (n=1) => ((4) (n=1) => ( i ) i ) (W(Wi i=1) =1) ；；(5) ((5) ( i ) i ) (W(Wi i=0) =0) (n>=1) => (n>=2) ; (n>=1) => (n>=2) ;(6) (n>=2) <=>X(6) (n>=2) <=>X0 0 ＝＝ { (0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)} { (0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}；；(7) (7) ( (有人看见一个非白点有人看见一个非白点) )(n>=2) (n>=2) (S(Si i=1) =1) =>(W=>(Wi i=1);=1);(8) ( (8) ( i ) i ) (W(Wi i=1) =1) (n>=2) => (n=2) ;(n>=2) => (n=2) ;(9) (n=2) => ((9) (n=2) => ( i ) i ) (W(Wi i=1);=1);(10) ((10) ( i ) i ) (W(Wi i=0) =0) (n>=2) => (n=3); (n>=2) => (n=3);(11) (n=3) <=> X(11) (n=3) <=> X0 0 ＝＝ { (1,1,1)} { (1,1,1)}；；(12) (n=3) => ((12) (n=3) => ( i ) i ) (W(Wi i=1).=1).7/25/202416 产生式表示法产生式表示法（例）（例） 上述结果可以推广到上述结果可以推广到更一般的情况更一般的情况：：设有设有m m个个大臣，国王说至少有大臣，国王说至少有l l个人的点是白色的个人的点是白色的，则有，则有下述产生式：下述产生式： (1)(1) (n>=l) <=>X (n>=l) <=>X0 0 ＝＝ {x|x {x|x中的白点数中的白点数>=l}>=l}；； (2)(2) (n>=l) (n>=l) (S(Si i=2) =2) =>(W=>(Wi i=1),(i=1,2,…,m,=1),(i=1,2,…,m,下同下同) )；； (3)(3)( ( i ) i ) (W(Wi i=1) =1) (n>=l) => (n=l) (n>=l) => (n=l) ；； (4)(4) (n=l) => ( (n=l) => ( i ) i ) (W(Wi i=l) =l) ；； (5) (5)( ( i ) i ) (W(Wi i=0) =0) (n>=l) (n>=l) (l (n>=l (l (n>=l＋＋1) ;1) ; (6) (6)( ( i ) i ) (W(Wi i=0) =0) (n>=l) (n>=l) (l (l＝＝m-1)=> (nm-1)=> (n＝＝m)m)。
7/25/202417 第五章第五章 产生式系统产生式系统产生式表示方法产生式表示方法产生式系统基本原理产生式系统基本原理产生式系统与图搜索产生式系统与图搜索产生式系统应用产生式系统应用7/25/202418 产生式系统基本原理产生式系统基本原理组成和分类组成和分类运行过程运行过程常用算法常用算法7/25/202419 产生式系统基本原理产生式系统基本原理（组成和分类）（组成和分类）产生式系统结构产生式系统结构产生式规则库产生式规则库(知识库知识库)推理机（控制）推理机（控制）全局数据库全局数据库7/25/202420 产生式系统基本原理产生式系统基本原理（组成和分类）（组成和分类）组成组成全局数据库全局数据库————人工智能系统的数据结构中心是人工智能系统的数据结构中心是一个动态数据结构，用来存放初始事实数据、中间一个动态数据结构，用来存放初始事实数据、中间结构和最后结果对应叙述性知识结构和最后结果对应叙述性知识产生式规则库产生式规则库————作用在全局数据库上的一些规则作用在全局数据库上的一些规则的集合每条规则都有一定的条件，若全局数据库的集合每条规则都有一定的条件，若全局数据库中内容满足这些条件可调用这条规则。
对应过程性中内容满足这些条件可调用这条规则对应过程性知识推理机推理机————负责产生式规则的前提条件测试或匹配，负责产生式规则的前提条件测试或匹配，规则的调度和选取，规则体的解释和执行对应控规则的调度和选取，规则体的解释和执行对应控制性知识制性知识7/25/202421 产生式系统基本原理产生式系统基本原理（组成和分类）（组成和分类）例例 旅行推销员问题求从旅行推销员问题求从A A城出发，经过其他城市一次城出发，经过其他城市一次且仅一次，最后回到且仅一次，最后回到A A城的最小费用路线城市之间的城的最小费用路线城市之间的交通费用标在相应的联线上建立产生式系统交通费用标在相应的联线上建立产生式系统BCADE713109656710107/25/202422 产生式系统基本原理产生式系统基本原理（组成和分类）（组成和分类）（（1 1））全局数据库全局数据库————（已访问过的城镇名称序列）已访问过的城镇名称序列）约约束条件是除城镇束条件是除城镇A A之外其他名称不得在序列中重复出现；之外其他名称不得在序列中重复出现；只有所有的名称都在序列中出现后，城镇只有所有的名称都在序列中出现后，城镇A A才能重复出才能重复出现。
现2 2））规则集规则集————如下表所示如下表所示3 3））推理推理：： （（A A）） （（ABAB）） （（ABEABE）） （（4 4））终止条件终止条件————序列始于序列始于A A，终止于，终止于A A，其中包含其，其中包含其他所有城镇一次，且费用最少他所有城镇一次，且费用最少5 5））各种各种搜索策略搜索策略选择规则，如广度优先搜索，最好优选择规则，如广度优先搜索，最好优先搜索等先搜索等 R2R57/25/202423 产生式系统基本原理产生式系统基本原理（组成和分类）（组成和分类）规则集规则集 规则规则动作动作条件条件R R1 1下一步到下一步到A A系列中包含所有城镇时可用系列中包含所有城镇时可用R R2 2下一步到下一步到B B每条规则只能使用一次，即每条规则只能使用一次，即序列中已有某城镇时，不能序列中已有某城镇时，不能再使用相应规则再使用相应规则R R3 3下一步到下一步到C CR R4 4下一步到下一步到D DR R5 5下一步到下一步到E E7/25/202424 产生式系统基本原理产生式系统基本原理（组成和分类）（组成和分类）与一般分级组织的计算机软件相比具有特点：与一般分级组织的计算机软件相比具有特点：全局数据库的内容可以为所有规则所访问，没有任何全局数据库的内容可以为所有规则所访问，没有任何部分是专为某一规则建立的，这种特性便于模仿智能行部分是专为某一规则建立的，这种特性便于模仿智能行为中的强数据驱动。
为中的强数据驱动规则本身不调用其他规则规则之间的联系必须通过规则本身不调用其他规则规则之间的联系必须通过全部数据库联系全部数据库联系全局数据库、规则和推理机之间相对独立，这种积木全局数据库、规则和推理机之间相对独立，这种积木式结构便于整个系统增加和修改知识式结构便于整个系统增加和修改知识7/25/202425 产生式系统基本原理产生式系统基本原理（组成和分类）（组成和分类）分类体系（尼尔逊）分类体系（尼尔逊）按搜索策略分按搜索策略分不可挽回（不可挽回（irreversibleirreversible）的产生式系统）的产生式系统试探性的（试探性的（TentativeTentative）产生式系统）产生式系统回溯式（回溯式（BackingBacking）产生式系统）产生式系统图搜索式（图搜索式（Graph SearchGraph Search）产生式系统）产生式系统按搜索方向分按搜索方向分向前产生式系统（向前产生式系统（Forward Production SystemForward Production System））向后产生式系统（向后产生式系统（Backward Production SystemBackward Production System））双向产生式系统（双向产生式系统（BiBi－－directional Production Systemdirectional Production System））两种特殊的产生式系统两种特殊的产生式系统可交换的（可交换的（CommutativeCommutative）产生式系统）产生式系统可分解的（可分解的（DecomposableDecomposable）产生式系统）产生式系统7/25/202426 产生式系统基本原理产生式系统基本原理组成和分类组成和分类运行过程运行过程控制策略与常用算法控制策略与常用算法7/25/202427 产生式系统基本原理产生式系统基本原理（运行过程）（运行过程）推理机一次运行过程推理机一次运行过程从规则库中取出一条规则，将其前提同从规则库中取出一条规则，将其前提同当前动态数据库中的事实进行模式匹配当前动态数据库中的事实进行模式匹配匹配成功否？匹配成功否？把该规则的结论放入当前动态数据库；把该规则的结论放入当前动态数据库；或执行规则所规定的动作或执行规则所规定的动作Y YN N7/25/202428 产生式系统基本原理产生式系统基本原理（运行过程）（运行过程）产生式系统运行过程产生式系统运行过程实际的产生式系统，目标条件往往要经过多步推理实际的产生式系统，目标条件往往要经过多步推理才能满足或者证明问题无解。
才能满足或者证明问题无解产生式系统的运行过产生式系统的运行过程就是推理机不断的运用规则库中的规则，作用于程就是推理机不断的运用规则库中的规则，作用于动态数据库，不断进行推理并不断检测目标条件是动态数据库，不断进行推理并不断检测目标条件是否被满足的过程否被满足的过程产生式系统运行过程是从初始事实出发，寻求到达产生式系统运行过程是从初始事实出发，寻求到达目标条件的通路的过程所以目标条件的通路的过程所以也是一个搜索的过程也是一个搜索的过程7/25/202429 产生式系统基本原理产生式系统基本原理组成和分类组成和分类运行过程运行过程常用算法常用算法7/25/202430 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）推理方式推理方式正向推理正向推理 ————从初始事实数据出发，正向从初始事实数据出发，正向使用规则进行推理，朝目标方向前进又称使用规则进行推理，朝目标方向前进又称为前向推理、正向链、数据驱动的推理为前向推理、正向链、数据驱动的推理反向推理反向推理 ————从目标出发，反向使用规则从目标出发，反向使用规则进行推理，朝初始事实或数据方向前进又进行推理，朝初始事实或数据方向前进。
又称反向推理、反向链、目标驱动的推理称反向推理、反向链、目标驱动的推理7/25/202431 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）正向推理算法正向推理算法步步1 1 将初始事实将初始事实/ /数据置入动态数据库；数据置入动态数据库；步步2 2 用动态数据库中的事实匹配目标条件，若目标条件用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束满足，推理成功，结束步步3 3 用规则库中各规则的前提匹配动态数据库中的事实，用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集将匹配成功的规则组成待用规则集步步4 4 若待用规则集为空，则运行失败，退出若待用规则集为空，则运行失败，退出步步5 5 将待用规则集中各规则的结论加入动态数据库，或将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步者执行其动作，转步2 27/25/202432 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）反向推理算法反向推理算法步步1 1 将初始事实将初始事实/ /数据置入动态数据库，数据置入动态数据库，将目标条件置入将目标条件置入目标链；目标链；步步2 2 若目标链为空，则推理成功，结束。
若目标链为空，则推理成功，结束步步3 3 取出目标链中第一个目标，用动态数据库中的事实同取出目标链中第一个目标，用动态数据库中的事实同其匹配，若匹配成功，转步其匹配，若匹配成功，转步2 2步步4 4 用规则集中的各规则的结论同该目标匹配，若匹配成用规则集中的各规则的结论同该目标匹配，若匹配成功，则功，则3333将第一个匹配成功且未用过的规则的前提作为将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标加入目标链，转步新的目标，并取代原来的父目标加入目标链，转步3 3步步5 5 若该目标是初始目标，则推理失败，退出若该目标是初始目标，则推理失败，退出步步6 6 将该目标的父目标移回目标链，取代该目标及其兄弟将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步目标，转步3 37/25/202433 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）例：动物识别系统的产生是系统描述及求解例：动物识别系统的产生是系统描述及求解规则规则：：r1r1：： IF IF 该动物有毛发该动物有毛发 THEN THEN 该动物是哺乳动物该动物是哺乳动物r2r2：： IF IF 该动物有奶该动物有奶 THEN THEN 该动物是哺乳动物该动物是哺乳动物r3r3：： IF IF 该动物有羽毛该动物有羽毛 THEN THEN 该动物是鸟该动物是鸟r4r4：： IF IF 该动物会飞该动物会飞 AND AND 会下蛋会下蛋 THEN THEN 该动物是鸟该动物是鸟r5r5：： IF IF 该动物吃肉该动物吃肉 THEN THEN 该动物是食肉动物该动物是食肉动物r6r6：： IF IF 该动物有犬齿该动物有犬齿 AND AND 有爪有爪 AND AND 眼盯前方眼盯前方 THEN THEN 该动物是食肉动物动物该动物是食肉动物动物7/25/202434 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）r7r7：： IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 有蹄有蹄 THEN THEN 该动物是有蹄类动物该动物是有蹄类动物r8r8：： IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 是嚼反刍动物是嚼反刍动物 THEN THEN 该动物是有蹄动物该动物是有蹄动物r9r9：： IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 是食肉动物是食肉动物 AND AND 是黄褐色是黄褐色 AND AND 身上有暗斑点身上有暗斑点 THEN THEN 该动物是金钱豹该动物是金钱豹 r10r10：：IF IF 该动物是哺乳动物该动物是哺乳动物 AND AND 是食肉动物是食肉动物 AND AND 是黄褐色是黄褐色 AND AND 身上有黑色条纹身上有黑色条纹 THEN THEN 该动物是虎该动物是虎r11r11：：IF IF 该动物是有蹄类动物该动物是有蹄类动物 AND AND 有长脖子有长脖子 AND AND 有长腿有长腿 AND AND 身上有暗斑点身上有暗斑点 THEN THEN 该动物是长颈鹿该动物是长颈鹿 r12r12：：IF IF 该动物有蹄类动物该动物有蹄类动物 AND AND 身上有黑色条纹身上有黑色条纹 THEN THEN 该动物是斑马该动物是斑马7/25/202435 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）r13r13：： IF IF 该动物是鸟该动物是鸟 AND AND 有长脖子有长脖子 AND AND 有长腿有长腿 AND AND 不会飞不会飞 AND AND 有黑白二色有黑白二色 THEN THEN 该动物是鸵鸟该动物是鸵鸟r14r14：： IF IF 该动物是鸟该动物是鸟 AND AND 会游泳会游泳 AND AND 不会飞不会飞 AND AND 有黑白二色有黑白二色 THEN THEN 该动物是企鹅该动物是企鹅r15r15：：IF IF 该动物是鸟该动物是鸟 AND AND 善飞善飞 THEN THEN 该动物是信天翁该动物是信天翁7/25/202436 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）初始事实：初始事实： f1f1：某动物有毛发。
某动物有毛发 f2 f2：吃肉 f3 f3：黄褐色 f4 f4：有黑色条纹：有黑色条纹目标条件为：该动物为什么？目标条件为：该动物为什么？7/25/202437 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）7/25/202438 产生式系统基本原理产生式系统基本原理（常用算法）（常用算法）7/25/202439 第五章第五章 产生式系统产生式系统产生式表示方法产生式表示方法产生式系统基本原理产生式系统基本原理产生式系统与图搜索产生式系统与图搜索产生式系统应用产生式系统应用7/25/202440 产生式系统与图搜索产生式系统与图搜索产生式系统产生式系统图搜索图搜索初始事实数据初始事实数据初始节点初始节点目标条件目标条件目标节点目标节点产生式规则产生式规则状态转换规则、问题变换规则状态转换规则、问题变换规则规则库规则库操作集操作集动态数据库动态数据库节点（状态节点（状态/ /问题）问题）控制策略控制策略搜索策略搜索策略产生式系统与图搜索对比7/25/202441 第五章第五章 产生式系统产生式系统产生式表示方法产生式表示方法产生式系统基本原理产生式系统基本原理产生式系统与图搜索产生式系统与图搜索产生式系统应用产生式系统应用7/25/202442 产生式系统的应用实例产生式系统的应用实例基于消解原理的产生式系统基于消解原理的产生式系统基于自然演绎法的产生式系统基于自然演绎法的产生式系统基于专用知识的产生式系统基于专用知识的产生式系统7/25/202443 基于消解原理的产生式系统基于消解原理的产生式系统消解原理的产生式系统消解原理的产生式系统全局数据库：子句集合全局数据库：子句集合S S产生式规则集：一般形式是消解产生式规则集：一般形式是消解控制系统控制系统终止条件：终止条件：NIL SNIL S搜索策略：是个可交换的系统，使用各个具体的消解与先搜索策略：是个可交换的系统，使用各个具体的消解与先后顺序无关，采用不可挽回的控制策略。
后顺序无关，采用不可挽回的控制策略7/25/202444 基于消解原理的产生式系统基于消解原理的产生式系统过程过程RESOLUTIONRESOLUTION步步1 CLAUSES S1 CLAUSES S；；步步2 until NIL2 until NIL是是CLAUSESCLAUSES中的元素为止，中的元素为止，dodo；；步步3 begin3 begin步步4 4 在在CLAUSESCLAUSES中选取两个可消解的子句中选取两个可消解的子句C Ci i和和C Cj j；；步步5 5 计算计算C Ci i和和C Cj j的消解式的消解式R Rijij；；步步6 6 把把R Rijij并入到并入到CLAUSESCLAUSES中；中；步步7 end7 end7/25/202445 基于消解原理的产生式系统基于消解原理的产生式系统控制策略控制策略广度优先搜索策略广度优先搜索策略 相当于水平浸透法完备的但相当于水平浸透法完备的但效率低支持集消解策略支持集消解策略 反向产生式系统完备的，但不反向产生式系统完备的，但不一定得到最优解一定得到最优解启发式搜索策略启发式搜索策略 利用消解原理求解问题的经验，利用消解原理求解问题的经验，设计启发函数。
设计启发函数7/25/202446 补充：解树代换的一致性（一）补充：解树代换的一致性（一）设有一个代换集设有一个代换集{u{u1 1,u,u2 2,…,…，，u un n} }，其中每个，其中每个u ui i都是一个都是一个代换代换{t{ti1i1/ v/ vi1i1, t, ti2i2/ v/ vi2i2,…,…，， t tim(i)im(i)/ v/ vim(i)im(i)} } 又设又设U1U1＝＝{v{v1111, …, v, …, vim(1)im(1),…,…，， v vn1n1, …, v, …, vnm(n)nm(n)} }（所（所有下边的变量）有下边的变量） U2U2＝＝{t{t1111, …, t, …, tim(1)im(1),…,…，， t tn1n1, …, t, …, tnm(n)nm(n)} } （所有上边的项）（所有上边的项）定义：定义：代换集代换集{u{u1 1,u,u2 2,…,…，，u un n} }是一致的，当且仅当是一致的，当且仅当U1U1和和U2U2是可合一的是可合一的定义：定义：{u{u1 1,u,u2 2,…,…，，u un n} }的的合一复合合一复合U U是是U1U1和和U2U2的最一般合的最一般合一。
一解树上所有代换是一致的，则该问题有解，最后的代换解树上所有代换是一致的，则该问题有解，最后的代换是合一复合是合一复合U U7/25/202447 补充：解树代换的一致性（二）补充：解树代换的一致性（二）例设有一个代换集例设有一个代换集{u{u1 1,u,u2 2} }，其中，其中 u u1 1＝＝{f(g(x{f(g(x1 1))/x))/x3 3,f(x,f(x2 2)/x)/x4 4} }U1U1和和U2U2是可合一的，其最一般合一是：是可合一的，其最一般合一是： U U＝＝{f(g(x{f(g(x1 1))/x))/x3 3,f(g(x,f(g(x1 1))/x))/x4 4，， g(xg(x1 1)/x)/x2 2} }u2＝{x4/x3,g(x1)/x2}U1={x3,, x4, x3 ,x2}U2={f(g(x1)) f(x2) ,x4 ,g (x1)}7/25/202448 产生式系统的应用实例产生式系统的应用实例基于消解原理的产生式系统基于消解原理的产生式系统基于自然演绎法的产生式系统基于自然演绎法的产生式系统基于专用知识的产生式系统基于专用知识的产生式系统7/25/202449 基于自然演绎法的产生式系统基于自然演绎法的产生式系统消解原理产生式系统特点消解原理产生式系统特点优点：形式单一，处理规则简单。
优点：形式单一，处理规则简单缺点：太一般化，丢失了原公式重要语义信息，对缺点：太一般化，丢失了原公式重要语义信息，对应用启发搜索系统和人－机交互带来了困难；组合应用启发搜索系统和人－机交互带来了困难；组合爆炸，难以直接使用爆炸，难以直接使用自然演绎法自然演绎法保持专家知识原始的逻辑形态，保留了控制信息保持专家知识原始的逻辑形态，保留了控制信息推理规则复杂，但便于设计启发函数推理规则复杂，但便于设计启发函数推理过程直观，便于理解推理过程直观，便于理解7/25/202450 基于自然演绎法的产生式系统基于自然演绎法的产生式系统规则基产生式系统规则基产生式系统事实事实 用非蕴含形式谓词公式表示，用非蕴含形式谓词公式表示，规则规则 用蕴含形式表示用蕴含形式表示F F－规则－规则 前向推理系统中应用前向推理系统中应用B B－规则－规则 后向推理系统中应用后向推理系统中应用 7/25/202451 1 1、基于规则的向前推理系统（一）、基于规则的向前推理系统（一）基本原理基本原理 从代表初始事实的谓词公式从代表初始事实的谓词公式F F0 0出发通过一组出发通过一组F F－规则－规则{F{F1 1，，…………，，F F2 2} }来证明目标公式来证明目标公式G G成立。
成立初始事实初始事实F F0 0任意谓词公式任意谓词公式前束范式表示；运用前束范式表示；运用SkolemSkolem函数消去存在量词；省函数消去存在量词；省去全称量词；得到任意与或型事实表达式，改名，去全称量词；得到任意与或型事实表达式，改名，使各主要合取项的变量应不相同使各主要合取项的变量应不相同与或图表示：析取部分用与节点表示合取部分用或与或图表示：析取部分用与节点表示合取部分用或节点表示节点表示7/25/202452 1 1、基于规则的向前推理系统（二）、基于规则的向前推理系统（二）F F－规则－规则形如形如 L=>W L=>WL L为单一文字为单一文字W W为任意与或型谓词公式；为任意与或型谓词公式；W W中用中用SkolemSkolem消去存在量消去存在量词，变元只受全称量词约束；改名，使不同规则具词，变元只受全称量词约束；改名，使不同规则具有不同变元，规则变元与事实变元也不同有不同变元，规则变元与事实变元也不同复杂规则化为简单规则复杂规则化为简单规则7/25/202453 1 1、基于规则的向前推理系统（三）、基于规则的向前推理系统（三）终止条件终止条件用目标谓词用目标谓词G G表示表示G G为文字的析取式（文字都为目标文字）；用为文字的析取式（文字都为目标文字）；用SkolemSkolem函数消去函数消去全称量词；消去存在量词；全称量词；消去存在量词；改名，改名，使同一变元在各目标文字、规则、事实中最多出现使同一变元在各目标文字、规则、事实中最多出现一次。
一次推理基本过程推理基本过程不断将规则不断将规则L=>WL=>W利用匹配弧连接在与或图的利用匹配弧连接在与或图的L L叶结叶结点上；目标文字点上；目标文字G G本身可看作本身可看作G =>GG =>G作用在与或图上；作用在与或图上；一致解树各个叶结点都终止在目标节点，成功终止一致解树各个叶结点都终止在目标节点，成功终止7/25/202454 1 1、基于规则的向前推理系统（四）、基于规则的向前推理系统（四）例例: :命题逻辑中一个定理证明问题命题逻辑中一个定理证明问题构造一个向前的规则基推理系统来求解构造一个向前的规则基推理系统来求解事实事实 F F0 0：：规则规则 F F1 1：： F F2 2 ：： F F3 3：：目标目标 G G：：7/25/202455 1 1、基于规则的向前推理系统（五）、基于规则的向前推理系统（五）7/25/202456 1 1、基于规则的向前推理系统（六）、基于规则的向前推理系统（六）例例: :谓词逻辑中一个定理证明问题谓词逻辑中一个定理证明问题 自然数都是大于自然数都是大于0 0的整数的整数 所有整数不是偶数就是奇数所有整数不是偶数就是奇数 偶数的一半是整数偶数的一半是整数 所有自然数不是奇数就是一半为整数的数。
所有自然数不是奇数就是一半为整数的数构造一个向前的规则基推理系统来求解构造一个向前的规则基推理系统来求解7/25/202457 1 1、基于规则的向前推理系统（六）、基于规则的向前推理系统（六）一、预处理一、预处理F F0 0为事实表达式方法：为事实表达式方法：（（1 1）将公式化称任意与或型前束范式，每个否定词仅管）将公式化称任意与或型前束范式，每个否定词仅管 辖一个谓词；辖一个谓词；（（2 2）用）用SkolemSkolem函数去掉存在量词并改名使主合取项之间函数去掉存在量词并改名使主合取项之间无相同变量；无相同变量；（（3 3）隐去全称量词隐去全称量词7/25/202458 1 1、基于规则的向前推理系统（七）、基于规则的向前推理系统（七）二、预处理二、预处理F F1 1 F F2 2为为F F－规则方法：－规则方法：（（1 1）暂时消去）暂时消去—>—>；；（（2 2）将公式化为前束范式，一个否定词管辖一个谓词；）将公式化为前束范式，一个否定词管辖一个谓词；（（3 3）用）用SkolemSkolem函数消去存在量词；函数消去存在量词；（（4 4）改变变元名称使其与其他公式不同；）改变变元名称使其与其他公式不同；（（5 5）恢复蕴含式。
恢复蕴含式7/25/202459 1 1、基于规则的向前推理系统（八）、基于规则的向前推理系统（八）三、处理目标三、处理目标G G：：（（1 1）用）用SkolemSkolem函数消去全称量词；函数消去全称量词；（（2 2）隐去存在量词隐去存在量词7/25/202460 1 1、基于规则的向前推理系统（九）、基于规则的向前推理系统（九）7/25/202461 2 2、基于规则的向后推理系统（一）、基于规则的向后推理系统（一）基本原理基本原理从代表目标的谓词公式出发，通过一组从代表目标的谓词公式出发，通过一组B B－规则证－规则证明事实公式成立明事实公式成立目标目标任意谓词公式，任意谓词公式，SkolemSkolem函数消去全称量词；隐去存函数消去全称量词；隐去存在量词；改名，公式中主要析取项的变元应不相同在量词；改名，公式中主要析取项的变元应不相同与或图表示：与节点对应合取；或节点对应析取；与或图表示：与节点对应合取；或节点对应析取；根节点上任何后裔都为子目标根节点上任何后裔都为子目标7/25/202462 2 2、基于规则的向后推理系统（二）、基于规则的向后推理系统（二）B B－规则－规则W=>LW=>L；；L L为单一文字；为单一文字；W W为任意与或型谓词公式，变元受全称量词约束，为任意与或型谓词公式，变元受全称量词约束，变元改名。
变元改名复杂规则化为简单规则复杂规则化为简单规则7/25/202463 2 2、基于规则的向后推理系统（三）、基于规则的向后推理系统（三）推理过程推理过程目标谓词公式的与或图中有一节点标为目标谓词公式的与或图中有一节点标为L’L’，且可，且可与与L L合一，则可将规则作用在该与或树上其结果合一，则可将规则作用在该与或树上其结果使在与或树上从使在与或树上从L’L’引出一条匹配弧，连接一个以引出一条匹配弧，连接一个以L L为根，表示为根，表示WσWσ的与或图，的与或图， σ σ为为L L与与L’L’的最一般合的最一般合一终止条件终止条件当与或树的一致解树各个叶节点都终止在事实节点当与或树的一致解树各个叶节点都终止在事实节点时，此产生式系统成功终止时，此产生式系统成功终止7/25/202464 2 2、基于规则的向后推理系统（四）、基于规则的向后推理系统（四）例例: :基于规则的向后推理系统基于规则的向后推理系统给定事实为给定事实为: : FidoFido是狗是狗 FidoFido不会吠叫不会吠叫 FidoFido会摇尾巴会摇尾巴 MyetleMyetle会咪咪叫会咪咪叫7/25/202465 2 2、基于规则的向后推理系统（五）、基于规则的向后推理系统（五）已知规则为目标：存在猫不怕狗的现象，即7/25/202466 2 2、基于规则的向后推理系统（六）、基于规则的向后推理系统（六）7/25/202467 3 3、、F F－系统和－系统和B B－系统的对比（一）－系统的对比（一）对比项目对比项目F F－系统－系统B B－系统－系统使用条件使用条件1 1、事实谓词可为任意形式；、事实谓词可为任意形式；2 2、规则的形式、规则的形式L=>W;L=>W;3 3、目标谓词公式是文字的、目标谓词公式是文字的析取。
析取1 1、事实谓词公式是文字的、事实谓词公式是文字的合取式；合取式；2 2、规则的形式是、规则的形式是W=>L;W=>L;3 3、目标谓词公式是任意形、目标谓词公式是任意形式预处理预处理用用SkolemSkolem函数消去事实和规函数消去事实和规则谓词公式中的存在谓词则谓词公式中的存在谓词; ;略去全称量词用略去全称量词用SkolemSkolem函函数消去目标谓词公式中的全数消去目标谓词公式中的全称量词；略去存在量词称量词；略去存在量词用用SkolemSkolem函数消去目标谓词函数消去目标谓词公式中的全称量词；略去存公式中的全称量词；略去存在量词用在量词用SkolemSkolem函数消去函数消去事实和规则谓词公式中的存事实和规则谓词公式中的存在谓词在谓词; ;略去全称量词略去全称量词7/25/202468 3 3、、F F－系统和－系统和B B－系统的对比（一）－系统的对比（一）对比项目对比项目F F－系统－系统B B－系统－系统初始数据初始数据库库事实谓词公式，用与或树事实谓词公式，用与或树表示表示目标谓词公式，用与或树表目标谓词公式，用与或树表示示推理过程推理过程事实－事实－> >目标目标匹配时注意：变量代换，匹配时注意：变量代换， 以以W W代替代替L L目标－目标－> >事实事实匹配时注意：变量代换，匹配时注意：变量代换， 以以W W代替代替L L终止条件终止条件得到目标的一致解树得到目标的一致解树得到事实的一致解树得到事实的一致解树子句子句文字的析取文字的析取文字的合取文字的合取子句集子句集子句的合取子句的合取子句的析取子句的析取7/25/202469 产生式系统的应用实例产生式系统的应用实例基于消解原理的产生式系统基于消解原理的产生式系统基于自然演绎法的产生式系统基于自然演绎法的产生式系统基于专用知识的产生式系统基于专用知识的产生式系统7/25/202470 基于专用知识的产生式系统（一）基于专用知识的产生式系统（一）例机器人完成食品装袋作业的产生式系统例机器人完成食品装袋作业的产生式系统BAGGERBAGGER。
全局数据库：全局数据库：记录阶段信息记录阶段信息（核对订货（核对订货/ /大件物大件物品装袋品装袋/ /中中 件物品装袋件物品装袋/ /小件物品装袋小件物品装袋/ /装装 袋完毕）；袋完毕）； 物品信息；物品信息； 装袋情况装袋情况7/25/202471 基于专用知识的产生式系统（二）基于专用知识的产生式系统（二）阶段：核对订货阶段：核对订货口袋口袋1 1：空：空待装物品待装物品容器容器大小大小冰冻冰冻数量数量面包面包塑料袋塑料袋中件中件非非1 1果酱果酱罐子罐子小件小件非非1 1点心点心硬纸盒硬纸盒大件大件非非2 2冰淇淋冰淇淋硬纸盒硬纸盒中件中件是是1 1炸土豆片炸土豆片塑料袋塑料袋中件中件非非1 1百事可乐百事可乐瓶子瓶子大件大件非非1 17/25/202472 基于专用知识的产生式系统（三）基于专用知识的产生式系统（三）规则集规则集R1R11 1：：IFIF核对核对订货阶段，有炸土豆片，无饮料核对核对订货阶段，有炸土豆片，无饮料 THEN THEN建议增订一瓶百事可乐建议增订一瓶百事可乐R1R12 2：：IFIF核对订货阶段，有面包，无黄油核对订货阶段，有面包，无黄油 THEN THEN建议增订一块黄油建议增订一块黄油R2R2：：IFIF核对订货阶段核对订货阶段 THEN THEN结束核对订货阶段，进入大件物品装袋阶段，并启用结束核对订货阶段，进入大件物品装袋阶段，并启用口袋口袋 为当前袋为当前袋R3R3：：IFIF大件物品装袋阶段，有瓶子待装，当前袋中大件物品少于大件物品装袋阶段，有瓶子待装，当前袋中大件物品少于6 6件件 THEN THEN把瓶子装入当前袋中把瓶子装入当前袋中R4R4：：IFIF大件物品装袋阶段，有大件物品待装，当前袋中大件物品少于大件物品装袋阶段，有大件物品待装，当前袋中大件物品少于6 6件件 THEN THEN把此大件武平转入当前袋中把此大件武平转入当前袋中7/25/202473 基于专用知识的产生式系统（四）基于专用知识的产生式系统（四）R5R5：：IFIF大件物品装袋阶段，有瓶子待装大件物品装袋阶段，有瓶子待装 THEN THEN启用新口袋启用新口袋I I＋＋1 1为当前袋为当前袋R6R6：：IFIF大件物品装袋阶段大件物品装袋阶段 THEN THEN进入中件物品装袋阶段，并启用一空口袋为当前袋。
进入中件物品装袋阶段，并启用一空口袋为当前袋R7R7：：IFIF中件物品装袋阶段，有冰冻物品待装，当前袋未满中件物品装袋阶段，有冰冻物品待装，当前袋未满 THEN THEN将此冰冻物品放入冰冻融离袋，然后放入当前袋中将此冰冻物品放入冰冻融离袋，然后放入当前袋中R8R8：：IFIF中件物品装袋阶段，有中件物品待装，当前袋中未满中件物品装袋阶段，有中件物品待装，当前袋中未满 THEN THEN把此中件物品放入当前袋把此中件物品放入当前袋R9R9：：IFIF中件物品装袋阶段，有中件物品待装中件物品装袋阶段，有中件物品待装 THEN THEN启用新口袋启用新口袋i i＋＋1 1为当前袋为当前袋 7/25/202474 基于专用知识的产生式系统（五）基于专用知识的产生式系统（五）R10R10：：IFIF中件物品装袋阶段中件物品装袋阶段 THEN THEN结束中件物品装袋阶段，进入小件物品装袋阶段，并结束中件物品装袋阶段，进入小件物品装袋阶段，并选一未满口袋为当前袋选一未满口袋为当前袋R11R11：：IFIF小件物品装袋阶段，有小件物品待装，当前袋未满小件物品装袋阶段，有小件物品待装，当前袋未满 THEN THEN把此小件物品装入当前袋中把此小件物品装入当前袋中R12R12：：IFIF小件物品装袋阶段，有小件物品待装小件物品装袋阶段，有小件物品待装 THEN THEN选一未满口袋或新口袋为当前袋选一未满口袋或新口袋为当前袋R13R13：：IFIF小件物品装袋阶段小件物品装袋阶段 THEN THEN结束装袋作业，装袋完毕。
结束装袋作业，装袋完毕控制系统控制系统：正向推理系统，规则优先权按自然大小排序，只有：正向推理系统，规则优先权按自然大小排序，只有RiRi规规则不能使用时才考虑则不能使用时才考虑R Ri i＋＋1 1规则 7/25/202475 基于专用知识的产生式系统（六）基于专用知识的产生式系统（六）上述初始状态经上述初始状态经BAGGERBAGGER作业后有如下终止状态：作业后有如下终止状态：阶段：装袋完毕阶段：装袋完毕待装：无待装：无口袋口袋1 1：百事可乐，点心（：百事可乐，点心（2 2））口袋口袋2 2：冰淇淋，炸土豆片、面包、果酱：冰淇淋，炸土豆片、面包、果酱7/25/202476 。