规则演绎系统课件

3.5规则演绎系统3.5规则演绎系统1例如：ABCACBABC

BAC都与子句A

BC等价。归结演绎将谓词公式化为子句集，原来蕴涵在谓词公式中的一些重要信息会在求取子句集的过程中丢失。但在A

BC中，是根本得不到原逻辑公式中所蕴涵的那些超逻辑的含义的。多数情况下，人们大多希望使用那种接近于原始问题描述的形式来进行求解，而不希望把问题描述化为子句集例如：都与子句ABC等价。归结演绎将谓词公式化为子2保留蕴涵式，将其作为推理规则，用于直接推导目标公式，不仅符合人的自然思维方式，也能通过规则（作为启发式知识）更有效地引导演绎推理过程。

保留蕴涵式，将其作为推理规则，用于直接推导目标公式，不仅符合3说明：

其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。

基于规则的问题求解系统运用下述规则：antecedentconcequent有时，then部分用于规定动作；这时，称这种基于规则的系统为反应式系统(reactionsystem)或产生式系统(production

system)。

说明：

其中，If部分可能由几个if组成，而Then部分可能43.5.1规则正向演绎系统逆向推理：正向推理：从事实出发，应用规则不断推导出中间结果作为新的事实，直至推导出目标公式

从目标公式出发，逆向应用规则不断推导出子目标，直至所有子目标就是给定的事实为止。

