- 1、本文档共124页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第3章 谓词逻辑与归结原理 命题逻辑 谓词逻辑基础 谓词逻辑归结原理 Herbrand定理 Herbrand定理 问题: 一阶逻辑公式的永真性(永假性)的判定是否能在有限步内完成? Herbrand定理 1936年图灵(Turing)和邱吉(Church)互相独立地证明了: “没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真(或永假)。但是如果公式本身是永真(或永假)的,那么就能在有限步内判定它是永真(或永假)。对于非永真(或永假)的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” Herbrand定理 Herbrand的思想 定义: 公式G永真:对于G的所有解释,G都为真。 思想: 寻找一个已给的公式是真的解释。然而,如果所给定的公式的确是永假的,就没有这样的解释存在,并且算法在有限步内停止。 Herbrand定理(H域) 基本方法: 因为量词是任意的,所讨论的个体变量域D是任意的,所以解释的个数是无限、不可数的 。 简化讨论域。建立一个比较简单、特殊的域,使得只要在这个论域上,该公式是不可满足的。 此域称为H域。 D域 H域 H域与D域关系示意图 H域例题 例3.19 设子句集S={P(x),Q(y)∨R(z)},求H域。 H0={a} H1=H0={a} …… H∞ = H1∪H2∪H3………={a} 例3.20 设子句集S={P(a),Q(x)∨R(f(x))},求H域。 H0={a} H1=H0={a,f(a)} H2={a,f(a),f(f(a))} …… H∞ = H1∪H2∪H3………={a,f(a),f(f(a))} 例3.21 设子句集S={P(a),Q(b)∨R(f(x))},求H域。 此题中有两个常量a,b H0={a,b} H1=H0={a,b,f(a),f(b)} H2={a,b,f(a),f(b),f(f(a)),f(f(b))} …… H∞ = H1∪H2∪H3………={a,b,f(a),f(b),f(f(a)),f(f(b)),…} H域例题 H域例题 例3.22 设子句集S = { P(x), Q(y,f(z,b)),R(a)},求H域 解: H0 = {a, b}为子句集中出现的常量 H1 = {a, b, f(a,b), f(a,a), f(b,a), f(b,b)} H2 = { a, b, f(a,b), f(a,a), f(b,a), f(b,b), f(a,f(a,b)), f(a,f(a,a)), f(a, f(b,a)), f(a, f(b,b)), f(b,f(a,b)), f(b,f(a,a)), f(b, f(b,a)), f(b,f(b,b)), f(f(a,b),f(a,b)), f(f(a,b),f(a,a)), f(f(a,b), f(b,a)), f(f(a,b), f(b,b)), f(f(a,a),f(a,b)), f(f(a,a),f(a,a)), f(f(a,a), f(b,a)), f(f(a,a), f(b,b)), f(f(b,a),f(a,b)), f(f(b,a),f(a,a)), f(f(b,a), f(b,a)), f(f(b,a), f(b,b)), f(f(b,b),f(a,b)), f(f(b,b),f(a,a)), f(f(b,b), f(b,a)), f(f(b,b), f(b,b))} ……… H∞ = H1∪H2∪H3……… H域例题 例3.23 设子句集S={P(c),Q(f(x),R(g(x)))},求H域。 此题中有常量c,函数f(x),g(x) H0={c} H1=H0={c,f(c),g(c)} H2={c,f(c),g(c),f(f(c)),f(g(c)),g(f(c)),g(g(c))} …… H∞ = H1∪H2∪H3………={c,f(c),g(c),f(f(c)),f(g(c)), g(f(c)),g(g(c))},…} Herbrand定理(H域) 原子集A:公式中的谓词取H域中的元素组成的集合。如 A = {所有形如 P(t1, t2, …tn)的元素} 即把H中的东西填到S的谓词里去。 S中的谓词是有限的、可数的,H域中的元素是可数的,因此,A中的元素也是可数的。 原子集例题 上例题的原子集为: A = { P(a), Q(a, a), R(a), P(b), Q(b, a), Q(b, b), Q(a, b), R(b), P( f(a,b)), Q(f(a, b), f(a, b)), R(f(a, b), P(f(a,a)), P(f(b,a)),
您可能关注的文档
- 中国戏曲文化课件.ppt
- 中国电影史(全套课件).ppt
- 压力性损伤预防及护理.ppt
- 色阶及其应用.ppt
- 人教版小学一年级上册数学全套课件-.ppt
- 人教版九年级英语全Unit4 I used to be afraid of the dark Section A 3a-4c 教学课件.ppt
- 染色体变异(公开课)2.ppt
- 模块化设计精选-课件.ppt
- 六年级上英语课件-Unit-3-My-weekend-plan第6课时--人教PEP.ppt
- 卷烟配方与评吸技术(2005工艺班).ppt
- 英语人教PEP版八年级(上册)Unit4+writing+写作.pptx
- 人美版美术四年级(上册)8 笔的世界 课件 (1).pptx
- 人美版美术七年级(上册)龙的制作.pptx
- 英语人教PEP版六年级(上册)Unit 2 第一课时.pptx
- 数学苏教版三年级(上册)3.3 长方形和正方形周长的计算 苏教版(共12张PPT).pptx
- 音乐人教版八年级(上册)青春舞曲 课件2.pptx
- 音乐人教版四年级(上册) 第一单元 音乐知识 附点四分音符|人教版.pptx
- 英语人教PEP版四年级(上册)Unit 6 Part B let's learn 1.pptx
- 道德与法治人教版二年级(上册)课件-3.11大家排好队部编版(共18张PPT).pptx
- 人美版美术七年级(上册)《黄山天下奇》课件1.pptx
最近下载
- 耳鼻喉科术后感染预防PDCA循环案例.pptx VIP
- 干部管理-华为学习材料.pdf VIP
- 华为干部管理七步曲.pdf VIP
- 外研版小学五年级英语上册《Module 5 Unit 1 There are only nineteen crayons 》教学教案.doc VIP
- 2018年春二年级下册道法教案.pdf VIP
- 高中体育新课标程准考试试题.doc VIP
- 甲亢甲减的相关知识与护理PPT课件.pptx VIP
- 新人教pep三年级上册Unit2 Different families PartA talk &learn 课件.ppt
- 九年级化学培优辅差工作总结 .pdf VIP
- 第4课《古代诗歌四首》核心素养教学设计-七年级语文上册(统编版).docx
文档评论(0)