逻辑表示及归结系统课件.ppt

例:S={P(a,x,h(g(z))),P(z,h(y),h(y))}1.g0={};Sg0不是单元素集,故求不一致集D0={a,z};2.g1=g0{a/z};Sg1={P(a,x,h(g(a))),P(a,h(y),h(y))}不是单元素集,故D1={x,h(y)};3.g2=g1{h(y)/x};Sg2=(Sg1){h(y)/x}={P(a,h(y),h(g(a))),P(a,h(y),h(y))}不是单元素集,故D2={g(a),y};4.g3=g2{g(a)/y};Sg3=(Sg2){g(a)/y}={P(a,h(g(a)),h(g(a))),P(a,h(g(a)),h(g(a))}是可合一的.即g3={a/z}{h(y)/x}{g(a)/y}={a/z,h(y)/x}{g(a)/y}={a/z,h(g(a))/x,g(a)/y}是一个mgu.第31页，讲稿共49页，2023年5月2日，星期三3)谓词逻辑中的归结式归结式:对于子句C1?L1和C2?L2，如果L1与~L2可合一，且s是其合一者，则(C1?C2)s是其归结式.例：P(x)?Q(y),~P(f(z))?R(z) =Q(y)?R(z)(s=f(z)/x)选不同文字对做归结时,可得不同的归结式练习:C1=P(x，f(y))?Q(y)C2=~P(z，f（A）)?~Q(z)第32页，讲稿共49页，2023年5月2日，星期三3)谓词逻辑中的归结式(续)注意点:被归结的子句C1,C2应具有不同的变量.方法:变量换名在求归结式时,不能同时消去两个互补文字对,消去两个互补文字对所得到的结果不是亲本子句的逻辑推论.例.C1=P(..)?Q(..),C2=~P(..)?~Q(..)如在参加归结的子句内含有可合一的文字,则应先对这些文字进行合一,化简后再归结.例.C1=P(x)?P(f(a))?Q(x),C2=~P(y)?R(b)第33页，讲稿共49页，2023年5月2日，星期三定义谓词写出已知条件和结论的谓词关系公式化为Skolem标准型求子句集合S对S中可归结的子句做归结(置换和合一)归结式仍放入S中,反复归结过程看能否导出空子句4)谓词逻辑中的归结过程第34页，讲稿共49页，2023年5月2日，星期三例、已知：1.会朗读的动物是识字的；2.海豚都是不识字的；3.有些海豚很机灵。证明：有些很机灵的动物不会朗读。已知：1.(?x)(R(x)?L(x));2.(?x)(D(x)?~L(x));3.(?x)(D(x)?I(x))求证：(?x)(I(x)?~R(x))化简前提条件公式，结论取反，得子句集：（1）~R(x)?L(x)（2）~D(y)?~L(y)（3a）D（A）（3b）I（A）（4）~I(z)?R(z)第35页，讲稿共49页，2023年5月2日，星期三{A/z}{A/x}{A/y}（1）~R(x)?L(x)（2）~D(y)?~L(y)（3a）D（A）（3b）I（A）（4）~I(z)?R(z)从子句集求归结式，并将它加进子句集，连续进行直到产生空子句为止，上图的归结过程代表一个可行的证明过程~I(z)?R(z)I（A）NIL~R(x)?L(x)R（A）L（A）~D(y)?~L(y)D（A）~D（A）归结反演树第36页，讲稿共49页，2023年5月2日，星期三3归结反演系统

3.1产生式系统的基本算法综合数据库：子句集(子句间为合取关系)规则集合：IFcx（?Si）和cy（?Si）有归结式rxyTHENSi+1=Si?{rxy}目标条件：Sn中出现空子句过程1Clauses：=S；S为初始的基本子句集。2untilNIL是Clauses的元素，do：3begin4在Clauses中选两个不同的可归结的子句ci、cj5求ci、cj的归结式rij；6Clauses：={rij}?Clauses7end；第37页，讲稿共49页，2023年5月2日，星期三3.2搜索策略任务:是在算法的第4步中确定选哪两个子句做归结，以及在第5步决定这两个子句中对哪一个文字做归结主要策略:宽度优先:第一级(