人工智能确定性推理.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第三章 确定性推理,1,人工智能确定性推理,第1页,需要掌握问题,应用归结原理求解以下问题：,任何弟兄都有同一个父亲，,John,和,Peter,是弟兄，且,John,父亲是,David,，问,Peter,父亲是谁？,2,人工智能确定性推理,第2页,按照推理过程所用知识确实定性，推理可分为确定性推理和不确定性推理。,自然演绎推理和归结推理是经典确实定性推理，它们以数理逻辑相关理论、方法和技术为理论基础，是机械化、可在计算机上加以实现推理方法。,本章在讨论相关推理普通概念以及命题和谓词逻辑基础上，介绍自然演绎推理方法和基于一阶谓词逻辑归结推理方法。,3,人工智能确定性推理,第3页,3.1 推理概述,3.1.1 推理基本概念,推理是指从已知事实出发，利用已掌握知识，推导出其中蕴含事实性结论或归纳出一些新结论过程。,其中，推理所用事实可分为两种情况，一个是与求解问题相关初始证据；另一个是推理过程中所得到中间结论，这些中间结论能够作为深入推理已知事实或证据。,人工智能系统组成：,推理机,一些程序来完成；,综合数据库存放有用于推理事实或证据；,知识库存放有用于推理所必须知识。,4,人工智能确定性推理,第4页,3.1 推理概述,3.1.2 推理方法及其分类,1.,按照推理逻辑基础分类,可分为演绎推理、归纳推理和默认推理。,（1）演绎推理,演绎推理是从已知普通性知识出发，推理出适合于某种个别情况结论过程。它是一个由普通到个别推理方法。,5,人工智能确定性推理,第5页,3.1 推理概述,（2）,归纳推理,归纳推理是从大量特殊事例出发，归纳出普通性结论推理过程，是一个由个别到普通推理方法。其基本思想是：首先从已知事实中猜测出一个结论，然后对这个结论正确性加以证实确认，数学归纳法就是归纳推理一个经典例子。,归纳推理又可分为：,从,特殊事例考查范围,看：,完全归纳推理,、,不完全归纳推理,；,从,使用方法,看：,枚举归纳推理、类比归纳推理。,6,人工智能确定性推理,第6页,3.1 推理概述,（3）,默认推理,默认推理又称缺省推理，是在知识不完全情况下假设一些条件已经具备所进行推理。也就是说，在进行推理时，假如对一些证据不能证实其不成立情况下，先假设它是成立，并将它作为推理依据进行推理，但在推理过程中，当因为新知识加入或因为所推出中间结论与已经有知识发生矛盾时，就说明前面相关证据假设是不正确，这时就要撤消原来假设以及由此假设所推出全部结论，重新按新情况进行推理,7,人工智能确定性推理,第7页,3.1 推理概述,2.,按所用知识确实定性分类,按推理时所用知识确实定性来划分，推理可,分为确定性,推理、不确定性推理。,3.,按推理过程单调性,按照推理过程中所推出结论是否单调地增加，或者说按照推理过程所得到结论是否越来越靠近最终目标来分类，推理可分为单调推理与非单调推理。,8,人工智能确定性推理,第8页,3.1 推理概述,3.1.3 推理控制策略,推理过程不但依赖于所用推理方法，同时也依赖于推理控制策略。控制策略包含推理方向、搜索策略、冲突消解策略等；而推理方法则是指在推理控制策略确定之后，在进行详细推理时所要采取匹配方法或不确定性传递算法等方法。,推理方向用来确定推理驱动方式，即是数据（证据）驱动或是目标驱动。所谓数据驱动即指推理过程从初始证据开始直到目标结束，而目标驱动则是指推理过程从目标开始进行反向推理，直到出现与初始证据相吻合结果。,按照对推理方向控制，推理可分为正向推理、反向推理、混合推理及双向推理四种情况。,9,人工智能确定性推理,第9页,3.1 推理概述,正向推理是一个从已知事实出发、正向使用推理规则推理方式，它是一个数据（或证据）驱动推理方式，又称前项链推理或自底向上推理。,反向推理是一个以某个假设目标为出发点，反向利用推理规则推理方式，它是一个目标驱动推理方式，又称反向链推理或自顶向下推理。,混合推理是把正向推理和反向推理结合起来所进行推理。,所谓双向混合推理是指正向推理和反向推理同时进行，使推理过程在中间某一步骤相汇合而结束一个推理方法。,10,人工智能确定性推理,第10页,3.1 推理概述,3.1.4,推理冲突消解策略,推理过程中冲突消解策略，就是确定怎样从多条匹配规则中选出一条规则作为启用规则，将它用于当前推理。,当前已经有各种冲突消解策略基本思想都是对匹配知识或规则进行排序，以决定匹配规则优先级别，优先级高规则将作为启用规则。,惯用排序方法有以下几个:,11,人工智能确定性推理,第11页,3.1 推理概述,按就近标准排序,按知识特殊性排序,按上下文限制排序,按知识新鲜性排序,按知识差异性排序,按领域问题特点排序,按规则次序排序,按前提条件规模排序,12,人工智能确定性推理,第12页,3.2 命题逻辑,3.2.1,命题,定义 3.1,能够分辨真假语句称作,命题,。,定义3.2,一个语句假如不能再深入分解成更简单语句，而且又是一个命题，则称此命题为,原子命题,。,原子命题是命题中最基本单位。我们普通用P、Q、R、大写拉丁字母表示命题，而命题真与假分别用“T”与“F”表示。,用大写英文字母表示命题既能够是一个特定命题，也能够是一个抽象命题。前者称为,命题常量,，后者称为,命题变量,。对于命题变量而言，只有把确定命题代入后，它才可能有明确逻辑值（,T,或,F,）。,13,人工智能确定性推理,第13页,3.2 命题逻辑,3.2.2,命题公式,1.连接词,：称为“非”或“否定”。,：称为“析取”。,：称为“合取”。,：称为“条件”或者“蕴含”。,：称为“双条件”。,P,Q,表示“,P,当且仅当,Q,”。,表3.1 命题逻辑真值表,P Q,P,Q,P,Q,PQ,P Q,P,T T,T,T,T,T,F,T F,T,F,F,F,F,F T,T,F,T,F,T,F F,F,F,T,T,T,14,人工智能确定性推理,第14页,3.2 命题逻辑,2.命题公式,定义3.3 以下面递归形式给出命题公式定义：,（1）原子命题是命题公式。,（2）,A,是命题公式，则,A,也是命题公式。,（,3,）若,A,和,B,都是命题公式，则,A,B,、,A,B,、,A,B,、A,B,（,4,）只有按（,1,）（,3,）所得公式才是命题公式。,15,人工智能确定性推理,第15页,3.2 命题逻辑,命题公式缺点：,无法把所描述客观事物结构和逻辑特征反应出来,不能把不一样事物共同特征反应出来,P:“张三是李四老师”；仅用字母P看不出张三和李四之间师生关系。,为了克服命题逻辑不足，引入了下面谓词逻辑,16,人工智能确定性推理,第16页,3.3 谓词逻辑,3.3.1 谓词与个体,在谓词逻辑中，将原子命题分解为,谓词,与,个体,两部分。,个体,是指能够独立存在物体，能够是抽象或详细。,谓词,则是用于刻画个体性质、状态或个体间关系。,比如：“李白是诗人”,可表示为：poet(LiBai),poet称为谓词，用以刻画“是诗人”；LiBai称为个体,17,人工智能确定性推理,第17页,3.3 谓词逻辑,一个谓词能够与一个个体相关联，此种谓词称作,一元谓词,，,它刻画了个体性质,。一个谓词也能够与多个个体相关联，此种谓词称为,多元谓词,，,它刻画了个体间“关系”,。,18,人工智能确定性推理,第18页,3.3 谓词逻辑,谓词普通形式：,P(x,1,x,2,x,n,),其中,P,是谓词，而,x,1,x,2,x,n,是个体。谓词通惯用大写字母表示，个体通惯用小写字母表示。,项：,在谓词中，个体能够是,常量,，也能够是,变量,，还能够是一个,函数,。比如，“小刘哥哥是个工人”，能够表示为,worker(brother(Liu),，其中,brother(Liu),是一个函数。个体常数、变量和函数统称为,项,。,谓词语义：,由使用者依据需要人为地定义.,19,人工智能确定性推理,第19页,3.3 谓词逻辑,谓词元数：,谓词中包含个体数目称为谓词,元数,，比如,P(x),是一元谓词，,P(x,y),是二元谓词，而,P(x,1,x,2,x,n,),则是,n,元谓词。,谓词阶数：,在谓词P(x,1,x,2,x,n,)中，若x,i,(i=1,2,n)都是个体常量、变元或函数，则称它为,一阶谓词,。假如某个x,i,本身又是一个一阶谓词，则称它为,二阶谓词,，依次类推。,谓词和函数区分：,谓词含有逻辑值“真”或“假”，而函数则是某个个体到另一个个体（按数学上概念是自变量到因变量）之间映射。,20,人工智能确定性推理,第20页,3.3 谓词逻辑,3.3.2,谓词公式,1.,连接词,，,2.,量词,为刻画谓词与个体间关系，引入了两个量词：全称量词（,x,）,和存在量词（,x,）。,3.,谓词演算公式,定义3.4,谓词演算中，由单个谓词组成不含任何连接词公式，叫做,原子谓词公式,。,21,人工智能确定性推理,第21页,3.3 谓词逻辑,由原子公式定义出发，可定义谓词演算合式公式以下。,定义3.5,可按下述规则得到谓词演算合式公式：,（1）,原子谓词公式是合式公式。,（2）,若,A,是合式公式，则,A,也是合式公式。,（,3,）若,A,和,B,都是合式公式，则,A,B,、,A,B,、,A,B,、,A,B,也都是合式公式。,（,4,）若,A,是合式公式，,x,是任一个体变元，则,(,x)A,和,(,x)A,也都是合式公式。,（,5,）只有按（,1,）,（,4,）所得公式才是合式公式。,22,人工智能确定性推理,第22页,3.3 谓词逻辑,4.量词辖域与约束变元,在一个公式中，假如有量词出现，位于量词后面单个谓词或者用括弧括起来合式公式称为,量词辖域,。在辖域内与量词中同名变元称为,约束变元,。,23,人工智能确定性推理,第23页,3.3 谓词逻辑,3.3.3 谓词公式永真性和可满足性,1谓词公式解释,定义3.6,设,D,为谓词公式,P,个体域，若对,P,中个体常量、函数和谓词按照以下要求赋值：,（,1,）为每个个体常量指派,D,中一个元素；,（,2,）为每个,n,元函数指派一个从,D,n,到,D,映射，其中,D,n,=(x,1,x,2,x,n,)|x,1,x,2,x,n,D,（,3,）为每个,n,元谓词指派一个从,D,n,到,F,T,映射；,则称这些指派为公式,P,在,D,上一个,解释,。,24,人工智能确定性推理,第24页,3.3 谓词逻辑,例3.1,设个体域,D=1,2,，求公式,A=(,x)(P(x),Q(f(x),b),在,D,上某一个解释，并指出在此解释下公式,A,真值。,详细求解过程参见教材,25,人工智能确定性推理,第25页,3.3 谓词逻辑,2谓词公式永真性,定义3.7,假如谓词公式,P,，对个体域,D,上任何一个解释都取得真值,T,，则称,P,在,D,上是,永真,；假如,P,在每个非空个体域上均永真，则称,P,永真,。,定义3.8,假如谓词公式,P,对于个体域,D,上全部解释都取得假值,F,，则称,P,在,D,上是,永假,；假如,P,在每个非空个体域上均永假，则称,P,永假,。,谓词公式永假性又称为不可满足性或不相容性。,26,人工智能确定性推理,第26页,3.3 谓词逻辑,3,谓词公式可满足性,定义3.9,对于谓词公式,P,，假如最少存在一个解释使得公式,P,在此解释下真值为,T,，则称公式,P,是,可满足,。,按照定义,3.9,，对谓词公式,P,，假如不存在任何解释，使得,P,取值为,T,，则称公式,P,是,不可满足,。所以，,谓词公式,P,永假与不可满足是等价。若,P,永假，则也可称,P,是不可满足。,27,人工智能确定性推理,第27页,3.3 谓词逻辑,3.3.4,谓词公式等价性与永真蕴含,定义3.10,设,P,与,Q,是两个谓词公式，,D,是它们共同个体域。若对,D,上任何一个解释，,P,与,Q,取值都相同，则公式,P,和,Q,在域,D,上是,等价,。假如,D,是任意个体域，则称,P,和,Q,是,等价,，记作,P,Q,。,惯用一些等价式参见教材,定义3.11,对于谓词公式,P,和,Q,，假如,P,Q,永真，则称,P,永真蕴含,Q,，且称,Q,为,P,逻辑结论,，称,P,为,Q,前提,，记作,P=Q,。,以后要用到一些永真蕴含式参见教材,28,人工智能确定性推理,第28页,3.3 谓词逻辑,谓词逻辑中还有以下一些推理规则：,（,1,）,P,规则：在推理任何步骤上都可引入前提。,（,2,）,T,规则：推理时，假如前面步骤中有一个或多个永真蕴含公式,S,，则可把,S,引入推理过程中。,（,3,）,CP,规则：假如能从,R,和前提集合中推出,S,来，则可从前提集合推出,R,S,来。,（,4,）反证法：,P=Q,，当且仅当,P,Q,F,，即,Q,为,P,逻辑结论，当且仅当,P,Q,是不可满足。,推广之，可得以下定理。,定理3.1,Q,为,P,1,，,P,2,，,P,n,逻辑结论，当且仅当,(P,1,P,2,P,n,),Q,是不可满足。,29,人工智能确定性推理,第29页,3.3 谓词逻辑,3.3.5,置换与合一,1.置换,置换定义,定义3.12,置换是形如,t,1,/x,1,t,2,/x,2,t,n,/x,n,一个有限集。其中,x,i,是变量，,t,i,是不一样于,x,i,项（常量，变量，函数），且,x,i,x,j,（,I,j,），,i,，,j=1,2,n,。,30,人工智能确定性推理,第30页,3.3 谓词逻辑,比如，,a/x,b/y,f(x)/z,，,f(z)/x,y/z,都是置换。,不含任何元素置换称为空置换，以表示。,置换乘法,置换乘法作用是将两个置换合成为一个置换。,定义3.13,假设,=t,1,/x,1,t,2,/x,2,t,n,/x,n,=u,1,/y,1,u,2,/y,2,u,m,/y,m,是两个置换，则它们乘积是一个新置换，其作用于公式,E,时，相当于先,后对,E,作用。它定义以下：,31,人工智能确定性推理,第31页,3.3 谓词逻辑,先作置换,t,1,/x,1,t,2,/x,2,t,n,/x,n,u,1,/y,1,u,2,/y,2,u,m,/y,m,。,若,y,i,x,1,x,n,时，先从上述集合中删除,u,i,/y,i,。,若,t,i,=x,i,时，再从上述集合中删除,t,i,/x,i,。,删除以后剩下元素所组成集合称作,与,乘积，记作,。,置换结合率,普通地说，以下置换结合律成立,(,),=,(,),但除了空置换外，置换交换律不成立。即只有,=,=,。,32,人工智能确定性推理,第32页,3.3 谓词逻辑,2.合一,合一概念,定义3.14,设有公式集,E,1,E,2,E,n,和置换，使,E,1,=E,2,=E,n,便称,E,1,，,E,2,，,，,E,n,是,可合一,，且称为,合一置换,。,定义3.15,若,E,1,，,E,2,，,，,E,n,有合一置换，且对,E,1,，,E,2,，,，,E,n,任一置换都存在一个置换，使得=,，则称是,E,1,，,E,2,，,，,E,n,最普通合一置换,，记为,mgu,。,33,人工智能确定性推理,第33页,3.3 谓词逻辑,最普通合一置换求取算法,设有两个谓词公式：,E,1,：,P(x,y,z);E,2,：,P(x,f(a),g(b),分别从,E,1,与,E,2,第一个符号开始逐一向右比较，此时发觉,E,1,中,y,与,E,2,中,f(a),不一样，则它们组成了一个不一致集：,D,1,=y,f(a),当继续向右比较时，又发觉中,E,1,中,z,与,E,2,中,g(b),不一样，则又得到一个不一致集：,D,2,=z,g(b),下面给出求公式,E,1,E,2,最普通合一置换算法：,34,人工智能确定性推理,第34页,3.3 谓词逻辑,（1）,令,W=E,1,E,2,。,（2）,令,k=0,，,W,k,=W,，,k,=,；,是空置换，它表示不作置换。,（3）,假如,W,k,只有一个表示式，则算法停顿，,k,就是所要求,mgu,。,（4）,找出,W,k,不一致集,D,k,。,（5）,若,D,k,中存在元素,x,k,和,t,k,，其中,x,k,是变元，,t,k,是项，且,x,k,不在,t,k,中 出现，则置：,k+1,=,k,t,k,/x,k,W,k+1,=w,k,t,k,/x,k,k=k+1,然后转（,3,）。,（6）,算法终止，,W,mgu,不存在。,能够证实，假如,E,1,和,E,2,可合一，则算法必停顿于第（,3,）步。,35,人工智能确定性推理,第35页,3.3 谓词逻辑,例3.5,设,E,1,=P(a,v,f(g(y),，,E,2,=P(z,f(a),f(u),，求,E,1,和,E,2,mgu,。,解题请参见教材,答案为：,3,=a/z,f(a)/v,g(y)/u,3,就是,E,1,和,E,2,mgu,。,36,人工智能确定性推理,第36页,3.4 自然演绎推理方法,3.4.1 自然演绎推理概念,自然演绎推理是指从一组已知为真事实出发，直接利用命题逻辑或谓词逻辑中推理规则推出结论过程。,假言三段论基本形式为,PQ，QR,PR,它表示假如谓词公式PQ和QR均为真，则谓词公式PR也为真。,假言推理可用以下形式表示,P，PQ,Q,它表示假如谓词公式P和PQ都为真，则可推得Q为真结论。,37,人工智能确定性推理,第37页,3.4 自然演绎推理方法,拒取式一般形式为,PQ，Q P,它表示如果谓词公式PQ为真且Q为假，则可推得P为假结论。,2.4.2 利用演绎推了解决问题,在利用自然演绎推理方法求解问题时，一定要注意防止两种类型错误：肯定后件错误和否定前件错误。,38,人工智能确定性推理,第38页,3.4 自然演绎推理方法,必定后件错误,是指当,P,Q,为真时，希望经过必定后件,Q,为真来推出前件,P,为真。这显然是错误推理逻辑，因为当,P,Q,及,Q,为真时，前件,P,既可能为真，也可能为假。,否定前件错误,是指当,P,Q,为真时，希望经过否定前件,P,来推出后件,Q,为假。这也是不允许，因为当,P,Q,及,P,为假时，后件,Q,既可能为真，也可能为假。,相关例题请参见教材,39,人工智能确定性推理,第39页,3.4 自然演绎推理方法,3.4.3 演绎推理特点,参见教材,40,人工智能确定性推理,第40页,3.5 归结推理方法,研究用计算机实现定理证实机械化，已是人工智能研究一个主要领域。,对于定理证实问题，假如用一阶谓词逻辑表示话，就是要求对前提,P,和结论,Q,证实,P,Q,是永真。,然而，要证实这个谓词公式永真性，必须对全部个体域上每一个解释进行验证，这是极其困难。为了化简问题，和数学上常采取方法一样，我们考虑反证法。,即，,我们先否定逻辑结论,Q,，再由否定后逻辑结论,Q,及前提条件,P,出发推出矛盾，即可证实原问题。,41,人工智能确定性推理,第41页,3.5 归结推理方法,3.5.1,谓词公式与子句集,1范式,前束形范式,一个谓词公式，假如它全部量词均非否定地出现在公式最前面，且它辖域一直延伸到公式之末，同时公式中不出现连接词及,，这种形式公式称作前束形范式。,比如，公式,(,x)(,y)(,z)(P(x),F(y,z),Q(y,z),即是一个前束形公式。,42,人工智能确定性推理,第42页,3.5 归结推理方法,斯克林范式,从前束形范式中消去全部存在量词所得到公式即为,Skolem,范式，或称,Skolem,标准型。,比如，假如用f(x)代替上面前束形范式中y即得到Skolem范式：,(,x)(,z)(P(x)F(f(x),z)Q(f(x),z),Skolem标准型普通形式是,(,x,1,)(,x,2,)(,x,n,)M(x,1,x,2,x,n,),其中，M(x,1,x,2,x,n,)是一个合取范式，称为Skolem标准型母式。,43,人工智能确定性推理,第43页,3.5 归结推理方法,将谓词公式,G,化为,Skolem,标准型步骤以下：,（1）,消去谓词公式,G,中蕴涵（）和双条件符号（,），以,A,B,代替,A,B,，以,(A,B),(,A,B),替换,A,B,。,（2）,降低否定符号（）辖域，使否定符号“”最多只作用到一个谓词上。,（3）,重新命名变元名，使全部变元名字均不一样，而且自由变元及约束变元亦不一样。,44,人工智能确定性推理,第44页,3.5 归结推理方法,（4）,消去存在量词。这里分两种情况，一个情况是存在量词不出现在全称量词辖域内，此时，只要用一个新个体常量替换该存在量词约束变元，就能够消去存在量词；另一个情况是，存在量词位于一个或多个全称量词辖域内，这时需要用一个Skolem函数替换存在量词而将其消去。,（,5,）把全称量词全部移到公式左边，并使每个量词辖域包含这个量词后面公式整个部分。,（,6,）母式化为合取范式：任何母式都能够写成由一些谓词公式和谓词公式否定析取有限集组成合取。,需要指出是，因为在化解过程中，消去存在量词时作了一些替换，普通情况下，,G,Skolem,标准型与,G,并不等值。,45,人工智能确定性推理,第45页,3.5 归结推理方法,2子句与子句集,定义3.16,不含有任何连接词谓词公式叫,原子公式,，简称,原子,，而原子或原子否定统称,文字,。,定义3.17,子句,就是由一些文字组成析取式。,定义3.18,不包含任何文字子句称为,空子句,，记为NIL。,定义3.19,9,由子句组成集合称为,子句集,。,46,人工智能确定性推理,第46页,3.5 归结推理方法,3不可满足意义下一致性,定理3.2,设有谓词公式,G,，而其对应子句集为,S,，则,G,是不可满足充分必要条件是,S,是不可满足。,要再次强调：,公式G与其子句集S并不等值，只是在不可满足意义下等价。,相关例子参见教材中例3.9,47,人工智能确定性推理,第47页,3.5 归结推理方法,4,P,P,1,P,2,P,n,子句集,当,P,P,1,P,2,P,n,时，若设,P,子句集为,S,P,，,P,i,子句集为,S,i,，则普通情况下，,S,P,并不等于,S,1,S,2,S,3,S,n,，而是要比,S,1,S,2,S,3,S,n,复杂得多。不过，在不可满足意义下，子句集,S,P,与,S,1,S,2,S,3,S,n,是一致，即,S,P,不可满足,S,1,S,2,S,3,S,n,不可满足,48,人工智能确定性推理,第48页,3.5 归结推理方法,3.5.2 Herbrand理论,1H域,定义3.20,设谓词公式,G,子句集为,S,，则按下述方法结构个体变元域H。称为公式,G,或子句集,S,Herbrand域,，简称,H域,。,（1）,令,H,0,是,S,中所出现常量集合。若,S,中没有常量出现，就任取一个常量,a,D,，要求,H,0,=a,。,（2）,令,H,i+1,=H,i,S,中全部形如,f(t,1,t,n,),元素,其中,f(t,1,t,n,),是出现于,G,中任一函数符号，而,t,1,，,，,t,n,是,H,i,中元素。,i=0,，,1,，,2,，,。,49,人工智能确定性推理,第49页,3.5 归结推理方法,例3.10 求子句集,S,T(x),Q(z),R(f(y),H,域。,解,此例中没有个体常量，任意指定一个常量,a,作为个体常量；只有一个函数,f(y),，有：,H,0,=a,H,1,=a,f(a),H,2,=a,f(a),f(f(a),H,=a,f(a),f(f(a),f(f(f(a),50,人工智能确定性推理,第50页,3.5 归结推理方法,2原子集,定义3.21,以下集合称为子句集,S,原子集,：,A,全部形如,P(t,1,t,2,t,n,),元素,其中，,P(t,1,t,2,t,n,),是出现在,S,中任一谓词符号，而,t,1,，,t,2,，,，,t,n,则是,S,H,域上任意元素。,51,人工智能确定性推理,第51页,3.5 归结推理方法,定义3.22,将没有变元出现原子、文字、子句和子句集分别称作,基原子,、,基文字,、,基子句,和,基子句集,。,定义3.23,当子句集,S,中某个子句,C,中全部变元符号均以其,H,域中元素替换时，所得到基子句称作,C,一个,基例,。,比如，对于子句集,S,P(a),P(x),P(f(x),它,H,域为,a,f(a),f(f(a),。,对于子句,P(a),，因为其中不含有变元，所以它已是基子句，而且,a,H,，所以它也是基例。,52,人工智能确定性推理,第52页,3.5 归结推理方法,3H域上解释,定义3.24,假如子句集,S,原子集为,A,，则对,A,中各元素真假值一个详细设定都是,S,一个,H解释,。,能够证实，在给定域D上任一个解释I，总能在H域上结构一个解释I*与之对应，使得假如D域上解释能满足子句集S，则在H域解释I*也能满足S（即若S|,I,=T，就有S|,I*,=T）。,相关举例参见教材,53,人工智能确定性推理,第53页,3.5 归结推理方法,定理3.3,设I是子句集S在域D上一个解释，则存在对应于IH域解释I,*,，使得若有 S|,I,=T，就必有S|,I*,=T。,定理3.4,子句集S不可满足充要条件是S对H域上一切解释都为假。,证实 充分性,：若S在普通域D上是不可满足，必定在H域上是不可满足，从而对H域上一切解释都为假。,必要性,：若S在任一H解释I,*,下均为假，必定会使S在D域上每一个解释为假。不然，假如存在一个解释I,0,使S为真，那么依据定理3.3可知，一定能够在H域找到相对应一个解释I,*,0,使S为真。这与S在全部H解释下均为假矛盾。,54,人工智能确定性推理,第54页,3.5 归结推理方法,定理3.5,子句集S不可满足充分必要条件是存在一个有限不可满足基例集S,。,该定理称为Herbrand定理，下面给出它简明证实。,证实 充分性：,设子句集S有一个不可满足基例集S,，因为它不可满足，所以一定存在一个解释I,使S,为假。依据H域上解释与D域上解释对应关系，可知在D域上一定存在一个解释使S不可满足，从而证实了子句集S是不可满足。,55,人工智能确定性推理,第55页,3.5 归结推理方法,必要性：,设子句集S不可满足，由定理3.4可知，S对H域上全部解释均为假。这么，就最少会存在一个S中某子句C,i,基例C,i,为假。既然最少有一个基例C,i,为假，因而S基例集S,是不可满足。另外，因为S中子句是有限，而每个子句又由有限文字组成，因而S不可满足基例集也是有限。,56,人工智能确定性推理,第56页,3.5 归结推理方法,3.5.3 归结原理,定义3.25,若,P,是原子谓词公式或原子命题，则称,P,与,P,为,互补文字,。,1命题逻辑中归结原理,归结与归结式,定义3.26,设,C,1,与,C,2,是子句集中任意两个子句，假如,C,1,中文字,L,1,与,C,2,中文字,L,2,互补，则从,C,1,和,C,2,中能够分别消去,L,1,和,L,2,，并将二子句中余下部分做析取组成一个新子句,C,12,，称这一过程为,归结,，所得到子句,C,12,称为,C,1,和,C,2,归结式,，而称,C,1,和,C,2,为,C,12,亲本子句,。,57,人工智能确定性推理,第57页,3.5 归结推理方法,定理3.6,归结式,C,12,是其亲本子句,C,1,和,C,2,逻辑结论。,推论,设,C,1,和,C,2,是子句集,S,上子句，,C,12,是,C,1,和,C,2,归结式。假如把,C,12,加入子句集,S,后得到新子句集,S,1,，则,S,1,和,S,在不可满足意义下是等价。即：,S,是不可满足,S,1,是不可满足,归结推理过程,子句集S不可满足性推理过程以下：,(1)对子句集S中各子句间使用归结推理规则。,(2)将归结所得归结式放入子句集S中，得新子句集S。,(3)检验子句集S中是否有空子句(NIL),若有则停顿推理;不然转（4）。,(4),置S=S，,转步骤（1）。,58,人工智能确定性推理,第58页,3.5 归结推理方法,2,一阶谓词逻辑中归结原理,下面是谓词逻辑关于归结定义。,定义3.27,设,C,1,和,C,2,是两个没有相同变元子句，,L,1,和,L,2,分别是,C,1,和,C,2,文字，假如,L,1,与,L,2,有,mgu ,，则把,C,12,=(C,1,L,1,),(C,2,L,2,),称作子句,C,1,和,C,2,一个,二元归结式,，而,L,1,和,L,2,是被归结文字。,为了说明方便。将,C,i,和,L,i,写成集合,形式，,如,P(x),Q(y),P(x),Q(y),。在集合表示下做减法或做并运算，然后再写成子句形，如集合运算结果为,P(x),Q(y),，可改写为,P(x),Q(y),。,59,人工智能确定性推理,第59页,3.5 归结推理方法,在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：,（1）若被归结子句,C,1,和,C,2,中含有相同变元时，需要将其中一个子句变元更名，不然可能无法做合一置换。从而没有方法进行归结。,（2）,在求归结式时，不能同时消去两个互补文字对，消去两个互补文字对所得结果不是两个亲本子句逻辑推论。,（3）假如在参加归结子句内含有可合一文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部化简。,60,人工智能确定性推理,第60页,3.5 归结推理方法,应用因子概念，可对谓词逻辑中归结原理定义以下。,定义3.28,设,C,1,和,C,2,是没有相同变元子句，则以下四种二元归结式都叫做,C,1,和,C,2,归结式，仍记作,C,12,。,（1）,C,1,与,C,2,二元归结式。,（2）,C,1,因子,C,1,1,与,C,2,二元归结式。,（3）,C,1,与,C,2,因子,C,2,2,二元归结式。,（4）,C,1,因子,C,1,1,与,C,2,因子,C,2,2,二元归结式。,61,人工智能确定性推理,第61页,3.5 归结推理方法,例,设,C,1,=,P(a),Q(x),R(x),，,C,2,=P(y),Q(b),，,求其二元归结式。,解,若选,L,1,=,P(a),，,L,2,=P(y),，则,L,1,和,L,2,mgu,是,=a/y,，于是由定义,3.27,得,C,1,和,C,2,二元归结式为,C,12,=(C,1,-L,1,),(C,2,-L,2,),=(,P(a),Q(x),R(x),-,P(a),(P(a),Q(b),-,P(a),=(Q(x),R(x),(,Q(b),=Q(x),R(x),Q(b),若选,L,1,=Q(x),，,L,2,=,Q(b),，则二者,mgu=b/x,，,C,12,=,P(a),R(b),P(y),62,人工智能确定性推理,第62页,3.5 归结推理方法,3归结原理完备性,对于一阶谓词逻辑，从不可满足意义上说，归结原理是完备。即若子句集是不可满足，则必存在一个从该子句集到空子句归结推理过程；反之，若从子句集到空子句存在一个归结推理过程，则该子句集必是不可满足。,63,人工智能确定性推理,第63页,3.5 归结推理方法,3.5.4 利用归结原理进行定理证实,应用归结原理进行定理证实步骤以下：,设要被证实定理可用谓词公式表示为以下形式：,A,1,A,2,A,n,B,(1),首先否定结论,B,，并将否定后公式,B,与前提公式集组成以下形式谓词公式：,G=A,1,A,2,A,n,B,(2),求谓词公式,G,子句集,S,。,(3),应用归结原理，证实子句集,S,不可满足性，从而证实谓词公式,G,不可满足性。这就说明对结论,B,否定是错误，推断出定理成立。,64,人工智能确定性推理,第64页,3.5 归结推理方法,例,已知：,A:(,x)(,y)(P(x,y),Q(y),(,y)(R(y),T(x,y),B:,(,x)R(x),(,x)(,y)(P(x,y),Q(y),求证：,B,是,A,逻辑结论。,证实,首先将,A,和,B,化为子句集,P(x,y),Q(y),R(f(x),P(x,y),Q(y),T(x,f(x)/(1)(2)为A,R(z),P(a，b),Q(b)/(3)(4)(5)为B,65,人工智能确定性推理,第65页,3.5 归结推理方法,下面进行归结：,（,6,）,P(x,y),Q(y),（,1,）与（,3,）归结，,=f(x)/z,（,7,）,Q(b),（,4,）与（,6,）归结，,=a/x,b/y,（,8,）,NIL,（空子句）,（,5,）与（,7,）归结,所以,B,是,A,逻辑结论,。,66,人工智能确定性推理,第66页,3.5 归结推理方法,3.5.5 应用归结原理进行问题求解,下面是利用归结原理求取问题答案步骤：,（1）把已知前提条件用谓词公式表示出来，并化成对应子句集，设该子句集名字为,S,1,。,（2）把待求解问题也用谓词公式表示出来，然后将其否定，并与一谓词,ANSWER,组成析取式。,谓词,ANSWER,是一个专为求解问题而设置谓词，,其变量必须与问题公式变量完全一致。,（3）把问题公式与谓词,ANSWER,组成析取式化为子句集，并把该子句集与,S,1,合并组成子句集,S,。,67,人工智能确定性推理,第67页,3.5 归结推理方法,（4）对子句集,S,应用谓词归结原理进行归结，在归结过程中，经过合一置换，改变,ANSWER,中变元。,（5）假如得到归结式,ANSWER,，则问题答案即在,ANSWER,谓词中。,68,人工智能确定性推理,第68页,3.5 归结推理方法,例,任何弟兄都有同一个父亲，,John,和,Peter,是弟兄，且,John,父亲是,David,，问,Peter,父亲是谁？,解,第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。,（1）,定义谓词：,设,Father(x,y),表示,x,是,y,父亲。,Brother(x,y),表示,x,和,y,是弟兄。,69,人工智能确定性推理,第69页,3.5 归结推理方法,（2）,将已知事实用谓词公式表示出来。,F,1,：任何弟兄都有同一个父亲。,(x)(y)(z)(Brother(x,y),Father(z,x),Father(z,y),F,2,：,John,和,Peter,是弟兄。,Brother(John,Peter),F,3,：,John,父亲是,David,。,Father(David,John),（3）,将它们化成子句集得：,S,1,=Brother(x,y),Father(z,x),Father(z,y),Brother(John,Peter),Father(David,John),70,人工智能确定性推理,第70页,3.5 归结推理方法,第二步：把问题用谓词公式表示出来，并将其否定与谓词,ANSWER,作析取。,设Peter父亲是u，则有：Father(u,Peter)。,将其否定与ANSWER作析取，得：,G：Father(u,Peter)ANSWER(u),71,人工智能确定性推理,第71页,3.5 归结推理方法,第三步：将上述公式G化为子句集S,2,，并将S,1,和S,2,合并到S。,S,2,=Father(u,Peter)ANSWER(u),S=S,1,S,2,将S中各子句列出以下：,（1）Brother(x,y)Father(z,x)Father(z,y)。,（2）Brother(John,Peter)。,（3）Father(David,John)。,（4）Father(u,Peter)ANSWER(u),。,72,人工智能确定性推理,第72页,3.5 归结推理方法,第四步：应用归结原理进行归结,（,5,）,Brother(John