boofun.core.representations.anf_form

Algebraic Normal Form (ANF) representation for Boolean functions.

ANF represents Boolean functions as multivariate polynomials over GF(2): f(x) = ⊕ c_S * ∏_{i∈S} x_i

where c_S ∈ {0,1} are coefficients and ⊕ denotes XOR. This representation enables sparse storage when few high-order monomials appear.

Mathematical Background:

Every Boolean function can be uniquely represented as a polynomial over GF(2). The ANF is obtained by applying the Möbius transform to the truth table.

Key properties: - Degree of ANF equals the algebraic degree of the function - Linear functions have degree ≤ 1 - Quadratic functions have degree ≤ 2 - XOR function: x₀ ⊕ x₁ has ANF {∅: 0, {0}: 1, {1}: 1, {0,1}: 0}

Performance Characteristics:

• Space: O(2^n) worst case, often much smaller for sparse functions

• Evaluation: O(number of monomials)

• Conversion from truth table: O(n * 2^n) via Möbius transform

Examples

>>> # XOR function: f(x0, x1) = x0 ⊕ x1
>>> anf_data = {frozenset(): 0, frozenset({0}): 1, frozenset({1}): 1, frozenset({0,1}): 0}
>>>
>>> # Majority function has higher degree terms
>>> # f(x0, x1, x2) = x0*x1 + x0*x2 + x1*x2 + x0*x1*x2
>>> maj_anf = {frozenset({0,1}): 1, frozenset({0,2}): 1, frozenset({1,2}): 1, frozenset({0,1,2}): 1}
>>>
>>> # Constant functions
>>> zero_anf = {frozenset(): 0}  # Always 0
>>> one_anf = {frozenset(): 1}   # Always 1

Functions

anf_to_string(data[, variable_names])	Convert ANF to human-readable string representation.
create_anf_from_monomials(monomials, n_vars)	Create ANF representation from list of monomials.

Classes

ANFRepresentation()

Algebraic Normal Form representation of Boolean functions.

class boofun.core.representations.anf_form.ANFRepresentation

Algebraic Normal Form representation of Boolean functions.

Stores Boolean functions as sparse polynomials over GF(2) where: - Keys are frozensets representing variable subsets (monomials) - Values are coefficients in {0, 1}

Example: f(x0, x1) = x0 ⊕ x1 ⊕ x0*x1 Representation: {frozenset(): 0, frozenset({0}): 1, frozenset({1}): 1, frozenset({0,1}): 1}

evaluate(inputs: ndarray, data: Dict[FrozenSet[int], int], space: Space, n_vars: int) → bool | ndarray

Evaluate ANF polynomial at given inputs.

Parameters:

• inputs – Input values - can be integer indices or binary vectors

• data – ANF coefficients as {monomial: coefficient} dict

• space – Evaluation space

• n_vars – Number of variables

Returns:

Boolean result(s)

dump(data: Dict[FrozenSet[int], int], space: Space, **kwargs) → Dict[str, Any]

Export ANF in serializable format.

convert_from(source_repr: BooleanFunctionRepresentation, source_data: Any, space: Space, n_vars: int, **kwargs) → Dict[FrozenSet[int], int]

Convert from another representation to ANF.

convert_to(target_repr: BooleanFunctionRepresentation, source_data: Dict[FrozenSet[int], int], space: Space, n_vars: int, **kwargs) → Any

Convert from ANF to another representation.

create_empty(n_vars: int, **kwargs) → Dict[FrozenSet[int], int]

Create empty ANF (zero function).

is_complete(data: Dict[FrozenSet[int], int]) → bool

Check if ANF representation is complete.

time_complexity_rank(n_vars: int) → Dict[str, int]

Return time complexity estimates for ANF operations.

get_storage_requirements(n_vars: int) → Dict[str, int]

Return memory requirements for ANF representation.

get_monomials(data: Dict[FrozenSet[int], int]) → List[FrozenSet[int]]

Get all monomials with non-zero coefficients.

get_degree_k_terms(data: Dict[FrozenSet[int], int], k: int) → Dict[FrozenSet[int], int]

Get all terms of exactly degree k.

is_linear(data: Dict[FrozenSet[int], int]) → bool

Check if the function is linear (degree ≤ 1).

is_quadratic(data: Dict[FrozenSet[int], int]) → bool

Check if the function is quadratic (degree ≤ 2).

boofun.core.representations.anf_form.create_anf_from_monomials(monomials: List[List[int]], n_vars: int) → Dict[FrozenSet[int], int]

Create ANF representation from list of monomials.

Parameters:

• monomials – List of variable lists, e.g., [[0], [1], [0,1]] for x0 ⊕ x1 ⊕ x0*x1

• n_vars – Number of variables

Returns:

ANF dictionary representation

boofun.core.representations.anf_form.anf_to_string(data: Dict[FrozenSet[int], int], variable_names: List[str] | None = None) → str

Convert ANF to human-readable string representation.

Parameters:

• data – ANF coefficients

• variable_names – Optional variable names (default: x0, x1, …)

Returns:

String representation like “x0 ⊕ x1 ⊕ x0*x1”