问题求解的基本方法-基于归结的演绎推理

1、问题求解的基本方法 -基于归结的演绎推理, 2,复习,合适公式 合取范式 合适公式的可满足性, 3,合适公式的定义 单一谓词公式（即原子公式）是合适公式； 若A是合适公式，则A也都是合适公式； 若A和B都是合适公式，则AB、AB、A B和A B也都是合适公式； 4）若A是合适公式，x是约束变量，则（“x）A和（$x)A也是合适公式 5）只有按上述规则（1）至（4）求得的公式，才是合适公式, 4,合取范式和析取范式定义1：文字是原子公式或原子公式之非定义2：公式G称为合取范式 ，当且仅当G有形式G1 Gn(n=1)，其中每个Gi都是文字的析取式定义3：公式G称为析取范式 ，当且仅当G有形式G1 Gn(n=1)，其中每个Gi都是文字的合取式, 5,合适公式的永真性和可满足性,1） 合适公式的永真性 若某合适公式P对于某论域D上的所有可能的解释都有真值T，则称P在D上是永真的；若P在每个可能的非空论域上均永真，则称P是永真的。2） 合适公式的可满足性 对于合适公式P，若在论域D上至少可以建立一个解释，使P有真值T，则称P在D上是可满足的；若至少有一个论域使P可满足，则称P是可满足的。, 6,

