第三章 经典逻辑推理.ppt

1、确定性推理,第三章,要求,掌握谓词公式的概念及可满足性的定义，理解置换与合一的概念，掌握求取最一般合一置换的方法,掌握归结原理及归结推理方法。掌握Skolem标准式和子句集的求取方法，理解谓词公式和子句集在不可满足意义下的一致性，理解Herbrand定理，掌握H域、原子集、H域上的解释求法，掌握命题逻辑和谓词逻辑中的归结原理,掌握利用归结原理进行定理证明的方法 掌握应用归结原理进行问题求解的方法 掌握归结过程中的控制策略,3.4 归结演绎推理,4,3.1 基本概念,3.1.1 推理的基本概念,按某种策略由已知判断推出另一判断的思维过程,推理,已知判断,掌握的与求解问题有关的知识及关于问题的已知

2、事实,推理的结论,由已知判断推出新判断,推理机,推理由程序程序实现，称为推理机,从一种判断推出另一种判断,3.1.2 推理方式及其分类,推理的基本任务,推理的逻辑基础,演绎推理,归纳推理,默认推理,推理的分类,演绎推理,从全称判断推导出特称判断或单称判断的过程,三段论式 演绎推理,在任何情况下，由演绎推导出的结论都是蕴涵在大前提的一般性知识中 只要大前提和小前提是正确的，则由它们推出的结论必然是正确的,推理过程,结论：由大前提推出的适合小前提情况的新判断,小前提：关于所研究的具体情况或个别事实的判断,大前提：已知的一般性知识或假设,完全归纳推理,不完全归纳推理,归纳推理,在进行归纳时考察了相应

3、事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性,只考察了相应事物的部分对象就得出了结论,枚举归纳推理：若已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此属性,类比推理：在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种推理,从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理,归纳推理,默认推理,摆脱了需要知道全部事实才能进行推理的需求，使得在知识不完全的情况下也能进行推理,又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理,默认推理,推理,按推理时所用知识的确定

4、性来划分,推理,按推理过程中推出的结论是否单调地增加,一个思维过程，即求解问题的过程,推理过程,推理的 控制策略,推理方向,搜索策略,冲突消解策略,求解策略,限制策略,3.1.3 推理的控制策略,3.1.3 推理的控制策略,正向推理,以已知事实作为出发点的一种推理，又称为数据驱动推理、前向链推理、模式制导推理及前件推理,反向推理,以某个假设目标为出发点的一种推理，又称为目标驱动推理、逆向链推理、目标制导推理及后件推理,1.推理方向,3.1.3 推理的控制策略,混合推理,已知的事实不充分。通过正向推理先把其运用条件不能完全匹配的知识都找出来，并把这些知识可导出的结论作为假设，然后分别对这些假设进

5、行反向推理 由正向推理推出的结论可信度不高 希望得到更多的结论,先正向再反向,通过正向推理，即从已知事实演绎出部分结果，然后再用反向推理验证这些结果或提高它们的可信度,先反向再正向,先从假设目标出发推出一些中间假设，然后再利用正向推理对这些中间假设进行证实,双向推理,双向推理是指正向推理与反向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理。 正向推理所得的中间结论恰好是逆向推理此时要求的证据,3.1.3 推理的控制策略,3.1.3 推理的控制策略,2.求解策略,推理是只求一个解还是求所有解以及最优解等,3. 限制策略,对推理的深度、宽度、时间、空间等进行限制,3.1.3 推理的控制

6、策略,4.冲突消解策略,在推理过程中，匹配会出现三种情况,已知事实可与知识库中的多个知识匹配成功；或者有多个（组）已知事实都可与知识库中某一知识匹配成功；或者有多个（组）已知事实可与知识库中的多个知识匹配成功,已知事实恰好只与知识库中的一个知识匹配成功,已知事实不能与知识库中的任何知识匹配成功,3.1.3 推理的控制策略,出现冲突的情况,逆向推理: 如果有多条产生式的后件都和同一假设匹配成功，或者有多条产生式后件可与多个假设匹配成功,正向推理: 如果有多条产生式规则的前件都和已知的事实匹配成功；或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功；或者两种情况同时出现,3.1.3 推理的