3.5.1规则正向演绎系统逆向推理：正向推理：从事实出发，5正向推理燕子飞回来了燕子飞回来了（中间结果）3燕子飞回来后就筑巢燕子筑巢了事实1.春天来了;2春天来了,燕子就飞回来了;3燕子飞回来后就筑巢(2、3为规则）目标:燕子筑巢了吗?正向推理:1.春天来了(事实)2春天来了,燕子就飞回来了正向推理燕子飞回来了燕子飞回来了（中间结果）3燕子飞回来后6逆向推理燕子飞回来了（子目标）2春天来了,燕子就飞回来了事实1.春天来了;2春天来了,燕子就飞回来了;3燕子飞回来后就筑巢(2、3为规则）目标:燕子筑巢了吗?正向推理:1.燕子筑巢了3燕子飞回来后就筑巢春天来了(事实)燕子飞回来了(子目标)逆向推理燕子飞回来了（子目标）2春天来了,燕子就飞回来了事7正向演绎推理要求将问题求解的描述分为三个部分：事实、规则集和目标。为便于演绎推理，需将表示它们的合适公式简化为下述标准形式，并加以适当限制。正向演绎推理要求将问题求解的描述分为三个部分：事实、规则集和8一、问题求解的规范表示

1.事实

为支持演绎推理，事实表达式不必化简为子句集，只需规范地表示为不含蕴涵符号的文字与或形。

例如有事实表达式：

（"x）（$y）（

z）{Q(x,y)∨[(R(y)∨P(z))∧S(x,z)]}

化简成：

Q(A,w)∧[(

R(y)∧P(f(y))∨

S(A,f(y))]

一、问题求解的规范表示1.事实

为支持演绎推理，事实表9事实表达式的文字与或形可以用与或图表示，两者间的对应关系规定如下：

（1）若母式（化简得到的文字与或形）为析取式：E1∨E2∨…∨Ek

则以一个K-连接指向各析取项Ei

（i=1,2,…,k）。

（2）若母式为合取式：

E1∧E2∧…

∧Ek,则以K个1-连接指向各合取项Ei(i=1,2,…,k)。

事实表达式的文字与或形可以用与或图表示，两者间的对应关系规定10例如：例如：11事实表达式的与或形变换：要把一个公式化为与或形，可采用下列步骤：

(1)利用(W1→W2)和(～W1∨W2)的等价关系，消去符号→(如果存在该符号的话)。实际上，在事实中间很少有符号→出现，因为可把蕴涵式表示为规则。

(2)用狄·摩根(DeMorgan)定律把否定符号移进括号内，直到每个否定符号的辖域最多只含有一个谓词为止。

事实表达式的与或形变换：要把一个公式化为与或形，可采用下列12(5)删去全称量词，而任何余下的变量都被认为具有全称量化作用。

(3)对所得到的表达式进行Skolem化和前束化。(4)对全称量词辖域内的变量进行改名和变量标准化，而存在量词量化变量用Skolem函数代替。(5)删去全称量词，而任何余下的变量都被认为具有全称量化作132.规则

正向演绎推理以正向方式使用规则(称为F规则)，要求规则化简为以下形式：

L=>W其中，L为单文字，W是与或形。

之所以限制规则左部为单文字，是为了在演绎推理过程中便于通过L和与或图叶节点的匹配来激活规则。

2.规则正向演绎推理以正向方式使用规则(称为F规则)，要求14设表示规则的原始蕴涵式为：

（"x）{($y)（

z）P(x,y,z)=>（

u）[Q(x,u)∨R(x,u)]}

例：则先暂时消去蕴涵符号并化简为文字与或形：

P(x,y,f(x,y))∨Q(x,u)∨R(x,u)

再恢复蕴涵式表示：

P(x,y,F(x,y))=>Q(x,u)∨R(x,u)

设表示规则的原始蕴涵式为：

（"x）{($y)（z15有时化简的结果会出现形如

L1∨L2=>W

的情况

可以进一步化简为与其等价的两条规则

L1=>W,L2=>W

单文字的限制对知识的表示有所限定，例如，

L1∧L2=>W

这样的规则就不允许出现，只有转变为

L1=>

L2∨W或L2=>

L1∨W

这种转变丢失了启发式知识（L1或L2同时为真导致W为真）。不过，这种限制对演绎推理方法本身并不产生影响。

有时化简的结果会出现形如

L1∨L2=>W

的情163.目标目标公式化简后限定表示为文字的析取式，即子句。

化简时量词消去方法取事实表达式的对偶形式，即将全称量词的约束变量以Skölem函数或常量取代，并使子句隐含地受存在量词约束。

3.目标目标公式化简后限定表示为文字的析取式，即子句。化简17例如目标公式：

（

x）(

y)（

z）[P(x,y,z)∨Q(x,y)]

则先以Skölem常量A和Skölem函数g(y)分别取代约束变量x和z，再消去全称量词，

于是得:

(

y)[P(A,y,g(y))∨Q(A,y)]

然后消去存在量词，并隐含着y是存在量词的约束变量。

关于为何需用对偶方式消去量词，这里不作形式证明，仅通过与归结反演方法作对比来加以直观说明。在归结反演中，需将目标公式取反，自然上例中x和z成为存在量词约束变量，而y成为全称量词约束变量。

例如目标公式：

（x）(y)（z）[P(x,18最后子句中变量须作换名处理，使各文字不含同名变量。

化简结果为：

P(A,y,g(y))∨Q(A,w)

最后子句中变量须作换名处理，使各文字不含同名变量。化简结果19二、正向演绎推理的实现

借助于与或图表示方式，正向演绎推理从事实表达式出发，不断用激活（左部单文字和与或图叶节点匹配）的F规则对与或图进行变换（从而扩展了与或图），直至得到一个将目标表达式（子句）包含的所有文字都作为叶节点的一致解图。

二、正向演绎推理的实现借助于与或图表示方式，正向演绎推理201.命题逻辑的情况

例：设事实表达式为：

（P∧Q）∨(R∧S)∨T

给定规则集：

P=>C1∧C2,S=>C3∨C4,T=>C5

目标公式为：

C1∨C3∨C5

正向演绎推理的实现：首先建立相应于事实表达式的初始与或图（树），然后选用激活的规则变换与或图

1.命题逻辑的情况例：设事实表达式为：

（P∧Q）21对与或图的变换实际上就是将该规则加入与或图：将规则左部单文字作为节点插入与或图，并通过匹配弧（以宽箭头表示）和与或图相应叶节点连接起来；再将规则右部以与或图子图的方式插入。

P=>C1∧C2当目标公式中的所有文字（本例中的C1、C3和C5）全部作为目标节点进入同一个解图时，演绎推理成功结束。

对与或图的变换实际上就是将该规则加入与或图：将规则左部单文字22事实表达式：P∧Q）∨(R∧S)∨T

规则集：P=>C1∧C2,S=>C3∨C4,T=>C5

目标公式：C1∨C3∨C5

事实表达式：P∧Q）∨(R∧S)∨T规则集：目标公式：232.谓词逻辑的情况

由于公式含有变量，谓词逻辑情况下的演绎推理增加了复杂性。首先在判断规则能否激活时，要对规则左部的单文字和与或图中的相应叶节点作合一处理

其次，演绎推理过程可能会对同一变量进行不一致的置换，从而导致不一致解图的生成。

2.谓词逻辑的情况由于公式含有变量，谓词逻辑情况下的演绎推24应用实例：事实：P(x,y)(Q(x)R(v,y))F规则：P(u,v)S(u)N(v)目标公式：S(a)N(b)Q(c)P(x,y)(Q(x)R(v,y))P(x,y)Q(x)R(v,y)P(u,v)S(u)N(v)S(a)N(b)Q(x)R(v,y)Q(c){u/x,v/y}{a/u}{b/v}{c/x}应用实例：事实：P(x,y)(Q(x)R(v,y))F25作业：设已知事实为：((PQ)R)(S(TU))F规则为：S(XY)Z试用正向演绎推理推出所有可能的目标子句。作业：设已知事实为：264.1.2规则逆向演绎系统从目标公式出发，逆向应用规则对相应于目标公式的原始与或图进行变换，直至得到一个所有叶节点都是事实节点（以事实表达式中的文字作为节点内容的节点）的一致解图为止。

逆向演绎推理情况下问题求解的描述也分为三部分：目标公式、规则和事实，它们的标准化表示形式与正向演绎呈现对偶关系。

4.1.2规则逆向演绎系统从目标公式出发，逆向应用规则对27一、问题求解的规范表示

1.目标公式

将目标公式化简为不含蕴涵符号的文字与或形。

例如有目标公式：

（$x）（"y）{P(x)=>[Q(x,y)∧(R(x)=>S(x,y))]}

先化简为：

（

x）（

y）{

P(x)∨[Q(x,y)∧(

R(x)∨S(x,y))]}一、问题求解的规范表示1.目标公式将目标公式化简为不含蕴28

将全称量词的约束变量y以Sk?lem函数取代，消去全称量词和存在量词，隐含着变量x受存在量词的约束

于是得：

P(x)∨[Q(x,f(x))∧(

R(x)∨S(x,f(x)))]

再通过换名，使顶层析取式的各析取项不含同名变量：

P(z)∧[(Q(x,f(x))∧(

R(x)∨S(x,f(x))))

将全称量词的约束变量y以Sk?lem函数取代，消去全称量词29目标公式的文字与或形也可以用与或图表示，两者间的对应关系规定如下：

（1）若母式（化简得到的文字与或形）为合取式：E1∧E2∧…

∧Ek

则以一个K-连接指向各合取项Ei(i=1,2,…,k)。

（2）若母式为析取式：E1∨E2∨…

∨Ek

则以K个1-连接指向各析取项Ei(i=1,2,…,k)。

目标公式的文字与或形也可以用与或图表示，两者间的对应关系规定30目标公式：P(z)∧[(Q(x,f(x))∧(

R(x)∨S(x,f(x))))目标公式：P(z)∧[(Q(x,f(x))∧(R(x)∨312.规则

逆向演绎推理以逆向方式使用规则（称为B规则），要求规则化简为以下形式：

W=>L

其中，L为单文字，W是与或形

规则的激活取决于L和与或图叶节点的匹配。

2.规则逆向演绎推理以逆向方式使用规则（称为B规则），要求32先暂时消去蕴涵符号并化简为与或形：

P(x,y,f(x,y))∨

Q(y,f(x,y))∨R(x,u)

设表示规则的原始蕴涵式为：

（

x）{(

y)（

z）[P(x,y,z)∧Q(y,z)]=>（

u）R(x,u)再恢复蕴涵式表示：

P(x,y,f(x,y)∧Q(y,f(x,y))=>R(x,u)

先暂时消去蕴涵符号并化简为与或形：

P(x,y,f(x33有时化简的结果会出现形如

W=>L1∧L2

的情况可以进一步化简为与其等价的两条规则

W=>L1,W=>L2

有时化简的结果会出现形如

W=>L1∧L2

的情343.事实表达式

事实表达式化简后限定表示为文字的合取式，消去量词时将存在量词的约束变量以SkÖlem函数或常量取代，并使合取式隐含地受全称量词约束。3.事实表达式

事实表达式化简后限定表示为文字的合取式，35二、逆向演绎推理的实现

借助于与或图表示方式，逆向演绎推理不断用激活