boofun.analysis.basic_properties

Basic properties of Boolean functions.

This module implements fundamental structural properties as defined in Scott Aaronson’s Boolean Function Wizard:

unate: Is the function isomorphic to a monotone function?
qsym: Is the function isomorphic to a symmetric function?
balanced: Is the function balanced (equal 0s and 1s)?
prime: Is the function prime (not decomposable)?
dependence: How many variables does the function actually depend on?

These properties are important for understanding the structure of Boolean functions and can dramatically affect their complexity measures.

Functions

`bias`(f)	Compute the bias of f: E[f(x)] = Pr[f(x) = 1].
`dependent_variables`(f)	Find variables that f depends on.
`essential_variables`(f)	Count the number of essential (dependent) variables.
`find_decomposition`(f)	Try to find a decomposition of f.
`is_balanced`(f)	Check if f is balanced (equal number of 0s and 1s).
`is_monotone`(f)	Check if f is monotone.
`is_prime`(f)	Check if f is prime (not decomposable).
`is_quasisymmetric`(f)	Check if f is quasisymmetric (isomorphic to a symmetric function).
`is_symmetric`(f)	Check if f is symmetric.
`is_unate`(f)	Check if f is unate (isomorphic to a monotone function).
`make_unate`(f)	Transform f to a monotone function by negating variables if possible.
`monotone_closure`(f)	Compute the monotone closure of f.
`symmetry_type`(f)	Determine the symmetry type of f.
`weight`(f)	Compute the weight (number of 1s in truth table) of f.

boofun.analysis.basic_properties.is_monotone(f: BooleanFunction) → bool[source]

Check if f is monotone.

A function is monotone if for all x <= y (coordinate-wise), f(x) <= f(y). Equivalently, all partial derivatives are non-negative.

Parameters:: f – BooleanFunction to check
Returns:: True if f is monotone

boofun.analysis.basic_properties.is_unate(f: BooleanFunction) → Tuple[bool, List[int] | None][source]

Check if f is unate (isomorphic to a monotone function).

A function is unate if there exists a setting of input polarities (negate some variables) that makes it monotone.

Parameters:: f – BooleanFunction to check
Returns:: Tuple of (is_unate, polarities) where polarities[i] = 1 means keep variable i as-is, polarities[i] = -1 means negate it. If not unate, returns (False, None).

boofun.analysis.basic_properties.make_unate(f: BooleanFunction) → 'BooleanFunction' | None[source]

Transform f to a monotone function by negating variables if possible.

Parameters:: f – BooleanFunction to transform
Returns:: Monotone BooleanFunction if f is unate, None otherwise

boofun.analysis.basic_properties.monotone_closure(f: BooleanFunction) → BooleanFunction[source]

Compute the monotone closure of f.

The monotone closure g(x) = max_{y <= x} f(y).

Parameters:: f – BooleanFunction to close
Returns:: Monotone closure of f

boofun.analysis.basic_properties.is_symmetric(f: BooleanFunction) → bool[source]

Check if f is symmetric.

A function is symmetric if its value depends only on the Hamming weight of the input (number of 1s), not on which specific coordinates are 1.

Parameters:: f – BooleanFunction to check
Returns:: True if f is symmetric

boofun.analysis.basic_properties.is_quasisymmetric(f: BooleanFunction) → Tuple[bool, List[int] | None][source]

Check if f is quasisymmetric (isomorphic to a symmetric function).

A function is quasisymmetric if there exists a permutation of the input variables that makes it symmetric.

Parameters:: f – BooleanFunction to check
Returns:: Tuple of (is_quasisymmetric, permutation). If quasisymmetric, permutation maps original indices to new indices.

boofun.analysis.basic_properties.symmetry_type(f: BooleanFunction) → str[source]

Determine the symmetry type of f.

Returns:: One of “symmetric”, “quasisymmetric”, “asymmetric”

boofun.analysis.basic_properties.is_balanced(f: BooleanFunction) → bool[source]

Check if f is balanced (equal number of 0s and 1s).

Parameters:: f – BooleanFunction to check
Returns:: True if f is balanced

boofun.analysis.basic_properties.bias(f: BooleanFunction) → float[source]

Compute the bias of f: E[f(x)] = Pr[f(x) = 1].

Parameters:: f – BooleanFunction to analyze
Returns:: Bias in [0, 1]

boofun.analysis.basic_properties.weight(f: BooleanFunction) → int[source]

Compute the weight (number of 1s in truth table) of f.

Parameters:: f – BooleanFunction to analyze
Returns:: Number of inputs where f(x) = 1

boofun.analysis.basic_properties.dependent_variables(f: BooleanFunction) → List[int][source]

Find variables that f depends on.

A variable i is essential if there exists some x where flipping bit i changes the output.

Parameters:: f – BooleanFunction to analyze
Returns:: List of essential variable indices

boofun.analysis.basic_properties.essential_variables(f: BooleanFunction) → int[source]

Count the number of essential (dependent) variables.

This is the vars(f) property from BFW.

Parameters:: f – BooleanFunction to analyze
Returns:: Number of variables f depends on

boofun.analysis.basic_properties.is_prime(f: BooleanFunction) → bool[source]

Check if f is prime (not decomposable).

A function is prime if it cannot be written as a composition g(h1(x), h2(x)) where g is not a projection and h1, h2 are non-trivial (depend on < n variables each).

Parameters:: f – BooleanFunction to check
Returns:: True if f is prime

Note

This is a simplified primality check. Full decomposition detection is more complex.

boofun.analysis.basic_properties.find_decomposition(f: BooleanFunction) → Tuple[str, List[int], List[int]] | None[source]

Try to find a decomposition of f.

Looks for simple decompositions like: - f(x) = g(x_S) op h(x_T) where S, T partition the variables - op is AND, OR, or XOR

Parameters:: f – BooleanFunction to decompose
Returns:: Tuple of (operator, S_indices, T_indices) if decomposable, None otherwise