《人工智能ppt课件 第四章 确定性推理.ppt》由会员分享，可在线阅读，更多相关《人工智能ppt课件 第四章 确定性推理.ppt（168页珍藏版）》请在三一办公上搜索。
1、2022/12/11,1,第4章 确定性推理,本章介绍： 自然演绎推理 归结演绎推理,推理就是按某种策略由已知判断推出另一判断的思维过程已知判断：包括已掌握的与求解问题有关的知识 及关于问题的已知事实 推理的结论：由已知判断推出新判断推理由程序程序实现，称为推理机,2022/12/11,2,1、演绎推理、归纳推理、默认推理推理的基本任务是从一种判断推出另一种判断按判断推出的途径来划分，可分为演绎推理、归结推理及默认推理（1）演绎推理演绎推理是从全称判断推导出特称判断或单称判断的过程演绎推理有多种形式，经常用的是三段论式三段论式包括大前提：已知的一般性知识或假设小前提：关于所研究的具体情况或个别
2、事实的判断结论：由大前提推出的适合于小前提所示情况的新判断,4.1 推理技术概述,2022/12/11,3,在任何情况下，由演绎推导出的结论都是蕴涵在大前提的一般性知识中只要大前提和小前提是正确的，则由它们推出的结论必然是正确的(2) 归纳推理归纳推理是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理归纳推理：完全归纳推理、不完全归纳推理完全归纳推理是在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性不完全归纳推理是指只考察了相应事物的部分对象就得出了结论,2022/12/11,4,枚举归纳推理：若已知某类事物的有限可数
3、个具体事物都具有某种属性，则可推出该类事物都具有此属性类比推理：在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种推理(3) 默认推理又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理摆脱了需要知道全部事实才能进行推理的需求，使得在知识不完全的情况下也能进行推理,2022/12/11,5,2、确定性推理、不确定性推理按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理确定性推理：推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或为假，没有第三种情况出现不确定性推理：推理时所用的知识不都是精确的，推出的结论也
4、不完全是肯定的，真值位于真与假之间，命题的外延模糊不清,2022/12/11,6,3、单调推理、非单调推理按推理过程中推出的结论是否单调地增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调推理单调推理：在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况非单调推理：在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始,2022/12/11,7,4.2 自然演绎推理,定义：自然演绎推理是指从一组已知的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程
5、。 推理规则：P规则：在推理的任何步骤上都可引入前提T规则：推理时，如果前面步骤中有一个或多个公式永真蕴涵公式S，则可把S引入推理过程中。CP规则：如果能从R和前提集合中推出S来，则可从前提集合推出 来。反证法： ，当且仅当 。即：Q为P的逻辑结论，当且仅当 是不可满足的。,2022/12/11,8,假言推理 表示：由 及P为真，可推出Q为真 拒取式推理 表示：由 为真及Q为假，可推出P为假,2022/12/11,9,避免产生两类错误：肯定后件(Q)的错误：希望通过肯定后件Q推出前件P为真否定前件(P)的错误：希望通过否定前件P推出后件Q为假,2022/12/11,10,例： 设已知事实 （1
6、）只要不怕困难的人，就会获得胜利。 （2）运动员都是不怕困难的人。 （3）王力是运动员。 求证：王力会获得胜利。,2022/12/11,11,自然演绎推理的优缺点优点： 定理证明过程自然，容易理解，而且它拥有丰富的推理规则，推理过程灵活，便于在它的推理规则中嵌入领域启发式知识。缺点： 容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增。,2022/12/11,12,1、合式公式的定义合式公式适合于一阶谓词逻辑遵从以下递归方式定义的逻辑语句称为合式公式单一谓词公式是合式公式；若A是合式公式，则A也是合式公式；若A和B都是合式公式，则AB、 AB、 AB和AB也都是合式公式；若A是合式公
7、式，x是约束变量，则(x)A和(x)A也都是合式公式；只有按上述规则-求得的公式，才是合式公式。连词优先级别是，、，、，但可通过括号改变优先级。,4.3 合式公式,一、合式公式,2022/12/11,13,一、合式公式,1、合式公式的定义例2、“所有人(Person)都喜欢(Like)一种游戏(Game)”谓词公式Person(x)Like(x,y)Game(y)量词(x)Person(x)表示所有人；(y)Game(y)表示一种游戏；合式公式(x)(y)Person(x)Game(y)Like(x,y),2022/12/11,14,一、合式公式,2、合式公式的解释命题逻辑不存在变量给命题中包
8、含的各个原子公式指派真值（T或F），称这种指派为命题的一个解释；解释确定后，可依据连接原子公式的连词的作用求出命题的真值（T或F）。谓词逻辑涉及变量不可能直接给原子公式指派真值；定义一个拟观察个体的可能论域；确定原子公式中变量项和函数项在论域中的取值；给原子公式指派真值。解释确定后，可依据连接原子公式的连词的作用求出合式公式的真值（T或F）。,2022/12/11,15,一、合式公式,2、合式公式的解释例3、合式公式(x)(y)P(x)Q(f(x),y)一个解释的建立。设定论域D=1,2; xD,yD对于x的每个取值函数f(x)：f(1)=2,f(2)=2;对于x的每个取值原子公式P(x)：P
9、(1)=T,P(2)=T；对于f(x)和y的每个取值组合(只有2个：2、1；2、2)原子公式Q(f(x),y)：Q(2,1)=T, Q(2,2)=F；上述指派就确定了该合式公式的一个解释；在这个解释下，合式公式有真值T；,2022/12/11,16,一、合式公式,3、合式公式的永真性和可满足性(1)合式公式的永真性若P在某个论域D上的所有可能的解释都有真值T，则称P在D上是永真的；若P在每个可能的非空论域D上均永真，则称P是永真的。(2)合式公式的可满足性若P在某个论域D上的至少可以建立一个解释，使P有真值T，则称P在D上是可满足的；若至少有一个非空论域D使P可满足，则称P是可满足的。(3)合
10、式公式的永假性若P在某个论域D上的所有可能的解释都有真值F，则称P在D上是永假的；若P在每个可能的非空论域D上均永假，则称P是永假的。,2022/12/11,17,一、合式公式,3、合式公式的永真性和可满足性论域个数较少，每个论域较小易判断合式公式的永真性和可满足性；论域个数较多，每个论域较大，解释个数有限永真性和可满足性总是可判断的；解释个数无限不能确保可判断；不能确保在有限的时间内判断。,2022/12/11,18,一、合式公式,4、合式公式的性质合式公式优点：具有强大的形式化表示功能；合式公式缺点：包括了多种连词和量词以及它们的嵌套应用，表示形式过于复杂；不利于演绎推理系统的设计和高效运
11、作。化简合式公式到某些约定的标准形式是很有意义。合取范式析取范式合式公式的性质则为化简工作提供了依据。,2022/12/11,19,一、合式公式,4、合式公式的性质十种常用性质(1)双重否定：(P) P(2)蕴涵式转化：P Q P Q(3)狄.摩根定律：(P Q) P Q(P Q) P Q(4)分配律P (Q R) (P Q) (P R) P (Q R) (P Q) (P R)(5)交换律P Q Q PP Q Q P(6)结合律(P Q) R P (Q R)(P Q) R P (Q R),2022/12/11,20,一、合式公式,4、合式公式的性质十种常用性质(7)逆否律P Q Q P(8)量
12、词否定(x) P(x) (x) (P(x) (x) P(x) (x) (P(x) (9)量词分配(x) P(x) Q(x) (x)P(x) (x) Q(x)(x) P(x) Q(x) ( x)P(x) ( x) Q(x) (10)约束变量的虚元化约束变量名的变换不影响合式公式的真值(x) P(x) (y) P(y) (x) P(x) (y) P(y),2022/12/11,21,一、合式公式,4、合式公式的性质(9)量词分配(x) P(x) Q(x) (x)P(x) (y) Q(y)(x) P(x) Q(x) ( x)P(x) ( y) Q(y) (10)约束变量的虚元化约束变量名的变换不影响
13、合式公式的真值(x) P(x) (y) P(y) (x) P(x) (y) P(y),2022/12/11,22,二、合式公式的标准化,1、标准化需求常见的基于谓词演算的推理：归结反演、(正向/逆向)演绎推理要求以量词前束范式来表示合式公式量词前束范式形式如下：(Q1x1) (Q2x2)(Qkxk)M，其中M 母式，不包括任何量词；QixiQi可以是量词符号或；xi是量词的约束变量(i=1,2,k)归结反演（4.5.5，2.3.3）要求M标准化为合取范式，定义如下：M=W1W2 WnWi=Li1Li2 Lim(i=1,2,n)Lij=Pij|Pij:文字（Literal），是谓词公式Pij或其
14、取反,2022/12/11,23,二、合式公式的标准化,1、标准化需求常见的基于谓词演算的推理：归结反演、规则演绎要求以量词前束范式来表示合式公式量词前束范式形式如下：(Q1x1) (Q2x2)(Qkxk)M归结反演要求M标准化为合取范式，定义如下：M=W1W2 WnWi=Li1Li2 Lim(i=1,2,n)Lij=Pij|Pij:文字（Literal），是原子谓词公式Pij或其取反析取范式定义：M=W1W2WnWi=Li1Li2Lim(i=1,2,n)Lij=Pij|Pij:文字（Literal），是原子谓词公式Pij或其取反,2022/12/11,24,定义 设F为一谓词公式，如果其中的
15、所有量词均非否定地出现在公式的最前面，而它们的辖域为整个公式，则称F为前束范式(prenex normal form)。一般地，前束范式可以写成:其中 为前缀， 是一个由全称量词或存在量词组成的量词串， 为母式，它是一个不含任何量词的谓词公式。,前束标准型,在一阶逻辑中，为了简化定理证明程序需要引入所谓的“前束标准型”。,2022/12/11,25,下面是一些前束范式的例子： 为了把一个公式化为前束范式，首先看一下包含一阶逻辑特有的等价式对，如下所示。,前束标准型,2022/12/11,26,在上述等价公式对中，F(x)和 H(x)都表示含未量化变量x的公式，G表示不含未量化变量x的公式，Q1
16、,Q2 或为 或为。 对(3)和(4)，要求z不出现在F(x) 中，并且符合约束变量的换名原则。,前束标准型,2022/12/11,27,使用前面定义的等价式，总可以把一个公式化为前束标准型。 变换过程如下： (1) 使用等价式中的连接词转化规律消去公式中的连接词, 。 (2) 反复使用双重否定律和德摩根律将“(或)”移到原子之前。 (3) 必要时重新命名量化的变量。 (4) 使用量词分配律和等价式，把所有量词都移到整个公式的最左边以得出一个范式。,前束标准型,2022/12/11,28,二、合式公式的标准化,2、合取范式的标准化过程应用合式公式性质将公式逐步转化的过程。转化步骤没有严格的规定
17、较合理的化简过程，分为8步：消去多余的量词（很少出现）；消去蕴涵符号；内移否定符号；变量换名；消去存在量词；全称量词前束化；消去全称量词；把母式转化为合取范式。,2022/12/11,29,二、合式公式的标准化,2、合取范式的标准化过程消去多余的量词（很少出现）若一个量词的辖域内并未出现量词的约束变量，则该量词是多余的，应该删除；例，(x)P(y)，则(x)可以消去，得到P(y)；正常情况下，合式公式中不应出现多余的量词。消去蕴涵符号蕴涵式转化：P Q P Q；例， Q(x,y) P(y) Q(x,y) P(y)。,2022/12/11,30,二、合式公式的标准化,2、合取范式的标准化过程内移
18、否定符号使否定只出现在原子谓词公式前，构成否定文字；狄.摩根定律：(P Q) P Q(P Q) P Q双重否定：(P) P量词否定：(x) P(x) (x) (P(x) (x) P(x) (x) (P(x) 例， (y)P(y)P(f(x,y)(y)P(y)P(f(x,y)变量换名“全称量词前束化”后，同名变量的辖域无法区分，所以为避免差错，必须换名；约束变量的虚元性进行变换；(x) P(x) (y) P(y) (x) P(x) (y) P(y),2022/12/11,31,消去存在量词,Skolem标准化过程,Step1: 化成前束范式:,Step2: 使用下述方法可以消去前缀中存在的所有量
19、词： 令 是 中出现的存在量词 。,Case1: 若在 之前不出现全称量词，则选择一个与M中出现的所有常量都不相同的新常量c，用c代替M中出现的所有xr，并且由前缀中删去(Qrxr) 。,Case2: 若在 之前出现全称量词 ，则选择一个与M中出现的任一函数符号都不相同的新m元函数符号f，用 代替M中的所有xr ，并且由前缀中删去(Qrxr) 。,按上述方法删去前缀中的所有存在量词之后得出的公式称为合式公式的Skolem标准型。替代存在量化变量的常量c(视为0元函数)和函数f称为Skolem函数。,2022/12/11,32,在公式中， 的前面没有全称量词， 的前面有全称量词 和 , 在 的前
20、面有全称量词 ， 和 。所以，在 中，用常数a代替x, 用二元函数f(y,z)代替u, 用三元函数g(y,z,v)代替w,去掉前缀中的所有存在量词之后得出Skolem标准型：,例题分析,例4.1 化公式,为Skolem标准型。,2022/12/11,33,二、合式公式的标准化,2、合取范式的标准化过程消去存在量词在的辖域内(z)(w)Q(x,z) P(z,w)w依赖于z，由函数w=g(z)来定义这种依赖关系；用g(z)来取代约束变量w，消去存在量词w；(z)Q(x,z) P(z,g(z)在多个的辖域内(x)(y)(z)(w)P(x,y,z,w)用多元函数g(x,y,z)来取代约束变量w，消去存
21、在量词w；(x)(y)(z)P(x,y,z,g(x,y,z)在的辖域外(w)(z) Q(x,z) P(z,w)用任意常量A取代约束变量w，消去存在量词w(z) Q(x,z) P(z,A),2022/12/11,34,二、合式公式的标准化,2、合取范式的标准化过程全称量词前束化经过“变量换名”后，所有量词的约束变量均有不同的名字；只要简单地将移到合式公式的最前面；约束变量的作用范围不会变化。消去全称量词经过“消去存在量词”后，所有变量均受的约束；简单地删除，只留下母式。把母式转化为合取范式分配律： P (Q R) (P Q) (P R),2022/12/11,35,二、合式公式的标准化,2、合取
22、范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y) P(f(x,y)(y)(w)Q(x,y)P(y,w),2022/12/11,36,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y) P(f(x,y)(y)(w)Q(x,y)P(y,w)消去蕴涵符号(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w),2022/12/11,37,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w)内移否定符号(x)P(x)(y)P(y)P
23、(f(x,y)(y)(w)Q(x,y)P(y,w),2022/12/11,38,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w)变量换名(x)P(x)(y)P(y)P(f(x,y)(z)(w)Q(x,z)P(z,w),2022/12/11,39,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y)P(f(x,y)(z)(w)Q(x,z)P(z,w)消去存在量词P(A)(y)P(y)P(f(A,y)(z)Q(A,z)P(z,g(z),2022/12/11,40,
24、二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式P(A)(y)P(y)P(f(A,y)(z)Q(A,z)P(z,g(z)全称量词前束化(y)(z)P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z),2022/12/11,41,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(y)(z)P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z)消去全称量词P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z),2022/12/11,42,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式P(A)P(y)P(f(A,y)Q(A,z)P
25、(z,g(z)把母式转化为合取范式P(A)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z),完成标准化过程！,2022/12/11,43,4.4 归结演绎推理,自动定理证明一般表示形式为：F1F2FnWF1, F2, ,Fn都是合式公式，表示公理或事实；W是合式公式，表示待证明的定理，称为目标公式；证明的方法可分两大类：演绎法直接证明F1F2FnW为永真；反证法间接证明(F1F2FnW)为永假；证明F1F2Fn W的永假即F1, F2, ,Fn W是一个矛盾集。,4.4 归结演绎推理,2022/12/11,44,4.4 归结演绎推理,海伯伦（Herbrand）提
26、出的H域（海伯伦域）和海伯伦定理；为自动定理证明奠定了理论基础；鲁宾逊（Robinson）提出的归结原理；使自动定理证明成为可能。,2022/12/11,45,4.4 归结演绎推理1）H域和海伯伦定理（了解）,1、子句和子句集子句仅由文字的析取构成的合式公式Wi=Li1Li2 Lim称为子句；合取范式定义：M=W1W2 WnWi=Li1Li2 Lim(i=1,2,n)Lij=Pij|Pij:文字（Literal），是原子谓词公式Pij或其取反合取范式可定义为子句的合取 ；合取范式表示为子句集，子句间隐含合取关系子句集W1,W2,Wn,2022/12/11,46,4.4 归结演绎推理1）H域和海
27、伯伦定理,1、子句和子句集子句仅由文字的析取构成的合式公式合取范式表示为子句集，子句间隐含具有合取关系P(A)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z)可进一步表示为子句集P(A),P(y)Q(A,z)P(z,g(z),P(f(A,y)Q(A,z)P(z,g(z),2022/12/11,47,4.4 归结演绎推理1）H域和海伯伦定理,1、子句和子句集子句仅由文字的析取构成的合式公式合取范式表示为子句集，子句间隐含具有合取关系(y) (z)P(A)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z)量词分配：(x) P(x) Q(
28、x) (x)P(x) (x) Q(x)(y) (z)P(A) (y) (z)P(y)Q(A,z)P(z,g(z) (y) (z)P(f(A,y)Q(A,z)P(z,g(z),2022/12/11,48,4.4 归结演绎推理1）H域和海伯伦定理,1、子句和子句集子句中的变量都是的约束变量(y) (z)P(A),(y) (z)P(y)Q(A,z)P(z,g(z),(y) (z)P(f(A,y)Q(A,z)P(z,g(z)为了消除子句间不必要的交互作用，保持子句的独立性，需要做变量换名P(A),P(y1)Q(A,z1)P(z1,g(z1),P(f(A,y2)Q(A,z2)P(z2,g(z2),202
29、2/12/11,49,例4.2 将合式公式化为子句形。解：（1）消去蕴涵符号：这可以利用等价式：得到：x(P(x)yP(y) P(f(x,y)yQ(x,y) P(y)（2）减少否定符号的辖域，把“ ”移到紧靠谓词的位置上：这可以利用下述等价式：,例题,2022/12/11,50,得到： x(P(x)yP(y) P(f(x,y)yQ(x,y) P(y)（3）变量标准化：重新命名变元名，使不同量词约束的变元有不同的名字：xP(x)yP(y)P(f(x,y)wQ(x,w) P(w)（4）消去存在量词： xP(x)yP(y)P(f(x,y)Q(x,g(x) P(g(x),2022/12/11,51,（
30、5）化为前束形： xyP(x) P(y)P(f(x,y)Q(x,g(x)P(g(x)（6）把母式化为合取范式： x yP(x) P(y)P(f(x,y)P(x) Q(x,g(x) P(x) P(g(x)（7）消去全称量词和合取连接词： P(x) P(y)P(f(x,y) P(x) Q(x,g(x) P(x) P(g(x),2022/12/11,52,（8）更改变量名，有时称为变量分离标准化。于是有： 必须指出: 一个子句内的文字可以含有变量，但这些变量总是被理解为全称量词量化了的变量。,2022/12/11,53,4.4 归结演绎推理1）H域和海伯伦定理,1、子句和子句集,合式公式F,合取范式
31、,子句集S,合式公式F永假,子句集S的不可满足性,充分必要条件,重要性质,S的不可满足性任意论域D上的任意解释I,S中都至少有一个子句真值为F,2022/12/11,54,4.4 归结演绎推理1）H域和海伯伦定理,1、子句和子句集,合式公式F,合取范式,子句集S,合式公式F永假,子句集S的不可满足性,充分必要条件,合式公式F,子句集S,不等价,S是F的特例,重要性质,S的不可满足性任意论域D上的任意解释I,S中都至少有一个子句真值为F,2022/12/11,55,4.4 归结演绎推理1）H域和海伯伦定理,2、H域（了解）证明子句集S的不可满足性与证明合式公式永真性类似由于个体论域的任意性和解释
32、个数的无限性，使得证明工作十分困难。若能建造一个较为简单的特殊论域，使得只要证明子句集S在该域不可满足，就可确保子句集在任何可能的论域上不可满足，将是十分有意义的！海伯伦建立的特殊域H就具有这样的性质。H域性质对于子句集S的任一可能论域D上的任一解释I，总能在S的H域上构造一个相应的解释I*，使子句集S具有相同的真值。证明子句集S的不可满足性确定子句集S在H域上的所有解释都不可满足。,2022/12/11,56,4.4 归结演绎推理1）H域和海伯伦定理,3、海伯伦定理（了解）子句集S中一子句包含的变量用H域中元素取代后，产生的子句称为基子句。海伯伦定理：子句集S不可满足的充要条件是存在一个有限
33、的不可满足的基子句集S。,有限的不可满足的基子句集S,子句集S不可满足性,充分必要条件,2022/12/11,57,4.4 归结演绎推理2）归结原理,动机为提高判定子句集S不可满足的有效性，鲁宾逊于1965年提出了归结(Resolution)原理，也称为消解原理。归结原理简单易行，便于计算机实现和执行，从而使定理的机器自动证明成为现实，也成为人工智能技术实用化的一次重要突破。,2022/12/11,58,4.4 归结演绎推理2）归结原理,1、归结方法(1)归结式（消解式*）设有两个子句C1=LC1、 C2=LC2从C1和C2中消去互补文字L和L；C1和C2通过组成新的子句C=C1 C2；称C为
34、C1和C2的归结式（消解式*）；例4、两个子句C1=P(A)Q(x)R(f(x)C2=P(A)Q(y)R(y)消去互补文字P(A)和P(A)后，生成归结式：C12= Q(x) R(f(x) Q(y) R(y),C1,C2,2022/12/11,59,4.4 归结演绎推理2）归结原理,1、归结方法(2)归结式性质定理：两个子句C1和C2的归结式C是C1和C2的逻辑推论任一使子句C1和C2为真的解释I，必使归结式C为真；归结式C为假的解释I，子句C1或者C2为假；推论：设C1 和C2 是子句集S中的两个子句，并以C作为它们的归结式；通过往S中加入C而产生的扩展子句集S与子句集S在不可满足的意义上是
35、等价的！,扩展子句集S,子句集S,不可满足性等价,2022/12/11,60,4.4 归结演绎推理2）归结原理,1、归结方法(3)空子句设C1=L、 C2=L，则归结式C为空；以表示为空的归结式C，并称C=为空子句；因为C1和C2是一对矛盾子句，不可同时满足，所以是不可满足的子句；通过往S中加入而产生的扩展子句集S不可满足；空子句是用归结原理判定子句集S不可满足的成功标志。,扩展子句集S,子句集S,不可满足性等价,2022/12/11,61,4.4 归结演绎推理2）归结原理,动机为提高判定子句集S不可满足的有效性，鲁宾逊于1965年提出了归结(Resolution)原理，也称为消解原理。归结原
36、理简单易行，便于计算机实现和执行，从而使定理的机器自动证明成为现实，也成为人工智能技术实用化的一次重要突破。基本思路通过归结方法不断扩充待判定的子句集S，并设法使其包含进指示矛盾的空子句。空子句是不可满足（即永假）的子句；,2022/12/11,62,4.4 归结演绎推理2）归结原理,2、归结推理过程归结演绎树(1)命题逻辑中的归结推理过程子句中文字只是原子命题公式或其取反，不带变量；易于判别哪些子句对包含互补文字；例5、子句集S=PQ, PR, Q, R的归结演绎树。,2022/12/11,63,4.4 归结演绎推理2）归结原理,2、归结推理过程(1)命题逻辑中的归结推理过程例5、子句集S=
37、PQ, PR, Q, R的归结演绎树。,扩展子句集S包含空子句,子句集S不可满足,2022/12/11,64,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程子句中含有变量，不能直接发现和消去互补文字；需对潜在的互补文字先作变量置换和合一处理。变量置换：用置换项取代公式中的变量；置换项可以是变量、常量或函数。置换元素t/v（置换项/变量）置换若干置换元素的集合；合一处理：,P(x, y, x, g(x), P(A, B, A, z),2022/12/11,65,P(x, y, x, g(x), P(A, B, A, z)我们可以为它们建立多个置换：S1 = A/
38、x, B/y, g(x)/z S2 = f(w)/x, z/y, C/zS3 = B/x, f(w)/y, y/z置换结果为：P(x, y, x, g(x), P(A, B, A, z)S1 =P(A, B, A, g(A), P(A, B, A, g(A) P(x, y, x, g(x), P(A, B, A, z)S2 =P(f(w), z, f(w), g(f(w), P(A, B, A, C) P(x, y, x, g(x), P(A, B, A, z)S3=P(B, f(w), B, g(B), P(A, B, A, y),S1使潜在的互补文字中的原子谓词公式变为同一，确认互补性。,
39、2022/12/11,66,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程子句中含有变量，不能直接发现和消去互补文字；需对潜在的互补文字先作变量置换和合一处理。变量置换：用置换项取代公式中的变量；置换项可以是变量、常量或函数。置换元素t/v（置换项/变量）置换若干置换元素的集合；合一处理：通过多个变量置换，使相应于潜在互补文字的原子谓词公式同一化的过程。,P(x, y, x, g(x), P(A, B, A, z),2022/12/11,67,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程通过一个匹配过程去检查两个原子谓词公式
40、的可合一性，并同时建立用于实现合一的置换。【匹配过程】两个原子谓词公式必须具有相同的谓词（符号) 和参数项个数；从左到右逐个检查每对参数项的可合一性；若每对参数项都可合一，则合一处理成功，并建立用于实现合一的置换。,2022/12/11,68,4.4 归结演绎推理2）归结原理,【匹配过程】从左到右逐个检查每对参数项的可合一性；参数对中有一个是变量v（不关心另一个t是否是变量）v初次出现，参数对可合一，以另一参数t为置换项，构成置换元素t/v;v出现过，则已建立相应的置换元素t/v ，取其置换项t，检查是否与另一参数t合一；若不合一，则处理失败；参数对中没有变量，则必须相同，否则合一处理失败。,
41、2022/12/11,69,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程匹配过程的例子P(x, y, x, g(x), P(A, B, A, z)两个原子谓词公式必须具有相同的谓词和参数项个数；从左到右逐个检查每对参数项的可合一性；x和A，x初次出现，可合一，建立置换元素A/x;y和B，y初次出现，可合一，建立置换元素B/y;x和A， x出现过，已经建立置换元素A/x，可合一；g(x)和z，z初次出现，可合一，建立置换元素g(x)/z；若每对参数项都可合一，则合一处理成功。建立置换S1=A/x, B/y, g(x)/z,2022/12/11,70,4.4 归
42、结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程谓词逻辑中子句归结的例子： C1=P(x,y) Q(x,f(x) R(x,f(y)C2=P(A,B) Q(z,f(z) R(z,f(z)L11=P(x,y)和L12= P(A,B)是潜在的互补文字L11和L12是可合一的；建立置换S1=A/x,B/y消去互补文字L11和L12后，得归结式：Q(A,f(A) R(A,f(B) Q(z,f(z) R(z,f(z)变量的置换必须在整个子句范围内进行,2022/12/11,71,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程谓词逻辑中子句归结的例子：
43、 C1=P(x,y) Q(x,f(x) R(x,f(y)C2=P(A,B) Q(z,f(z) R(z,f(z)L12=Q(x,f(x)和L22=Q(z,f(z)是潜在的互补文字L12和L22是可合一的；建立置换S2=z/x消去互补文字L12和L22后，得归结式：P(z,y) R(z,f(y) P(A,B) R(z,f(z),2022/12/11,72,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程谓词逻辑中子句归结的例子： C1=P(x,y) Q(x,f(x) R(x,f(y)C2=P(A,B) Q(z,f(z) R(z,f(z)L11=P(x,y)和L12=
44、 P(A,B)是互补文字L12=Q(x,f(x)和L22=Q(z,f(z)是互补文字两个子句可以有多于一对的互补文字,2022/12/11,73,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程,2022/12/11,74,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程,2022/12/11,75,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程,2022/12/11,76,4.4 归结演绎推理2）归结原理,2、归结推理过程(2)谓词逻辑中的归结推理过程,子句集S不可满足,2022/12/11,7
45、7,4.4 归结演绎推理2）归结原理,2、归结推理过程(3)归结演绎的完备性基于归结的演绎推理是完备的若子句集S不可满足，就必定存在一个从S到空子句的归结演绎；反之，若存在一个从S到空子句的归结演绎，则S必定是不可满足的；子句集S是永真的和可满足的，归结原理判定过程将无休止地进行下去，得不到任何结果。,2022/12/11,78,4.4 归结演绎推理 3）归结反演,归结演绎推理为反证法证明定理提供了有效手段。应用归结演绎推理的定理证明为归结反演。教学要求掌握主要内容掌握归结反演方法和提取问题回答技术；学会建立归结反演树和修改证明树。学习难点从以自然语言表示的事实集证明目标公式（定理）并提取回答
46、的综合题。,2022/12/11,79,4.4 归结演绎推理 3）归结反演归结反演系统,归结反演的基本思路：要从作为事实的公式集F证明目标公式W为真；先将W取反W ，加入公式集F；标准化FW为子句集S；通过归结演绎证明S不可满足，得出W为真的结论。归结反演系统组成：标准化部件将FW标准化为子句，并合并为子句集S；归结演绎部件按照归结演绎推理，控制定理证明的全过程。,2022/12/11,80,4.4 归结演绎推理 3）归结反演归结反演系统,例6、归结反演的应用食物问题已知下列事实为真T，王(Wang)喜欢(Like)所有种类的食物(Food)。苹果(Apples)是食物。任何一个东西，若任何人
47、吃了(Eat)它都不会被害死(Killed)，则该东西是食物。李(Li)吃花生(Peanuts)且仍然活着(Alive)。张(Zhang)吃任何李吃的东西。证明：王喜欢花生。,2022/12/11,81,4.4 归结演绎推理 3）归结反演归结反演系统,例6、归结反演的应用食物问题形式化把以自然语言表示的事实和要证明的目标形式化地表示为合式公式。王(Wang)喜欢(Like)所有种类的食物(Food)。(x)Food(x) Like(Wang,x)苹果(Apples)是食物。Food(Apples)任何一个东西，若任何人吃了(Eat)它都不会被害死(Killed)，则该东西是食物。(x)(y)E
48、at(y,x) Killed(y) Food(x)(x)(y)Eat(y,x) Alive(y) Food(x)李(Li)吃花生(Peanuts)且仍然活着(Alive)。Eat(Li,Peanuts) Alive(Li)张(Zhang)吃任何李吃的东西。(x)Eat(Li,x) Eat(Zhang,x)王喜欢花生。Like(Wang,Peanuts),减少谓词数,2022/12/11,82,4.4 归结演绎推理 3）归结反演归结反演系统,例6、归结反演的应用食物问题标准化将事实公式和取反后的目标公式分别标准化为子句，并组成子句集S。王(Wang)喜欢(Like)所有种类的食物(Food)。(
49、x)Food(x) Like(Wang,x)Food(x1)Like(Wang,x1)苹果(Apples)是食物。Food(Apples)Food(Apples)任何一个东西，若任何人吃了(Eat)它都不会被害死(Killed)，则该东西是食物。(x)(y)Eat(y,x) Alive(y) Food(x) Eat(y,x2) Alive(y) Food(x2),2022/12/11,83,4.4 归结演绎推理 3）归结反演归结反演系统,例6、归结反演的应用食物问题标准化将事实公式和取反后的目标公式分别标准化为子句，并组成字句集S。李(Li)吃花生(Peanuts)且仍然活着(Alive)。E
50、at(Li,Peanuts) Alive(Li)Eat(Li,Peanuts)Alive(Li)张(Zhang)吃任何李吃的东西。(x)Eat(Li,x) Eat(Zhang,x) Eat(Li,x3) Eat(Zhang,x3)王喜欢花生。Like(Wang,Peanuts) Like(Wang,Peanuts)取反,2022/12/11,84,4.4 归结演绎推理 3）归结反演归结反演系统,例6、归结反演的应用食物问题归结演绎应用归结演绎推理不断生成归结式以扩展子句集S，直到生成空子句。,2022/12/11,85,4.4 归结演绎推理 3）归结反演归结反演系统,例6、归结反演的应用食物问
