第3章(搜索推理技术5-消解原理).pptx

1、人 工 智 能 Artificial Intelligence (AI),刘 静 理工学院 2009年春季,第3章 搜索推理技术,3.1 图的搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 与或树搜索（补充） 3.5 博弈树搜索（补充） 3.6 消解原理,3.6 消解原理 3.6.1 子句集的求取 3.6.2 消解原理（补充） 3.6.3 消解推理规则 3.6.4 含有变量的消解式 3.6.5 消解反演求解过程 3.6.6 Horn子句集消解（补充） 3.6.7 Prolog 语言简介 （补充）,3.6 消解原理,第2章中介绍： 谓词逻辑的基本知识 合一算法（求最一般的一致置换或合一者

2、mgu） 本节： 消解原理（或者归结原理）,3.6.1 子句集的求取 如何将谓词公式转化为子句集，作为合一算法的输入（公式集） 3.6.1.1 若干基本概念 3.6.1.2 子句集的求取,3.6.1.1 若干基本概念 1 自由变元与约束变元 2 前束范式与前束合取范式 3 斯科伦（Skolem）范式 4 子句集,设，是一个谓词公式，将量词记作（即 或 ）,1 自由变元与约束变元,如果中包含部分公式 (x)，则中变元 x 的一切出现都称为 x 在 中的约束出现，相应地称 x 为约束变元（哑元、虚构变量、约束变量）,约束变元,中不在任何量词作用域内的变元 x ，称为变元 x 在 中的自由出现，相应

