人工智能课件知识的表示与推理

1、第2章 知识的表示与推理(2)第三节 经典逻辑推理 经典逻辑推理是根据经典逻辑的逻辑规则进行的一种推理，又称为机械-自动定理证明，主要有自然演绎推理、归结演绎推理和与/或形演绎推理等方法。第三节 经典逻辑推理一、基本概念1、什么是推理 从已知事实出发，通过运用已掌握的知识，找出其中蕴含的事实，或归纳出新的事实，该过程称为推理。 AI中称为推理机。第三节 经典逻辑推理2、推理方式及分类(1) 演绎推理、归纳推理、默认推理(2) 确定性推理、不确定性推理(3) 单调推理、非单调推理(4) 启发推理、非启发推理(5) 基于知识的推理、统计推理、直觉推理第三节 经典逻辑推理3、推理的控制策略推理的控制

2、策略主要包括：推理方向、搜索策略、冲突消解、求解策略和限制策略。4、推理方向(1).正向推理(2).逆向推理(3).双向推理从已知事实出发的推理。也称为数据驱动的推理。 以某个假设目标作为出发点的一种推理。也称为目标驱动的推理。 基本思想：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明假设是成立的。开始把已知事实放入DBDB中是否包含问题的解成功、退出KB中是否有可用知识选KB中可用知识到KSKS为空按冲突消解策略，从KS选知识推出新事实将新事实加入DBYNNYY用户可补充新事实Y失败、退出NN把用户提供的新事实放入DBY正向推理流程第三节 经典逻辑推理5、模式匹

3、配 指两个知识模式的比较。 确定性匹配(完全匹配) 模式匹配 不确定性匹配(具有一定的相似性) 在进行模式匹配之前，相比较的两个模式必须转换为统一的格式。 方法：采用代换第三节 经典逻辑推理定义(代换) 代换是形如 t1/x1,t2/x2,tn/xn的有限集合。其中t1,t2,t3是项；x1,x2,xn是互不相同的变元；ti/xi表示用ti代换xi，不允许ti和xi相同，也不允许变元xi循环出现在另一个xj中。例如： a/x,f(b)/y,w/z - 是一个代换 g(y)/x, f(x)/y - 不是一个代换第三节 经典逻辑推理定义(复合)：设 = t1/x1,t2/x2,tn/xn = u1

4、/y1,u2/y2,um/ym是两个代换，则该两个代换的复合，也是一个代换，它是从 t1/x1,t2/x2,tn/xn, u1/y1,u2/y2,um/ym中删除如下两种元素： ti/xi 当ti = xi ui/yi 当yix1,x2,xn后剩下的元素所构成的集合，记为。例如，设 = f(y)/x, z/y = a/x, b/y, y/z 则 = f(b)/x, y/z 第三节 经典逻辑推理定义(合一)： 设有公式集F=F1,F2,Fn，若存在一个代换，使得: F1 = F2=Fn则称为公式集 F 的一个合一，称F1,Fn是可合一的。定义(最一般合一)： 设是公式集F的一个合一，如果对于任一

