《人工智能技术简明教程 教学课件 ppt 作者 廉师友 第5章 知识表示与推理》由会员分享，可在线阅读，更多相关《人工智能技术简明教程 教学课件 ppt 作者 廉师友 第5章 知识表示与推理（131页珍藏版）》请在金锄头文库上搜索。
1、第5章 知识表示与推理 5.1 概述 5.2 基于谓词逻辑的机器推理 5.3 基于产生式规则的机器推理 5.4 几种结构化知识表示及其推理 5.5 不确定性知识的表示与推理,5.1 概述 5.1.1 知识及其表示 一些常用的知识表示形式： 一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等。 5.1.2 机器推理 演绎推理、归纳推理和类比推理 不确定性推理和不确切性推理 约束推理、定性推理、范例推理、非单调推理,5.2 基于谓词逻辑的机器推理 基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且
2、这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。,归结演绎推理是基于一种称为归结原理(亦称消解原理principle of resolution)的推理规则的推理方法。归结原理是由鲁滨逊(J.A.Robinson)于1965年首先提出。它是谓词逻辑中一个相当有效的机械化推理方法。归结原理的出现，被认为是自动推理，特别是定理机器证明领域的重大突破。,5.2.1 子句集 定义1 原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句
3、，由r个文字组成的子句叫r文字子句，1文字子句叫单元子句，不含任何文字的子句称为空子句，记为或NIL。 例： PQR P(x,y) Q(x),定义2 对一个谓词公式G，通过以下步骤所得的子句集合S，称为G的子句集。 (1)消去蕴含词和等值词。 (2)缩小否定词的作用范围，直到其仅作用于原子公式。 (3)适当改名，使量词间不含同名指导变元和约束变元。 (4)消去存在量词。 (5)消去所有全称量词。 (6)化公式为合取范式。 (7)适当改名，使子句间无同名变元。 (8)消去合取词，以子句为元素组成集合S。,定理1 谓词公式G不可满足当且仅当其子句集S不可满足。 定义3 子句集S是不可满足的，当且仅
4、当其全部子句的合取式是不可满足的。,5.2.2 命题逻辑中的归结原理 定义 设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分析取起来，记构成的新子句为C12，则称C12为C1,C2的归结式(或消解式)，C1,C2称为其归结式的亲本子句， L1,L2称为消解基。 例5.9 设C1= PQR, C2= QS, 则C1,C2的归结式为 PRS,定理2 归结式是其亲本子句的逻辑结果。 由定理2即得推理规则： C1C2 (C1-L1)(C2-L2) 其中C1,C2是两个子句，L1,L2分别是C1,C2中的文字，且L1
5、,L2互补。 此规则就是命题逻辑中的归结原理。,例3.10 用归结原理验证分离规则和拒取式 A(AB) B (AB) B A 解 A(AB) A( AB) B (AB) B ( AB)( B) A,例5.11 证明子句集 PQ,P,Q 是不可满足的。 证 (1)PQ (2)P (3)Q (4)Q 由(1),(2) (5) 由(3),(4),例5.12 用归结原理证明R是 P,(PQ)R,(SU)Q,U 的逻辑结果。 证 由所给条件得到子句集 S=P, P QR, SQ, UQ,U, R 然后对该子句集施行归结，归结过程用下面的归结演绎树表示（见图51）。由于最后推出了空子句，所以子句集S不可满
6、足，即命题公式 P( P QR)( SQ)( UQ)U R 不可满足，从而R是题设前提的逻辑结果。,图51 例5.12归结演绎树,5.2.3 替换与合一 例： C1=P(x)Q(x) C2=P(a)R(y) 用a替换C1中的x，则得到 C1=P(a)Q(a) C2=P(a)R(y),定义6 一个替换(Substitution)是形如t1/x1,t2/x2,tn/xn的有限集合，其中t1,t2,tn是项，称为替换的分子；x1,x2,xn是互不相同的个体变元，称为替换的分母；ti不同于xi，xi也不循环地出现在tj(i,j=1,2,n)中；ti/xi表示用ti替换xi。若t1,t2,tn都是不含变
7、元的项（称为基项）时，该替换称为基替换；没有元素的替换称为空替换，记作，它表示不作替换。,例如： a/x, g(y)/y ,f(g(b)/z 就是一个替换，而 g(y)/x, f(x)/y 则不是一个替换,因为x与y出现了循环替换。 定义7 设=t1/x1,tn/xn是一个替换，E是一个表达式，把对E施行替换，即把E中出现的个体变元xj(1jn)都用tj替换，记为E，所得的结果称为E在下的例(instance)。,定义9 设S=F1,F2,Fn是一个原子谓词公式集，若存在一个替换，可使F1=F2=Fn，则称为S的一个合一(Unifier)，称S为可合一的。 定义10 设是原子公式集S的一个合一
8、，如果对S的任何一个合一，都存在一个替换，使得 = 则称为S的最一般合一(MostGeneralUnifier)，简称MGU。,例5.14 设S=P(u,y,g(y),P(x,f(u),z)，S有一个最一般合一 =u/x,f(u)/y,g(f(u)/z 对S的任一合一，例如： =a/x,f(a)/y,g(f(a)/z,a/u 存在一个替换 =a/u 使得 =,3.2.4 谓词逻辑中的归结原理 定义12 设C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的两个文字，如果L1和L2有最一般合一，则子句 (C1-L1)(C2-L2)称作C1和C2的二元归结式(二元消解式)，C1和C2称
9、作归结式的亲本子句，L1和L2称作消解文字。,例5.18 设C1=P(x)Q(x),C2=P(a)R(y)，求C1,C2的归结式。 解 取L1=P(x),L2=P(a),则L1与 L2的最一般合一=a/x，于是, (C1-L1)(C2-L2) =(P(a),Q(a)-P(a) (P(a),R(y)-P(a) =Q(a),R(y) = Q(a)R(y) 所以，Q(a)R(y)是C1和C2的二元归结式。,例5.19 设C1=P(x,y)Q(a),C2=Q(x)R(y),求C1,C2的归结式。 解 由于C1,C2中都含有变元x,y，所以需先对其中一个进行改名,方可归结（归结过程是显然的，故从略）。
10、还需说明的是，如果在参加归结的子句内部含有可合一的文字，则在进行归结之前，也应对这些文字进行合一，从而使子句达到最简。例如，设有两个子句： C1=P(x)P(f(a)Q(x) C2=P(y)R(b),定义13 如果子句C中，两个或两个以上的文字有一个最一般合一，则C称为C的因子，如果C是单元子句，则C称为C的单因子。 例5.20 设C=P(x)P(f(y)Q(x), 令=f(y)/x，于是 C=P(f(y)Q(f(y) 是C的因子。,定义14 子句C1,C2的消解式，是下列二元消解式之一： (1) C1和C2的二元消解式; (2) C1和C2的因子的二元消解式; (3) C1的因子和C2的二元
11、消解式; (4) C1的因子和C2的因子的二元消解式。,定理4 谓词逻辑中的消解式是它的亲本子句的逻辑结果。 由此定理我们即得谓词逻辑中的推理规则： C1C2(C1-L1)(C2-L2) 其中C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的文字，为L1与L2的最一般合一。 此规则称为谓词逻辑中的消解原理（或归结原理）。,例5.21 求证G是A1和A2的逻辑结果。 A1: x(P(x)(Q(x)R(x) A2: x(P(x)S(x) G: x(S(x)R(x) 证 我们用反证法，即证明A1A2G不可满足。首先求得子句集S：,(1) P(x)Q(x) (2) P(y)R(y) (3
12、) P(a) (4) S(a) (5) S(z) R(z)( G) 然后应用消解原理，得 (6)R(a) (2),(3),1=a/y (7)R(a) (4),(5),2=a/z (8) (6),(7) 所以S是不可满足的，从而G是A1和A2的逻辑结果。,(A1),(A2),S,例 5.22 设已知： (1)能阅读者是识字的； (2)海豚不识字； (3)有些海豚是很聪明的。 试证明：有些聪明者并不能阅读。 证 首先，定义如下谓词： R(x)：x能阅读。 L(x)：x识字。 I(x)：x是聪明的。 D(x)：x是海豚。,然后把上述各语句翻译为谓词公式： (1) x(R(x)L(x) (2) x(D
13、(x) L(x) 已知条件 (3) x(D(x)I(x) (4) x(I(x)R(x) 需证结论,求题设与结论否定的子句集，得 (1) R(x)L(x) (2) D(y) L(y) (3)D(a) (4)I(a) (5) I(z)R(z),归结得 (6) R(a) (5)，(4)，a/z (7) L(a) (6)，(1)，a/x (8) D(a) (7), (2), a/y (9) (8), (3) 这个归结过程的演绎树如图52所示。,图5-2 例5.22 归结演绎树,定理5 （归结原理的完备性定理）如果子句集S是不可满足的，那么必存在一个由S推出空子句的消解序列。 (该定理的证明要用到Her
14、brand定理，故从略。),5.3 基于产生式规则的机器推理 5.3.1 产生式规则 一般形式： 前件后件 其中, 前件就是前提, 后件是结论或动作,前件和后件可以是由逻辑运算符AND、OR、NOT组成的表达式。 语义: 如果前提满足,则可得结论或者执行相应的动作, 即后件由前件来触发。 所以, 前件是规则的执行条件, 后件是规则体。,例： (1) 如果银行存款利率下调, 那么股票价格上涨。 (2) 如果炉温超过上限, 则立即关闭风门。 (3) 如果键盘突然失灵, 且屏幕上出现怪字符, 则是病毒发作。 (4) 如果胶卷感光度为200, 光线条件为晴天, 目标距离不超过5米, 则快门速度取250
15、, 光圈大小取f16。,5.3.2 基于产生式规则的推理模式,A B A B,5.3.3 产生式系统 1系统结构 产生式规则库 推理机 动态数据库。,图 6-2 推理机的一次推理过程,3控制策略与常用算法 1) 正向推理 正向推理算法一： 步1 将初始事实/数据置入动态数据库。 步2 用动态数据库中的事实/数据, 匹配/测试目标条件, 若目标条件满足, 则推理成功, 结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实/数据, 将匹配成功的规则组成待用规则集。 步4 若待用规则集为空, 则运行失败, 退出。 步5 将待用规则集中各规则的结论加入动态数据库, 或者执行其动作, 转步2。,例 动物分类问题的产生式系统描述及其求解。 r1： 若某动
