资源描述:
《人工智能原理教案02章 归结推理方法2.6 herbrand定理》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、2.6Herbrand定理 Herbrand定理是归结原理的理论基础,归结原理的正确性是通过Herbrand定理来证明的。同时归结原理是Herbrand定理的具体实现,利用Herbrand定理对公式的证明是通过归结法来进行的。本节简单地描述了Herbrand定理的基本思想和相关预备知识,最后给出Herbrand定理的一般形式。 公式G永真:对于G的所有解释,G都为真。 公式G永假(矛盾):没有一个解释使G为真。2.6.1Herbrand定理概述 问题:一阶逻辑公式的永真性(永假性)的判定是否能在有限步内完成? 1936年图灵(Turing)和邱吉
2、(Church)互相独立地证明了: "没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真(或永假)。但是如果公式本身是永真(或永假)的,那么就能在有限步内判定它是永真(或永假)。对于非永真(或永假)的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。"2.6.1.1Herbrand定理思想 要证明一个公式是永假的,采用反证法的思想(归结原理),就是要寻找一个已给的公式是真的解释。然而,如果所给定的公式的确是永假的,就没有这样的解释存在,并且算法在有限步内停止。因为量词是任意的,所讨论的个体变量域D是任意的,所以解释的个数是无限、不可数
3、的,要找到所有的解释是不可能的。Herbrand定理的基本思想是简化讨论域,建立一个比较简单、特殊的域,使得只要在这个论域上(此域称为H域),原谓词公式仍是不可满足的,即保证不可满足的性质不变。 H域和D域关系的如下图表示:图2-1H域与D域关系示意图t2-1_swf.htm2.6.1.2H域 H域的定义: 设S为给定公式G的子句集,定义在论域D上, H0为S中的常量集。如果S中没有常量,H0由任意单个常量构成,如{a}, Hi+1=Hi∪{fm(t1,t2,…tn)},i=0,1,… 其中,fm为S中出现的所有函数符号的集合,t1,t2,…t
4、n为Hi-1的元素,i=1,2,… 则规定H∞称为G的H域(或说是相应的子句集S的H域)。Hi称为S的i水平常量集。不难看出,H域是直接依赖于G的,而且最多只有可数个元素。 例题2-4 设子句集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))
5、, 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
6、(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……… 解毕 注意:一个函数中含有多个变量时,每个变量都要做到全部的组合。原子集A: 为研究子句集S中的不可满足性,需要讨论H域上S中各谓词的真值。这里原子集A为公式中出现的谓词套上H域的元素组成的集合。A={所有形如P(t1,t2,…tn)的元素}。这里,P(x1,…,xn)为出现于S中的任一谓词符号,而t1,t2,…tn为S的H域中的任意元素。即把H域中的东西填到S的谓词里去。 上
7、例题的原子集为: A={P(a),Q(a,a),R(a),P(b),Q(b,a),Q(b,b),Q(b,a),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)),……) 一旦原子集内真值确定好(规定好),则S在H上的真值可确定。不可数问题转化成为了可数问题。S中的谓词是有限的,H是可数的,因此,A也是可数的。 论域D上公式G或子句集S的H域的建立,仅依赖于S中出现的几个函数符号,以及S中出现的D的几个常量符号,或D中的一个常量符号,这些都是可数的H域比一般论
8、域D简单的原因。2.6.1.3H解释 解释I:谓词公式G在论域D