人工智能ch6 经典逻辑推理

第二部分推理第6章经典逻辑推理第7章不确定性推理第8章模糊推理推理与人工智能推理是人类求解问题的主要思维方法，其任务是利用知识得到结论，因而与知识的表达方法有密切的关系。计算机虽可以存储大量知识，却并不代表它拥有智能。只有当它能利用这些知识进行推理，求解问题（即具有思维能力），才认为它拥有智能。因此，关于推理及其方法的研究成为人工智能的一个重要研究课题。经典逻辑推理是最先提出的一种方法。推理的概念

例如：医疗诊断专家系统。知识库存储专家的经验及医学常识；数据库存放病人的症状、化验结果等初始事实。利用该专家系统为病人诊治疾病就是一次推理过程。即从病人的症状及化验结果等初始事实出发，利用知识库中的知识及一定的控制策略，对病情作出诊断，并开出医疗处方。按照某种策略从已有事实和知识推出另一判断的过程。从初始事实出发，不断运用知识库中的已知知识，逐步推出结论的过程就是推理。推理的概念推理一般包括两种判断：已知的判断，包括已掌握的与求解问题有关的知识及关于问题的已知事实；由已知判断推出的新判断，即推理的结论。在人工智能系统中，推理是由程序实现的，称为推理机。推理机利用知识库中的知识，按一定的控制策略求解问题。推理方式分类推理方式演绎推理、归纳推理、默认推理确定性推理、不确定性推理单调推理、非单调推理启发式推理、非启发式推理基于知识的推理、统计推理、直觉推理推出新判断的途径推理时所用知识的确定性推出结论是否越来越接近最终目标，即结论是否单调增加推理时是否应用与问题相关的启发性知识从方法论角度出发推理的控制策略推理是一个求解问题的过程。求解的质量和效率与求解方法以及求解问题的策略有关。控制策略主要包括：推理方向的选择、搜索策略、冲突消解策略、求解策略、限制策略等。求解策略确定推理是只求一个解，还是求所有解及最优解。限制策略为防止无穷推理过程，或由于推理过程太长增加时间及空间的复杂性，对推理的深度、宽度、时间、空间等进行限制。推理的控制策略推理方向确定推理的驱动方式。分为：正向推理、反向(逆向)推理、混合推理、双向推理。无论采用哪种方向，系统一般都包含：存放知识的知识库、存放初始已知事实及问题状态的数据库、用于推理的推理机。模式匹配模式匹配：对两个知识模式(如谓词公式、框架片断、语义网络片断等)的比较与耦合，即检查这两个知识模式是否完全一致或近似一致。按匹配时两个知识模式的相似程度划分：确定性匹配(完全匹配、精确匹配)——两个模式完全一致，或经过变量代换后变得完全一致。置换与合一(谓词逻辑表示法)不确定性匹配——两个模式不完全一致，但相似程度在规定限度内。冲突消解策略在推理过程中，系统不断地用DB中的事实与KB中的规则进行匹配，当发生以下情况之一：已知事实可与KB中的多各个知识匹配成功；有多个(组)已知事实都可与KB中某个知识匹配成功；有多个(组)已知事实可与KB中的多个知识匹配成功。需要用冲突消解策略来决定先使用哪个知识。冲突消解策略实际上就是确定规则的启用顺序。冲突消解策略以产生式系统为例，在产生式系统中，若出现以下情况就认为发生了冲突：对正向推理，如果有多条产生式规则的前件都和已知事实匹配成功；或有多组不同的已加事实都与同一条产生式规则的前件匹配成功；或以上两种情况同时出现。对逆向推理而言，如果有多条产生式规则的后件都和某个假设匹配成功；或有多条产生式规则的后件可与多个假设匹配成功。常用的冲突解决策略有：专一性排序、按己知事实的新鲜性排序、数据排序、上下文限制、按条件个数排序、按匹配度排序。第六章经典逻辑推理技术经典逻辑推理是根据经典逻辑(命题逻辑及一阶谓词逻辑)的逻辑规则进行的一种推理，又称为机械—自动定理证明(mechanical-automatictheoremproving)。主要推理方法有：自然演绎推理、归结演绎推理、与/或形演绎推理。由于以经典逻辑理论为基础，这种推理只有“真”和“假”两种真值，因此是一种精确推理(确定性推理)。6.1归纳演绎推理谓词演算中，利用等价式和永真蕴含式，从一些已知公式推导出新公式，新公式也被称为定理。推导过程中使用的推理规则序列就是该定理的证明。自动定理证明是人工智能的一个重要研究领域，不仅因为许多数学问题使用定理证明，许多非数学问题(如医疗诊断、机器人行动规划等)也可以归结为定理证明问题。定理证明的实质是对前提P和结论Q证明PQ的永真性。由于谓词公式永真性证明的困难性，一般用反证法思想把“永真性”问题转化为“不可满足性”证明，即证明P∧Q是不可满足的。定理：设有谓词公式F，其标准形的子句集为S，则F不可满足的充要条件是S不可满足。6.1归纳演绎推理子句鲁宾逊归结原理归结反演应用归结原理求问题答案归结策略子句的定义定义1：原子公式及原子公式的否定统称为文字。定义2：任何文字的析取式称为子句。P∨Q、P(x,f(x),y)∨Q(y)∨R(f(x))特例：不包含任何文字的子句称为空子句。空子句不包含文字，不能被任何解释满足，所以空子句是永假的，即不可满足的。定义3：由子句构成的集合称为子句集。任何一个谓词公式都可以化成一个子句集。谓词公式化为子句集的步骤将谓词公式化为子句集的步骤如下：(等价式和蕴含式详见合式公式性质)(1)利用连接词化归率消去、P→QP∨QPQ(P→Q)∧(Q→P)PQ(P∧Q)∨(Q∧P)例：(x){[P(x)∨Q(x)](y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]Step1：(x){[(P(x)∨Q(x))]∨(y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]Step1：(x){[(P(x)∨Q(x))]∨(y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]谓词公式化为子句集的步骤(2)利用等价关系把移到紧靠谓词的位置PP(P∧Q)P∨Q(P∨Q)P∧Q(x)P(x)P(x)P(x)P(3)重新命名变元名，使不同量词约束的变元有不同名字(x)P(x)(y)P(y)(x)P(x)(y)P(y)Step2：(x){[P(x)∧Q(x)]∨(y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]Step3：(x){[P(x)∧Q(x)]∨(y)[S(x,y)∧Q(x)]}∧(w)[P(w)∨B(w)](4)消去不在辖域内，采用存在固化，用个体常量代替受该约束的变元，消除。在辖域内，用Skolem函数代替有相互依赖关系变量，消除。

(y)[(x)P(x,y)](y)P(g(y),y)其中，g(y)是Skolem函数，g(y)应是原合式公式中没有的符号。Step3：(x){[P(x)∧Q(x)]∨(y)[S(x,y)∧Q(x)]}∧(w)[P(w)∨B(w)]谓词公式化为子句集的步骤Step4：(x){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧(w)[P(w)∨B(w)](5)将公式化为前束形把所有移到公式左边，使每个量词的辖域包含这个量词后面的整个部分，所得公式称为前束形。

前束形公式由前缀和母式组成，前缀由串组成，母式由没有量词的公式组成。

谓词公式化为子句集的步骤Step4：(x){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧(w)[P(w)∨B(w)]Step5：(x)(w){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧[P(w)∨B(w)](6)利用分配律将母式化为合取范式P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)(7)略去由于公式中所有的变量都是量化的变量，因此可以把省略。母式中，省略的变量被默认为量化变量。谓词公式化为子句集的步骤Step5：(x)(w){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧[P(w)∨B(w)]Step6：(x)(w){[P(x)∨[S(x,f(x))]∧Q(x)}∧[P(w)∨B(w)](8)消去，把母式用子句集表示P∧D可表示为子句集：P

D(9)子句变量标准化，即重新命名变量，使每个子句中的变量符号不同谓词公式化为子句集的步骤Step6：(x)(w){[P(x)∨[S(x,f(x))]∧Q(x)}∧[P(w)∨B(w)]Step7：{[P(x)∨[S(x,f(x))]∧Q(x)}∧[P(w)∨B(w)]Step8：P(x)∨[S(x,f(x))Q(x)P(w)∨B(w)Step9：P(x)∨[S(x,f(x))Q(y)P(w)∨B(w)鲁宾逊归结原理由谓词公式转化为子句集的过程中可以看出：子句集中，子句间是合取关系，只要有一个子句不可满足，则子句集就不可满足。若子句集中包含空子句，则该子句集一定不可满足。

归结原理又称为消解原理，它是定理证明的基础。鲁宾逊归结原理基本思想：检查子句集S是否包含空子句，若包含，则S不可满足；若不包含，在S中选择合适的子句进行归结，一旦推导出空子句，则S不可满足。命题逻辑中的归结原理定义1：若P是原子谓词公式，则称P与P为互补文字。定义2：基子句是指没有变量的子句。基子句的归结：设C1、C2是子句集中任意两个基子句，若Cl中文字L1与C2中文字L2互补，那么从Cl和C2中分别消去L1和L2，将两个子句的剩余部分析取，构成新子句Cl2，该过程被称为归结。C12称为C1、C2的归结式。C1、C2是Cl2的父子句。命题逻辑中的归结原理例：C1=P∨Q∨R

C2=P∨S∨TC12=Q∨R∨S∨T归结过程的树形表示P∨Q∨RQ∨R∨S∨TP∨S∨T命题逻辑中的归结原理定理：归结式C12是其父子句C1和C2的逻辑结论。推论1：设C1和C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性。推论2：设C1和C2是子句集S中的两个子句，C12是它们的归结式，若把C12加入S中，得到新子句集S2，则S和S2在不可满足性的意义上是等价的。命题逻辑中的归结原理注意：命题逻辑中，对不可满足的子句集S，归结原理是完备的。即若子句集S不可满足，则必然存在一个从S到空子句的归结演绎。对于可满足的子句集S，用归结原理得不到任何结果。谓词逻辑中的归结原理在谓词逻辑中，需要先用最一般合一对子句进行代换，使它们包括互补的文字，然后才能进行归结。定义：设Cl、C2是两个没有相同变元的子句，分别表示成两个文字集合{Li}和{Mi}，{li}是{Li}的一个子集，{mi}是{Mi}的一个子集，若是{li}和{mi}的最一般合一，则称：C12={C1-{li}}∪{C2-{mi}}为C1和C2的二元归结式，{li}和{mi}是归结式上的文字。谓词逻辑中的归结原理例：设C1=P(x)∨Q(a)，C2=P(b)∨R(x)C1和C2有相同的变元x，修改C2为：C2=P(b)∨R(y)L1=P(x)，L2=P(b)L1与L2的最一般合一：={b/x}C12={{P(b),Q(a)}-{P(b)}}∪{{P(b),R(y)}-{P(b)}}={Q(a),R(y)}=Q(a)∨R(y)谓词逻辑中的归结原理例：设C1=P(x)∨P(f(a))∨Q(x)，C2=P(y)∨R(b)C1中有可合一的文字，用它们的最一般合一：1={f(a)/x}，置换C1为：C11=P(f(a))∨Q(f(a))

C1的因子对C11和C2进行归结：L1=P(f(a))，L2=P(y)L1与L2的最一般合一：2={f(a)/y}C12=Q(f(a))∨R(b)谓词逻辑中的归结原理定义：子句C1和C2的归结式是下列二元归结式之一：(1)C1和C2的二元归结式；(2)C1和C2的因子的二元归结式；(3)C1的因子和C2的二元归结式；(4)C1的因子和C2的因子的二元归结式；与命题逻辑相同，谓词逻辑中归结式也是它的父子句的逻辑结论。用归结式取代子句集中的父子句，得到的新子句集仍保持原子句集的不可满足性。归结反演应用归结原理证明定理的过程称为归结反演。归结反演的步骤：(1)将定理证明的前提谓词公式转化为子句集F。(2)将要求证明的目标表示成的谓词公式G(目标公式)。(3)将G的否定G转化成子句，加入到F中，得到子句集S。(4)应用归结原理对S中的子句进行归结，把每次归结得到的归结式都并入S中。如此反复进行，当归结得到空子句NIL，则停止归结，此时就证明了G为真。例：归结反演例：已知前提F：(x){[P(x,y)∧Q(y)](y)[R(y)∧S(x,y)]}试证明结论G：(x)R(x)(x)(y)[P(x,y)Q(y)]前提F的子句集：P(x,y)∨Q(y)]∨R(f(x))P(x,y)∨Q(y)]∨S(x,f(x))]结论G的否定子句集：R(z)P(A,B)Q(B)例：归结反演例：已知：能阅读的都是有文化的；海豚是没有文化的；某些海豚是有智能的。试用归结反演证明：某些有智能的并不能阅读。谓词定义：R(x)：x能阅读L(x)：x有文化D(x)：x是海豚I(x)：x有智能将前提形式化地表示为：(x)(R(x)L(x))(y)(D(y)L(y))(z)(D(x)∧I(x))将结论形式化地表示为：(w)(I(w)∧R(w))前提的子句集：R(x)∨L(x))D(y)∨L(y))D(A)I(A)结论的子句集：I(w)∨R(w)应用归结原理求问题答案除定理证明外，归结原理可用来求问题答案，其思想与定理证明类似。归结原理求问题答案的一般步骤：(1)把已知前提用谓词公式表示出来，并化为子句集S。(2)把待求解问题用谓词公式G表示出来，构造G和谓词ANSWER的析取式。ANSWER是为求解问题而设的谓词，变元必须与问题公式的完全一致。(3)把析取式化为子句集，加入到S中，得到子句集S'。(4)对S'进行归结，形成归结反演树——修改的证明树。(5)若得到归结式ANSWER，答案就在ANSWER中。例：应用归结原理求问题答案例：已知：王先生是小李的老师；小李与小张是同班同学；如果x和y是同班同学，则x的老师就是y的老师。求：小张的老师是谁？谓词定义：T(x,y)：x是y的老师C(x,y)：x和y同班同学前提的谓词公式表示：T(Wang,Li)C(Li,Zhang)(x)(y)(z)C(x,y)∧T(z,x)T(z,y)待求解问题的谓词公式表示：(x)T(x,Zhang)∨ANSWER(x)6.2.4应用归结原理求问题答案前提的谓词公式表示：T(Wang,Li)C(Li,Zhang)(x)(y)(z)C(x,y)∧T(z,x)T(z,y)待求解问题的谓词公式表示：(x)T(x,Zhang)∨ANSWER(x)前提的子句集：T(Wang,Li)(1)C(Li,Zhang)(2)C(x,y)∨T(z,x)∨T(z,y)(3)待求解问题子句集：T(u,Zhang)∨ANSWER(u)(4)将子句(1)、(3)归结：C(Li,y)∨T(Wang,x)(5)将子句(4)、(5)归结：C(Li,Zhang)∨ANSWER(Wang)(6)将子句(2)、(6)归结：ANSWER(Wang)(7)应用归结原理求问题答案归结的一般过程归结的一般过程：对子句集中所有子句逐对进行比较，对任何一对可归结的子句对都进行归结。设有子句集：S={C1,C2,C3,C4}，其中，C1,C2,C3,C4是S中的子句。(1)从C1开始，逐个与C2,C3,C4比较，若找到可以与C1归结的子句，就求出归结式。然后用C2与C3,C4进行比较，凡可归结的都进行归结，最后用C3与C4比较，若能归结也对它们进行归结。经过以上比较及归结，得到一组归结式，称为第一级归结式。(2)从C1开始，用S中的子句分别与第一级归结式中的子句逐个比较、归结，得到一组归结式，称为第二级归结式。(3)从C1开始，用S中的子句和第一级归结式中的子句逐个与第二级归结式中的子句比较，得到第三级归结式。(4)如此继续，直到出现了空子句或不能再继续归结为止。只要子句集是不可满足的，上述归结过程一定会归结出空子句而终止。归结的一般过程例：设有子句集：S={P,R,P∨Q,Q∨R}一般归结过程为：S:(1)P(2)R(3)P∨Q(4)Q∨RS1:(5)Q(1)与(3)归结(6)Q

(2)与(4)归结(7)P∨R

(3)与(4)归结S2:(8)R(1)与(7)归结(9)P(2)与(7)归结(10)P(3)与(6)归结(11)R(4)与(5)归结S3:(12)NIL(1)与(9)归结问题：按一般归结过程进行归结时，不仅归结出许多无用子句，而且有些归结式还是重复的，既浪费时间又多占空间。对子句集进行归结时，如何从中找出可进行归结的一对子句。归结策略归结策略大致分为两大类：删除策略基本思想：归结时删除子句集中无用子句，缩小寻找范围，减少比较次数，提高归结效率。纯文字删除法、重言式删除法、包孕删除法。限制策略基本思想：对参加归结的子句进行限制，尽可能减小归结盲目性，使其尽快归结出空子句。支持集策略、线性输入策略、单文字子句策略、祖先过滤形策略归结策略以上列出的是几种最基本的归结策略。注意：具体应用时可组合在一起使用。下面讨论的归结过程都是按广度优先策略进行搜索的，也可用其它策略进行搜索，可根据实际情况决定。归结策略——删除策略1.纯文字删除法定义：如果某文字L在子句集中不存在可与之互补的文字L，则该文字被称为纯文字。显然，归结时纯文字不可能被消去，因而用包含它的子句进行归结时，也不可能得到空子句，因此在不影响子句集不可满足性条件下，可以把包含纯文字的子句从子句集中删去。归结策略——删除策略2.重言式删除法定义：如果一个子句中同时包含互补文字对，则该子句被称为重言式。

重言式是真值为真的子句。对一个子句集来说，增加或删去一个真值为真的子句，不会影响它的不可满足性，因此可从子句集中删去重言式。归结策略——删除策略3.包孕删除法定义：设有子句C1和C2，如果存在一个置换，使得C1C2，则称C1包孕于C2。删去子句集中被包孕的子句，不会影响子句集的不可满足性，因而可从子句集中删去。归结策略——限制策略1.支持集策略支持集策略是沃斯等人在1965年提出的一种归结策略。它对参加归结的子句提出以下限制：每次归结时，父子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后商。可以证明：支持集策略是完备的，即若子句集是不可满足的，则由支持集策略一定可以归结出空子句。归结策略——限制策略例：设有子句集：S={I(x)∨R(x),I(a),R(y)∨L(y),L(a)}其中，I(x)∨R(x)是目标公式否定后得到的子句。用支持集策略进行归结的过程：S:(1)I(x)∨R(x)(2)I(a)(3)R(y)∨L(y)(4)L(a)S1:(5)R(a)

(1)与(2)归结(6)I(x)∨L(x)

(1)与(3)归结S2:(7)L(a)(2)与(6)归结(8)L(a)

(3)与(5)归结(9)I(a)

(4)与(6)归结S3:(10)NIL(2)与(9)归结归结策略——限制策略2.线性输入策略对参加归结的子句的限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。定义：初始子句集是指初始时要求进行归结的子句集。例如：归结反演中，初始子句集就是由已知前提及结论的否定化构成的子句集。线性输入策略可限制生成归结式的数目，具有简单、高效的优点。但它是不完备的。也就是说，即使子句集是不可满足的，用线性输入策略进行归结时不一定能归结出空子句。归结策略——限制策略例：设有子句集：S={I(x)∨R(x),I(a),R(y)∨L(y),L(a)}其中，I(x)∨R(x)是目标公式否定后得到的子句。用线性输入策略进行归结的过程：S:(1)I(x)∨R(x)(2)I(a)(3)R(y)∨L(y)(4)L(a)S1:(5)R(a)

(1)与(2)归结(6)I(x)∨L(x)

(1)与(3)归结(7)R(a)

(3)与(4)归结S2:(8)I(a)(1)与(7)归结(9)L(a)(2)与(6)归结(10)L(a)

(3)与(5)归结(11)I(a)

(4)与(6)归结S3:(12)NIL(2)与(8)归结归结策略——限制策略3.单文字子句策略定义：若一个子句只包含一个文字，称它为单文字子句。单文字子句策略要求参加归结的两个子句中必须至少有一个是单文字子句。用单文字子句策略归结时，归结式比父子句含有较少的文字，有利于朝着空子句的方向前进，因此它有较高的归结效率。当初始子句集中不包含单文字子句时，归结就无法进行。因此，这种归结策略是不完备的。归结策略——限制策略例：设有子句集：S={I(x)∨R(x),I(a),R(y)∨L(y),L(a)}其中，I(x)∨R(x)是目标公式否定后得到的子句。用单文字子句策略进行归结的过程：S:(1)I(x)∨R(x)(2)I(a)(3)R(y)∨L(y)(4)L(a)S1:(5)R(a)

(1)与(2)归结(7)R(a)

(3)与(4)归结S2:(8)I(a)(1)与(6)归结(9)L(a)(3)与(5)归结S3:(12)NIL(2)与(7)归结归结策略——限制策略4.祖先过滤形策略当对两个子句C1和C2进行归结时，只要它们满足下述两个条件中的任意一个就可进行归结：(1)C1与C2中至少有一个是初始子句集中的子句。(2)如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先。一个子句(例如C1)是另一个子句(例如C2)的祖先是指：C2是由Cl与别的子句归结后得到的归结式。该策略与线性输入策略比较相似，但放宽了限制，而且它是完备的。归结演绎推理缺点归结反演中，必须先将谓词公式转化为子句，使得归结演绎推理存在以下缺点：不便于阅读与理解；可能丢失一些重要的控制信息；许多人工智能系统中，知识一般由蕴含式直接表示。归结反演中将它们转化为子句，推理效率较低。针对归结演绎推理存在的上述问题，人们提出了多种非子句定理证明方法：自然演绎推理、尼尔逊提出的基于与／或形的演绎推理等。6.2自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程称为自然演绎推理。基本的推理规则：P规则、T规则、假言推理、拒取式推理P规则：在推理的任何步骤上都可引入前提。T规则：推理时，如果前面步骤中有一个或多个公式永真蕴含公式S，则可把S引入推理过程中。CP规则：如果能从R和前提集合P推出S来，则可从前提集合推出：RS。(详见合式公式性质)伽利略在论证哥白尼的日心说时，使用了如下推理：(1)如果行星系统是以太阳为中心的，则金星会显示出位相变化；(2)金星显示出位相变化；(3)所以，行星系统是以太阳为中心的。6.2自然演绎推理假言推理的一般形式：P,PQQ拒取式推理的一般形式：PQ,QP注意应避免以下两类错误：肯定后件Q的错误否定前件P的错误6.2自然演绎推理例：设已知下列事实：A,B,AC,B∧CD,DQ求证：Q为真。证明：A,ACCB,CB∧CB∧C,B∧CDDD,DQQQ为真P规则和假言推理引入合取词T规则和假言推理T规则和假言推理6.2自然演绎推理例：设已知下列事实：(1)凡是容易的课程小王都喜欢。(2)C班的课程都是容易的(3)ds是C班的一门课程。求证：小王喜欢ds这门课程。证明：定义谓词：EASY(x)x是容易的

LIKE(x,y)x喜欢y

C(x)x是C班的一门课程EASY(x)LIKE(Wang,x)(x)(C(x)EASY(x))C(ds)LIKE(Wang,ds)6.2自然演绎推理(x)(C(x)EASY(x))C(y)EASY(y)C(ds),C(y)EASY(y)EASY(ds)EASY(ds),EASY(x)LIKE(Wang,x)LIKE(Wang,ds)全称固化P规则和假言推理T规则和假言推理6.2自然演绎推理优点：表达定理证明过程自然，容易理解，而且它拥有丰富的推理规则，推理过程灵活，便于在它的推理规则中嵌入领域启发式知识。缺点：容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增。6.3与/或形演绎推理与/或形演绎推理是一种直接的推理方法，基本思想：把有关问题的知识和信息分为规则与事实两类。规则由包含蕴含式的表达式表示。事实由无蕴含式的表达式表示。画出与/或树，然后通过蕴含式进行演绎推理。

推理形式：正向演绎、逆向演绎和双向演绎。6.3.1与/或形正向演绎推理正向演绎推理对应于正向推理，从已知事实出发，反复尝试所有可利用的规则(F规则)进行演绎推理，直至得到某个目标公式的一个终止条件为止。这种推理对已知事实、F规则及目标公式的表示形式都有一定的要求，如果不是所要求的形式，就需要进行变换。6.3.1与/或形正向演绎推理事实表达式的与/或形变换及其与/或树表示F规则的表示形式目标公式的表示形式推理过程含有变量的表达式6.3.1与/或形正向演绎推理一、事实表达式及其与或形表示正向演绎推理要求事实用不包含的与/或形表示。把一个表达式转化为标准的与/或形的步骤如下：(1)利用等价式：PQPQ，消去；(2)把移到每个谓词符号的前面；(3)重新命名变元，使不同量词约束的变元有不同的名字；(4)引人Skolem函数消去存在量词；(5)将公式化为前束形；(6)略去全称量词；(7)重新命名变量，使主要合取式中的变元不同名。过程与化子句集类似，但不必把公式化为子句的合取形式，也不能消去公式中的合取符。标准的与/或形：Q(z,a){[R(y)P(y)]S(a,y)}6.3.1与/或形正向演绎推理根节点：整个表达式叶节点：谓词公式中的单个文字节点：表示事实表达式及其子表达式(x)(y){Q(y,x)[(R(y)P(y))S(x,y)]}Q(z,a){[R(y)P(y)]S(a,y)}Q(z,a)[R(y)P(y)]S(a,y)[R(y)P(y)]S(a,y)[R(y)P(y)]6.3.1与/或形正向演绎推理用与/或树表示事实表达式的重要性质：从与/或树中可以读出由变换表达式得到的一组子句。每个子句是由叶节点组成的公式。每个子句相当于与/或树的一个解图。3个子句：Q(z,a)S(a,y)R(y)S(a,y)P(y)Q(z,a){[R(y)P(y)]S(a,y)}Q(z,a)[R(y)P(y)]S(a,y)[R(y)P(y)]S(a,y)[R(y)P(y)]6.3.1与/或形正向演绎推理二、F规则的表示形式通常，F规则具有以下形式： LW

要求：L是单文字，W是任意的与或形表达式；L、W中所有变元都是量化，默认作用于整个蕴含式。各条规则的变元各不相同，而且规则中的变元与事实表达式中的变量也不相同。6.3.1与/或形正向演绎推理问题：为什么F规则的左部L限制为单文字？

演绎推理时，要用F规则作用于表示事实的与/或树。与/或树的叶节点都是单文字。L为单文字时，可用F规则的左部与叶节点进行匹配，简化规则的应用过程。6.3.1与/或形正向演绎推理若规则(即知识)的表示形式不满足要求，可用如下步骤将其变换成标准形式：(1)暂时消去；(2)把移到每个谓词的前面；(3)引入Skolem函数消去存在量词；(4)将公式化为前束形，并略去全称量词；(5)利用等价关系：P∨QPQ恢复为蕴含式。6.3.1与/或形正向演绎推理三、目标公式的表示形式用子句表示，是文字的析取式，否则要化成子句形式。转化方法同“6.2.1”。6.3.1与/或形正向演绎推理四、推理过程将F规则作用于表示事实的与/或树，改变与/或树结构，产生新的事实，直至推出目标公式，则推理就成功结束。推理过程为：(1)首先用与/或树把已知事实表示出来；(2)用F规则的左部和与/或树的叶节点进行匹配，将匹配成功的F规则加入到与/或树中。(3)重复第(2)步，直到产生一个含有以目标节点作为终止节点的解图为止。6.3.1与/或形正向演绎推理例：设已知事实为：AB，F规则为：ACD，BEG试证明公式：CGABCDEGF规则ABAB已知事实匹配匹配CG证明公式：CG6.3.1与/或形正向演绎推理例：设已知事实为：AB，F规则为：ACD，BEG试证明公式：CG由已知事实、F规则和目标的否定构成的子句集为：

AB

ACADBEBGCG归结反演图ACCGBGABABBNIL6.3.1与/或形正向演绎推理五、含有变量的表达式如果事实表达式、规则和目标表达式中有变量，则在推理中需要用最一般合一进行变元的置换。R16.3.1与/或形正向演绎推理注意：当事实表达式、F规则和目标表达式中包含变量，只有解图中所用置换是一致的，解图对应的子句才成立。P(A)[Q(A)R(A)]P(A)Q(A)R(A)Q(A)R(A)Q(y)N(A)N(z)P(x)S(A)S(z){A/z}{A/z}{A/y}{A/x}R26.3.1与/或形正向演绎推理定义：设有一个置换集U：{u1，u2，…，un}，每个ui是一个置换对的集合，ui={ti1/vi1,ti2/vi2，…，tim(i)/vim(i)}，其中：t为项，v为变量。令：U1=(v11，…，v1m(1)，v21，…，v2m(2)，…，vnm(n))

U2=(t11，…，t1m(2)，t21，…，t2m(2)，…，tnm(n))则置换U一致的充要条件是Ul和U2可合一。U的合一复合u=mgu(Ul，U2)6.3.1与/或形正向演绎推理例1：u1={A/x,A/z}，u2={A/y,A/z}

U={u1，u2}是一致的，其合一复合为{A/x，A/y，A/z}例2：u1={x/y}，u2={y/z}

U={u1，u2}是一致的，其合一复合为{x/y，y/z}例3：u1={A/y}，u2={B/y}

U={u1，u2}是不一致的。例4：u1={f(z)/x}，u2={f(A)/x}

U={u1，u2}是一致的，其合一复合为={f(A)/x，A/z}6.3.2与/或形逆向演绎推理从目标表达式出发，通过逆向使用蕴含式(B规则)进行演绎推理，直到得到包含已知事实的终止条件为止。目标表达式的与/或形变换及其与/或树表示B规则的表示形式已知事实的表示形式推理过程6.3.2与/或形逆向演绎推理一、目标表达式及其与/或树表示将目标表达式转化成无的与或形式，并用与/或树表示，转化过程与正向演绎中对事实表达式的变换相似。6.3.2与/或形逆向演绎推理不同处：用约束的变元的Skolem函数替换，由约束的相应变元，然后略去，再消去。

例：目标表达式：(y)(x){P(x)[Q(x,y)∧(R(x)∧S(y))]}与/或形：P(f(z))∨{Q(f(y),y)∧[(R(f(y))∨S(y)]}与/或图中的n连接符把具有合取关系的子表达式连接起来，而在正向演绎中是把具有析取关系的子表达式连接起来。主要的析取式具有不同的变量名6.3.2与/或形逆向演绎推理目标表达式：(y)(x){P(x)[Q(x,y)(R(x)S(y))]}与/或形：P(f(z)){Q(f(y),y)[(R(f(y))S(y)]}P(f(z)){Q(f(y),y)[(R(f(y))S(y)]}(R(f(y))P(f(z))Q(f(y),y)[(R(f(y))S(y)]Q(f(y),y)(R(f(y))S(y)S(y)6.3.2与/或形逆向演绎推理二、B规则的表示形式B规则的表示形式为：WL其中：W为任一与/或形式表达式，L为单一文字。6.3.2与/或形逆向演绎推理B规则：WLL限制为单一文字。推理时要用L与目标树中的叶节点匹配，而叶节点是文字，这样可简化B规则对与/或树的应用。如果规则不符合这一要求，则要变换成这种形式。例：规则WL1L2转化为两个B规则：WL1，WL2规则中应Skolem化量化的变量，并略去，即规则中尚存的变量都是量化的变量。6.3.2与/或形逆向演绎推理三、已知事实的表示形式

文字的合取式，可表示为文字的集合。对任一事实表达式，应当用Skolem函数代替事实表达式中量化的变量，并略去量化的变量，将表达式转化成标准的文字合取式。6.3.2与/或形逆向演绎推理四、推理过程(1)用与/或树将目标表达式表示出来。(2)用B规则的右部和与/或树的叶节点进行匹配，并将匹配成功的B规则加入到与/或树中。一条规则可用多次，每次应使用不同的变量。当一个事实文字和与/或树中的一个文字可以合一时，可将该事实文字通过匹配弧连接到与/或树中相应的文字上，匹配弧应标明两个文字的最一般合一。(3)重复进行第(2)步，直到产生某个终止在事实节点上的一致解图。一致解图：推理时所用的置换是一致的。问题：是否存在一只猫和一只狗，试这只猫不怕这只狗？CAT