AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.boolSign_xor

theoremverifiedimported Lean

Boolean sign turns XOR into multiplication. Write $\mathrm{sgn} : \mathrm{Bool} \to \bbr$ for the Boolean sign map, which sends $\mathrm{false}$ to $1$ and $\mathrm{true}$ to $-1$. Then for all Boolean values $a, b$, \[ \mathrm{sgn}(a \oplus b) \;=\; \mathrm{sgn}(a)\,\mathrm{sgn}(b), \] where $a \oplus b$ denotes the exclusive-or of $a$ and $b$; equivalently, $\mathrm{sgn}$ is a homomorphism from $(\mathrm{Bool}, \oplus)$ to the multiplicative group $\{\pm 1\}$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
@[simp] lemma CommunicationComplexity.boolSign_xor (a b : Bool) :
    boolSign (Bool.xor a b) = boolSign a * boolSign b
Source
TCSlib, `CommunicationComplexity.boolSign_xor`
Lean proof
By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. 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
Classical.choiceQuot.soundpropext
Built on 1
  • CommunicationComplexity.boolSign$\texttt{boolSign} : \mathrm{Bool} \to \mathbb{R}$ assigns the real value $1$ to $\mathrm{false}$ and $-1$ to $\mathrm{true}$, embedding…
Used by 4

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- The sign of an exclusive or is the product of the signs: `boolSign (a xor b)` equals `boolSign a * boolSign b`. This is the one-bit case of the character identity `χ_S · χ_T = χ_{S △ T}` [OD14, §1.3]. -/@[simp] lemma CommunicationComplexity.boolSign_xor (a b : Bool) :    boolSign (Bool.xor a b) = boolSign a * boolSign b := by  cases a <;> cases b <;> norm_num [boolSign]
See it in the graphDiscuss this resultChallenge it