二阶扩展逻辑的复杂性与表达能力(英文)  

The Complexity and Expressive Power of Second-Order Extended Logic

作　　者：冯世光[1] 赵希顺[1] 

机构地区：[1]中山大学逻辑与认知研究所

出　　处：《逻辑学研究》2012年第1期11-34,共24页Studies in Logic

基　　金：supported by the NSFC project under grant No.60970040;the MOE project under grant No.11JJD720020

摘　　要：本文研究了在所有有穷结构上SO-HORN*,SO-HORNr和SO-HORN*r的表达能力。我们证明了SO-HORNr,SO-HORN*r和FO(LFP)的表达能力是一致的,SO-HORN*是SO-HORNr的一个严格子逻辑。为了证明这一结果,我们提出了DATALOG*程序,DATALOGr程序以及它们的分层版本S-DATALOG*程序和S-DATALOGr程序。我们证明了在所有有穷结构上DATALOGr和S-DATALOGr是等价的,并且DATALOG*是DATALOGr的一个严格子逻辑。最后我们还用两种方法证明了SO-HORN的一个扩展版本SO-EHORNr逻辑可以在所有有穷结构上刻画co-NP。We study the expressive powers of SO-HORN＊, SO-HORNτ and SO-HORN＊r on all finite structures. We show that SO-HORNτ, SO-HORN＊r, FO（LFP） coincide with each other and SO-HORN＊ is proper sublogic of SO-HORNr. To prove this result, we introduce the notions of DATALOG＊ program, DATALOGτ program and their stratified versions, S- DATALOG＊ program and S-DATALOGτ program. It is shown that, on all structures, DATALOGτ and S-DATALOGτ are equivalent and DATALOG＊ is a proper sublogic of DATALOGτ. SO-HORN＊ and SO-HORNτ can be treated as the negations of DATALOG＊ and DATALOGr, respectively. We also show that SO-EHORNτ logic which is an extended version of SO-HORN captures co-NP on all finite structures.

关 键 词：表达能力 逻辑 复杂性 SO 结构 证明 程序 版本 

分 类 号：B81[哲学宗教—逻辑学]