计算中的逻辑

计算中的逻辑运用数理逻辑工具来描述、规范和推理计算系统，并通过定义问题所需的逻辑资源来表征复杂性类别。

Definition

计算中的逻辑是研究形式逻辑系统作为指定和验证计算行为的语言，以及作为衡量计算复杂性的标尺，将计算和逻辑可定义性视为同一现象的两个方面。

Scope

该领域涵盖了用于指定程序和反应系统行为的时态逻辑和模态逻辑，将复杂性类别与逻辑可定义性等同起来的描述复杂性，以及哥德尔不完备定理的计算解读及其与不可判定性的关系，这都借鉴了逻辑与计算机科学之间长期的相互作用。

Sub-topics

• 描述复杂性
• 哥德尔不完备性与计算
• 计算中的时态逻辑与模态逻辑

Core questions

• 逻辑公式如何指定程序和系统的正确行为？
• 复杂性类别能否纯粹通过逻辑表达能力来表征？
• 哥德尔不完备定理的计算内容是什么？
• 逻辑和计算如何相互阐明彼此的局限性？

Key theories

描述复杂性

主要的复杂性类别与特定逻辑中可定义的问题类别相吻合，因此计算资源可以通过逻辑表达能力而不是机器时间或空间来衡量。

程序行为逻辑

时态逻辑、模态逻辑和动态逻辑为指定安全性（safety）和活性（liveness）等属性提供了精确的语言，构成了硬件和软件形式验证的基础。

Clinical relevance

系统行为的逻辑规范是形式验证和模型检查的基础，用于认证安全关键型硬件和软件，而描述复杂性则提供了独立于机器的可处理性视角，为数据库查询语言和复杂性理论的基础提供了信息。

History

逻辑与计算之间的联系从20世纪30年代的哥德尔和图灵一直延续到计算机科学的兴起。法金（Fagin）1974年的定理开启了描述复杂性，普努埃利（Pnueli）于1977年引入了用于程序的时态逻辑，模型检查在20世纪80年代发展成为一项主要的验证技术，深化了该领域的逻辑基础。

Key figures

• Kurt Gödel
• Amir Pnueli
• Neil Immerman
• Ronald Fagin

Seminal works

• immerman1999
• harel2000

Frequently asked questions

除了纯数学之外，逻辑在计算机科学中是如何应用的？

逻辑提供了精确说明系统应做什么的语言以及证明其确实如此的方法。时态逻辑指定持续行为，类型系统和程序逻辑认证代码，描述复杂性则从可定义性角度重新审视效率，使逻辑既是实用的工程工具，也是基础理论。

描述复杂性揭示了什么？

它表明复杂性类别可以在不提及机器或时间限制的情况下定义，纯粹通过哪种逻辑可以表达其问题。例如，在有序结构上可在多项式时间内解决的问题，恰好是某种一阶逻辑扩展中可定义的问题，这便将计算与逻辑表达能力联系起来。