人工智能及其应用课件.ppt

1,2.5消解原理2.6规则演绎系统2.7产生式系统2.8系统组织技术2.9小结,第2章知识表示与推理技术,2,推理的基本概念,推理是指按照某种策略从已知事实出发去推出结论的过程。其中，推理所用的事实可分为两种：一种是与求解问题有关的初始证据；另一种是推理过程中所得到的中间结论。通常，智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统用来实现推理的那些程序。例，在医疗诊断专家系统中，所有与诊断有关的医疗常识和专家经验都被保存在知识库中。当系统开始诊断疾病时，首先把病人的症状和检查结果放到事实库中，然后再从事实库中的这些初始证据出发，按照某种策略在知识库中寻找可以匹配的知识，如果得到的是一些中间结论，则需要把它们作为已知事实放入事实库中，并继续寻找可以匹配的知识，如此反复进行，直到推出最终结论为止。由初始事实出发到推出最终结论的过程就是推理，实现这一推理过程的程序称为推理机。,3,推理的基本概念（续）,智能系统的推理包括两个基本问题：一个是推理的方法；另一个是推理的控制策略。推理方法主要解决在推理过程中前提与结论之间的逻辑关系，以及在非精确性推理中不确定性的传递问题。,4,推理的基本概念（续）,1.按推理的逻辑基础分类按照推理的逻辑基础，常用的推理方法可分为演绎推理、归纳推理和默认推理。(1)演绎推理。演绎推理是从已知的一般性知识出发，去推出组合在这些已知知识中适合于某种个别情况的结论的过程。它是一种由一般到个别的推理方法，其核心是三段论，即假言推理、拒取式推理和假言三段论。常用的三段论是由一个大前提、一个小前提和一个结论三部分组成的。其中，大前提是由已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。,5,推理的基本概念（续）,（2）归纳推理归纳推理的前提是一些关于个别事物或现象的命题，而结论则是关于该类事物或现象的普遍性命题。归纳推理的结论所断定的知识范围超出了前提所断定的知识范围，因此，归纳推理的前提与结论之间的联系不是必然性的，而是或然性的。也就是说，其前提真而结论假是可能的，所以，归纳推理是一种或然性推理。基本思想：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认。如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理。,6,推理的基本概念（续）,3)默认推理。默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺省推理。在推理过程中，如果发现原先的假设不正确，就撤销原来的假设以及由此假设所推出的所有结论，重新对新情况进行推理。由于默认推理容许在推理过程中假设某些条件是成立的，这就解决了在一个不完备的知识集中进行推理的问题。,7,推理的基本概念（续）,2.按照所用知识的确定性分类确定性推理和不确定性推理3.按推理过程的单调性分类按照推理过程的单调性，或者说按照推理过程所得到的结论是否越来越接近目标，推理可分为单调推理与非单调推理两类。4.按照方法论分类按照方法论，常见的推理有基于知识的推理、统计推理和直觉推理等。基于知识的推理，是指根据已掌握的事实，通过运用知识进行的推理。例如：医生诊断疾病时，根据病人症状及检验结果，运用医学知识进行推理，给出诊断结论及治疗方案。统计推理，是指根据对某事物的数据统计进行的推理。例如，农民根据对农作物产量统计得出是否增产的结论，从而找出增产或者减产的原因。直觉推理又称为常识性推理，是指根据常识进行的推理。例如，当你猛然发现头上有一物体掉落时，立即会意识到危险，并立即躲开，这就是直觉推理。,8,推理的基本概念（续）,推理的控制策略智能系统的推理过程相当于人类的思维过程，即求解问题的过程。问题求解的质量与效率不仅依赖于所采用的求解方法，而且还依赖于求解问题的策略，即推理的控制策略。推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。其中，推理策略主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等，,9,推理的基本概念（续）,推理方向用来确定推理的控制方式，即用来确定推理过程是从初始证据开始到目标，还是从目标开始到初始证据。按照对推理方向的控制，推理可分为正向推理、逆向推理、混合推理及双向推理等4种。求解策略是指仅求一个解，还是求所有解或最优解等。限制策略是指为了防止无穷的推理，以及推理过程太长而对推理的深度、宽度、时间、空间等进行限制的策略。冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。目前已有多种消解冲突的策略，其基本思想都是对知识进行排序，比如：按针对性排序；按已知事实的更新程度排序；按匹配程度排序；按产生知识冗余大小排序；按产生结论的条件个数排序等。,10,3.5消解原理,3.5.1子句集的求取3.5.2消解推理规则3.5.3含有变量的消解式3.5.4消解反演求解过程,11,2.5消解原理(续),知识表示方式:谓词公式解决问题:定理的自动证明问题的自动求解消解原理由Robinson于1965年提出，又称为归结原理。将要证明的前提及结论合并在一起,化为子句集,利用消解原理对子句集进行消解,如果得到空子句则成立,否则失败.例:如果存在某个公理E1E2和另一公理E2E3，那么E1E3在逻辑上成立。这就是消解，而称E1E3为E1E2和E2E3的消解式（resolvent）。,12,2.5.1子句集的求取,相关概念文字:原子谓词公式及其否定统称为文字。子句:任何文字的析取式称为子句。空子句:不包含任何文字的子句称为空子句。记为：或NIL子句集:由子句和空子句所构成的集合称为子句集例:P(x,y)Q(x,y),P(x,y)U(x)V(y),Q(x,y)U(y)在谓词逻辑中，任一谓词演算公式可以化成一个子句集,13,2.5.1子句集的求取（续）,子句集的化简步骤:例:(z)(x)(y)(P(x)Q(x)R(y)U(z)（1）利用等价关系消去蕴涵和双条件符(“”或“”)PQPQ,PQ(PQ)(QP)对于本例有:(P(x)Q(x)R(y)(P(x)Q(x)R(y)(z)(x)(y)(P(x)Q(x)R(y)U(z),14,2.5.1子句集的求取（续）,（2）减小否定符号的辖域使得否定符只作用于谓词符号(原子公式)。狄摩根定律和量词转换率(PQ)PQ，(PQ)PQ(x)P(x)P，(x)P(x)P对于本例有:(z)(x)(y)(P(x)Q(x)R(y)U(z),15,2.5.1子句集的求取（续）,（3）对变量标准化（变元换名）在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量)，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合式公式中变量的标准化，意味着对哑元改名以保证每个量词有其自己唯一的哑元。(x)P(x)(y)P(y)(x)P(x)(y)P(y)例：(x)A(x)(x)B(x)化为：(x)A(x)(y)B(y),16,2.5.1子句集的求取（续）,（4）消去存在量词(skolem化)Skolem函数:在公式(y)(x)P(x,y)中，存在量词是在全称量词的辖域内，我们允许所存在的x可能依赖于y值。令这种依赖关系明显地由函数g(y)所定义，它把每个y值映射到存在的那个x。这种函数叫做Skolem函数。如果用Skolem函数代替存在的x,我们就可以消去全部存在量词，并写成：(y)P(g(y),y)不在任何全称量词辖域内的存在量词约束的变元用具体没有出现过的常量代替。(x)P(x)化为P(A)在全称量词辖域内的存在量词约束的变元用新的skolem函数符号代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)化为(x)(P(x)Q(x)R(g(x)U(a),17,2.5.1子句集的求取（续）,（5）化为前束范式（量词左移）到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即前束形=(前缀)(母式)全称量词串无量词公式,18,2.5.1子句集的求取（续）,（6）化为合取范式(Skolem标准形)合取范式:谓词公式或谓词公式的否定的析取的有限集合组成的合取,叫做合取范式。结合律,分配率(PQ)RP(QR)(PQ)RP(QR)P(QR)(PQ)(PR)P(QR)(PQ)(PR)对于本例有:(x)(P(x)Q(x)R(g(x)U(a)化为(x)P(x)Q(x)R(g(x)U(a)结合律化为(x)P(x)R(g(x)U(a)Q(x)R(g(x)U(a),19,2.5.1子句集的求取（续）,（7）消去全称量词:每个全称量词的辖域都是整个公式。P(x)R(f(x)U(a)Q(x)R(f(x)U(a)（8）消去连词符号（表示为子句集）方法:用A,B代替(AB)对于本例有：P(x)R(f(x)U(a),Q(x)R(f(x)U(a),20,2.5.1子句集的求取（续）,（9）更换变量名称使任意两个子句不出现同名的变量。对于本例有：P(x)R(f(x)U(a),Q(y)R(f(y)U(a),21,2.5.1子句集的求取（续）,例：(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)1：消去蕴含符号(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)2：减否定符号辖域(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)3:对变量标准化(x)P(x)(y)P(y)P(f(x,y)(q)Q(x,q)P(q)4：消去存在变量(Skolem函数:q=W(x)(x)P(x)(y)P(y)P(f(x,y)Q(x,W(x)P(W(x)5:化为前束形(x)(y)P(x)P(y)P(f(x,y)Q(x,W(x)P(W(x)6:化为合取范式(x)(y)(P(x)P(y)P(f(x,y)(P(x)Q(x,W(x)(P(x)P(W(x),22,2.5.1子句集的求取（续）,7:消去全称变量(P(x)P(y)P(f(x,y)(P(x)Q(x,W(x)(P(x)P(W(x)8:消去合取符P(x)P(y)P(f(x,y)，P(x)Q(x,W(x),P(x)P(W(x)9:更换变量名P(x)P(y)P(f(x,y)，P(x1)Q(x1,W(x1),P(x2)P(W(x2),23,2.5.1子句集的求取（续）,经上述步骤化简得到的标准式是经过Skolem化的前束范式，通常也称为S-标准形。要注意S-标准形不是唯一的，若把它记为Fs，则Fs仅仅是F（未Skolem化的前束式）的一个特例，取用不同的Skolem函数会得到不同的结果。当F为非永假公式时，Fs与F并不等价，但当F为永假时，Fs也一定是永假的，即Skolem化并不影响F的永假特性。这个结论很重要，可用定理形式描述如下：定理：若S是合式公式F的S-标准形之子句集，则F为永假的充要条件是S为不可满足的。子句集中所有元素（即子句）的合取式不为真，则称该子句集为不可满足的。谓词演算体系中还有一些很重要的概念，如谓词演算的可判定性问题、逻辑推论、推理规则的有效性、推理规则系统的完备性等等，对人工智能推理机制的研究都很有用。,24,2.5.2消解推理规则,消解式:设C1=L1和C2=L2是两个没有公共变元的子句,L1和L2分别是原子公式（具有相同的谓词符号，但一般具有不同的变量）。如果L1和L2存在最一般合一者,那么消解C1和C2推导出一个新子句()称为C1和C2的消解式。它是由取这两个子句的析取，然后消去互补对而得到的。,25,2.5.2消解推理规则(续),a)假言推理PPQ(即PQ)消解式Qb)合并PQPQ消解式QQ=Qc)重言式PQPQ消解式QQ或PPd)空子句PP消解式NILe)链式(三段论)PQ(即PQ)QR(即QR)消解式PR(即PR),26,2.5.3含有变量的消解式,对于含有变量的子句,如果谓词符号相同,而变量名不同,则需要找一个置换作用于父辈子句,使其含有互补文字,再进行消解。例1:B(x)B(x)C(x)消解式C(x)例2:P(x)Q(x)Q(f(y)置换=f(y)/x消解式P(f(y)例3:Px,f(y)Q(x)Rf(a),yPf(f(a),zR(z,w)置换=f(f(a)/x,f(y)/z消解式:Qf(f(a)Rf(a),yRf(y),w,27,2.5.4消解反演求解过程,基本思想:反证法:在反证法中首先假定要证明的结论不成立，然后通过推导出存在矛盾的方法，反证出结论成立。在归结法中首先对结论求反，然后将已知条件和结论的否定合在一起用子句集表达。如果该子句集存在矛盾，则证明了结论的正确性。思路：设S是已知条件和结论的否定合并后所对应的子句集。假定有一种变换方法，可以对S实施一系列的变换。而且该变换能够保证变换前后的子句集，在不可满足的意义下是等价的。这样，如果最终得到的子句集是不可满足的，就证明了子句集S是不可满足的，从而证明结论成立。由前面谓词公式转化为子句集的过程可知，子句集中的子句是与的关系，如果在子句集中出现了空子句，则说明该子句集是不可满足的。因此，归结过程就是寻找空子句的过程。如果把这一过程看作是搜索的话，初始状态就是已知条件和结论的否定对应的子句集，而目标就是空子句，规则就是归结。,28,2.5.4消解反演求解过程,1.消解反演已知一个公式集S和目标公式L,通过反证或反演来求证目标公式L,证明步骤如下:否定L,得到L;把L添加到S中去;把新产生的集合L,S化成子句集;应用消解原理,力图推导出一个表示矛盾的空子句。,29,2.5.4消解反演求解过程（续）,反演求解的正确性设公式L在逻辑上遵循公式集S，那么按照定义满足S的每个解释也满足L。决不会有满足S的解释能够满足L的，所以不存在能够满足并集SL的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，如果L在逻辑上遵循S，那么SL是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句NIL。因此，如果L在逻辑上遵循S，那么由并集SL消解得到的子句，最后将产生空子句；反之，可以证明，如果从SL的子句消解得到空子句，那么L在逻辑上遵循S。,30,2.5.4消解反演求解过程（续）,例:已知:每个储蓄钱的人都获得利息结论:如果没有利息,那么就没有人去储蓄钱。证明:定义谓词:S(x,y):表示”x储蓄y”M(x):表示”x是钱”I(x):表示”x是利息”E(x,y):表示”x获得y”已知:(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论:(x)I(x)(x)(y)(M(y)S(x,y),31,2.5.4消解反演求解过程（续）,1.否定结论:(x)I(x)(x)(y)(M(y)S(x,y)2.把结论加入已知,构成新集合G:(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y),(x)I(x)(x)(y)(M(y)S(x,y)3.将集合G化为子句集（y=f(x)为Skolem函数）(1)S(x,y)M(y)I(f(x)(2)S(x,y)M(y)E(x,f(x)(3)I(z)(4)S(a,b)(5)M(b),32,2.5.4消解反演求解过程（续）,4.应用消解原理进行推导。(1)S(x,y)M(y)I(f(x)(2)S(x,y)M(y)E(x,f(x)(3)I(z)(4)S(a,b)(5)M(b)(6)S(x,y)M(y)(1)和(3)消解=f(x)/z(7)M(b)(6)和(4)消解=a/x,b/y(8)NIL(5)和(7)消解,33,2.5.4消解反演求解过程（续）,消解反演可以表示为一棵反演树,34,2.5.4消解反演求解过程（续）,归结方法很简单，但是即便是对于一个比较简单的问题，往往可以进行归结的子句也比较多。如何从众多的可归结的子句中选择两个子句，即为搜索策略问题。不同的搜索策略，会影响到系统的效率和开销，同时也会涉及到完备性问题。搜索策略的目标就是要找到一棵归结反演树。一个反演系统当存在一个矛盾时，如果使用的一种策略，最终都将找到一棵反演树（即能找到矛盾），则这种策略是完备的。在实际应用中，有些策略虽不完备，但具有极高的效率，也是可取的。提高策略效率的一些作法是：只归结含有互补对的文字；及时删去出现的重言式和被其他子句所包含的子句；每次归结都取与目标公式否定式有关的子句作为母子句之一进行归结等等。,35,2.5.4消解反演求解过程（续）,2.反演求解过程问题的求解利用消解反演除了可以实现定理的自动证明之外，也可以对简单问题进行求解。例:张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。问现在李在哪里上课？,36,2.5.4消解反演求解过程（续）,从反演树求问题答案的过程：1.把问题的已知条件用谓词公式表示出来，并化为相应的子句集；2.把问题的目标的否定用谓词公式表示出来，并化为子句集；3.对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标否子句和此目标否定子句的否定之间再进行析取所得到的子句），用这些重言式代替相应的目标否定子句，并把这些重言式加入到前提子句集中，得到一个新的子句集。,37,2.5.4消解反演求解过程（续）,4.对这个新的子句集，应用消解原理求出其反演证明树，这时证明树的根子句不为空，称这个证明树为修改证明树；5.用修改证明树的根子句作为回答语句，则答案就在此根子句中。,38,2.5.4消解反演求解过程（续）,例：如果无论约翰(JOHN)到哪里去,菲多(FIDO)也就去那里,那么如果约翰在学校里,菲多在哪里呢?解：定义谓词：AT（x,y）:表示x在y处1.已知的谓词表示:(x)AT(JOHN,x)AT(FIDO,x),AT(JOHN,SCHOOL)化为子句集:AT(JOHN,y)AT(FIDO,y),AT(JOHN,SCHOOL),39,2.5.4消解反演求解过程（续）,2.目标否定的谓词表示：(x)AT(FIDO,x),(x)AT(FIDO,x)化为子句集:AT(FIDO,x)3.构造目标否定子句的重言式,并代替原子句AT(FIDO,x)AT(FIDO,x)4.将3得到的子句集加入前提子句集中:G=AT(JOHN,y)AT(FIDO,y),AT(JOHN,SCHOOL),AT(FIDO,x)AT(FIDO,x),40,2.5.4消解反演求解过程（续）,5.对新子句集G应用消解原理求出反演树:G=AT(JOHN,y)AT(FIDO,y),AT(JOHN,SCHOOL),AT(FIDO,x)AT(FIDO,x),41,2.5.4消解反演求解过程（续）,例：张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员A说“赵与钱中至少有一人作案”；侦察员B说“钱与孙中至少有一人作案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与孙中至少有一人与此案无关”；侦察员E说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都是可信的，试用消解反演推理求出谁是盗窃犯。定义谓词：P（x）：x作案。,42,2.5.4消解反演求解过程（续）,由五个侦察员的话为真，有P（z）P（q）（1）P（q）P（s）（2）P（s）P（l）（3）P（z）P（s）（4）P（q）P（l）（5）把结论的否定加入结论的否定的否定的子句中去，得：P（x）vP（x）（6）因为这些全都是子句，所以化为子句集的步骤可以省略了。（1），（4）归结得：P（q）P（s）（7）（2），（7）归结得：p（q）（8）即：钱是盗窃犯。,43,2.5.5含状态项的回答语句的求取,猴子和香蕉问题,44,2.5.5含状态项的回答语句的求取,ONBOX(S0),AT(box,b,S0),AT(monkey,a,S0)，HB(S0),pushbox(x,S)：在状态S下，猴子把箱子推到水平位置xclimbbox(S)：在状态S下，猴子爬上箱顶grasp(S)：在状态S下，猴子摘到香蕉,45,2.5.5含状态项的回答语句的求取,(x)(S)ONBOX(S)AT(box,x,pushbox(x,S)(S)ONBOX(climbbox(S)(S)ONBOX(S)AT(box,c,S)HB(grasp(S)(x)(S)AT(box,x,S)AT(box,x,climbbox(S)ONBOX(S0)(S)HB(S)要证的结论,46,2.5.5含状态项的回答语句的求取,ONBOX(S)AT(box,x,pushbox(x,S)ONBOX(climbbox(S)ONBOX(S)AT(box,c,S)HB(grasp(S)AT(box,x,S)AT(box,x,climbbox(S)ONBOX(S0)目标的非：HB(S),47,2.5.5含状态项的回答语句的求取,ONBOX(S1)AT(box,x,pushbox(x,S1)ONBOX(climbbox(S2)ONBOX(S3)AT(box,c,S3)HB(grasp(S3)AT(box,x,S4)AT(box,x,climbbox(S4)ONBOX(S0)目标的非：HB(S5),48,HB(S5),ONBOX(S3)AT(box,c,S3)HB(grasp(S3),ONBOX(S3)AT(box,c,S3),grasp(S3)/S5,ONBOX(climbbox(S2),climbbox(S2)/S3,AT(box,c,climbbox(S2),AT(box,x,S4)AT(box,x,climbbox(S4),S4/S2,c/x,ONBOX(S0),AT(box,c,S4),ONBOX(S1)AT(box,x,pushbox(x,S1),pushbox(x,S1)/S4,c/x,ONBOX(S1),S0/S1,NIL,49,2.6规则演绎系统,消解反演的局限:实际应用中,很多的事实更直观地表现为若干的规则IfThen(如果那么)其中If部分称为前项,Then部分称为后项。其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成例:表示为蕴含式:ABC,ACB,ABC,BAC都与子句:ABC等价一些重要信息在求取子句集过程中丢失;问题描述方式不自然。,50,2.6规则演绎系统（续）,规则演绎系统:基于规则求解问题的系统叫做规则演绎系统.两种推理方向正向推理:从if部分向then部分推理的过程,叫做正向推理。逆向推理:从then部分向if部分推理的过程,叫做逆向推理。按推理方向分类规则正向演绎系统:从事实出发利用规则推导出结论。规则逆向演绎系统:从目标出发利用规则推导出事实。规则双向演绎系统,51,2.6.1规则正向演绎系统,规则正向演绎系统:是从已知事实出发,正向使用规则对事实表达式的与或树进行变换，直到找到一个含有目标节点的一致解树为止。已知事实:事实表达式的与或树目标表达式：限制为文字的析取式F规则:LW,其中L为单文字,W为与或形。结束条件:目标表达式是析取式。得到结束于目标节点的一致解树。,52,2.6.1规则正向演绎系统（续）,1.事实表达式的与或形变换2.事实表达式的与或树表示3.与或图的F规则变换4.目标公式的表示形式5.规则正向演绎推理过程,53,2.6.1规则正向演绎系统（续）,1.事实表达式的与或形变换规则正向演绎系统中要求事实表达式化简为与或形。(1)消去”蕴含”和”双条件”符号;(2)减小否定符号的辖域,使否定符号只作用于原子公式;(3)利用Skolem函数消去存在量词;(4)对变量进行换名，使得不同的主要合取式中，具有不同的变量名;(5)隐去全称量词，默认公式中的变量受全称量词约束。,54,2.6.1规则正向演绎系统（续）,例:(x)(y)(Q(y,x)(R(y)P(y)S(x,y)消去量词化为:Q(y,a)(R(y)P(y)S(a,y)再变量更名化为:Q(z,a)(R(y)P(y)S(a,y),55,2.6.1规则正向演绎系统（续）,2.事实表达式的与或树(图)表示子表达式间的与、或关系规定如下:当母表达式为E1E2E3Ek时，则每一个子表达式Ei被表示成一个后继节点，并由一个k-连接符来连接；当母表达式为E1E2E3Ek时，则每一个子表达式Ei均由1-连接符连接。,56,2.6.1规则正向演绎系统（续）,Q(z,a)(R(y)P(y)S(a,y),事实表达的与或树表达式,57,2.6.1规则正向演绎系统（续）,与或树所有结束于叶节点的解树的求法从根节点(初始结点)开始，正确选择一个外向连接符，再从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行下去直到结束在叶结点上为止。例:求上例中的事实表达式的与或树的解树,58,2.6.1规则正向演绎系统（续）,59,2.6.1规则正向演绎系统（续）,与或树的性质:事实表达式的子句集与事实表达式的与或树解树集是一一对应的关系。事实表达式的与或树解树集中的每个解树都对应着子句集中的一个子句。解树集中每个解树的叶节点上的文字的析取就是子句集中的一个子句。例:Q(z,a)(R(y)P(y)S(a,y)化为子句集:Q(z,a),R(y)S(a,y),P(y)S(a,y),60,2.6.1规则正向演绎系统（续）,3.与或图的F规则变换规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式F规则:LW其中,L为单文字,W为与或形唯一公式。假设出现在蕴涵式中的任何变量都有全称量化作用于整个蕴涵式。这些事实和规则中的一些变量被分离标准化，使得没有一个变量出现在一个以上的规则中，而且使规则变量不同于事实变量。单文字前项的任何蕴涵式，不管其量化情况如何都可以化为某种量化辖域为整个蕴涵式的形式,61,2.6.1规则正向演绎系统（续）,F规则的化简例:(x)(y)(z)P(x,y,z)(u)Q(x,u)(1)暂时消去蕴涵符号;(x)(y)(z)P(x,y,z)(u)Q(x,u)(2)减少否定符号的辖域,使仅作用于文字;(x)(y)(z)P(x,y,z)(u)Q(x,u)(3)消去存在量词Skolem化;(x)(y)P(x,y,f(x,y)(u)Q(x,u)(4)化成前束式并消去全称量词;P(x,y,f(x,y)Q(x,u)(5)恢复蕴涵式表示。化简为:P(x,y,f(x,y)Q(x,u),62,2.6.1规则正向演绎系统（续）,对规则作单文字前项的限制将大大简化了应用时的匹配过程，对非单文字前项的情况，(L1L2)W转换成:L1W,L2W4.目标公式的表示形式目标公式要求:子句形即文字的析取式子句形的化简步骤:消去蕴涵符;减小否定符号的辖域;对变元标准化（变元换名）;化为前束范式（量词左移）;消去全称量词(对偶形式的skolem化);进行变元换名,使不同的主析取元具有不同的变元;消去存在量词,变量都受存在量词的约束;,63,2.6.1规则正向演绎系统（续）,例:(y)(x)(P(x,y)Q(x,y)用Skolem函数消去全称量词有:(y)(P(f(y),y)Q(f(y),y)进行变量更名有:(y)(P(f(y),y)(z)Q(f(z),z)消去存在量词:P(f(y),y)Q(f(z),z),64,2.6.1规则正向演绎系统（续）,5.规则正向演绎推理过程规则正向演绎推理过程:就是不断的对事实表达式的与或树施以F规则变换,直到找到一个一致解树,该解树中的所有叶节点全部都与目标公式中的文字匹配为止。如何进行F规则变换?如何判断终止?,65,2.6.1规则正向演绎系统（续）,命题逻辑的规则正向演绎过程F规则变换:如果在与或树中有一个叶节点刚好与某F规则LW的前件L匹配，则将该叶节点与L用一个匹配弧连接起来，将规则后件W添加到与或树中。这样,就对与或树用规则LW实施了一次变换,得到了一个“更新”了的与或树。例:事实表达式的与或形为:(PQ)R)(S(TU)规则:S(XY)Z,66,2.6.1规则正向演绎系统（续）,应用F规则得到的新与或树,67,2.6.1规则正向演绎系统（续）,与或树的变换与子句集的消解分析:事实表达式的子句集:S(PQ),SR,(TU)(PQ),(TU)R规则S(XY)Z对应的子句集:S(XZ),S(YZ)规则变换:新与或树对应的子句集(TU)(PQ),(TU)R,(XZ)(PQ),(XZ)R,(YZ)(PQ),(YZ)R,68,2.6.1规则正向演绎系统（续）,消解:将事实表达式和规则子句集合并S(PQ),SR,(TU)(PQ),(TU)R,S(XZ),S(YZ)作如下消解:S(PQ),S(XZ):(XZ)(PQ)S(PQ),S(YZ):(YZ)(PQ)SR,S(XZ):(XZ)RSR,S(YZ):(YZ)R得新的子句集:(TU)(PQ),(TU)R,(XZ)(PQ),(XZ)R,(YZ)(PQ),(YZ)R,69,2.6.1规则正向演绎系统（续）,结论:与或树的规则变换与消解之间具有一定的联系。应用一条规则到与或树的过程,以极其经济方式的达到了用其它方法要进行的多次消解才能达到的目的。,70,2.6.1规则正向演绎系统（续）,命题逻辑的规则演绎过程例:事实表达式：AB规则集：ACDBEG目标公式：CG,71,2.6.1规则正向演绎系统（续）,谓词逻辑的规则正向演绎过程a)事实表达式进行与或树表示;b)规则转换成F规则LW,其中L为单文字,W为与或形;c)目标表达式变换成子句形;d)对与或树进行F规则变换;e)结束条件:找到所有叶节点都与目标节点匹配的一致解树。,72,2.6.1规则正向演绎系统（续）,F规则变换:设与或树中有一个端节点的文字L和L可合一,mgu是u，则这条规则可应用,这时用匹配弧连接的后裔节点是L，它是规则后项Wu对应的与或树表示的根节点,在匹配弧上标记有u,表示用u置换后可与规则匹配。,73,2.6.1规则正向演绎系统（续）,例:事实与或形表示:P(A,y)(Q(x,A)R(B,y)规则蕴涵式:P(z,B)(S(z)X(B),应用一条规则的新与或树,74,2.6.1规则正向演绎系统（续）,上图应用规则变换后得到的与或树有两个解树,对应的两个子句是S(A)X(B)Q(x,A)S(A)X(B)R(B,B)事实和规则组成的子句集,对文字P进行归结:P(A,y)Q(x,A)P(A,y)R(B,y)P(z,B)S(z)X(B)R(B,B)S(A)X(B)归结=A/z,B/yQ(x,A)S(A)X(B)归结=A/z,B/y结论:规则的应用结果是得到这条规则的应用演绎出所有的逻辑推论。,75,2.6.1规则正向演绎系统（续）,一致解树一个具有一致置换的解树称为一致解树。一致置换:当置换集没有矛盾存在时，称该置换集是一致的，否则就是不一致的。例:1=a/x,b/y和2=b/x,c/z例:设已知事实的与或形表示为:P(x,y)(Q(x)R(v,y)F规则为:P(u,v)S(u)N(v)目标公式为:S(a)N(b)Q(c),76,2.6.1规则正向演绎系统（续）,谓词逻辑的规则演绎过程,77,2.6.2规则逆向演绎系统,规则逆向演绎推理:从目标表达式出发，反方向使用规则（B规则）对表示目标的与或树进行变换，直到得到含有事实节点的一致解树。目标表达式:目标的与或树事实表达式:限制为文字的合取形。规则:B规则,WL其中,W是任意形式的与或形，L是单文字终止条件:得到含有事实节点的一致解树。,78,2.6.2规则逆向演绎系统（续）,1.目标表达式的与或形变换2.目标公式的与或树表示3.B规则的表示形式4.已知事实的表示形式5.规则逆向演绎推理过程,79,2.6.2规则逆向演绎系统（续）,1.目标表达式的与或形变换(1)消去”蕴含”和”双条件”符号;(2)减小否定符号的辖域,使否定符号只作用于原子公式;(3)利用Skolem函数消去全称量词;(4)对变量进行换名，使得不同的主合取元，具有不同的变量名;(5)隐去存在量词，默认公式中的变量受存在量词约束。例:(y)(x)(P(x)(Q(x,y)(R(x)S(y)P(f(z)(Q(f(y),y)(R(f(y)S(y),80,2.6.2规则逆向演绎系统（续）,2.目标公式的与或树表示规定子表达式间的析取用1连接符连接，即表示为“或”的关系，而子表达式的合取用k连接符连接，即表示为“与”的关系。,目标公式的与或树表示,81,2.6.2规则逆向演绎系统（续）,与或树解树对应的子句(文字的合取):P(f(z),Q(f(y),y)R(f(y),Q(f(y),y)S(y)目标公式的析取范式中子句:P(f(z),Q(f(y),y)R(f(y),Q(f(y),y)S(y)3.B规则的表示形式B规则形式限制为:WL其中,W是任意形式的与或形，L是单文字，它表示L可以由W推导出。,82,2.6.2规则逆向演绎系统（续）,B规则化简：其中的变量受全称量词约束，如果有存在量词，则将其Skolem化，消去存在量词。当B规则为WL1L2时，则可化简为两条规则WL1和WL2来处理。4.已知事实的表示形式事实表达式均限制为文字合取形,它可以表示为一个文字集并且进行了普通的Skolem化简，变量受全称量词约束。,83,2.6.2规则逆向演绎系统（续）,5.规则逆向演绎推理过程:就是不断的对目标公式的与或树施以B规则变换，直到找到一个一致解树，该解树中的所有叶节点全部都与事实表达式中的文字匹配为止。B规则匹配和变换匹配:当与或树中有某个端点的文字和L可合一且mgu为u时，则B规则可应用变换:求出该叶节点与L的mguu，将该叶节点与L用一个匹配弧连接起来，用u对W进行置换，然后将Wu添加到与或树中。成功终止条件:与或树包含终止在事实节点上的一致解树。,84,2.6.2规则逆向演绎系统（续）,例:设有如下事实和规则:事实：F1:DOG(FIDO)；狗的名字叫FidoF2:BARKS(FIDO)；Fido是不叫的F3:WAGS-TAIL(FIDO)；Fido摇尾巴F4:MEOWS(MYRTLE)；猫咪的名字叫Myrtle规则：R1:(WAGS-TAIL(x1)DOG(x1)FRIENDLY(x1);摇尾巴的狗是温顺的狗R2:(FRIENDLY(x2)BARKS(x2)AFRAID(y2,x2)；温顺而又不叫的东西是不值得害怕的R3:DOG(x3)ANIMAL(x3)；狗为动物R4:CAT(x4)ANIMAL(x4)；猫为动物R5:MEOWS(x5)CAT(x5)；猫咪是猫问题：是否存在这样的一只猫和一条狗，使得这只猫不怕这条狗?,85,2.6.2规则逆向演绎系统（续）,1.目标表示为与或树目标用谓词公式表示:(x)(y)(CAT(x)DOG(y)AFRAID(x,y)消去存在量词化为与或形:CAT(x)DOG(y)AFRAID(x,y)目标公式表示成与或树2.规则符合B规则要求不需变换3.事实是文字的合取形DOG(FIDO),BARKS(FIDO),WAGSTAIL(FIDO),MEOWS(MYRTLE)4.规则逆向推理:分别应用规则R5,R2,R1变换5.找到一致解树,成功终止。,86,规则逆向演绎推理过程例,87,2.6.2规则逆向演绎系统（续）,一致解树（图）.所有匹配弧上的置换集：x/x5，MYRTLE/x,FIDO/y,x/y2,y/x2,FIDO/y,y/x1,FIDO/y,FIDO/y没有矛盾,是一致置换集。回答语句：CAT(MYRTLE)DOG(FIDO)AFRAID(MYRTLE,FIDO),88,89,2.6.3规则双向演绎系统,正向演绎和逆向演绎推理的局限性:正向演绎推理要求:目标公式必须可化简为文字的析取式。逆向演绎推理要求:事实表达式必须可化简为文字的合取式。限制了正向和逆向推理的应用范围。规则双向演绎推理任意形式的事实表达式和目标公式。同时采用规则正向和规则逆向推理。,90,2.6.3规则双向演绎系统（续）,规则双向演绎推理综合数据库:事实表达式的与或树(简称事实树)和目标公式的与或树(简称目标树)。规则库:F规则和B规则。规则双向演绎推理:运用F规则对事实树进行变换,运用B规则对目标树进行变换。终止条件:事实树与目标树的某个交接处。缺点：判断困难,较复杂。,91,2.6.3规则双向演绎系统（续）,终止条件:若标记于事实文字节点L1和目标文字节点L2上的文字有mguu,则在L1和L2之间建立匹配棱线连接,并用对应的mguu来标记匹配棱线。对于初始综合数据库,事实树和目标树间的匹配棱线必须在叶节点之间。当用F规则和B规则对图进行扩展之后,匹配就可以出现在任何文字节点上。例:设已知事实和目标分别为:事实:Q(x,a)(R(x)S(a)目标:P(f(y)(Q(f(y),y)(R(f(y)S(y),92,规则双向推理过程例,93,2.6.3规则双向演绎系统（续）,终止条件:当在事实树与目标树之间建立了所有的可能匹配棱线之后,目标树中根节点上的表达式是否已经根据事实树中根节点上的表达式和规则得到证明的问题仍然需要判定。判断方法:一个建立在事实节点和目标节点间一种叫做CANCEL的对称关系的基础上的判定方法。,94,2.6.3规则双向演绎系统（续）,CANCEL的递归定义:如果(n,m)中有一个为事实节点,另一个为目标节点,如果n和m都由可合一的文字所标记,则称这两节点n和m互相CANCEL(即互相抵消),否则如果n有外向k线连接符接至一个后继节点集Si且对此集的每个元素CANCEL(Si,m)都成立,那么也称这两节点n和m互相CANCEL。,95,2.6.3规则双向演绎系统（续）,当事实树的根节点和目标树的根节点互相CANCEL时,我们得到一个候补解。在事实和目标树内证明该目标根节点和事实根节点互相CANCEL的图结构叫做候补CANCEL图。如果候补CANCEL图中所有匹配的mgu都是一致的，那么这个候补解就是一个实际解。找到实际解,推理成功,目标得证。,96,2.7产生式系统,2.7.1产生式系统的组成2.7.2产生式系统的推理2.7.3产生式系统的控制策略,97,产生式系统(productionsystem)首先是由波斯特(Post)于1943年提出的产生式规则(productionrule)而得名的。他们用这种规则对符号串进行置换运算。后来，美国的纽厄尔和西蒙利用这个原理建立一个人类的认知模型(1965年)。同时，斯坦福大学利用产生式系统结构设计出第一个专家系统DENDRAL。产生式系统用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统(rulebasedsystem)。,98,2.7产生式系统（续）,产生式系统中的知识表示1.事实的表示：确定性的知识：命题、谓词、三元组(对象,属性,值)或(关系,对象1,对象2)老李和老张是朋友:（Friend,Lee,Chang）不确定性的知识：四元组(对象，属性，值，可信度因子)极少数花的颜色是黑的:（花，颜色，黑，0.1),99,2.7产生式系统（续）,2.推理过程和行为(规则)的表示产生式或规则：PQIFPTHENQP是产生式的前提，或称为前件是一组结论或操作，或称为后件IF(动物,本领,会下蛋)AND(动物,本领,会飞)THEN(动物,类别,鸟)IF(病人,症状,咳嗽)AND(病人,症状,流涕)THEN(病人,疾病,感冒,0.85),100,2.7.1产生式系统的组成,1.综合数据库：全局数据库，事实数据库2.产生式规则库：产生式规则3.控制系统：控制策略,推理机,101,2.7.1产生式系统的组成（续）,1.综合数据库是一个用来存放与求解问题有关的各种当前信息的数据结构。问题的初始状态、事实、证据、中间推理结论及最后结果等。2.产生式规则库是用来存放与求解问题有关的某个领域知识的规则的集合及其交换规则。这里所说的产生式规则和谓词逻辑中所讨论的产生式规则，从形式上看都采用了IF-THEN的形式，但这里所讨论的产生式更为通用。在谓词运算中的IF-THEN实质上是表示了蕴涵关系。也就是说要满足相应的真值表。这里所讨论的条件和操作部分除了可以用谓词逻辑表示外，还可以有其他多种表示形式，并不受相应的真值表的限制。,102,2.7.1产生式系统的组成（续）,3.控制系统：(1)匹配在这一步，把当前