Skip to content

Algebraic normal form

The unique multilinear polynomial over GF(2) representing a Boolean function as an XOR of square-free AND monomials and an optional constant.

Version
v1 · 2026-09-28 · History
Domain-specific #
7918
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomains
Boolean Algebra, Finite Fields → Mathematics

Core Idea

Algebraic normal form is the unique multilinear polynomial over GF(2) for a Boolean function: square-free AND monomials with 0/1 coefficients are combined by XOR, with an optional constant. Because coefficients are only zero or one, a monomial is either absent or present. Because coefficients are only zero or one, a monomial is either absent or present.

How would you explain it like I'm…

The Lamp-Flipping List

Imagine a lamp that some teams of switches can flip. Each team flips the lamp only when every switch in that team is on. You start with the lamp off, or sometimes on, and each team that's all on flips it once more. Algebraic normal form writes any on-off rule as a list of which teams flip the lamp, and each rule has only one such list.

AND Groups Joined by XOR

A Boolean function takes some yes/no inputs and gives a yes/no answer, like a rule deciding if a light turns on from several switches. Algebraic normal form writes any such rule in one standard way. You make groups of inputs joined by AND (all must be on), and then combine the groups with XOR, which flips the answer each time a group is on. You can also include a constant 1 at the start. Every Boolean rule can be written like this in exactly one way, so two rules are the same if and only if their lists match. This is different from the more familiar way of combining groups with OR.

Unique GF(2) Polynomial Form

Algebraic normal form (ANF) writes a Boolean function as a polynomial over GF(2), the two-element field where 1 + 1 = 0. Multiplication in that field is AND and addition is XOR. Each term is a product of distinct variables, called a monomial, and the function is the XOR of some of these monomials plus possibly the constant 1. Because every input is 0 or 1, x² = x, so no variable ever needs to appear squared, and because x XOR x = 0, repeated terms cancel. What remains is a unique reduced polynomial for each function, so two functions are equal exactly when their ANFs match. It is used in cryptography and circuit design, though some simple functions need a lot of terms in ANF. It is not the same as disjunctive normal form (DNF), which combines terms with OR.

 

Algebraic normal form represents a Boolean function f: {0,1}^n → {0,1} as a polynomial over GF(2). Monomials are products of distinct variables, i.e., conjunctions, and the polynomial is the XOR (field addition) of a set of such monomials plus an optional constant. Since coefficients are 0 or 1, each monomial is simply present or absent; since Boolean inputs satisfy x² = x, higher powers collapse; and since duplicate monomials cancel under XOR, the result is a reduced multilinear polynomial. Every Boolean function has a unique ANF, which supports equality testing, cryptographic analysis such as reasoning about algebraic degree, and circuit representation. Its size is basis-dependent: a function that is compact in another representation may need many ANF monomials. ANF must not be confused with DNF, where OR replaces XOR and uniqueness does not hold in the same way.

Scope of Application

ANF applies wherever a Boolean function is analyzed through its unique GF(2) multilinear polynomial. Use it for Boolean functions only under GF(2) arithmetic, x²=x reduction, duplicate cancellation, and exact equality on all inputs.

  • Boolean algebra. Provides a canonical function representation.
  • Cryptography. Studies algebraic degree and nonlinear terms.
  • Logic circuits. Translates functions into XOR–AND structure.
  • Coding theory. Uses GF(2) polynomial relations.
  • Formal verification. Compares functions through canonical coefficients.

Clarity

The representation separates three operations often blurred in logical notation: AND is multiplication, XOR is addition, and ordinary OR must be translated. Its uniqueness applies to the represented function after GF(2) reduction, not to arbitrary written formulas. The closest near miss sets the boundary: Disjunctive normal form is the closest near miss: it also sums conjunction-like terms but uses OR rather than XOR and is not generally unique. A positive case must satisfy this test: Include a reduced XOR sum of distinct square-free conjunction monomials over GF(2) that equals the Boolean function on all assignments.

Manages Complexity

A truth table with 2^n rows becomes a set of monomial coefficients. The canonical form supports comparison and algebraic manipulation while exposing degree and interaction structure that a syntactic Boolean formula can hide. The central canonical comparison–representation size tradeoff is this: Uniqueness simplifies equality while some functions expand into many monomials. A second logical intuition–GF(2) arithmetic tension matters because Familiar OR/NOT syntax does not map symbol-for-symbol to XOR–AND algebra.

Abstract Reasoning

Use three linked moves: fix Boolean variables and interpret values in GF(2); convert logical operations or the truth table into polynomial coefficients; reduce powers using x²=x and coefficients modulo two. As a collapse test, the case exits when arithmetic is not mod 2, variables are not Boolean/idempotent, or the expression is not reduced to its unique square-free monomial set. A fourth check is to cancel duplicate monomials under XOR and order the remainder canonically. A final check is to verify function equality on all assignments or through a valid transform.

Knowledge Transfer

ANF transfers literally across Boolean functions, circuits, and cryptographic mappings using the same GF(2) semantics. Calling an ordinary polynomial 'algebraic normal form' outside this quotient structure is not literal transfer. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. ANF maps a Boolean function into a polynomial medium with exact fidelity. Reduction yields a canonical member of the equivalence class.

Relationships to Other Abstractions

Local relationship map for Algebraic normal formParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Algebraic normal formDOMAINDomain-specific abstraction: Polynomial — is a kind ofPolynomialDOMAIN

Current abstraction Algebraic normal form Domain-specific

Parents (1) — more general patterns this builds on

  • Algebraic normal form is a kind of Polynomial Domain-specific

    It is a multilinear polynomial normal form over GF(2).

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Algebraic normal form sits in a moderately populated region (47th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Polynomials & Algebraic Invariants (20 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08