归结演绎的归结策略课件.ppt

1、归结反演系统面临归结反演系统面临着大子句集而引起着大子句集而引起的演绎效率问题。的演绎效率问题。 若盲目地随机选择子句对进行归结，不仅要耗费许多时间，而且还会因为归结出了许多无用的归结式而过分扩张了子句集，从而浪费了时空，并降低了效率。 解决问题的关键解决问题的关键在于在于选择有利于选择有利于导致快速产生空导致快速产生空子句子句的子句对进的子句对进行归结行归结。 归结策略归结策略删除策略删除策略：限制策略：限制策略：通过通过删除删除某些某些无用无用的子句来的子句来缩小缩小归结的范围归结的范围 通过设置通过设置选用条件选用条件对参与对参与归结的子句进行种种归结的子句进行种种限制限制，减少减少归结

2、的盲目性归结的盲目性 ，如如支支持集、线性输入、单文字持集、线性输入、单文字子句优先、祖先过滤子句优先、祖先过滤等策等策略。略。 广度优先策略广度优先策略广度优先是一种穷广度优先是一种穷尽子句比较的复杂尽子句比较的复杂搜索方法搜索方法广度优先的归结过程：广度优先的归结过程：设初始子句集为S0,归结过程如下：1. 从S0出发，对S0中的全部子句作所有可能的归结，得到第一层归结式，把这些归结式的集合记为S1 。2. 用S0中的子句与S1中的子句作所有可能的归结，得到第二层归结式，把这些归结式的集合记为S2 。3. 用S0和S1中的子句与S2中的子句作所有可能的归结，得到第三层归结式，把这些归结式的

3、集合记为S3 。如此继续,直到得到空子句。例：子句集例：子句集S= I(x) R(x),I(a), R(x) L(y), L(a)S:S0:R(a)I(x)L(x)I(x)R(x)I(a)R(x) L(y)L(a)R(a)S1:L(a)L(a)I(a)I(a)NIL广度优先策略归结出广度优先策略归结出了许多无用的子句，了许多无用的子句，既浪费时间，有浪费既浪费时间，有浪费空间。容易引起组合空间。容易引起组合爆炸。爆炸。P(A)当问题有解时，用广当问题有解时，用广度优先策略归结能保度优先策略归结能保证找到最短路径。因证找到最短路径。因此，它是一种完备的此，它是一种完备的归结策略。归结策略。支持集

4、策略支持集策略要求每依次参加归结要求每依次参加归结的两个亲本子句中，的两个亲本子句中，至少应该有一个是由至少应该有一个是由目标公式的否定所得目标公式的否定所得到的子句或它们的后到的子句或它们的后裔。裔。支持集策略是完备的，支持集策略是完备的，即当子句集不可满足即当子句集不可满足时，由支持集策略一时，由支持集策略一定能够归结出一个空定能够归结出一个空子句。子句。例：子句集例：子句集S= I(x) R(x),I(a), R(x) L(y), L(a)S:S0:R(a)I(x)L(x)I(x)R(x)I(a)R(x) L(y)L(a)S1:L(a)L(a)I(a)NILS3:删除策略删除策略归结时将

5、归结时将无用无用的子句的子句删除删除掉，缩小搜索范掉，缩小搜索范围，减少比较次数，围，减少比较次数，从而提高归结效率。从而提高归结效率。常用的删除方法：常用的删除方法：（1）纯文字删除法纯文字纯文字：如果文字L在子句集中不存在与其互补的文字L，则称该文字为纯文字。例：对于子句集S=PQ R, Q R,Q, R其中P为纯文字，因此， PQ R可从S中删除。（2）重言式删除法重言式重言式：如果一个子句中包含有互补的文字对，则称该子句为重言式。例： P(x) P(x) 、 P(x) Q(x) P(x) （3）包孕删除法例： P(x)包孕于 P(y) Q(z) s =y/x P(x)包孕于 P(a)

6、s=a/x P(x ) Q(z)包孕于 P(f(x) Q(a) R(y) s=f(a)/x),a/z设有子句C1和C2，如果存在一个置换s,使得C1sC2，则称C1包孕于C2。 单文字子句策略单文字子句策略要求每次参加归结要求每次参加归结的两个亲本子句至的两个亲本子句至少有一个子句是少有一个子句是单单文字子句文字子句单文字子句单文字子句：如果一个子句只包含一个文字，则称此子句为单文字子句。例：子句集例：子句集S= I(x) R(x),I(a), R(x) L(y), L(a)S:S0:R(a)I(x)R(x)I(a)R(x) L(y)L(a)R(a)NIL采用单文字子句策略，采用单文字子句策略

7、，归结式包含的文字数归结式包含的文字数将少于其亲本子句中将少于其亲本子句中的文字数，这将有利的文字数，这将有利于向空子句的方向发于向空子句的方向发展。展。但这种归结策略是不完备的。即当子句集为不可满足时，用这种归结策略不一定能归结出空子句。线性输入策略线性输入策略要求每次参加归结要求每次参加归结的来年各个亲本子的来年各个亲本子句中，至少应该有句中，至少应该有一个是初始子句集一个是初始子句集中的子句。中的子句。例：子句集例：子句集S= I(x) R(x),I(a), R(x) L(y), L(a)S:S0:R(a)I(x)L(x)I(x)R(x)I(a)R(x) L(y)L(a)R(a)S1:I

8、(a)L(a)L(a)I(a)NIL线性输入策略可限制线性输入策略可限制生成归结式的数目，生成归结式的数目，具有简单高效的优点，具有简单高效的优点，但也是一种不完备的但也是一种不完备的策略。策略。例：子句集：例：子句集：S=Q(u) P(a) , Q(w) P(w),Q(x) P(x) ,Q(y) P(y) 从从S出发和容易找到一克归结反演树，却不存在出发和容易找到一克归结反演树，却不存在线性输入策略的归结反演树。线性输入策略的归结反演树。 祖先过滤策略祖先过滤策略每次参加归结的两个亲本子句，只要满足以下两每次参加归结的两个亲本子句，只要满足以下两个条件中的任意一个就可进行归结：个条件中的任意

9、一个就可进行归结：（1）两个亲本子句中至少有一个是初始子句集中）两个亲本子句中至少有一个是初始子句集中的子句。的子句。（2）如果两个亲本子句都不是初始子句集中的子）如果两个亲本子句都不是初始子句集中的子句，则一个子句应该是另一个子句的先辈子句。句，则一个子句应该是另一个子句的先辈子句。例：子句集：例：子句集：S= Q(x) P(x) , Q(y) P(y), Q(w) P(w) ,Q(a) P(A) 用祖先过滤策略证用祖先过滤策略证明明S为不可满足。为不可满足。 Q(x) P(x)Q(y) P(y) P(x) Q(w) P(w) Q(w)Q(a) P(A)P(A)NIL可以证明祖先过可以证明祖

10、先过滤策略也是完备滤策略也是完备的。的。实际应用中可以将几实际应用中可以将几种策略结合起来使用。种策略结合起来使用。在选择归结反演策略在选择归结反演策略时，主要应考虑其完时，主要应考虑其完备性和效率问题。备性和效率问题。作业作业1：设有子句集：设有子句集： P(x) Q(x,b) , P(a) Q(a,b) , Q(a,f(a) , P(x) Q(x,x)，分别用各种归结策略求出其归结，分别用各种归结策略求出其归结式。式。作业作业2：对子句集：对子句集：P Q, Q R, R W, R P, W Q, Q R用线性输入策略是否可证明用线性输入策略是否可证明该子句的不可满足性？该子句的不可满足性？