第5章 知识表示与推理 5.1 概述 5.2 基于谓词逻辑的机器推理 5.3 基于产生式规则的机器推理 5.4 几种结构化知识表示及其推理 5.5 不确定性知识的表示与推理,5.1 概述 5.1.1 知识及其表示 一些常用的知识表示形式： 一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等。 5.1.2 机器推理 演绎推理、归纳推理和类比推理 不确定性推理和不确切性推理 约束推理、定性推理、范例推理、非单调推理,5.2 基于谓词逻辑的机器推理 基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。,归结演绎推理是基于一种称为归结原理(亦称消解原理principle of resolution)的推理规则的推理方法。归结原理是由鲁滨逊(J.A.Robinson)于1965年首先提出。它是谓词逻辑中一个相当有效的机械化推理方法。归结原理的出现，被认为是自动推理，特别是定理机器证明领域的重大突破。,5.2.1 子句集 定义1 原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，由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是不可满足的，当且仅当其全部子句的合取式是不可满足的。,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,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不可满足，即命题公式 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都是不含变元的项（称为基项）时，该替换称为基替换；没有元素的替换称为空替换，记作，它表示不作替换。,例如： 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的一个合一，如果对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称作归结式的亲本子句，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，所以需先对其中一个进行改名,方可归结（归结过程是显然的，故从略）。 还需说明的是，如果在参加归结的子句内部含有可合一的文字，则在进行归结之前，也应对这些文字进行合一，从而使子句达到最简。例如，设有两个子句： 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的二元消解式; (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) 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(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推出空子句的消解序列。 (该定理的证明要用到Herbrand定理，故从略。),5.3 基于产生式规则的机器推理 5.3.1 产生式规则 一般形式： 前件后件 其中, 前件就是前提, 后件是结论或动作,前件和后件可以是由逻辑运算符AND、OR、NOT组成的表达式。 语义: 如果前提满足,则可得结论或者执行相应的动作, 即后件由前件来触发。 所以, 前件是规则的执行条件, 后件是规则体。,例： (1) 如果银行存款利率下调, 那么股票价格上涨。 (2) 如果炉温超过上限, 则立即关闭风门。 (3) 如果键盘突然失灵, 且屏幕上出现怪字符, 则是病毒发作。 (4) 如果胶卷感光度为200, 光线条件为晴天, 目标距离不超过5米, 则快门速度取250, 光圈大小取f16。,5.3.2 基于产生式规则的推理模式,A B A B,5.3.3 产生式系统 1系统结构 产生式规则库 推理机 动态数据库。,图 6-2 推理机的一次推理过程,3控制策略与常用算法 1) 正向推理 正向推理算法一： 步1 将初始事实/数据置入动态数据库。 步2 用动态数据库中的事实/数据, 匹配/测试目标条件, 若目标条件满足, 则推理成功, 结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实/数据, 将匹配成功的规则组成待用规则集。 步4 若待用规则集为空, 则运行失败, 退出。 步5 将待用规则集中各规则的结论加入动态数据库, 或者执行其动作, 转步2。,例 动物分类问题的产生式系统描述及其求解。 r1： 若某动