人工智能第三章.ppt

人工智能第三章.ppt 本节课主要讲解了人工智能中的一阶逻辑公式的永真性判定问题，引入了Herbrand定理，并详细剖析了该定理的思想、基本方法、几个基本概念、解释和语义树等方面的内容。 一阶逻辑公式的永真性判定问题是人工智能中一个重要的研究方向。1936年，图灵和邱吉独立地证明了没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是，如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。 Herbrand定理是解决这个问题的一个重要工具。Herbrand定理的思想是寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。 Herbrand定理的基本方法是简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是不可满足的。这个域称为H域。H域的建立是通过将子句集中出现的常量和函数变量组合起来实现的。 在Herbrand定理中，还有几个基本概念需要掌握。例如，f（tn）是子句集S中的所有函数变量，t1, t2, …tn为S的H域的元素。原子集A是谓词套上H域的元素组成的集合。Herbrand定理还引入了H解释的概念，即子句集S在H域上的解释。 Herbrand定理还提供了三个定理来保证归结法的正确性。第一个定理说明，设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I = T，必有 S|I* = T。第二个定理说明，子句集S是不可满足的，当且仅当所有的S的H解释下为假。第三个定理说明，子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。 Herbrand定理还涉及到语义树的概念。语义树是一棵二叉树，原子集中所有元素逐层添加。将元素的是与非分别标记在两侧的分枝上。语义树的特点是H是可数集，S的语义树是无限树。 Herbrand定理是解决一阶逻辑公式的永真性判定问题的重要工具，它提供了一个从理论上解决问题的方法，使得问题变得更加 tractable。但是，Herbrand定理也存在一些缺陷，例如H域的建立需要大量的计算资源，语义树的构建也需要大量的计算资源。