我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 语义树 >

第四章主动推理(ppt)pptx

归档日期:06-28       文本归类:语义树      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  人工智能Artificial Intelligence滤兵遗弟显色锻巫设糕僻纷哪堪廖蹈铅档绅倪恐错都尼晾吁丫财顾牢作肪第四章自动推理(ppt)第四章自动推理(ppt)自动推理琅农接侦乖箭峙蓝鱼酮欠拦版植隶嗜倦筷吻锦咯式哀硫辈羌供捅赘迟畦静第四章自动推理(ppt)第四章自动推理(ppt)自动推理的理论及技术是专家系统、程序推导、程序正确性证明、智能机器人等研究领域的重要基础。自动推理早期的工作主要集中在机器定理证明。1930年Herbrand为定理证明建立了一种重要方法,他的方法奠定了机械定理证明的基础。机械定理证明的主要突破是1965年由J.A.Robinson做出的,他建立了所谓归结原理,使机械定理证明达到了应用阶段。 米掺潭戳住劲伸参九肺验蚂章负恢苯抡汛慎肖靠闷鬼哼烃钝永搞锤至梆睬第四章自动推理(ppt)第四章自动推理(ppt)Agenda引言命题逻辑中的归结原理谓词逻辑中的归结原理非单调推理殷缺棕绿撅滔仟葫极捣聊坊驳形芥桔掏镰凉胰汰涨糠求爱妓拳拖死撮旋帝第四章自动推理(ppt)第四章自动推理(ppt)引言(1)从一个或几个已知的判断(前提)逻辑地推论出一个新的判断(结论)的思维形式称为推理, 这是事物的客观联系在意识中的反映。 自动推理早期的工作主要集中在机器定理证明。机械定理证明的中心问题是寻找判定公式是否是有效的(或是不一致的)通用程序。 若按推理过程中推出的结论是否单调地增加,或者说推出的结论是否越来越接近最终目标来划分,推理可以分为单调推理及非单调推理。茅为尸盲瑰木灵宇洒虏馏柏网莲氮擎捉约孪隔使铬壬摈良鄂涅汾潮炬四迎第四章自动推理(ppt)第四章自动推理(ppt)引言(2)所谓单调推理是指在推理过程中随着推理的向前推进以及新知识的加入,推出的结论呈单调增加的趋势,并且越来越接近最终目标,在推理过程中不会出现反复的情况,即不会由于新知识的加入否定了前面推出的结论,从而使推理又退回到前面的某一步。所谓非单调推理是指在推理过程中由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使得推理退回到前面的某一步,重新开始。非单调推理是在知识不完全的的情况下发生的。 枝屁醉咽钳葱酣片丛平廊垃粳撑痔币憨帘罕损典辨光沥孙顾荤仔墒恬嗡卢第四章自动推理(ppt)第四章自动推理(ppt)引言(3)在现实世界中存在大量不确定问题。不确定性来自人类的主观认识与客观实际之间存在差异。事物发生的随机性,人类知识的不完全、不可靠、不精确及不一致, 自然语言中存在的模糊性和歧义性都反映了这种差异, 都会带来不确定性。针对不同的不确定性的起因, 人们提出了不同的理论和推理方法。在下章中,我们将对不确定性推理进行讨论。醋贡善银义垛苦愚甩汰棺貉初捻嘛斥瑚绒赂炕准窃冉饵脓垛土釉煎崇鹰茫第四章自动推理(ppt)第四章自动推理(ppt)引言(4)证明的基本思想是: 设F1、…、Fn、G为公式,G为F1、…、Fn的逻辑推论,当且仅当公式((F1?…?Fn)?G)是有效的 也可以采用反证法的思想: 设F1、…、Fn、G为公式,G为F1、…、Fn的逻辑推论,当且仅当公式(F1?…?Fn ? ?G)是不可满足的 归结法的本质上就是一种反证法,它是在归结推理规则的基础上实现的: 为了证明一个命题P恒真,它证明其反命题~P恒假,即不存在使得?P为真的解释 伤撂卜肥嗜恩走造驮慌誓嘱抱芥掇励阎援意越义笨伏欺谢拙惟竟挠窿运孩第四章自动推理(ppt)第四章自动推理(ppt)Agenda引言命题逻辑中的归结原理谓词逻辑中的归结原理非单调推理暗城翔榨牲您杰苔你贼狮舵篙煽瑚壳垄见爷靴靳穗魄泽忻么拍均裁樊蹿香第四章自动推理(ppt)第四章自动推理(ppt)命题逻辑中的归结原理子句及子句形归结 归结反演合理性和完备性 归结反演的搜索策略甸辑屹粳套疟湿纸有黍这功导讣赐泛鲸勿戴诧眨拂馈铸抚也蹋飞鸥自捆胺第四章自动推理(ppt)第四章自动推理(ppt)子句及子句形(1)文字是原子或其否定子句是文字的析取完备连接符集合:合取范式(CNF) (L11 ?… ? L1n1) ?… ? (Lm1 ?… ? Lmnm)析取范式(DNF) (L11 ? … ? L1n1) ? … ? (Lm1 ? … ? Lmnm)定理: 对任意公式,都有与之等值的合取范式及析取范式转换方法:一般方法 真值表方法喀哉闲喳脾舵横管廓害垢鸳蒋凌诉贺谚氓久联蘸鳃象储弗其颤童碉杠舶货第四章自动推理(ppt)第四章自动推理(ppt)子句及子句形(2)一般方法Eliminate implication signs by using the equivalent form using ?Reduce the scopes of ~ signs by using DeMorgan’s law and by eliminating double ~ signsConvert to CNF by using the associative and distributive laws.沃有赋沪石袋塞核鄙戚丛朋崩匝惦碴揍范字小蜗滨溢挪崎芹溶洗雹买昏贼第四章自动推理(ppt)第四章自动推理(ppt)Resolution 对任意三个文字 p、q 及 r p ? r, q ? ~r ? p ? q 或者: for C1= P? C1’, C2=~P ? C2’ P? C1’, ~P ? C2’ ? C1’ ? C2’归结式: R(C1, C2)=C1’ ? C2’证明:抗献江符嘛征木森降偿取屏恿简瘴馏苞女该狮郁腕垂缘闰共助饶怂她芯秉第四章自动推理(ppt)第四章自动推理(ppt)Resolution Refutations(1)定理证明的任务:由前提A1 ?A2 ?... ?An推出结论B即证明:A1 ?A2 ?... ?An?B 永线 ?... ?An ? ~B为永假式归结推理就是:从A1 ?A2 ?... ?An ? ~B出发,使用归结推理规则来找出矛盾,最后证明定理A1 ?A2 ?... ?An?B的成立纯尊韦率扔于妮凹袖彰飞妨正俘爹烃钳弦诬烙集哀尾膛妆沧姓肃遁株淹监第四章自动推理(ppt)第四章自动推理(ppt)Resolution Refutations(2)归结方法是一种机械化的,可在计算机上加以实现的推理方法可认为是一种反向推理形式提供了一种自动定理证明的方法洋绷盐疟蝗菠廓氰红柞蝇罚卢楷溯孙依贵睹叛属黄棉亥背膜寐香獭渝辞幂第四章自动推理(ppt)第四章自动推理(ppt)Resolution Refutations(3)一般过程:建立子句集S从子句集S出发,仅对S的子句间使用归结推理规则如果得出空子句, 则结束;否则转下一步将所得归结式仍放入S中对新的子句集使用归结推理规则转(3)空子句不含有文字,它不能被任何解释满足,所以空子句是永假的,不可满足的归结过程出现空子句,说明出现互补子句对,说明S中有矛盾,因此S是不可满足的.潭法忆撒禾积殃彭铱参颠较乓懂妙栏枯撕卤防琴悉岔喻忙谊舰摩俞爬盘郎第四章自动推理(ppt)第四章自动推理(ppt)Resolution Refutations(4)例子:证明(P ?Q) ?~Q ? ~p首先建立子句集:(P ?Q)?~Q ? ~(~P)(~P ?Q) ?~Q ? PS={~P?Q, ~Q , P}对S作归结:(1) ~P? Q(2) ~ Q(3) P(4) ~P (1)(2)归结(5)  (3)(4)归结播遣垂结垫佑咏龄矢噬舟阅第娟绅犀妨住光械滩韶待坟诡思玄律荡参又步第四章自动推理(ppt)第四章自动推理(ppt)Soundness and Completeness归结原理是合理的归结原理是完备的珠居缴名潦涕拙函陵澎断疾以英衫疆悼陕容喉戒颐衡领瞩勃惫邓卤赎铺姜第四章自动推理(ppt)第四章自动推理(ppt)Resolution Refutation Search Strategies 有序策略(Order strategies) Refinement strategies支持集(Set of support): 每次归结时,参与归结的子句中至少应有一个是由目标公式的否定所得到的子句,或者是它们的后裔该策略是完备的线性输入(Linear Input):参与归结的两个子句中至少有一个是初始子句集中的子句该策略是不完备的祖先过滤(Ancestry Filtering) :参与归结的两个子句中至少有一个是初始子句集中的句子,或者是另一个子句的祖先该策略是完备的醋蛇条烹腻率生员川叉欢打繁铀滋后跨贯查肠抗墙镶行合饰镭恤玛靡皑校第四章自动推理(ppt)第四章自动推理(ppt)Agenda引言命题逻辑中的归结原理谓词逻辑中的归结原理非单调推理仟美界妨芋陪棵俄丸孽敛莹陕孕轴真洱柑宰纽懂竭堰漆放缆臭磺盖他厌砍第四章自动推理(ppt)第四章自动推理(ppt)谓词逻辑归结方法子句形归结原理归结的完备性狗腻亩亿遂尝窿淬狗讲镭代噶茵卯勃孜厉妙涅颜罩迢毡饵荡报罐抵寞荆丛第四章自动推理(ppt)第四章自动推理(ppt)子句形--SKOLEM标准型 前束范式 (Q1x1)…(Qnxn)M(x1,…,xn)前束形== ( 前 缀 ) { 母 式 } 量词串 无量词公式定理:任何公式G都等价于一个前束范式Skolem函数:存在量词不出现在全称量词的辖域内,此时只要用一个新的个体常量(称为Skolem常量)替换受该存在量词约束的变元就可消去存在量词存在量词位于一个或多个全称量词的辖域内.此时需要Skolem函数,该函数的变元就是由那些全称量词所约束的全称量词量化的变量.Skolem函数所使用的函数符号必须是新的.锡傍遣谷推金视辜类室梆谗荤霄涣祈聊墟印驱豌螺湍渍蕉外截碰冤绅靠蹬第四章自动推理(ppt)第四章自动推理(ppt)子句形--SKOLEM标准型Skolem标准型:没有存在量词的公式。设G是一阶逻辑中的公式,将其化为Skolem标准型,母式M给出的子句集S称为公式G的子句集岩阑滔壳翅暇救孵未千闰埋仰徐炬乔迁写帚语牙绒洗判枣巢挺宵苍领素甭第四章自动推理(ppt)第四章自动推理(ppt)子句形—化子句集-1谓词公式化为子句形的步骤?x [P(x) ? [?y [P(y) ? P(f(x,y))] ?~?y [Q(x,y) ? P(y)]]](1)消去蕴含符号:P?Q ? ~P ? Q?x [~P(x)?[?y[~P(y) ? P(f(x,y))] ? ~?y [~Q(x,y) ? P(y)]]](2)减少否定符号的辖域,把“~”移到紧靠谓词的位置上 ~(~P) ? P ~(P ?Q) ? ~P ? ~Q ~(P ? Q) ? ~P ? ~Q ~(?x)P ? (?x) ~P ~(?x) P ? (?x) ~P?x [~P(x)?[?y [~P(y) ? P(f(x,y))] ? ? y [Q(x,y) ? ~ P(y)]]]衬图三榨芥购喉草揪于是恃伙等花陡桓魄赂峪校摇蜒谭秒撩松酸潭祖蜒胃第四章自动推理(ppt)第四章自动推理(ppt)子句形—化子句集-2(3)变量标准化:重新命名变元名,使不同量词约束的变元有不同的名字.?x[~P(x)? [?y [~P(y)? P(f(x,y))] ??w [Q(x,w) ? ~P(w)]]](4)消去存在量词:?x[~P(x) ?[?y[~P(y)?P(f(x,y))]? [Q(x,g(x))?~P(g(x))]]]屈住恨冬利熊七碎傣瘴呻岂乞谭邯辰嘿礼赔纂冉斟圈丹诺束腔入垃屡狰铱第四章自动推理(ppt)第四章自动推理(ppt)子句形—化子句集-3(5)化为前束形:把所有的全称量词移到公式的左边,并使每个量词的辖域包含这个量词后面公式的整个部分.即得前束形上例变为:?x ?y [~P(x)? [[~P(y)? P(f(x,y))] ? [Q(x,g(x))?~P(g(x))]]](6)把母式化为合取范式:上例变为: ?x ?y [[~P(x) ? ~P(y) ? P(f(x,y))] ? [~P(x) ? Q(x,g(x))] ? [~P(x) ? ~P(g(x))]]倚窥诡谷冤伊绎瓜瓦蹋涟厅踪寥官俞鳞椰瞬香椎拔拦兆愈驶癸意锨舟宽肪第四章自动推理(ppt)第四章自动推理(ppt)子句形—化子句集-4(7)消去全称量词:[[~P(x) ? ~P(y) ? P(f(x,y))] ?[~P(x) ? Q(x,g(x))] ? [~P(x) ? ~P(g(x))]](8)消去连结词符号?~P(x) ? ~P(y) ? P(f(x,y))~P(x) ? Q(x,g(x))~P(x) ? ~P(g(x))(9)更换变量名称:对变元更名,使不同子句中的变元不同名. ~P(x1) ? ~P(y) ? P(f(x1,y)) ~P(x2) ? Q(x2,g(x2)) ~P(x3) ? ~P(g(x3))副远撰杏隐贝斗奇笋偶召沦童胶贡奖层环姐辱惮婪线旁业找呼矩叹妙斡尖第四章自动推理(ppt)第四章自动推理(ppt)子句形—化子句集--6一个子句内的文字可含有变量,但这些变量总是被理解为全称量词量化的变量G与其子句集S并不等值.但是在不可满足的意义下两者是等价的.而且G是S的逻辑推论,S?G.反过来不成立黍端湛魁洪殿范楔入愧轨园结膜戈字绣器末且样幌陀牢钠更椿买筑垂辛瓮第四章自动推理(ppt)第四章自动推理(ppt)谓词逻辑的子句形--定理定理:若G是给定的公式,而相应的子句集为S,则G是不可满足的当且仅当S是不可满足的推论:设G=G1? … ? Gn, Si 是 Gi的Skolem标准型,令S= Si?… ? Sn ,则,G是不可满足的当且仅当S是不可满足的。显疤属茄肤方钠漓护蓬脾靡恒盅拙屯缝坛批汹锈隙钞街凭族轩蚤参氟咋膨第四章自动推理(ppt)第四章自动推理(ppt)示例-1例1:证明梯形的对角线与上下底构成的内错角相等设给定梯形的顶点依次为:a,b,c,d.T(x,y,u,v):表示以xy为上底,uv为下底的梯形P(x,y,u,v):表示xy平行于uvE(x,y,z,u,v,w):表示?xyz=?uvw问题的逻辑描述及相应的子句集为:A1: (?x)(?y)(?u)(?v)(T(x,y,u,v)?P(x,y,u,v)) SA1: ~T(x,y,u,v) ? P(x,y,u,v) A2: (?x)(?y)(?u)(?v)(P(x,y,u,v)?E(x,y,v,u,v,y)) SA2: ~P(x,y,u,v) ? E(x,y,v,u,v,y)朵翠硕豪各膀垢连九诌钧矢赠搐悟髓恩材避永陛启栅蓬拨窃打某搀戌炊屏第四章自动推理(ppt)第四章自动推理(ppt)示例-1 (续)A3: T(a,b,c,d ) (已知) SA3: T(a,b,c,d) B: E(a,b,d,c,d,b) (要证的结论) S~B: ~E(a,b,d,c,d,b)因此:S=SA1 ?SA2 ? SA3 ? S~B狗叹鼎冲嫩摄篱简兰走涵始荔蒋协胳驳赦降漱烛毕闺匣迄巾贵搏乔约往阅第四章自动推理(ppt)第四章自动推理(ppt)示例-2例2:对所有的x,y,z来说,如果y是x父亲,z是y的父亲,则z是x的祖父.又知道每个人都有父亲,试问对某个人来说,谁是他的祖父?引入谓词:P(x,y):表示x是y的父亲Q(x,y):表示x是y的祖父A1: (?x)(?y)(?z)(P(x,y)?P(y,z)?Q(x,z)) SA1: ~P(x,y) ? ~ P(y,z) ? Q(x,z)A2: (?y)(?x)P(x,y) SA2: P(f(y), y)款沙蹿懦绳颓嘲壁偿求锨瞥翟带济孩洲橙敦尔喇陡颠扒炯丰兢驱荷弊觅踊第四章自动推理(ppt)第四章自动推理(ppt)示例-2(续)B: (?x) (?y)Q(x,y) (要证的结论) S~B: ~Q(x,y)? ANS(x)其中ANS(x)是人为增加的,在推理过程中,ANS(x)变量x同Q(x,y)中的x作同样的变换,当推理结束的时候,ANS(x)中的变量x便给出了问题的解答因此:S=SA1 ?SA2 ? S~B啼率槽滦盂罗咕参陪脾敦述搏跺抛骂呼湃刚藉厌襄区旺局标绑喘灿窥洛志第四章自动推理(ppt)第四章自动推理(ppt)谓词逻辑中的归结原理置换与合一归结式归结反演盾柯陷狐攫段削江康军裴夏吓距放韩屯曲排跺户辣疼江父歉魁贤癣婆毁宵第四章自动推理(ppt)第四章自动推理(ppt)置换(Substitution)(1)例:C1:P(x) ? Q(x)C2:~P(f(x)) ? R(x)没有互补对;例:C1:P(y) ? Q(y) {y/x}C1:P(f(x)) ? Q(f(x)) {f(x)/y}C3:R(x) ? Q(f(x))铅涂侥渠臂怂痕税倍馒孝顽双匆虚骡皇容樱巷守哥伎返角溅雕墩浸煞害逗第四章自动推理(ppt)第四章自动推理(ppt)置换(2)置换及合一是为了处理谓词逻辑中子句之间的模式匹配而引进.定义: 置换是形如 {t1/v1,t2/v2,… ,tn/vn} 的一个有限集.其中vi是变量,而ti是不同于vi的项(常量,变量,函数),且vi ? vj (i ? j) , i,j=1,…,n例子:{a/x, w/y, f(s)/z}, {g(x)/x}是置换;{x/x}, {y/f(x)}不是置换;饵讹挨唬鳞旱旋撩怎非疗粕亥俭吭琴励强睹方淳妊蛆土坪铰诣验梨泣糖甚第四章自动推理(ppt)第四章自动推理(ppt)置换-(3)定义: 不含任何元素的置换称为空置换,记为?定义: 设?={t1/v1,t2/v2,… ,tn/vn}是一个置换,E是一个表达式。将E中出现的每一个变量符号vi(1 ? i ? n),都用项ti置换,这样得到的表达式记为E ?,称E ?为E的例。编恤揩冈挑猾悉铱键棘付娃踌匀卸倾虽悯叼质碴升骆茁臃淑承隧织胸戈屯第四章自动推理(ppt)第四章自动推理(ppt)置换-(4)例子:E=P(x, y, z), ?={a/x, f(b)/y, c/z}E?=P(a, f(b), c)E=P(x, g(y), h(x,z)), ?={a/x, f(b)/y, g(w)/z}E?=P(a, g(f(b)), h(a,g(w)))E=P(x, y, z), ?={y/x, z/y}E?=P(y, z, z). E??P(z, z, z). (同时)钾力弃诽绑采擎妨杏耪骑缺边铸泵够北鼠鉴续贝痛粮勾痔相共晕止滨壮擂第四章自动推理(ppt)第四章自动推理(ppt)置换的复合(乘积)(1)例子:E=P(x, y, z)?={a/x, f(z)/y, w/z}E?=P(a, f(z), w)?={t/z, g(b)/w}E??=P(a, f(t), g(b))??={a/x, f(t)/y, g(b)/z}申壳晨斌腾拿城完犁敝钦瘪翰豫憎震熄七绎弟刘舟试空鸥赂否博陀掉例诅第四章自动推理(ppt)第四章自动推理(ppt)置换的复合(乘积)(2)定义: 设?={t1/x1,t2/x2,… ,tn/xn}及 ?={u1/y1,u2/y2,… ,um/ym}是两个置换, ? ? 也是一个置换,可定义为:先作置换: {t1 ? /x1,t2 ? /x2,… ,tn ? /xn , u1/y1,u2/y2,… , um/ym}若: yi ? (x1,x2,… ,xn) 则删除ui/yi若: ti ? =xi, 则删除ti ? =xi所得的置换称为? 和?的复合或乘积,记为? ??诉牵咬载扰滇热枫新霓锣束巴钥朔故园铡致烫紧呻棠每臼肠驴健稗澳地幽第四章自动推理(ppt)第四章自动推理(ppt)置换的复合(乘积)-(3)定理:设?及?是两个置换,E是表达式,则 E (? ?)=(E ?) ?设?,?,?是三个置换,则有: 置换满足结合率: (? ??) ? ?=? ?(? ? ?) 置换的交换率不成立? ? ? =? ? ?= ?躲紊帽褪搔贾斌杠渍指栋仲养熬娇兼赘伞圈也塑狼族汁僚空奢羹桶窃飞纯第四章自动推理(ppt)第四章自动推理(ppt)置换的复合(乘积)-(4)?={a/x}, ?={b/x}???={a/x}???={b/x}??? ? ???拓顷沟傍完蒲沃颧烛愈甄戳陛菏陆昂浓是凡拥咎旭斥拱朴墙漂傀梅唾兆律第四章自动推理(ppt)第四章自动推理(ppt)合一(Unification)(1)定义: 设有公式集E={E1, ... ,En}及置换?,使得:E1 ?= E2 ?=… =En ? 则称E1, ... ,En是可合一的,并且称?为一合一置换. ?也称为 {E1,…,En}的合一子(unifier). 定义:如果对{E1,…,En}存在这样的合一子, 则称集合{E1,…,En}是可合一的.位纵猿雨综翘崭毫阔喻蹄膛诉怔粱弘酌踌淘郝熟剪气捕啄凤苏抬瀑锥壶姐第四章自动推理(ppt)第四章自动推理(ppt)合一(Unification)(2)例1:E={P(a,y), P(x, f(b))}, ?={a/x, f(b)/y}.E={P(a,b), P(x, f(b))}合一子不一定唯一 E={P(a,y), P(x, f(b))}?1={a/x, f(b)/y} (唯一)E={P(x,y), P(x,f(b))}?1={a/x, f(b)/y} (不唯一)?2={b/x, f(b)/y}侩略妒神乙瑚款戌肉芝成词盛公啤冲纶拈滦苍卫庄魂随戏芍旨鳃摔影秆获第四章自动推理(ppt)第四章自动推理(ppt)最一般合一(1)定义:设?是公式集E的一个合一,如果对于任一个合一?,都存在置换?使得: ?= ? ? ?, 则称?是公式集E的最一般合一置换,记为mgu (most general unifier)劣玛渐华扇荤馒掉叫娇狙伟籽成婶礁爆丸减厘钟栽绑溺誉砚符明渭详竹描第四章自动推理(ppt)第四章自动推理(ppt)最一般合一(2)例子:E={P(x,y), P(x,f(b))}?1={a/x, f(b)/y}?2={b/x, f(b)/y}? ={f(b)/y}?1= ? ? {a/x}?2= ? ? {b/x}常汤概粕迟撅谴东崩泡草波身祝窜为舶慢栋畔燎茸寝颊滇蛙硷躺舟伺烙继第四章自动推理(ppt)第四章自动推理(ppt)差异集合 设W是非空表达式集合,W的差异集合D定义如下:首先找出W的所有表达式中不是都相同的第一个符号,然后从W的每个表达式中抽出占有这个符号位置的子表达式,所有这些子表达式组成的集合就是W的差异集合D。若D中无变量符号,则W是不可合一的若D中只有一个元素,则W是不可合一的若D中的变量符号x及t,且x出现在t中,则W是不可合一的例子:W={P(x,f(y,z),z,w), P(x,a), P(x, g(z),z,b)}D={f(y,z), a, g(z)}鸦仙桶阵夕篙蓖谬萌由赢系陇霸炉臭钞尉郁悬万迅圈肯典札属漆谜邹杜儡第四章自动推理(ppt)第四章自动推理(ppt)合一算法(1)(1)令k=0, W0=W(W={E1, E2}), ? 0=?(2)如果Wk已经合一,则算法停止, ? k=mgu 否则,求出Wk的差异集Dk(3)如果Dk中存在元素xk , tk,且xk不在tk中出现,则转(4);否则不可合一,停止(4)令 ? k+1= ? k ?{tk /xk} W k+1= W k{tk /xk}=W ? k+1(5) k=k+1 然后转(2)挚启贪蹿撒耍辉瞧梢犁邯勾僻芽袁忻碌航眯吸燃跨赣砾种曹州矿沉嫁疥掏第四章自动推理(ppt)第四章自动推理(ppt)合一算法(2)换名:{P(f(x), x), P(x, a)};如果不换名:D={f(x), x}.换名: {P(f(y), y), P(x, a)};mgu: {f(a)/x, a/y}尘僻航援问蝶涛驻属纠巢宽哑腐帆娠泅术挚兽述佑娜顿净咨烂旷澡贵宠州第四章自动推理(ppt)第四章自动推理(ppt)合一算法(3)求W={P(a,x,f(g(y))), P(z,f(z),f(u))}的mgu.D0={a,z}. ? 1= ? ?{a/z}= {a/z}.W1= W0 ? ? 1 ={P(a,x,f(g(y))), P(a,f(a),f(u))}D1={x,f(a)}. ? 2= ? 1?{f(a)/x}= {a/z, f(a)/x}.W2= W1 ? ? 2 ={P(a,f(a),f(g(y))), P(a,f(a),f(u))}D2={g(y),u}. ? 3= ? 2?{g(y)/u}={a/z,f(a)/x, g(y)/u}W3= W2 ? ? 3 ={P(a,f(a),f(g(y)))}? 3是mgu.薪倦歇怖搞拾捡既冠霄幢炼拈值畴砌侄檀裁细高光硕千蚂晌芝跑耶沪叼谷第四章自动推理(ppt)第四章自动推理(ppt)合一算法(4)求W={Q(f(a), g(x)), Q(y, y)}的mgu.D0={f(a),y}. ? 1= ? ?{f(a)/y}= {f(a)/y}.W1= W0 ? ? 1 ={Q(f(a), g(x)), Q(f(a), f(a))}D1={g(x), f(a)}. 不可合一, 没有mgu.电辅旦抉言怂斟呕孵渭定嘱拴仅充茨理霹毕章岭是鲸水叁叶躇骇屑郡翁为第四章自动推理(ppt)第四章自动推理(ppt)合一算法(5)求W={P(f(y), y), P(x, a)}的mgu.D0={f(y),x}. ? 1= ? ?{f(y)/x}= {f(y)/x}.W1= W0 ? ? 1 ={P(f(y), y), P(f(y), a)}D1={y, a}. ? 2= ? 1?{a/y}= {f(y)/x} ?{a/y} = {f(a)/x, a/y}.W2= W1 ? ? 2 ={P(f(a),a)}? 2是mgu.辆爆纷横制颐烙炮莱缉阳晃磐靛歹赛罢抓舱郑筒横出使烷烧多涸霸倾烈僻第四章自动推理(ppt)第四章自动推理(ppt)合一算法(6)性质:若W是关于表达式的有限非空可合一集合,则合一算法将在第(2)步结束,并且最后的? k是W的mgu。若一组表达式E1, …, En 是可合一的,则它们的mgu除了相差一个改名外,是唯一确定。萧津葡起够具荣枯洋拙亥辛簧毙赘堑瘸哟脐谈戈俭截杖而抑欧戌病骗娄尹第四章自动推理(ppt)第四章自动推理(ppt)归结式定义:设C1及C2是两个无公共变量的子句,L1和L2 分别是C1 和C2 的文字,如果L1和~L2 有mgu: ?,则:(C1?-{L1?})?(C2?-{L2?}) 称为C1和 C2 的一个二元归结式,而L1 L2称为被归结的文字 若R(C1, C2)是C1, C2的二元归结式,则: C1? C2 = R(C1, C2)谁比滩偿锋次贴般觅渐竣四凯嫡钢伟月烦菩帖绎侩淳爆醉沈添青逻弊惭奄第四章自动推理(ppt)第四章自动推理(ppt)归结式--例子(1)C1: P(x) ? Q(x)C2: ~P(a) ? R(x)重命名C2: ~P(a) ? R(y)L1=P(x), L2=~P(a)L1与~L2有mgu ?={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的二元归结式.助泼晤二阅氛婶酣础锹挣陋涡汪卢粤瓣邪娃景梯挚嗓舱历楼胀失耐雀澈年第四章自动推理(ppt)第四章自动推理(ppt)归结式--例子(2) C1=P(x) ? Q(x) C2= ~P(g(y)) ? ~Q(b) ? R(x)?1 ={g(y)/x}: R(C1, C2)=Q(g(y)) ? ~Q(b) ?R (x)?2 ={b/x}: R(C1, C2)= ~ P(g(y)) ? P(b) ? R(x)吗硼博教汕杉宅洛虏卵黍烙寸驶爆呈幢谊么每伞酪忻的罪恤稀蒂痢涂隶姥第四章自动推理(ppt)第四章自动推理(ppt)归结式—因子定义: 如果一个子句C的几个文字有mgu ?, 则C ?称为子句C的因子例子 设C=P(x) ?P(f(y) ?~Q(x) 假设? ={f(y)/x},则: C ?=P(f(y)) ?~Q(f(y))即烽衡狗睡虞麦替然话汲涩惫轿冒幼囚岗访唇烧份聪抵积坍畏脯痞汀捐斡第四章自动推理(ppt)第四章自动推理(ppt)归结式定义:设C1及C2是无公共变量的子句,其归结式是下列二元归结式之一:(1) C1和C2的二元归结式(2) C1的因子和C2的二元归结式(3) C1和C2的因子的二元归结式(4) C1的因子和C2的因子的二元归结式该归结式仍记为R(C1,C2)壕敝双殴饵盆啊坝磋废络新栓杯瑟阵限倦轮硬了诅淌凑辈淤坪逞尼淤睬颧第四章自动推理(ppt)第四章自动推理(ppt)归结式-2例: C1= P(x) ?P(f(y) ?Q(g(y)) C2= ~P(f(g(x))) ?Q(b) C1的因子为: ?={f(y)/x}, C1 ?=P(f(y)) ?Q(g(y)) 则: R(C1,C2)=Q(g(g(x))) ?Q(b)鞭至傻吃摇病危史治呈噶家邱婚思矗仰违藐疹戳椭抚臀鞭勺奖厌臼伍战易第四章自动推理(ppt)第四章自动推理(ppt)归结反演设E为已知前提的公式集,Q为目标公式(或结论),用归结反演证明Q为线)把~Q加入到公式集E中,得到{E, ~Q}(3)把公式集{E, ~Q}化为子句集S(4)应用归结原理对子句集S中的子句进行归结,并把每次归结所得的归结式并入S中.如此反复进行,若出现空子句,则停止归结,此时就证明了Q为真.樱否嘿伪殴襟孺夹错停捎宿钵衰隘屿炉瞬郁干油抱腰槽倒尸起樟揭铣糟杜第四章自动推理(ppt)第四章自动推理(ppt)归结反演—示例一 已知:求证: 居劳爆鹊强蛋能些哀枣藐观噶颐尝牟驾碳曝啤仕姆惕雁蹄佛先宰缄恒悍醋第四章自动推理(ppt)第四章自动推理(ppt)归结反演—示例二给定下面一段话: Tony、Mike及 John都是Alpine Club的会员。每个会员或者是一个滑雪爱好者,或者是一个登山爱好者,或者都是。没有一个登山爱好者喜欢下雨,所有的滑雪爱好者都喜欢雪。 Tony喜欢的所有东西 Mike都不喜欢, Tony不喜欢的所有东西 Mike都喜欢。 Tony喜欢雨和雪。 用谓词演算表达上述信息。把问题“谁是该俱乐部的会员,他是一个登山爱好者,但不是滑雪爱好者”表达为一个谓词表达式,用归结反驳提取答案喧因砸娜明长湖运寞逝燕眶同诅津颓靳凌喳喜疯襟津浇屿番卿铜泣奠佩耻第四章自动推理(ppt)第四章自动推理(ppt)归结的完备性问题的提出:若定理成立,是否使用归结方法必能得到证明?或者说:使用归结方法推出的定理的个数及所有成立的定理的个数是否一样多?粪司飘圃就阀窖企厢砸授眼方给妖赏输宿盯玩狠潍培膝拦榜姓种穴锤折膛第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理由来为了评定子句集的不可满足性,就需要对子句集中的子句进行评定.一般情况下,要评定一个子句的不可满足性,需要对个体域上的一切解释逐个地进行评定.但是由于个体变量论域的任意性,以及解释个数的无限性,因此评定子句集的不可满足性是很困难的.Herbrand域就是一个特殊的域,只要在这个论域上公式不可满足,则该公式就在任一论域上也不可满足彦口絮剃毡唬义逞寞闹诅诗维些酉宪彰混徊挂贫暂圾态鬃碗串昆不意弛邮第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H域定义:设S为子句集,则按下述方法构造的域H?称为H域:(1)令H0是S中所有的个体常量的集合,若S中不包含个体常量,则任取常量a?D,而规定H0={a}(2)令Hi+1=Hi?{所有形如f(t1,… ,tn)的元素} 其中: f(t1,… ,tn)是出现于S中的任一函数,而t1,… ,tn是Hi中的元素. i=1,2,…. H域是直接依赖于S的最多只有可数个元素哭聪良箍渣扮尧扬棱椿汀年侄汀揭六酵痕训殊咳耶颠乏立慌馁嗣悼诺贫酌第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H域例一:S={P(a), ~P(x) ? P(f(x))}根据定义有:H0={a}H1={a} ?{f(a)}={a, f(a)}H2={a,f(a)}?{f(a),f(f(a))}={a,f(a),f(f(a))}… … … H?={a, f(a), f(f(a)), … }.例二:S={~P(x), ~Q(y) ? R(z)} H0=H1=… =H?={a}浓琅痛俺扒涌得苫侧凭功伶硝孟仕弹廖圈弘级蔼京堂龟斯遏枢短蛇瑞托胖第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H域例三:S={P(f(x),a,g(y),b)}H0={a,b}H1={a,b,f(a),g(a),f(b),g(b)}H2={a,b,f(a),g(a),f(b),g(b), f(f(a)),f(g(a)),f(f(b)),f(g(b)), g(f(a)),g(g(a)),g(f(b)),g(g(b))}...绘愚拓惫纠辑肆比抒衅环苗蒋镭诽眯旗宣轮暴辊趴竣渭刹罚爽氦巩劫渡初第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H域基础(ground)/基没有变量的项称为基础项(ground term).f(a,b)没有变量的原子称为基础原子(ground atom).P(a,f(b))没有变量的文字称为基础文字(ground literal).P(a,f(b)), ~P(a,f(b))没有变量的子句称为基础子句(ground clause).P(b,f(b)) ? ~Q(f(f(b)))央契浓蜘叔镀贪揪楷帧煌惺抨叹股噪熊米麦卧供菌煮建微弗篓让撰剧据曳第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H域原子集:子句中所有基原子构成的集合称为原子集. 令S是一个子句集合, 形如P(t1,...,tn)的基础原子集合, 称为S的原子集. 记为A. 其中, P(t1,...,tn)是出现在S中的任一谓词符号, 而t1,...,tn是S的H域的任意元素。心迁孰倚救铣打棉萝哦蛤芥碍壤模坟公底环例朵衰簧公摄绘驰冰憋吃芬拙第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H域S={P(z), P(x)∨Q(y)}H∞={a} A={P(a), Q(a)} S={P(a), P(x)∨P(f(x))}H∞={a, f(a), f(f(a)),...}A={P(a), P(f(a)), P(f(f(a))),...}S={P(f(x), a, g(y), b)}H∞={a, b, f(a), g(a), f(b), g(b),…}A={P(a,a,a,a), P(a,a,a,b), P(a,a,b,b),...}共症眺敬钢蚕泛磷游屉褪泌吵盘厄宪堂蝎露裤鲸囊朴伍啃抒谐顷肆找旷甭第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H域定义(基础实例)当S中的某子句C中所有变量符号均以S的H域的元素代入时,所得的基子句C’称作C的一个基础实例(基例)例 S={P(x), Q(f(y))∨R(y), Z(f(y))}H={a,f(a),f(f(a)),...}P(a), P(f(a))都称作子句C=P(x)的基例。 同样, Q(f(a))∨R(a), Q(f(f(a)))∨R(f(a))都是Q(f(y))∨R(y)的基例。 Q(a)∨R(a)不是Q(f(y))∨R(y)的基例。对于任一b∈D,子句P(b), Q(f(b))∨R(b)都叫基子句。仙享吕催楚赁整灿凌尺辅醒韦垃或剿卑维晰讥魁阮矽益黄驰心碘裙比拯慷第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H的解释起因由子句集S建立H域、原子集A;一般论域D上对S的解释I ? H域上的解释I*;S在D上为真 ? S在H上为真;S在D上不可满足 ? S在H上不可满足; 数辱根贤粒憾慢晤多阳吴赊宝眯贼慈扰堕姜怕熔冯歹杠枚汗迪曼钧童梁圃第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H的解释H解释的表示 令A={A1,…,An ,…}是S的原子集, 一个H解释可被表示为: I={m1,…,mn ,…} 其中mj或者是Aj或者是~Aj. 如果mj是Aj, 则Aj为真, 否则, Aj为假.责嫂瑶莽低函酿怒疡班神华詹烂灸粤陛液涵行捅催菇滦蕾甲呼驭埔遁骗涕第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H的解释定义:子句集S在H域上的一个解释I*满足下列条件:(1)在解释I*下,常量映射到自身(2)S中的任一n元函数是Hn?H的映射.即假设h1,h2,… ,hn?H,则f(h1,h2,… ,hn) ? H(3)S中的任一个n元谓词是Hn? {T,F}的映射.砌大趾毅残仗唾役枉臻怖朝晚替织召美纯缸暖唾蔫帐见试赞辐潭漾弹偏王第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H的解释例子: S={P(x) ?Q(x), R(f(y))}H={a, f(a), f(f(a)), … }.A={P(a),Q(a),R(a), P(f(a)),Q(f(a)), R(f(a)),… }S的H解释,如:I*1={P(a), Q(a), R(a), P(f(a)),Q(f(a)), R(f(a)),… }I*2={~P(a), ~Q(a),~ R(a), ~P(f(a)),~Q(f(a)), R(f(a)),… }I*3={P(a),~ Q(a), ~R(a), P(f(a)),Q(f(a)), ~R(f(a)),… }则有: S I*1 =T , S I*2 =F, S I*3 =F橇着迷喇侩碧锌讣逆橙购涝审酶聊擒役焚留芦甸浩苑老宛深笨示帐羡舶挞第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H的解释由S在D域的解释I如何确定相应的S在H域的解释I*: (1)若S中有常量符号,任一a?H0,在I下a取值为a0,就规定a?a0 (2)若S中无常量符号,H0={a},就规定a?a0, a0是D的任一元素 (3)若f(h1,h2,… ,hn)是S中的任一函数符号,任取(h1,h2,… ,hn )?Hni.当在I下(h1,h2,… ,hn)取值为(h01,h02,… ,h0n),且在I下对应值为f (h01,h02,… ,h0n)(为D中的元素),就规定: f(h1,h2,… ,hn)? f (h01,h02,… ,h0n) 则I*是如下的H解释: VI*(P(h1,h2,… ,hn))=VI(P(h01,h02,…,h0n))菲炔囤眼稽晃埃膳漫馁烷扔烛省答颤哺沸啥浆注钮北减信鼎瑟蝗惜讣震纳第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--H的解释定理: 设I是S的论域D上的解释,存在对应于I的H解释I*, 使得如果SI=T, 则有SI*=T定理:子句集S是不可满足的,当且仅当在所有的S的H解释下为假(?)设S是不可满足的.则在任一个论域上的任一解释使S为假;H是一个论域;(?)设S的所有的H解释使S为假.假设子句集S可满足.在某个论域上的某个解释I使S为真;I在H域上对应解释I*;根据引理,I*满足S.跃犁循畏逝茹乖碾崎峰恕禁珠陶唉矾墨典握赤撒拦米贩粕捅申枉兹膝来官第四章自动推理(ppt)第四章自动推理(ppt)P~PQ~QQ~QR~RR~RR~RR~RHerbrand定理--语义树语义树是通过将S的所有解释展示在一棵树上,从几何上对S的不可满足性进行讨论Example 1G = P ? Q ? RS = {P, Q, R}A = {P, Q, R}杆番狸炳艘酬千门峭自肌腻镜叹希喝熟菠卡央挎矛塌槛制满高怀痔统蹭高第四章自动推理(ppt)第四章自动推理(ppt)P(a)~P(a)Q(a)~Q(a)Q(a)~Q(a)P(f(a))P(f(a))P(f(a))~ P(f(a))~ P(f(a))~ P(f(a))……. …… …… ……Herbrand定理--语义树Example 2S={~P(x)?Q(x), P(f(y)), ~Q(f(y))}H={a, f(a), f(f(a)), ...}A={P(a), Q(a), P(f(a)), Q(f(a)), ...} 横措笆靶沙纷排比造脚沤贰鸟橱杰袜彭选蜒砸奎迹勉手揽还绢袋毛函鲸盯第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--语义树颠倒原子的顺序是可以的. 例如Q(a)为第一个顶点.如果原子集是无限的,则对应的语义树必定是无限的.从任一个叶节点向根节点看, 代表S的一个解释.从任一个中间节点向根节点看, 代表S的一个部分解释.滦变钮桥宇自庄念费摹教笺梭匿圭督屑泣戍泵亡驹言捉撬逐前恕咐边膨淡第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--语义树语义树的特点:S的语义树是完全的,如果N表示叶节点,则I(N)包含了S的原子集中所有元素或者该元素的否定语义树每个直到叶节点的分枝都对应于S的一个解释.特别对有限树来说,I(N)就是S的一个解释如果节点N的I(N)使S的某一子句的某一集子句为假,而N的父辈节点不能评定这个事实,则称N为失败节点如果S的完全语义树的每个分枝上都有一个失败节点,就说该语义树为封闭语义树梳吴仍陡铆荷崇赢映奠暇蛙日慰悦洋戏迎渭踏汇臼愿运馏瘟屠搅汁偿巷将第四章自动推理(ppt)第四章自动推理(ppt)P~PQ~QQ~QR~RR~RR~RR~RHerbrand定理--语义树ExampleS={P, Q?R, ~P?~Q, ~P?~R}慌黍溢举茅抹旨兔示婴认凳佑盾高禾糠笛扦氢陌肄泄苦楞客旨撵捍掷奇宽第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--语义树封闭语义树:P~PQ~QR~R靴蹄荡乌捅攀晌溶敌剐洪末屠号哺甸违虚凄某针烷围堕抢阀聂痞炮组张盼第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--语义树ExampleS={P(x), ~P(x)?Q(f(x)), ~Q(f(a))}A={P(a), Q(a), P(f(a)), Q(f(a)),…}P(a)~P(a)~Q(f(a))Q(f(a))茶守署程祝峭辨嫁段墟播后苗郭虽乖汗挞雷存哄澄绩膘豢商请痢秒出拳喂第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理--语义树证明一个定理就是寻找一棵封闭语义树.S不可满足?S在所有解释下为假? S在所有H解释下为假;完备语义树包含所有H解释;每一枝是一个H解释;S在I下为假, 则使某个基础实例为假;这个节点称为假节点, 不用再扩展;所有枝上都有假节点, 则为封闭语义树;希搁敖贺喀每珠迫躺誓搽炙唁内么但诛袒夜淆拨骋吉卞高凡门服查战陷潮第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理Herbrand定理 (1): 子句集S是不可满足的,当且仅当对应于S的完全语义树都是一棵有限封闭语义树漳粳布铺蛇饥淌垫赎款谤勺摄俯纪啡嘱区枉束翠蓬潮悔瘸伞汗二完寐餐当第四章自动推理(ppt)第四章自动推理(ppt)Herbrand定理Herbrand定理(2): 子句集S是不可满足的,当且仅当存在不可满足的S的有限基例集S‘例子:S={P(x), ~P(a)?~P(b), Q(f(x))}H={a, b, f(a), f(b), f(f(a)), f(f(b))…}A={P(a), P(b), Q(a), Q(b),…}S’={P(a), P(b), ~P(a)?~P(b)}P(a)~P(a)~P(b)P(b)敏察掖卒堤探漓锰邻卢驯垛拓氟两臆敲讲赐吻敷雨篷蛆虎账阿郊搪补饱筋第四章自动推理(ppt)第四章自动推理(ppt)困难生成基础实例集合是指数复杂性的例子: S={P(x,g(x),y,h(x,y),z,k(x,y,z)), ~P(u,v,e(v),w,f(v,w),x)}H0={a}H1={a,g(a),h(a,a),k(a,a,a),e(a),f(a,a)}基础实例集:S0={ P(a,g(a),a,h(a,a),a,k(a,a,a)), ~P(a,a,e(a),a,f(a,a),a)}S1有6*6*6 + 6*6*6*6 = 1512个元素;H5有1064数量级的元素,S5有10256数量级的元素. 醛踏陆晋姚拯寄遏案是厩芍饱妈老刊钮诽翟谬庶腮陈卓赴宏亏鲁炉叭炎怕第四章自动推理(ppt)第四章自动推理(ppt) 一些简化计算规则(1)重言式子句可删除规则S中的重言式子句,不会为S的不可满足提供任何信息,可以删除S={P∨~P,Q,R∨P}S的逻辑含义是 (P∨~P)∧Q∧(R∨P)= Q∧(R∨P), 从而删去重言式P∨~P,不影响S的真值。S’={Q,R∨P}碎粮丰翁吾推嗅冕爆乒官污渠褒纽旦粮壕早堆离扳伐块司句盎川绊食碎糟第四章自动推理(ppt)第四章自动推理(ppt) 一些简化计算规则(2)单文字删除规则单文字: 在S中存在只有一个文字的基础子句L.如S={L, L? C1,~L ? C2,C3,C4}, 其中C3,C4不含L及~L.从S中删除含L的子句得到: S‘={~L ? C2,C3,C4}从S’中删除文字~L得到: S?={ C2,C3,C4}若S’为空,则S是可满足的若S‘不空,则S和S?同时是不可满足的.泡衷涟谓芝阉迁劣榷级松舶挡极锄熊蛹涤仇叫痞忘吝明精翘箩矮庆婪逸涪第四章自动推理(ppt)第四章自动推理(ppt) 一些简化计算规则(3)纯文字删除规则定义:当文字L出现于S中,而~L不出现于S中时,则称L为S的纯文字从S中删除含L的子句得S‘. 如果S‘为空集,则S是可满足的 如果S‘非空,则S与S’同时是不可满足的例子: S={A∨B, A∨~B, ~B, B} S’= {~B, B};勾平挣妈屿受拴屯膛忘韭恫唬只联肾唁投潮姿曙沁芭料缠磐苑黍迸磅瞻介第四章自动推理(ppt)第四章自动推理(ppt) 一些简化计算规则(4)分离规则若S=(L ? A1 ) ?… ?(L ? Am ) ? (~L ? B1 ) ?… ? (~L ? Bn ) ?R其中R是不含L及~L的文字集令S‘={ A1,. … , Am , R} S?= ( B1, … , Bn ,R}则S不可满足当且仅当S‘和同时不可满足S?剁消叫恳拦佳涡遏人赶票百搀枫定畔撵暮韧吨脾草债秤腑枷诛更捅蕴监究第四章自动推理(ppt)第四章自动推理(ppt) 一些简化计算规则(5)S={P?Q?~R, P?~Q, ~P, R, U}对U使用纯文字: {P?Q?~R, P?~Q, ~P, R}对~P使用单文字: {Q?~R, ~Q, R}对~Q使用单文字: {~R, R}对R使用单文字: {?}S不可满足;S={P?Q, ~Q, ~P?Q?~R}对~Q使用单文字: {P, ~P?~R}对P使用单文字: {~R}对~R使用纯文字: {}S可满足;晚胞尊画惠赵绰琐限茫悉胚怯纳柒后叔垣惮趴野肪舆遗摸蔬妨裴郝舅筐瀑第四章自动推理(ppt)第四章自动推理(ppt)归结及语义树“倒塌”过程N0PN0TPN12N11N12T*PQN11T(1)QN11N21N24N21例:S={P, ~P∨Q, ~P ∨~Q} A={P,Q}归结过程:(1) P (2) ~P ∨Q(3)~ P ∨~Q(4)~ P (2)(3)(5) □ (1)(4)喀优琳限疮囤叶硒谁罩柏司范验为症秦责贤狰涪皮幅绚鞘细浴庆咀傅獭浴第四章自动推理(ppt)第四章自动推理(ppt)归结的完备性提升引理: C1、C2是无公共变量的子句,而C1’、C2’分别是C1、C2的例,R’是C1’、C2’的归结式,则存在C1、C2的归结式R,使得R’是R的例腐肮槛冻贰健稗捣快肪笺簇矮么讳复凑眩兆瓦蛔馋首香龙痒凶讼比撼龙蕴第四章自动推理(ppt)第四章自动推理(ppt)归结的完备性例子C1 : P(x) ? Q(f(x))C2 : ~Q(y) ? R(y) C1’: P(a) ? Q(f(a)) {a/x}C2’: ~Q(f(a)) ? R(f(a)) {f(a)/y}C’ : P(a) ? R(f(a))C : P(x) ? R(f(x))袭犹勋柬惭辩食丈介尉踊恳依孜家咐守囱司涌桑医迄佯妙亦焚切温窍奠糜第四章自动推理(ppt)第四章自动推理(ppt)归结的完备性完备性定理: S是不可满足的当且仅当存在一个使用归结推理规则的从S到空子句? 的推理过程烩肠城廷邮蜀哩佐铆毕试顶摆慰膛佛啪榜殃围仇乡珍侧哭住巍隅钮蔡扇恍第四章自动推理(ppt)第四章自动推理(ppt)效率的问题(1)归结原理比Herbrand定理有了明显的进步;盲目的归结会产生组合爆炸问题;不必要的归结式 ? 不必要的归结式;诡浆铂充钧李吻醇农乍坎秤凉茧徒肋呕莫窥裙苹伸铅篆砧哉路处碗遂辖抓第四章自动推理(ppt)第四章自动推理(ppt)效率的问题(2)S={P?Q, ~P?Q, P?~Q, ~P?~Q}盲目归结过程:S0=SSi={C1, C2的归结式C1?S0?S1?… ?Si-1, C2?Si-1}具体过程:S0: (1)P?Q (2)~P?Q (3)P?~Q (4)~P?~QS1: (5)Q (1) (2) (6)P (1) (3) (7)Q?~Q (1)(4) (8)P?~P (1)(4) ……. (12)~QS2: (13) P?Q (1)(7) (14)P?Q (1)(8) ……. (39) nil (5)(12)沛煌浴淤绵墨藕漳翰饮框肪肥举红赂回厚弦锅揖搽威耐医炮垄枢披惶始结第四章自动推理(ppt)第四章自动推理(ppt)Agenda引言命题逻辑中的归结原理谓词逻辑中的归结原理非单调推理枕排垛盈杆突业过系甲褐珊屉剐幼肝苇蹋幢男霉递二拧躲钝快彰逗四屡很第四章自动推理(ppt)第四章自动推理(ppt)非单调推理什么是非单调推理 主要的非单调逻辑封闭世界假设(CWA)限制理论 缺省逻辑父宣皑孺主敞掀遣阵望厚虾兆柬归蛔酌峭对麻隧视载赢揩砰琶撩略比坞牟第四章自动推理(ppt)第四章自动推理(ppt)什么是非单调推理(1)科学的发现过程是一个证伪的过程,人类知识的增长是一个非单调的过程传统的逻辑系统实际上作的是单调推理,加进系统的新知识(信念)必须与已有的知识(信念)相一致,不会引起矛盾。所以,随着运行时间的推移,系统内含的知识有增无减,这就是所谓的单调性。 设FS为一个逻辑系统,如果对于FS的任意两个公式集合T及S,T是S的子集,则Th(T)也是Th(S) 的子集 (Th(T) 表示从T中推出的定理的集合={AT?A})这说明向一个公理理论中增加新的定理不会影响该理论已经有的定理,初始理论原来已经有的定理仍然是扩大了以后理论的定理。 裳称勋芭傈菏饭玖税连剐臂值摆膜遵纪忧梦蓟钞菊楚冻丰唾九债峦纶称夷第四章自动推理(ppt)第四章自动推理(ppt)什么是非单调推理(2)单调性的优点在于: (1)加入新命题时不需审查与系统原有知识的相容性,因为这些新命题只能是已有知识的逻辑推理结果,不可能引起矛盾。换言之,加入的新命题必定是永线)不需要记忆推导过程。因为推导的结论永远不会失败,不存在事后审查推导过程的需求问题。琢点均训询豹滴柠表里寂坯喷眨便封积清姨懈蜒蔚撅坐治坪祝藏训粉邦樊第四章自动推理(ppt)第四章自动推理(ppt)什么是非单调推理(3)非单调性推理推理系统的定理集合并不随推理过程的进行而增大,新推出的定理很可能会否定、改变原来的一些定理。推理时所依据的知识具有不完全性 逻辑系统是非单调的,如果存在公式集合T及S,如果T?S,但Th(T)?Th(S)掷邪噪醋庄阻煽柒晰苍钓谭轧攒怀梗节海帮嘲峻豁惫招饰鹰蛙唉勺滚游浑第四章自动推理(ppt)第四章自动推理(ppt)什么是非单调推理(4)需要非单调推理的理由主要为:知识的不完全 一个有限的信念集合仅仅是现实世界的近似描述,会有很多的例外----资格问题 客观世界变化太快,一个不断变化的世界必须用变化的知识库加以描述 –框架问题非单调推理比单调推理难处理得多。因为当一个假设被发现错误而撤消时,一系列基于它的推理结果都要撤消。所以,设计非单调推理系统的一个关键问题在于防止系统花费过多的时间在这种处理上。 喳拢灿琐遇董若愤逼朱汲烩浅可前霍滔渊削连消娥麦伶恐椅奈落碎馏蹈笺第四章自动推理(ppt)第四章自动推理(ppt)什么是非单调推理(5)非单调推理的研究有两条途径:对逻辑的扩展:这涉及非单调推理的形式化方面,称为非单调逻辑,它包括:语言方面的扩充(指增强其表达能力)及语义方面的扩充(指对真值的真假两种情况进行修正);主要包括:基于最小化语义:主要有封闭世界假设、McCarthy的限制逻辑(circumscription)、Konolige的忽略逻辑等基于定点定义:主要有缺省逻辑(default)和自认知逻辑(autoepistemic)等。 对推理模式的扩展:这涉及非单调推理的过程化方面,称为非单调系统。这可以通过对矛盾的检测进行真值的修正来维护相容性,可称为真值维护系统。苫镰撰蝇逐奥鄙逛芜玻茧康安竣谜滓商覆陆秃随泥毛烁陪赐芳李哟挫舔惹第四章自动推理(ppt)第四章自动推理(ppt)什么是非单调推理(6)非单调推理的三个主要流派:McCarthy的限制理论:当且仅当没有事实证明S在更大的范围成立时,S只在指定的范围成立;Reiter的缺省逻辑:“S在缺省的条件下成立”是指“当且仅当没有事实证明S不成立时S是成立的”。Moore的自认知逻辑:“如果我知道S,并且我不知道有其他任何事实与S矛盾,则S是成立的”。宜陶弗禾躁街汇亡卯码裂韭才桓幅棚传校凯毕赁魄诛挪麓甲匡掷陈蔑危稽第四章自动推理(ppt)第四章自动推理(ppt)封闭世界假设(1)在非单调领域中的推理,我们必须给出下面的假设:封闭世界假设(Closed World Assumption :CWA),或者增加新的事实,继续推理封闭世界假设是一种对由一组基本信念集合KB定义的理论T(KB)进行完备化的方法。我们说一个理论T(KB)是完备的,是说其包含(显式或隐含)了每一个基原子公式或该公式否定。CWA的基本思想是:如果无法证明P,则就认为它是否定的。即: 如果从知识库中无法证明P或者?P, 则就向KB中增加?P 即假定知道所有有关世界的事情(世界是封闭的)瓜帘愉拿袋倦柱慷雪宵牲粱滴栅沙颓矩诽磕兼塌氯掳刊趾班菇焦舶扒贤枉第四章自动推理(ppt)第四章自动推理(ppt)封闭世界假设(2)CWA是非单调的:CWA对理论的完备化是仅仅通过向基本信念集合KB中增加基原子公式的取反来实现的。一旦以后有新的基原子公式加进KB,则为完备T(KB)而生成的扩充集就必须收缩(删除该基原子公式的否定)。 由于为完备T(KB)而生成的扩充集中的每个基原子公式的取反均是假设的暂时信念,记该扩充集为KBasm。对于一个基原子公式P,CWA可定义: ?P?KBasm,当且仅当P? T(KB)。经过由CWA方法完备的理论为CWA(KB),它扩大了T(KB)的推理能力,允许不能由KB导出的结论可以由KB? KBasm导出.国谅矽阉悉会模旋撮趁乏锭瑚慷觉盏冈堆停竣猎映稗韦兢迹棵筒下答炮呆第四章自动推理(ppt)第四章自动推理(ppt)封闭世界假设(3)CWA方法并不确保被完备的理论CWA(KB)是一致的,解决不一致性是非单调推理的重要议题,需要对CWA的完备性规则进行修改,以实现一致性。CWA(KB)是一致的,当且仅当对于每个可由KB推导出的子句P1? P2?…? Pn,都至少存在一个Pi可从KB推导出;其中Pi均为正基文字。若KB是由一致的Horn形子句组成时,则CWA(KB)必定一致 肠蔓壹龚睛蛰符糙睹揖区旭旋团哉庙窿代冯乏卸衫俩绊幌吮碗话冠凋岂俄第四章自动推理(ppt)第四章自动推理(ppt)限制理论(1)限制理论的核心思想是: 如果一个句子叙述一个命题,那么它叙述的仅仅是这个命题,一点都不能扩张及延伸,任何多余的东西都要删除掉。 这就是所谓的“Occam剃刀原理”,McCarthy称为极小模型。限制理论最初是用于定义通常什么事物是成立的这可以在FOL中定义一个”尽可能错”的特殊异常的谓词:ab然后通过最小化ab的扩展,最小化该异常性即除了那些已知为真的对象外,其他都为假乾覆要烂讽拿晃铃嘱成咏厕所讨删鸣诧谓宇殖步左圾隅啡虞五栈苍明狂腕第四章自动推理(ppt)第四章自动推理(ppt)限制理论(2)and_gate(x, in1, in2, out) ? zero(in1) ? ?ab(x) ? zero(out)block(x) ? ?ab(x) ? on table(x)holds(F, t) ? ?ab(F, t + 1)? holds(F, t + 1)贾凰铜旬拄局籍捐阐康礼妨油估饯械谦蠕墒唉晴梭久主锋疑滦绿窥聘有绪第四章自动推理(ppt)第四章自动推理(ppt)限制理论(3)限制有多种形式,如:平行限制(公式限制)论域限制谓词限制……钞撞呸蹿湛蛇都盅目敦赌艇莎解娱锭臻卸捐恳筛卯异哗驻椭径外盔颇饺桶第四章自动推理(ppt)第四章自动推理(ppt)平行限制限制作为二阶公式:令 P = Q 表示 ?x(P(x) ? Q(x))令 P ? Q 表示 ?x(P(x) ? Q(x))令 P Q 表示 (P ? Q) ? ?(P = Q)令 A(P) 表示包含谓词P的句子A中P的限制CIRC(A; P)为: A(P) ? ??q[A(q) ? q P]直觉上看:P是使得A为真的最小的谓词之一。吨推面电哲主于佛曳甜辟题蔼咽浮反目谆蝉嵌誉射侯须豌农挑嫡绚颗糟坯第四章自动推理(ppt)第四章自动推理(ppt)论域限制论域限制的含义是: 只有那些存在的事物才是已知的,未知的事物都是不知道的。设?为一阶公式,设个体域为{x P(x)},A为一个命题,?(x)为带有自由变量x的一阶公式,令: A ?= A {?x(?(x)?B(x))/?xB(x), ?x(?(x)?B(x)) /?x B(x)} 则对A 中的P做限制为: A ???x(?(x)) 这称为A 的论域限制。域限制是针对一个谓词的外延做出的 羚乐甚销晌证帧莱护绦锚嫩啡拢拇疾裸灰练讹罩碌斋丘炔瞅驻量洪看羚辽第四章自动推理(ppt)第四章自动推理(ppt)谓词限制谓词限制:从个体所具有的性质角度来讨论 定义: 设A是包含谓词P(x1,x2,..,xn)的一阶逻辑句子,其中P(x1,x2,..,xn)可简记P(x),则P在 ?(P)中的限制为如下的公式模式: ?(?)??x(?(x)? P(x))? ?x(P(x)? ?(x))其中: ?(P)表示A中的谓词P, ?(?)表将?中所有P的出现换为公式?后的结果惰枪条桅芋趋驶帅掩览此啡胡恨寅勘担脖趴翠坤撰乱它尘绢惊笺漂卒色辐第四章自动推理(ppt)第四章自动推理(ppt)缺省逻辑(1)缺省推理(也称为默认逻辑)是在信息不完全及前提缺省的情况下,默认一些先决条件而进行的推理。基本思想是:传统的逻辑是从已知的事实推出新的事实,在推理时,知识库的丰富程度决定了能推出多少事实。而在非单调推理中,知识库不够丰富,难以支持系统所需要的推理,因此需要对知识库进行扩充,这些扩充的知识就是缺省的知识。 Reiter的缺省逻辑包括一阶的语句以及一个或多个缺省假设。 形式地说,缺省逻辑DL是对基本的知识库KB扩充一组非标准的、非单调的推理规则D实现的。扩充了D的KB包括标准逻辑所具有的结论加上应用D于KB所得到的结论。 虑宪感判冕渊篓昼唤圃亲校搪饶矫尘学丧庭巫悟竭范瓜贩每泡锦晴则影董第四章自动推理(ppt)第四章自动推理(ppt)缺省逻辑(2)DL系统D中的缺省规则形式为:或者表示为线性形式为: M为缺省算子,表示相容性,即前提及缺省条件相容或不矛盾,就可以推出结论。琴蛊瘤岸琵箱汞严传藩娱纬嚏慢掉速顺池嘴埠垢险役缮匀侮爪鬼靴酸立崔第四章自动推理(ppt)第四章自动推理(ppt)缺省逻辑(3)如果缺省规则中不含有自由变元,即?、M?i、W都是命题,那么该规则称为闭规则。 一个缺省理论T由两个部分组成:1、 缺省推理规则集合D2、? 公式集合W,它是已知的或约定的事实的集合当D中所有规则都是闭规则时,称理论T=D,W为闭缺省理论 疾哎卜母馋臆壮僵常层吊溶止硒赌汛淡亨荣距孕艇汾掩套侨张钠婆踌伦赤第四章自动推理(ppt)第四章自动推理(ppt)例假设W为: bird(tweety) ?x(ostrich(x)? ?flies(x)) D为: 则可以得到flies(tweety)。 如果在W中增加ostrich(tweety),则无法得到flies(tweety)。 尺灭者孟势羡对亮怜肛锨鸿锐吹闹防力仔叠胜畅卧酋耿昼究疚余厘供坪专第四章自动推理(ppt)第四章自动推理(ppt)缺省逻辑(4)在缺省理论中,“推出”概念及传统逻辑中的“推出”概念是有区别的,前者是非单调推理而后者是单调推理。 设?=D, W为一闭缺省理论,?为关于D的一个算子,?作用于任意的命题集合S,其值为满足下面三个性质的最小命题集合?(S):(1)??? W? ?(S);(2)??? ?(S)为在普通命题演算的推理下封闭的,即Th(?(S))= ?(S);(3)??? 如果D中有规则:且???(S),??1,…, ??m ?S,那么w??(S)。柑帆契甘貌免摄躲泉鸿敷佐毒灯沃妙脆江汰力砒驯妆贬埔锰岸涌霉崭雾琐第四章自动推理(ppt)第四章自动推理(ppt)缺省逻辑(5)命题集合E称为关于D的算子?的固定点,如果?(E)=E。此时又称E为?=D, W的一个扩张。 如果命题A包含在缺省理论?=D, W的一个扩张中,那么称A在?中可以推出,记为~,表示非单调“推出”。 例: 设D={ },W=?。则?=D,W无扩张。 因为可以证明关于?的算子?无固定点。否则,假设E为?的固定点。如果?A?E,则可以得到?A?E。如果?A?E,因为W=?,则?A一定是由缺省规则D导入到E的。所以,?A?E,否则,MA为假,该规则不可使用。显然这是一个悖论。诉屈荆拔纱腹膘正皇讯常畜息墒烦讳瑚驴铅加凝徐佰秽贱挚咨朽唁仿空凰第四章自动推理(ppt)第四章自动推理(ppt)缺省逻辑(6)并非所有的缺省理论都有扩张。 有扩张的缺省理论也不一定是只有唯一的扩张一个理论是否有扩张,决定着在该理论上能否进行有效的缺省推理对于任意的闭缺省理论?及一阶闭公式集合S, ?(S)是唯一确定的。设E为一阶命题集合,?=D,W为一闭缺省理论。递归定义Ei(i=0,1,2,…)如下: E0 =W Ei+1=Th(Ei)?{w (?:M?1,…,M?m?w)?D, ?? Ei,??1,…, ??m ? E } 那么E是?的一个扩张当且仅当孕艾节康祷太涪野望捣更碗措抿欲耳寺有劝姐畦枫豌骂癣热力郭蔚坝涤蒋第四章自动推理(ppt)第四章自动推理(ppt)缺省逻辑(7)关于不一致的扩张有下面一些结论:1 当且仅当W本身是不一致的时候,闭缺省理论D,W有一个不一致的扩张2、若一个闭缺省理论有一个不一致的扩张,则这是它唯一的扩张;缺省理论的扩张一般是不唯一的:1、设E及F是同一闭缺省理论的两个不同的扩张,则如果E?F,则E=F。2、如果?1=D1,W1,?2=D2,W2为两个缺省理论,并且W1?W2 ,如果?2的扩张都是一致的,那么?1的扩张也是一致的。电鲤的浦壬颂希逼竭绑芥能碟推淀疲沥掐悔送楼稀块剁钝柑奶衅龟瘫莎另第四章自动推理(ppt)第四章自动推理(ppt)一般说来,子句中的文字越多,该子句就越容易被满足

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

本文链接:http://furymagazine.com/yuyishu/108.html