第三章人工智能蔡自兴

1、1第三章第三章 归结推理方法归结推理方法 概述概述 命题逻辑的归结法命题逻辑的归结法 谓词归结子句形谓词归结子句形 归结原理归结原理 归结过程的策略控制归结过程的策略控制 Herbrand定理定理2归结归结推理推理命题命题逻辑逻辑谓词逻谓词逻辑辑Skolem标准形、标准形、子句集子句集基本基本概念概念谓词逻辑谓词逻辑归结原理归结原理合一和置换、合一和置换、控制策略控制策略数理数理逻辑逻辑命题逻辑命题逻辑归结归结Herbrand定理定理3第三章第三章 归结推理方法归结推理方法 概述概述 命题逻辑的归结法命题逻辑的归结法 谓词归结子句形谓词归结子句形 归结原理归结原理 归结过程的策略控制归结过程的

2、策略控制4概述概述 归结原理归结原理由由J.A.Robinson由由1965年提出。年提出。 是一阶逻辑中至今为止的最有效的半可判定的算法。是一阶逻辑中至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。以在有限步内给以判定。 语义网络、框架表示、产生式规则等等都是以推理方语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即：有了规则已知条件，顺藤摸瓜找到法为前提的。即：有了规则已知条件，顺藤摸瓜找到结果。结果。 而归结方法是自动推理、自动推导证明用的。而归结方法是自动推理、自动推导证明用的

3、。（“数学定理机器证明数学定理机器证明”） 本课程只讨论一阶谓词逻辑描述下的归结推理方法，不本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题涉及高阶谓词逻辑问题。 5第三章第三章 归结推理方法归结推理方法 概述概述 命题逻辑的归结法命题逻辑的归结法 谓词归结子句形谓词归结子句形 归结原理归结原理 归结过程的策略控制归结过程的策略控制 Herbrand定理定理6命题逻辑的归结法命题逻辑的归结法 命题逻辑基础：命题逻辑基础： 定义：定义： 合取式：合取式：p与与q，记做，记做p q 析取式：析取式： p或或q，记做，记做p q 蕴含式：蕴含式： 如果如果p则则q，记做，记做p

4、q 等价式：等价式：p当且仅当当且仅当q，记做，记做p q。7命题逻辑基础命题逻辑基础 定义：定义： 若若A无成假赋值，则称无成假赋值，则称A为为重言式或永真式重言式或永真式； 若若A无成真赋值，则称无成真赋值，则称A为为矛盾式或永假式矛盾式或永假式； 若若A至少有一个成真赋值，则称至少有一个成真赋值，则称A为可满足的为可满足的； 析取范式析取范式：仅由有限个简单合取式组成的析取式。：仅由有限个简单合取式组成的析取式。 合取范式合取范式：仅由有限个简单析取式组成的合取式。：仅由有限个简单析取式组成的合取式。8命题逻辑基础命题逻辑基础 基本等值式基本等值式 交换率交换率：pq q p ； p q

5、 q p 结合率结合率： (pq) r p(q r); (p q) r p (q r) 分配率分配率： p(q r) ( (pq)(p r) ； p (q r) ( (p q) (p r) 9命题逻辑基础命题逻辑基础 基本等值式基本等值式 摩根率摩根率: (pq) p q ； (p q) p q 吸收率吸收率: p(pq ) p ； p (pq ) p 同一律同一律: p00 p ； p11 p 蕴含等值式蕴含等值式: p q pq 假言易位式假言易位式: p q q p10命题举例命题举例命题：能判断真假（不是既真又假）的陈述句。命题：能判断真假（不是既真又假）的陈述句。 简单陈述句描述事实

6、、事物的状态、关系等性质。简单陈述句描述事实、事物的状态、关系等性质。例如：例如：1 1+1=22 雪是黑色的。雪是黑色的。3 北京是中国的首都。北京是中国的首都。4 到冥王星去渡假。到冥王星去渡假。 判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上上4个例子都是命题。个例子都是

7、命题。而例如：而例如：1 快点走吧！快点走吧！ 2 到那去？到那去？ 3 x+y10等等句子，都不是命题。等等句子，都不是命题。11命题表示公式（命题表示公式（1）将陈述句转化成命题公式。将陈述句转化成命题公式。如：设如：设“下雨下雨”为为p，“骑车上班骑车上班”为为q，1“只要不下雨，我骑自行车上班只要不下雨，我骑自行车上班”。p 是是 q的充分条件，的充分条件，因而，可得命题公式：因而，可得命题公式： p q2“只有不下雨，我才骑自行车上班只有不下雨，我才骑自行车上班”。p 是是 q的必要条件，的必要条件，因而，可得命题公式：因而，可得命题公式：q p 12命题表示公式（命题表示公式（2）

8、例如：例如： 1 “如果我进城我就去看你，除非我很累。如果我进城我就去看你，除非我很累。”设：设：p，我进城；，我进城；q，去看你；，去看你；r，我很累。，我很累。则有命题公式：则有命题公式：r (p q)。 2“应届高中生，得过数学或物理竞赛的一等应届高中生，得过数学或物理竞赛的一等 奖，奖，保送上北京大学。保送上北京大学。” 设：设：p，应届高中生，应届高中生，q，保送上北京大学上学，保送上北京大学上学， r，是得过数学一等奖。，是得过数学一等奖。t，是得过物理一等奖。，是得过物理一等奖。 则有命题公式公式：则有命题公式公式：p ( r t t ) q。 13命题命题 逻辑的推理规则逻辑的

9、推理规则附加：附加：A=（A B)简化简化： (AB) = A假言推理假言推理: (AB) A) = B拒取式：拒取式：(AB) B) = A析取三段论：析取三段论： (A B) A) = B假言假言三段论：三段论： (AB ) (BC ) ) = (AC) 等价三段论：等价三段论： (A B) (B C ) ) = (A C) 构造性两难：构造性两难： (AB ) (CD ) （A C) = (B D) 14利用规则构造证明利用规则构造证明例：例：前提：前提：p q, pr , st, s r, t 结论：结论：q 证明：证明： st 前提引入前提引入 t 前提引入前提引入 s 拒取规则拒取