3、地称 x 为自由变元（自由变量）,自由变元：,量词的作用域（辖域）是直接跟在它后面的公式 如果有括号，则是括号里的公式 如果没有括号，则是最短的完整公式,说明：,例1： x ( P(x) y (R(x, y) ) x , y 都是约束变元 例2： x ( P(x) (R(x, y) ) x 是约束变量，y 是自由变元,改名：将谓词公式中一个变元名改成另一个变元名，但是要求改名后的公式与原公式意义相同（真假值相同） 原则：改成的新的变元名一定是量词作用域中没有出现过的变元名（包括约束变元和自由变元）,约束变元的改名或变量的标准化,例3： x ( P(x) (R(x, y) 除了 y 外，可以将

4、x 改成任何变元名 例4： x P(x) Q(y) 可以改成任何变元名，包括 y（建议不要用）,2 前束范式与前束合取范式,定义：设谓词公式具有形式： (1x1)(nxn) M 其中：i ( i = 1 , , n ) 是 或 M 是不包含量词的谓词公式 则，称是前束范式 称 (1x1)(nxn ) 为前束 称 M 为母式,定义：设谓词公式是一个前束范式，如果的母式具有形式： （M11M12M1 n1） （M21M22M2 n2） (Mm1Mm2Mm nm） 其中，M i j 是原子公式或其非，则称是前束合取范式。相应地有前束析取范式,前束范式： (x) (y) (z)(P(x)Q(y)R(z

5、) 前束合取范式（交换律、分配律，p.33） (x) (y) (z)(R(z)P(x)(R(z)Q(y),例：,3 斯柯伦范式,定义：前束中不含存在量词的前束范式称为斯柯伦范式,若xk (1kn )左边没有全称量词，则取不在母式中出现的常量替代母式中的所有 xk ，并删除前束中的 xk,消去存在量词的规则 或 前束范式化成斯柯伦的步骤是：,若 xk (1 kn )左边有全称量词 (xs1) (xs2)(xsr) ( 1r，1s1s2srk) 则，取不在母式中出现的 r 阶函数 fr (xs1, xs2,xsr)替代母式中的所有xk ，并删除前束中的 xk,反复使用上述两条规则，消除前束中的所有

6、存在量词，即得到斯柯伦范式 其中，引入的函数称为斯柯伦函数,x y z u v w A(x,y,z,u,v,w) (用a替代x，删除x) = y z u v w A(a,y,z,u,v,w) （用f(y,z)代替u，删除u） = y z v w A(a,y,z, f(y,z),v,w) （用h(y,z,v)代替w，删除w） = y z v A(a,y,z, f(y,z),v,h(y,z,v),例：求斯柯伦范式,说明： 一个谓词公式的斯科伦范式不是唯一的，尽可能将斯科伦函数取得简单一点,化成前束范式 化成前束合取范式 化成斯科伦范式（斯科伦函数的变元较多）,对于谓词公式：=12,正常的做法：,将

7、1、2 分别化成前束范式 对1、2 分别求出斯柯伦范式1、2 将12 的量词左移得到的斯柯伦范式（即前束范式）,简化的做法：,好处：简化斯科伦函数,=12, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = y1 x1 x2 y2 (P( x1 , y1 ) Q( x2 , y2 ) （前束合取范式） = x1 x2 (P( x1 , a1 ) Q( x2 , f(x1,x2) ),例：正常化法, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = x1 P( x1 , a1 ) x2 Q( x2 , f(x2) ) （先分别化

8、成斯科伦范式） = x1 x2 (P( x1 , a1 ) Q( x2 , f(x2) ) (前束合取范式）,简化化法,4 子句集,原子命题是原子公式 如果t1,tn(n1)是项，P是谓词，则P(t1,tn)是原子公式 其它表达式都不是原子公式,原子公式的定义：, 文字（或基本式）：“原子公式”或者“原子公式的非” 子句：一个或多个基本式的 析取,子句的定义：,一个谓词公式具有形式： ( x1 )( xn )( c1c2cm ) 其中，ci ( i = 1, , m )为子句 x1, , xn 是子句中出现的约束变元 则，称谓词公式具有子句形式,子句形式的定义：,闭公式：不含自由变量的谓词公式

9、 谓词公式的子句形式是闭公式 母式为子句的合取范式 前束中只有全称量词，无存在量词,说明：,若谓词公式 具有子句形式，记 S = ( c1 , c2 , , cm ) 则，称 S 为谓词公式的子句集,( x1 )( xn )( c1c2cm ),子句集的定义：,为了便于消解推理，要通过改名使得一个变量符号不出现在一个以上的子句中，即每一个子句具有不同的变量,说明：,子句形式： (x) (y) (z)(R(z)P(x)(R(z)Q(y) 子句集： R(z)P(x) , R(z)Q(y) R(z1)P(x1) , R(z2)Q(y1) （改名）,例：,3.6.1.2 子句集的求取,子句集的求取（将

10、谓词公式化成子句集）有两种方法，其形式上会有差别，但是其逻辑意义是相同,1、将谓词合适公式转化为前束合取范式 消去“蕴含”和“等价”连结词 将“”连结词直接作用到原子公式前 约束变元改名，使所有的约束变元名都不相同 将量词移到谓词公式的左边，得到前束范式 将前束范式化成前束合取范式,方法1（离散数学、数理逻辑采用的方法）：,2、将前束范式转化为斯柯伦（Skolem）范式 得到斯科伦范式 3、将斯柯伦范式转化为子句集 消去前束（全称量词） 消去合取连词 变量改名，得到子句集,为了使斯科伦函数更简单一些，可以将合取关系的各个谓词公式分别先分成前束范式、斯科伦范式，再综合起来化成前束范式、前束合取范

11、式（后面的定理证明部分就采用了这一种化法）,说明：, 消去“蕴含”和“等价”连结词 减少“非”连结词的辖域（将“”连结词直接作用到原子公式前） 对变量标准化（约束变元改名）,方法2 （教材采用的方法）：,消去存在量词（引入斯科伦函数） 化成前束范式 将母式化成合取范式 消去全称量词 消去合取连结词 更改变量名，得到子句集,两者的差别：在于三步 方法 1 是先得到前束合取范式，再化成斯科伦范式 方法 2 是先引入斯科伦函数消去存在量词，再化成前束合取范式,三步的结果： 得到不含存在量词的前束合取范式,谓词公式 = 全称量词串 + 合取范式的母式,注：母式中的斯科伦函数变元个数可能不相同,求取子句

12、集的步骤(教材)：,使用的公式： AB = AB AB = (AB)(B A), 消去“蕴含”和“等价”连结词,将“”连结词直接作用到原子公式前，使得每一个“非”联结词最多只能作用于一个原子公式（谓词符号）, 减少“非”连结词的辖域,(A) A (AB) = AB (AB) = AB (x)A(x) = (x)(A(x) (x)A(x) = (x)(A(x),使用的公式是：,说明： 到现在为止，谓词公式只包含三种连结词 “合取”： “析取” “非” ,对约束变元改名，使得所有的约束变元名都不相同，保证每一个量词都有自己唯一的约束变元, 对变量标准化,以一个斯科伦函数代替每一个带存在量词的约束变

13、元，斯科伦函数的变元是（左边）带全称量词的约束变元，而且这些全称量词的辖域必须包括被消去的存在量词的辖域, 消去存在量词,消去存在量词的规则：,如果要消去的存在量词不在任何一个全称量词的辖域内，则用常量来代替 斯科伦函数和常量的符号必须是未在谓词公式出现过的符号, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = x1 P( x1 , a1 ) x2 Q( x2 , f(x2) ) （引入斯科伦函数，消去存在量词， x1 的辖域不包含y2 的辖域）,例：,将全称量词移到谓词公式的左边，使得每一个量词的辖域包括该量词后面的整个谓词公式, 化成前束范式,(x)A(

14、x)R = (x) (A(x)R) (x)A(x)R = (x) (A(x)R) (1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z) (1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z) 说明：A(x), B(z), R中允许含有与x，z不同的自由变量,使用的规则：,前束范式 （前束） （母式）,全称量词串,无量词公式, 将母式化成合取范式,利用分配律将前束范式化成前束合取范式： P(QR) = (PQ)(PR) （析取 合取）,谓词公式已经化成了前束合取范式，且只包含全称量词，此时全称量词的次序也不重要了，所以可以消去全部量词（即前束、前缀）,

15、消去全称量词, 消去合取连结词 ,母式为合取范式： A1 A2 An 消去合取连结词，得到子句集： A1 , A2, , An 子句：基本式（文字）的析取（只含）,更改变元名，使得一个变量符号不出现在一个以上的子句中，即不同的子句包含不同的约束变元名, 更换变元名,(x)A(x) (x)B(x) = (x)A(x)(x)B(x) （消去“蕴含”） = (x) (A(x)(x)B(x) （“非”直接作用谓词符号） = ( x) (A(x) ) (z) B(z) (改名) = A(a)B(b) （消去存在量词） 子句集= A(a)B(b) 注：两种方法的结果相同,例1：,仔细分析量词的辖域,(x)

16、 (y)( (z)(A(x,z)A(y,z) (u)B(x,y,u) =(x) (y)( (z)(A(x,z)A(y,z)(u)B(x,y,u) =(x) (y)( (z)(A(x,z)A(y,z) )(u)B(x,y,u) =(x) (y)( (z)(A(x,z)A(y,z) )B(x,y,f(x,y) = (x) (y) (z)(A(x,z)A(y,z) B(x,y,f(x,y),使用方法1，函数将为f(x,y,z),子句,例2：,(x)P(x)(y)Q(y) (x)R(x) =(x)P(x)(y)Q(y) (x)R(x) =(x)P(x)(y)Q(y) (x)R(x) =( (x)(P(

17、x)(y)(Q(y) (x)R(x) =( (x)(P(x)(y)(Q(y) (z)R(z) (改名),例3：, ( (P(a)(y)(Q(y) (z)R(z) （消去存在量词） (y) (z)( P(a) Q(y) R(z) ) （化成前束范式） (y) (z)( (P(a) R(z)(Q(y) R(z) ) (化成前束合取范式) 子句集= P(a) R(z) , Q(y) R(x) ,两者化法结果相同,=( (x)(P(x)(y)(Q(y) (z)R(z),例4：将谓词公式化成子句集, 消去“蕴含”符号, “非”直接作用到谓词符号, 约束变量改名,后面的 y 改成 w, 引入斯科伦函数消去

18、存在量词,斯科伦函数 w = g ( x ), 化成前束范式, 化成前束合取范式,分配律： P(QR) = (PQ)(PR),注：使用分配律两次, 消去全称量词或者前束, 消去合取符号，得到子句, 变量改名，使得变量不相同，得到子句集,如果使用方法1，函数g将会有两个变量g(x,y),设c1 , c2是两个无公共变元的子句，令 c1= P(t11,t1n)P(tk1,tkn)c1 c2= P(t11,t1n)P(tm1,tmn)c2,3.6.2 消解原理,说明：谓词符号相同，变元不同,消解式定义：,若 P(t11,t1n), , P(tk1,tkn), P(t11,t1n), , P(tm1,

19、tmn) 有最一般的合一者（或一致置换）（mgu）,说明：用合一算法求取mgu,则称 c = ( c1 c2) 为c1 , c2的消解式 称 P(t11,t1n), ., P(tk1,tkn), P(t11,t1n), , P(tm1,tmn) 为被消解式,设c1 , c2为无变量子句，c1=Lc1，c2=Lc2 其中 L 是基本式 则c = c1 c2 为c1 , c2 的消解式 当c1c2时，c= (空句子),对于子句中无变量的特殊情况（即命题情况）：,例1：c1=PQ，c2=PQ c1=P c2=P c = c 1 c 2= P （消解式）,L= Q,设c1 = P(x) Q(x), c

20、2 = P(a) R(y) P(x), P(a)的最一般的合一者为 a/x c1= Q(x) c2= R(y) 则c1, c2的消解式为 c=Q(a)R(y),例2：,设S是子句集，c是子句。若存在一个子句序列c1,cn满足 cn = c 任意一个 ci 或者属于 S 或者它前面的子句 ck, cl ( ik , il )的消解式,消解演绎和反演的定义：,则称 c1, , cn 是从子句集 S 到子句 c 的一个消解演绎 当 c= 时的消解演绎称为（消解）反演,把谓词公式转化为子句集S（所有子句的变量名不同） 如空子句成为子句集的子句，则算法结束 在子句集中选取两个不同的可以消解的子句ci ,

21、 cj,注：子句的个数限制,反演的基本算法：,计算 ci , cj 的消解式 rij 把 rij 加到子句集中，形成新的子句集S 转到,反演的流程图,将谓词公式化成子句集,有空子句？,成功结束,取两个子句,有消解式？,无解结束,将消解式送到子句集,有,无,例1：设子句集为S= PQ, PQ, PQ, PQ 求S的一个反演,S的一个反演为：,PQ (S) PQ (S) PQ (S) PQ (S) Q Q ,P P ,S的另一个反演为：,例2：设S= P(z1,a)P(z1,x1)P(x1,z1), P(z2,f(z2)P(a, z2), P(f(z3),z3)P(a, z3) 求S的一个反演,

22、P(z1,a)P(z1,x1)P(x1,z1) （S） P(z2,f(z2)P(a ,z2) （S） P(f(z3),z3)P(a ,z3) （S）,S的一个反演为：, 取c1=，c1= P(z2,f(z2) 取c2=，c2= 公式集为： P(z1,a), P(z1,x1), P(x1,z1), P(a,z2) 最一般的合一者为=a/x1, a/z1, a/z2 对应的消解式：P(a, f(a), P(z1,a)P(z1,x1)P(x1,z1) P(z2,f(z2)P(a ,z2), 取c1=，c1= P(f(z3),z3) 取c2=，c2= 公式集为 P(z1,a), P(z1,x1), P

23、(x1,z1), P(a, z3) 最一般的合一者为=a/x1,a/z1,a/z3 对应的消解式为：P(f(a), a), P(z1,a)P(z1,x1)P(x1,z1) P(f(z3),z3)P(a ,z3),取c1=，c1= 取c2=，c2=P(z1,a)P(z1,x1) 公式集 P(x1,z1), P(a, f(a) 最一般的合一者为=a/x1,f(a)/z1 对应的消解式为：P(f(a),a), P(z1,a)P(z1,x1)P(x1,z1) P(a, f(a),取c1= ，c1= 取c2= ，c2= 公式集: P(f(a) , a) 最一般的合一者为= 对应的消解式为： , P(f(

24、a), a) P(f(a),a), P(z1,a)P(z1,x1)P(x1,z1) （S） P(z2,f(z2)P(a ,z2) （S） P(f(z3),z3)P(a ,z3) （S） P(a, f(a) ( ) P(f(a), a) ( ) P(f(a),a) ( ) ( ),反演过程：,3.6.3 消解推理规则 （命题的特殊情况）,从父子句求消解式的若干例子,1、假言推理,2、合并,3、重言式,4、空子句（矛盾）,5、链式（三段论）,3.6.4 含有变量的消解式（谓词情况）,先求最一般的合一者mgu，再求消解式,例1,置换,例2,例3,1 消解反演（数学定理的证明，论断是否成立，即反演）

25、2 反演求解过程（回答问题，即消解演绎）,3.6.5 消解反演求解过程,1 消解反演 消解反演证明定理的思路非常类似于数学中的反证法,给定一个公式集 S（前提条件）和目标公式 L（结论），通过反演来求证目标公式 L，其证明过程为： 否定 L ，得到 L 把 L 加到 S 中 把新形成的集合 S ， L 化为子句集（简化化法） 应用消解原理，试图导出一个表示矛盾的空子句,设SF1,Fn 是前提条件，L是欲求证的结论 则，从前提条件推出结论的问题，可以表示成： F1Fn L （F1Fn ）L 并证明其永真（永远成立）,反演证明过程的正确性：,先将公式取“非” ： （F1Fn ）L） （F1Fn ）

26、 L F1Fn L 利用消解原理来证明它是永假的（即，构造一个反演）,实际中，我们可以将 F1Fn L 中的每一个部分化成子句集（化法任选），合并后得到完整的子句集，然后利用消解原理导出空子句（反演）,设有公式集： F1: (x)(C(x)(W(x)R(x) F2: (x)(C(x)O(x) L: (x)(O(x)R(x) 试证：L是F1，F2的逻辑结果，即F1F2L,例1：,利用消解原理来构造F1F2L的一个反演 首先分别求出F1，F2和 L 的子句集,证明：,(x)(C(x)(W(x)R(x) = (x)(C(x)(W(x)R(x) = (x)(C(x)W(x) )(C(x)R(x) 子句

27、集= C(x)W(x) , C(x)R(x) (未改名),F1的前束合取范式与子句集：,(x)(C(x)O(x) = (C(a)O(a) 子句集= C(a), O(a) ,F2的前束合取范式和子句集：,(x)(O(x)R(x) = (x)(O(x)R(x) 子句集=O(x)R(x),L 的前束范式和子句集：,构成子句集（注意改名） C(x)W(x), C(y)R(y), C(a)， O(a), O(z)R(z) , C(x)W(x) C(y)R(y) C(a) O(a) O(z)R(z),证明过程：, R(a) ，mgu=a/y R(a) mgu=a/z , C(y)R(y) C(a), O(

28、a) O(z)R(z),前提：每一个储蓄钱的人都获得利息 结论：如果没有利息，那么就没有人去储蓄钱,例2：用消解反演证明,S ( x , y )：某人 x 储蓄 y（数量） M ( x )：x（数量） 是钱 I( x )：x （数量）是利息 E( x , y )：某人 x 获得 y （数量）,证明： 设,前提：每一个储蓄钱的人都获得利息,结论：如果没有利息，那么就没有人去储蓄钱,任何人 x 将 y 数量的钱存入银行,任何人 x 得到 y 数量的利息,没有 x 数量的利息,任何人 x 就不会将任何数量 y 的钱存入银行,将前提条件化成子句集,前束范式,前束合取范式,前提条件的子句集,结论取非：,

29、化成子句集,改名、消除,“结论非”的子句集,完整的子句集,反演过程,储蓄问题的反演树（简单情况下使用）,2 反演求解过程,从反演树求取某一个问题的答案，其过程为： 将前提条件用谓词表示出来，并化成子句集 S,将目标公式（问题）用谓词表示出来，把由目标公式的否定所产生的子句及其非（目标公式否定之否定）用析取连接词相连组成一个新子句（重言式），加到 S 构成新的子句集 S,对子句集 S ，进行消解演绎，直到得到某一个子句为止 将此子句作为问题的答案,例： 已知三个前提条件 F1:：王(Wang)先生是小李(Li)的老师 F2：小李与小张(Zhang)是同班同学 F3：如果x与y是同班同学，则x的老

30、师就是y的老师 问题：小张的老师是谁？,解： 定义谓词 T(x , y) : x 是 y 的老师 C(x , y) : x 与 y 是同班同学,前提： F1：T(Wang , Li) F2：C(Li , Zhang) F3： (x) (y) (z) (C(x,y)T(z,x) T(z,y) 目标： G： (x)T(x,Zhang) G： (x)T(x,Zhang)=(x) ( T(x,Zhang),用谓词表示前提条件与目标（问题）：,前提的子句集： (1) T(Wang, Li) (2) C(Li, Zhang) (3) C(x,y) T(z,x) T(z,y) 目标的否定的子句及其非组成重言

31、式： (4) T(x,Zhang) T(x,Zhang),完整的子句集： (1) T(Wang, Li) (2) C(Li, Zhang) (3) C(x,y) T(z,x) T(z,y) (4) T(u,Zhang) T(u,Zhang),(1) T(Wang, Li) (2) C(Li, Zhang) (3) C(x,y) T(z,x) T(z,y) (4) T(u,Zhang) T(u,Zhang) (5) C(Li ,y) T(Wang,y) (1)(3) mgu=Wang/z, Li/x),消解演绎过程,(6) C(Li ,Zhang) T(Wang, Zhang) (4)(5) mgu=Wang/u, Zhang/y (7) T(Wang, Zhang) (6)(2),问题的答案,(4) T(u,Zhang) T(u,Zhang) (5) C(Li ,y) T(Wang,y),(2) C(Li, Zhang),mgu= ,例：如果无论约