paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On Natural Deduction for Herbrand Constructive Logics I: Curry-Howard Correspondence for Dummett's Logic LC

论 Herbrand 构造逻辑的自然演绎 I:Dummett 逻辑 LC 的 Curry-Howard 对应
LMCS vol.Volume 12, Issue 32017匹配度 2/10 · 该论文属于证明论、Curry-Howard 对应与类型系统方向,与形式化验证仅有间接背景关联;但它不涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,也不讨论工业落地或 benchmark,因此与用户当前研究画像匹配度很低。引用 9 inbox
Federico Aschieri
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:为 Dummett 逻辑 LC 建立一阶与二阶自然演绎及 Curry-Howard 对应,并证明其类型化演算可规范化并导出 Herbrand 析取。

Dummett 逻辑 LC 是在直觉主义逻辑上加入 Dummett 公理(任意两命题必有其一蕴涵另一)而得到的逻辑。本文为一阶和二阶 Dummett 逻辑给出自然演绎系统与 Curry-Howard 对应。作者在 lambda 演算中增加一个算子:编程上表示并行计算及通信机制,逻辑上对应 Dummett 公理。文章证明所得类型化演算具有规范化性质,并进一步说明存在量化公式的证明项可归约为由个体项列表构成的 Herbrand 析取。该工作为 Herbrand 构造逻辑系列研究奠定基础。

问题
如何为 Dummett 逻辑 LC 的一阶与二阶片段建立自然演绎,并给出其 Curry-Howard 对应?
方法
扩展 lambda 演算,加入对应 Dummett 公理的算子(表示并行计算与通信),定义类型化演算并证明规范化。
评估
通过证明类型化演算规范化,并分析存在量化公式的证明项归约得到 Herbrand 析取来验证系统。
原文摘要(Abstract)

Dummett's logic LC is intuitionistic logic extended with Dummett's axiom: for every two statements the first implies the second or the second implies the first. We present a natural deduction and a Curry-Howard correspondence for first-order and second-order Dummett's logic. We add to the lambda calculus an operator which represents, from the viewpoint of programming, a mechanism for representing parallel computations and communication between them, and from the viewpoint of logic, Dummett's axiom. We prove that our typed calculus is normalizing and show that proof terms for existentially quantified formulas reduce to a list of individual terms forming an Herbrand disjunction.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@article{Aschieri16,
  title = {On Natural Deduction for Herbrand Constructive Logics I: Curry-Howard Correspondence for Dummett's Logic LC},
  author = {Federico Aschieri},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 12, Issue 3},
  year = {2017},
  doi = {10.2168/lmcs-12(3:13)2016}
}