人工智能 第三章3

1、3.4 Herbrand定理 问题：一阶逻辑公式的永真性（永假性）的判定是否能在有限步内完成？ 1936年图灵(Turing)和邱吉(Church)互相独立地证明了： “没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” 3.4 Herbrand定理 Herbrand的思想定义：公式G永真：对于G的所有解释，G都为真。思想：寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且

2、算法在有限步内停止。 3.4 Herbrand定理 基本方法： 因为量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的 。 简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是不可满足的。 此域称为H域。 ),.,(11niittfHH3.4 Herbrand定理D域H域H域与D域关系示意图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

3、)，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

4、(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 = H1H2H33.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),

5、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),) 一旦原子集内真值确定好（规定好），则S在H上的真值可确定。成为可数问题。3.4 Herbrand定理 解释I：谓词公式G在论域D上任何一组真值的指定称为一个解释。 H解释：子句集S在的H域上的解释称为H解释。 问题： 对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决 。3.4 Herbrand定理 如下三个定理保证了归结法的正确性： 定理定理1：设I

6、是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I = T，必有 S|I* = T。 定理定理2 2：子句集S是不可满足的，当且仅当所有的S的H解释下为假。 定理定理3 3：子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。 3.4 Herbrand定理 基例S中某子句中所有变元符号均以S的H域中的元素代入时，所得的基子句C称为C的一个基例。 若一个子句为假，则此解释为假。 一般来说，D是无穷不可列的，因此，子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。 解决问题的方法：语义树3.4 Herbrand

7、定理 构成方法原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上（可不完全画完） 。 特点一般情况H是可数集，S的语义树是无限树。 3.4 Herbrand定理N0P(a)N12Q(a)P(f(a)N24N31N38无限语义树N11P(a)Q(a)Q(a)Q(a)P(f(a)N21SP(x)Q(x)，P(f(y)，Q(f(y) 3.4 Herbrand定理 意义S H A 语义树可以理解语义树为H域的图形解释。 目的：把每个解释都摊开。语义树中包含原子集的全部元素。因此，语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。

8、如果每个基例都为假，则可认为是不可满足的。3.4 Herbrand定理 几个概念 失败结点： 当（由上）延伸到点N时，I(N)已表明了S的某子句的某基例假。但N以前尚不能判断这事实。就称N为失败结点。 封闭语义树：如果S的完全语义树的每个分枝上都有一个失败结点，就称它是一棵封闭语义树。3.4 Herbrand定理N0P(a)N1,2Q(a)P(f(a)N2,4N3,1N3,8N1,1N4,2N4,1N2,1N3,2N2,2N3,6N4,9N4,10N4,13N4,14封闭语义树Q(f(a)SP(x)Q(x)，P(f(y)，Q(f(y) 3.4 Herbrand定理Herbrand定理：1. 子句集S是不可满足的，当且仅当对应于S的完全语义数是棵有限封闭树。 2. 子句集S是不可满足的，当且仅当存在不可满足的S的有限基例集。 3.4 Herbrand定理 定理的意义 Herbrand定理已将证明问题转化成了命题逻辑问题。 由此定理保证，可以放心的用机器来实现自动推理了。（归结原理） 注意 Herbrand定理给出了一阶逻辑的半可判定算法，即仅当被证明定理是成立时，使用该算法可以在有限步得证。而当被证定理并不成立时，使用该算法得不出任何结论。但是 3.4 Herbrand定理 仍存在的问题问题：基例集序列元素的数目随子句基的元素数目成指数地