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.
2、7 Prolog 语言简介语言简介 （补充）（补充）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 在在 中的自由出现，相应地称中的自由出现，相应地
4、称 x 为为自由变自由变元元（自由变量）（自由变量）自由变元自由变元： 量词的作用域（辖域）是直接跟在它后面的公量词的作用域（辖域）是直接跟在它后面的公式式 如果有括号，则是括号里的公式如果有括号，则是括号里的公式 如果没有括号，则是最短的完整公式如果没有括号，则是最短的完整公式说明说明：例例1： x ( P(x) ) x , y 都是约束变元都是约束变元例例2： x ( P(x) (R(x, y) ) x 是约束变量，是约束变量，y 是自由变元是自由变元改名改名：将谓词公式中一个变元名改成另一个变元：将谓词公式中一个变元名改成另一个变元名，但是要求改名后的公式与原公式名，但是要求改名后的公式
5、与原公式意义相同意义相同（真假值相同）（真假值相同）原则原则：改成的新的变元名一定是：改成的新的变元名一定是量词作用域量词作用域中没中没有出现过的变元名（包括约束变元和自由变元）有出现过的变元名（包括约束变元和自由变元）约束变元的改名约束变元的改名或或变量的标准化变量的标准化例例3： x ( P(x) (R(x, y) 除了除了 y 外，可以将外，可以将 x 改成任何变元名改成任何变元名例例4： x P(x) Q(y) 可以改成任何变元名，包括可以改成任何变元名，包括 y（建议不要用建议不要用）2 前束范式与前束合取范式前束范式与前束合取范式 定义定义：设谓词公式：设谓词公式具有形式：具有形式
6、： (1x1)(nxn) M其中：其中：i ( i = 1 , , n ) 是是 或或 M 是不包含量词的谓词公式是不包含量词的谓词公式则，称则，称是是前束范式前束范式 称称 (1x1)(nxn ) 为为前束前束 称称 M 为为母式母式定义定义：设谓词公式：设谓词公式是一个前束范式，如果是一个前束范式，如果的母式的母式具有形式：具有形式： （M11M12M1 n1） （M21M22M2 n2） (Mm1Mm2Mm nm）其中，其中，M i j 是原子公式或其非，则称是原子公式或其非，则称是是前束合取前束合取范式范式。相应地有前束析取范式。相应地有前束析取范式前束范式前束范式：( x) ( y)
7、 ( z)(P(x)Q(y)R(z) 前束合取范式前束合取范式（交换律、交换律、分配律分配律）( x) ( y) ( z)(R(z)P(x)(R(z)Q(y)例例：3 斯柯伦范式斯柯伦范式 定义定义：前束中：前束中不含存在量词不含存在量词的前束范式称为斯的前束范式称为斯柯伦范式柯伦范式若若 xk (1kn )左边左边没有全称量词没有全称量词，则取不，则取不在母式中出现的常量替代母式中的所有在母式中出现的常量替代母式中的所有 xk ，并并删除前束中的删除前束中的 xk消去存在量词的规则消去存在量词的规则 或或 前束范式化成斯柯伦前束范式化成斯柯伦的的步骤步骤是：是：若若 xk (1 kn )左边
8、有全称量词左边有全称量词 ( xs1) ( xs2)( xsr) ( 1r，1s1s2srk , il )的消解式的消解式消解演绎和反演的定义消解演绎和反演的定义：则称则称 c1, , cn 是从子句集是从子句集 S 到子句到子句 c 的一个的一个消消解演绎解演绎当当 c= 时的消解演绎称为（消解）时的消解演绎称为（消解）反演反演 把谓词公式转化为子句集把谓词公式转化为子句集S（所有子句的变量名不所有子句的变量名不同同）如空子句成为子句集的子句，则算法结束如空子句成为子句集的子句，则算法结束在子句集中选取在子句集中选取两个不同两个不同的的可以消解可以消解的子句的子句ci , cj注：子句的个数
9、限制注：子句的个数限制反演的基本算法反演的基本算法：计算计算 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的另一个反演为：的另一个反演为：
10、例例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),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 对应的对应的消
11、解式消解式：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 对应的对应的消解式消解式为：为：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
12、) 最一般的合一者最一般的合一者为为=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,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)
13、,a) ( ) ( )反演过程反演过程：3.6.3 消解推理规则消解推理规则 （命题的特殊情况命题的特殊情况）从父子句求消解式的若干例子从父子句求消解式的若干例子1、假言推理假言推理2、合并合并3、重言式重言式4、空子句（矛盾）空子句（矛盾）5、链式（三段论）链式（三段论）( )( )B yC y( )B x3.6.4 含有变量的消解式（谓词情况）含有变量的消解式（谓词情况）先求最一般的合一者先求最一般的合一者mgu，再求消解式再求消解式例例1 置换置换 / x y( )C x例例2例例31 消解反演（数学定理的证明，论断是否成立，消解反演（数学定理的证明，论断是否成立，即即反演反演）2 反演
14、求解过程（回答问题，即反演求解过程（回答问题，即消解演绎消解演绎）3.6.5 消解反演求解过程消解反演求解过程1 消解反演消解反演消解反演证明定理的思路非常类似于数学中的消解反演证明定理的思路非常类似于数学中的反证法反证法给定一个公式集给定一个公式集 S（前提条件）和目标公式前提条件）和目标公式 L（结结论），通过反演来求证目标公式论），通过反演来求证目标公式 L，其证明过程其证明过程为：为：否定否定 L ，得到得到 L把把 L 加到加到 S 中中把新形成的集合把新形成的集合 S ， L 化为子句集（化为子句集（简化化简化化法法）应用消解原理，试图导出一个表示矛盾的应用消解原理，试图导出一个表
15、示矛盾的空子句空子句设设SF1,Fn 是前提条件，是前提条件，L是欲求证的结论是欲求证的结论则，从前提条件推出结论的问题，可以表示成：则，从前提条件推出结论的问题，可以表示成： F1Fn L （F1Fn ）L 并证明其并证明其永真永真（永远成立）（永远成立）反演证明过程的正确性反演证明过程的正确性：先将公式取先将公式取“非非” ： （F1Fn ）L）（F1Fn ） L F1Fn L利用消解原理来证明它是利用消解原理来证明它是永假永假的（即，构造一个的（即，构造一个反演）反演）实际中，我们可以将实际中，我们可以将 F1Fn L中的每一个部分化成子句集（中的每一个部分化成子句集（化法任选化法任选）
16、，合），合并后得到完整的子句集，然后利用消解原理导并后得到完整的子句集，然后利用消解原理导出空子句（反演）出空子句（反演）设有公式集：设有公式集：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) 子
17、句集子句集= 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) 证明过程证明
18、过程： 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 （数量）数量）证明证明：设设前提前提：每一个储蓄钱的人都获得利息每一个储蓄钱的人都获得利息结论结论：如
19、果没有利息，那么就没有人去储蓄钱如果没有利息，那么就没有人去储蓄钱任何人任何人 x 将将 y 数量数量的钱存入银行的钱存入银行任何人任何人 x 得到得到 y 数量的利息数量的利息没有没有 x 数数量的利息量的利息任何人任何人 x 就不会将任何就不会将任何数量数量 y 的钱存入银行的钱存入银行将前提条件化成子句集将前提条件化成子句集前束前束范式范式前束合前束合取范式取范式前提条件的前提条件的子句集子句集(1) ( , )( )( ( )S x yM yI f x(2) ( , )( )( ,( )S u vM vE u f u结论取非：结论取非：化成子句集化成子句集改名、消除改名、消除 “结论非
20、结论非”的子句集的子句集(3) ( )I z(4) ( , )S a b(5) ( )M b完整的子句集完整的子句集(1) ( , )( )( ( )S x yM yI f x(2) ( , )( )( ,( )S u vM vE u f u(3) ( )I z(4) ( , )S a b(5) ( )M b反演过程反演过程 ( )(6) ( , )( ) (1)(3) f xzS x yM ymgu (7) ( ) (6)(4) ,abxyM bmgu (8) (5)(7) mgu (1) ( , )( )( ( )S x yM yI f x(2) ( , )( )( ,( )S u vM
21、vE u f u(3) ( )I z(4) ( , )S a b(5) ( )M b储蓄问题的反演树（简单情况下使用）储蓄问题的反演树（简单情况下使用）2 反演求解过程反演求解过程从反演树求取某一个问题的答案，其过程为：从反演树求取某一个问题的答案，其过程为：将前提条件用谓词表示出来，并化成子句集将前提条件用谓词表示出来，并化成子句集 S将目标公式（问题）用谓词表示出来，将目标公式（问题）用谓词表示出来，把由目把由目标公式的否定所产生的子句标公式的否定所产生的子句及其及其非非（目标公（目标公式否定之否定）用式否定之否定）用析取连接词析取连接词相连组成一个相连组成一个新子句新子句（重言式），加到
22、（重言式），加到 S 构成新的子句集构成新的子句集 S 对子句集对子句集 S ，进行，进行消解演绎消解演绎，直到得到某一，直到得到某一个个子句子句为止为止将此子句作为将此子句作为问题的答案问题的答案例：例： 已知三个前提条件已知三个前提条件F1:：王王(Wang)先生是小李先生是小李(Li)的老师的老师F2：小李与小张小李与小张(Zhang)是同班同学是同班同学F3：如果如果x与与y是同班同学，则是同班同学，则x的老师就是的老师就是y的老师的老师问题：小张的老师是谁？问题：小张的老师是谁？解：解：定义谓词定义谓词T(x , y) : x 是是 y 的老师的老师C(x , y) : x 与与 y
23、 是同班同学是同班同学前提前提：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)目标的否定的子句及其非目标的否定的子句及其非组成重言式：组成重言式：(4) T(x,Zhang) T(x,Z
24、hang) 完整的子句集完整的子句集：(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)
25、 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）为：为：前提条件的子句集：前提条件的子句集：目标目标的的“非非”及其子及其子句句将目标的否定的子句及其
26、非构成将目标的否定的子句及其非构成重言式重言式：子句集：子句集：(1) AT(JOHN, )AT(FIDO, )(2) AT(JOHN, SCHOOL)(3) AT(FIDO, )AT(FIDO, )yyxx (4) AT(JOHN, )AT(FIDO, ) (3)(1) mgu=x / yxx (2) AT(JOHN, SCHOOL)(3) AT(FIDO, )AT(FIDO, )xx (1) AT(JOHN, )AT(FIDO, )yy 消解过程消解过程(5) AT(FIDO, SCHOOL) (4)(2) mgu=SCHOOL/ x(1) AT(JOHN, )AT(FIDO, )yy (
27、3) AT(FIDO, )AT(FIDO, )xx (4) AT(JOHN, )AT(FIDO, ) xx mgu= / xy(2) AT(JOHN, SCHOOL)(5) AT(FIDO, SCHOOL)mgu=SCHOOL/ x反演树反演树3.6.6 Horn子句集消解子句集消解 Horn子句集是一阶谓词公式的真子集子句集是一阶谓词公式的真子集 与一阶谓词逻辑具有同样的表达能力与一阶谓词逻辑具有同样的表达能力 Horn子句集的特点子句集的特点：如果对于谓词公式如果对于谓词公式 的任意一组指派（具体的一的任意一组指派（具体的一组值），公式组值），公式 的值均为真，则称的值均为真，则称 为为永
28、真公永真公式式 ( x) ( )() ( )PPP xy P y 如果对于谓词公式如果对于谓词公式 的任意一组指派，公式的任意一组指派，公式 的值均为假，则称的值均为假，则称 为为不可满足不可满足（永假永假）公式，）公式，相应地称公式相应地称公式 的子句集是的子句集是不可满足不可满足的的 ( x) ( ) () ( )PPP xy P y 如果至少存在一组指派，使公式如果至少存在一组指派，使公式 为真，则称为真，则称 为为可满足公式可满足公式一个非一个非 Horn 子句集子句集 S 可以通过变换化成可以通过变换化成为为 Horn 子句集子句集 S，两者在两者在上等价上等价 原子公式原子公式：原
29、子命题（：原子命题（0元谓词）和谓词元谓词）和谓词基本式基本式：原子公式或原子公式的非：原子公式或原子公式的非 我们再将基本式细分我们再将基本式细分：正基本式正基本式：不带：不带“非号非号”的原子公式的原子公式负基本式负基本式：带：带“非号非号”的原子公式的原子公式 ：最多只含有一个正基本式的子句（最多只含有一个正基本式的子句（）：每一个子句均为每一个子句均为Horn子句的子句集子句的子句集Horn子句及子句及Horn子句集的定义子句集的定义：例例：设设 Pi 和和 Qi 是正基本式，有谓词公式：是正基本式，有谓词公式：(P1Pk)(Q1Q2)=(P1Pk) (Q1Q2)=(P1Pk Q1)(
30、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)
