知识表示与推理.ppt
《知识表示与推理.ppt》由会员分享,可在线阅读,更多相关《知识表示与推理.ppt(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,L2互补。此
5、规则就是命题逻辑中的归结原理。例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
6、不可满足,从而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的一个合一,如果对S的任何一个合一,都存在一个替换,使得 =则称为S的最一般合一(MostGe
8、neralUnifier),简称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(
9、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的二元消解式;(4)C1的因子和C2的因子的二元消解式。定理4 谓词逻辑中的消解式是它的亲本子句的逻辑结果。由此定理我们即得谓词逻辑中的推理规则:C
11、1C2(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)所以
12、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
13、),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组成的表达式。语义:如果前提满足,则可得结论或者执行相应的动作,即后件由前件来触发。所以,前件是规则的执行条件,
14、后件是规则体。例:例:(1)如果银行存款利率下调,那么股票价格上涨。(2)如果炉温超过上限,则立即关闭风门。(3)如果键盘突然失灵,且屏幕上出现怪字符,则是病毒发作。(4)如果胶卷感光度为200,光线条件为晴天,目标距离不超过5米,则快门速度取250,光圈大小取f16。5.3.2 基于产生式规则的推理模式 A B A B 5.3.3 产生式系统 1 1系统结构系统结构 产生式规则库 推理机 动态数据库。图 6-2 推理机的一次推理过程 3 3控制策略与常用算法控制策略与常用算法 1)正向推理 正向推理算法一:步1 将初始事实/数据置入动态数据库。步2 用动态数据库中的事实/数据,匹配/测试目标
15、条件,若目标条件满足,则推理成功,结束。步3 用规则库中各规则的前提匹配动态数据库中的事实/数据,将匹配成功的规则组成待用规则集。步4 若待用规则集为空,则运行失败,退出。步5 将待用规则集中各规则的结论加入动态数据库,或者执行其动作,转步2。例例动物分类问题的产生式系统描述及其求解。r1:若某动物有奶,则它是哺乳动物。r2:若某动物有毛发,则它是哺乳动物。r3:若某动物有羽毛,则它是鸟。r4:若某动物会飞且生蛋,则它是鸟。r5:若某动物是哺乳动物且有爪且有犬齿且目盯前方,则它是食肉动物。r6:若某动物是哺乳动物且吃肉,则它是食肉动物。r7:若某动物是哺乳动物且有蹄,则它是有蹄动物。r8:若某
16、动物是有蹄动物且反刍食物,则它是偶蹄动物。r9:若某动物是食肉动物且黄褐色且有黑色条纹,则它是老虎。r10:若某动物是食肉动物且黄褐色且有黑色斑点,则它是金钱豹。r11:若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点,则它是长颈鹿。r12:若某动物是有蹄动物且白色且有黑色条纹,则它是斑马。r13:若某动物是鸟且不会飞且长腿且长脖子且黑白色,则它是驼鸟。r14:若某动物是鸟且不会飞且会游泳且黑白色,则它是企鹅。r15:若某动物是鸟且善飞且不怕风浪,则它是海燕。规则集形成的部分推理网络 再给出初始事实:f1:某动物有毛发。f2:吃肉。f3:黄褐色。f4:有黑色条纹。目标条件为:该动物是什么?该
17、系统的运行结果为:该动物是老虎。关于“老虎”的正向推理树 2)反向推理反向推理反向推理算法:步1 将初始事实/数据置入动态数据库,将目标条件置入目标链。步2 若目标链为空,则推理成功,结束。步3 取出目标链中第一个目标,用动态数据库中的事实/数据同其匹配,若匹配成功,转步2。步4 用规则集中的各规则的结论同该目标匹配,若匹配成功,则将第一个匹配成功且未用过的规则的前提作为新的目标,并取代原来的父目标而加入目标链,转步3。步5 若该目标是初始目标,则推理失败,退出。步6 将该目标的父目标移回目标链,取代该目标及其兄弟目标,转步3。例例对于上例中的产生式系统,改为反向推理算法,则得到下图所示的推理
18、树。关于“老虎”的反向推理树 3)3)冲突消解策略冲突消解策略 正向推理算法二:步1 将初始事实/数据置入动态数据库。步2 用动态数据库中的事实/数据,匹配/测试目标条件,若目标条件满足,则推理成功,结束。步3 用规则库中各规则的前提匹配动态数据库中的事实/数据,将匹配成功的规则组成待用规则集。步4 若待用规则集为空,则运行失败,退出。步5 用某种策略,从待用规则集中选取一条规则,将其结论加入动态数据库,或者执行其动作,撤消待用规则集,转步2。常用的冲突消解策略有:优先级法(优先级高者 优先)、可信度法(可信度高者优先)、代价法(代价低者优先)及自然顺序法等。产生式系统的推理方式、搜索策略及冲
19、突消解策略等,一般统称为推理控制策略控制策略,或简称控制策略。一个产生式系统的控制策略就体现在推理机的算法描述中。4 4程序实现程序实现1)产生式规则的程序语言实现产生式规则的程序语言实现 将规则的前提部分做成形如 条件1 AND 条件2 AND AND 条件n 或 条件1 OR 条件2 OR OR 条件m 将规则结论部分做成形如 断言1/动作1 AND 断言2/动作2 AND AND 断言k/动作k 或 断言1/动作1 OR 断言2/动作2 OR OR 断言k/动作k 一般地做成 条件1 AND 条件2 AND AND 条件n断言/动作v在PROLOG程序中要表示产生式规则,至少有两种形式:
20、(1)用PROLOG的规则表示产生式规则。(2)用PROLOG的事实表示产生式规则。例例把上述动物分类系统中的产生式规则用PROLOG的规则可表示如下:animal_is(老虎):-it_is(食肉动物),fact(黄褐色),fact(有黑色条纹).it_is(食肉动物):-it_is1(哺乳动物),fact(有爪),fact(有犬齿),fact(目盯前方).it_is(食肉动物):-it_is1(哺乳动物),fact(吃肉).it_is1(哺乳动物):-fact(有奶).it_is1(哺乳动物):-fact(有毛发).也可以将上面的规则表示成如下的形式:rule(“食肉动物”,“黄褐色”,“
21、有黑色条纹”,“老虎”).rule(“哺乳动物”,“有爪”,“有犬齿”,“目盯前方”,“食肉动物”).rule(“哺乳动物”,“吃肉”,“食肉动物”).rule(“有奶”,“哺乳动物”).rule(“有毛发”,“哺乳动物”).2 2)规则库的程序实现)规则库的程序实现 3 3)动态数据库的程序实现)动态数据库的程序实现 4 4)推理机的程序实现)推理机的程序实现 5.5.产生式系统与图搜索问题求解产生式系统与图搜索问题求解 5.4 几种结构化知识表示及其推理5.4.1 框架 1.框架的概念|v 例例7.17.1 下面是一个描述“教师”的框架:v 框架名:v 类属:v 工作:范围:(教学,科研)
22、v 缺省:教学v 性别:(男,女)v 学历:(中师,高师)v 类型:(,)v 例例7.27.2 下面是一个描述“大学教师”的框架:v 框架名:v 类属:v 学历:(学士,硕士,博士)v 专业:v 职称:(助教,讲师,副教授,教授)v 外语:语种:范围:(英,法,日,俄,德,)v 缺省:英v 水平:(优,良,中,差)v 缺省:良v 例例7.37.3 下面是描述一个具体教师的框架:v 框架名:v 类属:v 姓名:李明v 性别:男v 年龄:25v 职业:教师v 职称:助教v 专业:计算机应用v 部门:计算机系软件教研室v 工作:v 参加工作时间:1995年8月v 工龄:当前年份-参加工作年份v 工资
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 知识 表示 推理