第5章知识表示与推理.

第5章知识表示与推理5.1概述5.2基于谓词逻辑的机器推理5.3基于产生式规则的机器推理5.4几种结构化知识表示及其推理5.5不确定性知识的表示与推理5.1概述5.1.1知识及其表示◆一些常用的知识表示形式：一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等。5.1.2机器推理◆演绎推理、归纳推理和类比推理◆不确定性推理和不确切性推理◆约束推理、定性推理、范例推理、非单调推理5.2基于谓词逻辑的机器推理基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。归结演绎推理是基于一种称为归结原理(亦称消解原理principleofresolution)的推理规则的推理方法。归结原理是由鲁滨逊(J.A.Robinson)于1965年首先提出。它是谓词逻辑中一个相当有效的机械化推理方法。归结原理的出现，被认为是自动推理，特别是定理机器证明领域的重大突破。5.2.1子句集定义1原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，由r个文字组成的子句叫r—文字子句，1—文字子句叫单元子句，不含任何文字的子句称为空子句，记为或NIL。例：P∨Q∨﹁RP(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=﹁P∨Q∨R,C2=﹁Q∨S,则C1,C2的归结式为﹁P∨R∨S定理2归结式是其亲本子句的逻辑结果。由定理2即得推理规则：C1∧C2＝＞(C1-｛L1｝)∪(C2-｛L2｝)其中C1,C2是两个子句，L1,L2分别是C1,C2中的文字，且L1,L2互补。此规则就是命题逻辑中的归结原理。例3.10用归结原理验证分离规则和拒取式A∧(A→B)＝＞B(A→B)∧﹁B＝＞﹁A解A∧(A→B)＝A∧(﹁A∨B)＝＞B(A→B)∧﹁B＝(﹁A∨B)∧(﹁B)＝＞﹁A例5.11证明子句集{P∨﹁Q,﹁P,Q}是不可满足的。证(1)P∨﹁Q(2)﹁P(3)Q(4)﹁Q由(1),(2)(5)□由(3),(4)例5.12用归结原理证明R是P,(P∧Q)→R,(S∨U)→Q,U的逻辑结果。证由所给条件得到子句集S=｛P,﹁P∨﹁Q∨R,﹁S∨Q,﹁U∨Q,U,﹁R｝然后对该子句集施行归结，归结过程用下面的归结演绎树表示（见图5―1）。由于最后推出了空子句，所以子句集S不可满足，即命题公式P∧(﹁P∨﹁Q∨R)∧(﹁S∨Q)∧(﹁U∨Q)∧U∧﹁R不可满足，从而R是题设前提的逻辑结果。图5―1例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(1≤j≤n)都用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谓词逻辑中的消解式是它的亲本子句的逻辑结果。由此定理我们即得谓词逻辑中的推理规则：C1∧C2＝＞(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))证我们用反证法，即证明A1∧A2﹁G不可满足。首先求得子句集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)这个归结过程的演绎树如图5―2所示。图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→BA—————B5.3.3产生式系统1．系统结构产生式规则库推理机动态数据库。图6-2推理机的一次推理过程3．控制策略与常用算法1)正向推理算法一：步1将初始事实/步2用动态数据库中的事实/数据,匹配/测试目标条件,若目标条件满足,则推理成功,结束。步3用规则库中各规则的前提匹配动态数据库中的事实/数据,将匹配成功的规则组成待用规则集。步4若待用规则集为空,则运行失败,退出。步5将待用规则集中各规则的结论加入动态数据库,或者执行其动作,转步2。例动物分类问题的产生式系统描述及其求解。r1：若某动物有奶,则它是哺乳动物。r2：若某动物有毛发,则它是哺乳动物。r3：若某动物有羽毛,则它是鸟。r4：若某动物会飞且生蛋,则它是鸟。r5：若某动物是哺乳动物且有爪且有犬齿且目盯前方,则它是食肉动物。r6：若某动物是哺乳动物且吃肉,则它是食肉动物。r7：若某动物是哺乳动物且有蹄,则它是有蹄动物。r8：若某动物是有蹄动物且反刍食物,则它是偶蹄动物。r9：若某动物是食肉动物且黄褐色且有黑色条纹,则它是老虎。r10：若某动物是食肉动物且黄褐色且有黑色斑点,则它是金钱豹。r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点,则它是长颈鹿。r12：若某动物是有蹄动物且白色且有黑色条纹,则它是斑马。r13：若某动物是鸟且不会飞且长腿且长脖子且黑白色,则它是驼鸟。r14：若某动物是鸟且不会飞且会游泳且黑白色,则它是企鹅。r15：若某动物是鸟且善飞且不怕风浪,则它是海燕。规则集形成的部分推理网络再给出初始事实：f1f2f3f4：有黑色条纹。目标条件为：该动物是什么？该系统的运行结果为：该动物是老虎。关于“老虎”的正向推理树2)反向推理反向推理算法：步1将初始事实/数据置入动态数据库,将目标条件置入步2若目标链为空,则推理成功,结束。步3取出