摘要: 1．本文的创新点析取逻辑程序(DLP)是知识表示和推理的重要工具之一，在人工智能领域有着广泛的应用。根据需要，析取逻辑程序的各种语义相继被提出来，其中最著名的有：稳定模型语义（stable model semantics）、极小模型语义(minimal model semantics)、完满模型语义(perfect model semantics)、以及部分稳定模型语义（partial stable model semantics）。一般地，人们都认为这些语义都是互不相同的。之所以如此，是因为人们往往以等价性为标准来比较不同逻辑系统的表达能力的。具体地，说一个逻辑系统C1的表达能力比另一个系统C2的表达能力弱如果C1中的每个公式都可转换成C2种的一个公式使得二者根据各自的语义有相同的模型。然而，如果以等价性为标准，在稳定模型语义（或极小模型语义，或完满模型语义）下，DLP与经典的命题逻辑具有同样的表达能力。这似乎也不符合人们的直觉，因为DLP被认为可以处理不完全信息下的推理，而命题逻辑则不然。为此作者曾提出以多项式时间模型等价归约来比较逻辑系统间的表达能力。更具体地，说C1可以多项式时间模型等价归约到C2是指C1中的每个公式T1都可在多项式时间内转换为C2中的一个公式T2使得T1和T2模型等价，即二者模型之间有一个多项时间可计算的一一对应。本文就是以模型等价归约为标准对上面提及的DLP的语义进行了比较。本文证明了，DLP的稳定模型语义、完满模型语义和部分稳定模型语义实际上具有相同的表达能力。也就是说，以稳定模型语义和完满模型语义为例，任何一个析取逻辑程序P1都可在多项式间内转换为另一个析取逻辑程序P2使得P1的稳定模型与P2的完满模型一一对应，且该一一对应在多项式时间内可计算。且反之亦然。然而，如果计算复杂性理论的多项式分层不坍塌，极小模型语义则具有较弱的表达能力。2．实现方法（包括实验环境，实验数据）本文分别比较以上各种语义与仅带全称量词的量化布尔公式("PF*)的表达能力。除了极小模型语义，它们都与"PF*同样的表达能力。本文首先分析了已有的相关的归约，指出了哪些是模型等价归约，并用于我们的证明。同时，本文还提出了两个新的模型等价规约，即，完满模型语义和部分稳定语义都可模型等价归约到"PF*。3．结论本文证明了，在模型等价归约下，DLP的稳定模型语义、完满模型语义和部分稳定模型语义具有同样的表达能力，而极小模型语义则具有较弱的表达能力。4．本文的主要贡献本文根据作者曾提出的模型等价归约，对DLP的各种语义以及量化布尔公式进行了系统比较。本文的工作不仅是我们对DLP的各种语义的表达能力有了深刻地认识，而且还具有应用价值。例如，当我们需要计算完满模型时， 我们可以先把它转换为另外一个逻辑程序，然后利用已有的Solver（如DLP）计算稳定模型，而后再计算相应的完满稳定模型。