10、规则 s r 前提引入前提引入 r pr 前提引入前提引入 p 拒取规则拒取规则 p q 前提引入前提引入 q 析取三段论析取三段论15命题逻辑的归结法命题逻辑的归结法 基本单元基本单元：简单命题（陈述句）：简单命题（陈述句）例：例： 命题：命题： A A1 1、A A2 2、A A3 3 和和 B B求证：求证： A A1 1AA2 2AA3 3成立，则成立，则B B成立，成立，即：即：A A1 1AA2 2AA3 3 B B反证法反证法：证明：证明A A1 1AA2 2AA3 3B B 是矛盾式是矛盾式 （永假式）（永假式） 16归谬法证明归谬法证明例：例：前提：前提：p （ （r s)

11、q ), p, s 结论：结论：q 证明：证明： p （ （r s) q ) 前提引入前提引入 p 前提引入前提引入 （r s) q 假言推理假言推理 q 否定结论引入否定结论引入（r s) 拒取式拒取式 s 前提引入前提引入 s 简化简化 s s 合取合取 得到矛盾结果得到矛盾结果17命题逻辑的归结法命题逻辑的归结法 归结原理是在谓词公式的子句集合之上进行归结的，因而首先归结原理是在谓词公式的子句集合之上进行归结的，因而首先讨论子句集。讨论子句集。建立子句集建立子句集l合取范式合取范式：命题、命题和的与，：命题、命题和的与， 如：如：PP（ PQPQ）（ PQPQ）l子句集子句集S S：合取

12、范式形式下的子命题（元素）的集合：合取范式形式下的子命题（元素）的集合例：命题公式：例：命题公式： PP（ PQPQ）（ PQPQ） 子句集子句集 S S：S = P, PQ, S = P, PQ, PQPQ 18命题逻辑的归结法命题逻辑的归结法 归结式归结式消除互补对，求新子句消除互补对，求新子句得到归结式得到归结式。如子句：如子句：C C1 1, C, C2 2， 归结式：归结式：R(CR(C1 1, C, C2 2) = C) = C1 1CC2 2 注意：注意：C C1 1CC2 2 R(C R(C1 1, C, C2 2) ) ， 反之反之成立。成立。 19命题逻辑的归结法命题逻辑的

13、归结法 归结过程归结过程 将命题写成合取范式将命题写成合取范式 求出子句集求出子句集 对子句集使用归结推理规则对子句集使用归结推理规则 归结式作为新子句参加归结归结式作为新子句参加归结 归结式为空子句归结式为空子句 ，S是不可满足的（矛盾），原命题成立。是不可满足的（矛盾），原命题成立。 （证明完毕）（证明完毕） 谓词的归结谓词的归结：除了有量词和函数以外，其余和命题归：除了有量词和函数以外，其余和命题归结过程一样。结过程一样。 20命题逻辑归结例题（命题逻辑归结例题（1）例题，证明公式：例题，证明公式：(P Q) (Q P)证明：证明： （1）根据归结原理，将待证明公式转化成待归结命题公式：

14、）根据归结原理，将待证明公式转化成待归结命题公式：(P Q) (Q P)（2）分别将公式前项化为合取范式：）分别将公式前项化为合取范式：P Q P Q结论求后的后项化为合取范式：结论求后的后项化为合取范式：(Q P) (QP) Q P两项合并后化为合取范式：两项合并后化为合取范式：（P Q）Q P （3）则子句集为：）则子句集为： PQ，Q，P21命题逻辑归结例题（命题逻辑归结例题（2）子句集为：子句集为： PQ，Q，P（4）对子句集中的子句进行归结可得：）对子句集中的子句进行归结可得： 1. PQ 2. Q 3. P 4. Q，（1，3归结）归结） 5. ，（2，4归结）归结）由上可得原公式

