用代数方法重新表达命题逻辑，提升表示灵活性与计算效率。
State Algebra for Propositional Logic
- 构建三层代数表示：集合、坐标与行分解，结合语义与代数计算优势。
- 通过固定变量顺序可获得唯一标准形式，但默认不保证标准性以换取更紧凑表示。
- 适用于搜索算法与知识编译，可扩展至概率逻辑与加权模型计数。
本文提出状态代数（State Algebra），一种基于代数方法表示与操作命题逻辑的新框架。该框架采用三层结构：集合、坐标和行分解，既锚定于经典语义，又支持强大的代数运算。关键特性在于表示灵活性：尽管默认状态向量化简不具唯一性，但通过在化简过程中应用固定变量顺序，可获得唯一标准形式。这体现了权衡——放弃强制标准性以换取对特定问题类别的更紧凑表示。本文探讨了该框架如何支持搜索型与知识编译型算法，并讨论其自然延伸至概率逻辑与加权模型计数的能力。
原文摘要 · Abstract (English)
This paper presents State Algebra, a novel framework designed to represent and manipulate propositional logic using algebraic methods. The framework is structured as a hierarchy of three representations: Set, Coordinate, and Row Decomposition. These representations anchor the system in well-known semantics while facilitating the computation using a powerful algebraic engine. A key aspect of State Algebra is its flexibility in representation. We show that although the default reduction of a state vector is not canonical, a unique canonical form can be obtained by applying a fixed variable order during the reduction process. This highlights a trade-off: by foregoing guaranteed canonicity, the framework gains increased flexibility, potentially leading to more compact representations of certain classes of problems. We explore how this framework provides tools to articulate both search-based and knowledge compilation algorithms and discuss its natural extension to probabilistic logic and Weighted Model Counting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。