"""
BooFun: A comprehensive Boolean function analysis library.
This library provides tools for creating, analyzing, and visualizing Boolean functions
using multiple representations and advanced mathematical techniques.
Key Features:
- Multiple Boolean function representations (truth tables, circuits, BDDs, etc.)
- Spectral analysis and Fourier transforms
- Property testing algorithms
- Visualization tools
- Built-in Boolean function generators
Basic Usage:
>>> import boofun as bf
>>>
>>> # Create functions from any input
>>> xor = bf.create([0, 1, 1, 0]) # From truth table
>>> maj = bf.majority(5) # Built-in majority
>>> parity = bf.parity(4) # Built-in parity (XOR)
>>>
>>> # Natural operations
>>> g = xor & maj # AND
>>> h = ~xor # NOT
>>>
>>> # Spectral analysis
>>> xor.fourier() # Fourier coefficients
>>> xor.influences() # Variable influences
>>> xor.degree() # Fourier degree
"""
import typing
from typing import Optional
from .api import create, from_hex, partial, to_hex
from .core import BooleanFunction, ExactErrorModel, NoiseErrorModel, PACErrorModel, Property, Space
from .core.adapters import (
CallableAdapter,
LegacyAdapter,
NumPyAdapter,
SymPyAdapter,
adapt_callable,
adapt_numpy_function,
adapt_sympy_expr,
)
from .core.builtins import BooleanFunctionBuiltins
from .core.io import load, save
from .core.partial import PartialBooleanFunction
from .core.spaces import Measure
# Exception hierarchy for structured error handling
from .utils.exceptions import (
BooleanFunctionError,
ConfigurationError,
ConversionError,
ErrorCode,
EvaluationError,
InvalidInputError,
InvalidRepresentationError,
InvalidTruthTableError,
InvariantViolationError,
ResourceUnavailableError,
ValidationError,
)
# Legacy adapter for migrating from old BooleanFunc class (kept for backwards compatibility)
# Import on demand: from boofun.core.legacy_adapter import from_legacy, to_legacy
try:
from .core.legacy_adapter import LegacyWrapper, from_legacy, to_legacy
_HAS_LEGACY = True
except ImportError:
_HAS_LEGACY = False
from .analysis import PropertyTester, SpectralAnalyzer
from .analysis import block_sensitivity as analysis_block_sensitivity
from .analysis import certificates as analysis_certificates
from .analysis import sensitivity as analysis_sensitivity
from .analysis import symmetry as analysis_symmetry
# Fourier analysis utilities (Chapter 1 O'Donnell)
from .analysis.fourier import (
convolution,
dominant_coefficients,
even_part,
fourier_degree,
fourier_sparsity,
negate_inputs,
odd_part,
parseval_verify,
plancherel_inner_product,
restriction,
spectral_norm,
tensor_product,
)
# GF(2) analysis (Algebraic Normal Form)
from .analysis.gf2 import (
correlation_with_parity,
gf2_degree,
gf2_fourier_transform,
gf2_monomials,
gf2_to_string,
is_linear_over_gf2,
)
# Global Hypercontractivity (Keevash, Lifshitz, Long & Minzer)
from .analysis.global_hypercontractivity import (
GlobalHypercontractivityAnalyzer,
find_critical_p,
generalized_influence,
hypercontractivity_bound,
is_alpha_global,
noise_stability_p_biased,
p_biased_expectation,
p_biased_influence,
p_biased_total_influence,
threshold_curve,
)
# Hypercontractivity (Chapter 9 O'Donnell)
from .analysis.hypercontractivity import (
bonami_lemma_bound,
friedgut_junta_bound,
hypercontractive_inequality,
junta_approximation_error,
kkl_lower_bound,
level_d_inequality,
lq_norm,
max_influence_bound,
noise_operator,
)
from .testing import BooleanFunctionValidator, quick_validate, validate_representation
from .utils.finite_fields import GFField
from .utils.finite_fields import get_field as get_gf_field
# =============================================================================
# Top-level shortcuts for common functions (mathematician-friendly API)
# =============================================================================
[docs]
def majority(n: int) -> BooleanFunction:
"""
Create majority function on n variables: Maj_n(x) = 1 iff |{i: x_i=1}| > n/2.
Example:
>>> maj5 = bf.majority(5)
>>> maj5([1, 1, 1, 0, 0]) # True (3 > 2.5)
"""
return BooleanFunctionBuiltins.majority(n)
[docs]
def parity(n: int) -> BooleanFunction:
"""
Create parity (XOR) function on n variables: ⊕_n(x) = x_1 ⊕ x_2 ⊕ ... ⊕ x_n.
Example:
>>> xor3 = bf.parity(3)
>>> xor3([1, 1, 0]) # False (even number of 1s)
"""
return BooleanFunctionBuiltins.parity(n)
[docs]
def tribes(k: int, n: int) -> BooleanFunction:
"""
Create tribes function: AND of ORs on groups of k variables.
Tribes_{k,n}(x) = ⋀_{j=1}^{⌈n/k⌉} ⋁_{i∈T_j} x_i
This is the **dual tribes** convention (AND-of-ORs). The textbook tribes
(O'Donnell Ch. 4) uses OR-of-ANDs; the two are related by negation.
Args:
k: Size of each tribe (number of variables per group)
n: Total number of variables (if not divisible by k, last group is smaller)
Examples:
>>> t = bf.tribes(2, 4) # (x₀ ∨ x₁) ∧ (x₂ ∨ x₃), 4 variables
>>> t = bf.tribes(3, 9) # (x₀∨x₁∨x₂) ∧ (x₃∨x₄∨x₅) ∧ (x₆∨x₇∨x₈), 9 variables
"""
return BooleanFunctionBuiltins.tribes(k, n)
[docs]
def dictator(n: int, i: int = 0) -> BooleanFunction:
"""
Create dictator function on variable i: f(x) = x_i.
Args:
n: Number of variables
i: Index of dictating variable (default 0)
Examples:
>>> d = bf.dictator(5) # 5-var dictator on x₀
>>> d = bf.dictator(5, 2) # 5-var dictator on x₂
"""
return BooleanFunctionBuiltins.dictator(n, i)
[docs]
def constant(value: bool, n: int) -> BooleanFunction:
"""
Create constant function: f(x) = value for all x.
Example:
>>> zero = bf.constant(False, 3)
>>> one = bf.constant(True, 3)
"""
return BooleanFunctionBuiltins.constant(value, n)
[docs]
def AND(n: int) -> BooleanFunction:
"""
Create AND function on n variables: f(x) = x_1 ∧ x_2 ∧ ... ∧ x_n.
Example:
>>> and3 = bf.AND(3)
"""
truth_table = [0] * (2**n)
truth_table[-1] = 1 # Only all-1s input gives 1
return typing.cast("BooleanFunction", create(truth_table))
[docs]
def OR(n: int) -> BooleanFunction:
"""
Create OR function on n variables: f(x) = x_1 ∨ x_2 ∨ ... ∨ x_n.
Example:
>>> or3 = bf.OR(3)
"""
truth_table = [1] * (2**n)
truth_table[0] = 0 # Only all-0s input gives 0
return typing.cast("BooleanFunction", create(truth_table))
def f2_polynomial(n: int, monomials: typing.Any) -> BooleanFunction:
"""
Create f(x) = (-1)^{p(x)} where p is a polynomial over GF(2).
Each monomial is a set of variable indices. The function outputs 1
when the sum of monomials is 1 (mod 2), 0 otherwise.
Args:
n: Number of variables
monomials: Iterable of sets/lists of variable indices.
E.g., [{0,1}, {2,3}] means p(x) = x0*x1 + x2*x3 (mod 2).
Examples:
>>> f = bf.f2_polynomial(4, [{0,1}, {2,3}]) # x0*x1 + x2*x3 mod 2
>>> f = bf.f2_polynomial(5, [{0,1,2}]) # x0*x1*x2 mod 2
"""
return BooleanFunctionBuiltins.f2_polynomial(n, monomials)
[docs]
def random(n: int, balanced: bool = False, seed: int | None = None) -> BooleanFunction:
"""
Create a random Boolean function on n variables.
Args:
n: Number of variables
balanced: If True, output has equal 0s and 1s (default False)
seed: Random seed for reproducibility
Returns:
Random Boolean function
Example:
>>> f = bf.random(4) # Random 4-variable function
>>> g = bf.random(4, balanced=True) # Random balanced function
>>> h = bf.random(4, seed=42) # Reproducible random function
"""
import numpy as np
rng = np.random.default_rng(seed)
size = 2**n
if balanced:
# Balanced: exactly half 0s and half 1s
truth_table = np.zeros(size, dtype=int)
ones_positions = rng.choice(size, size // 2, replace=False)
truth_table[ones_positions] = 1
else:
truth_table = rng.integers(0, 2, size)
return typing.cast("BooleanFunction", create(truth_table.tolist()))
[docs]
def from_weights(weights: typing.Any, threshold_value: typing.Any = None) -> BooleanFunction:
"""
Create LTF (Linear Threshold Function) from weight vector.
Alias for weighted_majority() with more intuitive name for LTF creation.
f(x) = 1 iff w₁x₁ + w₂x₂ + ... + wₙxₙ ≥ θ
Args:
weights: List of integer/float weights for each variable
threshold_value: Threshold (default: sum(weights)/2)
Returns:
LTF (Linear Threshold Function)
Example:
>>> # Electoral college with 3 states: CA(55), TX(38), NY(29)
>>> electoral = bf.from_weights([55, 38, 29], threshold=61)
"""
return weighted_majority(weights, threshold_value)
[docs]
def threshold(n: int, k: int) -> BooleanFunction:
"""
Create k-threshold function on n variables.
f(x) = 1 if Σxᵢ ≥ k, else 0
Special cases:
- threshold(n, n) = AND
- threshold(n, 1) = OR
- threshold(n, (n+1)/2) = MAJORITY (for odd n)
Example:
>>> at_least_2 = bf.threshold(4, 2) # True if ≥2 inputs are 1
"""
from .analysis.ltf_analysis import create_threshold_function
return create_threshold_function(n, k)
[docs]
def weighted_majority(weights: typing.Any, threshold_value: typing.Any = None) -> BooleanFunction:
"""
Create a weighted majority (LTF) function.
f(x) = sign(w₁x₁ + ... + wₙxₙ - θ)
LTFs are also called "halfspaces" - they represent hyperplanes
cutting through the Boolean hypercube.
Example:
# Nassau County voting system
>>> nassau = bf.weighted_majority([31, 31, 28, 21, 2, 2])
# Standard majority (all equal weights)
>>> maj = bf.weighted_majority([1, 1, 1, 1, 1])
"""
from .analysis.ltf_analysis import create_weighted_majority
return create_weighted_majority(weights, threshold_value)
# Function families for growth analysis
try:
from .families import (
ANDFamily,
DictatorFamily,
FunctionFamily,
GrowthTracker,
InductiveFamily,
LTFFamily,
MajorityFamily,
ORFamily,
ParityFamily,
ThresholdFamily,
TribesFamily,
)
HAS_FAMILIES = True
except ImportError:
HAS_FAMILIES = False
# Optional imports with graceful fallback
try:
from .visualization import BooleanFunctionVisualizer
HAS_VISUALIZATION = True
except ImportError:
HAS_VISUALIZATION = False
# quantum_complexity is NOT re-exported here. It is an experimental module
# that computes classical estimates of quantum complexity bounds. Users who
# want it should import directly:
# from boofun.quantum_complexity import QuantumComplexityAnalyzer
# Version information
__version__ = "1.3.0"
__author__ = "Gabriel Taboada"
# Core exports for typical usage
__all__ = [
"AND",
"OR",
"BooleanFunction",
# =====================================================
# SECONDARY API (advanced users)
# =====================================================
# Full builtins class
"BooleanFunctionBuiltins",
"BooleanFunctionError", # Base exception
# Testing and validation
"BooleanFunctionValidator",
# Adapters for external integration
"CallableAdapter",
"ConfigurationError", # Setup/configuration errors
"ConversionError", # Representation conversion failures
# =====================================================
# EXCEPTIONS (structured error handling)
# =====================================================
"ErrorCode", # Machine-readable error codes
"EvaluationError", # Function evaluation failures
"ExactErrorModel",
"GFField",
# Global Hypercontractivity (Keevash et al.)
"GlobalHypercontractivityAnalyzer",
"InvalidInputError", # Invalid function arguments
"InvalidRepresentationError", # Unsupported representation
"InvalidTruthTableError", # Malformed truth table
"InvariantViolationError", # Internal library bugs
"LegacyAdapter",
"Measure",
"NoiseErrorModel",
"NumPyAdapter",
"PACErrorModel",
"PartialBooleanFunction",
"Property",
"PropertyTester",
"ResourceUnavailableError", # Optional deps unavailable
# Core utilities
"Space",
# Analysis (use directly or via function methods)
"SpectralAnalyzer",
"SymPyAdapter",
"ValidationError", # User input validation failures
# Version info
"__version__",
"adapt_callable",
"adapt_numpy_function",
"adapt_sympy_expr",
"analysis_block_sensitivity",
"analysis_certificates",
# Analysis submodules
"analysis_sensitivity",
"analysis_symmetry",
"bonami_lemma_bound",
"constant",
"convolution",
"correlation_with_parity",
# =====================================================
# PRIMARY API (mathematician-friendly)
# =====================================================
# Creation
"create",
"dictator",
"dominant_coefficients",
"even_part",
"find_critical_p",
"fourier_degree",
"fourier_sparsity",
"friedgut_junta_bound",
# Hex string I/O (thomasarmel-compatible)
"from_hex",
"from_weights", # Alias for weighted_majority
"generalized_influence",
"get_gf_field",
"gf2_degree",
# GF(2) analysis
"gf2_fourier_transform",
"gf2_monomials",
"gf2_to_string",
"hypercontractive_inequality",
"hypercontractivity_bound",
"is_alpha_global",
"is_linear_over_gf2",
"junta_approximation_error",
"kkl_lower_bound",
"level_d_inequality",
# File I/O
"load",
"lq_norm",
# Built-in functions (short names)
"majority",
"max_influence_bound",
"negate_inputs",
# Hypercontractivity (Chapter 9 O'Donnell)
"noise_operator",
"noise_stability_p_biased",
"odd_part",
"p_biased_expectation",
"p_biased_influence",
"p_biased_total_influence",
"parity",
# Fourier analysis (Chapter 1 O'Donnell)
"parseval_verify",
# Partial functions (streaming/incremental)
"partial",
"plancherel_inner_product",
"quick_validate",
"random", # Random function generator
"restriction",
"save",
"spectral_norm",
"tensor_product",
"threshold",
"threshold_curve",
"to_hex",
"tribes",
"validate_representation",
"weighted_majority",
]
# Add optional exports if available
if HAS_FAMILIES:
__all__.extend(
[
"ANDFamily",
"DictatorFamily",
"FunctionFamily",
"GrowthTracker",
"InductiveFamily",
"LTFFamily",
"MajorityFamily",
"ORFamily",
"ParityFamily",
"ThresholdFamily",
"TribesFamily",
]
)
if HAS_VISUALIZATION:
__all__.append("BooleanFunctionVisualizer")