boofun.analysis.equivalence

Equivalence testing and canonical forms for Boolean functions.

This module provides tools for: - Computing canonical representatives under various symmetry groups - Testing equivalence of Boolean functions - Finding automorphisms (self-symmetries) - Applying variable permutations and input/output transformations

Two functions are considered equivalent if one can be transformed into the other via some combination of: - Variable permutation: f(x_π(1), x_π(2), …, x_π(n)) - Input negation: f(x ⊕ s) for some shift s - Output negation: ¬f(x)

The canonical form is the lexicographically smallest representative under these transformations, enabling fast equivalence checking.

Functions

apply_permutation(f, perm)	Apply a variable permutation to a Boolean function.
are_equivalent(f, g[, include_shifts, ...])	Test if two Boolean functions are equivalent.
automorphisms(f[, include_shifts, ...])	Find all automorphisms (self-symmetries) of a Boolean function.
canonical_form(f[, include_shifts, ...])	Compute the canonical form of a Boolean function.
equivalence_class_size(f)	Compute the size of the equivalence class of f.
is_symmetric(f)	Check if a function is symmetric (invariant under all variable permutations).

Classes

AffineEquivalence([include_negation])	Utility class for affine equivalence testing.
PermutationEquivalence()	Utility class for permutation equivalence testing.

boofun.analysis.equivalence.canonical_form(f: BooleanFunction, include_shifts: bool = True, include_negation: bool = True) → Tuple[Tuple[int, ...], Tuple | None]

Compute the canonical form of a Boolean function.

The canonical form is the lexicographically smallest truth table achievable by applying allowed transformations: 1. Variable permutations (always applied) 2. Input shifts: f(x ⊕ s) (if include_shifts=True) 3. Output negation: ¬f (if include_negation=True)

Two functions have the same canonical form if and only if they are equivalent under the specified group of transformations.

Parameters:

• f – BooleanFunction to canonicalize

• include_shifts – Whether to consider input shifts (affine equivalence)

• include_negation – Whether to consider output negation

Returns:

Tuple of (canonical_truth_table, transformation) where transformation describes how to get from original to canonical form.

Example

>>> f = bf.create([0, 1, 1, 0])  # XOR
>>> g = bf.create([1, 0, 0, 1])  # XNOR
>>> canonical_form(f)[0] == canonical_form(g)[0]
True  # Same under negation

boofun.analysis.equivalence.are_equivalent(f: BooleanFunction, g: BooleanFunction, include_shifts: bool = True, include_negation: bool = True) → bool

Test if two Boolean functions are equivalent.

Two functions are equivalent if one can be transformed into the other via variable permutation, input shift, and/or output negation.

Parameters:

• f – Functions to compare

• g – Functions to compare

• include_shifts – Consider input shifts (affine equivalence)

• include_negation – Consider output negation

Returns:

True if f and g are equivalent

boofun.analysis.equivalence.apply_permutation(f: BooleanFunction, perm: Tuple[int, ...]) → BooleanFunction

Apply a variable permutation to a Boolean function.

If perm[i] = j, variable x_i in the original function becomes x_j in the result.

Parameters:

• f – BooleanFunction to permute

• perm – Permutation as a tuple where perm[i] is the new position of var i

Returns:

New BooleanFunction with permuted variables

Example

>>> f = bf.create([0, 0, 0, 1])  # AND(x0, x1)
>>> g = apply_permutation(f, (1, 0))  # Swap x0 and x1
>>> # g is still AND(x0, x1) since AND is symmetric

boofun.analysis.equivalence.automorphisms(f: BooleanFunction, include_shifts: bool = False, include_negation: bool = False) → List[Tuple[int, ...]]

Find all automorphisms (self-symmetries) of a Boolean function.

An automorphism is a transformation that maps f to itself. By default, only variable permutations are considered.

Parameters:

• f – BooleanFunction to analyze

• include_shifts – Consider input shifts

• include_negation – Consider output negation

Returns:

List of transformations (permutations) that are automorphisms

Example

>>> xor = bf.create([0, 1, 1, 0])
>>> autos = automorphisms(xor)
>>> len(autos)
2  # Identity and swap

boofun.analysis.equivalence.equivalence_class_size(f: BooleanFunction) → int

Compute the size of the equivalence class of f.

This is the number of distinct functions equivalent to f under variable permutation (excluding shifts and negation).

By the orbit-stabilizer theorem:

|orbit| = n! / |automorphisms|

Parameters:

f – BooleanFunction to analyze

Returns:

Size of the equivalence class

class boofun.analysis.equivalence.PermutationEquivalence

Utility class for permutation equivalence testing.

Provides caching and optimizations for repeated equivalence checks.

__init__()

canonical(f: BooleanFunction) → Tuple[int, ...]

Get cached canonical form.

equivalent(f: BooleanFunction, g: BooleanFunction) → bool

Test permutation equivalence using cached canonical forms.

clear_cache()

Clear the canonical form cache.

class boofun.analysis.equivalence.AffineEquivalence(include_negation: bool = True)

Utility class for affine equivalence testing.

Affine equivalence considers variable permutation, input shifts, and output negation.

__init__(include_negation: bool = True)

canonical(f: BooleanFunction) → Tuple[int, ...]

Get cached affine canonical form.

equivalent(f: BooleanFunction, g: BooleanFunction) → bool

Test affine equivalence using cached canonical forms.

clear_cache()

Clear the canonical form cache.