带函数析取逻辑程序的无基集及其应用

摘要

Under answer sets (stable models) semantics, disjunctive logic programming with functions provides an important knowledge representation and reasoning method. As it is difficult (Σ2-complete) to determine whether the disjunctive logic programs have an answer set, checking if a set of atoms is an answer set is coNP-complete, no effective method for computing answer sets of disjunctive logic programming with functions has been found. This paper puts forward a notion of unfounded sets for the disjunctive logic programming with functions, and finds a one-to-one relationship between the unfounded-free sets and answer sets. Accordingly this paper discovers that a model is an answer set of a logic program whenever a corresponding propositional formula is unsatisfiable. Thus, it theoreti-cally provides an efficient approach to compute answer sets of disjunctive logic programs with functions.%基于回答集（也称稳定模型）语义的带函数析取逻辑程序是一种重要的知识表示和推理方法。由于判定一个析取逻辑程序是否有回答集是困难的（Σ2完全的），目前还没有有效的方法来计算带函数析取逻辑程序的回答集，主要原因之一是检查一个集合是否是回答集是coNP完全的。提出了带函数析取逻辑程序无基集（unfounded sets）的概念，发现了空无基集（unfounded-free sets）与稳定模型之间的一一对应关系，在此基础上，证明了一个逻辑程序的模型是该程序的稳定模型当且仅当它们对应的一个命题公式是不可满足的，从而在理论上为计算带函数析取逻辑程序的回答集提供了一种有效的途径。