fbool

A Rust library for analyzing Boolean functions, with a focus on entanglement, information-theoretic measures, and circuit complexity. Includes Python bindings and a command-line interface.

This library was developed to support research on entanglement measures for Boolean functions. If you use it in your work, please cite the associated paper (see Citation).

Overview

fbool provides data structures and algorithms for:

• Representing Boolean functions compactly (truth-table encoding)
• Computing entanglement and min-max entanglement via bipartitions of variables
• Computing Shannon entropy of variable partitions
• Measuring influence, sensitivity, spectral properties (Walsh-Hadamard transform), and frontier structure
• Estimating certificate complexity
• Finding the minimum gate count for functions of up to 5 variables (via an integrated C++ optimizer)

The workspace also ships a Python package (fbool) built with PyO3 and maturin, and a CLI tool (fbool-cli).

Repository Structure

fbool/                 # Core Rust library
fbool-cli/             # Command-line interface
fbool-py/              # Python bindings (PyO3 + maturin)
clique_solver/         # CLIQUE-problem solver used internally
optimal5/              # Rust wrapper around Adam P. Goucher's optimal5 C++ engine (minimal-gate optimizer)

Theoretical Background

Boolean Functions

A Boolean function f : {0,1}^n -> {0,1} is represented as a truth table: a vector of 2^n Boolean values indexed by the binary encoding of each input.

Entanglement

Given a bipartition (A, B) of the n input variables, the information I(S) of a set S counts the number of distinct sub-functions obtained by fixing all variables outside S. The two entanglement measures defined in this work are:

Entanglement(f)        = min_{A,B}  [ I(A) + I(B) ]
MinMax-Entanglement(f) = min_{A,B}  max( I(A), I(B) )

Both minimize over all non-trivial bipartitions of {0, ..., n-1}.

Entropy

For a bipartition (A, B), the entropy is computed as the sum of the Shannon entropies of the empirical distributions induced by each partition. The minimum over all bipartitions gives the entropy measure of the function.

Rust Usage

Add fbool to your Cargo.toml:

[dependencies]
fbool = { git = "https://github.com/edugzlez/fbool" }

Basic Example

use fbool::fvalue::FValue;
use fbool::entanglement::{Entanglement, Entropy};

fn main() {
    // Majority function on 4 variables
    let f = FValue::majority(4);

    println!("Entanglement:        {}", f.entanglement());
    println!("MinMax entanglement: {}", f.minmax_entanglement());
    println!("Entropy:             {}", f.entropy());

    // Inspect all bipartitions
    for es in f.entanglement_sets() {
        println!("  {:?} | {:?}  ->  {}", es.set1, es.set2, es.entanglement);
    }
}

Available Boolean Functions

FValue provides constructors for many classical families:

Metrics

Python Usage

Installation

Build and install locally with maturin:

cd fbool-py
pip install maturin
maturin develop

Or with uv:

cd fbool-py
uv sync
uv run maturin develop

Example

import fbool

# Construct a Boolean function (primality on 4 variables)
f = fbool.FBool.primality(4)

# Entanglement
print("Entanglement:", f.entanglement())
print("MinMax entanglement:", f.minmax_entanglement())

# All bipartitions
for es in f.entanglement_sets():
    print(f"  {es.set1} | {es.set2}  ->  {es.entanglement}")

# Entropy
print("Entropy:", f.entropy())

# Truth table as NumPy array
tt = f.truth_table()
print("Truth table shape:", tt.shape)

FBool API

CLI Usage

Build and run:

cargo build --release --bin fbool-cli
./target/release/fbool-cli --help

Examples

# Entanglement of the majority function with 4 variables
fbool-cli entanglement majority -n 4

# All bipartitions, sorted by entanglement value
fbool-cli entanglement parity -n 5 --sets --sorted

# Entropy
fbool-cli entropy majority -n 4 --sets

# Per-variable information
fbool-cli subinfo primality -n 5

# Serialize a function to binary
fbool-cli encode primality -n 5 -o primality_5.bin

Building

Requirements: Rust 1.70+, a C++ compiler (for optimal5), Python 3.11+ (for Python bindings).

# Build the full workspace
cargo build --release

# Run all tests
cargo test --all

# Run lints
cargo clippy --all-targets --all-features

License

This project is licensed under the MIT License. See LICENSE for details.

Citation

If you use this software in academic work, please cite:

@software{fbool,
  author  = {Eduardo Gonz\'{a}lez and Ricardo Maurizio Paul},
  title   = {fbool: A Rust library for Boolean function entanglement analysis},
  year    = {2025},
  url     = {https://github.com/edugzlez/fbool}
}

The associated paper citation will be added upon publication.

Authors

• Eduardo González-Vaquero — edugzlez
• Ricardo Maurizio Paul

Acknowledgements

The optimal5 crate is a Rust wrapper around the optimal5 C++ engine by Adam P. Goucher, used under the MIT License. The original engine computes the minimum number of logic gates required to implement any Boolean function of up to 5 variables using a precomputed exhaustive lookup table.