15、成立。由上可得原公式成立。22第三章第三章 归结推理方法归结推理方法 概述概述 命题逻辑的归结法命题逻辑的归结法 谓词归结子句形谓词归结子句形 归结原理归结原理 归结过程的策略控制归结过程的策略控制 Herbrand定理定理23谓词归结原理基础谓词归结原理基础一阶逻辑一阶逻辑 基本概念基本概念 个体词：表示主语的词个体词：表示主语的词 谓词：刻画个体性质或个体之间关系谓词：刻画个体性质或个体之间关系的词的词 量词：表示数量的词量词：表示数量的词24谓词归结原理基础谓词归结原理基础小王是个工程师。小王是个工程师。8是个自然数。是个自然数。我去买花。我去买花。小丽和小华是朋友。小丽和小华是朋友。其

16、中，其中，“小王小王”、“工程师工程师”、“我我”、“花花”、“8”、“小丽小丽”、“小华小华”都是个体词，而都是个体词，而“是个是个工程师工程师”、“是个自然数是个自然数”、“去买去买”、“是朋友是朋友”都是谓词。显然前两个谓词表示的是事物的性质，都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词第三个谓词“去买去买”表示的一个动作也表示了主、表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词宾两个个体词的关系，最后一个谓词“是朋友是朋友”表表示两个个体词之间的关系。示两个个体词之间的关系。25谓词归结原理基础谓词归结原理基础一阶逻辑一阶逻辑 公式及其解释公式及其解释 个体常量：

17、个体常量：a,b,c 个体变量：个体变量：x,y,z 谓词符号：谓词符号：P,Q,R 量词符号：量词符号： , , 26谓词归结原理基础谓词归结原理基础 例如：（例如：（1）所有的人都是要死的。）所有的人都是要死的。 （2） 有的人活到一百岁以上。有的人活到一百岁以上。在个体域在个体域D为人类集合时，可符号化为为人类集合时，可符号化为：（1） xPxP( (x x) )，其中，其中P P( (x x) )表示表示x x是要死的。是要死的。（2） x Qx Q( (x x), ), 其中其中Q Q( (x x) )表示表示x x活到一百岁以上。活到一百岁以上。在个体域在个体域D是全总个体域时，是