2、一 归结演绎方法,F1, F2, ,Fn|= W F1F2Fn = W,证明的方法可分二大类 ： 直接证明F1F2Fn = W为永真, 即演绎法 间接证明(F1F2Fn = W)为永假，即反证法,反证法：F1F2Fn W 证明上式永假，这实际上就是要证明F1, F2, ,Fn W是一个矛盾集, 7,概念： 文字：谓词公式或其取反P（a,b)， Human(x), 父亲（a,A) 子句：一些文字的析取（谓词的和），不含任何文字的子句称为空子句，记为Q(y,b) R(x) 子句集：所有子句的集合 P(a,x,f(x), Q(g(x),b) P(a,x,f(x) Q(g(x),b)P(x,y) P(y,z),Q(x,z), 8,子句及子句集的作用：合取范式可以定义为子句的合取进而把合取范式表示为子句集当合适公式F化简为标准化的子句集S时，有一个重要性质，即S的不可满足(对于任意论域上的任意解释，S中都至少有一个子句真值为F)成为F永假的充分必要条件, 9,Skolem标准型前束范式中消去所有的量词，这种形式的合适公式称为Skolem标准型任何一个合适公式都可以转化为与之对应的Skolem标准

3、型，但不唯一,前束范式谓词公式P如果具有以下的形式，即把所有的量词都提到最左端去：（Q1x1)(Q2x2)(Qnxn)P(x1,x2,xn), 10,将合适公式G转换成前束范式；消去前束范式中的存在量词，略去其中的任意量词，生成Skolem标准型将Skolem标准型中的各个子句提出，表示为集合形式 可以看出Skolem标准型必须满足合取范式的条件,例如：P（a,x,f(x) Q(g(x),b) R(x)的子句集为：P（a,x,f(x) , Q(g(x),b) , R(x) ,子句集的求取过程：, 11,海伯伦（Herbrand）定理是归结原理的理论基础，归结原理是通过海伯伦定理 证明的，同时又是海伯伦定理 的具体实现。,1. H域和海伯伦定理,海伯伦定理思想：反证法，要证明一个公式是永假的，就是要寻找一个已给出的公式是真的解释。海伯伦定理的基本思想是简化论域，建立一个比较简单、特殊的域，使得只要在这个论域上，不可满足，那么就可以保证公式的不可满足性, 12,设S为子句集，D为S的某个论域，那么H域： (1) 令H0 是S中出现的所有常量的集合，若S中未出现常量，就任取常量a属于D,并令

4、H0 =a. (2)令Hi+1=Hi出现于S中的函数在Hi上的所有实例,i=1,2,；形如f(x1 ,x2, ,xn)的函数的实例通过让xj=kjHi来形成（j=1,2,n） 显然，Hi可以迭代扩展到H，我们称H为海伯伦域，简称H域,H域, 13,例如, 对于子句集S= P(x)R(f(x),Q(y,g(y)， 有： H0=a, 任取一常量aD； H1=a，f(a),g(a) H2=a，f(a),g(a), f(g(a),g(f(a), f(f(a),g(g(a) ., 14,例如, 对于子句集S= P(a)Q(b)，R(f(z,y)， 有： H0=a，b；H1=a，b，f(a,a)，f(a,b)，f(b,a)，f(b,b)H2=？., 15,对于子句集S=P（x)，Q(y) R(z) H0=H1=H=a, 16,定义H域上的原子谓词公式实例集A：A=所有出现于S中原子谓词公式的实例例如：子句集S= P(x)R(f(x),Q(y,g(y)H0=a, 任取一常量aD； H1=a，f(a),g(a) A=P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a),称A中的元素

5、为基原子，A称为基原子集 所以，只要给它们每个指定一个真值（T或F），就可建立子句集在H域上的一个解释，记为I*。, 17,可以证明：对于子句集S的任一可能论域D上的任一解释I，总能在S的H域上构造一个相应的解释I*，使子句集具有相同的真值。所以，只要能够确定子句集对H域上所有解释都不满足，就可确定，对于任意可能论域上的所有解释，子句集都不满足，即子句集是不可满足的。, 18,当子句集中一子句包含的变量用H域中元素取代时（即该元素作为变量值），称这样产生的子句为基子句。由有限个不可同时满足的基子句构成的集合S，称为基子句集。, 19,海伯伦定理子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S困难： 子句集的不可满足性是不可判的，既不能确保在有限步数内判定 即使能判定，计算量也巨大。, 20,二 归结原理,为提高判定子句集不可满足的有效性，鲁宾逊于1965年提出了归结(Resolution)原理，也称为消解原理 归结原理简单易行，便于计算机实现和执行，从而使定理的机器自动证明成为现实，也成为人工智能技术实用化的一次重要突破, 21,归结原理的基本思路通过归结方法不断扩充待判

6、定的子句集，并设法使其包含进指示矛盾的空子句 ，从而达到判定子句集具有不可满足 性, 22,1. 归结方法 1） 归结式 设有二个子句： C1 = LC1 , C2 = L C2 从C1 和C2 中消去互补文字L和L，并通过析取将C1 和C2 的剩余部分组成新的子句： C = C1 C2 则称C为C1 和C2 的归结式，例如有子句 P(A)Q(x)R(f(x), P(A)Q(y)R(y) 则可以消去互补文字P(A)和 P(A), 生成归结式： Q(x)R(f(x)Q(y)R(y), 23,2）归结式性质 定理：二个子句C1 和C2的归结式C是C1 和C2 的逻辑推论。 该定理意指，在任一使子句C1 和C2为真的解释下，必有归结式C为真。 推论：设C1 和C2 是子句集S中的两个子句，并以C作为它们的归结式，则通过往S中加入C而产生的扩展子句集S与子句集S在不可满足的意义上是等价的，即 S的不可满足 S的不可满足。 这个推论确保了用归结原理来判定子句集不可满足的可行性。, 24,3） 空子句 当C1 = L和C2 = L时，归结式为空；我们以口指示为空的归结式，并称C = 口为空子句。显

7、然C1 和C2是一对矛盾子句-无论为子句集指派什么解释，C1 和C2不可同时满足，所以空子句实际上是不可满足的子句，进而导致子句集不可满足。 换言之，空子句成为用归结原理判定子句集不可满足的成功标志。, 25,归结推理过程 1）命题逻辑中的归结推理过程 例子：S=PQ, PR, Q, R, 26,2） 谓词逻辑中的归结推理过程定理：合适公式G是不可满足的，当且仅当其子句集S是不可满足的,谓词逻辑中含有变量，需要通过变量置换和合一处理 ，才能进行归结。合一处理，就是通过变量置换，使相应于这两个文字的原子谓词公式同一化的过程 变量置换就是用置换项取代公式中的变量，置换项可以是变量、常量或函数,例如：P(x) Q(y) 与 P(a) R(z), 27,例如：P(x, y, x, g(x), P(A, B, A, z),可以为它们建立多个置换： S1 = A/x, B/y, g(x)/z S2 = f(w)/x, z/y, C/z S3 = 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(

8、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), 28,检查两个原子谓词公式的可合一性 ： （1） 二个公式必须具有相同的谓词和参数项个数； （2） 从左到右逐个检查参数项的可同一性： 若一对参数项中有一个变量v（不必关注另一个是否变量），并初次出现，则这对参数项可同一，并以另一参数t为置换项，与该变量一起构成一个置换元素t/v； 若该变量出现过，则已建立相应的置换元素，就取取其置换项，代替该变量，检查是否与另一参数同一；若不能同一，则合一处理失败。 若一对参数项中没有一个是变量（往往都是常量），则它们必须相同，否则合一处理失败。 （3） 若每对参数项都可同一，则合一处理成功，并构成用于实现合一的置换, 29,实例：（1）R(x, y)Q(y)P(f(x) (2) R(z, y)Q(y)W(x, f(x) (3) P(z) (4

9、) R(A, B) (5) Q(B),步骤： （6）R(x,yQ(y), （1）与（3）归结，f(x)/z (7) Q(B) （6）与（4）归结，A/x,B/y (8) 口， （7）与（5）归结，, 30,归结演绎树, 31,问题：假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的, 32,解答步骤：R1：任何通过计算机考试并获奖的人都是快乐的（“x）（Pass(x,computer) Win(x,prize) = Happy(x)R2: 任何肯学习或幸运的人都可以通过所有的考试（姜海燕除外）（“x） （“y）Study ( y) Lucky(x) = Pass(x,y)R3: 张不肯学习但他是幸运的 Study(zhang) Lucky(zhang) R4: 任何幸运的人都能获奖（“x） (Lucky(x) = Win(x,prize)结论：“张是快乐的”的否定Happy(zhang), 33,三 归结反演,归结演绎方法为采用间接法（即反证法）证明定理提供了有效手段，我们称应用归结演绎方法的定理证明为归结反演,归结反演的基本思路是：要从作为事实的公式集F证明目标公式W为真，可以先将W取反，加入公式集F,标准化F为子句集S，再通过归结演绎证明S不可满足，并由此得出W为真的结论,

《问题求解的基本方法-基于归结的演绎推理》由会员龙***分享，可在线阅读，更多相关《问题求解的基本方法-基于归结的演绎推理》请在金锄头文库上搜索。