人工智能搜索推理技术消解原理.ppt

《人工智能搜索推理技术消解原理.ppt》由会员分享，可在线阅读，更多相关《人工智能搜索推理技术消解原理.ppt（147页珍藏版）》请在三一办公上搜索。

1、人 工 智 能Artificial Intelligence(AI),第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章中介绍：谓词逻辑的基本知识合一算法（求最一般的一致置换或合一者mgu）本节：消解原理（或者归结原理）,3.6.1 子句集的求取如何

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

3、果有括号，则是括号里的公式如果没有括号，则是最短的完整公式,说明：,例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 外，可以将 x 改成任何变元名例4：x P(x)Q(y)可以改成任何变元名，包括 y（建议不要用）,2 前束范式与前束合取范式,定义：设谓词公式具有形式：(1x

4、1)(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)前束合取范式（交换律、分配律）(x)(y)(z)(R(z)P(x)(R(z)Q(y),例：,3 斯柯伦范式,定义：前束中不含存在量词的前束范式称为斯柯伦范式,若xk(1kn)左边没有全称量词，则取不在母

5、式中出现的常量替代母式中的所有 xk，并删除前束中的 xk,消去存在量词的规则 或 前束范式化成斯柯伦的步骤是：,若 xk(1 kn)左边有全称量词(xs1)(xs2)(xsr)(1r，1s1s2srk)则，取不在母式中出现的 r 阶函数 fr(xs1,xs2,xsr)替代母式中的所有xk，并删除前束中的 xk,反复使用上述两条规则，消除前束中的所有存在量词，即得到斯柯伦范式其中，引入的函数称为斯柯伦函数,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,

6、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,正常的做法：,将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)（前束合

7、取范式）=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)（先分别化成斯科伦范式）=x1 x2(P(x1,a1)Q(x2,f(x2)(前束合取范式）,简化化法,4 子句集,原子命题是原子公式如果t1,tn(n1)是项，P是谓词，则P(t1,tn)是原子公式其它表达式都不是原子公式,原子公式的定义：,文字（或基本式）：“原子公式”或者“原子公式的非”子句：一个或多个基本式的 析取,子句的定义：,一个谓词公式具有形式：(x1)(xn)(c1c2cm)其中，ci(i=1,

8、m)为子句 x1,xn 是子句中出现的约束变元则，称谓词公式具有子句形式,子句形式的定义：,闭公式：不含自由变量的谓词公式谓词公式的子句形式是闭公式母式为子句的合取范式前束中只有全称量词，无存在量词,说明：,若谓词公式 具有子句形式，记 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)（

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

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

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

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

13、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)（析取 合取）,谓词公式已经化成了前束合取范式，且只包含全称量词，此时全称量词的次序也不重要了，所以可以消去全部量词（即前束、前缀）,消去全称量词,消去合取连结词,母式为合取范式：A1 A2 An消去合取连结词，得到子句集：A1,A2,An子句：基本式（文字）的析取（只含）,

14、更改变元名，使得一个变量符号不出现在一个以上的子句中，即不同的子句包含不同的约束变元名,更换变元名,(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)(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)(

15、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(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)(化成前束合取范式)

16、子句集=P(a)R(z),Q(y)R(x),两者化法结果相同,=(x)(P(x)(y)(Q(y)(z)R(z),例4：将谓词公式化成子句集,消去“蕴含”符号,“非”直接作用到谓词符号,约束变量改名,后面的 y 改成 w,引入斯科伦函数消去存在量词,斯科伦函数 w=g(x),化成前束范式,化成前束合取范式,分配律：P(QR)=(PQ)(PR),注：使用分配律两次,消去全称量词或者前束,消去合取符号，得到子句,变量改名，使得变量不相同，得到子句集,如果使用方法1，函数g将会有两个变量g(x,y),设c1,c2是两个无公共变元的子句，令 c1=P(t11,t1n)P(tk1,tkn)c1 c2=P(

17、t11,t1n)P(tm1,tmn)c2,3.6.2 消解原理,说明：谓词符号相同，变元不同,消解式定义：,若 P(t11,t1n),P(tk1,tkn),P(t11,t1n),P(tm1,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=(空句子),对于子句中无变量的特殊情况（即命题情况）：

18、,例1：c1=PQ，c2=PQ c1=P c2=P c=c 1 c 2=P（消解式）,L=Q,设c1=P(x)Q(x),c2=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（所有子句的变量名不同）如空子句成

19、为子句集的子句，则算法结束在子句集中选取两个不同的可以消解的子句ci,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)

20、求S的一个反演,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(x1,z1),P(a,z3)最一般的合

21、一者为=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(a),a)P(f(a),a),P(z1,a)P(z1,x1)P(x1,z1)（S）P(z2,

22、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 消解反演（数学定理的证明，论断是否成立，即反演）2 反演求解过程（回答问题，即消解演绎）,3.6.5 消解反演求解过程,1 消解反演消解反演证明定理的思路非常类似于数学中的反证法,给定一个公

23、式集 S（前提条件）和目标公式 L（结论），通过反演来求证目标公式 L，其证明过程为：否定 L，得到 L把 L 加到 S 中把新形成的集合 S，L 化为子句集（简化化法）应用消解原理，试图导出一个表示矛盾的空子句,设SF1,Fn 是前提条件，L是欲求证的结论则，从前提条件推出结论的问题，可以表示成：F1Fn L（F1Fn）L 并证明其永真（永远成立）,反演证明过程的正确性：,先将公式取“非”：（F1Fn）L）（F1Fn）L F1Fn L利用消解原理来证明它是永假的（即，构造一个反演）,实际中，我们可以将 F1Fn L中的每一个部分化成子句集（化法任选），合并后得到完整的子句集，然后利用消解原理

24、导出空子句（反演）,设有公式集：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)子句集=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)=(

25、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(a)O(z)R(z),前提：每一个储蓄钱的人都获得利息结论：如果没有利息，那么就没有人去储蓄钱,例2：用消解反演证明,S(x,y)：某人 x 储蓄 y（数量）M(x)：x（数量）是钱I(x)：x（数量）是利息E(x,y)：某人 x 获得 y（数量）,证明：设,前提：每一个

26、储蓄钱的人都获得利息,结论：如果没有利息，那么就没有人去储蓄钱,任何人 x 将 y 数量的钱存入银行,任何人 x 得到 y 数量的利息,没有 x 数量的利息,任何人 x 就不会将任何数量 y 的钱存入银行,将前提条件化成子句集,前束范式,前束合取范式,前提条件的子句集,结论取非：,化成子句集,改名、消除,“结论非”的子句集,完整的子句集,反演过程,储蓄问题的反演树（简单情况下使用）,2 反演求解过程,从反演树求取某一个问题的答案，其过程为：将前提条件用谓词表示出来，并化成子句集 S,将目标公式（问题）用谓词表示出来，把由目标公式的否定所产生的子句及其非（目标公式否定之否定）用析取连接词相连组成

27、一个新子句（重言式），加到 S 构成新的子句集 S,对子句集 S，进行消解演绎，直到得到某一个子句为止将此子句作为问题的答案,例：已知三个前提条件F1:：王(Wang)先生是小李(Li)的老师F2：小李与小张(Zhang)是同班同学F3：如果x与y是同班同学，则x的老师就是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,Zha

28、ng),用谓词表示前提条件与目标（问题）：,前提的子句集：(1)T(Wang,Li)(2)C(Li,Zhang)(3)C(x,y)T(z,x)T(z,y)目标的否定的子句及其非组成重言式：(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=Wan

29、g/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=,例：如果无论约翰(John)去哪里，菲多(Fido)也就去哪里，那么如果约翰在学校里，则菲多在哪里？,解：定义谓词 AT(x,y)：人 x 在 y 处,前提条件（F1、F2）与目标（G）为：,前提条件的子句集：,目标的“非”及其子句,将目标的否定的子句及其非构成重言式：,子句集：

30、,消解过程,反演树,3.6.6 Horn子句集消解,Horn子句集是一阶谓词公式的真子集与一阶谓词逻辑具有同样的表达能力,Horn子句集的特点：,如果对于谓词公式 的任意一组指派（具体的一组值），公式 的值均为真，则称 为永真公式,如果对于谓词公式 的任意一组指派，公式 的值均为假，则称 为不可满足（永假）公式，相应地称公式 的子句集是不可满足的,如果至少存在一组指派，使公式 为真，则称 为可满足公式,一个非 Horn 子句集 S 可以通过变换化成为 Horn 子句集 S，两者在不可满足性上等价,原子公式：原子命题（0元谓词）和谓词基本式：原子公式或原子公式的非我们再将基本式细分：正基本式：不

31、带“非号”的原子公式负基本式：带“非号”的原子公式,Horn子句：最多只含有一个正基本式的子句（只含一个正基本式或者不含正基本式）Horn子句集：每一个子句均为Horn子句的子句集,Horn子句及Horn子句集的定义：,例：设 Pi 和 Qi 是正基本式，有谓词公式：(P1Pk)(Q1Q2)=(P1Pk)(Q1Q2)=(P1Pk Q1)(P1PkQ2)子句集S：P1Pk Q1,P1PkQ2是Horn子句集,消解原理部分的书面作业1、求公式集W=P(f(x),y),P(f(y),a)的最一般的合一者（一致置换）,2化成子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),3、设子句集为：S=P(x)Q(x),P(f(a),Q(f(z)请求出它的一个反演,4、设前提条件为 F1:(x)P(x)(y)Q(y)L(x,y)F2:(x)P(x)(y)R(y)L(x,y)试用消解原理证明下列结论成立：G:(x)R(x)Q(x),