人工智能第三章.ppt
《人工智能第三章.ppt》由会员分享,可在线阅读,更多相关《人工智能第三章.ppt(20页珍藏版)》请在三一办公上搜索。
1、3.4 Herbrand定理,问题:一阶逻辑公式的永真性(永假性)的判定是否能在有限步内完成?,1936年图灵(Turing)和邱吉(Church)互相独立地证明了:,“没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真(或永假)。但是如果公式本身是永真(或永假)的,那么就能在有限步内判定它是永真(或永假)。对于非永真(或永假)的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。”,3.4 Herbrand定理,Herbrand的思想定义:公式G永真:对于G的所有解释,G都为真。思想:寻找一个已给的公式是真的解释。然而,如果所给定的公式的确是永假的,就没有这样的解释存在,并且
2、算法在有限步内停止。,3.4 Herbrand定理,基本方法:因为量词是任意的,所讨论的个体变量域D是任意的,所以解释的个数是无限、不可数的。简化讨论域。建立一个比较简单、特殊的域,使得只要在这个论域上,该公式是不可满足的。此域称为H域。,3.4 Herbrand定理,H域例题,设子句集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)
3、,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)
4、H=H1H2H3,3.4 Herbrand定理,几个基本概念f(tn):f为子句集S中的所有函数变量。t1,t2,tn为S的H域的元素。通过它们来讨论永真性。原子集A:谓词套上H域的元素组成的集合。如A=所有形如 P(t1,t2,tn)的元素即把H中的东西填到S的谓词里去。S中的谓词是有限的,H是可数的,因此,A也是可数的。,3.4 Herbrand定理,上例题的原子集为: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),P(f(b,b),)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 第三

链接地址:https://www.31ppt.com/p-5194349.html