7、控制策略,按就近原则排序,把最近被使用过的规则赋予较高的优先级,按已知事实的新鲜性排序,赋予新鲜知识更高的优先性,按匹配度排序,根据匹配程度决定哪一个产生式规则优先被应用,3.1.3 推理的控制策略,按领域问题特点排序,按照问题领域的特点将知识排成固定的次序,按上下文限制排序,根据当前数据库已知事实与上下文匹配情况,按条件个数排序,将条件少的规则赋予较高优先级，优先被启用,按规则的次序排序,以知识库中预先存入规则的排列顺序作为知识排序依据,3.2 推理的逻辑基础,3.2.1 谓词公式,个体,可以独立存在的物体，抽象、具体都可以,谓词,刻画个体的性质、状态或个体间的关系,元数,谓词中包含的个体数

8、目,个体域,个体变元的取值范围，可以有限，也可无限,3.2.1 谓词公式,连接词,将原子谓词公式连接起来,量词,刻画谓词与个体之间的关系,原子谓词公式,由单个谓词构成的不含任何连接词的公式,谓词演算公式,按规则由原子公式、连接词、量词及圆括号所组成的字符串,3.2.1 谓词公式,合式公式,量词辖域,位于量词后面的单个谓词或者用括号括起来的合式公式,约束变元,辖域内与量词中同名的变元,自由变元,不受约束的变元,3.2.2 谓词公式的解释,定义,使公式中的每个变元都有个体域中的元素相对应,赋值原则,为每个n元函数指派一个从Dn到D的映射,为每个个体常量指派D中的一个元素,D是谓词公式P的非空个体域

9、,为每个n元谓词指派一个从Dn到F,T的映射,3.2.2 谓词公式的解释,例,设个体域D=1，2，求公式 在D上的解释，并指出每一种解释下公式A的真值,3.2.3 谓词公式的值,永真,对非空个体域中的任一解释都取得真值,可满足,如果至少存在一个解释，使其值为真,永假,对非空个体域的任一解释都取得假值,3.2.4 谓词公式的等价性与永真蕴涵,等价,等价公式,D是谓词公式P和Q共同的个体域。若对D上任何一个解释，P与Q的取值都相同，则公式P和Q在域上是等价的,对合律 幂等律 结合律、交换律、分配率 吸收律 德.摩根律 同一律、零律、补余律、逆否定律 连接词化规律、量词转换律、量词分配律,3.2.4

10、 谓词公式的等价性与永真蕴涵,永真蕴涵,如果PQ永真，则称P永真蕴涵Q，记为P=Q,永真蕴涵式,3.2.5 置换与合一,模式匹配,指对两个知识模式的比较与耦合，即检查这两个知识是否完全一致或近似一致,模式匹配的分类,不确定性匹配：两个知识模式不完全一致，但从整体上看，它们的相似程度落在规定的范围内,确定性匹配：两个知识模式完全一致，或者经过变量置换后变得完全一致,3.2.5 置换与合一,置换,置换是形如 t1/x1, t2/x2, tn/xn 的有限集合。其中，t1,t2,tn 是项，x1,x2,xn是变元；ti/xi表示用ti替换xi，不允许ti与xi相同，也不允许变元xi循环出现在另一个t

11、j中,3.2.5 置换与合一,置换复合,设 是两个置换，则此两个置换的复合也是一个置换，它是从 中删去如下两种元素： 先删除: 后删除:,3.2.5 置换与合一,解：先做置换 得到 先删除a/x,b/y,再删除y/y,例,3.2.5 置换与合一,合一,设有公式集E=E1,E2,En ，若存在一个置换使得 E1=E2=En 则称为公式集E的一个合一置换，且称 E1,E2,En是可合一的。,一个公式集的合一置换一般来说是不唯一的。,3.2.5 置换与合一,最一般合一置换,设 是公式集E的一个合一，如果对任一合一 都存在一个置换 ，使得 则称 是E的最一般合一置换，记为mgu,最一般合一置换并不是是

