第8,9章-49(56-2013上课)

1、0871-50313012021年7月12日星期一 1 / 16 信 息 学 院 人工智能 一种现代方法 B1,1 (P1,2 P2,1) B2,1 (P1,1 P2,2 P3,1) 命题逻辑命题逻辑 陈述式语言 可采用析取式和合取式来处理不完全、不连贯信息,例如 B1,1 P1,2 合成性: 语句的语义是其各部分含义的函数 上下文无关 表达能力有限 0871-50313012021年7月12日星期一 2 / 16 信 息 学 院 人工智能 一种现代方法 第八章第八章 一阶逻辑和一阶推理一阶逻辑和一阶推理 8.1 一阶逻辑的语法和语义 8.2 使用一阶逻辑 8.3 命题与一阶推理 8.4 sk

2、olem标准型 8.5 置换和合一 8.6 归结 8.7 前向链接 8.8 反向链接 0871-50313012021年7月12日星期一 3 / 16 信 息 学 院 人工智能 一种现代方法 命题逻辑的模型只是命题符号的真值集。命题逻辑的模型只是命题符号的真值集。 一一阶逻辑的模型：阶逻辑的模型： 对象（对象（objectsobjects）：数字、人）：数字、人. 关系（关系（RelationshipRelationship）: : 是自然数、是工程师是自然数、是工程师( (属性属性).). .和和,是同学，在是同学，在.里面里面.(n.(n元关系元关系) ) 函数（函数（FunctionsF

3、unctions）: :最好的朋友最好的朋友 小王是个工程师小王是个工程师 9 9是个自然数是个自然数 我去买水我去买水 小王和小李是同学小王和小李是同学 谓词逻辑（一阶逻辑）谓词逻辑（一阶逻辑） 模型的域是所包含的对象集。模型的域是所包含的对象集。 0871-50313012021年7月12日星期一 4 / 16 信 息 学 院 人工智能 一种现代方法 常量符号：命名对象，例如，常量符号：命名对象，例如，John,Flower,.John,Flower,. 变量符号变量符号 x,y,zx,y,z 谓词符号谓词符号: :命名关系命名关系 谓词谓词: :刻画对象性质和对象之间关系刻画对象性质和对

4、象之间关系 谓词的一般形式：谓词的一般形式：P(x1,x2,xn)P(x1,x2,xn) 其中其中P P是谓词名，是谓词名，xixi是个体。是个体。 个体可以是常量出可以个体可以是常量出可以 是变量，还可以是一个函数。是变量，还可以是一个函数。 当谓词的变元都用特定的个体表达时，谓词只有一个当谓词的变元都用特定的个体表达时，谓词只有一个 确定的真值，确定的真值，T T或或F F。 谓词中包含的个体数目称为谓词的元数，谓词中包含的个体数目称为谓词的元数， P P（x)x)称为一元谓词，称为一元谓词，P(x,y)P(x,y)称为二元谓词。称为二元谓词。 谓词逻辑（一阶逻辑）谓词逻辑（一阶逻辑） 0

5、871-50313012021年7月12日星期一 5 / 16 信 息 学 院 人工智能 一种现代方法 谓词逻辑（一阶逻辑）谓词逻辑（一阶逻辑） 在谓词中，若在谓词中，若xi(i=1,n)都是个体常量，变元或函数，称它为都是个体常量，变元或函数，称它为 一阶谓词，如果某个一阶谓词，如果某个xi 本身又是一阶逻辑或一阶谓词，则称它为本身又是一阶逻辑或一阶谓词，则称它为 二阶逻辑或二阶谓词。二阶逻辑或二阶谓词。 0871-50313012021年7月12日星期一 6 / 16 信 息 学 院 人工智能 一种现代方法 谓词公式谓词公式 连接词：用来将谓词连接起来的连接词。连接词：用来将谓词连接起来的

6、连接词。 非非“”或否定，作用是否定位于它后面的公式。或否定，作用是否定位于它后面的公式。 析取析取“”表示与它连接的公式具有或的关系。表示与它连接的公式具有或的关系。 合取合取“”表示与它连接的公式具有与的关系。表示与它连接的公式具有与的关系。 条件或蕴涵条件或蕴涵“”，P Q表示表示P蕴涵蕴涵Q，即如果，即如果P，则，则 Q 双条件双条件“”，P Q表示表示P当且仅当当且仅当Q。 谓词公式谓词公式: 由连接词、原子命题、原子公式、量词及圆括号组成由连接词、原子命题、原子公式、量词及圆括号组成 的字符串的字符串 等式：用等号来声明两个表达式指代同一个对象等式：用等号来声明两个表达式指代同一个

7、对象 Brother(John)=Richard 0871-50313012021年7月12日星期一 7 / 16 信 息 学 院 人工智能 一种现代方法 量词量词 全称量词：全称量词：x表示对个体域中的所有（或任一表示对个体域中的所有（或任一 个）个体个）个体x。 x At(x,YNU) Smart(x) :对象全域上的合取式对象全域上的合取式 At(a,YNU) Smart(a) At(b,YNU) Smart(b) At(c,YNU) Smart(c) x At(x,YNU) Smart(x) 每个人在每个人在YNUYNU并且每个人是并且每个人是smartsmart 0871-50313

