高级人工智能确定性推理

1、人工智能2016年秋季本章内容本章内容 推理推理的基本概念的基本概念 推理推理的逻辑基础的逻辑基础 自然演绎推理自然演绎推理 归结推理归结推理本章内容本章内容 推理推理的基本概念的基本概念 推理推理的逻辑基础的逻辑基础 自然演绎推理自然演绎推理 归结推理归结推理什么什么是推理是推理 推理推理是是指按照某种策略从已知事实出发去推出结论的过指按照某种策略从已知事实出发去推出结论的过程。程。 推理推理所用的事实：所用的事实： 初始初始证据：证据：推理前用户提供的 中间结论：中间结论：推理过程中所得到的 推理推理过程：过程：由推理机来由推理机来完成完成 推理推理的两个基本问题的两个基本问题 推理的方法

2、：推理的方法：解决解决前提和结论的逻辑关系，不确定性传递前提和结论的逻辑关系，不确定性传递 推理的控制策略：推理的控制策略：解决推理方向，冲突消解策略解决推理方向，冲突消解策略推理推理方法及其方法及其分类分类 演绎推理：演绎推理： 一般一般到个别的推理到个别的推理方法：方法：从从已知的一般性知识出发，去推出蕴已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的含在这些已知知识中的适合于某种个别情况的结论结论 核心核心：三段论。三段论。 常用常用的的三段论包括：三段论包括：大前提：大前提：已知的一般性知识或推理过程得到的判断小前提：小前提：关于某种具体情况或某个具体实例的判断结

3、论：结论：由大前提推出的，并且适合于小前提的判断。 例如，有如下三个判断：例如，有如下三个判断： 计算机系的学生都会编程序；计算机系的学生都会编程序； （一般性知识）（一般性知识） 程强是计算机系的一位学生；程强是计算机系的一位学生； （具体情况）（具体情况） 程强会编程序。程强会编程序。 （结论）（结论） 归纳推理：归纳推理：由由个别到一般的推理个别到一般的推理方法方法完全归纳推理：完全归纳推理：是是指在进行归纳时需要考察相应事物的指在进行归纳时需要考察相应事物的全部对象全部对象，并根，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性据这些对象是否都具有某种属性，推出该类事物是否

4、具有此属性。不完全归纳推理：不完全归纳推理：是是指在进行归纳时只考察了相应事物的部分对象，就指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，随机抽查。得出了关于该事物的结论。例如，随机抽查。枚举归纳推理：枚举归纳推理：是是指在进行归纳时，如果已知某类事物的有限可数个具指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性体事物都具有某种属性，则可推出该类事物都具有此种属性。例如，设有如下事例： 王强是计算机系学生，他会编程序； 高华是计算机系学生，她会编程序； 当这些具体事例足够多时，就可归纳出一个一般性的知识： 凡是计算机

5、系的学生，就一定会编程序。推理推理方法及其方法及其分类分类类比类比归纳推理：归纳推理：是在两个或两类事物有许多属性都相同或相似的基属性都相同或相似的基础上础上，推出它们在其他属性上也相同推出它们在其他属性上也相同或相似的一种归纳推理设设A、B分别是两类事物的集合：分别是两类事物的集合： A=a1,a2, B=b1,b2,并设并设ai与与bi总是成对出现，且当总是成对出现，且当ai有属性有属性P时，时，bi就有属性就有属性Q与此对应，即与此对应，即 P(ai)Q(bi) i=1,2,.则则当当A与与B中有一新的元素对出现时，若已知中有一新的元素对出现时，若已知a有属性有属性P，b有属性有属性Q，

6、即，即 P(a)Q(b)类比类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。关程度。推理推理方法及其方法及其分类分类演绎推理与归纳推理的区别演绎推理与归纳推理的区别演绎推理：演绎推理：在已知领域内的一般性知识的前提下，通过演绎或者不能增殖新不能增殖新知识：知识：所得出的结论蕴含在一般性知识的前提中，推理过程是将已有事实揭露出来归纳推理归纳推理所推出的结论是没有包含在前提内容中的增殖新知识的增殖

7、新知识的过程：过程：是由个别事物或现象推出一般性知识的过程。推理推理方法及其方法及其分类分类 按按所用知识的确定性分类所用知识的确定性分类 确定性确定性推理推理 vs. 不确定性推理不确定性推理 按按推理过程的单调性分类推理过程的单调性分类 单调推理单调推理 vs. 非单调推理非单调推理 单调：不会由于新知识的加入否定前面的单调：不会由于新知识的加入否定前面的结论结论 (不能不能取消原有的取消原有的结论结论) 非非单调：知识不完全情况下，某些新知识的加入会否单调：知识不完全情况下，某些新知识的加入会否定前面的定前面的结论结论推理推理方法及其方法及其分类分类推理推理的控制策略及其分类的控制策略及

8、其分类推理的控制策略推理的控制策略 推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略 推理的控制策略是指推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略如何使用领域知识使推理过程尽快达到目标的策略控制控制策略的分类策略的分类 推理策略主要推理策略主要解决推理方向、冲突消解等问题解决推理方向、冲突消解等问题，如推理方向控制策略、，如推理方向控制策略、求解策略、限制策略、冲突消解策略等求解策略、限制策略、冲突消解策略等 推理推理方向控制方向控制策略：策略：确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双

