AFTD Auto-Formalizing Theoretical Domains

BoolFourier.BoolToPM1_xor

theoremverifiedimported Lean

XOR as multiplication under the $\pm 1$ embedding. Let $\mathrm{BoolToPM1} : \mathrm{Bool} \to \bbr$ be the map sending $\mathtt{false}$ to $1$ and $\mathtt{true}$ to $-1$. Then for all Booleans $a$ and $b$, \[ \mathrm{BoolToPM1}(a \oplus b) = \mathrm{BoolToPM1}(a)\cdot\mathrm{BoolToPM1}(b), \] so the exclusive-or $a \oplus b$ is carried to the ordinary product in $\{-1,1\}\subset\bbr$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BooleanAnalysis in
lemma BoolFourier.BoolToPM1_xor (a b : Bool) :
    BoolToPM1 (Bool.xor a b) = BoolToPM1 a * BoolToPM1 b
Source
TCSlib, `BoolFourier.BoolToPM1_xor`
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
Classical.choiceQuot.soundpropext
Built on 2
  • BooleanAnalysis.boolToSignThe sign encoding maps $\mathrm{Bool}$ to $\{-1,1\}\subset\bbr$:…
  • BoolFourier.BoolToPM1The map $\mathrm{BoolToPM1} : \mathrm{Bool} \to \mathbb{R}$ sends $\mathtt{false}$ to $1$ and $\mathtt{true}$ to $-1$, realising the…
Used by 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Finset BooleanAnalysis in/-- Shows that the `{±1}` encoding converts XOR into multiplication. **Source:** [OD14, §1.3]. -/lemma BoolFourier.BoolToPM1_xor (a b : Bool) :    BoolToPM1 (Bool.xor a b) = BoolToPM1 a * BoolToPM1 b := by  cases a <;> cases b <;> simp [BoolToPM1, boolToSign, Bool.xor]
See it in the graphDiscuss this resultChallenge it