We use cookies to improve your experience with our site.

有穷正规逻辑程序的一致性性质

Consistency Property of Finite FC-Normal Logic Programs

  • 摘要: 知识表示和推理一直以来就是人工智能领域研究的核心内容之一。实践表明,人们现实生活中的常识知识几乎都是不完全和非单调的,新的知识的发现会导致不得不放弃一些原有的信念。逻辑程序作为一种重要的知识表示和推理方法,在逻辑程序中引入缺省否定后的稳定模型(stable model)(或者回答集)语义,使得基于稳定模型语义的逻辑程序设计成了一种新的程序设计范例:用逻辑程序来描述问题,问题的解就对应于逻辑程序的稳定模型。而目前各种稳定模型求解器的产生大大地推动了逻辑程序的应用,包括常识推理、智能规划、智能诊断、任务调度和语言学研究等理论方面以及向美国航天飞机设计的具体应用领域。一般说来,一个逻辑程序可能没有稳定模型,也可能有多个。而判定是否有稳定模型是NP-完全的,使得我们相信(至少目前如此),没有多项是时间可行的算法来求解其稳定模型。所以,具有多项式时间可计算其稳定模型的逻辑程序自然就是非常理想的一个子类。Marek等1999年提出的FC-正规逻辑程序就是其中一种,它具有稳定模型,而且可以多项式时间计算它的一个稳定模型。按照定义,为了判定一个程序的FC-正规性,得事先猜中一个一致性性质(非常多),然后验证它是不是程序FC-正规性的证据。但是就我们目前所知,还不知道有什么好的方法来确定那样的一个一致性性质。所以找到它(如果有的话)非常重要。受正规一致性性质思想的启发,在这篇文章中,我们研究发现,对任何逻辑程序P(包括无穷),都有那样的一个一致性质存在LCon(P),它仅仅依赖于程序P自身,使得P是FC-正规的当且仅当P是关于LCon(P)FC-正规的。并且,我们为有穷的逻辑程序构造了一个算法,来计算对那个LCon(P)的逼近。而且我们发现,这个LCon(P)并不能是P的所有稳定模型的幂集的集合;这从理论上否定了原来关于猜测一个一致性性质的一个可能误区:是不是那样的一致性性质就是所有稳定模型的幂集的集合?另外一个附加的结果是,我们也证明了尽管对FC-正规的逻辑程序,能多项式时间计算它的其中一个稳定模型,但是它的勇敢推理(是否一个给定的原子在它的稳定模型中)和谨慎推理(是否一个给定的原子在它的所有稳定模型中)仍然和一般逻辑程序的相应推理一样难。 文章的主要创新点就是为有穷的逻辑程序P,为了确定它的FC-正规性,而找到了一个最小的、必要的一致性性质LCon(P)和为它提出的一个算法。

     

    Abstract: Marek's forward-chaining construction is one of the importanttechniques for investigating the non-monotonic reasoning. Byintroduction of consistency property over a logic program, theyproposed a class of logic programs, FC-normal programs, each ofwhich has at least one stable model. However, it is not clear how tochoose one appropriate consistency property for deciding whether ornot a logic program is FC-normal. In this paper, we firstly discoverthat, for any finite logic program \it\Pi, there exists the leastconsistency property \it LCon(\it\Pi) over \it\Pi, which justdepends on \it\Pi itself, such that, \it\Pi is FC-normal if andonly if \it\Pi is FC-normal with respect to (w.r.t.) \itLCon(\it\Pi). Actually, in order to determine the FC-normality of alogic program, it is sufficient to check the monotonic closed sets in\it LCon(\it\Pi) for all non-monotonic rules, that is \itLFC(\it\Pi). Secondly, we present an algorithm for computing \itLFC(\it\Pi). Finally, we reveal that the brave reasoning task andcautious reasoning task for FC-normal logic programs are of the samedifficulty as that of normal logic programs.

     

/

返回文章
返回