9、向推理。 求解求解策略策略：确定是仅求一个解、求所有解、还是最优解等。 限制限制策略：策略：对推理的深度、宽度、时间、空间等进行的限制。 冲突消解冲突消解策略：策略：当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。 搜索策略主要搜索策略主要解决推理线路、推理效果、推理效率等解决推理线路、推理效果、推理效率等问题问题正向推理正向推理逆向推理逆向推理混合混合推理推理混合混合推理推理 把把正向推理和逆向推理结合起来所进行的正向推理和逆向推理结合起来所进行的推理推理 用于解决用于解决较复杂较复杂问题。问题。混合推理的方法混合推理的方法 先先正向后正向后逆向：逆向：先进

10、行正向推理，从已知事实出发推出部分结果，然先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。后再用逆向推理对这些结果进行证实或提高它们的可信度。 先逆向后先逆向后正向：正向：先先进行逆向推理，从假设目标出发推出一些中间假设，进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。然后再用正向推理对这些中间假设进行证实。 双向双向混合：混合：正向推理和逆向推理同时进行，使推理过程在中间的某一正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。步结合起来。本章内容本章内容 推理推理的基本概念的基本概念 推理推理

11、的逻辑基础的逻辑基础 自然演绎推理自然演绎推理 归结推理归结推理谓词谓词公式的公式的解释解释（语义）（语义） 命题逻辑命题逻辑 vs. 谓词逻辑谓词逻辑 命题逻辑：命题逻辑：命题符号P，Q代表一定的命题，看不出关系，表达不出共同特征 谓词逻辑：谓词逻辑： 可表示关系。如：Weather(Tuesday，Rain） 允许包含变元。如： Weather（X，Rain） 命题公式命题公式的的解释：解释： 命题公式命题公式的一个解释就是对该谓词公式中的一个解释就是对该谓词公式中各个命题变各个命题变元的元的一次真一次真值值指派指派 可根据解释求出该命题公式可根据解释求出该命题公式的的真值真值 谓词公式谓

12、词公式的解释的解释： 先考虑这些先考虑这些个体常量和函数在个体域上的取值个体常量和函数在个体域上的取值， 然后根据其具体然后根据其具体取值为取值为谓词分别指派真值谓词分别指派真值。 设设D是谓词公式是谓词公式P的非空个体域，若对的非空个体域，若对P中的个体常量、函数和中的个体常量、函数和谓词按如下规定赋值：谓词按如下规定赋值：为为每个个体常量指派每个个体常量指派D D中的一个元素；中的一个元素；对对每一个变元，指派每一个变元，指派D D的一个非空集合，这是该变元的变域的一个非空集合，这是该变元的变域( (个个体域体域) )；为为每个每个n n元函数指派一个从元函数指派一个从D Dn n到到D

13、D的一个映射，其中的一个映射，其中 D Dn n =(x=(x1 1, x, x2 2, , x, , xn n)| x)| x1 1, x, x2 2, , x, , xn nDD为为每个每个n n元谓词指派一个从元谓词指派一个从D Dn n到到FF，TT的映射。的映射。则称这些指派为则称这些指派为P P在在D D上的一个解释上的一个解释I I谓词谓词公式的公式的解释解释（语义）（语义）谓词公式的谓词公式的解释解释（语义）（语义）例例1 1：设设个体域个体域D=1, 2D=1, 2，求，求公式公式A=(A=(x)( y)P(x, y)x)( y)P(x, y)在在D D上上的解释，并指出在每

14、一种解释下公式的解释，并指出在每一种解释下公式A A的真值。的真值。 解解：由于公式由于公式A A中没有包含个体常量和函数，故可直接为谓词指中没有包含个体常量和函数，故可直接为谓词指派真值，设有派真值，设有把把P P理解为一个元素为二元组的集合理解为一个元素为二元组的集合 P=(1,1),(2,1) P=(1,1),(2,1) P(1,1) P(1,2) P(2,1) P(2,2) T F T F谓词公式的谓词公式的解释解释（语义）（语义）例例1 1：设设个体域个体域D=1, 2D=1, 2，求，求公式公式A=(A=(x)( y)P(x, y)x)( y)P(x, y)在在D D上上的解释，并

15、指出在每一种解释下公式的解释，并指出在每一种解释下公式A A的真值。的真值。 解解：由于公式由于公式A A中没有包含个体常量和函数，故可直接为谓词指中没有包含个体常量和函数，故可直接为谓词指派真值，设有派真值，设有这就是公式这就是公式A A 在在D D 上的一个解释。从这个解释可以看出：上的一个解释。从这个解释可以看出： 当当x=1x=1、y=1y=1时，有时，有P(x,y)P(x,y)的真值为的真值为T;T; 当当x=2x=2、y=1y=1时，有时，有P(x,y)P(x,y)的真值为的真值为T;T; 即对即对x x在在D D上的任意取值，都存在上的任意取值，都存在y=1y=1使使P(x,y)

16、P(x,y)的真值为的真值为T T。因此，在此解释下公式因此，在此解释下公式A A的真值为的真值为T T。 P=(1,1),(2,1)P=(1,1),(2,1)说明：说明：一个谓词公式在其个体域上的解释不是唯一的一个谓词公式在其个体域上的解释不是唯一的。例如，。例如，对公式对公式A A，若给出另一组真值指派，若给出另一组真值指派这这也是公式也是公式A A 在在D D 上的一个解释。从这个解释可以看出：上的一个解释。从这个解释可以看出： 当当x=2x=2、y=1y=1时，有时，有P(x,y)P(x,y)的真值的真值为为F;F; 当当x=2x=2、y=2y=2时时，有，有P(x,y)P(x,y)的

17、真值为的真值为F;F;即对即对x x在在D D上的任意取值，不存在一个上的任意取值，不存在一个y y使得使得P(x,y)P(x,y)的真值为的真值为T T。因此，在此解释下公式因此，在此解释下公式A A的真值为的真值为F F。 P(1,1) P(1,2) P(2,1) P(2,2) TT F F谓词公式的谓词公式的解释解释（语义）（语义）公式公式A=(A=(x)( y)P(x, y)x)( y)P(x, y)P=(1,1),(1,2)P=(1,1),(1,2)例例2 设个体域设个体域D=1, 2，给出公式，给出公式B=(x)P(f(x), a)在在D上的解释，并指出上的解释，并指出在该解释下公

18、式在该解释下公式B的真值。的真值。解解：设对个体常量：设对个体常量a和函数和函数f(x)的值指派为：的值指派为：对谓词的真值指派为：对谓词的真值指派为：根据根据此此解释下有解释下有 当当x=1时，时，a=1使使P(1,1)=T 当当x=2时，时，a=1 使使P(2,1)=T即对即对x在在D上的任意取值，都存在上的任意取值，都存在a=1使使P(f(x), a)的真值为的真值为T。因此，在此。因此，在此解释下公式解释下公式B的真值为的真值为T。可以可以看出，看出，谓词公式的真值都是针对某一个解释而言的谓词公式的真值都是针对某一个解释而言的，它可能在某一，它可能在某一个解释下真值为个解释下真值为T，

19、而在另一个解释下为，而在另一个解释下为F。af(1)f(2)112P(1,1)P(1,2)P(2,1)P(2,2)T T谓词公式的谓词公式的解释解释（语义）（语义）谓词谓词公式的永真性和可满足性公式的永真性和可满足性 永真性：永真性：如果谓词公式P对非空个体域D上的任一解释都取得真值T，则称P在D 上是永真的；如果P在任何非空个体域上均是永真的，则称P永真。 可满足性（相容性）：可满足性（相容性）：对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的。 永假性（不可满足性）：永假性（不可满足性）：如果谓词公式P对非空个体域D上的任一解释都取真值F

20、，则称P在D上是永假的；如果P在任何非空个体域上均是永假的，则称P永假。谓词公式的等价性谓词公式的等价性 谓词公式的等价性：谓词公式的等价性：设设P与与Q是是D上的两个谓词公式，若对上的两个谓词公式，若对D上的任意解释，上的任意解释，P与与Q都有都有相同的真值，则称相同的真值，则称P与与Q在在D 上是等价的上是等价的。如果如果D是任意非空个体域，则称是任意非空个体域，则称P与与Q是等价的，记作是等价的，记作PQ。 (1) 双重否定律双重否定律 P P(2) 交换律交换律 (PQ) (QP)， ( PQ) ( QP)(3) 结合律结合律 (PQ)R P(QR) (PQ)R P(QR)(4) 分配

21、律分配律 P(QR) (PQ)(PR) P(QR) (PQ)(PR)(5)德摩根德摩根(否定否定)律律 (PQ) P Q (PQ) P Q(6) 吸收律吸收律 P(PQ) P P(PQ) P(7) 补余律补余律 P P T, P P F (8) 连词化归律连词化归律 PQ PQ PQ (PQ)(QP) PQ (PQ)( Q P)(9) 量词转换律量词转换律 (x)P (x)( P) (x)P (x) ( P)(10) 量词分配律量词分配律 (x) (PQ) (x)P(x)Q (x) (PQ) (x)P(x)Q置换律：置换律：(PQ) (QP)常用的等价式常用的等价式谓词公式的永真蕴含式谓词公式

22、的永真蕴含式永真蕴含：永真蕴含：对对谓词公式谓词公式P P和和Q Q，如果，如果PQPQ永真，则称永真，则称P P 永真蕴含永真蕴含Q Q，且称，且称Q Q为为P P的的逻辑结论，逻辑结论，P P为为Q Q的前提，记作的前提，记作P P Q Q。 (1) 化简式化简式 PQ P， PQ Q (2) 附加式附加式 P PQ， Q PQ (3) 析取三段论析取三段论 P, PQ Q (4) 假言推理假言推理 P, PQ Q (5) 拒取式拒取式 Q, PQ P (6) 假言三段论假言三段论 PQ, QR PR (7) 二难推理二难推理 PQ, PR, QR R (9) 存在固化存在固化 (x)P(

23、x) P(y)其其中，中，y是个体域中某一个可以使是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。为真的个体，依此可消去谓词公式中的存在量词。等价等价式和永真蕴含式也式和永真蕴含式也称推理称推理规则规则谓词公式的范式谓词公式的范式范式范式是谓词公式的标准形式。在谓词逻辑中，范式分为两种：是谓词公式的标准形式。在谓词逻辑中，范式分为两种：前束范式前束范式 例如例如，(x) (y) (z)(P(x)Q(y,z)R(x,z)是前束范式。是前束范式。 任任一谓词公式均可化为与其对应的一谓词公式均可化为与其对应的前束范式前束范式Skolem范式范式 任一谓词公式均可化为与其对应

24、的任一谓词公式均可化为与其对应的Skolem范式范式设设F为一谓词公式，如果其中的所有量词为一谓词公式，如果其中的所有量词均非否定地均非否定地出现在公式的最前面，且它出现在公式的最前面，且它们的辖域为整个公式，则称们的辖域为整个公式，则称F为前束范式。一般形式：为前束范式。一般形式： (Q1x1)(Qnxn)M(x1,x2,xn)其中，其中，Qi(i=1,2,n)为前缀，它是一个由全称量词或存在量词组成的量词串；为前缀，它是一个由全称量词或存在量词组成的量词串； M(x1,x2,xn)为母式，它是一个不含任何量词的谓词公式。为母式，它是一个不含任何量词的谓词公式。如果前束范式如果前束范式中中不

25、包含存在量词且不包含存在量词且母母式式M M是是“合取范式合取范式”，则称这种形式的谓词则称这种形式的谓词公式为公式为SkolemSkolem范式。范式。置换置换可简单的理解为是在一个谓词公式中可简单的理解为是在一个谓词公式中置换置换置换置换是形是形如如 t1/x1,t2/x2,tn/xn 的的有限集合。其中，有限集合。其中，t1,t2,tn是项是项；x1,x2, xn是互不相同的变元；是互不相同的变元；ti/xi表示用表示用ti替换替换xi。并且。并且要求要求ti与与xi不能相不能相同，同，xi不能循环地出现在不能循环地出现在tj（j=1n）中）中。a/x, c/y, f(b)/z g(y)

26、/x, f(x)/y x与y之间出现了循环置换现象。即当用g(y)置换x,用f(g(y)置换y时，既没有消去x，也没有消去yg(a)/x, f(x)/y 用g(a)置换x ，用f(g(a)置换y ，则消去了x和y通常，置换是用希腊字母通常，置换是用希腊字母、 、 等来表示的等来表示的设设=t1/x1,t2/x2,tn/xn是一个置换，是一个置换，F是一个谓词公式，把公式是一个谓词公式，把公式F中出现中出现的所有的所有xi换成换成ti(i=1,2,n)，得到一个新的公式，得到一个新的公式G，称，称G为为F在置换在置换下的下的例示例示，记作，记作G=F。一个谓词公式的任何例示都是该公式的逻辑结论一

27、个谓词公式的任何例示都是该公式的逻辑结论合一合一: 寻找寻找项对变量的置换，使两个谓词公式项对变量的置换，使两个谓词公式一致一致例如，设有公式集例如，设有公式集F=P(x,y,f(y), P(a,g(x),z)，则，则=a/x, g(a)/y, f(g(a)/z是它的一个合一是它的一个合一。 一一个公式集的合一不是唯一个公式集的合一不是唯一的的，但最一般合一是唯一的。，但最一般合一是唯一的。合一合一设有公式集设有公式集F=F1, F2,Fn，若存在一个置换，若存在一个置换，可使，可使 F1=F2=Fn，则称则称是是F的一个合一。称的一个合一。称F1,F2,Fn是可合一的是可合一的设设是公式集是

28、公式集F的一个合一，如果对的一个合一，如果对F的任一个合一的任一个合一都存都存在一个置换在一个置换，使得，使得=，则称，则称是一个是一个最一般合一最一般合一合一合一 如何高效实现合一算法呢？如何高效实现合一算法呢？提示：由于谓词、函数等只是符号，合一过程中没有使提示：由于谓词、函数等只是符号，合一过程中没有使用其语义信息，仅仅使用其语法信息，因此，将其转换用其语义信息，仅仅使用其语法信息，因此，将其转换成成list的表示形式的表示形式合一的算法可以通过递归实现本章内容本章内容 推理推理的基本概念的基本概念 推理推理的逻辑基础的逻辑基础 自然演绎推理自然演绎推理 归结推理归结推理自然自然演绎推理

29、演绎推理 自然自然演绎推理：演绎推理：从一组已知为真的事实出发，直接运用经典逻从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。辑中的推理规则推出结论的过程称为自然演绎推理。 自然自然演绎推理最基本的推理规则是演绎推理最基本的推理规则是三段论推理三段论推理，它包括：，它包括： 假言推理假言推理 P, PQ Q 拒拒取式取式 Q, PQ P 假言假言三段论三段论 PQ, QR PR例：设已知如下事实：A, B, AC, BCD, DQ。求证：Q为真。 证明： 因为 A, AC C 假言推理 B, C BC 引入合取词 BC，BCD D 假言推理 D, DQ Q

30、 假言推理 因此，Q为真机器自动推理机器自动推理 能否设计一个算法，自动证明能否设计一个算法，自动证明PQ永永真。真。 如果这个算法存在，则证明过程，变如果这个算法存在，则证明过程，变成了一个计算过程成了一个计算过程归结归结演绎推理演绎推理在在人工智能中人工智能中，很多问题，很多问题都可以转化为一个定理证明都可以转化为一个定理证明问题问题，即对即对前提前提P和结论和结论Q，证明，证明PQ永永真。真。 途径途径1：证明PQ在任何一个非空的个体域上都永真 （非常困难，甚至不可实现）的 途径途径2：反证法. 把把关于永真性的证明转化为关于不可满足性的证明关于永真性的证明转化为关于不可满足性的证明。即

31、：证明 (PQ) 或 P Q是不可满足 鲁宾逊鲁宾逊归结原理归结原理(亦亦称为消解称为消解原理原理): 鲁宾逊于1965年在海伯伦（Herbrand）理论的基础上提出的基于逻辑的“反证法” 使定理证明的机械化成为现实。归结演绎推理归结演绎推理是一种基于鲁宾逊（是一种基于鲁宾逊（Robinson）归结归结原理的机器推理技术。原理的机器推理技术。John Alan RobinsonJ. A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 1965, 12(1):23

32、-41机器自动推理机器自动推理 子句集的化简子句集的化简 归结归结子句和子句集子句和子句集 鲁鲁滨逊滨逊归结原理归结原理的基础是的基础是子句集子句集 子句子句和子句集和子句集 文字：文字：原子谓词公式及其否定 例如：例如：P(x)、Q(x)、 P(x)、 Q(x) 子句：子句：任何文字的析取式 例如：例如：P(x)Q(x)，P(x，f(x)Q(x，g(x) 空子句：空子句：不含任何文字的子句，通常被一般被记为或NIL 空子空子句是永假的，不可满足的句是永假的，不可满足的。 子句子句集：集：由子句或空子句所构成的集合子句集的化简子句集的化简 任何任何一个谓词公式都可以通过应用等价关系及推理规则化

33、一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集成相应的子句集。 化化简简步骤：步骤： (1) 消去连接词消去连接词“”和和“” 反复使用例如：例如： (x)(y)P(x,y) (y)(Q(x,y)R(x,y)经等价变化后为经等价变化后为 (x)(y)P(x,y) (y)(Q(x,y)R(x,y)(2) 减少否定符号的辖域减少否定符号的辖域反复使用将每个否定符号“”移到紧靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。例如例如： (x)(y)P(x,y) (y)(Q(x,y)R(x,y)经经等价变换后等价变换后为为 (x)(y)P(x，y)(y)( Q(x，y) R(x，y)

34、子句集的化简子句集的化简(3) 对变元标准化对变元标准化在一个量词的辖域内，把谓词公式中，使不同量词约束的变元有不同的名字。 例如例如：(x)(y)P(x，y)(y)( Q(x，y) R(x，y) 经变换后为经变换后为 (x)(y)P(x，y)(z)( Q(x，z) R(x，z)(4) 化为前束范式化为前束范式不能改变其相对顺序不能改变其相对顺序 移动的可行性：由于变元已被标准化，每个量词都有自己的变元，消除了任何由变元引起冲突的可能。例如例如，(x)(y)P(x，y)(z)( Q(x，z) R(x，z)化为化为前束范式后前束范式后为为 (x)(y) (z)(P(x，y)( Q(x，z) R(

35、x，z)子句集的化简子句集的化简(5) 消去存在量词消去存在量词 存在量词存在量词不出现在全称量词的辖域内（即它的左边没有全称不出现在全称量词的辖域内（即它的左边没有全称量词量词）：）：只要用一个，就可消去该存在量词 若若存在量词位于一个或多个全称量词的辖域内存在量词位于一个或多个全称量词的辖域内，例如 (x1)(xn) (y)P(x1，x2 , xn ,y)则需要，然后再消去该存在量词例如例如， (x)(y) (z)(P(x，y)( Q(x，z) R(x，z)替换替换后的式子后的式子为为 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x)子句集的化简子句集的化简(6) 化为化为Sko

36、lem标准标准形形 Skolem标准形: (x1)(xn) M(x1,x2,xn)例如例如，为为 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x) 化为化为Skolem标准标准 形后为形后为 (x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)(7) 消去全称量词消去全称量词 由于，并且全称量词的，因此。 剩下剩下的母式，仍假设其变元是被全称量词量化的的母式，仍假设其变元是被全称量词量化的。例如，例如，(x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x) 消消去全去全称量词后称量词后为为 (P(x,f(x)Q(x,g(x) (P(x,f(x

37、)R(x,g(x)子句集的化简子句集的化简(8) 消去合取词消去合取词，把母式用子句集的形式表示出来例如，例如，(P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x)的的子句集中包含以下两个子句子句集中包含以下两个子句 P(x,f(x)Q(x,g(x) P(x,f(x)R(x,g(x)(9) 更换变量名称更换变量名称例如例如，对前面的公式，可把第二个子句集中的变元名，对前面的公式，可把第二个子句集中的变元名x更换为更换为y，得到如下子句集得到如下子句集 P(x,f(x)Q(x,g(x) P(y,f(y)R(y,g(y)子句集的化简子句集的化简练习：子句集化简练习：子句集化简1.

38、( X) (a(X)b(X) c(X, l )( Y) (Zc(Y，Z)d(X,Y) ) ) ( X) (e(X) 2.( X) ( a(X) b(X)c(X，l)( y) ( Zc(Y,Z)d(X,Y)(）(e(X)3.( X) ( a(X) b(X)c(X, l)( Y) ( Z) c(Y,Z)d(X,Y)( X)(e(X)4.( X) (a(X) b(X)c(X, l ) ( Y) ( Z) c(Y,Z)d(X,Y)( W) (e(W) 所有量词移到最左边而不改变其次序所有量词移到最左边而不改变其次序 5.( X)( Y)( Z)( W) ( a(X) b(X)c(X,l) c(Y,Z)

39、d(X,Y)e(W)前束范式前束范式Skolem标准化标准化去掉所有的存在量词去掉所有的存在量词练习：子句集化简练习：子句集化简6. ( X)( Z)( W) (a(X) b(X)c(X,l)c (f(X),Z)d(X,f(X)e(W) 5.( X)(彐彐Y)( Z)( W) ( a(X) b(X)c(X,l) c(Y,Z)d(X,Y)e(W)Skolem标准化后标准化后去掉全称量词去掉全称量词7.( a(X) b(X)c(X, l) c(f(X), Z)d(X, f(X)e(W)8.a(X) b(X)c(X,l)e(W)a(X) b(X) c(f(X), Z)d(X, f(X)e(W)转换成

40、析取式的合取转换成析取式的合取每个合取式为一个分离的子句每个合取式为一个分离的子句9a: a(X) b(X)c(X,l)e(W)9b: a(X) b(X) c(f(X), Z)d(X, f(X)e(W)把分离的变元归一化把分离的变元归一化10a: a(X) b(X)c(X,l)e(W)10b: a(U) b(U) c(f(U), Z) d(U, f(U)e(V)子句集的应用子句集的应用 注意：注意： 由于在消去存在量词时所用的Skolem函数可以不同，因此化化简简后的标准子句集是不唯一的后的标准子句集是不唯一的。 Skolem化并不影响原谓词公式的永假性化并不影响原谓词公式的永假性。 Skol

41、em化后得到的公式与原公式化后得到的公式与原公式不等价不等价，但具有，但具有相同的不可相同的不可满足性满足性定理定理 设有谓词公式设有谓词公式F F，其标准子句集为，其标准子句集为S S，则，则F F为不可为不可满足的充要条件是满足的充要条件是S S为不可满足的。为不可满足的。鲁鲁滨逊滨逊归结原理归结原理-基本基本思想思想 两两个关键个关键: 子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的；一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。 鲁鲁滨逊归结原理基本思想滨逊归结原理基本思想 首先首先把欲证明问题的结论否定，并加入子句集，得到一个扩充把欲证明问题的结论否定，并

42、加入子句集，得到一个扩充的子句集的子句集S。 然后然后设法检验子句集设法检验子句集S是否含有空子句，若含有空子句，则表是否含有空子句，若含有空子句，则表明明S是不可满足的是不可满足的； 若若不含有空子句，则继续使用归结法，在子句集中选择合适的不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止子句进行归结，直至导出空子句或不能继续归结为止。鲁鲁滨逊滨逊归结原理归结原理-命题逻辑命题逻辑的的归结归结 归结归结推理的核心是求两个子句的归结式推理的核心是求两个子句的归结式 归结归结式的式的定义定义: 若P是原子谓词公式，则称P与P为。 设C1和C2是子句

43、集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为归结归结，称C12为C1和C2的归结式归结式，称C1和C2为C12的。 例例: 设设C1=PQR，C2=PS，求，求C1和和C2的归结式的归结式C12。 解：这里L1=P，L2=P，通过归结可以得到 C12= QRS 例例: 设设C1=Q，C2=Q，求，求C1和和C2的归结式的归结式C12。 解：这里L1=Q，L2=Q，通过归结可以得到 C12= NIL例例: 设设C1 =P Q ，C2=Q，C3=P，求求C1、C2、

44、C3的归结式的归结式C123。解解：若先对：若先对C1、C2归结，可得到归结，可得到 C12=P然后再对然后再对C12和和C3归结，得到归结，得到 C123=NIL归结过程可用归结过程可用归结树归结树表示表示归结过程不唯一归结过程不唯一: 如果如果改变归结改变归结顺序，同样可以得到相同的顺序，同样可以得到相同的结果结果P QQP P NILP Q P QQ NIL鲁鲁滨逊滨逊归结原理归结原理-命题逻辑命题逻辑的的归结归结证明：设设C1=LC1 ，C2=LC2关于解释关于解释I为为真真只需证明只需证明C12= C1 C2关于解释关于解释I也为也为真真因为，对于解释I，L和L中必有一个为假若L为假

45、，则必有C1为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1为真。同理，若L为假，则必有C2为真。因此，必有C12= C1C2关于解释I也为真。即C12是C1和C2的逻辑结论。鲁鲁滨逊滨逊归结原理归结原理-命题逻辑命题逻辑的的归结归结定理：定理：归结式归结式C C1212是其亲本子句是其亲本子句C C1 1和和C C2 2的的逻辑逻辑结论结论证明证明：设S= C1，C2，C3，Cn，C12是C1和C2的归结式，则用C12代替C1和C2后可得到一个新的子句集 S1= C12，C3，, Cn。设S1是不可满足的，则对不满足S1的任一解释I，都可能有以下两种情况： 解释I使C12

46、为真，则C3，Cn中必有一个为假，即S是不可满足的。 解释I使C12为假，即C12为真，根据上述定理有 (C1C2)永真，即C1C2永真，它说明解释I使C1为假，或C2为假。即S也是不可满足的。 因此可以得出 S1的不可满足性S的不可满足性鲁鲁滨逊滨逊归结原理归结原理-命题逻辑命题逻辑的的归结归结推论推论1：设设C1和和C2是子句集是子句集S中的两个子句，中的两个子句，C12是是C1和和C2的归的归结式，若用结式，若用C12代替代替C1和和C2后得到新的子句集后得到新的子句集S1，则由，则由S1的不的不可满足性可以推出原子句集可满足性可以推出原子句集S的不可满足性。即：的不可满足性。即：先先证

47、明证明 设S= C1，C2，C3，Cn是不可满足的，则C1，C2，C3，Cn中必有一子句为假，因而S2= C12，C1，C2，C3，Cn必为不可满足。再再证明证明 设S2是不可满足的,则对不满足S2的任一解释I,都可能有以下两种情况： 解释I使C12为真，则C1，C2，C3，Cn中必有一个为假，即S是不可满足的。 解释I使C12为假，即C12为真，根据定理3.2有 (C1C2)永真，即C1C2永真，它说明解释I使C1为假，或C2为假。即S也是不可满足的。由此可见S与S2的不可满足性是等价的。即 S的不可满足性 S2的不可满足性鲁鲁滨逊滨逊归结原理归结原理-命题逻辑命题逻辑的的归结归结推论推论2

48、：设设C1和和C2是子句集是子句集S中的两个子句，中的两个子句，C12是是C1和和C2的归的归结式，若把结式，若把C12加入加入S中得到新的子句集中得到新的子句集S2，则，则S与与S2的不可满的不可满足性是等价的。即：足性是等价的。即：S2的不可满足性的不可满足性S的不可满足性的不可满足性 为为证明子句集证明子句集S S的不可满足性，只要对其中可进行归结的子的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入到子句集句进行归结，并把归结式加入到子句集S S中，或者用归结式中，或者用归结式代替他的亲本子句，然后对新的子句集证明其不代替他的亲本子句，然后对新的子句集证明其不可满足性可满

49、足性即即可可。 如果如果经归结能得到空子句，根据空子句的不可满足性，即可经归结能得到空子句，根据空子句的不可满足性，即可得到原子句集得到原子句集S S是不可满足的结论。是不可满足的结论。 在在命题逻辑中，对不可满足的子句集命题逻辑中，对不可满足的子句集S S，归结原理，归结原理是是的的。鲁鲁滨逊滨逊归结原理归结原理-命题逻辑命题逻辑的的归结归结定理定理 子句集子句集S S是不可满足的，当且仅当存在一个从是不可满足的，当且仅当存在一个从S S到空到空子句的归结过程。子句的归结过程。例例 设已知的公式集为设已知的公式集为P, (PQ)R, (ST)Q, T，求证结论，求证结论R。解：假设结论R为假

50、, 将R加入公式集，并化为子句集 S=P,PQR, SQ, TQ, T, R其归结过程如右图的归结演绎树所示。该树根为空子句。其含义为：先假设子句集S中的所有子句均为真，即原公式集为真,R也为真；然后利用归结原理，对子句集进行归结，并把所得的归结式并入子句集中；重复这一过程，最后归结出了空子句。P QR RP QPQT QTTNIL鲁滨逊归结原理鲁滨逊归结原理-命题逻辑的归结命题逻辑的归结 在在谓词逻辑中，由于子句集中的谓词一般都含有谓词逻辑中，由于子句集中的谓词一般都含有变元变元，因此，因此不能不能象命题逻辑那样象命题逻辑那样直接消去互补文字直接消去互补文字。而需要先用一个。而需要先用一个对

51、变元进行代换，然后才能进行归结。对变元进行代换，然后才能进行归结。 谓词逻辑谓词逻辑中的归结中的归结式：式：鲁滨逊归结原理鲁滨逊归结原理谓词谓词逻辑的归结逻辑的归结设设C1和和C2是两个是两个没有公共变元没有公共变元的子句，的子句，L1和和L2分别是分别是C1和和C2中中的文字。如果的文字。如果L1和和L2存在最一般合一存在最一般合一，则称，则称 C12=(C1- L1)( C2- L2)为为C1和和C2的的二元归结式二元归结式，而，而L1和和L2为归结式上的文字为归结式上的文字。例例 设设C1=P(a)R(x)，C2=P(y)Q(b)，求，求 C12解：取L1= P(a), L2=P(y)，

52、则L1和L2的最一般合一是=a/y。 C12=( C1-L1) (C2-L2) =(P(a), R(x)-P(a)(P(a), Q(b)-P(a) =(R(x)(Q(b) = R(x), Q(b) =R(x)Q(b)鲁滨逊归结原理鲁滨逊归结原理-谓词逻辑谓词逻辑的归结的归结例例 设设C1=P(x)Q(a)，C2=P(b)R(x) ，求，求 C12解：由于C1和C2有相同的变元x，不符合定义3.20的要求。为了进行归结，需要修改C2中变元的名字，令C2=P(b)R(y)。此时L1= P(x), L2 =P(b)，L1和L2的最一般合一是=b/x。则有 C12=( C1-L1) (C2-L2) =

53、(P(b), Q(a)-P(b) (P(b), R(y)-P(b) =(Q(a) (R(y) = Q(a), R(y) =Q(a)R(y)鲁滨逊归结原理鲁滨逊归结原理-谓词逻辑谓词逻辑的归结的归结例例 设设C1=P(x)Q(b)，C2=P(a)Q(y)R(z) 解：对C1和C2通过最一般合一（=a/x, b/y）的作用，可以得到两个互补对。 注意：求归结式不能同时消去两个互补对，这样的结果不是二注意：求归结式不能同时消去两个互补对，这样的结果不是二元归结式。如在元归结式。如在=a/x, b/y下，若同时消去两个互补对，所得的下，若同时消去两个互补对，所得的R(z)不是不是C1和和C2的二元归结

54、式的二元归结式。鲁滨逊归结原理鲁滨逊归结原理-谓词逻辑谓词逻辑的归结的归结例例: 设设C1=P(x)P(f(a)Q(x) ，C2=P(y)R(b)，求，求C12 解：对参加归结的某个子句，若其内部有可合一的文字，则在若其内部有可合一的文字，则在进行归结之前应先对这些文字进行合一进行归结之前应先对这些文字进行合一。 C1中有可合一的文字P(x)与P(f(a)，用它们的最一般合一=f(a)/x进行代换，可得到 C1=P(f(a)Q(f(a) 对C1与C2进行归结。选L1= P(f(a), L2 =P(y)，L1和L2的最一般合一是=f(a)/y，则可得到C1和C2的二元归结 C12=R(b)Q(f

55、(a)若若子句子句C中有两个或两个以上的文字具有最一般合一中有两个或两个以上的文字具有最一般合一，则称，则称C为为子句子句C的的因子因子。如果。如果C是一个单文字，则称它为是一个单文字，则称它为C的的单元因子单元因子。鲁滨逊归结原理鲁滨逊归结原理-谓词逻辑谓词逻辑的归结的归结定义定义 若若C1和和C2是无公共变元的子句，则是无公共变元的子句，则 C1和和C2的二元归结式的二元归结式; C1和和C2的因子的因子C22的二元归结式；的二元归结式； C1的因子的因子C11和和C2的二元归结式；的二元归结式； C1的因子的因子C11和和C2的因子的因子C22的二元归结式。的二元归结式。 这这四种二元归

56、结式都是子句四种二元归结式都是子句C1和和C2的二元归结式，记为的二元归结式，记为C12。鲁滨逊归结原理鲁滨逊归结原理-谓词逻辑谓词逻辑的归结的归结例例3.15 设设C1=P(y)P(f(x)Q(g(x) ，C2=P(f(g(a)Q(b)，求，求C12。 解：对C1 ，取最一般合一=f(x)/y，得C1的因子 C1=P(f(x)Q(g(x)对C1的因子和C2归结（=g(a)/x ），可得到C1和C2的二元归结式 C12=Q(g(g(a)Q(b)说明说明： 对对谓词逻辑谓词逻辑，归结归结式式C12是其亲本子句是其亲本子句C1和和C2的逻辑结论。用归结式的逻辑结论。用归结式取代取代它在子句它在子句

57、集集S中的亲本子句，所得到的子句集仍然保持着原子句集中的亲本子句，所得到的子句集仍然保持着原子句集S的不可满足性。的不可满足性。 对谓词逻辑，从对谓词逻辑，从不可满足的意义上说，一阶谓词逻辑的归结原理也是完备的不可满足的意义上说，一阶谓词逻辑的归结原理也是完备的 鲁滨逊归结原理鲁滨逊归结原理-谓词逻辑谓词逻辑的归结的归结归结归结演绎推理的归结策略演绎推理的归结策略归结演绎推理实际上就是从子句集中不断寻找可进行归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对，并通过对这些子句对的归结，最终得归结的子句对，并通过对这些子句对的归结，最终得出一个空子句的过程。出一个空子句的过程。由于事先并

58、不知道哪些子句对可进行归结，更不知道由于事先并不知道哪些子句对可进行归结，更不知道通过对哪些子句对的归结能尽快得到空子句，因此就通过对哪些子句对的归结能尽快得到空子句，因此就需要对子句集中的需要对子句集中的所有子句逐对进行比较所有子句逐对进行比较，直到得出，直到得出空子句为止空子句为止。盲目盲目的全面进行归结的全面进行归结的方法，不仅会产生许多无用的的方法，不仅会产生许多无用的归结式，更严重的是会产生组合爆炸问题归结式，更严重的是会产生组合爆炸问题。广度广度优先是一种优先是一种穷尽子句比较穷尽子句比较的复杂搜索的复杂搜索方法方法设设初始子句集为初始子句集为S0，广度优先策略的归结，广度优先策略

59、的归结过程：过程：1.从S0出发，对S0中的全部子句作所有可能的归结，得到第一层归结式，把这些归结式的集合记为S1;2.用S0中的子句与S1中的子句进行所有可能的归结，得到第二层归结式，把这些归结式的集合记为S2;3.用S0和S1中的子句与S2中的子句进行所有可能的归结，得到第三层归结式，把这些归结式的集合记为S3;4.如此继续，直到得出空子句或不能再继续归结为止。归结归结演绎推理的归结策略演绎推理的归结策略例设有例设有如下子句集如下子句集：S=I(x)R(x), I(a), R(y)L(y), L(a) 用广度优先策略证明用广度优先策略证明S为不可满足为不可满足。广度优先策略的归结树如下：广

60、度优先策略的归结树如下：I(x)R(x)I(a)R(y)L(y)L(a)R(a)I(x) L(x)R(a)L(a)L(a)I(a)I(a)NILS0S1S2归结归结演绎推理的归结策略演绎推理的归结策略 广度优先广度优先策略的优点：策略的优点： 当问题有解时保证能找到最短归结路径。 是一种完备的归结策略。 广度优先策略的广度优先策略的缺点：缺点： 归结出了许多无用的子句 既浪费时间，又浪费空间 广度广度优先对大问题的归结容易产生组合爆炸，但对优先对大问题的归结容易产生组合爆炸，但对小小问题问题却仍是一种比较好的归结策略。却仍是一种比较好的归结策略。归结归结演绎推理的归结策略演绎推理的归结策略 常