二阶逻辑的表达能力与计算复杂性

项目名称： 二阶逻辑的表达能力与计算复杂性

项目编号： No.60970040

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 赵希顺

作者单位： 中山大学

项目金额： 30万元

中文摘要： Gabbay、Ohlbach等人认为表达能力是逻辑系统的最重要的性质之一。表达能力的研究和比较可以使我们对各种逻辑系统有更深刻地认识，为在实际应用选取"最好"的表示系统提供帮助。逻辑系统之间的表达能力关系与计算复杂性理论中的重要猜想有着密不可分的联系，因此，表达能力的研究也具有重要的理论意义。然而表达能力研究被认为是具有挑战性的课题。本项目一方面以申请者提出的模型等价归约为工具研究二阶命题逻辑(即QBF)的表达能力及其与计算复杂性的关系。另一方面，提出Henkin二阶量词，推广比例量词，并研究带有这些二阶量词谓词逻辑，提出有穷模型等价归约，进而研究各种谓词逻辑的表达能力。本项目的就是进一步探讨逻辑系统表达能力的强弱与计复杂性理论中的重要猜想之间的联系。

中文关键词： 量化布尔公式；量化布尔电路；二阶HORN逻辑；表达能力；计算复杂性

英文摘要：

英文关键词： Quantified Boolean Formula；Quantified Boolean Circuit；Second-Order HORN Logic；Expressive Power；Computational Complexity