8、012021年7月12日星期一 8 / 16 信 息 学 院 人工智能 一种现代方法 存在存在量词：量词：x表示表示“在个体域中的存在个体在个体域中的存在个体 x。 x At(x,YNU) Smart(x) ：对象全域上的析取式：对象全域上的析取式 At(a,YNU) Smart(a) At(b,YNU) Smart(b) . x At(x,YNU) Smart(x) 则则a不在不在YNU蕴含关系任然成立。蕴含关系任然成立。 0871-50313012021年7月12日星期一 9 / 16 信 息 学 院 人工智能 一种现代方法 量词辖域：如果有量词出现，位于量词后面的单个或用括量词辖域：如果

9、有量词出现，位于量词后面的单个或用括 号括起来的合式公式称为量词的辖域。号括起来的合式公式称为量词的辖域。 约束变元：在辖域内与量词中同名的变元称为约束变元。约束变元：在辖域内与量词中同名的变元称为约束变元。 不受约束的称为自由变元。不受约束的称为自由变元。 x P(x,y) 0871-50313012021年7月12日星期一 10 / 16 信 息 学 院 人工智能 一种现代方法 量词性质量词性质 x x y y brother(x,y)= sibling(x,y) brother(x,y)= sibling(x,y) y y x x x x y y 不等于不等于 y y x x x x y

10、 y Loves(x,y), Loves(x,y),其中其中LovesLoves（x,y)x,y)表示表示x x喜爱喜爱y y “存在某人，他存在某人，他/ /她喜爱世界上每一个人她喜爱世界上每一个人” y y x Loves(x,y)x Loves(x,y) “世界上每一个人至少有一个人喜爱他世界上每一个人至少有一个人喜爱他/ /她她” 嵌套量词嵌套量词 0871-50313012021年7月12日星期一 11 / 16 信 息 学 院 人工智能 一种现代方法 x x Likes(x,IceCream) Likes(x,IceCream) 等价于等价于x x Likes(x,IceCream

11、)Likes(x,IceCream) 所有人喜欢吃冰淇淋所有人喜欢吃冰淇淋 不存在不喜欢吃冰淇淋的人不存在不喜欢吃冰淇淋的人 x Likes(x, IceCream) x Likes(x, IceCream) 等价于等价于x x Likes(x,IceCream)Likes(x,IceCream) 有人喜欢吃冰淇淋有人喜欢吃冰淇淋 不是所有人都不喜欢吃冰淇淋不是所有人都不喜欢吃冰淇淋 量词性质量词性质 量词否定等值式：量词否定等值式： ( x)M(x) ( y) M(y) ( x)M(x) ( y) M(y) ( x)M(x) ( y) M(y) ( x)M(x) ( y) M(y) 0871

12、-50313012021年7月12日星期一 12 / 16 信 息 学 院 人工智能 一种现代方法 量词分配：量词分配： ( (x)(PQ) (x)(PQ) (x)P(x)P(x)Qx)Q ( (x)(Px)(PQ) (Q) (x)Px)P( (x)Qx)Q 消去量词等值式：设个体域为有穷集合消去量词等值式：设个体域为有穷集合(a1,a2,.,an)(a1,a2,.,an) ( (x)P(x) P(a1)P(a2),. P(an)x)P(x) P(a1)P(a2),. P(an) ( (x)P(x) P(a1)x)P(x) P(a1)P(a2) P(a2) ,. ,. P(an) P(an)

