AFTD Auto-Formalizing Theoretical Domains

BoolBLR.bool_dist

defimported Lean

The distance between two Boolean functions $f, g : \{0,1\}^n \to \{0,1\}$ is \[ \dist(f, g) \;=\; \Pr_{x \sim \{0,1\}^n}[f(x) \ne g(x)], \] computed as the uniform expectation of the indicator $\mathbf{1}[f(x) \ne g(x)]$.

Statement

open Finset BoolFourier in
noncomputable def BoolBLR.bool_dist {n : ℕ}
    (f g : hypercube n → Bool) : ℝ
Defined in
TCSlib, `BoolBLR.bool_dist`
Lean proof
By Prastik Mohanraj, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Prastik Mohanraj. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Built on 2
  • BoolFourier.expectationFor $f : \{0,1\}^n \to \mathbb{R}$, the uniform expectation is \[ \mathbb{E}[f] = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} f(x). \]
  • BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for BooleanAnalysis.BoolCube $n$.
Used by 3

Lean source view module on GitHub

open Finset BoolFourier in
/-- Defines the uniform Hamming distance between two Boolean functions. **Source:** [OD14, §1.6]. -/
noncomputable def BoolBLR.bool_dist {n : ℕ}
    (f g : hypercube n → Bool) : ℝ :=
  expectation (fun x =>
    if f x = g x then 0 else 1)
See it in the graphDiscuss this resultChallenge it