18、全总个体域时，引入特殊谓词引入特殊谓词R R( (x x) )表示表示x x是人，可符号化为：是人，可符号化为：（1 1） x x（R R( (x x) ) P P( (x x) )）, , 其中，其中，R R( (x x) )表示表示x x是人；是人；P P( (x x) )表示表示x x是要死的。是要死的。（2 2） x x（R R( (x x) ) Q Q( (x x) )），），其中，其中，R R( (x x) )表示表示x x是人；是人；Q Q( (x x) )表示表示x x活到一百岁以上活到一百岁以上。 27谓词归结原理基础谓词归结原理基础量词否定等值式量词否定等值式：( ( x

19、x ） MM（x x） （ y y ） MM（y y） ( ( x x ） MM（x x） （ y y ） MM（y y）量词分配等值式量词分配等值式： ( ( x x ）( ( P P（x x） Q Q（x x）) () ( x x ） P P（x x） ( ( x x ） Q Q（x x） ( ( x x ）( ( P P（x x） Q Q（x x）) () ( x x ） P P（x x） ( ( x x ） Q Q（x x）消去量词等值式消去量词等值式：设个体域为有穷集合（设个体域为有穷集合（a a1 1, a, a2 2, a, an n） ( ( x x ） P P（x x） P

20、P（ a a1 1 ） P P（ a a2 2 ） P P（ a an n ） ( ( x x ）P P（x x） P P（ a a1 1 ） P P（ a a2 2 ） P P（ a an n ）28谓词归结原理基础谓词归结原理基础量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式： ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( (

21、x x ）( (Q Q P P（x x） ) ) Q Q ( ( x x ） P P（x x） ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( ( x x ）( (Q Q P P（x x） ) ) Q Q ( ( x x ） P P（x x）29谓词归结子句形谓词归结子句形( Skolem ( Skolem 标准形标准形) )SKOLE

22、MSKOLEM标准形标准形前束范式前束范式定义定义：说公式：说公式A A是一个前束范式，如果是一个前束范式，如果A A中的一切量词都位于该公式的最左边中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域（不含否定词），且这些量词的辖域都延伸到公式的末端。都延伸到公式的末端。 30谓词归结子句形谓词归结子句形( Skolem ( Skolem 标准形标准形) )即：即： 把所有的量词都提到前面去，然后把所有的量词都提到前面去，然后消掉所有量词消掉所有量词(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2)(Q)(Qn nx xn n)M(x)M(x1 1,x ,x2 2,x,x

23、n n) )约束变项换名规则：约束变项换名规则：(Qx(Qx ） MM（x x） （QyQy ） MM（y y） (Qx(Qx ） MM（x,zx,z） （QyQy ） MM（y,zy,z）31谓词归结子句形谓词归结子句形( Skolem ( Skolem 标准形标准形) )量词消去原则量词消去原则：消去存在量词消去存在量词“ ”，即将该量词约束的即将该量词约束的变量用任意常量（变量用任意常量（a,ba,b）或任意变量函数）或任意变量函数(f(x)(f(x)、g(y)g(y)）代替。）代替。略去任意量词略去任意量词“ ”。32谓词归结子句形谓词归结子句形( Skolem ( Skolem 标准

24、形标准形) )l l l l l l l l l l l l l l l l l l l l l l l l l lSKOLEMSKOLEM定理定理：谓词逻辑的任意公式都可以化为与之等谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。价的前束范式，但其前束范式不唯一。 SKOLEMSKOLEM标准形定义标准形定义：消去量词后的谓词公式。消去量词后的谓词公式。 注意注意：谓词公式：谓词公式G G的的SKOLEMSKOLEM标准形同标准形同G G并不等值并不等值。 33谓词归结子句形谓词归结子句形( Skolem ( Skolem 标准形标准形) )例例: :将下式化为将下式化为

25、Skolem标准形：标准形：( x)( y)P(a, x, y) ( x)( y)Q(y, b)R(x) 解：第一步，消去解：第一步，消去号，得：号，得：( x)( y)P(a, x, y) ( x) ( y)Q(y, b)R(x) 第二步，深入到量词内部，得：第二步，深入到量词内部，得：( x)( y)P(a, x, y) ( x)x) ( y)Q(y, b)R(x) 第三步，变元易名，得第三步，变元易名，得( x)( y)P(a, x, y) ( u) ( v)(Q(v, b) R(u) 第四步，存在量词左移，直至所有的量词移到前面，得：第四步，存在量词左移，直至所有的量词移到前面，得：

26、( x) ( y) ( u) ( v)P(a, x, y) (Q(v, b) R(u)由此得到前述范式由此得到前述范式34谓词归结子句形谓词归结子句形( Skolem ( Skolem 标准形标准形) )第五步，消去第五步，消去“ ”（存在量词），略去（存在量词），略去“ ”任意量任意量词词消去消去( y)，因为它左边只有，因为它左边只有( x)，所以使用，所以使用x的函数的函数f(x)代替之，这样得到：代替之，这样得到：( x)( z)( P(a, x, f(x) Q(z, b)R(x)消去消去( z)，同理使用，同理使用g(x)代替之，这样得到：代替之，这样得到：( x) ( P(a, x

27、, f(x) Q(g(x), b)R(x)则，略去全称变量，原式的则，略去全称变量，原式的Skolem标准形为：标准形为： P(a, x, f(x) Q(g(x), b)R(x) 35谓词归结子句形谓词归结子句形 子句与子句集子句与子句集 文字文字：不含任何连接词的谓词公式。：不含任何连接词的谓词公式。 子句子句：一些文字的析取（谓词的和）。：一些文字的析取（谓词的和）。 子句集子句集S S的求取的求取： G G SKOLEM SKOLEM标准形标准形 消去存在变量消去存在变量 以以“，”取代取代“”，并表示为集合形，并表示为集合形式式 。36谓词归结子句形谓词归结子句形 G是不可满足的是不可

28、满足的 S是不可满足的是不可满足的 G与与S不等价，但在不可满足的意义下是一不等价，但在不可满足的意义下是一致的。致的。 定理：定理：若若G是给定的公式，而是给定的公式，而S是相应的子句集，是相应的子句集，则则G是不可满足的是不可满足的 S是不可满足的。是不可满足的。 注意注意：G真不一定真不一定S真，而真，而S真必有真必有G真。真。即：即： S = = G37谓词归结子句形谓词归结子句形 G = GG = G1 1 G G2 2 G G3 3 G Gn n 的子句形的子句形G G的字句集可以分解成几个单独处理。的字句集可以分解成几个单独处理。 有有 S SG G = S = S1 1 U S

29、U S2 2 U S U S3 3 U U S U U Sn n则则S SG G 与与 S S1 1 U SU S2 2 U S U S3 3 U U S U U Sn n在不可满足在不可满足得意义上是一致的。得意义上是一致的。即即S SG G 不可满足不可满足 S S1 1 U SU S2 2 U S U S3 3 U U S U U Sn n不不可满足可满足38求取子句集例求取子句集例(1)例：对所有的例：对所有的x,y,z来说，如果来说，如果y是是x的父亲，的父亲，z又又是是y的父亲，则的父亲，则z是是x的祖父。又知每个人都有的祖父。又知每个人都有父亲，试问对某个人来说谁是他的祖父？父亲

30、，试问对某个人来说谁是他的祖父？求：用一阶逻辑表示这个问题，并建立子句集。求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：解：这里我们首先引入谓词：P(x, y) 表示表示x是是y的父亲的父亲Q(x, y) 表示表示x是是y的祖父的祖父ANS(x) 表示问题的解答表示问题的解答39求取子句集例求取子句集例(2)对于第一个条件对于第一个条件，“如果如果x是是y 的父亲，的父亲， y又是又是z 的父亲，则的父亲，则x是是z 的的祖父祖父”，一阶逻辑表达式如下：，一阶逻辑表达式如下：A1：( x)( y)( z)(P(x, y)P(y, z)Q(x, z)S A1：P(x ,y)

31、P(y, z)Q(x, z)对于第二个条件对于第二个条件：“每个人都有父亲每个人都有父亲”，一阶逻辑表达式：，一阶逻辑表达式：A2：( y)( x)P(x, y)S A2：P(f(y), y)对于结论：对于结论：某个人是他的祖父某个人是他的祖父B：( x)( y)Q(x, y)否定后得到子句：否定后得到子句： （ ( x)( y)Q(x, y)） ANS(x)SB：Q(x, y)ANS(x)则得到的相应的子句集为：则得到的相应的子句集为： S A1，S A2，SB 40第三章第三章 归结推理方法归结推理方法 概述概述 命题逻辑的归结法命题逻辑的归结法 谓词归结子句形谓词归结子句形 归结原理归结

32、原理 归结过程的策略控制归结过程的策略控制 Herbrand定理定理41归结原理归结原理 归结原理正确性的根本在于，找到归结原理正确性的根本在于，找到矛盾可以肯定不真。矛盾可以肯定不真。 方法：方法： 和命题逻辑一样。和命题逻辑一样。 但由于有函数，所以要考虑但由于有函数，所以要考虑合一合一和和置置换换。 42 置置 换换置换置换：可以简单的理解为是在一个谓词公式中用置换项去置：可以简单的理解为是在一个谓词公式中用置换项去置换变量。换变量。定义定义：置换是形如置换是形如t1/x1, t2/x2, , tn/xn的有限集合。其中，的有限集合。其中，x1, x2, , xn是互不相同的变量，是互不

33、相同的变量，t1, t2, , tn是不同于是不同于xi的项（的项（常常量、变量、函数量、变量、函数）；）；ti/xi表示用表示用ti置换置换xi，并且要求，并且要求ti与与xi不能不能相同，而且相同，而且xi不能循环地出现在另一个不能循环地出现在另一个ti中。中。在谓词逻辑的归结过程中，寻找项之间合适的变量置换使表在谓词逻辑的归结过程中，寻找项之间合适的变量置换使表达式一致是一个很重要的过程，这个过程称为达式一致是一个很重要的过程，这个过程称为合一合一。 43例例a/x，c/y，f(b)/z是一个置换是一个置换g(y)/x，f(x)/y不是一个置换。不是一个置换。 原因原因：它在：它在x和和

34、y之间出现了循环置换现象。置换的目的是要之间出现了循环置换现象。置换的目的是要将某些变量用另外的变量、常量或函数取代，使其不在公式将某些变量用另外的变量、常量或函数取代，使其不在公式中出现。这里用中出现。这里用g(y)置换置换x, 用用f(g(y)置换置换y,既没有消去既没有消去x,也没也没有消去有消去y. 若改为若改为 g(a)/x，f(x)/y 就可以了。就可以了。44置换的合成置换的合成 设设 t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , un/yn，是两个置换。，是两个置换。 则则 与与 的合成也是一个置换，记作的合成也是一个置换，记作 。它是从集合。它

35、是从集合t1 /x1, t2 /x2, , tn /xn, u1/y1, u2/y2, , un/yn 中删去以下两种元素：中删去以下两种元素： 当当ti =xi时，删去时，删去ti /xi (i = 1, 2, , n); 当当yi x1,x2, , xn时，删去时，删去uj/yj (j = 1, 2, , m)最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。 合成即是对合成即是对ti先做先做 置换然后再做置换然后再做 置换，置换置换，置换xi45置换的合成置换的合成 例：例：设：设： f(y)/x, z/y， a/x, b/y, y/z，求，求 与与 的合成。的合成。解：先求出集合

36、解：先求出集合f(b/y)/x, (y/z)/y, a/x, b/y, y/zf(b)/x, y/y, a/x, b/y, y/z其中，其中，f(b)/x中的中的f(b)是置换是置换 作用于作用于f(y)的结果；的结果；y/y中中的的y是置换是置换 作用于作用于z的结果。在该集合中，的结果。在该集合中，y/y满足定义满足定义中的条件中的条件i，需要删除，需要删除；a/x，b/y满足定义中的条件满足定义中的条件ii，也需要删除。最后得也需要删除。最后得 f(b)/x，y/z t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , un/yn， =t1 /x1, t2 /x2

37、, , tn /xn, u1/y1, u2/y2, , un/yn 当当titi =xi=xi时，删去时，删去titi /xi (i = 1, 2, , /xi (i = 1, 2, , n);n);当当yiyi x1,x2, , xnx1,x2, , xn时，删去时，删去uj/yj (j uj/yj (j = 1, 2, , m)= 1, 2, , m)46合一合一 合一合一可以简单地理解为可以简单地理解为“寻找相对变量的置换，使寻找相对变量的置换，使两个谓词公式一致两个谓词公式一致”。 定义定义：设有公式集：设有公式集FF1，F2，Fn，若存在一，若存在一个置换个置换 ，可使，可使F1 F

38、2 = Fn ，则称，则称 是是F的一个的一个合一。同时称合一。同时称F1，F2，. ，Fn是可合一的。是可合一的。 例：例：设有公式集设有公式集FP(x, y, f(y), P(a,g(x),z)，则，则 a/x, g(a)/y, f(g(a)/z是它的一个合一。是它的一个合一。 注意：一般说来，一个公式集的合一不是唯一的。注意：一般说来，一个公式集的合一不是唯一的。 47 例例1 1：设有置换设有置换s=z/x, A/ys=z/x, A/y，则：则：Px, f(y), Bs=Pz, f(A), BPx, f(y), Bs=Pz, f(A), B。这里这里x x被换成了被换成了z z，y y

39、被换成了被换成了A A。设有公式的集合设有公式的集合Ei(i=1, 2, ., m)Ei(i=1, 2, ., m)，如果存在一个置换，如果存在一个置换s s，使得这使得这m m个公式被施以个公式被施以s s以后，变得完全一样了，则称这以后，变得完全一样了，则称这m m个公个公式是可合一的，置换式是可合一的，置换s s是它们的合一者。是它们的合一者。48例例2 2：设有公式集设有公式集P(x, f(y), B), P(z, f(B), B)P(x, f(y), B), P(z, f(B), B)和置换和置换s1=A/x, s1=A/x, B/y, A/zB/y, A/z，由于：，由于：P(x,

40、 f(y), B)s=P(A, f(B), B)P(x, f(y), B)s=P(A, f(B), B)P(z, f(B), B)s=P(A, f(B), B)P(z, f(B), B)s=P(A, f(B), B)所以公式集所以公式集P(x, f(y), B), P(z, f(B), B)P(x, f(y), B), P(z, f(B), B)是可合一的，是可合一的，置换置换s1=A/x, B/y, A/zs1=A/x, B/y, A/z是它们的合一者。是它们的合一者。49 若存在一个置换若存在一个置换s使得表达式集使得表达式集Ei中每个元素经置换后的例中每个元素经置换后的例有：有：E1s=

41、E2s=E3s= ，则称表达式集，则称表达式集Ei是可合一的，这个是可合一的，这个置换置换s称作称作Ei的合一者。的合一者。 在归结法中主要是处理可合一的子句集，例如有子句集在归结法中主要是处理可合一的子句集，例如有子句集: P（x，f（y），），B），），P（x，f（B），），B），若对两个子句，若对两个子句作置换作置换sA/x，B/y，则可得，则可得P（A，f（B），），B），因而该，因而该子句集是可合一的。子句集是可合一的。 仅仅从合一的角度看，仅仅从合一的角度看，s并不是最简单的合一者，因为还存在并不是最简单的合一者，因为还存在另一个另一个s1B/y的合一者，使子句集合一为的合一者，使

42、子句集合一为Px，f（B），），B。因此通常还要求找的是最一般或最普通的合一者（。因此通常还要求找的是最一般或最普通的合一者（most general unifier）g，记为，记为mgu g。50 任一合一者任一合一者s与与g之间的关系是之间的关系是： 存在一个置换存在一个置换s，使得，使得EisEigs。再比较上例的两个合一。再比较上例的两个合一者，有者，有A/x，B/yB/yA/x，因此，因此mgu gB/y。可见。可见mgu g的置换限制最少，所产生的例更一般化，这有利于归结过程的置换限制最少，所产生的例更一般化，这有利于归结过程的灵活使用。的灵活使用。 51UNIFY算法算法 UNI

43、FY算法不仅可以判断两个公式是否可合一，而且在可合算法不仅可以判断两个公式是否可合一，而且在可合一的情况下，给出它们的一的情况下，给出它们的mgu。该算法为了表述上的方便，。该算法为了表述上的方便，假定谓词是以表的形式表示的。假定谓词是以表的形式表示的。 如谓词如谓词P(x, f(y), B)表示为表示为(P x (f y) B)。 UNIFY算法的基本思想是，从左向右按位置扫描两个谓词的算法的基本思想是，从左向右按位置扫描两个谓词的每一个对应部分，如果二者一致，则转入下一项。如果不一每一个对应部分，如果二者一致，则转入下一项。如果不一致，则看是否存在一个置换，使得对应项经过置换后是一致致，则

44、看是否存在一个置换，使得对应项经过置换后是一致的。如果不存在这样的置换，则两个公式是不可合一的。如的。如果不存在这样的置换，则两个公式是不可合一的。如果两个谓词的对应部分都是一致的，或者经置换后是一致的，果两个谓词的对应部分都是一致的，或者经置换后是一致的，则两个公式是可合一的，这些置换的合成是它们的合一者。则两个公式是可合一的，这些置换的合成是它们的合一者。如果当两个对应项都是变量时，置换选作用一个变量代替另如果当两个对应项都是变量时，置换选作用一个变量代替另一个变量，则这样得到的合一者是一个变量，则这样得到的合一者是mgu。52 例：例：公式集如下：公式集如下：P(x, x, z), P(

45、f(y), f(B), y)用表的形式表示为：用表的形式表示为：E1=(P x x z)E2=(P (f y) (f B) y) 从左向右按顺序扫描两个谓词。从左向右按顺序扫描两个谓词。E1和和E2的第一项都是的第一项都是P，是，是一致的，转入第二项。一致的，转入第二项。E1的第二项是的第二项是x，E2的第二项是的第二项是(f y)，二者不一致。由于其中一个是变量，可以进行置换。选置换二者不一致。由于其中一个是变量，可以进行置换。选置换(f y)/x使得二者成为一致的。该置换同时作用于使得二者成为一致的。该置换同时作用于E1的第三项的第三项x。这样有：。这样有：E1= (P (f y) (f

46、y) z)E2= (P (f y) (f B) B)53 E1= (P (f y) (f y) z)E2= (P (f y) (f B) B)继续看第三项。继续看第三项。E1的第三项是的第三项是(f y)，E2的第三项是的第三项是(f, B)。由于两个都是表，需要进入表的内部进行比较。由于两个都是表，需要进入表的内部进行比较。 在表的内部，第一项均是在表的内部，第一项均是f，是一致的。第二项一个是变量，是一致的。第二项一个是变量y，一个是常量，一个是常量B。选置换。选置换B/y使二者成为一致的。该置换使二者成为一致的。该置换不仅使得两个公式中的所有不仅使得两个公式中的所有y都被替换为了都被替换

47、为了B，而且也作用，而且也作用于前一个置换于前一个置换(f y)/x，使得该置换变成了，使得该置换变成了(f B)/x。这样有：。这样有：E1= (P (f B) (f B) z)E2= (P (f B) (f B) B)54 E1= (P (f B) (f B) z)E2= (P (f B) (f B) B) E1的第四项是变量的第四项是变量z，E2的第四项是常量的第四项是常量B，选置换，选置换B/z使得二者成为一致的。有：使得二者成为一致的。有：E1= (P (f B) (f B) B)E2= (P (f B) (f B) B)至此，至此，E1和和E2是完全一样的了，说明是完全一样的了，说

48、明E1和和E2是可合一的。是可合一的。其合一者是这一过程中几个置换的并其合一者是这一过程中几个置换的并(f B)/x, B/y, B/z，该合一者也是该合一者也是mgu。55 如果这一过程中有某一个对应项是不能置换为一样的，则如果这一过程中有某一个对应项是不能置换为一样的，则说明两个公式不可合一。如该例如果是：说明两个公式不可合一。如该例如果是：E1=(P x x A)E2=(P (f y) (f B) y)则是不可合一的。因为经过几步变换后有：则是不可合一的。因为经过几步变换后有：E1= (P (f B) (f B) A)E2= (P (f B) (f B) B)此时此时E1的第四项是常量的

49、第四项是常量A，而，而E2的第四项是常量的第四项是常量B，二者，二者不一致，而且都是常量，无法置换。因此两个公式不可合不一致，而且都是常量，无法置换。因此两个公式不可合一。一。 56P105 例例3.16 W=P(a,x,f(g(y),P(z,f(a),f(u), 其中其中F1=P(a,x,f(g(y), F2=P(z,f(a),f(u), 求求F1和和F2 的的mgu57谓词逻辑的归结过程谓词逻辑的归结过程 对于谓词逻辑来说，可以这样判断两个子句是否可进行对于谓词逻辑来说，可以这样判断两个子句是否可进行归结，及其归结式是什么。归结，及其归结式是什么。对于子句对于子句C1L1和和C2L2，如果

50、，如果L1与与L2可合一，可合一，且且s是其合一者，则是其合一者，则(C1C2)s是其归结式。其中是其归结式。其中L1、L2是是单文字。事实上单文字。事实上L1、L2中有一个含有否定符，所以对另一中有一个含有否定符，所以对另一个加上否定符后，才能判断它们是否可合一。个加上否定符后，才能判断它们是否可合一。 58 设设C1和和C2为两个不同的子句，子句中的变量已标准化。为两个不同的子句，子句中的变量已标准化。我们采用文字集的形式来表示子句（即文字之间理解为析我们采用文字集的形式来表示子句（即文字之间理解为析取关系），则有取关系），则有 C1C1i（i1，2，n），）， C2C2j（j1，2，m）

51、再设再设L1k和和L2k分别为分别为C1和和C2的两个子集。的两个子集。若若L1k和和L2k的并集存在一个的并集存在一个mgu s，则两个子句的归，则两个子句的归结式为结式为 CC1iL1ksC2jL2ks可以看出对这两个子句进行归结时，由于有多种方式选取可以看出对这两个子句进行归结时，由于有多种方式选取L1k和和L2k，因此归结式不是唯一的。，因此归结式不是唯一的。59 例：例： C1P（x，f（A）P（x，f（y）Q（y）C2P（z，f（A）Q（z） 取取L11P（x，f（A），），L21P（z，f（A）存在）存在 sz/x , 使使L11和和L21合一，所以归结式为合一，所以归结式为 P

52、（z，f（y）Q（y）Q（z） 取取L11P（x，f（y），），L21P（z，f（A） 则则 s（z/x，A/y），），归结式为归结式为 Q（A）Q（z） 取取L11Q（y），），L21Q（z） 则则 sy/z，归结式为，归结式为 P（x，f（A）P（x，f（y）P（y，f（A）60 这个例子说明，选择不同文字对做归结时这个例子说明，选择不同文字对做归结时可得到不同的归结式，但由于都是用最一可得到不同的归结式，但由于都是用最一般的合一者作置换，因此这些归结式仍是般的合一者作置换，因此这些归结式仍是最一般的归结式。就是说，如果对某个文最一般的归结式。就是说，如果对某个文字不是用字不是用mgu来合

53、一，那么得到的归结式来合一，那么得到的归结式比最一般的归结式则有较多的限制。实际比最一般的归结式则有较多的限制。实际上我们总是希望用最一般的归结式，以增上我们总是希望用最一般的归结式，以增加归结过程的灵活性。加归结过程的灵活性。61归结原理归结原理归结的归结的注意事项注意事项：n谓词的一致性谓词的一致性，名称不一致的谓词，如，名称不一致的谓词，如 P()P()与与Q()Q()， 不可以不可以n常量的一致性常量的一致性，含有不同常量的谓词，如，含有不同常量的谓词，如P(a, )P(a, )与与P(b,.)P(b,.)， 不可以不可以如果是常量与变量，如果是常量与变量，P(a, .)P(a, .)

54、与与P(x, )P(x, )， 可以可以3. 3. 变量与函数，变量与函数，P(x, x, .)P(x, x, .)与与P(x, f(x), )P(x, f(x), )， 不可以不可以, , 因为不能进行因为不能进行x/f(x)x/f(x)的置换；的置换； 但但P(x, x, .)P(x, x, .)与与P(x, f(y), )P(x, f(y), )，可以通过对两式分别做，可以通过对两式分别做 f(y)/xf(y)/x置换，而后进行归结。置换，而后进行归结。n4. 4. 不能同时消去两个互补对，不能同时消去两个互补对，PQPQ与与PPQ Q的空，不可以的空，不可以1. 1.5. 5. 先进行

55、内部简化，再进行置换与合并。先进行内部简化，再进行置换与合并。 62例：设例：设C1=P(y)P(f(x)Q(g(x),C1=P(y)P(f(x)Q(g(x), C2= C2=P(f(g(a)Q(b),P(f(g(a)Q(b), 求求C1C1和和C2C2的归结式。的归结式。解：对解：对C1, C1, 取最一般合一取最一般合一 =f(x)/y 得得C1的因子的因子 C1 =P(f(x) Q(g(x)Q(g(x) C1 C1与与C2C2归结，归结， 2=f(x)/y,g(a)/x得归结式：得归结式： Q(g(g(a)Q(b)Q(g(g(a)Q(b)63归结原理归结原理 归结的过程归结的过程写出谓词

56、关系公式写出谓词关系公式 用反演法写出谓词表达式用反演法写出谓词表达式 SKOLEMSKOLEM标准形标准形 子句集子句集S S 对对S S中可归结的子句做归结中可归结的子句做归结 归结式仍放入归结式仍放入S S中，反复归结过程中，反复归结过程 得到空子句得到空子句 得证得证64例题例题“快乐学生快乐学生”问题问题 假设任何通过计算机考试并获奖的人都假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：幸运的，任何幸运的人都能获奖。求证：张是快

57、乐的。张是快乐的。65例题例题“快乐学生快乐学生”问题问题 解：先将问题用谓词表示如下：解：先将问题用谓词表示如下： R1:“R1:“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考试并获奖的人都是快乐的”( ( x)(Pass(x, computer)Win(x, prize)Happy(x)x)(Pass(x, computer)Win(x, prize)Happy(x) R2:“R2:“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”( ( x)(x)( y)(Study(x)Lucky(x)Pass(x, y)y)(Study(x)Lucky(x)P

58、ass(x, y) R3:“R3:“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)Study(zhang)Lucky(zhang) R4:“R4:“任何幸运的人都能获奖任何幸运的人都能获奖”( ( x)(Luck(x)Win(x,prize)x)(Luck(x)Win(x,prize) 结论：结论：“张是快乐的张是快乐的”的否定的否定 Happy(zhang)Happy(zhang)66例题例题“快乐学生快乐学生”问题问题由由R1及逻辑转换公式及逻辑转换公式:PWH = （PW） H ，可得，可得 (1)Pass(x, computer)Win(

59、x, prize)Happy(x)由由R2： (2)Study(y)Pass(y,z) (3)Lucky(u)Pass(u,v)由由R3： (4)Study(zhang) (5)Lucky(zhang)由由R4： (6)Lucky(w)Win(w，prize)由结论由结论：(7)Happy(zhang) （结论的否定）（结论的否定）(8)Pass(w, computer)Happy(w)Luck(w) (1)(6)，w/x(9)Pass(zhang, computer)Lucky(zhang) (8)(7)，zhang/w(10) Pass(zhang, computer) (9)(5)(11

60、) Lucky(zhang) (10)(3)，zhang/u, computer/v(12) (11)(5) 67归结原理归结原理 归结法的实质归结法的实质 归结法是仅有一条推理规则的推理方法。归结法是仅有一条推理规则的推理方法。 归结的过程是一个语义树倒塌的过程。归结的过程是一个语义树倒塌的过程。 归结法的问题归结法的问题 子句中有等号或不等号时，完备性不成立。子句中有等号或不等号时，完备性不成立。 Herbrand Herbrand定理的不实用性引出了可实用定理的不实用性引出了可实用的归结法。的归结法。68第三章第三章 归结推理方法归结推理方法 概述概述 命题逻辑的归结法命题逻辑的归结法