paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Encoding many-valued logic in $\lambda$-calculus

在 λ-演算中编码多值逻辑
LMCS vol.Volume 17, Issue 22021匹配度 1/10 · 该论文属于 λ-演算与多值逻辑的形式语义研究,关注 Church 编码和无穷 λ-演算的理论构造,与用户核心方向(机器学习/Agent 程序的静态分析、LLM 与程序分析/形式化验证交叉、浮点程序分析、贝叶斯程序分析)几乎没有直接关联。引用 0 inbox
Fer-Jan de Vries
crossref: 2026-09-10

AI 速览

一句话:将 Church 布尔编码推广到无穷 λ-演算,用 ⊥ 标识不可解项,从而编码 McCarthy 三值逻辑并可细化到四、五值逻辑。

本文研究如何在 λ-演算中表示多值逻辑。已知 Church 编码可将布尔逻辑嵌入 λ-演算;作者将其推广到合适的无穷 λ-演算,引入新常量 ⊥ 并将所有不可解项等同,从而给出 McCarthy 三值逻辑的编码。该编码可进一步细化为四值和五值逻辑,并且同样的思路也适用于 Church 最初的 λI-演算。作为动机,文章讨论 Russell 悖论,并利用该编码在无穷设定下计算无穷闭命题的真值。这表明 λ-演算的编码技术能统一处理多值真值与无穷命题。

问题
如何将 Church 的布尔逻辑编码推广到多值逻辑,并在 λ-演算中为不可解项与无穷闭命题赋予真值。
方法
在 λ-演算中引入新常量 ⊥ 来标识所有不可解项,构造合适的无穷 λ-演算,并据此编码 McCarthy 三值逻辑以及四、五值逻辑;同类构造也适用于 λI-演算。
评估
文章以 Russell 悖论为动机,展示该编码可在无穷设定下计算无穷闭命题的真值,从而说明其表达能力和统一性。
原文摘要(Abstract)

We will extend the well-known Church encoding of Boolean logic into $\lambda$-calculus to an encoding of McCarthy's $3$-valued logic into a suitable infinitary extension of $\lambda$-calculus that identifies all unsolvables by $\bot$, where $\bot$ is a fresh constant. This encoding refines to $n$-valued logic for $n\in\{4,5\}$. Such encodings also exist for Church's original $\lambda\mathbf{I}$-calculus. By way of motivation we consider Russell's paradox, exploiting the fact that the same encoding allows us also to calculate truth values of infinite closed propositions in this infinitary setting.

链接与引用

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

BibTeX
@article{paperbot1303,
  title = {Encoding many-valued logic in $\lambda$-calculus},
  author = {Fer-Jan de Vries},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 2},
  year = {2021},
  doi = {10.46298/lmcs-17(2:25)2021}
}