paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Combinatorial Proofs and Decomposition Theorems for First-order Logic

一阶逻辑的组合证明与分解定理
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 2/10 · 该论文属于纯证明论/一阶逻辑的组合证明与分解定理,与用户关注的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析均无直接关联;仅在形式化验证的逻辑基础层面有非常间接的联系。引用 4 inbox
Dominic J. D. Hughes, Lutz Strasburger, Jui-Hsuan Wu
crossref: 2026-09-12

AI 速览

一句话:揭示一阶逻辑组合证明与句法证明的关系,通过深度推理分解定理给出新正规形式及可靠/完备/完全完备性结果。

本文研究一阶逻辑(不含等词)中组合证明与句法证明之间的深层联系。句法证明由推理规则形式化,组合证明则是无语法、独立于推理规则集合的证明呈现。作者通过深度推理分解定理将两者联系起来,并为句法证明建立了一种新的正规形式。基于该定理,作者给出组合证明可靠性与完备性的简洁证明,表明其与一阶逻辑有效性一致;同时证明完全完备性:每个组合证明都是某个句法证明的像,说明组合证明未超出句法证明的表达范围。该工作为组合证明提供了句法基础,并深化了对一阶逻辑证明结构与正规形式的理解。

问题
如何刻画一阶逻辑中独立于推理规则、无语法呈现的组合证明,并建立其与标准句法证明之间的精确对应?
方法
通过深度推理分解定理,将句法证明化为一种新的正规形式,并在组合证明与句法证明之间建立联系。
评估
以理论证明方式评估:给出组合证明的可靠性与完备性证明,并证明完全完备性——每个组合证明都是某个句法证明的像。
原文摘要(Abstract)

We uncover a close relationship between combinatorial and syntactic proofs for first-order logic (without equality). Whereas syntactic proofs are formalized in a deductive proof system based on inference rules, a combinatorial proof is a syntax-free presentation of a proof that is independent from any set of inference rules. We show that the two proof representations are related via a deep inference decomposition theorem that establishes a new kind of normal form for syntactic proofs. This yields (a) a simple proof of soundness and completeness for first-order combinatorial proofs, and (b) a full completeness theorem: every combinatorial proof is the image of a syntactic proof.

链接与引用

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

BibTeX
@inproceedings{paperbot6209,
  title = {Combinatorial Proofs and Decomposition Theorems for First-order Logic},
  author = {Dominic J. D. Hughes and Lutz Strasburger and Jui-Hsuan Wu},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470579}
}