人工智能 第3章 谓词逻辑与归结原理

1、 智力题：五个房子，五个人，五种宠物，智力题：五个房子，五个人，五种宠物， 五种饮料，五种香烟五种饮料，五种香烟 1、有5栋5种颜色的房子 2、每一位房子的主人国籍都不同 3、这5个人只喝一个牌子的饮料，只抽一 个牌子的香烟，只养一种宠物 4、没有人有相同的宠物，抽相同牌子的香 烟，喝相同的饮料 谁养鱼？谁养鱼？ 已知条件：已知条件： 1、英国人住在红房子里 2、瑞典人养了一条狗 3、丹麦人喝茶 4、绿房子在白房子左边 5、绿房子主人喝咖啡 6、抽PALLMALL烟的人养了一只鸟 7、黄房子主人抽DUNHILL烟 8、住在中间那间房子的人喝牛奶 9、挪威人住在第一间房子 10、抽混合烟的人住在

2、养猫人的旁边 11、养马人住在DUNHILL烟的人旁边 12、抽BLUEMASTER烟的人喝啤酒 13、德国人抽PRINCE烟 14、挪威人住在蓝房子旁边 15、抽混合烟的人的邻居喝矿泉水 推理的一般形式 已知：实事一，实事二， 如果实事一，那么结论一； 如果实事二，那么结论二； 得到：结论一，结论二， 如果将实事和规则抽象出来，不涉及具体内容， 借助一些符号来表示，推理过程可形式化为： P：某已知实事 PQ：如果P，则Q 结论：Q 逻辑 经典逻辑： 命题逻辑、谓词逻辑 非经典逻辑： 不确定性推理、非单调性推理 第3章 谓词逻辑与归结原理 归结归结 推理推理 命题命题 逻辑逻辑 谓词谓词 逻辑

3、逻辑 Skolem标准形、标准形、 子句集子句集 基本基本 概念概念 谓词逻辑谓词逻辑 归结原理归结原理 合一和置换、合一和置换、 控制策略控制策略 数理数理 逻辑逻辑 命题逻辑命题逻辑 归结归结 Herbrand 定理定理 第3章 谓词逻辑与归结原理 命题逻辑命题逻辑 谓词逻辑基础 谓词逻辑归结原理 Herbrand定理 命题例子 命题：命题：能判断真假（不是既真又假）的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如： 1 1+1=2 2 雪是黑色的。 3 北京是中国的首都。 4 到冥王星去渡假。 例如： 1 快点走吧！ 2 到那去？ 3 x+y10 命题公式命题公式 基本联结

4、词 否定、合取、析取、蕴含、等价否定、合取、析取、蕴含、等价 命题公式的联结词的组合仍然是命题公式 合取式：p与q，记做p q 析取式：p或q，记做p q 蕴含式：如果p则q，记做p q 等价式：p当且仅当q，记做p q 将陈述句转化成命题公式 如：设“下雨”为p，“骑车上班”为q， 1“只要不下雨，我骑自行车上班”。p 是 q 的充分条件， 因而，可得命题公式： p q 2“只有不下雨，我才骑自行车上班”。p 是 q的必要条件， 因而，可得命题公式：q p 1、认真分析蕴含式的前件和后件的关系、认真分析蕴含式的前件和后件的关系 2、注意同一命题的各种等价说法、注意同一命题的各种等价说法 1

5、“如果我进城我就去看你，除非我很累。” 设：p，我进城，q，去看你，r，我很累。 则有命题公式：r (p q)。 2“应届高中生，得过数学或物理竞赛的一等 奖，保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学， r，是得过数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p ( r t ) q。 给出事件的命题公式的基本步骤：给出事件的命题公式的基本步骤： 符号化、适当联结词符号化、适当联结词 几个概念 命题公式的解释 真值表 公式的分类 若A无成假赋值，则称A为重言式或永真式 若A无成真赋值，则称A为矛盾式或永假式 若A至少有一个成真赋值，则称A为可满足的 等值式等值式 基

6、本等值式基本等值式 交换律：A B B A A B B A 结合律： (AB) C A(BC) (A B) C A (B C) 分配律： A(B C) (AB) (A C) A (B C) (A B) (A C) 双重否定律： A A 等幂律： A A A； A A A 若等价式若等价式A B 是重言式，则称是重言式，则称A和和B等值，记作等值，记作A B 摩根律：(AB) A B (A B) A B 吸收律：A(A B) A A (AB) A 同一律： A0 A ；A 1 A 零律： A1 1； A 0 0 排中律： AA 1 矛盾律： A A 0 蕴含等值式：A B AB 等价等值式：A

7、B ( A B ) ( B A ) 假言易位式: A B B A 等价否定等值式： A B A B 归谬论：归谬论： (A B) (A B) A 等值演算 置换规则 联结词的优先顺序 范范 式式 简单合取范式 简单析取范式 合取范式：仅由有限个简单析取式组成的合取式。 析取范式：仅由有限个简单合取式组成的析取式。 主合取范式 主析取范式 范式存在定理 求合取范式的基本步骤 例例3.1 例例3.2 命题逻辑的意义命题逻辑的意义 给计算机、智能体建模的过程就是对知识进行描给计算机、智能体建模的过程就是对知识进行描 述，应用知识进行推理得到结论，并将结论用人述，应用知识进行推理得到结论，并将结论用人