13、量词性质量词性质 0871-50313012021年7月12日星期一 13 / 16 信 息 学 院 人工智能 一种现代方法 量词辖域收缩和扩张等值式量词辖域收缩和扩张等值式 ( x)(P(x) Q) ( x)P(x) Q ( x)(P(x) Q) ( x)P(x) Q ( x)(Q P(x) Q (x)P(x) ( x)(P(x) Q) ( x)P(x) Q ( x)(P(x) Q) ( x)P(x) Q ( x)(P(x) Q) ( x)P(x) Q ( x)(Q P(x) Q ( x)P(x) ( x)(P(x) Q) ( x)P(x) Q 量词性质量词性质 0871-503130120

14、21年7月12日星期一 14 / 16 信 息 学 院 人工智能 一种现代方法 定义：设定义：设D为谓词公式为谓词公式P的个体域，若对的个体域，若对P中的个体变量，中的个体变量， 函数按照如下规定赋值：函数按照如下规定赋值： 1。为每个变量指派。为每个变量指派D中的一个元素。中的一个元素。 2。为每个。为每个n元函数指派一个从元函数指派一个从 谓词公式的解释谓词公式的解释 ,),( 2121 DxxxxxxD nn n 谓词逻辑中，公式中可能有个体常量，个体变元谓词逻辑中，公式中可能有个体常量，个体变元 或函数，所以不能像命题公式一样给予出真值表的或函数，所以不能像命题公式一样给予出真值表的

15、解释。解释。 到到D的映射，其中的映射，其中 n D Brother(Richard, John) 即一阶逻辑的解释指定了符号到模型的一个映射。即一阶逻辑的解释指定了符号到模型的一个映射。 则称这些指派为公式则称这些指派为公式P在在D上的一个解释。上的一个解释。 0871-50313012021年7月12日星期一 15 / 16 信 息 学 院 人工智能 一种现代方法 永真：如果谓词公式永真：如果谓词公式P，对个体域，对个体域D上的任何一个解释都取上的任何一个解释都取 得真值得真值T，则称，则称P在在D上是永真的；如果上是永真的；如果P在每个非空个体域上在每个非空个体域上 均永真，则称均永真，

16、则称P永真。永真。 永假：如果谓词公式永假：如果谓词公式P，对个体域，对个体域D上的任何一个解释都取上的任何一个解释都取 得真值得真值F，则称，则称P在在D上是永假的；如果上是永假的；如果P在每个非空个体域上在每个非空个体域上 均永假，则称均永假，则称P永假。永假。 对于谓词公式对于谓词公式P，如果至少存在一个解释使得公式，如果至少存在一个解释使得公式P在此解在此解 释下的真值为释下的真值为T，则称，则称P是可满足的。是可满足的。 谓词公式的永真性和可满足性谓词公式的永真性和可满足性 0871-50313012021年7月12日星期一 16 / 16 信 息 学 院 人工智能 一种现代方法 等

17、价：设公式等价：设公式P与与Q，有共同的个体域，有共同的个体域D，且对，且对D上上 的任何一个解释，的任何一个解释，P与与Q的取值都相同，则的取值都相同，则P和和Q在在D上上 是等价的。是等价的。 记作：记作：PQ 谓词公式的等价性谓词公式的等价性 0871-50313012021年7月12日星期一 17 / 16 信 息 学 院 人工智能 一种现代方法 命题逻辑只是对事实的存在进行限定，而一阶逻辑对对象命题逻辑只是对事实的存在进行限定，而一阶逻辑对对象 和关系的存在进行限定，因而有更强的表达能力和关系的存在进行限定，因而有更强的表达能力 0871-50313012021年7月12日星期一 1

18、8 / 16 信 息 学 院 人工智能 一种现代方法 谓词公式表示知识举例谓词公式表示知识举例 (1) 所有人都是要死的所有人都是要死的 (2)有的人活到一百岁以上有的人活到一百岁以上 在域为人类集合时，可符号化为：在域为人类集合时，可符号化为： (1) x P(x)，其中P(x)表示x是要死的。 (2) x Q(x)，其中Q(x)表示x活到一百岁以上。 在域为全个体域时，引入谓词在域为全个体域时，引入谓词R(x)表示表示x是人，可符号化为：是人，可符号化为： (1) x (R(x) P(x)， (2) x (R(x) Q(x)， 0871-50313012021年7月12日星期一 19 /

19、16 信 息 学 院 人工智能 一种现代方法 WumpusWumpus世界世界 Tell(KB,Percept(Smell,Breeze,None, None, None,t) Ask(KB, a BestAction(a,t) Answer: a/Shoot 感知：感知： t,s,b,m,c Percept(s, b, Glitter, m, c, t) Glitter(t) 行动选择：行动选择：t Glitter(t) BestAction(Grab,t) Turn(Right), Turn(Left), Forward, Shoot, Grab Percept(Stench,Breeze

20、, Glitter, None, None, t) 0871-50313012021年7月12日星期一 20 / 16 信 息 学 院 人工智能 一种现代方法 Home(Wumpus) Pit(s) At(Agent, s, t) x,y,a,b Adjacent(x,y,a,b) a,b x+1,y, x-1,y,x,y+1,x,y-1 s,t At(Agent, s, t) Breeze(t) Breezy(s) s Breezy(s) r Adjacent(r,s) Pit(r) s Breezy(s) r Adjacent(r,s) Pit(r) s Breezy(s) r Adjac

21、ent(r,s) Pit(r) 0871-50313012021年7月12日星期一 21 / 16 信 息 学 院 人工智能 一种现代方法 常用的等值式常用的等值式 交换率：交换率： PQ QP； PQ Q P 结合率：结合率： (PQ)R P(QR) 分配率：分配率： P(QR) (PQ)(PR) 摩根定律：摩根定律： (PQ) P Q 否定之否定：否定之否定： ( P) P 吸收律：吸收律： P(PQ) P 补余律：补余律： P P T 逆否定律：逆否定律： P Q Q P 0871-50313012021年7月12日星期一 22 / 16 信 息 学 院 人工智能 一种现代方法 常用的转

22、换律常用的转换律 连接词化归：连接词化归： P Q PQ PQ (P Q)(Q P) P Q (PQ)( P Q) 量词转换：量词转换： (x)P (x)( P) (x)P (x) ( P) 量词分配：量词分配： (x)(PQ) (x)P(x)Q (x)(PQ) (x)P(x)Q 0871-50313012021年7月12日星期一 23 / 16 信 息 学 院 人工智能 一种现代方法 永真蕴含式永真蕴含式 化简式：化简式： (PQ) P, (PQ) Q 附加式：附加式： P(PQ) , Q(PQ) 析取三段论：析取三段论： P, (PQ)Q 假言推理：假言推理： P, PQQ 析取推理：析取

23、推理： Q, PQ P 假言三段论：假言三段论： PQ QRPR 二难推理：二难推理： (PQ),PR,QRR 全称固化：全称固化： (x)P(x) P(y) y是是D中任一个体中任一个体 存在固化：存在固化： (x)P(x) P(y) y是是D中某一个体中某一个体 P(y)为真为真 0871-50313012021年7月12日星期一 24 / 16 信 息 学 院 人工智能 一种现代方法 谓词归结子句形谓词归结子句形(Skolem(Skolem标准形标准形) ) 前束范式：一个谓词公式前束范式：一个谓词公式, ,如果它的所有量词均非否定如果它的所有量词均非否定 地出现在公式的最前面地出现在公

24、式的最前面, ,且它的辖域一直延伸到公式之末且它的辖域一直延伸到公式之末, , 同时不出现连接词同时不出现连接词=和和, ,这种形式的公式称为前束形范式这种形式的公式称为前束形范式. . (Q1X1)(Q2X2)(QnXn)M(X1,X2,Xn) 例如：例如：( (X)(X)(Y)(Y)(Z)(P(X)F(Y,X)Q(Y,X)Z)(P(X)F(Y,X)Q(Y,X) 0871-50313012021年7月12日星期一 25 / 16 信 息 学 院 人工智能 一种现代方法 约束变量换名规则：约束变量换名规则： (Qx)M(x) (Qy)M(y) (Qx)M(x，z) (Qy)M(y，z) 量词消

25、去规则：消去存在量词量词消去规则：消去存在量词 ，略去全称量词，略去全称量词。 左边有全称量词的存在量词，消去时该变量改写成为全左边有全称量词的存在量词，消去时该变量改写成为全 称量词的函数，如果没有，则改写成常量。称量词的函数，如果没有，则改写成常量。 谓词归结子句形谓词归结子句形(Skolem(Skolem标准形标准形) ) 0871-50313012021年7月12日星期一 26 / 16 信 息 学 院 人工智能 一种现代方法 谓词归结子句形谓词归结子句形(Skolem(Skolem标准形标准形) ) SkolemSkolem定理：定理： 谓词逻辑的任意公式都可以转化为与之等价的前束范

26、式，谓词逻辑的任意公式都可以转化为与之等价的前束范式， 但其前束范式不唯一。但其前束范式不唯一。 SkolemSkolem标准形：消去量词后的谓词公式。标准形：消去量词后的谓词公式。 注意，谓词公式注意，谓词公式G G的的SkolemSkolem范式同范式同G G并不等值。并不等值。 0871-50313012021年7月12日星期一 27 / 16 信 息 学 院 人工智能 一种现代方法 谓词公式化为谓词公式化为skolemskolem标准型的解题步骤标准型的解题步骤 1、取消、取消 ，连接连接词。词。 2、把、把 的的辖辖域域减减少到最多只作用于一少到最多只作用于一个谓词个谓词。 3 3、

27、把全称量词移到公式左边。并使其辖域包括后面整个把全称量词移到公式左边。并使其辖域包括后面整个 公式。公式。 4. 4. 变变量更名，存在量量更名，存在量词词左移左移 5 5、消去存在量、消去存在量词词: : （1 1）存在量）存在量词词不出不出现现在全在全称称量量词词的的辖辖域域内内，用一，用一个个新的新的 个个体常量替体常量替换该换该存在量存在量词词。 （2 2）存在量）存在量词词位于一位于一个个或多或多个个全全称称量量词词的的辖辖域域内将内将存在存在 量量词变词变元用元用它它前面的前面的约约束束变变元的元的skolemskolem函函数数替替换换。 0871-50313012021年7月1

28、2日星期一 28 / 16 信 息 学 院 人工智能 一种现代方法 谓词公式化为谓词公式化为skolemskolem标准型（例）标准型（例） （(x)( y)P(a, x, y) (x) ( (y)Q(y,b) R(x)） 1、 消去消去: （ (x)( y)P(a,x,y) (x) ( (y)Q(y,b)R(x)） 2、 深入到量词内部：深入到量词内部： (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)M(x) ( y) M(y) ( x)M(x) ( y) M(y) 谓词公式：谓词公

29、式： 0871-50313012021年7月12日星期一 29 / 16 信 息 学 院 人工智能 一种现代方法 谓词公式化为谓词公式化为skolemskolem标准型（例）标准型（例） 4. 变量易名，存在量词左移，直到所有量词移到前面：变量易名，存在量词左移，直到所有量词移到前面： (x)(y)P(a,x,y) (z) ( Q(z,b) R(x) (x)(y) (z) (P(a,x,y) ( Q(z,b) R(x) 5.消去存在量词，略去全称量词消去存在量词，略去全称量词 消去消去(y)，因为其左边只有，因为其左边只有(x)，因此使用，因此使用x的函数的函数f(x)代替：代替： (x)(z

30、)(P(a,x,f(x) Q(z,b) R(x) 消去消去(z)，同理函数，同理函数g(x)代替之：代替之： (x)(P(a,x,f(x) Q(g(x),b) R(x) 原式的原式的Skolem标准形：标准形：P(a,x,f(x) Q(g(x),b) R(x) 3、 全称量词左移（利用分配律）：全称量词左移（利用分配律）： (x)( (y)P(a,x,y) (y)( Q(y,b) R(x) 0871-50313012021年7月12日星期一 30 / 16 信 息 学 院 人工智能 一种现代方法 子句与子句子集子句与子句子集 不含有任何连接词的谓词公式称做原子公式，不含有任何连接词的谓词公式称

31、做原子公式， 简称原子，而原子或原子的否定统称文字。简称原子，而原子或原子的否定统称文字。 子句：由文字组成的析取式。子句：由文字组成的析取式。 谓词公式的谓词公式的skolem标准型是由一些子句的合取组成。标准型是由一些子句的合取组成。 前例前例 S=P(a,x,f(x)， Q(g(x),b)， R(x) 0871-50313012021年7月12日星期一 31 / 16 信 息 学 院 人工智能 一种现代方法 G G是不可满足的是不可满足的S S是不可满足的是不可满足的 G G和和S S不等价，但在不可满足的意义下是一致的。不等价，但在不可满足的意义下是一致的。 定理：若定理：若G G是给

32、定的公式，而是给定的公式，而S S是相应的子句集，则是相应的子句集，则G G是不可是不可 满足的满足的S S是不可满足的。是不可满足的。 注意：注意：G G真不一定真不一定S S真，而真，而S S真必有真必有G G真，即真，即S = G S = G 0871-50313012021年7月12日星期一 32 / 16 信 息 学 院 人工智能 一种现代方法 G = GG = G1 1 G G2 2 . . G Gn n 的子句形的子句形 G G的子句集可以分解成几个单独处理：的子句集可以分解成几个单独处理： S SG G 和 和 S S1 1 S S2 2 . . S Sn n 在不可满足的意义

33、上是一致的，在不可满足的意义上是一致的， 即即S SG G 不可满足 不可满足 S S1 1 S S2 2 . . S Sn n 不可满足不可满足 0871-50313012021年7月12日星期一 33 / 16 信 息 学 院 人工智能 一种现代方法 例：对所有的例：对所有的x x，y y，z z来说，如果来说，如果y y是是x x的父亲，的父亲，z z又是又是y y的父的父 亲，则亲，则z z是是x x的祖父，又知道每个人都有父亲，则试问对某的祖父，又知道每个人都有父亲，则试问对某 个人来说谁是其祖父。用一阶逻辑表示这个问题，并建立个人来说谁是其祖父。用一阶逻辑表示这个问题，并建立 子句

34、集。子句集。 解：定义谓词：解：定义谓词： P(x,y)P(x,y)表示表示x x是是y y的父亲的父亲 Q(x,y)Q(x,y)表示表示x x是是y y的祖父的祖父 ANS(x)ANS(x)表示问题的解答表示问题的解答 0871-50313012021年7月12日星期一 34 / 16 信 息 学 院 人工智能 一种现代方法 A1A1： ( (x)(x)(y)(y)(z)(P(x,y) z)(P(x,y) P(y,z)=Q(x,z) P(y,z)=Q(x,z) S1S1： P(x,y)P(x,y) P(y,z)P(y,z)Q(x,z)Q(x,z) 对第二个条件对第二个条件“每个人都有父亲每个

35、人都有父亲”,”,一阶逻辑表达式一阶逻辑表达式: : A2: (A2: (y)(y)(x)P(x,y)x)P(x,y) S2: P(f(y),y)S2: P(f(y),y) 对于结论：对于结论：“某个人是某人祖父某个人是某人祖父” B: (B: (x)(x)(y)Q(x,yy)Q(x,y） 否定后得到子句：否定后得到子句： (x)(x)(y)Q(x,y)y)Q(x,y)）ANS(x)ANS(x) S S B B ： ： Q(x,y) Q(x,y)ANS(x)ANS(x) 则得到相应的子句集为则得到相应的子句集为S1, S2, SS1, S2, S B B 对第一个条件对第一个条件“如果如果y是

36、是x的父亲，的父亲，z又是又是y的父亲，的父亲， 则则z是是x的祖父的祖父”，一阶逻辑表达式如下：，一阶逻辑表达式如下： 0871-50313012021年7月12日星期一 35 / 16 信 息 学 院 人工智能 一种现代方法 归结原理归结原理 归结原理正确性的根本在于，找到矛盾可以肯定不真归结原理正确性的根本在于，找到矛盾可以肯定不真 方法：和命题逻辑一样方法：和命题逻辑一样 但由于有函数，所以要考虑合一和置换但由于有函数，所以要考虑合一和置换 0871-50313012021年7月12日星期一 36 / 16 信 息 学 院 人工智能 一种现代方法 置换置换 置换：是一个形如置换：是一个

37、形如t1/ x1,t2/x2,tn/xn的有限集合。的有限集合。 其中，其中，xi是变量，且是变量，且 ti 是置换项（常量、变量、函数），是置换项（常量、变量、函数），ti/xi表示用表示用ti替换替换xi， 并且要求并且要求ti和和xi不相同，而且不相同，而且xi 不应循环地出现在另一个不应循环地出现在另一个ti 中。中。 例如：例如：a/x, c/y, f(b)/z g(y)/x, f(x)/y njjixx ji , 2 , 1),( 置换可以简单的理解为是在一个谓词公式中用置置换可以简单的理解为是在一个谓词公式中用置 换项去替换变量。换项去替换变量。 0871-50313012021

38、年7月12日星期一 37 / 16 信 息 学 院 人工智能 一种现代方法 置换置换 /,/ )(,/ztydfxc ),(),(yxguzyxQP 例如置换：例如置换： 公式：公式： )(,(),),(,(dfcgutdfcQP 置换后：置换后： 0871-50313012021年7月12日星期一 38 / 16 信 息 学 院 人工智能 一种现代方法 置换乘法（合成）置换乘法（合成） /,/,/ /,/,/ 2211 2211 nn nn yuyuyu xtxtxt /,/,/,/,/,/ 22112211mmnn yuyuyuxtxtxt 如置换：如置换： 置换的乘法也是一个置换，记为置

39、换的乘法也是一个置换，记为 iini iiii yuxxx：y xtx：t /, /, 21 则删去若 则删除若 即对即对ti先做先做置换然后再做置换然后再做置换置换 0871-50313012021年7月12日星期一 39 / 16 信 息 学 院 人工智能 一种现代方法 置换乘法（例）置换乘法（例） /,/,/ /,/ )( zyybxa yzxyf /,/,/,/,/ )( /,/,/,/ )/( ,/ )/( /,/,/,/,/)( zyybxayyxbf zyybxayzyxybf zyybxayzxyf 如置换：如置换： 置换的乘法：置换的乘法： /,/ )()( /,/ / zy

40、xbf ybxa yy 再删除 删去 置换后：置换后： 0871-50313012021年7月12日星期一 40 / 16 信 息 学 院 人工智能 一种现代方法 合一合一 , 21n EEEE n EEE 21 定义：设有公式集定义：设有公式集 ，若存在一个置换，若存在一个置换可使可使 n EEE, 21 则称则称是是E的一个合一，同时称的一个合一，同时称 是可合一的。是可合一的。 置换与合一的意义：推理过程中要根据知识模置换与合一的意义：推理过程中要根据知识模 式的相似程度进行匹配，为使已知事实与知识库中式的相似程度进行匹配，为使已知事实与知识库中 的知识完全匹配，需要经过一定的变量置换，

41、或做的知识完全匹配，需要经过一定的变量置换，或做 某种变元的置换与合一。某种变元的置换与合一。 合一可以简单地理解为：寻找相对变量的置换，使两个谓词公式合一可以简单地理解为：寻找相对变量的置换，使两个谓词公式 一致。一致。 0871-50313012021年7月12日星期一 41 / 16 信 息 学 院 人工智能 一种现代方法 例：公式集例：公式集P(x, f(y), B), P(z, f(B), B)P(x, f(y), B), P(z, f(B), B) 置换置换T T =A/x, B/y, A/z=A/x, B/y, A/z是一个合一，因为是一个合一，因为 P PT T(x, f(y)

42、, B)(x, f(y), B) = P(A,f(B),B)= P(A,f(B),B) P PT T(z,f(B),B) = P(A,f(B),B)(z,f(B),B) = P(A,f(B),B) 同时置换同时置换z/x,B/yz/x,B/y和和x/z,B/yx/z,B/y也都是这两个谓词公式的也都是这两个谓词公式的 合一。合一。 P(z,f(B),B) P(x,f(B),B) P(z,f(B),B) P(x,f(B),B) 一般说来，一个公式集的合一不是唯一的。一般说来，一个公式集的合一不是唯一的。 0871-50313012021年7月12日星期一 42 / 16 信 息 学 院 人工智能

43、 一种现代方法 最一般的合一（最一般的合一（mgumgu） n EEE, 21 设设 有合一置换有合一置换 的任一置换的任一置换 n EEE, 21 若使若使 最一般的合一。最一般的合一。 都存在一个置换都存在一个置换 称称是是 n EEE, 21 且且 置换最少，限制最少，最具一般性。置换最少，限制最少，最具一般性。 mgu也不是唯一的。也不是唯一的。 0871-50313012021年7月12日星期一 43 / 16 信 息 学 院 人工智能 一种现代方法 最一般的合一（例）最一般的合一（例） 设设E1=P(a,v,f(g(y),E2=P(z,f(a),f(u) 求求E1和和E2的最一般合

44、一的最一般合一mgu. 令令W=P(a,v,f(g(y),P(z,f(a),f(u) 从左到右找不一致集，得从左到右找不一致集，得D=a,z 作置换作置换a/z W=P(a,v,f(g(y),P(a,f(a),f(u) 从左到右找不一致集，得从左到右找不一致集，得D=v,f(a) 作置换作置换a/z,f(a)/v W=P(a,f(a),f(g(y),P(a,f(a),f(u) 从左到右找不一致集，得从左到右找不一致集，得D=g(y),u 作置换作置换a/z,f(a)/v,g(y)/u W=P(a,f(a),f(g(y),P(a,f(a),f(g(y) a/z,f(a)/v,g(y)/u是是E1

45、和和E2的的mgu 0871-50313012021年7月12日星期一 44 / 16 信 息 学 院 人工智能 一种现代方法 归结原理归结原理 归结的注意事项：归结的注意事项： 1.1.谓词的一致性，谓词的一致性，P()P()和和Q()Q()，不可以归结，不可以归结 2.2.常量的一致性，常量的一致性，P(A,)P(A,)和和P(B,)P(B,)不可以归结不可以归结 3.3.变量和函数，变量和函数，P(a,xP(a,x，)和和P(x,f(x)P(x,f(x)不可以归结不可以归结 但但P(a,zP(a,z，)和和P(x,f(y)P(x,f(y)可以可以 4.4.不能同时消去两个互补对，例如：不

46、能同时消去两个互补对，例如：PQPQ和和 P P Q Q的空的空 不可以。不可以。 5.5.先进行内部简化（置换、合并）先进行内部简化（置换、合并） 归结：设归结：设C1与与C2是子句集中的任意两个子句，如是子句集中的任意两个子句，如 果果C1中的文字中的文字L1与与C2中的文字中的文字L2互补，则从互补，则从C1和和C2 中可以分别消去中可以分别消去L1和和L2，并将两个子句中余下的部份，并将两个子句中余下的部份 做析取构成一个新的子句做析取构成一个新的子句C12，称这一过程为归结。，称这一过程为归结。 0871-50313012021年7月12日星期一 45 / 16 信 息 学 院 人工

47、智能 一种现代方法 归结过程归结过程 写成谓词关系公式写成谓词关系公式 用反证法写成谓词表达式用反证法写成谓词表达式 SkolemSkolem标准形标准形-子句集子句集S S 对对S S中可归结的子句做归结中可归结的子句做归结 归结式仍放入归结式仍放入S S中，反复归结过程中，反复归结过程 得到空子句得到空子句 得证得证 0871-50313012021年7月12日星期一 46 / 16 信 息 学 院 人工智能 一种现代方法 例题：快乐学生问题例题：快乐学生问题 解：先将问题用谓词表示： R1：任何通过计算机考试并获奖的人都是快乐的 (x)( (Pass(x,computer)Win(x,p

48、rize) = Happy(x) ) R2:任何肯学习或幸运的人都可以通过所有的考试 (x)(y)(Study(x)Lucky(x) )=Pass(x,y) R3:小王不肯学习但他是幸运的 Study(Wang) Lucky(Wang) R4:任何幸运的人都能获奖 (x)( Lucky(x)=Win(x,prize) 结论：小王是快乐的. Happy（Wang）（结论的否定） 假设任何通过计算机考试并获奖的人都是快乐的，任假设任何通过计算机考试并获奖的人都是快乐的，任 何肯学习或幸运的人都可以通过所有的考试，小王不何肯学习或幸运的人都可以通过所有的考试，小王不 肯学习但他是幸运的，任何幸运的人

49、都能获奖，求证，肯学习但他是幸运的，任何幸运的人都能获奖，求证， 小王是快乐的小王是快乐的. 0871-50313012021年7月12日星期一 47 / 16 信 息 学 院 人工智能 一种现代方法 由由R1R1和逻辑转换公式和逻辑转换公式P PW=H W=H （P PW W) )HH，得，得 (1) (1) Pass(x,computer)Pass(x,computer) Win(x,prize) Happy(x)Win(x,prize) Happy(x) 由由R2R2得得( ( Study(x)Study(x) Lucky(x)Lucky(x)Pass(x,y)Pass(x,y) (2)

50、 (2) Study(y)Study(y)Pass(y,z)Pass(y,z) (3) (3) Lucky(u)Lucky(u)Pass(u,v)Pass(u,v) 由由R3R3得得 (4)(4) Study(Wang) Study(Wang) (5)Lucky(Wang) (5)Lucky(Wang) 由由R4R4得得 (6) (6) Lucky(w) Lucky(w) Win(w,prize) Win(w,prize) 结论的否定：结论的否定：(7) (7) HappyHappy（WangWang） 0871-50313012021年7月12日星期一 48 / 16 信 息 学 院 人工智

51、能 一种现代方法 (1)(1) Pass(x,computer)Pass(x,computer) Win(x,prize)Happy(x)Win(x,prize)Happy(x) (2) (2) Study(y)Study(y)Pass(y,z)Pass(y,z) (3) (3) Lucky(u)Lucky(u)Pass(u,v)Pass(u,v) (4)(4) Study(Wang) Study(Wang) (5)Lucky(Wang)(5)Lucky(Wang) (6) (6) Lucky(w) Lucky(w) Win(w,prize) Win(w,prize) (7) (7) Happ

52、yHappy（WangWang） (8)(8) Pass(w,computer)Pass(w,computer)Happy(w)Happy(w) Lucky(w) (1)(6) w/xLucky(w) (1)(6) w/x (9)(9) Pass(wang,computer)Pass(wang,computer) Lucky(wang)Lucky(wang) (8)(7) wang/w (8)(7) wang/w (10)(10) Pass(wang,computer) (9)(5)Pass(wang,computer) (9)(5) (11)(11) Lucky(wang)Lucky(wan

53、g) (10)(3) wang/u, computer/v (10)(3) wang/u, computer/v (12)(12)空空 (11)(5)(11)(5) 0871-50313012021年7月12日星期一 49 / 16 信 息 学 院 人工智能 一种现代方法 归结法的实质：归结法的实质： 归结法是仅有一条推理规则的推理方法。归结法是仅有一条推理规则的推理方法。 归结的过程是一个语义树倒塌的过程。归结的过程是一个语义树倒塌的过程。 归结法的问题：归结法的问题： 子句中有等号或不等号时，完备性不成立。子句中有等号或不等号时，完备性不成立。 0871-50313012021年7月12日

54、星期一 50 / 16 信 息 学 院 人工智能 一种现代方法 归结过程的控制策略归结过程的控制策略 要解决的问题：要解决的问题： 归结方法的知识爆炸。归结方法的知识爆炸。 控制策略的目的：控制策略的目的： 归结点尽量少。归结点尽量少。 控制策略的原则：控制策略的原则： 仅选择合适的子句间做归结，避免多余的、不必要的仅选择合适的子句间做归结，避免多余的、不必要的 归结式出现，即少做归结仍能导出空子句。归结式出现，即少做归结仍能导出空子句。 0871-50313012021年7月12日星期一 51 / 16 信 息 学 院 人工智能 一种现代方法 控制策略控制策略 删除策略（完备）删除策略（完备

55、） 归类：设两个子句归类：设两个子句C C和和D D，若有置换，若有置换 ，使得，使得 成立则称成立则称 子句子句C C把子句把子句D D归类归类 对子句集对子句集S S归结过程中，当归结式归结过程中，当归结式C C是重言式或是重言式或C C被被S S中子句中子句 所归类时，将所归类时，将C C删除，以缩小搜索范围删除，以缩小搜索范围( (减少比较次数减少比较次数) )。 归结式产生后方能判断是否删除。归结式产生后方能判断是否删除。 删除策略的归结推理是完备的。删除策略的归结推理是完备的。 DC 0871-50313012021年7月12日星期一 52 / 16 信 息 学 院 人工智能 一种

56、现代方法 使用支撑集（完备）使用支撑集（完备） 支撑集：设有不可满足子句集支撑集：设有不可满足子句集S S的子集的子集T T，如果，如果S-TS-T是可满足是可满足 的，则的，则T T是支撑集。是支撑集。 归结过程中，只选取不同时属于归结过程中，只选取不同时属于S-TS-T的子句，在其间进行归的子句，在其间进行归 结，即有一个子句来自于支撑集结，即有一个子句来自于支撑集T T或由或由T T导出的归结式。导出的归结式。 例：例：A1 A1 A2 A2 A3 A3 B B中的中的 B B可作支撑集，每一次参加归结可作支撑集，每一次参加归结 的子句中，至少应有一个是有的子句中，至少应有一个是有 B

57、B所得到的子句或者其后裔。所得到的子句或者其后裔。 支撑集策略的归结是完备的。支撑集策略的归结是完备的。 最容易找到的支撑集是目标子句的非，即最容易找到的支撑集是目标子句的非，即S S B B 控制策略控制策略 0871-50313012021年7月12日星期一 53 / 16 信 息 学 院 人工智能 一种现代方法 控制策略控制策略 语义归结（完备）语义归结（完备） 将子句将子句S S按照一定的语义分成两部分，约定每部分内的子句按照一定的语义分成两部分，约定每部分内的子句 间不允许做归结，还引入文字次序，约定归结时其中的一间不允许做归结，还引入文字次序，约定归结时其中的一 个子句的被归结文字

58、只能是该子句中最大的文字个子句的被归结文字只能是该子句中最大的文字 语义归结策略的归结是完备的。问题是如何寻找合适的语语义归结策略的归结是完备的。问题是如何寻找合适的语 义分类方法，并根据其含义将子句集两个部分中的子句进义分类方法，并根据其含义将子句集两个部分中的子句进 行排序。行排序。 0871-50313012021年7月12日星期一 54 / 16 信 息 学 院 人工智能 一种现代方法 控制策略控制策略 线性归结（完备）线性归结（完备） 从子句集中选取一个作为顶子句从子句集中选取一个作为顶子句C0C0开始归结，所得到的归开始归结，所得到的归 结式结式C Ci i立即同另一子句立即同另一

59、子句B Bi i进行归结得进行归结得C Ci+1 i+1，而 ，而B Bi i属于属于S S或是已或是已 出现的归结式出现的归结式C Cj j(ji)(j H - A - S - H - A - 语义树语义树 语义树是语义树是H H域的图形解释域的图形解释 目的：把每个解释都摊开。语义树中包含原子集的全部元素，目的：把每个解释都摊开。语义树中包含原子集的全部元素， 因此语义树是完全的。每一个直到叶子节点的分支对应因此语义树是完全的。每一个直到叶子节点的分支对应S S的的 一个解释。可以通过对语义树每一个分支来计算一个解释。可以通过对语义树每一个分支来计算S S的真值。的真值。 如果每个基例都为假，则可认为是不可满足的。如果每个基例都为假，则可认为是不可满足的。 0871-50313012021年7月12日星期一 69 / 16 信 息 学 院 人工智能 一种现代方法 失败节点：当（由上）延伸到点失败节点：当（由上）延伸到点N N时，时，I(N)I(N)已表已表 明了明了S S的某子句的某基例为假，但的某子句的某基例为假，但N N以前尚不能判以前尚不能判 定该事实，则称定该事实，则称N N为失败节点。为失败节点。 S= P(x)Q(x), P(f(y), Q(f(y) 封闭语