arXiv:2608.18445cs.LOcs.AI2026-08

首次形式化验证罗马诺夫三元组逻辑,构建可信赖的3-CNF求解过滤器。

Formal Verification of Romanov's Triplet Logic: A Verified Filter for Sliding-window 3-CNF with Application to Structured Formulas

  • 用Rocq证明助手形式化三元组逻辑核心,含转换、清除与交集算法
  • 证明滑动窗口片段多项式时间复杂度,且给出满足性判定精确边界
  • 产出可运行的验证版工具,适合形式化验证与逻辑求解研究者

我们在Rocq证明助手中首次实现了罗马诺夫三元组逻辑(TLS)的机械化形式化。TLS是一种基于三元组结构的组合框架,源于布尔可满足性问题,包含一种称为简单顶点交集(SVI)的过滤器。我们形式化了TLS的核心内容,包括从3-CNF的转换、清除过程及SVI算法。针对良构滑动窗口片段,我们证明了各过滤阶段的明确多项式时间界,并验证了转换与交集操作的正确性。主要贡献是精确的正确性边界:对一般公式,SVI非空是满足性的必要但不充分条件;对对齐结构,我们证明了完全双向蕴含,并扩展至结构系统。我们还形式化了分组窗口转换,提供了其不完备性的正式反例。引入VFR(验证的罗马诺夫三元组逻辑过滤器),一个提取的OCaml原型,实现滑动窗口片段的验证决策过程和通用3-CNF的可靠过滤器,配有Python运行时和Docker打包。基准测试验证了预期行为,完整工具链作为精心整理的Zenodo资源发布。Rocq开发包含超过23,000行代码,424个已证明引理,无未证明假设。

原文摘要 · Abstract (English)

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a combinatorial framework originally motivated by Boolean satisfiability, based on triplet structures and a filter that we call Simple Vertex Intersection (SVI). We formalise the core of TLS, including its translation from 3-CNF, the clearing procedure, and the SVI algorithm. For the well-formed sliding-window fragment, we prove explicit polynomial-time bounds for the filter stages and verify the translation and intersection operations. Our main contribution is a precise correctness boundary: for general formulas, SVI non-emptiness is necessary but not sufficient for satisfiability; for aligned structures, we prove a full bi-implication, extended to systems of structures. We also formalise the grouped-window translation and provide a formal counterexample to its completeness. We introduce VFR (Verified Filter for Romanov's triplet logic), an extracted OCaml prototype that implements a verified decision procedure for the sliding-window fragment and a sound filter for general 3-CNF, with a Python runtime and Docker packaging. Benchmarks corroborate the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises over 23,000 lines of code, with 424 proved lemmas and no unproved assumptions.

形式化验证逻辑求解三元组逻辑可满足性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。