8、 能够接受理解的形式显示的过程。能够接受理解的形式显示的过程。 知识可以用公式表示为对特征值的约定。知识可以用公式表示为对特征值的约定。 知识用特征描述后可以用于推理。知识用特征描述后可以用于推理。 命题逻辑有数理逻辑作为坚实的理论支柱，同时命题逻辑有数理逻辑作为坚实的理论支柱，同时 又是谓词逻辑的基础，对于人工智能知识表示与又是谓词逻辑的基础，对于人工智能知识表示与 推理研究有着重要的意义。推理研究有着重要的意义。 命题逻辑的推理规则命题逻辑的推理规则 逻辑结论 推理规则 常用推理定律 证明中常用的推理规则 例例3.3 例例3.4 命题逻辑的归结法命题逻辑的归结法 归谬法归谬法 例：例： 命

9、题： A1、A2、A3 和 B 求证： A1 A2 A3成立，则B成立， 即：A1 A2 A3 B 反证法：证明A1 A2 A3 B 是矛盾式 （永假式） 归结原理归结原理 依赖于一个单一的规则： 如pq和qr都为真，则pr为真。 基本思想：将待证明逻辑公式的结论，通过等值 公式转换成附加前提，再证明该逻辑公式是不可 满足的。 子句子句 建立子句集子句集 合取范式：命题、命题和的与， 如： P（PQ）（PQ） 子句集S：合取范式形式下的子命题（元 素）的集合 例：命题公式：P（PQ）（PQ） 子句集 S：S = P, PQ, PQ 例例3.5 例例3.6 归结式归结式 消除互补对，求新子句得到

