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

摘要：

基于回答集（也称稳定模型）语义的带函数析取逻辑程序是一种重要的知识表示和推理方法。由于判定一个析取逻辑程序是否有回答集是困难的（Σ2完全的），目前还没有有效的方法来计算带函数析取逻辑程序的回答集，主要原因之一是检查一个集合是否是回答集是coNP完全的。提出了带函数析取逻辑程序无基集（unfounded sets）的概念，发现了空无基集（unfounded-free sets）与稳定模型之间的一一对应关系，在此基础上，证明了一个逻辑程序的模型是该程序的稳定模型当且仅当它们对应的一个命题公式是不可满足的，从而在理论上为计算带函数析取逻辑程序的回答集提供了一种有效的途径。

关键词：析取逻辑程序、回答集、函数、无基集

分类号：TP18(自动化基础理论)

资助基金：The National Natural Science Foundation of China under Grant No.60963009

在线出版日期：2015-06-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：747-755