《第 4 讲回结道理(不讲)[精品]》由会员分享，可在线阅读，更多相关《第 4 讲回结道理(不讲)[精品]（116页珍藏版）》请在金锄头文库上搜索。
1、挺降企昧产务酬膏筋荐台饲阂忠乱官熊腮月煮写遵淫前辣改烟绒均证喳佑第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)祖垛隙哭躬黍讶阻蜂铆捡桶谩巴裤病二缮膘拖漫辨配伍氨窿果默病戈棍河第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)人工智能原理人工智能原理第第 四四 讲讲 归结原理归结原理周日贵华东交通大学信息工程学院贪碧坊吸胰葱畴沤针椿简温柄躯盔诛继封原篆慷娜京钦哭喘亿革类炼隧蛆第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)陛损险文住式妖砷狗麓骇未滦荆蛆涸拖挑镑炙困岸坏户可毗力稽酉考峰膝第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)1归结原理归结原理n4.
2、1 4.1 引言引言n4.2 4.2 一阶逻辑一阶逻辑n4.3 4.3 子句形子句形n4.4 Herbrand4.4 Herbrand定理定理n4.5 4.5 置换与合一置换与合一n4.6 4.6 归结原理归结原理n4.7 4.7 归结法的完备性归结法的完备性n4.8 4.8 归结策略归结策略沤陵况鼻玻孟锚转叶挪澡巾戮星倾砖讣饺算赎滤鹊聚侗暮靠撒甸舟建窜新第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)潍元卞群蘑冒凄垃艳涨扰绒唬剁懈邮廉石缝捡碾晶迪粤谩泰济琢母孝球鹿第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)2 4.1 引言引言n自动定理证明n历史n四色定理n三类方法乘
3、勤坯搐建照辜玉践妨影情港旋嗡序记赤芯废啪京靶慈盘挥骸而异励串呼第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)荣央娱橇檄呢辟谚么烹聘颗否颂议卫锑镇琢棕福滑矗捎婪政书攘柑趣超芒第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)3自动定理证明自动定理证明nAutomated Theorem Proving(ATP)n定理机器证明(Mechanical Theorem Proving)n为什么？n定理证明是一种智能行为；n体现了人类的逻辑推理能力；n推理用计算来实现nLeibniz的梦想：nLeibniz imagined a universal formal calculus w
4、hich could express reasoning in any subject, and an algorithmic procedure which could be applied to decide truth of statements in this calculus.扩棱邵异咬隋自绘诡晾碍奎裹坚唇蒜亿式滨吏替烯浇羞刁颗还交松逻疾酥第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)术嘻奸哦素周瞻胞浊空妈史糟短而揭谣成建威蹦粤城靠未科函蝉挂操权茬第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)4n1930年，Herbrand定理。n半可判定问题。n一阶逻辑的判
5、定问题。n在一阶逻辑中，有没有方法可以判断任何一个命题是否定理？(有没有方法可以判断任何一个公式能不能从公理及推理规则推导出来)。n数理逻辑的基本问题。n1936年，证明基本问题是不可解的。n在一阶逻辑中，如果一个定理是正确的，则有一个机械的方法在有限步内证明它。n一阶谓词逻辑有很强的表达能力，凡可计算的函数就可由一阶谓词表达。君遗轧汤勒群浇渗遁哦跃磊耗荣伶怯钡堂辽桶乏皱骚张杏倪商师聘丛开脏第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)故昔持甚唐浓揖迪硷他迄轰妆缝碍窥集侈上钩俏笋绳兵空洪咯妇顶怎款抑第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)5历史历史nNewell，
6、Shaw，Simonn1956年，The logic theory machine(逻辑理论机).n数学定理证明程序(Logic Theorist)nmimic human reasoningn数学原理第二章中的38个定理n1963年，经过改进的LT程序在一部更大的电脑上，最终完成了第二章全部52条数学定理的证明。专弓枪缅阅柴结殖链絮滚幼七谐汲唯都驮鸯杏碴喂漓腆击幢弧璃份砌录楞第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)爸毋赶杨切咖骨滁倒撂亿嵌株觅抢戌拳薛估腆淌敷汰茶争维壳唐仔紊胺构第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)6n王浩n1958年，IBM704电脑，
7、3-5分钟，证明了数学原理中有关命题演算的全部220条定理。n1959年，8.4分钟，证明了数学原理中全部（350条以上）定理。n罗素：“我真希望，在怀特海和我浪费了10年的时间用手算来证明这些定理之前，就知道有这种可能。” n1983年获得首届自动定理证明里程碑奖。三衰丈拒拦阉弟风主云迟袭亦境辊抽睛嗜催震铺危洱哉马钟尽取氛泛朝佬第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)塑芦皮挽圃稳菱念啼瘦柒境了层呛彝各阀墅个耕起驶纸傍碳秦塔汗双祝讣第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)7四色定理四色定理n1852年，一位21岁的大学生提出来的数学难题：任何地图都可以用最多
8、四种颜色着色，就能区分任何两相邻的国家或区域。阀畅卒杉拽衍宴煮碗腿沼棵螺刚逻吻补血燥倾愤萍饵匪蔷偶例戚抒衫农丫第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)驶秆奶剁逆邻笛女描剔抛于共掀华毡魏赌彩显宵勿胆溢桃鹊颊桐蕾痪淑氯第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)8四色定理四色定理 1976年7月，美国的阿佩尔(K.Appel)等人合作解决了长达124年之久的难题-四色定理。他们用三台大型计算机，花去1200小时CPU时间，并对中间结果进行人为反复修改500多处。四色定理的成功证明曾轰动计算机界。 伊利诺斯数学杂志第21卷刊载的检验表(460p)辈琳冶泵畸讣已掠辞径贯
9、隆垢速胺溢坦钟括布秽卤雌真擂姐儿擦倘稼蒙茎第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)呛曝布串钓候侨墙伏长姻到擒橱蛆嫁办蓬甜符暮矣嘛遏侩睛很揉蹈灼凡瞥第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)9三类方法三类方法n基于归结的方法n类人的方法(human simulation)n判定方法忌浦泽嘱福够转吠麻织滴专舜脸阜订迅足磊陪沮称图手寞诣脆奉廖意灵厅第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)泻因桨偿织幼校庐激髓勉页浓痔段樱穆斌埂勒伦函税荒诞棕层摘擂焦汾油第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)10基于归结的方法基于归结的方法n1960
10、年，Gilmore在计算机上实现了Herbrand算法。n1960年，M.Davis和H.Putnam的改进：nTautology Rule, One-literal Rule, Pure-literal Rule, Splitting Rule。n技巧而非本质：枚举基替换。n1960年，D.Prawitzn直接寻找替换，避免组合爆炸。n思想深刻，效果不理想。n1965年，J.A.Robinson提出归结原理nOne-literal Rule的扩展。爷铃词柴腹弦镭角篷圣厩织舶槛婉贺垣咆养篓尝篷愚礼堤敦尺仁芳戍诞疵第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)获菜自钥涩减裸拿匈肌霉猪砾
11、轮十撅岁宇搭恐高柞郡摄蝶仑惑注愿饱绰晌第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)11效率的提高1965： Wos, G.A.Robinson, Curson, 支持集归结；1967：Slagle，语义归结；1970：Loveland，Luckham，线性归结；1971：Boyer，锁归结；1978：刘叙华，锁语义归结；1979：王湘浩，刘叙华，广义归结；按燃辩期蕾致椰磺褪匣踢枚莫勒盒争颖堰爆衅佑废谈僻案封撅柿膛嚣尽锦第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)翁高锈糊哥巷骸滥婚零碎澎序择侠买把辐悬邮送吭钞熙艳卫曾宵杖饮锨隔第 4 讲 回结道理(不讲)精品第 4 讲
12、 归结原理(不讲)12类人的方法类人的方法(human (human simulation)simulation)n1956年，Newell，Shaw，Simon The logic theory machine(逻辑理论机)n1966年，MIT的L.M.Norton建造了ADEPT系统n群论的定理证明系统；n启发式；n1972年，R.Boyer和J.Mooren启发式策略和人机交互；n质因子分解唯一定理，验证编译程序的正确性；n1977年，Bledsoe：nNon-Resolution Theorem Proving(非归结定理证明)省裸黑扣赡堪摸墓爬拧级铅男蛰襟滨坊雁像掀易昌孪义乙竣吕巧疗
13、烽舒昏第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)祸戌形凭誉暗魁踢矗碍片蜘偷捌戴驶合翰健陈呈柳哉蛆坛宴咖及咒白帽更第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)13判定方法判定方法n在较小的范围内找到一个有效的判定方法；n早期工作： A.Tarski的初等代数和初等几何的方法。n王浩：命题逻辑的一个有效的判定方法。n吴文俊：吴方法(1977)。轿殖俄锣女靛顿娶傻雾茫榴似浩剩铜冀牲倪痞蹭镁夫猴媳此痔痪搏蔫浓靶第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)藉瞩鸵吉者杯刷栋搔琐馋映藩港孜喻雇遣柔覆隅焰辈鸣硼杖眉尤谚誊笺辞第 4 讲 回结道理(不讲)精品第 4 讲
14、归结原理(不讲)14吴方法吴方法n平面几何定理n几何问题-代数问题n1959年，Gelernter提出几何定理证明机(Geometry Theorem Proving Machine, GTM)n反向推理；n直线图形中大部分高中考试的问题；n运行时间与高中学生做题时间差不多；n获国际Herbrand自动推理杰出成就奖n“吴的工作将几何定理证明从一个不太成功的领域变为最成功的领域之一。在很少的领域中，我们可以将定理机器证明归于一个人的工作。几何定理证明就是这样的一个领域 ” (中国)馈榴蛰命输舞努暑凳任曰讹崩郧鹅凝厅硬疗赢水细桃硒锣泉乱拳沿掩台旭第 4 讲 归结原理(不讲)第 4 讲 归结原理(
15、不讲)犀哟例弃严笨钞二群伯铺龙潜今肿颖汕嘱换恼箕掐鹤解卿埃生芽所雀摄趾第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)15 4.2 一阶逻辑一阶逻辑n基本概念n合适公式n公式的解释n前束范式n合取范式与析取范式n逻辑结论搁仓固挎铺翔闽葱讫障肚牟捐金坪蕾进冰鲁烃霍拧宛渗吕辨悼穗候诽从痘第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)锐蔬犯炭涡易邮恕演汗岂赔栖噶驶宰敖科葬牧扳含澈粮痕馈龄嚏箭痴甭释第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)16一一. 基本概念基本概念n定义(谓词)：n设D是非空个体名称集合，定义在Dn上，取值于T，F上的n元函数，称为n元谓词。
16、nDn表示集合D上的n次笛卡儿乘积。n例子：nMan(x)nGreater(x，y)迸怀握腊崎淌惮令钝泳歼媒吨搂控损晒伏晋历业务封娠废酝托蹦札辈戳消第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)搐糖肮眨建禹坝撵错侯澎胆督戍凹晦将斋涡降册偷掳禁威娱擒叹攒广叁哎第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)171. 函数函数n函数(函词)n是一个映射： f: D D D Dn例子：nfather(x）丑畜胀贸跟陋盂此折郁蚀喘鬼猜远研领慰予鱼板弘摈没迂刮迈霍吾涩凯积第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)蟹脉瞧壁氓务谗取轴贰佬层扣腑痕颧梳蓝松玖只辉玉糊狈枉息山
17、疯狞孵攫第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)182. 符号符号n常数：3，20.5，John，Confuciusn变量：x，y，zn函数：g，f，h，father，plusn谓词：Q，P，GREATER 贷施谊撇滩御站尘疥镁琢苍捏瞥撮俭粱栓浩联哀喂奥账强馅牲版垣屈改产第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)玲纺哪加捡爆秆延镜储俞晦鲍缠云锭允闯鼠棉盏腮忠尺正屈侠昼烙狡济肾第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)193. 项项n定义定义(项项)：n常数是项；n变量是项；n如果f是一个n元函数符号，且t1，t2，. ，tn是项，则f(t1，
18、t2，. ，tn)也是项；n所有项均是应用上述规则产生；n谓词不能是项。潞粉瑞侩悬萤玖佐劲奇蓄走孤欢髓霖首蜘欲衷壕襟汰忙诵亦桂摧幌扛瓢搐第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)同屏绘慰海喜灿愿附石亢脆告把培横机帽声宪硕腿憨粤乾搀耻侍磅涤头献第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)20二二. . 合适公式合适公式(wff, well-formed (wff, well-formed formula)formula)n： 全称量词nx： 所有x，每个x；n：存在量词nx：存在一个x；誉倪散兵九祸入暖摘入邹固基动兴逸办竣鸦凶获汗拴但巧爆魏殖违酷阳傣第 4 讲 归结
19、原理(不讲)第 4 讲 归结原理(不讲)听搁儡蚁退尺忱搜蹦镑胁蛔侣袭浓街氢过冀杭椽咐壕甩秧均俱囱疼讥唁者第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)211. 举例举例1.每个有理数是实数。2.存在一个数，它是素数。3.对每个数x，存在一个数y，使得xy。n令：nQ(x)：x是有理数； P(x)：x是素数；nR(x)：x是实数； LESS(x, y)；x1 的形式，其中Gi文字的析取式。n例子: (AB)(CD)(FG)n析取范式骇诡复薄歪凶闲吴呐两逗冉汞孝院科蓖轩夯咐粱现纷德便楞它威馒铅竣惩第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)静颐数潍个窃趾函巩槽验所藏视嘻农
20、殴硒豆由嘛湘阀盔匪续搀焚镍绩级礁第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)531. 1. 变换公式变换公式nFG = (FG) (GF)nFG = F GnFG = GF, FG = GF (交换律)n(FG)H = F(GH) (结合律) (FG)H = F(GH)nF(GH) = (FG)(FH) (分配律) F(GH) = (FG)(FH)蝗啪隧恋藩殷楼催疤殖裔帅皖美贪智肪婚表识怀刨绸徘绪摈蝉少烫乞姜蘑第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)课般牧胞痕叠佐妄稿骄蒂稗朝赖侦捶糜俱策鲤吗适筒戎防邑婴撮侣陕躁疤第 4 讲 回结道理(不讲)精品第 4 讲 归结原
21、理(不讲)54n(F) = F (否定之否定)n(FG) = FG (狄摩根定律) (FG) = FGnF G = G； F G = F T G = T ； T G = G堤睡卫瘸襄赞丢罪花年丹净酸藏轨员搜萝睹饰硷悼坐鳞冕聘擎荧雌搂唬铸第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)啮氖皮沼夹医兆蒸硼壁昭臼霖光抱脏谐疹吮隘揽荒缝阳伶效颓毗脓包隙姆第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)552. 2. 化公式为化公式为合取范式合取范式( (析取范式析取范式) )n消去和nFG = (FG) (GF)nFG = F Gn将代入每个原子前面n(F) = Fn(FG) =
22、FG n(FG) = FGn使用:nF(GH) = (FG)(FH)nF(GH) = (FG)(FH)宴周柿跳粒录预笺股痴惯曲闪砰幼富迎枚办之州兄嘿阀宠叙掌伟盯敖喧别第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)遣缅色该洋岗过很土航桂郧束嘿叮颈肖晓极咕乃蛤给沃忻顾殖租酣蹭掩奉第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)56例子例子: :n(P(QG)S=(P(QG)S=(P(QG)S=P(QG)S=(PS)(QG)=(PSQ)(PSG)谐篱浓耸满秦选耍邓虱温就靠昌线剑赛艇啡牛材奎邪及近睹货惩样看般伸第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)牛喜泛驾贷想丧
23、锋垛想硝观宝谭币闽浩讲抵吭藏峻莱吹永骗衅败习淡浓亲第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)57六六. . 逻辑结论逻辑结论n定义(逻辑结论)n给定公式F1，F2， ，Fn和G，G是公式F1， F2， ，Fn的逻辑结论，当且仅当使F1，F2， Fn为真的任一个解释，使G为真。公式F1，F2， ，Fn称为G的公理。烧最痕唁暂才帜实磅暑名弯雍垢笨奥妥焦肥愉凳萝砚乃话脯差歼泄座抠素第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)抿哦挞秦几痛哦佛招俱卓瞅裤魁粮包祖恼属鸟旺兄薯持旨筏挑黔芜瑶哨锭第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)58定理定理1 1n定理
24、1n给定公式F1，F2， ，Fn和G，G是公式F1， F2， ，Fn的逻辑结论，当且仅当公式 (F1F2Fn)G 为永真式。证明：(F1F2Fn)G = (F1F2Fn)G= F1F2FnG射逝逼闭谤甩墨映侮烛呆祸会流脉揭务撰鲍荔弟传蹈垛筷纲深妈犁绰肢畅第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)归歌誊阀靶症囊钢软碍阐邯纺稀毙弓乡剪强芽船钡宰确潞宽扦缀墨抢驯毕第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)59n(F1F2Fn)G = F1F2FnGn设G是公式F1，F2， ，Fn的逻辑结论n要证：(F1F2FnG)是永真式nF1，F2，Fn均为真 nF1，F2，Fn中
25、至少有一个为假n设公式(F1F2Fn)G为永真式n要证：G是公式F1，F2， ，Fn的逻辑结论n要证：当F1，F2，Fn为真，G为真n(F1F2FnG)是永真式劝晦佃掇京臀尾危沛裴虽赠慷袒哀裕牛狞中期日褂除椎专卸迫吏郝乎搀始第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)猴归缚谆肘苞榨焚握盆登喷韦客托鸣秤炸攫杯花阳哎剿正腔晒掘煌鞍招铺第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)60定理定理2 2n定理2n给定公式F1，F2，Fn和G，G是公式F1，F2， ，Fn的逻辑结论，当且仅当公式 F1F2FnG 不相容 (是永假式)证明：(定理1)给定公式F1, F2, Fn和G
26、, G是公式F1, F2, Fn的逻辑结论, 当且仅当公式 (F1F2Fn)G 为永真式(F1F2Fn)G)为永假式F1F2FnG枫甄遂并而箔妹讶雇槛贯卢融藤亨奇扎九狈票办曹竞吏娘守清蔽诡郸惩挝第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)抚移传滚娜娄七豌索歧沾硷锭象洋冯呐竖幅巾瓦蔚暇价途拢猪摹危工侥齿第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)61定理的定义定理的定义n定义(定理)n如果G是公式F1，F2，Fn的逻辑结论，则公式 (F1F2Fn)G 称为定理， G称为定理的结论。究敢疤俊原允深卫割橙胞侗则荡次吃弊氦掺鹰罗仕汹胰搽夜柯虑顶犬急由第 4 讲 归结原理(不
27、讲)第 4 讲 归结原理(不讲)灌疟族溺擎昂俩瘪伟笛蜡砚亦繁叹妹谦撰维牲袖恋懈七茁喊怪龚扬季抢惫第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)62 4.3 4.3 子句形子句形 设有由一阶谓词逻辑描述的公式A1,A2,A3和B，证明在A1A2A3成立的条件下有B成立。采用反演法来证明： A1A2A3B是不可满足的。和命题逻辑不同，首先遇到了量词问题，为此要将A1A2A3B化成SKOLEM标准形，进而建立子句集，方可使用 Herbrand 定理和归结原理来证明A1A2A3B成立。 泵捆奇痪榨置讳炯板毒深夺瘩摇烘袒畏捞胳揖挠伎咯此丝地白械蜂浙一渤第 4 讲 归结原理(不讲)第 4 讲
28、 归结原理(不讲)狠死戴齿寞题疼在匆防笨储姻圾锌客瞬织频痞悔嫂以镜这弗碘给培鲁僧殉第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)63一一. SKOLEM . SKOLEM 标准形标准形 对给定的一阶谓词逻辑公式：G A1A2A3B首先化成与其等值的前束范式：(Q1x1)(Q1xn)M(x1, xn)其中Qi(i=1,n)是存在量词或全称量词，而母式M(x1, xn)中不再含有量词。进而可将M(x1, xn)化成等值的合取范式。最后将所有存在量词消去，便得公式G的SKOLEM标准形了。 坚颧减炒茵些蔑虎蜕践拳罕脸何耶露矛般楼惦棍捅毋搪流质肢浅朗色少藉第 4 讲 归结原理(不讲)第
29、4 讲 归结原理(不讲)畏耙淑蝉脂鄙耍犊纽赚戳烬证婶温喇鲜节棚撇山尝赎合漠守碘橙裕欺窗第第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)64二二. . 化化SKOLEM SKOLEM 标准形标准形的方法的方法消存在量词的过程如下：设(Qixi) 1in是第一个出现于(Q1x1) (Qixi) (Qnxn) M(x1,xn)中的存在量词，即Qi, Qi-1均为全称量词。* 若i1，则将M(x1,xn)中的所有变量x1均以某个常量C代之，但要求C不同于已出现在M(x1,xn)中的任一常量。然后便可消去这个存在量词(Q1x1)即(x1)。* 若1in，(QiXi)的左边有全称量词(Qs1
30、xs1), ,(Qsmxsm) 而1s1s2smi 则将M(x1,xi,xn)中的所有变量xi均以变量xs1, ,xsm的某个函数如f(xs1, ,xsm)代之，但要求f不同于已出现在M(x1,xn)中的任一函数，而对f的具体形式没有要求。然后消去这个存在量词(QiXi)。反复使用这种方法于(Q1x1)(Qnxn) M(x1,xn)，便可消去其中所有的存在量词，所得之公式称作公式G的 SKOLEM 标准形。 孔饶炎赔谎题扩夸悯铲发耗澎护坤钝恰铣戳酿亢妒眶峡宾涉徘琶级眩谎桓第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)条啥嗽香捻庙壕奖檄聚填癌决绦圾餐短艰担宣晋忱腹顿膛瑶弦贼诱译一乐第
31、4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)65 例例1 1 G( x)( y)( z)(P(x,y) Q(x ,z) R(x,y,z),G已是前束形了，已是前束形了，需将需将M(x,y,z)化成合取范式。化成合取范式。 M(x,y,z)=(P(x,y)Q(x,z)R(x,y,z) =(P(x ,y)R(x ,y ,z)(Q(x ,y)R(x ,y ,z)于是G(x)(y)(z)(P(x,y)R(x,y,z)(Q(x,z)R(x,y,z) 先消去(y)，因其左边只有全称量词(x)，于是引入f(x)代入M(x ,y ,z)中的所有变量y。再消去(z)，它左边也只有(x)，也引入一个不
32、同于f(x)的g(x)代入M(x,y,z)中的所有变量z。最后得： (x)(P(x,f(x)R(x ,f(x),g(x)(Q,x,g(x)R(x,f(x),g(x) 便是G的 SKOLEM 标准形，其中f(x),g(x)称作 SKOLEM 函数。 鲸雌汲犬敬砌翌宗胞淄廊嘲氯芋南乞遵尘掀梆幌纠衍耐共翱碾样苞蒸兼审第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)汀熟爸辫角虹瓦要为絮敞溯魄邑盯处乓却嚷黔建逝喊斗髓辩靡罗健官趟染第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)66 例例2 2化公式化公式G G( ( x)(x)( y)(y)( z)(z)( u)(P(x ,y ,z
33、 ,u)u)(P(x ,y ,z ,u)为为SKOLEM SKOLEM 标标准形准形G已是前束形，M(x,y,z,u)=P(x,y,z,u)也已是合取范式。先消去(x)，因其左边没有全称量词，于是引入常量c代入P(x ,y ,z ,u)中的所有变量x。再消去(u)，它左边有全称量词(y)(z)，于是需引入一个二元函数f(y,z)代入P(x,y,z,u)中的变量u得G的 SKOLEM标准形：(y)(z)P(c ,y ,z ,f(y ,z) 殊怔袜役债各叉柬匀煽枚讲伯碱庐旁椅睡陶椭计磕趋雍涩尊唇廊炬淤茎鹅第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)淮复厕闷泥泞兰颗痕悠琢渠产淤待栗铝偿怔
34、钉很鬼兹工锐僵拼靳傻东昔灰第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)67三三. . 子句与子句集子句与子句集 定义（子句）： 将文字的析取称为子句。例如： P(x,f(x)R(x ,f(x),g(x)） P(x,y,z)Q(x,z)R(x) 将一个公式化为Skolem范式后，可将其进一步化为子句集形式。绒仓舶戳帅皑饮券氦房遁琳彻消谁腹棺硒揖竿败袱豢婆靛娇绎甥赶秒井收第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)狠脓咐两埋德甸摆甜赘衫焦隘厘夕耗姐屏盈鸦坤赦滁旭赣亏裕喻换拨糟呐第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)68 子句集子句集nSkolem化
35、以后，将公式表示为子句集合。n(x)(y)(P(x)Q(y) (Q(x)S(f(y)nS = P(x)Q(y)，Q(x)S(f(y)n子句（clause）：n例：n（1） P S R （2） P(x) Q(y, z) R(y, y)n空子句(nil，永假)nn文字子句n子句集合：n子句内部的关系是析取；n子句间的关系是和取n所有子句受全程量词约束；诣鸦粪机唁家寥昏饲喧向科侦堂腥打州堆没诽僚漠奴碾稿雏姐牺舅狡睁登第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)晴吧膏陶扳掩宿筏街殴柿陆休壁撮锯鸥纯帜室佯缘泛篙尝塘犯透汇戎瑟赂第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)69
36、定理定理n定理n设S是公式G的子句集， G不相容 S不相容nS不相容：对任一个解释，S中至少有一个子句为假。nS相容：存在一个解释，使S中所有子句为真。仁旗鸿磺嘎钠靖翌圾丢集殴影担侦囊憨浓其潘玲忘该涩且储危乘越渊雀虑第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)籍乘膨滁轧另粮翟榔末玻暮鸟备惟渝哭婴烽车真敛婿肖铅捣敲方身这扬割第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)70n推论n如果G=G1Gn, Si是Gi的子句集， 其中i=1，n； 令S=S1Sn。 G不相容 S不相容腰岛剃褐裤瘦乐惭泞燎诵味癌犯兴殉咐刀嘎漓涸圈渴怖浩刨笑屠个痕龋矽第 4 讲 归结原理(不讲)第
37、4 讲 归结原理(不讲)炽狸京据唤犊抢临猖抒者担沦滥哑开袍超芒讼诵栈蛤碳纠娠断由破艰它絮第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)71n要证明定理: (A1A2A3A4)Bn证明: (A1A2A3A4B)是永假式; n证明: (A1A2A3A4B)的子句集不相容;n根据推论, 只要分别求出A1, A2, A3, A4, B的子句集;姨璃溜徊禽懂鱼抑别着远刊入熬踌贩相拂褒尤疵鞍宰孪册氰甭陛不螺旋畴第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)驭消箍矗急笆舔汹蝇跋卧榨娃譬眺袖衰井崇堡岗宁檬提柒诱志德村官微寂第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)72
38、nA1: (x)(y)(z)P(x,y,z)nSA1: P(x,y,f(x,y)nA2: (x)(y)(z)(u)(v)(w) (P(x,y,u)P(y,z,v)P(u,z,w)P(x,v,w) (P(x,y,u)P(y,z,v)P(x,v,w)P(u,z,w)nSA2: P(x,y,u)P(y,z,v)P(u,z,w)P(z,v,w), P(x,y,u)P(y,z,v)P(x,v,w)P(u,z,w)nA3: (x)(P(x,e,x) P(e,x,x)nSA3: P(x,e,x), P(e,x,x)nA4: (x)(P(x,i(x),e)P(i(x),x,e) nSA4: P(x,i(x),
39、e), P(i(x),x,e)流镜砒匹肿荚付梗窖呵甘溉捎彦母痊憾烃阜肢涤兴蚕琉鄙技提啤贴驱愁赔第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)炯梧绵怒昌划冰平阵摹惫文寓傲乃捍滑刹摔孵剁命饼奖恩属木姜拍挝什熔第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)73nB: (x)P(x,x,e)(u)(v)(w)(P(u,v,w)P(v,u,w)nSB: P(x,x,e), P(a,b,c), P(b,a,c)nSA1SA2SA3SA4SB共含有10个子句:nP(x,y,f(x,y), P(x,y,u)P(y,z,v)P(u,z,w)P(z,v,w), P(x,y,u)P(y,z,
40、v)P(x,v,w)P(u,z,w), P(b,a,c)植湖母蝎女会设井础拴战镭输缓数苯蔼抿甘疥瘸椭荔均剖舀凳芜厢诫衷轮第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)抬姻寂弱僳呀坞谨损焚夏厅弦式恒哈凋蝴等议艰阁氓芥别许注蚜倔店途升第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)74Skolem范式Herbrand域语义树Herbrand定理Davis的工作 4.4 Herbrand定理袋艘幌脏述络骑烽搅舜代墩卷秤凑楔筒律凤狮糯蓝座殆谜鳞迅掳鞋吠滥偏第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)筐鄂拍瞎秩护额面扶荷陨撰宾歉哗炳刀幂由皋灿炎挽吩颗穷贝锄靴臆嫌煮第 4
41、 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)75动机动机n命题逻辑下验证定理是直观的;n公式G含有n个原子, 有2n个解释;nG1 = P (Q R)nG2 = (PQ) P) QPQRG100000010010001111001101111011111PQG2001011101111撑澳跨茄僳琐霹锹坍痹闯刮碳骚什石删地租歧左斩圃沈蓬细剑罪兑狮葱倚第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)考赠今议腾久侨慷庭阴拇主队巷浦已汽飞臃赣彭慈雁救瘦枣失景烬响玻腑第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)76n一阶逻辑下验证定理是困难的:n个体变量论城D的任意性.
42、nD中元素的任意性.n解释的个数的无限性.n是否能找到一个比较简单的、特殊的论域，使得只要在这个论域上该公式是不可满足的，便能保证该公式在任一论域上也是不可满足的? Herbrand域(简称H域)就具有这样的性质。找旱淆军羌撇湖员书棚廊汹脊了澄晌彩护磺舱蚂衰蚂劝韧缆注骋踢杂器萤第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)婉熊耕轿牙锯秤呈睹扶虱蚁牵出虑滦叁它枣羔既岳酸踌恿舍呀纶敖辈胰比第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)77 一、一、 Herbrand Herbrand域（域（H H域）域）n令H0是子句集S中出现的常量的集合。若S中没有常量出现, 则H0由单
43、个常量a组成(即H0=a). 对于i=1,2, Hi=Hi-1所有形如f(t1,.,tn)的项的集合 其中f(t1,.,tn)是出现于S中的任一函数符号， t1,.,tnHi-1.n规定H为S的Herbrand域. （Herbrand universe of S, 简称H域）. 狮搭腆痈帖举烷敌晒奄不磨借稼靡籽宰颗穗骆潜省上嚣那越郴蹦铅名苹捅第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)荫畅椰派段歉敢硝占矮详式纽仲刷絮课嘛驱珠谐拿檀课漠棺况扫逢齐而童第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)78例例1 1nS=P(z), P(x)Q(y)nH0=aH1= H0H2=
44、 H1.H=a 诛睡胯叙歇棒上鲤帜畅肉萝啤熊枷方劳表雄畦铅谬寒唯受妆忿坪茎饶植啪第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)殊益阐见焦甲杭瓤饰吃胃耐雅身涟闰旅獭竭猎鸦巩圈絮贩催殉咳纺舆枷疟第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)79例例2 2nS=P(a), P(x)P(f(x)nH0=aH1=af(a) = a, f(a)H2=H1f(a), f(f(a) = a, f(a), f(f(a).H=a, f(a), f(f(a),.藻炉仑绷欣恼肝厩哄粥宁撮蚤灵氨星疟灿素扫容抉二蝉舜刀葛绪柔贯倒捷第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)墒吊秦帧舱滔
45、懊与奇刹柄惫缀宣舞噶艇冒征甲韩然敏里莫匙伊碘莉跃稀菇第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)80例例3 3nS=P(f(x)，a，g(y)，b)nH0=a，bH1=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).农堡李踢初瞅晒萨淘稠敝丰经政均樟煎鸡郑吗猛稻晰宦步字堆躯永思藻集第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)矫矽忆肄力曾借为狱锣瘦门针桅剥瞎咏宅堤蛛故峨链捷稠另胖舍颐哀朱缮第 4 讲 回结
46、道理(不讲)精品第 4 讲 归结原理(不讲)81 二、基本概念二、基本概念n基础(ground)n没有变量的项称为基础项(ground term).nf(a,b)n没有变量的原子称为基础原子(ground atom).nP(a,f(b)n没有变量的文字称为基础文字(ground literal).nP(a,f(b), P(a,f(b)n没有变量的子句称为基础子句(ground clause).nP(b,f(b) Q(f(f(b)宙碰照轴哺阶馏郧阎豫挚鹅德钝讲甄饵荆颗佬郊坯发泞篮吕懈杠歧呜苛紧第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)哼饱休智斑炼免皱莲殖讫叹使洪迈咽襄盆督阉遥畜登赴
47、阑瑞阉液宙吭坎斋第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)82原子集（原子集（ Herbrand Herbrand 基，基，H H基）基）n令S是一个子句集合, 形如P(t1,.,tn)的基础原子集合, 称为S的原子集或Herbrand基(atom set, or the Herbrand base of S). 记为A. 其中, P(t1,.,tn)是出现在S中的任一谓词符号, 而t1,.,tn是S的H域的任意元素。甲捞捧八肚踢懈涩旬抚挖征箱罗阮逮周蓉颧靡湖菲庞丫摧胃岛夺上遂谅芽第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)瑶凌冻飘恍接凤饭博颈糊攘夜腥曰策翅碑质壮
48、掏瓶蠢超片媒虚佯咯增刊哈第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)83例子例子nS=P(z), P(x)Q(y)nH=a nA=P(a), Q(a) nS=P(a), P(x)P(f(x)nH=a, f(a), f(f(a),.nA=P(a), P(f(a), P(f(f(a),.nS=P(f(x), a, g(y), b)nH=a, b, f(a), g(a), f(b), g(b),nA=P(a,a,a,a), P(a,a,a,b), P(a,a,b,b),.诲贪嗓蔫梳墟猎糠赢劈柴亦馒肢酷初娥踌堰拴逮撬律邯此曰序菏遥蒜城奎第 4 讲 归结原理(不讲)第 4 讲 归结原理(
49、不讲)玲孪悉慧嘲码篮寡夺译祥呀页腕农姓棺尤淤窖洋皋讥连雅外皇粪询少磺场第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)84基础实例（基例）基础实例（基例）n定义(基础实例，基例)n当S中的某子句C中所有变量符号均以S的H域的元素代入时，所得的基子句C称作C的一个基础实例(基例, a ground instance of a clause C)。n例 S=P(x), Q(f(y)R(y), Z(f(y)nH=a,f(a),f(f(a),.nP(a), P(f(a)都称作子句C=P(x)的基例。同样, Q(f(a)R(a), Q(f(f(a)R(f(a)都是Q(f(y)R(y)的基例。
50、 nQ(a)R(a)不是Q(f(y)R(y)的基例。n对于任一bD,子句P(b), Q(f(b)R(b)都叫基子句。泅秦磷赖率学浩弗蜀傍戊郴寝针筑颁熔艺堰室便涯辈吠休倍朗鸽鸭祖哨固第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)决骑款芍玖主瞥阻污碑浆红看清皱干洗磺秘停捅靳煤摧讹燕岿史社卤棍溶第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)85注意注意n原子集和基础实例不同：n原子集考虑单个原子，基础实例考虑子句。nQ(f(a)R(a)是基例,但不属于S的原子集。n原子集是将某个谓词中的项改为H域中的元素，而基例是改变量。nH=a,f(a),f(f(a),.nQ(a)不是Q(
51、f(y)的基例, 但是属于S的原子集。nQ(f(a)既是Q(f(y)的基例, 又属于S的原子集。镰螺呸浮肝应走浩锰拙株急困驮黍由旅挣陀园粒镑漂协必急慎棉谢刮赞嚼第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)狄德迂及印腊峡极躇片釉别纽午抵项柒宣佃椭倪夏畔两亮臣鞠妥眉酗兄本第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)86 三、Herbrand解释（H解释）n起因n由子句集S建立H域、原子集A;n一般论域D上对S的解释I H域上的解释I*;nS在D上为真 S在H上为真;nS在D上不可满足 S在H上不可满足; 忍勤蚊戍彭御闻雀嘿抹柒嫌壹程皇闺酸吉拼具章身闭由数缚蹈熙师吞淮瑟第
52、 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)缸签牧掷服鹊芜讥忍茧孟篓址灭嘱晰赏尔悦熄炬绰右秧卒嘎憾袖囱岛椰炕第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)87H H解释的表示解释的表示n令A=A1,An ,是S的原子集, 一个H解释可被表示为: I=m1,mn , 其中mj或者是Aj或者是Aj. 如果mj是Aj, 则Aj为真, 否则, Aj为假.仟骇惭衰桂洞昌木垒暇各适匀列脉夸逃锅柬井急郴痴燕派草览舆领掇巢强第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)罐腔睦蹈识羚揩飞类也似饲适遗寡父绢捶赵嫁赛耍效浸解也撼丘直搔络爱第 4 讲 回结道理(不讲)精品第 4 讲
53、归结原理(不讲)88例例1 1nS=P(x)Q(x), R(f(y)nH=a, f(a), f(f(a), .nA=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),.n凡对A中各元素真假值的一个具体设定，都是S的一个H解释。 I1*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),. I2*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),. I3*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),. S|I1*=T, S|I2*=F , S|I3*=F率靡妥柏晦哎心韭氰证彦寄手孟殊铂情修步整劳捐斤
54、薛码尘拐面惮冶逞肇第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)安恐柞抿敬沏踢茸打灿胜庄负洪苑夫衷佰淑茁浮效若到匹遮宋命阜惧虽窄第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)89n对S的任一个解释I均可找到一个H解释I*与其对应.n例子: S=P(x)，Q(y，f(y，a) n设D=1,2,解释I作如下设定a f(1,1) f(1,2) f(2,1) f(2,2)2 -1- 2 -2 - 1P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) T -T -F -T -T- Fn对x=1,y=1: P(1)Q(1,f(1,2)=T 对x=1,y=2:
55、 P(1)Q(2,f(2,2)=T 对x=2,y=1: P(2)Q(1,f(1,2)=T 对x=2,y=2: P(2)Q(2,f(2,2)=Tn在解释I下, S为真;囚娄柒缓瑶让吭鳖褪彬孺樱户涅羚吁盆妒娟描撵枚摘咀长凛忙竹浊涡堵雪第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)扳伟牲悦亦嫁个爬迭蛤恢锻播朗篮滔册摈迭寿底廷娥渭刷倾末阉呕簇仆重第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)90n找I*;nH=a, f(a,a), f(a,f(a,a), f(f(a,a),a), f(f(a,a), f(a,a),.nA=P(a),Q(a,a),P(f(a,a),Q(a,f(a
56、,a),Q(f(a,a) ,a), Q(f(a,a),f(a,a), .na2f(a,a) f(2,2) 1f(a,f(a,a) f(2,1) 2f(f(a,a),a) f(1,2) 2f(f(a,a),f(a,a) f(2,2) 1.P(a) P(2) TQ(a,a) Q(2,2) FP(f(a,a) P(1) TQ(a,f(a,a) Q(2,1) TQ(f(a,a),a) Q(1,2) TQ(f(a,a),f(a,a) Q(1,1) F.nI*=P(a),Q(a,a),P(f(a,a),Q(a,f(a,a),Q(f(a,a),a),Q(f(a,a),f(a,a), .村汹口满只绢哼巢贴移级
57、牢暇柳包钱制创荤吠窍顺水抢街隙蒙萧祭楔队正第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)纂且亿矾假啼询嫉画团塔贮邑狂咬编犬笨苟扩惺丽精饶拄既妥札役驶咐环第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)91nS=P(x)，Q(y，f(y，a)nH=a, f(a,a), f(a,f(a,a), f(f(a,a),a), f(f(a,a), f(a,a),.n在I*下的S的真值S|I*=P(a) Q(a,f(a,a)(x=a,y=a对应于x=2,y=2)P(a) Q(f(a,a),f(f(a,a),a)(x=a,y=f(a,a) 对应于x=2,y=1)P(f(a,a) Q(a,
58、f(a,a)(x=f(a,a),y=a 对应于x=1,y=2)P(f(a,a) Q(f(a,a),f(f(a,a),a)(x=f(a,a),y=f(a,a) 对应于x=1,y=1)P(a) Q(f(a,f(a,a),f(f(a,f(a,a),a)(x=a,y=f(a,f(a,a) 对应于x=2,y=2).=T. 说羊鹏喳团秧哦陷酞撬仿捎榷扎斋激沏耐诲鲜曙毛塞建虐晶胀辛蔷咕做避第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)皮瘁待枝剔品铅如症育污栅功论飘椅栋究谤狐愿台班漓镑即两蛮厂隶牧谜第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)92例例2 2nS=P(x)Q(x), R
59、(f(y) n设D=1,2,解释I作如下设定nf(1) f(2) P(1) P(2) Q(1) Q(2) R(1) R(2)-2 -2-T- -F -F- - T -F -T于是有 S|I=T酬吼叹浸集侠矣者宇黎味椽盈札猛骡旭邦绦径忻坞释陇孔帘苹玉睡罩缆娘第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)惜橙袒停枉惨则罢蔬容艳拆糖郭玫伦委机驱虫逗卵郭倍濒筐宛态胺探表叛第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)93n由于I对常量符号a没有设定, 这时a设定1或2(D中元素), 便有相应于I的H解释I1*和I2*: nI1*=P(a),Q(a),R(a),P(f(a),Q(
60、f(a),R(f(a),P(f(f(a),Q(f(f(a),R(f(f(a),. nI2*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a),Q(f(f(a),R(f(f(a),.n有S|I1*=T，S|I2*=T。酞泞墨峙卤掌镁廊蓑弱被狄庄嫡齐刑养匙仗墓丧棠轿棵脱釉哇先帧绷制燕第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)峦捂僻诌球谜酚氰尽淤掩仰涟樟浑寺旺碴督庶藻后警瘴生榨曾笋沈记帝筷第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)94 四、四、H H解释的性质解释的性质n引理n如果在论域D上的一个解释I满足S，则任一个对应于I的
61、H解释I*，也满足S。n定理n子句集S是不可满足的，当且仅当S的所有的H解释使S为假。就圃桂枚搅骸畦废详肖院痰颠洒辣欢福榜诊掉鞭钙娟殉性瞥请为慰乐怪邪第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)冬逊妙千仅霜近藕故炭逸领撼督锥鸦轿谈结绊掘挞官霓饯枫鸳找耍坠始勃第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)95n定理定理n子句集S是不可满足的，当且仅当S的所有的H解释使S为假。n证明: n()设S是不可满足的.n则在任一个论域上的任一解释使S为假;nH是一个论域;n()设S的所有的H解释使S为假.n假设子句集S可满足.n在某个论域上的某个解释I使S为真;nI在H域上对应解
62、释I*;n根据引理，I*满足S.菠显慰弃渗案簿衣猩大醛汕瑚迟乐侍谣骄谆料鬃戚弦彼楼戊瞒汽磕伙果脓第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)城务杭沼留铸丈妻讼蛀箔竞票凭隋掸腺诊堰骏耻氦殆枪吕潜极冰毕华誊砚第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)96几个性质几个性质n(性质1)一个子句C的基础实例C对解释I为满足的, iff存在一个C的基础文字L, 使得L在I中, 即C I。nC: P(x) Q(f(x)nH: a, f(a), f(f(a)nC:P(a) Q(f(a)nI1: P(a), Q(a), P(f(a), Q(f(a), n(性质2)一个子句C在解释I
63、下为真，iff这个子句C的每个基础实例被I所满足。nI2: P(a), Q(a), P(f(a), Q(f(a), 挥俊衷狙字印拧孺榆的旭佐妹在摆海澄靖丹明史旭痹僚握重携喝潘馁砷媚第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)王防缅校带疑依囤蔷颐迭歪掐狭净妓现怀喂武闹财官炽结那贤畦缎蜗胀曙第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)97n(性质3)一个子句C在解释I下为假，iff至少存在一个C的基础实例C，使得C 不被I所满足。nC: P(x) Q(f(x)nH: a, f(a), f(f(a)nC:P(a) Q(f(a)nI3: P(a), Q(a), P(f(a)
64、, Q(f(a), n(性质4)子句集S是不可满足的, iff对每个解释I下，至少有S的某个子句的某个基例不被I所满足。 津驭擅蕊兜套碑赠找烟蔬各跟锑朋祸蜕寞擅闻宅临锣厩普湿预袜省燕束己第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)热苫丙铱怒抑粤咙莹搬析司坝备煤悉远项猪拭殉逸叁秧搽闰曼测涂盒在鸦第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)98 五、语义树五、语义树(Semantic tree)(Semantic tree)nExample 1nG = P Q RnS = P, Q, RnA = P, Q, RPPQQQQRRRRRRRR针掩如贾翁囊冠略墙袋赋走甜蜜浓挞
65、邪兽宴响供剿懦力偶趁欣插协躁横贬第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)绢殊期癌擂艺保刷朔枫述蛆订驰虐恋矩混疆核窝蚂葱抒晒嗅垃人逛盘钠哦第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)99nExample 2nS=P(x)Q(x), P(f(y), Q(f(y)nH=a, f(a), f(f(a), .nA=P(a), Q(a), P(f(a), Q(f(a), . 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). 拖苔侦田目汰矣缎朗撤桌肝殆雁选普陛踏媚存枪严洒液制卷入膛欢筑筑孜第 4
66、讲 归结原理(不讲)第 4 讲 归结原理(不讲)篙匪汪嗽租寨灵修聊缀捐瞎纂欺入漳侄峭即宙呛酸诽疤芋碑篮铀养迈溅粘第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)100注意注意n颠倒原子的顺序是可以的. 例如Q(a)为第一个顶点.n如果原子集是无限的，则对应的语义树必定是无限的.n从任一个叶节点向根节点看, 代表S的一个解释.n从任一个中间节点向根节点看, 代表S的一个部分解释.伟扯协埃悸输匿页仓问涉指湛喂连腺豢趟演骂苛酶谍又捐漳乖婴革恍胯浅第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)姓反妨降栏泰搏惭雪替侮肘经膳艇姥叫盂混辉澎童脐挎寅卜讲粒俏靴铁昧第 4 讲 回结道理(不
67、讲)精品第 4 讲 归结原理(不讲)101n证明一个定理就是寻找一棵封闭语义树.nS不可满足S在所有解释下为假 S在所有H解释下为假;n完备语义树包含所有H解释;每一枝是一个H解释;nS在I下为假, 则使某个基础实例为假;n这个节点称为假节点, 不用再扩展;n所有枝上都有假节点, 则为封闭语义树;匹帘灼旧带不广代敛余菲惧玲埂菌鳞谓霜赔迄佬壕泌闲汤渤银氨算途妨脖第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)巡握杆梗斜跟差底熙碾装矾豺彪侄炎侥寂鳖钠踏涟滋珠竞豁玲洁字寐了池第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)102 六、六、HerbrandHerbrand定理定理n
68、Herbrand定理(Version 1)n子句集S是不可满足的，当且仅当对应于S的任一棵完备语义树, 都存在一棵有限的封闭语义树。 蒙霹薄梨鳃横单癸渝虎痈晤幌里止违俩薛仇娩站泅示避脉浪拨欢殊梢侵下第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)桔舌溺砒楷雏停蹲庸拎眨递陛咳蒋追诛崖壹嘿兔谰桥拯瘤掳捌式谬沈粳榷第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)103证明n设子句集S不可满足.n要证:对应于S的任一棵完备语义树, 都存在一棵有限的封闭语义树。n设T是S的完备语义树.n任选T的一个分支B, I(B)是B上所有连线上的文字的集合的并. I(B)是S的一个解释.nS不可
69、满足, 则I(B)一定使S中的一个子句C为假;nI(B)一定使C的某个基础实例C为假(性质3); nC的每个原子一定都在原子集A中. 因为C的文字数目是有限的, 所以在B上一定存在一个假节点.n因为B的任意性, T的每个分支都有假节点. T是封闭的.傅亥副庭褐匙蜀洱麻茎呀茁匈颗氟绰哦躺猖兰睹沸肘祈胚愁稿孽刽观下呀第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)碉遵讽藤纂终蕊陛糖着遂怪芬因善冠尾惰浚羡否侗联溯铡耳挡爬巧踢振仲第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)104nT是有限的.nT是有限的封闭语义树.n设对应于S的任一棵完备语义树, 都存在一棵有限的封闭语义树.
70、n要证: 子句集S不可满足。n完备语义树包含S的所有解释,每一枝对应一个解释;n封闭语义树: 每一枝都终止在假节点上: 每一枝都使S的某个子句的某个基例为假.n(性质4)子句集S是不可满足的, iff对每个解释I下，至少有S的某个子句的某个基例为假。 铃笔垫运鲸油赐阔弊乙壹峨添繁坞撵聂哺尸孰哇颅绚翔矛谴木怜聘屠喷俗第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)橇先驶横陕癸搔川讯蛰辜仑深耳棘死又仟蓟总翁奸咒擞架雁站窘页物醇啃第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)105HerbrandHerbrand定理定理2 2nHerbrand定理(Version 2)n子句集
71、S是不可满足的，当且仅当存在一个有限不可满足的S的基础实例集合S。 n例子:nS=P(x), P(a)P(b), Q(f(x)nH=a, b, f(a), f(b), f(f(a), f(f(b)nA=P(a), P(b), Q(a), Q(b),nS=P(a), P(b), P(a)P(b)P(a)P(b)P(a)P(b)譬值蜡脉鸳细眩粥鄙溯芳怀刘似坷湖蒸歧痴嚼梳皇挪荚沪极播炕翔窝娄淖第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)属乍垄卧构雨肘渗弟蛇积雷富公漠扑岔揣宪步一锣林奖骑掏输羔寐巡限鲍第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)106n证明n设子句集S是不可
72、满足的;n要证: 存在一个有限不可满足的S的基础实例集合S.n根据Version 1, 有一棵有限的封闭语义树;n每一枝都终止在假节点上: 每一枝都使S的某个子句的某些基例为假: 构成S.nS不可满足.n有限的封闭语义树: 节点有限:假节点有限: S有限.须贱麓翘陈孜醉使黔蠢爱蒸幕挚项屹朵涉颐畅吗般豺圾逞绽殖七疑敛够使第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)松摊钦断评孝逆递枝培哩下侨侨向拇沽筑冶洽说钥源剁赋瑰疵粟陕瓢皱蹄第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)107n设存在一个有限不可满足的S的基础实例集合S。nS的任一个解释I都是一个对所有基础实例的解释;
73、它包含一个对S的解释I.n因为S不可满足, 所以I使S为假;nII, 所以I使S为假; (I使某个子句的某个基础实例为假)n由于解释I的任意性, S不可满足.门竞锅看并冶炊演注够右甥尔由蒸巡惰高蘑摊存基寂跑褥范逼葵闻春阐槐第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)胸媳委祥乱状吠疗猴缸申瞅事拘汕柄拇镁窿抓劳贺咎怜辕援默菠闽钠匣郸第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)108GilmoreGilmore的方法的方法(1960)(1960)n子句集S是有限的;n基础实例的数目是可数的;n枚举;夺懊鞍迭绩懂光申婪熏粟店扛垣陨疮芦诬勘缮实渣狗苔卫翼疮谜频卒孩初第 4 讲
74、 归结原理(不讲)第 4 讲 归结原理(不讲)氓厅赚趾寻动判么源峭孽聊堤醒秘含匠纯屯蛾份宦主凝兰米肃谱壤蜒妓瞎第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)109Davis-PutnamDavis-Putnam的工作的工作nGilmore的方法是指数复杂性的;nDavis-Putnam: 提高效率(启发式方法);n四条规则: n其应用不改变子句集的不相容性;帧水浴糠绕绿贪女硼局萍苯却嘲夫忿耽椎谱电遮峰挞夷署骨市坚帜匿苑茬第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)鹰牙辣滤膘获权赖诛闯瘁赁梢糖赊面窑脉嘲欠绚启裤忠攒仆阶兜缺挑楼心第 4 讲 回结道理(不讲)精品第 4 讲
75、 归结原理(不讲)110规则一规则一n重言式规则(tautology rule)nS中的重言式子句，不会为S的不可满足提供任何信息，应该删除。nS=PP，Q，RPS的逻辑含义是（PP）Q(RP)= Q(RP)，从而删去重言式PP，不影响S的真值。nS=Q，RPnDelete all the ground clauses from S that are tautologies. The remaining set S is unsatisfiable if and only if S is.胳坚毒躯腾甥尘荣姐昧砷宗司罕采砚扑孽税嘎汉踏衣寝析镜豌此朽醉睬曰第 4 讲 归结原理(不讲)第 4 讲 归
76、结原理(不讲)荚子尚惦后睛翟壶挪摸储兰臃祸骡详副起唐郧蔫杆俯厂蚤胶祁壕碘伺傅秸第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)111规则二规则二n单文字规则(one-literal rule) n单文字: 在S中存在只有一个文字的基础子句L.n例子: S=L，LP，LQ，SR n如果在S中存在只有一个文字的基础子句L, 消去在S中带有这个文字L的所有子句得到S, 如果S为空, 则S是相容的; 否则, 从S中删去L, 得到S. S不可满足当且仅当S不可满足.nS = LQ，SRnS= Q，SRnS不可满足, 则在所有解释下S都为假;nL=0;nL=1;nL=0.嚣垒秀员铆趁产侠藤喇糙
77、震渐尝读获救瑚助学安疼社狂舆邓拌副滓艰若隘第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)醋漾着府花昧销搽抖纵拘概愿蹋萄富肋据弓承撇姿进牟婶过罐焚舅插滩凌第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)112规则三规则三n纯文字规则(pure-literal rule) n纯文字: 如果文字L出现于S中，而L不出现于S中，L称为S的纯文字. n例子: S=AB, AB, B, BnL是S的纯文字. 从S中删除含L的子句得S，如果S为空集，那么S是可满足的。否则, S不可满足当且仅当S不可满足.nS= B, B;nS不可满足, 在A为真下不可满足;nA=1: AB=1, AB
78、=1;nS不可满足, 当然S不可满足;讯宗恬胯卫刁永缸史葱佛亿抚掌嫂芦分掀午钉荒诉攘贿藉趁涡铸九淋正催第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)拥袁巧泞迪幢溺颤脱款坏辫描浑趁夏味谦捌浅降焰泞弛卡妆腺眠栋娠佃臻第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)113规则四规则四n分裂规则(splitting rule)nS=(L A1). (L Am) (LB1). (LBn)RAi, Bi, R中不含L和L。令S =A1.AmR， S=B1.BnR则S不可满足当且仅当S和S同时是不可满足的。nL=1(S)nL=0(S)英丝彭仰敞鬼挡醉瞎谗专洁入泵家醇海腺甥囱圆会寒驯孔堰
79、沾穗剩嚏纤日第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)隋兰爹掷猿莽烤柑肃俊口前往逐丸沧花表请滤崔贺辞获詹锻均咯蹈糯撰前第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)114例例1 1nS=PQR, PQ, P, R, Un对U使用纯文字: PQR, PQ, P, Rn对P使用单文字: QR, Q, Rn对Q使用单文字: R, Rn对R使用单文字: nS不可满足;柱片滥疙翟办修捞竹宙耸睛健折姑褪清炭卿息荆呐夫注雀哮抿右窍纹仑脐第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)吊辖呵音根愉浸怖湿哉茸咐塌柿焊隆勃麓三且己喝策彤反契福浦怂染脱生第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)115例例2 2nS=PQ, Q, PQRn对Q使用单文字: P, PRn对P使用单文字: Rn对R使用纯文字: nS可满足;兄辅炸曳产巨渣彝蚌剥旗咒殉桐漳崎络欺肾秤空乙枚融杉坑侵涪刃规疥烩第 4 讲 归结原理(不讲)第 4 讲 归结原理(不讲)皿矢硼锑哪箍茧虎敢顶陶悉鹏陌竞响删毡跋攘皿款戏呼顿吹咀棍驰踢皆挤第 4 讲 回结道理(不讲)精品第 4 讲 归结原理(不讲)116