5、个，都存在一个代换，使得, = 则称是一个最一般合一。第三节 经典逻辑推理 最一般合一是唯一的，如果用最一般合一代换那些可合一的谓词公式，可使它们变成完全一致的谓词公式。求取最一般合一的算法：(1) 设k=0,Fk=F, k=；(2) 若Fk只含一个表达式，则停止，k就是；(3) 找出Fk的差异集Dk；(4) 若Dk中存在元素xk和tk,其中，xk是变元，tk是项，且xk不在tk中出现，则置： k+1 = k tk/xk Fk+1 = Fktk/xk、 k = k+1 转(2)(5)算法停止，F的最一般合一不存在。第三节 经典逻辑推理例、设，F=P(a,x,f(g(y), P(z,f(z),f

6、(u) 求F的最一般合一。(1) 0=,F0=F;(2) 差异集 D0 = a,z;(3) 1= 0 a/z = a/z ; F1= P(a,x,f(g(y), P(a,f(a),f(u) (4) D1 = x, f(a) (5) 2= 1 f(a)/x = a/z,f(a)/x ; F2 = F1 f(a)/x = P(a,f(a), f(g(y), P(a,f(a),f(u) ;第三节 经典逻辑推理(6) D3 = g(y),u (7) 3= 2 g(y)/u = a/z,f(a)/x, g(y)/u ;(8) F3 = F2 g(y)/u = P(a,f(a), f(g(y)。最一般合一

7、为： a/z,f(a)/x, g(y)/u 第三节 经典逻辑推理6、冲突消解在推理过程中，可能出现下列三种情况：(1) 已知事实不能与知识库中的任何知识匹配；(2) 已知事实恰好与知识库中的一个知识匹配；(3) 已知事实与知识库中的多个知识匹配。第三节 经典逻辑推理冲突消解的一般策略：(1) 按针对性排序(2) 按已知事实的新鲜性排序(3) 按匹配度排序(4) 按领域问题的特点排序(5) 按上下文限制排序(6) 按条件个数排序(7) 按冗余限制排序第三节 经典逻辑推理二、自然演绎推理 从一组已知的事实出发，直接运用经典逻辑的推理规则推出结论的过程。第三节 经典逻辑推理例1、设已知事实 A B

8、AC B C D D Q求证：Q证明： A,AC =C P规则及假言推理 B,C=B C 引入合取词 B C,B C D=D T规则及假言推理 D,D Q = Q T规则及假言推理第三节 经典逻辑推理例2、设已知如下事实(1) 凡是容易的课程小王都喜欢(2) C班的课程都是容易的(3) ds是C班的一门课程求证：小王喜欢ds课程证明： 定义谓词: Easy(x): x是容易的 Like(x,y): x喜欢y C(x): x是C班的一门课程。第三节 经典逻辑推理用定义的谓词表示上述事实： Easy(x)Like(Wang,x) (x) ( C(x) Easy(x) ) C(ds)问题：Like(

9、Wang,ds) (x) ( C(x) Easy(x) ) C(y) Easy(y) C(ds),C(y) Easy(y) =Easy(ds) Easy(ds), Easy(x) Like(Wang,x)=Like(Wang,ds)第三节 经典逻辑推理三、归结演绎推理 定理证明的实质：PQ的永真性 研究表明：要证明PQ永真，只要证明P Q不可满足即可。 海伯伦域； 鲁滨逊归结原理。第三节 经典逻辑推理1、子句文字：在谓词逻辑中，将原子谓词公式及其否定统称为文字。定义：任何文字的析取式称为子句。定义：不包含任何文字的子句称为空子句。 空子句因为不能做任何解释，所以，空子句是永假的，不可满足的。定

10、义：由子句构成的集合称为子句集。 谓词逻辑中，任何谓词公式都可变为子句集。第三节 经典逻辑推理将谓词公式化成子句集的方法：样例：(x)(y)P(x,y) (y)( Q(x,y) R(x,y) ) )(1)消取谓词公式中的“”和“ ”；利用公式：P Q PQ P Q (PQ) (PQ)样例变为： (x)(y)P(x,y)(y)(Q(x,y)R(x,y) ) )第三节 经典逻辑推理(2)把“”移到紧靠谓词的位置；利用公式： ( P) P ( PQ) PQ ( PQ) P Q (x) P (x)P (x) P (x)P样例: (x)(y)P(x,y)(y)(Q(x,y)R(x,y) ) )变为： (

11、x)( (y)P(x,y) (y)( Q(x,y)R(x,y) ) )第三节 经典逻辑推理(3)重新命名变元，使不同量词约束的变元有不同的名字；样例： (x)( (y)P(x,y) (y)( Q(x,y)R(x,y) ) )变为： (x)( (y)P(x,y) (z)( Q(x,z)R(x,z) ) )第三节 经典逻辑推理(4)消去存在量词。有两种情况：一种是存在量词不出现在全称量词的辖域内，此时，只要用一个新的个体变量替换该存在量词约束的变元即可；另一种情况是存在量词位于一个或多个全称量词的辖域内，此时，用Skolem函数替换受该存在量词约束的变元；例如， (x1) (x2) (xn)(y)

12、P(x1,x2,xn,y)设， Skolem函数为f(x1,x2,xn)则， (x1) (x2) (xn) P(x1,x2,xn,f(x1,xn)样例: (x)( (y)P(x,y) (z)( Q(x,z)R(x,z) ) )变为：(x)( P(x,f(x) ( Q(x,g(x)R(x,g(x) ) ) )第三节 经典逻辑推理(5)把全称量词移到公式的左边；(6)将公式化为Skolem标准形，即 (x1) (x2) (xn) M其中M是合取式；利用公式：P( Q R ) ( P Q) ( P R)样例： (x)( P(x,f(x) ( Q(x,g(x)R(x,g(x) ) ) )变为： (x)

13、( (P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x) ) ) )第三节 经典逻辑推理(7)消去全称量词； 样例变为： (P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x) ) ) (8)对变元更名，使不同子句的变元不同名；样例变为： (P(x,f(x)Q(x,g(x)(P(y,f(y)R(y,g(y) ) ) (9)消去合取词，即得子句集。 子句集： P(x,f(x)Q(x,g(x) ) P(y,f(y)R(y,g(y) ) 第三节 经典逻辑推理2、海伯伦理论 为判定子句集的不可满足性，需要对子句集中的子句进行判定。为判定一个子句的不可满足性，需要对个体域

14、上的一切解释进行判定，只有当子句对任何非空个体域上的任何一个解释都是不可满足时，才能判定该子句的不可满足性，这是很烦琐的。为此，海伯伦构造了一个特殊的域，并证明只要对这个特殊域上的一切解释进行判定，就可得知子句是否不可满足，这个特殊域称为海伯伦域。第三节 经典逻辑推理定义：设S为子句集，则按下述方法构造的域H称为海伯伦域，简记为H域。 (1)令 H0是S中所有个体常量的集合，若 S中不包含个体常量，则令 H0=a,其中,a为任一个体常量; (2)令Hi+1=HiS中所有n元函数f(x1xn)|xj是Hi中的元素例，求子句集S=P(x) Q(x),R(f(y)的 H域 H0=a H1=a,f(a

15、) H2=a,f(a),f(f(a) H3 = a,f(a),f(f(a),f(f(f(a) H = a,f(a),f(f(a),f(f(f(a), 第三节 经典逻辑推理定理：子句集S不可满足的充要条件是S对H域上的一切解释均为假。定理：子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S。第三节 经典逻辑推理3、归结原理基本思想：检查子句集S中是否包含空子句，若包含，则S不可满足；若不包含，则在S中选择合适的子句进行归结，直到归结出空子句。定义:若P是原子谓词公式，称P与P为互补文字。第三节 经典逻辑推理(1)、命题逻辑中的归结原理定义：设C1和C2是子句集中的任意两个子句，如果C

16、1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并将两个子句中余下的部分析取，构成一个新子句C12，则称该过程为归结，C12为C1和C2的归结式，C1和C2为C12的亲本子句。第三节 经典逻辑推理例1、设 C1= P V Q V R C2= Q V S则 L1=Q，L2= Q，通过归结得： C12= P V R V S例2、设 C1 = P C2 = P则 C12 = NIL第三节 经典逻辑推理定理：归结式C12是其亲本子句 C1与C2的逻辑结论。即 C1 C2 =C12推论1：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2后得到

17、新子句集S1,则由S1的不可满足性可推出S的不可满足性。推论2：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若把C12加入S中，得到新子句集S2,则S2与S的不可满足性是等价的。第三节 经典逻辑推理(2)、谓词逻辑中的归结原理 在谓词逻辑中，由于子句含有变元，因此，在归结前，需要先用最一般合一对变元进行代换。例如，设 C1 = P(x) V Q(x) C2 = P(a) V R(y)最一般合一=a/x则 C1 = P(a) V Q(a) C2 = P(a) V R(y)则 C12 = Q(a) V R(y)第三节 经典逻辑推理定义: 设C1与C2是两个没有相同变元的子句，L1和L

18、2分别是C1和C2中的文字，若是L1和L2的最一般合一，则称 C12=( C1- L1 ) ( C2- L2 )为C1和C2的二元归结式，L1和L2为归结式上的文字。第三节 经典逻辑推理例、设 C1 = P(a) V Q(x) V R(x) C2 = P(y) V Q(b)选 L1 = P(a), L2 = P(y) 则= a/y C12=( C1- L1 ) ( C2- L2 ) =( P(a), Q(x),R(x) P(a) ( P(a),Q(b) P(a) ) =(Q(x),R(x) ( Q(b) = Q(x) V R(x) V Q(b)第三节 经典逻辑推理注意：如果在参加归结的子句内部

19、含有可合一的文字，则在进行归结前应对这些文字先进行合一。例如， C1 = P(x) V P( f(a) ) V Q(x) C2 = P(y) V R(b)在C1中P(x)和P(f(a)可合一，= f(a)/x 则，C1=P(f(a) V Q(f(a)此时，可对C1和 C2进行归结。若选 L1 = P(f(a) L2 = P(y)则 = f(a) / y c12 = R(b) V Q( f(a) ) 第三节 经典逻辑推理定义：子句C1和C2的归结式是下列二元归结式之一. C1与C2的二元归结式；. C1与C2的因子C2的二元归结式；. C1的因子C1与C2的二元归结式；. C1的因子C11与C2

20、的因子C12的二元归结式。第三节 经典逻辑推理4、归结反演 欲证明(P1 P2 Pn)Q 则只需证明(P1 P2 Pn) Q是不可满足的。 应用归结原理证明定理的过程称为归结反演。证明步骤：(1) 否定Q，把Q加入到公式集 F, Q (2) 把公式集 F, Q 化为子句集S(3) 应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式并入S中。反复进行，直到出现空子句。第三节 经典逻辑推理例1、已知F: (x)( (y) (A(x,y) B(y)(y)(C(y) D(x,y) ) )G: (x)C(x)(x) (y)(A(x,y) B(y) )求证：G是F的逻辑结论证明，将 F和G化

21、为子句集：(1) A(x,y) V B(y) V C(f(x) ) (2) A(x,y) V B(y) V D(x,f(x) )(3) C(z)(4) A(a,b)(5) B(b)FG第三节 经典逻辑推理进行归结：(6) A(x,y) V B(y) 由(1)和(3)归结,f(x)/z (7) B(b) 由(4)和(6)归结,a/x,b/y (8) NIL 由(5)和(7)归结第三节 经典逻辑推理例2、某公司招聘工作人员，A,B,C三人应试，经面试后公司表示如下想法：(1) 三人中至少录取一人。(2) 如果录取A，而不录取B，则一定录取C。(3) 如果录取B，则一定录取C。求证：公司一定录取C。

22、证明：用P(x)表示录取x则公司的想法用谓词表示为:(1) P(A) V P(B) V P(C)(2) P(A) P(B)P(C)(3) P(B) P(C)第三节 经典逻辑推理把求证问题否定，并用谓词表示：(4) P(C)将上述公式化为子句集. P(A) V P(B) V P(C). P(A) V P(B) V P(C). P(B) V P(C). P(C)归结：. P(B)VP(C) 和归结. P(C) 和归结. NIL 和归结第三节 经典逻辑推理5、应用归结原理求取问题的答案求解步骤：(1) 把已知前提用谓词公式表示出来，并且化为相应的子句集，设为S;(2) 把待求解的问题用谓词公式表示出

23、来，否定后与谓词 Answer构成析取式，并化为子句集，并入S，得到S；(3) 对S进行归结；(4) 若得到归结式 Answer，则答案包含在Answer中。第三节 经典逻辑推理例、已知 F1: 王 (Wang) 先生是小李的老师； F2: 小李与小张是同班同学； 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) )第三节 经典逻辑推理问

24、题：G: (x)T(x,Zhang)Answer(x)化为子句集：(1) T(Wang,Li)(2) C(Li, Zhang )(3) C(x,y) T(z,x) T(z,y)(4) T(u,Zhang)Answer(u)归结：(5) C(Li,y)T(Wang,y) (1),(3)归结(6) C(Li,Zhang)Answer(Wang) (4),(5)归结(7) Answer(Wang) (2),(6)归结则，张的老师是Wang。第三节 经典逻辑推理6、归结策略 对子句进行归结的关键是选择可进行归结的一对子句。 删除策略 归结策略 限制策略第三节 经典逻辑推理(1)、用计算机实现归结的一般

25、过程 设S = C1,C2,C3,C4, 从子句C1开始，逐个与C2,C3,比较，看哪个可以归结，若可以，就求出归结式。然后C2与C3,C4,进行比较，直到所有子句进行两两比较完毕。得到的归结式称为第一级归结式。 从C1开始，用S中的子句与第一级归结式逐个比较、归结，得到第二级归结式。 从C1开始，用S中的子句和第一级归结式子句与第二级归结式逐个比较，得到第三级归结式。 如此反复，直到得到空子句。第三节 经典逻辑推理(2)、删除策略 纯文字删除法 如果某文字L在子句集中不存在与之互补的文字，则称为纯文字。 重言式删除法 如果一个子句中同时包含互补的文字，则称为重言式。 包孕删除法 对子句C1和

26、C2，如果存在一个代换，使得 C1 C2则称C1包孕于 C2。第三节 经典逻辑推理(3)、支持集策略 每一次归结时，亲本子句中至少应有一个是由目标公式的否定所得得子句，或者是他们得后裔。 完备的。(4)、线性输入策略 参加归结的两个子句中必须至少有一个是初始子句集中的子句。(5)、单文字策略 如果一个子句中只包含一个文字，则称为单文字子句。 参加归结的子句中必须至少有一个是单文字子句。第三节 经典逻辑推理(6)、祖先过滤策略 归结的子句必须满足下列条件之一： C1和C2中至少有一个是初始子句集中的子句。 如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先。 完备的。第三节 经典逻辑推

27、理7、归结原理的应用基于归结法的问答系统基于归结的自动程序综合基于归结的问题求解方法基于归结法的问答系统 实质：构造性证明方法。 思路：对一个问题，先证明一个与回答问题语句中提问项匹配的一般语句，然后再找某个具体的匹配值，该值即为问题的答案。基于归结法的问答系统例：If Fido goes whereven John goes and if John is at school, where is Fido? 问题的谓词公式表示： 事实(前提)： (x) ( At(John,x) At( Fido,x ) ) At(John,School) 目标公式： (x)At(Fido,x)基于归结法的问答

28、系统 先证明结论是前提的逻辑结论：化成的子句集:前提：At(John,x)At(Fido,x) At(John,School)结论： At(Fido,x)基于归结法的问答系统At(Fido,x)At(John,x)At(Fido,x)At(John,x)At(John,school)Nil归结反演树代换：x/school基于归结法的问答系统 再找出一个x的实例：方法：(1) 用一个重言式来取代目标公式的否定，例如，该例的为： At(Fido,x) At(Fido,x)(2) 按反演树的构造进行归结，给出重言式代替目标否定子句后的证明树，这时根子句不为空；(3)用根部的子句作为问题的回答。基于归

29、结法的问答系统At(Fido,x) At(Fido,x)At(John,x)At(Fido,x)At(John,x) At(Fido,x) At(John,school)At(Fido,school) 代换：x/school答案：school修正的证明树基于归结法的问答系统提取回答的一般过程： 提取回答过程中应考虑的问题：（1）回答中出现Skolem函数的情况 例1. 对所有的x,y，如果x是y的父亲，y是z的父亲，则x是z的祖父。每一个人都有一个父亲。询问：是否存在x和y,x是y的祖父？ 事实： (x) (y)(P(x,y)P(y,z) G(x,z ) ) (y) (x)P(x,y) 目标公

30、式： (x) (y)G(x,y)基于归结法的问答系统G(u,v)P(x,y)P(y,z) G(x,z)P(u,y) P(y,z) P(f(w),w)P(u,f(v)P(f(w),w)Nil反演树基于归结法的问答系统G(u,v)G(u,v)P(x,y)P(y,z) G(x,z)P(u,y) P(y,z)G(u,y)P(f(w),w)P(u,f(v) G(u,v)P(f(w),w)G(f(f(v),v)修正的证明树基于归结法的问答系统（2）目标公式是析取范式的情况 例2. 事实：A(x)F(x) G(f(x) ) F(x)B(x) F(x)C(x) G(x)B(x) G(x)D(x) A(g(x)

31、F(h(x) )目标： (x) (y)(B(x)C(x)(D(y)B(y)基于归结法的问答系统则，目标否定后的子句： B(x) C(x) ， D(y) B(y)在这种情况下构造的重言式是： B(x) C(x) ( B(x) C(x) ) D(y) B(y) ( D(y) B(y) )( B(x) C(x) )和( D(y) B(y) )当成单文字来处理。基于归结法的问答系统（3）目标公式含有全称量词量化的情况 例3. 对所有的x, x是p(x)的孩子。对所有的x,y，如果x是y的孩子，则y是x的父亲。询问：对任何一个x，谁是x的父亲？ 事实： (x)C(x,p(x) ) (x) (y)( C(

32、x,y)P(y,x) ) 目标： (x) (y)P(y,x)基于归结法的问答系统子句集： C(x1,P(x1), C(x2,y1)P(y1,x2), P(y2,A) 其中，A是化简目标否定式消去存在量词时引进的S函数。C(x2,y1)P(y1,x2)P(y2,A)P(y2,A)C(A,y2)P(y2,A)C(x1,p(x1)P(p(A),A)修正的证明树基于归结法的问答系统提取问题的步骤：(1)使用某种策略求出一个归结反演树，树中对合一集加上标记。(2)目标公式否定式化简得到的子句中，对出现的任一S型函数均以新变量置换。(3)根据目标公式否定式的子句，构造重言式。(4)按反演树结构，将目标否定

33、式子句用永真式替代，且每次合一文字集不变，生成出修正的证明树。(5)根部子句就作为所要提取的回答问题。基于归结的自动程序综合基本思想：要生成的程序x(输入)y(输出)R:xy 设，谓词关系R由某个公理系统定义，要构造程序使用的基本函数由另一些公理定义。如果某个定理证明系统能够证明目标公式：(x)(y)R(x,y)是公理集的逻辑结论，则在应用提取回答的过程中，这个定理证明系统能生成所要的程序，即在回答的语句中，y将以基本函数的组合形式给出，这些函数的组合就是要生成的程序。基于归结的自动程序综合例子、生成一个实现数字排序的程序。 输入x：一个数字表x 输出y：一个数字递增的有序表。 构造程序的函数

34、： car(x):返回x的第一个元素。 cdr(x):返回除x的第一个元素以外的剩余表。 cons(e,x):返回元素e加到表x之前的新表。 merge(e,l):返回元素e插入到已排序表l中组成的一个新有序表。基于归结的自动程序综合引入的公理：(1) (x)(y)(R(x,y)(S(y)I(x,y)(S(y)I(x,y) R(x,y) ) )(2) (x) (y) (u)( I(x,y) I(cons(u,x),merge(u,y)(3) I(nil,nil)(4) (x) (y)( S(y) S(merge(x,y) ) )(5) S(nil)S(y)表示表y是一个有序表，I(x,y)表示

35、x表和y表，元素数目相同但排序不同。基于归结的自动程序综合公式化简后的子句集：(1a) R(x,y)S(y)(1b) R(x,y)I(x,y)(1c) S(y) I(x,y) R(x,y)(2) I(x,y) I(cons(u,x),merge(u,y) )(3) I(nil,nil)(4) S(y) S(merge(x,y) )(5) S(nil)证明的目标公式： (x)(y)R(x,y)基于归结的自动程序综合证明（归纳法）：(1) x的长度 n = 0此时，目标公式为 (y)R(nil,y)。否定式: (y)R(nil,y)R(nil,y)S(y) I(x,y) R(x,y)S(y) I(

36、nil,y)S(nil)I(nil,nil)I(nil,y)NIL反演树由此可构造证明树，得到根部的回答是：R(nil,nil)基于归结的自动程序综合(2) x为非空表假设：对任一非空表x，cdr(x)可以排序，即可以认为有某种排序函数“Sort”具有能够实现对小表排序的功能，因此，可得归纳假设的子句形：R(cdr(x),Sort(cdr(x)。要证明(x)(y)R(x,y)，须使用关系式： (x)(cons(car(x),cdr(x) = x )引入事实：(x) (y)(R(cons(car(x),cdr(x),y)R(x,y)因此，有：R(cons(car(x),cdr(x),y)R(x,

37、y)目标公式的否定为：R(a,y)基于归结的自动程序综合则根据修正的证明树可得： R(a,merge(car(a),sort(cdr(a)将Skolem函数用新变量替代，可得 R(x,merge(car(x),sort(cdr(x)合并以上情况，有 if x = nil then nil Sort = else merge(car(x),sort(cdr(x)基于归结的问题求解方法例、猴子和香蕉问题香蕉箱子猴子acb基于归结的问题求解方法初始状态：S0： ONBox At(Box,b) At(Monkey,a) HB谓词的含义：ONBox：当猴子在箱顶时取真；HB：当猴子那到香蕉时取真；At：

38、当y位于x时取真。目标状态：HB操作符：goto(u) P：ONBox(x)At(Monkey,x) D：At(Monkey,x) A：At(Monkey,u)基于归结的问题求解方法pushbox(v) P：ONBox(x)(At(Monkey,x)At(box,x) ) D：At(Monkey,x)，At(box,x) A：At(Monkey,v)，At(box,v)climbbox P：ONBox(x)(At(Monkey,y)At(box,x) ) D：ONBox A：ONBoxgrasp P：ONBoxAt(box,c ) D：HB A：HB基于归结的问题求解方法一种求解方法：状态空间

39、谓词求解方法： 引入状态变量s，以说明谓词应用的具体状态条件。如，初始状态可表示为： ONBox(s), At(Box,b,s),At(Monkey,a,s),HB(s) 规则也应用谓词表示。基于归结的问题求解方法(1) ONBox(s)(2) (x)(s)(ONBox(s)At(box,x,pushbox(x,s)(3) (s)(ONBox(climbbox(s)(4) (s)(ONBox(s)At(box,c,s)HB(grasp(s)(5) (x) (s)(At(box,x,s)At(box,x,climbbox(s)(6) (s)HB(s)基于归结的问题求解方法为求解问题，将上式化为子

40、句集，根据归结反演树，构造修正证明树，可得，问题的答案： HB(grasp(climbbox(pushbox(c,s) ) ) )第四节 规则演绎系统规则演绎系统的推理：正向推理、逆向推理、双向推理正向推理：从已知的事实出发，通过运用规则，得到问题(目标)的一致解图。逆向推理：从目标出发，反向运用规则，得到与已知事实匹配的一致解图。第四节 规则演绎系统一、规则正向演绎系统1、事实表达式的与/或形变换及其树形表示 在正向推理中，要求已知事实用不含蕴涵符号“”的与/或形表示。 把一个公式变换为与/或形的一般步骤：(1)消去公式中的“”；(2)把“”移到紧靠谓词的位置上；(3)重命名变元，使不同量词

41、约束的变元有不同的名字；(4)用Skolen函数消去存在量词；(5)消去全称量词，且使各合取式中的变元不同名。第四节 规则演绎系统例如，有事实表达式 (x)(y)Q(y,x) ( R(y) V P(y) ) S(x,y)得到 Q(z,a) R(y) P(y) V S(a,y) 事实表达式的与/或形可以用一棵与/或树表示出来。 上例的与/或树为：第四节 规则演绎系统Q(z,a) R(y) P(y) V S(a,y) Q(z,a) R(y) P(y) V S(a,y)R(y) P(y)S(a,y) R(y) P(y)注意：析取关系具有连接符(一条弧)，合取关系没有连接符。第四节 规则演绎系统与/或

42、树的一个特点： 把用“连接符”连接的节点看成具有“与”关系，把不用“连接符”连接的节点看成具有“或”关系，则由叶节点所组成的公式： Q(z,a) R(y) V S(a,y) P(y) V S(a,y)恰好是由原表达式化成的子句集合。第四节 规则演绎系统2、F规则的表示形式 要求F规则具有下列形式： L W其中，L是文字，W是与或形。3、目标公式的表示形式 要求目标公式用子句表示。第四节 规则演绎系统4、推理过程(1)用与或树把事实表示出来；(2)用F规则的左部和与或树的叶节点进行匹配，并将匹配成功的F规则加入到与或树中；(3)重复(2)，直到产生一个含有以目标节点作为终止节点的解图为止。第四节

43、 规则演绎系统例1、设已知事实为 A V B F规则为： r1: AC D r2: BE G求证： C V G第四节 规则演绎系统A V BA B A C D C B E G G 目标匹配F规则匹配已知事实推理过程第四节 规则演绎系统例2、设已知事实为 P(a) V Q(a) R(a) F规则为： r1: P(x)S(x) r2: Q(y)N(y)求证： S(z) V N(z)第四节 规则演绎系统 P(a) V Q(a) R(a) P(a)Q(a) R(a) P(x)S(a)S(z)Q(a)R(a)Q(y)N(a)N(z)a/zr1a/xa/yr2a/z推理过程第四节 规则演绎系统二、规则逆向

44、演绎系统1、目标表达式的与/或形变换及其树形表示 在逆向推理中，要求目标公式用与/或形表示。2、B规则的表示形式 要求B规则具有下列形式： W L其中，L是文字，W是与或形公式 特别的，当W ( L1 L2)时，有 W L1 ， W L2第四节 规则演绎系统3、已知事实的表示形式 要求已知事实是文字的合取式。4、推理过程(1)用与或树把目标公式表示出来；(2)用B规则的右部和与或树的叶节点进行匹配，并将匹配成功的B规则加入到与或树中；(3)重复(2)，直到产生一个终止在事实节点上的一致解图为止。第四节 规则演绎系统三、规则双向演绎系统 正向推理中，要求目标公式是文字的析取式，逆向时，要求事实是

45、文字的合取式，这些均存在一定的局限性，为充分发挥各自的长处，可进行双向推理。 双向推理的关键是终止条件，当进行正、反两方推理时，只有它们对应的叶节点都可合一时，推理才能结束。第四节 规则演绎系统四、代换的一致性和剪枝策略1、代换的一致性定义：设代换集合 =1, 2, n中第i个代换为 i=ti1/xi1,ti2/xi2,tim/xim 则代换集是一致的充要条件是如下两个元组： T=t11,t12,t21,t22,tnm X=x11,x12,x21,x22,xnm 可合一。第四节 规则演绎系统2、剪枝策略基本思想：每当选用一条规则时，就进行一次一致性检查，如果当前的部分解图是一致的，则继续扩展，

46、否则就放弃该规则而选用其他的规则。第四节 规则演绎系统五、与或图的搜索搜索策略盲目搜索启发式搜索与或图的搜索一些概念:n0n1n2n3n4n5n6n8n7连接符：节点间的连线。规定k-连接符号是从一个父节点指向一组k个后继节点的节点集。例如，节点n0有两个连接符：1-连接符指向n1；2-连接符指向节点集n4,n5根节点：没有父节点的节点。端节点(叶节点)：没有后继节点的节点。终节点：对应本原问题的节点。与或图的搜索可解节点 终节点是可解节点； 若非终节点有“或”子节点，当且仅当其子节点是一个可解节点时，该非终节点才是可解节点。 若非终节点是“与”子节点，当且仅当其子节点均能解时，该非终节点才是

47、可解节点。不可解节点 没有后裔的非终节点是不可解节点； 若非终节点有“或”子节点，当且仅当其所有的子节点均是不可解节点时，该非终节点才不可解。 若非终节点是“与”子节点，当至少其一个子节点不可解时，该非终节点才不可解。与或图的搜索解图 一个与或图G中，从节点n到节点N的解图记为G， G是G的子图。 若n是N的一个元素，则G由单一元素组成； 若n是指向节点n1,n2,nk的外向连接符K，使得每一个ni到N有一个解图， 则G由节点n，连接符K，及n1,n2,nk中的每一个节点到N的解图所组成； 否则 n 到 N 不存在解图。与或图的搜索n0n1n2n3n4n5n6n8n7n0n1n3n5n6n8n

48、7一个解图原图与或图的搜索耗散值的计算 设连接符的耗散值规定为，K-连接符的耗散值 = K，若解图的耗散值记为k(n,N)，则递归定义如下： 若n是N的一个元素，则k(n,N) = 0； 若n有一个外连接符，指向后继接点n1,n2,nk，并设该连接符的耗散值为Cn，则 k(n,N)=Cn + k(n1,N)+ +k(nk,N)耗散值计算示例n0n1n3n5n6n8n7n8n700n52n62n36n17n08与或图的启发式搜索算法AO*1、与或图搜索的一般过程(1)把原始问题作为初始节点S0，并把它作为当前节点。(2)对当前节点进行扩展。(3)为每个子节点设置指向父节点的指针。(4)选择合适的

49、子节点作为当前节点，反复执行第2步和第3步，在此期间要多次调用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点。一般搜索举例例、设下面的与或图按图中标注的顺序号进行扩展。其中t1,t2,t3,t4节点为可解节点，A,B为不可解节点。12345BAt1t2t3t4一般搜索举例1Open表内容： 1 23 2,3 4t1 3, 4, t1 5B4, t1,5,B At2t1,5,B,A,t2 标注为可解t3t4t1,B,A,t2,t3,t4 可解可解可解与或图的启发式搜索算法AO*2、AO*算法(1). 建立一个搜索图G，G := s，计算q(s) = h(s)， IF Go

50、al(s) Then M(s,Solved);(2). Until s 已标记上Solved, do:(3). Begin(4). G := Find(G);(5). N := G中的任一非终接点;(6). Expand(n),生成子节点集nj, G := Add(nj,G), 计算q(nj) = h(nj),其中 nj G， If Goal(nj) Then M(nj,Solved);与或图的启发式搜索算法AO*(7). S:= n (8). Until S 为空，do:(9). Begin(10). Remove(m,S), mc S(11). 修改m的耗散值q(m): 加指针到min q

51、i(m)的连接符上，或修改 If M(nij,Solved) Then M(m,Solved);(12) IF M(m,Solved)(q(m)q0(m) Then Add(m,S)(13) End(14) End与或图的启发式搜索算法AO*算法分为两个阶段： 第一阶段： 4 6步，完成自顶向下的图生成 操作，先通过标记连接符，找到目前为止最好的一个局部解图，然后对其中的一个非终节点进行扩展，并对其后继节点赋估计耗散值，和加能解标记。 第二阶段： 7 12步，完成自下向上的耗散值修正计算，连接符的标记及节点的能解标记。算法应用举例n0n1n2n3n4n5n6n8n7设各节点的h值如下：h(n0

52、) = 3, h(n1) = 2h(n2) = 4, h(n3) = 4h(n4) = 1, h(n5) = 1h(n6) = 2, h(n7) = h(n8)=0假设 K-连接符的耗散值 = K问题：求右图的解图。n03n12n51n41n04n15n51n41n34n24n05n15n52n41n34n24n62n70n80n05n15n52n41n34n24n62n70n80与或图的启发式搜索算法AO*4、算法应用的若干问题（1）在第6步扩展节点n时，若不存在后继节点，则可在第11步中对m(即n)赋一个高的q值，这个值会传递到s，使得含有节点n的子图具有高的q(s)，从而排除了被当作侯选

53、局部解图的可能。（2）在第5不中如何选出G中的一个非终节点来扩展，一般可以选出一个最可能导致该局部解图耗散值发生较大变化的那个节点先扩展，因为选这个节点先扩展，会促进及时修改局部解图的标记。（3）若sN集存在解图，当h(n)h*(n)且满足单调性，则AO*一定可以找到最佳解图，即具有可纳性。博弈树的搜索1、概述“二人零和、全信息、非偶然”博弈(1) 对垒的A、B双方轮流采取行动，博弈的结果：A方胜、B方败; A方败、B方胜;平局。(2) 在对垒过程中，任何一方都了解当前的格局和过去的历史。(2) 在任何一方采取行动之前都要根据当前的情况，进行得分分析，选择对自己最有利的而对对方最不利的对策，不

54、存在“碰运气”情况。博弈树的搜索博弈过程分析 在博弈过程中，任何一方都希望自己获胜。因此，某一方当前有多个行动方案可供选择时，总是挑选对自己最有利而对对方最不利的那个行动方案。在选择时，主动权操在自己手中，因此，各方案之间是“或”的关系；而当对方选择方案时，对方总是选择对对手不利的方案，因此，对方的选择方案对“自己”来说是“与”的关系。由于轮流走步（选择），因此，博弈过程用图表示时，得到的是一棵“与或”树（博弈树）。博弈树的搜索博弈树的特点(1)博弈的初始格局是初始节点；(2)“与”节点和“或”节点交替出现。自己一方扩展的节点是“或”节点，对方扩展的节点是“与”节点。(3)所有能使自己获胜的节

55、点都是本原问题，相应的节点是可解节点；所有使对方获胜的节点都是不可解节点。博弈树的搜索2、博弈树的极大极小分析法(MAX-Min)(1) 设博弈的双方为A、B，极大极小分析法是为其中的一方寻找一个最优的行动方案。(2) 为了找到当前的最优方案，需要对各个方案可能产生的后果通过打分的方式进行比较。(3) 为了计算得分，需要根据问题的特性定义一个评价函数，用来估算当前博弈树端节点的得分。(4) 当端节点的分值估算出来后，再推算出父节点的得分(到推值),直到开始节点,“与”节点取较小值(Min)，“或”节点取较大值(Max)。如果一个方案获得较大的到推值，则它就是最好的方案。博弈树的搜索23-1-2

56、412233423323博弈树的搜索例1、分钱币游戏。有一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两个小堆，如此进行下去直到有一位选手无法把钱币再分成不相等的两堆时就认输。76-15-24-35-1-14-2-13-2-23-3-14-1-1-13-2-1-12-2-2-13-1-1-1-12-2-1-1-12-1-1-1-1-1N=7时，分钱币游戏状态图MaxMinMaxMinMax博弈树的搜索例2、一字棋游戏。 两位选手在棋盘上轮流摆上各自的棋子，谁先取得三个棋子一线的结果谁就取胜。博弈树的搜索设两位选手分别为A和B，摆放的棋子对应为a,b；设

57、棋局为P，评估函数为e(p)，定义为：(1) 若P是A必胜的棋局，则e(p) = +(2) 若P是B必胜的棋局，则e(p) = -(3) 若P是A胜负未定的棋局，则 e(p) = e(+P) e(-P)其中， e(+P)为有可能使A成为三子一线的棋局； e(-P)为有可能使B成为三子一线的棋局。例如，右面的棋局e(+) = 6e(-) = 4e(P) = 6 4 = 2博弈树的搜索ba例如对右面的棋局，对A，有e(+P) = 6e(-P) = 4e(P) = 6 4 = 2aaaabababababbababaababbaba1010-1-10-10-2121-2-11向前看两步的状态图博弈树

58、的搜索3、-剪枝技术 在Max-Min方法中，总是先生成一定深度的博弈树，然后对端点进行估值，再计算出上层节点的倒推值，效率较低。 由于博弈树具有“与”节点和“或”节点交替出现的特点，如果能边生成节点边计算估值及倒推值，就可能删除一些不必要的节点，从而减少搜索及计算工作量。博弈树的搜索S0S1S2S6S5S4S33523由于从 (S3，S4)S1 := 3 S1 S0 := 3而，S2 不可能大于2，所以，S2以后的分枝可以剪去。 像这样边生成边计算，从而剪去某些分枝的技术成为-剪枝技术。 对于一个“与”节点，它取当前子节点中的最小倒推值为它的倒推值的上界，称此值为值； 对于一个“或”节点，它

59、取当前子节点中的最大倒推值为它的倒推值的下界，称此值为值。博弈树的搜索-剪枝技术的一般规律(1) 任何“或”节点x的值如果不能降低其父节点的值，则对节点x以下的分枝可停止搜索，并使x的倒推值为。这种剪枝称为剪枝。(2) 任何“与”节点x的值如果不能升高其父节点的值，则对节点x以下的分枝可停止搜索，并使x的倒推值为。这种剪枝称为剪枝。博弈树的搜索= 56788(值)剪枝：被剪去博弈树的搜索= 52342(值)剪枝：被剪去例题 考虑下列一段知识：tony,mike和john属于Alpine俱乐部，Alpine俱乐部的每个成员不是滑雪运动员就是登山运动员。登山运动员不喜欢雨，而且任一不喜欢雪的人不是

60、滑雪运动员。Mike讨厌tony所喜欢的一切东西，而喜欢tony所讨厌的一切东西。Tony 喜欢雨和雪。 以谓词演算语句的集合表达这段知识，这些语句要适合一个逆向的基于规则的演绎系统。说明怎样才能回答，有没有Alpine俱乐部的一个成员，他是一个登山运动员，但不是一个滑雪运动员。例题定义谓词：(1) Alpine(x) 表示x是Alpine俱乐部的成员(2) Mounter(x) 表示x是登山运动员(3) Skeer(x) 表示x是滑雪运动员(4) Like(x,y) 表示x喜欢y事实的谓词表示：(1) Alpine(tony)，Alpine(mike)，Alpine(john)(2) Lik