12、唯一的。,3.2.5 置换与合一,1,2,找出Ek的不一致集Dk,3,4,5,令k=0, Ek=E, k=,若Ek只含有一个表达式，则算法停止,若Dk中存在元素xk和tk，其中xk是变元， tk是项，且tk不在xk 中出现，则做(5)，否则不可合一,令,最一般合一置换算法,例如：E1=P(a,x,f(g(y) E2=P(z,f(a),f(u)求mgu 。 解： (1) W=E1,E2=P(a,x,f(g(y) ,P(z,f(a),f(u) (2) W0=W,g= (3) W0未合一，从左到右找不一致集，有D0=a,z (4) 取v0=z,t0=a (5) 令g1= g0t0/v0,=a/z W

13、1= W0 g1= P(a,x,f(g(y) ,P(a,f(a),f(u),(3) W1未合一，从左到右找不一致集，有D1=x,f(a) (4) 取v1=x,t1=f(a) (5) 令g2= g1t1/v1,=a/z,f(a)/x W2= W1 g2= P(a,f(a),f(g(y) ,P(a,f(a),f(u) (3) W2未合一，从左到右找不一致集，有D2=g(y),u) (4) 取v2=u,t2=g(y) (5) 令g3= g2t2/v2,=a/z,f(a)/x,g(y)/u W3= W2 g3= P(a,f(a),f(g(y) ,P(a,f(a),f(g(y) (3) W3已合一，这时

14、g3 =a/z,f(a)/x,g(y)/u,3.3 自然演绎推理,3.3.1 自然演绎推理的基本概念,自然演绎推理,从一组已知的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程,推理规则,3.3.1 自然演绎推理的基本概念,避免产生两类错误：,肯定后件(Q)的错误： 希望通过肯定后件Q推出前件P为真,否定前件(P)的错误： 希望通过否定前件P推出后件Q为假,3.3.2 利用演绎推理解决问题,例1,3.3.2 利用演绎推理解决问题,例2,设已知事实 （1）只有勤学苦练的人，才会成为技术能手。 （2）学习积极分子都是勤学苦练的人。 （3）李明是学习积极分子。 求证：李明会成为技术能手

15、。,解：（1）定义谓词 Diligent(x):x是勤学苦练的人 Master(x):x是技术能手 Study(x):x是学习积极分子,(2)将已知事实及问题用谓词公式表示 Diligent(x)Master(x) Study(x)Diligent(x) Study(Liming) Master(Liming) (3)应用推理规则进行推理,3.3.2 利用演绎推理解决问题,优点,缺点,定理证明过程自然，容易理解 拥有丰富的推理规则，推理过程灵活， 便于在它的推理规则中嵌入领域启发式知识,容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增,自然演绎推理的 优缺点,3.4 归结演绎推理,

16、3.4.1 子句,文字,原子谓词公式及其否定统称为文字,子句,任何文字的析取式称为子句,空子句,不包含任何文字的子句称为空子句,空子句中不包含任何文字，不能被任何解释满足，所以空子句是永假的，不可满足的,3.4.1 子句,消去存在量词,1,3,谓词公式化为 子句集步骤,重新命名变元,利用等价关系消去谓词公式中的“ ”和“ ”,利用等价关系把“ ”移到紧靠谓词,3.4.1 子句,把全称量词移到公式左边,谓词公式化为 子句集步骤,消去全称量词,利用等价关系把母式化为合取范式,使不同子句中的变元不同名,消去合取词，生成子句集,3.4.1 子句,定理：设有谓词公式F，其标准形的子句集为S，则F不可满足

17、的充要条件是S不可满足。,Skolem标准形的一般形式,3.4.2 海明伦理论,令H0是S中所有个体常量的集合，若S中不包含个体常量，则令 H0=a，其中a为任意指定的一个个体常量,令,1,2,H域,设S为子句集，则按下述方法构造的域称为海明伦域，简称为H域,下列集合称为子句集S的原子集： A=所有形如P(t1,t2,tn)的元素 其中，P(t1,t2,tn) 是出现在S中的任一谓词符号，而t1,t2,tn 是S在H域上的任意元素。,3.4.2 海明伦理论,原子集,3.4.2 海明伦理论,H域上的解释,子句集S在H域上的解释就是对S中出现的常量、函数及谓词取值，一次取值就是一个解释。,子句集S

18、在H域上的一个解释I满足下列条件：,在解释下，常量映射到自身,S中的任一个n元函数是HnH的映射,S中的任一个n元谓词是HnT,F的映射。谓词的真值可以指派为T，也可以指派为F,1,2,3,子句集不可满足的充要条件是存在一个有限的不可满足的基子句集S,3.4.2 海明伦理论,子句集S不可满足的充要条件是S对H域上的一切解释都为假。,定理,可证明，对给定域D上的任何一个解释，总能在H域上构造一个解释与它对应，如果D域上的解释能满足子句集S，则在H域上相应解释也能满足S。,定理,3.4.3 鲁宾逊归结原理,鲁宾逊归结原理基本思想,检查子句集S中是否包含空子句，若包含，则S不可满足；若不包含，就在子

19、句集中选择合适的子句进行归结，一旦通过归结能推出空子句集，就说明子句集S是不可满足的。,互补文字,若P是原子谓词公式或原子命题，则称P 与 为互补文字,命题逻辑中的归结原理,归结,设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句,归结式C12是亲本子句C1与C2的逻辑结论,定理,推论1,推论2,设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2得到新子句集S1，

20、则由S1的不可满足性可推出原子句集S的不可满足性，即 S1的不可满足性 S的不可满足性,设C1与C2是子句集S中的两个子句，C12是它们的归结式，若把C12加入S中。得到新子句集S2，则由S2的不可满足性可推出原子句集S的不可满足性，即 S2的不可满足性 S的不可满足性,命题逻辑中的归结原理,设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若是L1和L2的最一般合一，则称 为C1和C2的二元归结式，L1和L2称为归结式上的文字,谓词逻辑中的归结,定义,3.4.3 鲁宾逊归结原理,定义,子句C1和C2的归结式是下列二元归结式之一： C1与C2的二元归结式 C1与C2的因

21、子C2 2的二元归结式 C1的因子C1 1与C2的二元归结式 C1的因子C1 1与C2的因子C2 2的二元归结式,几点说明,确保每个子句有不同的变元名，以免归结产生不便或错误 如果参加归结的子句内部含有可合一的文字时，则在进行归结之前先对这些文字进行合一 若两个子句中有两对可互补的文字，不能同时消去，否则会产生错误,3.4.4 使用归结原理证明问题,1,2,3,否定G， 得到,把 并入到公式集F中，得到F, ,把公式集F, 化为子句集S,4,应用归结原理，证明子句集S的不可满足性，从而证明FG为真,设F为已知前提的公式集，G为目标公式(结论)，用归结反演证明Q为真的步骤是：,3.4.4 使用归

22、结原理证明问题,已知能阅读的都是有文化的；海豚是没有文化的；某些海豚是有智能的；证明：某些有智能的并不能阅读。 证明：符号化R(x):x能阅读 L(x):x有文化 D(x)：x是海豚 I(x)：x有智能,3.4.4 使用归结原理证明问题,3.4.4 使用归结原理证明问题,3.4.5 用归结原理求解问题,用归结原理求解问题,把已知前提用谓词公式表示出来，并且化为相应的子句集S,把待求解的问题用谓词公式表示，把它否定并与谓词ANSWER构成析取式,若得到归结式ANSWER，则答案在ANS WER中,对S应用归结原理进行归结,1,2,3,4,5,把此析取式化为子句集，并且把该子句集并入到子句集S中，得到子句集S,例4.6 已知F1：王(wang)先生是小李(Li)的老师 F2：小李和小张 (zhang) 是 同班同