Power Term Polynomial Algebra for Boolean Logic

Emanuele Sansone, Armando Solar-Lezama · 2026

Read Power Term Polynomial Algebra for Boolean Logic by Emanuele Sansone, Armando Solar-Lezama (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13854.txt.

Introduction

Sansone and Solar-Lezama introduce power term polynomial algebra, a new language for Boolean formulas. It aims to bridge conjunctive normal form and algebraic normal form, two standard forms that convert badly between each other. Direct conversion can blow up in size unless extra variables are added. The new language encodes whole families of monomials compactly and keeps clauses in direct form. The authors define its semantics and prove rewrite rules that let formulas be manipulated without full expansion.

Catalog record

CREATOREmanuele Sansone, Armando Solar-Lezama
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75763
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13854

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Power Term Polynomial Algebra for Boolean Logic Emanuele Sansone, Armando Solar-Lezama Abstract We introduce power term polynomial algebra , a representation language for Boolean formulae designed to bridge conjunctive normal form (CNF) and algebraic normal form (ANF). The language is motivated by the tiling mismatch between these representations: direct CNF ↔ \leftrightarrow ANF conversion may cause exponential blowup unless formulas are decomposed into smaller fragments, typically through auxiliary variables and side constraints. In contrast, our framework addresses this mismatch within the representation itself, compactly encoding structured families of monomials while representing CNF clauses directly, thereby avoiding auxiliary variables and constraints at the abstraction level. We formalize the language through power terms and power term polynomials, define their semantics, and show that they admit algebraic operations corresponding to Boolean polynomial addition and multiplication. We prove several key properties of the language: disjunctive clauses admit compact canonical representations; power terms support local shortening and expansion rewrite rules; and products of atomic terms can be systematically rewritten within the language. Together, these results yield a symbolic calculus that enables direct manipulation of formulas without expanding them into ordinary ANF. The resulting framework provides a new intermediate representation and rewriting calculus that bridges clause-based and algebraic reasoning and suggests new directions for structure-aware CNF ↔ \leftrightarrow ANF conversion and hybrid reasoning methods. \hideLIPIcs CSAIL, MIT, USA and ESAT, KU Leuven, Belgium and https://emsansone.github.io [email protected]://orcid.org/0000-0002-6143-1619European Research Council (ERC) under Grant No. 101149800CSAIL, MIT, [email protected]://orcid.org/0000-0001-7604-8252National Science Foundation under Grant No. 1918839 \Copyright Emanuele Sansone and Armando Solar-Lezama \ccsdesc [500]Theory of computation Abstraction \ccsdesc [500]Theory of computation Logic \EventEditors John Q. Open and Joan R. Access \EventNoEds 2 \EventLongTitle 42nd Conference on Very Important Topics (CVIT 2016) \EventShortTitle SAT 2026 \EventAcronym SAT \EventYear 2016 \EventDate December 24–27, 2016 \EventLocation Little Whinging, United Kingdom \EventLogo \SeriesVolume 42 \ArticleNo 23 keywords Algebra, Boolean Logic, Power Term Polynomial Algebra, Power Term Polynomial Calculus, Polynomial Calculus category \relatedversion 1 Introduction Representations based on CNF and ANF lie at the core of modern approaches to reasoning about Boolean formulae. CNF representations underpin the success of modern SAT solvers and have been widely adopted for automated reasoning across a broad range of applications. In contrast, ANF representations play a central role in algebraic proof systems and have long been studied as a natural framework for analysing algebraic structure and complexity [ 6 , 3 ] . Although CNF and ANF describe the same underlying Boolean functions, they organize information in fundamentally different ways and therefore support different styles of reasoning. This difference becomes particularly relevant when converting between the two representations. While such conversions are always possible in principle, they can lead to significant growth in representation size because structure that is compact in one form may expand in the other [ 9 ] . As a result, existing approaches often require decomposing formulae into smaller fragments before translation. In this paper, we refer to this phenomenon as the tiling mismatch : the structure of the original representation does not align with the granularity naturally supported by the target representation. The goal of this work is to introduce a representation language that helps bridge this mismatch. We propose power term polynomial algebra , an abstraction language that compactly represents structured families of monomials while still encoding CNF clauses directly. The key idea is to group related monomials into symbolic objects called power terms , which can then be combined into power term polynomials . This yields a representation that sits between clause-based and polynomial-based descriptions while supporting algebraic-style manipulation. We first review the Boolean representations underlying SAT and the standard conversions between them, using this discussion to motivate the notion of tiling mismatch. We then introduce power terms and power term polynomials, define their semantics, and show that they admit natural composition rules based on addition and multiplication. Finally, we present rewriting principles that allow expressions to be manipulated directly in the abstraction language without expanding them into ordinary polynomial form. 2 Preliminaries We introduce the main representations underlying proof systems for the SAT problem, based on resolution and algebraic methods [ 6 ] . We then present conversions between these representations and finally introduce the tiling mismatch between representations. In the following, we consider a finite set of variables \mathcal{D}:=\{x_{1},\ldots,x_{n}\} , each defined over the set of Boolean values \mathbb{B}:=\{0,1\} , where 0 and 1 conventionally denote false and true , respectively. It is also useful to introduce the Boolean field \mathbb{F}_{2}:=GF(2) , also known as the Galois field with two elements, whose operations include addition, defined as integer addition modulo 2, and integer multiplication. Finally, we use the compact notation [n] to denote the index set \{1,\ldots,n\} . Boolean functions . The first representation is based on multivariate functions mapping \mathbb{B}^{n} to \mathbb{B} . The behaviour of a Boolean function f can be specified using a truth table , which assigns a Boolean value to each possible combination of variable assignments. A truth table can be represented canonically by listing the assignments for which f evaluates to 1 . Equivalently, this corresponds to defining the set of satisfying assignments \mathcal{A}(f):=\{a\in\mathbb{B}^{n}\mid f(a)=1\} . Propositional logic formulae . The second representation introduces logical connectives, including negation \neg , conjunction \land , and disjunction \lor , to construct expressions composed of variables from the domain \mathcal{D} . In the context of SAT, formulae are typically expressed in CNF, i.e., as a conjunction of a finite set of clauses \phi:=\bigwedge_{i=1}^{m}C_{i} . Each clause is a disjunction of literals C_{i}:=\bigvee_{j=1}^{n_{i}}L_{i,j} , where literals are either variables or their negations (referred to as positive and negative literals, respectively). Semantically, each logical connective is associated with a predefined truth table. The meaning of clauses and formulae can therefore be defined recursively from variable assignments and the corresponding truth tables of the connectives. Analogously to Boolean functions, the set of satisfying assignments of \phi is the set of variable assignments for which the formula evaluates to true , i.e. \mathcal{A}(\phi):=\{a\in\mathbb{B}^{n}\mid\phi(a)=1\} . Every CNF formula \phi corresponds to a unique Boolean function f , defined by the relation \mathcal{A}(\phi)=\mathcal{A}(f) . The mapping from CNF formulae to Boolean functions is therefore surjective, since the same Boolean function can be represented by many different CNF formulae. Boolean polynomials . The third representation uses polynomials over the field \mathbb{F}_{2} , together with the idempotent relation x_{i}^{2}=x_{i} for every variable. 1 1 1 Mathematically written as \mathbb{F}_{2}[x_{1},\ldots,x_{n}]/\{x_{i}^{2}=x_{i}\mid i\in[n]\} . This relation ensures that variables appearing in monomials are square-free. More concretely, a polynomial is a linear combination of monomials p:=\sum_{S\subseteq[n]}\alpha_{S}m_{S} , where each monomial is the product of a set of variables m_{S}:=\prod_{i\in S}x_{i} (with the convention that m_{\emptyset}:=1 ) and \alpha_{S}\in\mathbb{B} are coefficients associated with each monomial. Since every polynomial contains a unique set of monomials and monomials represent a basis for the polynomial space, the relation between the semantic behaviour of Boolean polynomials and Boolean functions is bijective. Consequently, Boolean polynomials provide a canonical representation of propositional logic formulae and are therefore often referred to as their ANF. Another subtle but important result is that the coefficients of the ANF representation are uniquely determined by the truth table of the corresponding Boolean function. In particular, the mapping between the truth table of

Read the complete text