10、归结式。 如子句：C1, C2 归结式：C12 = C1 C2 C1, C2为C12的亲本子句。 注意：C1C2 C12 ， 反之成立。 归结式的性质归结式的性质 : :归结式是亲本子句的逻辑结论。归结式是亲本子句的逻辑结论。 归结法证明过程归结法证明过程 归结方法推理过程步骤： 1、建立待归结命题公式，根据反证法将所求证的问 题转化为命题公式，求证其是矛盾式 2、求取合取范式 3、建立子句集 4、对子句集中的子句使用归结推理规则 归结式作为新子句参加归结 归结式为空子句 ，停止 S是不可满足的（矛盾），原命题成立。 （证明完毕） 命题逻辑归结例题命题逻辑归结例题 例题3.7：证明公式：(P

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

12、逻辑基础 一阶谓词逻辑中，简单命题被分解成个体 词和谓词两部分。 基本概念基本概念 个体词：个体词：表示主语的词 谓词：谓词：刻画个体性质或个体之间关系的词 量词：量词：表示数量的词 例子 小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中：“小王”、“工程师”、“我”、“花”、“8”、 “小丽”、“小华”都是个体词，而“是个工程师”、“是 个自然数”、“去买”、“是朋友”都是谓词。 显然前两个谓词表示的是事物的性质，第三个谓词“去买” 表示的一个动作也表示了主、宾两个个体词的关系，最后一 个谓词“是朋友”表示两个个体词之间的关系。 基本定义基本定义 个体常量：a,b,c

13、个体变量：x,y,z 个体域：D 谓词常量：P,Q,R 谓词变量：P(x),Q(x,y),R(x,b) n元谓词：P(x1,x2,xn) 一阶谓词 任意量词： 存在量词： 例子 例如：（1）所有的人都是要死的。 （2）有的人活到一百岁以上。 在个体域个体域D为人类集合为人类集合时，可符号化为： （1）xP(x)，其中P(x)表示x是要死的。 （2）xQ(x), 其中Q(x)表示x活到一百岁以上。 在个体域个体域D是全总个体域是全总个体域时， 引入特殊谓词R(x)表示x是人，可符号化为： （1）x（R(x) P(x)）, 其中，R(x)表示x是人；P(x)表示x是要死的。 （2）x（R(x) Q

14、(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。 使用量词时需注意的事项使用量词时需注意的事项 一阶谓词公式一阶谓词公式 原子公式 谓词公式 指导变量 辖域 约束出现 自由出现 谓词公式：谓词公式： x x（P(x)P(x) yQ(x,y)yQ(x,y)） 换名规则：换名规则：将量词辖域中出现的某个约束 出现的个体变量及相应的指导变量，改成 另一个此辖域中未曾出现过的个体变量符 号，公式中其余部分不变。 替代规则：替代规则：对某自由出现的个体变量用与 原公式中所有个体变量符号不同的变量符 号去替代，且处处替代。 换名规则、替代规则在谓词逻辑归结的子句集求 取过程中不可缺少，

15、只有进行适当的换名和替代 才能够正确得到前束范式和Skolem标准型。 谓词公式的解释谓词公式的解释 对谓词公式中的各种变量制定特殊的常量 去替代，就构成了一个谓词的解释。 在使用一个解释I，解释一个谓词公式A时， 将A中的个体常量用I中特定常量代替，函数 和谓词用I中特定函数和谓词代替。 解释是一个集合的概念 解释的例子解释的例子 例3.8，给定解释I如下： 个体域DI=2，3； 函数f(x)为f(2)=3,f(3)=2； 谓词P(x)为P(2)=0,P(3)=1； Q(x,y)为Q(i,j)=1,i,j=2,3； R(x,y)为 R(2,2)=R(3,3)=1,R(2,3)=R(3,2)=

16、0。 求（1）在解释I下，x(P(f(x)Q(x,f(x)的真值。 （2）在解释I下， xyR(x,y)的真值。 解： （1） x(P(f(x)Q(x,f(x)的真值为 = (P(f(2)Q(2,f(2)(P(f(3)Q(3,f(3) = (P(3)Q(2,3)(P(2)Q(3,2) = (11)(01) = 1 （2） xyR(x,y)的真值为 = (R(2,2)R(2,3) (R(3,3)R(3,2) = (11) = 1 约束出现的变量取值关系与量词的性质有关。约束出现的变量取值关系与量词的性质有关。 谓词公式是永真的 谓词公式是不可满足的 谓词逻辑的归结推理方法，即归结原理， 就是将对

17、谓词公式的正确性推理证明转换 成为该谓词公式的不可满足性证明 谓词演算等值公式谓词演算等值公式 约束变项换名规则： (Qx ） P（x） （Qy ） P（y） (Qx ） P（x,z） （Qy ） P（y,z） 量词否定等值式： ( x ） P（x） （ y ） P（y） ( x ） P（x） （ y ） P（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

18、 ） Q Q（x x） 消去量词等值式：设个体域为有穷集合（a1, a2, an） （ x ） P（x） P（ a1 ） P（ a2 ） P（ an ） （ x ）P（x） P（ a1 ） P（ a2 ） P（ an ） 谓词演算等值公式谓词演算等值公式 量词辖域收缩与扩张等值式： ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( x ）(Q P（x）) Q ( x ） P（x） ( x ）( P（x） Q) ( x ） P（x

19、） Q ( x ）( P（x） Q) ( x ） P（x） Q ( ( x x ）( ( P P（x x） Q Q) () ( x x ） P P（x x） Q Q ( x ）(Q P（x） ) Q ( x ） P（x） 前束范式 谓词公式P如果具有以下形式，即把所有的 量词都提到最左端去 (Q1X1)(Q2X2)(QnXn) P(x1,x2,xn) 称为P的前束范式 任何谓词公式的前束范式都是存在的 前束范式不唯一 前束范式例子 例例3.9 求(xP(x,y)yQ(y)xR(x,y)的 前束范式 解： (xP(x,y)yQ(y)xR(x,y) (xP(x,z)yQ(y)xR(x,z) (xP

20、(x,z)yQ(y)tR(t,z) x(P(x,z)yQ(y)tR(t,z) xy(P(x,z)Q(y)tR(t,z) xy(P(x,z)Q(y)tR(t,z) xyt(P(x,z)Q(y)R(t,z) 谓词推理谓词推理 量词的削去和引入的基本思想是任意量词 可以削去，用变量和常量表示，存在量词 可以用常量表示。 削去和引入量词的规则：削去和引入量词的规则： （1）xP(x) = P(y) , xP(x) = P(c) （2） xP(x) = P(c) （3）P(y) = xP(x) （4）P(c) = xP(x) 谓词推理例子 例例3.10 20世纪70年代的漫画都是日本漫画 家创作的，这幅

21、漫画是20世纪70年代的作 品，因此，这幅漫画是日本漫画家的作品。 解： 设P(X)：20世纪70年代的漫画； Q(y)：日本漫画家的作品； a：一幅漫画。 前提： xP(x) Q(x)，P(a) 结论：Q(a) 证明： xP(x) Q(x) P(a) P(a) Q(a) Q(a) 以上推理为演绎推理 演绎推理的局限性 谓词知识表示谓词知识表示 谓词可以用来表达人工智能需要处理 的知识。 谓词逻辑的基本组成部分是谓词符号、 变量符号、函数符号和常量符号，并 用括号隔开，以表示论域内的关系。 例如：INROOM(ROBOT,r1) PLAY(Zhang，Li，tennis) 用连接词构成合式公式

22、用连接词构成合式公式 INROOM(ROBOT,r2) LIKE(I,MUSIC) LIKE(I,PAINING) PLAYS(LIMING,BASKETBALL) PLAYS(LIMING,FOOTBALL) OWNS(HEPING,BOOK) COLOR(BOOK,BLUE) (x)ROBOT(X)COLOR(x,GRAY) (x)INROOM(x,HOUSE1) 谓词表示知识的步骤谓词表示知识的步骤 用对象、函数、关系将知识概念化 构造谓词表达式 写出概念化知识的谓词公式 谓词逻辑法比命题逻辑法更加细致 谓词逻辑法应用广泛的原因 逻辑表示法的缺点 机器人搬弄积木块问题的谓词逻辑表示机器人

23、搬弄积木块问题的谓词逻辑表示 例例3.11 一个房间里，有一个机器人Robot， 一个积木块Box，两个桌子A和B，开始时 机器人Robot在桌子A旁边，两手空空的， 桌子A上放着积木块Box，桌子B上是空的， Robot将Box从桌子A转移到桌子B上，并回 到桌子A旁边。 怎样用逻辑法描述从初始状态到目标状态 的机器人操作过程？ 第一步：定义谓词如下第一步：定义谓词如下 Table(x)：x是桌子 EmptyHanded(x)：x双手是空的 At(x,y)：x在y旁边 Holds(y,w)：y拿着w On(w,x)：w在x上 EmptyTable(x)：桌子x上是空的 第二步：题目涉及的个体

24、定义为第二步：题目涉及的个体定义为 机器人Robot、积木块Box、桌子A、桌子B 第三步：描述问题的初始状态和目标状态第三步：描述问题的初始状态和目标状态 初始状态：EmptyHanded(Robot) On(Box,A) Table(A) Table(B) EmptyTable(B) 目标状态：EmptyHanded(Robot) On(Box,B) Table(A) Table(B) EmptyTable(A) 第四步：对问题求解。第四步：对问题求解。实际上是寻找一组 机器人可进行的操作，实现一个由初始状 态到目标状态的机器人操作过程 机器人要执行的动作有： GOTO(x,y)：从x出走

25、到y处 PICK_UP(x)：在x处拿起积木块 SET_DOWN(x)：在x处放下积木块 可进行的操作一般分为先决条件和动作两部 分，这3个操作表示如下： （1）GOTO(x,y) 条件：At(Robot,x) 动作：删除 At(Robot,x) 增加 At(Robot,y) （2）PICK_UP(x) 条件：On(Box,x)Table(x)At(Robot,x)EmptyHanded(Robot) 动作：删除 On(Box,x)EmptyHanded(Robot) 增加 Holds(Robot,Box) （3）SET_DOWN(x) 条件：Table(x) At(Robot,x) Hold

26、s(Robot,Box) 动作：删除 Holds(Robot,Box) 增加 On(Box,x) EmptyHanded(Robot) 机器人在执行每一操作之前需要检查所需 先决条件是否满足，只有条件满足以后， 才执行相应的操作。 操作过程如下：操作过程如下： PICK_UP(A) GOTO(A,B) SET_DOWN(B) GOTO(B,A) 第3章 谓词逻辑与归结原理 命题逻辑 谓词逻辑基础 谓词逻辑归结原理谓词逻辑归结原理 Herbrand定理 归结原理概述 谓词逻辑归结方法和命题逻辑归结方法基 本原理是一样的。 谓词逻辑归结在生成子句集之前要将逻辑 公式转化为Skolem标准型，然后再

27、进行归 结。 Herbrand采用反证法思想，将永真性的证明问题 转化为不可满足性的证明问题。而Robinson的归 结原理使得自动定理证明得以实现。 归结法的基本原理归结法的基本原理是采用反证法将待证明 的表达式转换为逻辑公式(谓词公式)，然后 再进行归结，归结能够顺利完成，则证明 公式是正确的。 Skolem Skolem 标准型标准型 前束范式中消去所有的量词，称这种 形式的谓词公式为Skolem标准型。 任何一个谓词公式都可化为与之对应 的Skolem标准型，但不唯一。 Skolem标准型的转化过程：标准型的转化过程：依据约束变量换名规 则，把公式变型为前束范式，然后依照量词消去 原则

28、或者略去所有量词。 量词消去原则量词消去原则 一、消去存在量词“” 注意：左边有全称量词的存在量词，消 去时该变量改写成为全称量词的函数； 如没有，改写成为常量。 二、略去全称量词“” 例例3.12：将下式化为将下式化为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) (y)Q(y, b)R(x) 第三步，变元易名，得 (x)(y)P(a, x, y) (u) ( v)(Q(v,

29、 b) R(u) 第四步，存在量词左移，直至所有的量词移到前面，得： (x)(y)(u)(v)(P(a, x, y) Q(v, b) R(u) 由此得到前束范式 第五步，消去“”（存在量词），略去“”全 称量词 消去(y)，因为它左边只有(x)，所以使用x的 函数f(x)代替之，这样得到： (x) (u) (v) P(a, x, f(x) (Q(v, b) R(u) 消去(u)，同理使用g(x)代替之，这样得到： (x) (v) ( P(a, x, f(x) Q(v, b) R(g(x) 略去全称变量，原式的Skolem标准形为： P(a, x, f(x) Q(v, b) R(g(x) Sko

30、lem定理 谓词逻辑的任意公式都可以化为与之等价 的前束范式，但其前束范式不唯一。 Skolem标准形定义： 消去量词后的谓词公式。 注意： 谓词公式G的Skolem标准形同G并不等值。并不等值。 子句集子句集 文字：文字：不含任何连接词的谓词公式。 子句：子句：一些文字的析取。 子句集子句集S S的求取：的求取： G 前束范式 消去存在量词、略去任意量词，生成 Skolem标准型(必须满足合取范式条件) 以“，”取代“”，并表示为集合形式 。 练习：求谓词公式的子句集 (x) P(x) (y)P(y) P(f(x,y) (y)Q(x,y) P(y) 子句集子句集S求取过程求取过程 1、消去蕴

31、涵符号 2、减少否定符号的辖域 3、对变量标准化 4、消去存在量词 5、化为前束范式 6、把母式化为合取式 7、消去全称量词 8、消去“” 9、更换名称变量 定理定理3.13.1 谓词公式G是不可满足的，当且仅当其子句 集S是不可满足的 G与S不等价，但在不可满足得意义下是一致的。 注意注意：G真不一定S真，而S真必有G真。 即： S = G 定理3.1推广 G = G1 G2 G3 Gn 的子句形 G的子句集可以分解成几个单独处理。 S SG G = S = S1 1 U S U S2 2 U S U S3 3 U U U SU Sn n SG 与 S1 U S2 U S3 U U Sn在不

32、可满足的意 义上是一致的。 1. SG 不可满足 S1 U S2 U S3 U U Sn不可 满足 求子句集例子 例3.13：对所有的x,y,z来说，如果y是x的父亲，z又 是y的父亲，则z是x的祖父。又知每个人都有父亲， 试问对某个人来说谁是它的祖父？ 求：用一阶逻辑表示这个问题，并建立子句集。 解：这里我们首先引入谓词： P(x, y) 表示y是x的父亲 Q(x, y) 表示y是x的祖父 ANS(x) 表示问题的解答 求子句集例子 1、对于第一个条件，“如果x是y 的父亲， y又是z 的父亲，则x是z 的祖父”，一阶逻辑表达式如下： A1：(x)(y)(z)(P(x, y)P(y, z)Q

33、(x, z) S A1：P(x ,y)P(y, z)Q(x, z) 2、对于第二个条件：“每个人都有父亲”，一阶逻 辑表达式： A2：(x)(y)P(x, y) S A2：P(x,f(x) 3、对于结论：某个人是他的祖父 B：(x)(y)Q(x, y) 否定后得到子句： （ (x)(y)Q(x, y)）ANS(y) SB：Q(x, y)ANS(y) 则得到的相应的子句集为： S A1，S A2，SB = P(x ,y)P(y, z)Q(x, z), P(x,f(x), Q(x, y)ANS(y) 置换与合一 由于含有个体变量与函数，一阶谓词 逻辑的归结比命题逻辑的归结复杂得 多。 方法： 合一

34、和置换，即对个体变量作适当替换。 置换置换 置换：可以简单的理解为是在一个谓词公式中用 置换项去置换变量。 定义： 置换是形如t1/x1, t2/x2, , tn/xn的有限集合。其 中，x1, x2, , xn是互不相同的变量，t1, t2, , tn 是不同于xi的项（常量、变量、函数）；ti/xi表示 用ti置换xi，并且要求ti与xi不能相同，而且xi不能 循环地出现在另一个ti中。 例如 a/x，c/y，f(b)/z是一个置换。 g(y)/x，f(x)/y不是一个置换。 置换的合成 设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); 当yix1,x2, , xn时，删去uj/yj (j = 1, 2, , m) 最后剩下的元素所构成的集合。 合成即是对ti先做置换然后再做置换，置换xi 置换的合成 例例3.14： 设：f(y)/x, z/y，a/x, b/y, y/z，求与 的合成。 解： 1、先求出集合 f(b/y)/x, (y/z)/y, a/x, b/y, y/zf(b)/x, y/y, a/x

36、, b/y, y/z 其中，f(b)/x中的f(b)是置换作用于f(y)的结果； y/y中的y是置换作用于z的结果。 2、在该集合中，y/y满足定义中的条件i，需要 删除；a/x，b/y满足定义中的条件ii，也需要 删除。最后得 f(b)/x，y/z 合一合一 合一可以简单地理解为“寻找相对变量的置换，使两 个谓词公式一致”。 定义：设有公式集FF1，F2，Fn，若存在一个 置换，可使F1F2= Fn，则称是F的一个合 一。同时称F1，F2，. ，Fn是可合一的。 例例3.15： 设有公式集FP(x, y, f(y), P(a,g(x),z)，则a/x, g(a)/y, f(g(a)/z是它的

37、一个合一。 注意：一般说来，一个公式集的合一不是唯一的。一般说来，一个公式集的合一不是唯一的。 求公式集F=P(x),P(f(y)的合一 1=f(a)/x,a/y, 2=f(y)/x都是F1F2的合一。 差异集(不一致集) S是一个非空的具有相同谓词名的原子公式 集，从S各公式的左边第一项开始，同时向 右比较，直到发现第一个不都相同的项为 止，用这些项的差异部分组成S的一个差异 集。 差异集(不一致集)的求法 设公式集F1,F2， F1=P(x,y,z)，F2=P(x,f(a),h(b) 解：从左到右进行比较， 1、首先两公式第一个元素，发现相同； 2、接着比较第二个元素，不同，则构成差 异集

38、 D1=y,f(a)； 3、再比较第三个元素，不同，构成差异集 D2=z,h(b)。 最一般合一最一般合一 设是谓词公式集F的一个合一，如果对F的 任意一个合一都存在一个置换，使得= ，则称是一个最一般合一(mgu)。 最一般合一的求取方法 最一般合一是唯一的最一般合一是唯一的(除了字母变化外除了字母变化外) F=P(x),P(y) y/x、x/y都是F1F2的mgu 例例3.16 求求mgu 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的mgu 由算法 1、W=P(a,x,f(g(y),P(z

39、,f(a),f(u) 2、W0=W, 0= 3、W0未合一，从左到右找不一致集，有D0=a,z 4、取v0=z，t0=a 5、令1= 0t0/v0 = a/z W1=W0 1 =P(a,x,f(g(y),P(a,f(a),f(u) 3、W1未合一，从左到右找不一致集，有D1=x,f(a) 4、取v1=x，t1=f(a) 5、令2= 1t1/v1 = a/z f(a)/x=a/z,f(a)/x W2=W1 2 =P(a,f(a),f(g(y),P(a,f(a),f(u) 3、W2未合一，从左到右找不一致集，有D2=g(y),u 4、取v2=u，t2=g(y) 5、令3= 2t2/v2 = a/z

40、,f(a)/xg(y)/u = a/z,f(a)/x,g(y)/u W3=W2 3 =P(a,f(a),f(g(y),P(a,f(a),f(g(y) 3、W3已合一 3= a/z,f(a)/x,g(y)/u是F1和F2的mgu。 谓词逻辑的归结式谓词逻辑的归结式 归结式求取方法归结式求取方法 归结的注意事项： 1、谓词的一致性，P()与 Q()， 不可以 2、常量的一致性， P(a, )与 P(b,.)， 不可以 P(a, .)与 P(x, )， 可以 3、变量与函数， P(x, x, .)与 P(x, f(x), )，不可以 P(x, x, .)与 P(x, f(y), )，可以 4、不能同

41、时消去两个互补对， PQ与PQ，不可以 5、先进行内部简化（置换、合并） 例例3.17 求求C1C2的归结式的归结式 设C1=P(y)P(f(x)Q(g(x), C2=P(f(g(a)Q(b) 解： 对C1取最一般合一=f(x)/y，得C1的因子， C1= P(f(x)Q(g(x) 对C1的因子和C2进行归结，得归结式 Q(g(g(a)Q(b) , g(a)/x 1、F1=B(x),F2=B(x)C(x) 2、F1=P(x)Q(x),F2=Q(f(y) 3、F1=P(x,f(y)Q(x)R(f(a),y),F2=P(f(f(a),z)R(z,w) 谓词逻辑的归结过程谓词逻辑的归结过程 1、写出

42、谓词关系公式 2、用反演法写出谓词表达式 3、化为SKOLEM标准形 4、求取子句集S 5、对S中可归结的子句做归结 6、归结式仍放入S中，反复归结过程 7、得到空子句 8、 命题得证 例例3.18 假设任何通过计算机考试并获奖的人都是快乐假设任何通过计算机考试并获奖的人都是快乐 的，任何肯学习或幸运的人都可以通过所有的考试，张不的，任何肯学习或幸运的人都可以通过所有的考试，张不 肯学习但他是幸运的，任何幸运的人都能获奖。求证：张肯学习但他是幸运的，任何幸运的人都能获奖。求证：张 是快乐的。是快乐的。 解：一、先将问题用谓词表示如下：一、先将问题用谓词表示如下： R1:“任何通过计算机考试并获

43、奖的人都是快乐的” (x)(Pass(x, computer)Win(x, prize)Happy(x) R2:“任何肯学习或幸运的人都可以通过所有考试” (x)(y)(Study(x)Lucky(x)Pass(x, y) R3:“张不肯学习但他是幸运的” Study(zhang)Lucky(zhang) R4:“任何幸运的人都能获奖” (x)(Luck(x)Win(x,prize) 结论：“张是快乐的”的否定 Happy(zhang) 二、将每一个表示逻辑条件的谓词子句转换为二、将每一个表示逻辑条件的谓词子句转换为Skolem标准型标准型 由R1及逻辑转换公式:PWH=(PW) H ，可得

44、(1)Pass(x, computer)Win(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, c

45、omputer) (9)(5) (11) Lucky(zhang) (10)(3)，zhang/u, computer/v (12) (11)(5) 归结原理归结原理 归结法的实质： 归结法是仅有一条推理规则的推理方法。 归结过程是一个语义树倒塌的过程。 归结法的问题 子句中有等号或不等号时，完备性不成立。 通过对谓词公式的否定式的子句集使用消解法归结， 若在某一步时推导出空字句，即推导出了矛盾，则说子 句集是不可满足的，从而原谓词公式也是不可满足的 归结方法是完备的，即对于正确的逻辑公式，使用 该方法可以在有限步内得到结论。 归结过程的控制策略归结过程的控制策略 要解决的问题： 归结方法的知

46、识爆炸。 控制策略的目的 归结点尽量少 控制策略的原则 删除不必要的字句，或对参加归结的子句加以限制 给出控制策略，以便仅选择合适的子句对其做 归结，避免多余的、不必要的归结式出现。 控制策略的方法(1) 删除策略=完备 归类：归类：设有两个子句C和D，若有置换使 得C D成立，则称子句C把子句D归类。 由于小的可以代表大的，所以小的吃掉了由于小的可以代表大的，所以小的吃掉了 大的。大的。 若对S使用归结推理过程中，当归结式Cj是 重言式（永真式）和Cj被S中子句和子句集 的归结式Ci(ij)所归类时，便将Cj删除。这 样的推理过程便称做使用了删除策略的归 结过程。 归结过程在寻找可归结子句时

47、，子句集中 的子句越多，需要付出的代价就会越大。如果 在归结时能把子句集中无用的子句删除掉，就 会缩小搜索范围，减少比较次数，从而提高归 结效率。 缩短归结过程 判别是否可被删除的计算量 删除策略的归结推理是完备的 并非所有可归结的谓词公式都可采用删除策略 删除策略的主要思想 控制策略的方法(2) 采用支撑集 完备 支撑集：支撑集：设有不可满足子句集S的子集T，如果S-T是可 满足的，则称T是S的支撑集。 S T 可满足 支撑集示意图 采用支撑集策略时，从开始到得到的整个归 结过程中，只选取不同时属于S-T的子句，在其间 进行归结。就是说，至少有一个子句来自于支撑集 T或由T导出的归结式。 例

48、如：A1A2A3B中的B可以作为支撑 集使用。要求每一次参加归结的亲本子句中，只要 应该有一个是有目标公式的否定（B）所得到的 子句或者它们的后裔。 思想：尽量避免在可满足的子句集中进行归结， 因为从中推导不出空子句。 可将支撑集策略理解为目标指导的反向推力。 支撑集策略的归结是完备的，同样，所有可归结 的谓词公式都可以用采用支撑集策略达到加快归 结速度的目的。 问题是如何寻找合适的支撑集。一个最容易找到 的支撑集是目标子句的非，即SB。 例如 S=PQ,PR,QR,R，取T=R 支撑集归结过程为： P Q Q P R 控制策略的方法(3) 语义归结 完备 语义归结策略是将子句S按照一定的语义

49、 分成两部分，约定每部分内的子句间不允许 作归结。同时还引入了文字次序，约定归结 时其中的一个子句的被归结文字只能是该子 句中“最大”的文字。 例如例如 S=PQR，PR，QR，R 1、规定顺序为PQR 2、用S的一个解释I=P,Q,R 把S分为两部分 S1=PR，QR，S2=PQR，R 语义归结策略的归结是完备的，同样，所有可 归结的谓词公式都可以用采用语义归结策略达到加 快归结速度的目的。 问题是如何寻找合适的语义分类方法，并根据 其含义将子句集两个部分中的子句进行排序。 归结过程如下： PQR ? S2 PR ? S1 QR ? S1 R ? S2 QR , ? S2 PR , ? S2

50、 R ,? S1 R ,? S1 控制策略的方法(4) 线性归结 完备 线性归结策略首先从子句集中选取一个称作顶 子句的子句C0开始作归结。归结过程中所得到的归 结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi 属于S或是已出现的归结式Cj(j 完备 单元归结策略要求在归结过程中，每次 归结都有一个子句是单元子句（只含一个文 字的子句）或单元因子。显而易见，此种方 法可以简单地削去另一个非单子句中的一个 因子，使其长度减少，构成简单化，归结效 率较高。 不是所有可以归结的谓词公式集合都可以 采用单元归结策略进行归结。初始子句集中 没有单元子句时，单元归结策略无效。 控制策略的方法(6

51、) 输入归结 = 完备 与单元归结策略相似，输入归结策略要求 在归结过程中，每一次归结的两个子句中必须 有一个是S的原始子句。这样可以避免归结出 的不必要的新子句加入归结，造成恶性循环。 可以减少不必要的归结次数。 如同单元归结策略，不是所有的可归结谓 词公式的最后结论都是可以从原始子句集中的 得到的。 简单的例子，归结结束时，即最后一个归 结式为空子句的条件是，参加归结的双方必须 是两个单元子句。原始子句集中没有单元子句 的谓词公式一定不能采用输入归结策略。 第3章 谓词逻辑与归结原理 命题逻辑 谓词逻辑基础 谓词逻辑归结原理 Herbrand定理定理 Herbrand定理 问题： 一阶逻辑

52、公式的永真性 （永假性）的判定是否能 在有限步内完成？ Herbrand定理 1936年图灵(Turing)和邱吉(Church)互相独 立地证明了： “没有一般的方法使得在有限步内判定一阶逻 辑的公式是否是永真（或永假）。但是如果公 式本身是永真（或永假）的，那么就能在有限 步内判定它是永真（或永假）。对于非永真 （或永假）的公式就不一定能在有限步内得到 结论。判定的过程将可能是不停止的。” Herbrand定理 Herbrand的思想 定义： 公式G永真：对于G的所有解释，G都为真。 思想： 寻找一个已给的公式是真的解释。然而， 如果所给定的公式的确是永假的，就没有 这样的解释存在，并且算

53、法在有限步内停 止。 Herbrand定理（H H域）域） 基本方法： 因为量词是任意的，所讨论的个体变量域D是 任意的，所以解释的个数是无限、不可数的 。 简化讨论域。建立一个比较简单、特殊的域， 使得只要在这个论域上，该公式是不可满足的。 此域称为H域。 ),.,( 11nii ttfHH D域 H域 H域与D域关系示意图 H域例题 例3.19 设子句集S=P(x)，Q(y)R(z)，求H域。 H0=a H1=H0=a H = H1H2H3=a 例3.20 设子句集S=P(a)，Q(x)R(f(x)，求H域。 H0=a H1=H0=a,f(a) H2=a,f(a),f(f(a) H = H

54、1H2H3=a,f(a),f(f(a) 例3.21 设子句集S=P(a)，Q(b)R(f(x)，求H域。 此题中有两个常量a,b H0=a,b H1=H0=a,b,f(a),f(b) H2=a,b,f(a),f(b),f(f(a),f(f(b) H = H1H2H3=a,b,f(a),f(b),f(f(a),f(f(b), H域例题 H域例题 例3.22 设子句集S = P(x), Q(y,f(z,b),R(a)，求H域 解： H0 a, b为子句集中出现的常量 H1 a, b, f(a,b), f(a,a), f(b,a), f(b,b) H2 a, b, f(a,b), f(a,a), f

55、(b,a), f(b,b)， f(a,f(a,b), f(a,f(a,a), f(a, f(b,a), f(a, f(b,b), f(b,f(a,b), f(b,f(a,a), f(b, f(b,a), f(b,f(b,b), f(f(a,b),f(a,b), f(f(a,b),f(a,a), f(f(a,b), f(b,a), f(f(a,b), f(b,b), f(f(a,a),f(a,b), f(f(a,a),f(a,a), f(f(a,a), f(b,a), f(f(a,a), f(b,b), f(f(b,a),f(a,b), f(f(b,a),f(a,a), f(f(b,a), f(

56、b,a), f(f(b,a), f(b,b), f(f(b,b),f(a,b), f(f(b,b),f(a,a), f(f(b,b), f(b,a), f(f(b,b), f(b,b) H = H1H2H3 H域例题 例3.23 设子句集S=P(c)，Q(f(x),R(g(x)，求H域。 此题中有常量c，函数f(x),g(x) H0=c H1=H0=c,f(c),g(c) H2=c,f(c),g(c),f(f(c),f(g(c),g(f(c),g(g(c) H = H1H2H3=c,f(c),g(c),f(f(c),f(g(c), g(f(c),g(g(c), Herbrand定理（H H域）

57、域） 原子集A：公式中的谓词取H域中的元素组 成的集合。如 A = 所有形如 P(t1, t2, tn)的元素 即把H中的东西填到S的谓词里去。 S中的谓词是有限的、可数的，H域中的元素是可 数的，因此，A中的元素也是可数的。 原子集例题 上例题的原子集为： A = P(a), Q(a, a), R(a), P(b), Q(b, a), Q(b, b), Q(a, b), R(b), P( f(a,b), Q(f(a, b), f(a, b), R(f(a, b), P(f(a,a), P(f(b,a), P(f(b,b),) 一旦原子集内真值确定好（规定好），则S在H上 的真值可确定。成为可

58、数问题。 论域D上公式G或者说其子句集S的H域的建立， 仅仅依赖于S中出现的几个函数和D的几个常量，或 D中任意的一个常量，而且这些都是可数的，这就 是H域比一般论域D简单的原因。 因此，如果能够将谓词逻辑公式的不可满足性 问题的讨论从D转换到H域，其复杂程度将得到相应 地减少，使得不可解的问题成为可解的问题。 Herbrand定理（H H解释）解释） 解释I：谓词公式G在论域D上任何一组真值 的指定称为一个解释。 H解释：子句集S在的H域上的解释称为H解释。 基例：子句集S中某子句C中所有变元符号均 以S的H域中的元素代入后，所得的基子句C 称为C的一个基例。 例如：S=P(x),Q(f(y

59、)R(y),Z(f(y) H=a,f(a),f(f(a), P(a),P(f(a)为子句C=P(x)的基例 Q(f(a)R(a),Q(f(f(a)R(f(a)都是Q(f(y)R(y)的基例 问题： 对于所有的解释，全是假才可判定。因为 所有解释代表了所有的情况，如可穷举，问 题便可解决 。 例3.24 S=P(x)Q(x),R(f(y)，求其一个H解释I* 解： S的H域为：a,f(a),f(f(a), S的原子集A为：P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a), I1*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a), I2*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a), I3*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a), 原子集A中各元素真假值的一个具体设定或对S中出现的常量、 函数及谓词的一次取值