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

《第3章(搜索推理技术5-消解原理).pptx》由会员分享，可在线阅读，更多相关《第3章(搜索推理技术5-消解原理).pptx（148页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人人 工工 智智 能能ArtificialIntelligence(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.6Horn子句集消解（补充）子句集消解（补充

2、）3.6.7Prolog语言简介语言简介（补充）（补充）3.6消解原理消解原理第第2章中介绍章中介绍：谓词逻辑的基本知识谓词逻辑的基本知识合一算法（求最一般的一致置换或合一者合一算法（求最一般的一致置换或合一者mgu）本节本节：消解原理（或者归结原理）消解原理（或者归结原理）3.6.1子句集的求取子句集的求取如如何何将将谓谓词词公公式式转转化化为为子子句句集集，作作为为合合一一算算法法的输入（公式集）的输入（公式集）3.6.1.1若干基本概念若干基本概念3.6.1.2子句集的求取子句集的求取3.6.1.1若干基本概念若干基本概念1自由变元与约束变元自由变元与约束变元2前束范式与前束合取范式前束

3、范式与前束合取范式3斯科伦（斯科伦（Skolem）范式范式4子句集子句集设设，是是一一个个谓谓词词公公式式，将将量量词词记记作作（即即 或或）1自由变元与约束变元自由变元与约束变元如果如果中包含部分公式中包含部分公式(x)，则则中变元中变元x的的一切出现都称为一切出现都称为x在在中的约束出现，相应地称中的约束出现，相应地称x为为约束变元约束变元（哑元、虚构变量、约束变量）（哑元、虚构变量、约束变量）约束变元约束变元中不在任何量词作用域内的变元中不在任何量词作用域内的变元x，称为变称为变元元x在在中的自由出现，相应地称中的自由出现，相应地称x为为自由变自由变元元（自由变量）（自由变量）自由变元自

4、由变元：量词的作用域（辖域）是直接跟在它后面的公量词的作用域（辖域）是直接跟在它后面的公式式如果有括号，则是括号里的公式如果有括号，则是括号里的公式如果没有括号，则是最短的完整公式如果没有括号，则是最短的完整公式说明说明：例例1：x(P(x)y(R(x,y)y(R(x,y)x,y都是约束变元都是约束变元例例2：x(P(x)(R(x,y)x是约束变量，是约束变量，y是自由变元是自由变元改改名名：将将谓谓词词公公式式中中一一个个变变元元名名改改成成另另一一个个变变元元名名，但但是是要要求求改改名名后后的的公公式式与与原原公公式式意意义义相相同同（真假值相同）（真假值相同）原原则则：改改成成的的新新

5、的的变变元元名名一一定定是是量量词词作作用用域域中中没没有出现过的变元名（包括约束变元和自由变元）有出现过的变元名（包括约束变元和自由变元）约束变元的改名约束变元的改名或或变量的标准化变量的标准化例例3：x(P(x)(R(x,y)除了除了y外，可以将外，可以将x改成任何变元名改成任何变元名例例4：xP(x)Q(y)可以改成任何变元名，包括可以改成任何变元名，包括 y（建议不要用建议不要用）2 前束范式与前束合取范式前束范式与前束合取范式定义定义：设谓词公式：设谓词公式具有形式：具有形式：(1x1)(nxn)M其中：其中：i(i=1,n)是是 或或 M是不包含量词的谓词公式是不包含量词的谓词公式

6、则，称则，称是是前束范式前束范式称称(1x1)(nxn)为为前束前束称称M为为母式母式定定义义：设设谓谓词词公公式式是是一一个个前前束束范范式式，如如果果的的母母式式具有形式：具有形式：（M11M12M1n1）（M21M22M2n2）(Mm1Mm2Mmnm）其中，其中，Mi j是原子公式或其非，则称是原子公式或其非，则称是是前束合取前束合取范式范式。相应地有前束析取范式。相应地有前束析取范式前束范式前束范式：(x)(y)(z)(P(x)Q(y)R(z)前束合取范式前束合取范式（交换律、交换律、分配律，分配律，p.33）(x)(y)(z)(R(z)P(x)(R(z)Q(y)例例：3 斯柯伦范式斯

7、柯伦范式定定义义：前前束束中中不不含含存存在在量量词词的的前前束束范范式式称称为为斯斯柯伦范式柯伦范式若若 xk(1kn)左左边边没没有有全全称称量量词词，则则取取不不在在母母式式中中出出现现的的常常量量替替代代母母式式中中的的所所有有 xk，并并删删除前束中的除前束中的 xk消去存在量词的规则消去存在量词的规则或或前束范式化成斯柯伦前束范式化成斯柯伦的的步骤步骤是：是：若若 xk(1 kn)左边有全称量词左边有全称量词 (xs1)(xs2)(xsr)(1r，1s1s2srk,il)的消解式的消解式消解演绎和反演的定义消解演绎和反演的定义：则则称称 c1,cn是是从从子子句句集集 S到到子子句

8、句 c的的一一个个消消解演绎解演绎当当 c=时的消解演绎称为（消解）时的消解演绎称为（消解）反演反演把把谓谓词词公公式式转转化化为为子子句句集集S（所所有有子子句句的的变变量量名名不不同同）如空子句成为子句集的子句，则算法结束如空子句成为子句集的子句，则算法结束在子句集中选取在子句集中选取两个不同两个不同的的可以消解可以消解的子句的子句ci,cj注：子句的个数限制注：子句的个数限制反演的基本算法反演的基本算法：计算计算ci ,cj 的消解式的消解式rij把把rij 加到子句集中，形成新的子句集加到子句集中，形成新的子句集S转到转到反演的流程图反演的流程图将谓词公式化成子句集将谓词公式化成子句集

9、有空子句？有空子句？成功结束成功结束取两个子句取两个子句有消解式？有消解式？无解结束无解结束将消解式将消解式送到子句送到子句集集有有无无例例1：设子句集为：设子句集为S=PQ,PQ,PQ,PQ求求S的一个反演的一个反演S的一个反演为：的一个反演为：PQ(S)PQ(S)PQ(S)PQ(S)QQPPS的另一个反演为：的另一个反演为：例例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的一个反演的一个反演P(z1,a)P(z1,x1)P(x1,z1)（S）P(z2,f(z2)P(a,z2)（S）P(f(z3)

10、,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)最一般的合一者最一般的合一者为为=a/x1,a/z1,a/z3对应的对应的消

11、解式消解式为：为：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)

12、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例例31消解反演（数学定理的证

13、明，论断是否成立，消解反演（数学定理的证明，论断是否成立，即即反演反演）2反演求解过程（回答问题，即反演求解过程（回答问题，即消解演绎消解演绎）3.6.5消解反演求解过程消解反演求解过程1消解反演消解反演消解反演证明定理的思路非常类似于数学中的消解反演证明定理的思路非常类似于数学中的反证法反证法给给定定一一个个公公式式集集S（前前提提条条件件）和和目目标标公公式式L（结结论论），通通过过反反演演来来求求证证目目标标公公式式L，其其证证明明过过程程为：为：否定否定L，得到得到L把把L加到加到S中中把把新新形形成成的的集集合合S，L化化为为子子句句集集（简简化化化化法法）应用消解原理，试图导出一个

14、表示矛盾的应用消解原理，试图导出一个表示矛盾的空子句空子句设设SF1,Fn是前提条件，是前提条件，L是欲求证的结论是欲求证的结论则，从前提条件推出结论的问题，可以表示成：则，从前提条件推出结论的问题，可以表示成：F1Fn L （F1Fn）L并证明其并证明其永真永真（永远成立）（永远成立）反演证明过程的正确性反演证明过程的正确性：先将公式取先将公式取“非非”：（F1Fn）L）（F1Fn）LF1FnL利利用用消消解解原原理理来来证证明明它它是是永永假假的的（即即，构构造造一一个个反演）反演）实际中，我们可以将实际中，我们可以将F1FnL中的每一个部分化成子句集（中的每一个部分化成子句集（化法任选化

15、法任选），合），合并后得到完整的子句集，然后利用消解原理导并后得到完整的子句集，然后利用消解原理导出空子句（反演）出空子句（反演）设有公式集：设有公式集：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)

16、,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/yR(a)mgu=a/zC(y)R(y)C(a)O(a

17、)O(z)R(z)前提前提：每一个储蓄钱的人都获得利息：每一个储蓄钱的人都获得利息结论结论：如果没有利息，那么就没有人去储蓄钱：如果没有利息，那么就没有人去储蓄钱例例2：用消解反演证明：用消解反演证明S(x,y)：某人某人x 储蓄储蓄y（数量）数量）M(x)：x（数量）数量）是钱是钱I(x)：x（数量）是利息数量）是利息E(x,y)：某人某人x获得获得y（数量）数量）证明证明：设设前提前提：每一个储蓄钱的人都获得利息每一个储蓄钱的人都获得利息结论结论：如果没有利息，那么就没有人去储蓄钱如果没有利息，那么就没有人去储蓄钱任何人任何人x 将将y 数量数量的钱存入银行的钱存入银行任何人任何人x 得到

18、得到y 数量的利息数量的利息没有没有x 数数量的利息量的利息任何人任何人x 就不会将任何就不会将任何数量数量y的钱存入银行的钱存入银行将前提条件化成子句集将前提条件化成子句集前束前束范式范式前束合前束合取范式取范式前提条件的前提条件的子句集子句集结论取非：结论取非：化成子句集化成子句集改名、消除改名、消除“结论非结论非”的子句集的子句集完整的子句集完整的子句集反演过程反演过程储蓄问题的反演树（简单情况下使用）储蓄问题的反演树（简单情况下使用）2反演求解过程反演求解过程从反演树求取某一个问题的答案，其过程为：从反演树求取某一个问题的答案，其过程为：将前提条件用谓词表示出来，并化成子句集将前提条件

19、用谓词表示出来，并化成子句集S将目标公式（问题）用谓词表示出来，将目标公式（问题）用谓词表示出来，把由目把由目标公式的否定所产生的子句标公式的否定所产生的子句及其及其非非（目标公（目标公式否定之否定）用式否定之否定）用析取连接词析取连接词相连组成一个相连组成一个新子句新子句（重言式），加到（重言式），加到S构成新的子句集构成新的子句集S对子句集对子句集S，进行，进行消解演绎消解演绎，直到得到某一，直到得到某一个个子句子句为止为止将此子句作为将此子句作为问题的答案问题的答案例：例：已知三个前提条件已知三个前提条件F1:：王王(Wang)先生是小李先生是小李(Li)的老师的老师F2：小李与小张小李

20、与小张(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,Zhang)用谓词表示前提条件与目标（问题）：用谓词表示前提条件与目标（问题）：前提的子句集前提的子句集：(1)T(

21、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=Wang/z,Li/x)消解演绎

22、过程消解演绎过程(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）为：为：前提条件

23、的子句集：前提条件的子句集：目标目标的的“非非”及其子及其子句句将目标的否定的子句及其非构成将目标的否定的子句及其非构成重言式重言式：子句集：子句集：消解过程消解过程反演树反演树3.6.6Horn子句集消解子句集消解Horn子句集是一阶谓词公式的真子集子句集是一阶谓词公式的真子集与一阶谓词逻辑具有同样的表达能力与一阶谓词逻辑具有同样的表达能力Horn子句集的特点子句集的特点：如如果果对对于于谓谓词词公公式式 的的任任意意一一组组指指派派（具具体体的的一一组值），公式组值），公式 的值均为真，则称的值均为真，则称 为为永真公式永真公式如如果果对对于于谓谓词词公公式式 的的任任意意一一组组指指派派

24、，公公式式 的的值值均均为为假假，则则称称 为为不不可可满满足足（永永假假）公公式式，相应地称公式相应地称公式 的子句集是的子句集是不可满足不可满足的的如如果果至至少少存存在在一一组组指指派派，使使公公式式 为为真真，则则称称 为为可满足公式可满足公式一个非一个非 Horn子句集子句集 S可以通过变换化成可以通过变换化成为为 Horn子句集子句集 S，两者在两者在不可满足性不可满足性上上等价等价原子公式原子公式：原子命题（：原子命题（0元谓词）和谓词元谓词）和谓词基本式基本式：原子公式或原子公式的非：原子公式或原子公式的非我们再将基本式细分我们再将基本式细分：正基本式正基本式：不带：不带“非号

25、非号”的原子公式的原子公式负基本式负基本式：带：带“非号非号”的原子公式的原子公式HornHorn子子子子句句句句：最最多多只只含含有有一一个个正正基基本本式式的的子子句句（只只只只含一个正基本式或者不含正基本式含一个正基本式或者不含正基本式含一个正基本式或者不含正基本式含一个正基本式或者不含正基本式）HornHorn子句集子句集子句集子句集：每一个子句均为每一个子句均为Horn子句的子句集子句的子句集Horn子句及子句及Horn子句集的定义子句集的定义：例例：设设Pi 和和Qi 是正基本式，有谓词公式：是正基本式，有谓词公式：(P1Pk)(Q1Q2)=(P1Pk)(Q1Q2)=(P1PkQ1

26、)(P1PkQ2)子句集子句集S：P1PkQ1,P1PkQ2是是Horn子句集子句集消解原理部分的书面作业消解原理部分的书面作业1、求公式集、求公式集W=P(f(x),y),P(f(y),a)的最一般的合一者（一致置换）的最一般的合一者（一致置换）2、p108页页3-17(4)，化成子句集，化成子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)注注：书中的小写：书中的小写p 应改为大写应改为大写P3、设子句集为：、设子句集为：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)5、编写、编写Prolog程序，并上机调试通过：程序，并上机调试通过：已知三个前提已知三个前提F1:F1:王王(Wang)Wang)先生是小李先生是小李(Li)Li)的老师的老师F2:F2:小李与小张小李与小张(Zhang)Zhang)是同班同学是同班同学F3:F3:如果如果x x与与y y是同班同学，则是同班同学，则x x的老师就是的老师就是y y的老师的老师问题：小张的老师是谁？问题：小张的老师是谁？判断一个整数是否偶数判断一个整数是否偶数