CAJ | 학술논문

基于回答集（也称稳定模型）语义的带函数析取逻辑程序是一种重要的知识表示和推理方法。由于判定一个析取逻辑程序是否有回答集是困难的（Σ2完全的），目前还没有有效的方法来计算带函数析取逻辑程序的回答集，主要原因之一是检查一个集合是否是回答集是coNP完全的。提出了带函数析取逻辑程序无基集（unfounded sets）的概念，发现了空无基集（unfounded-free sets）与稳定模型之间的一一对应关系，在此基础上，证明了一个逻辑程序的模型是该程序的稳定模型当且仅当它们对应的一个命题公式是不可满足的，从而在理论上为计算带函数析取逻辑程序的回答集提供了一种有效的途径。
기우회답집（야칭은정모형）어의적대함수석취라집정서시일충중요적지식표시화추리방법。유우판정일개석취라집정서시부유회답집시곤난적（Σ2완전적），목전환몰유유효적방법래계산대함수석취라집정서적회답집，주요원인지일시검사일개집합시부시회답집시coNP완전적。제출료대함수석취라집정서무기집（unfounded sets）적개념，발현료공무기집（unfounded-free sets）여은정모형지간적일일대응관계，재차기출상，증명료일개라집정서적모형시해정서적은정모형당차부당타문대응적일개명제공식시불가만족적，종이재이론상위계산대함수석취라집정서적회답집제공료일충유효적도경。
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.