valueOfXOR
plain-language theorem explainer
This definition supplies a function that evaluates an XOR constraint under a partial Boolean assignment, returning the computed parity when every variable is assigned and none otherwise. Researchers implementing backpropagation or unit propagation for SAT instances mixing CNF and XOR clauses in the Recognition Science complexity layer would cite it. The body is a direct conditional that tests assignment completeness via .all before folding Bool.xor over the retrieved values.
Claim. Let $n$ be a natural number, let $σ$ be a partial assignment (a map from variables to optional Booleans), and let $X$ be an XOR constraint consisting of a list of variables together with a target parity. Then valueOfXOR$(σ, X)$ equals some$(b)$ if every variable in the list of $X$ is mapped to some Boolean under $σ$, where $b$ is the result of left-folding XOR starting from false over those values, and equals none otherwise.
background
The module treats partial assignments as the state of a backpropagation process over SAT instances that include XOR constraints. PartialAssignment is the type Var n → Option Bool, where none marks an undetermined variable and some b marks a fixed value. An XORConstraint is the structure holding a list of variables together with the Boolean parity their values must satisfy.
proof idea
The definition is a direct case split: it checks whether X.vars.all (fun v => (σ v).isSome), and if true returns some of the foldl of Bool.xor starting from false over the list of (σ v).getD false values; otherwise it returns none.
why it matters
The definition supplies the primitive evaluator needed to propagate values through XOR clauses during backpropagation steps. It sits inside the SAT backpropagation machinery that supports complexity analysis in Recognition Science, feeding sibling functions such as BPStep and complete even though no external uses are recorded yet. It aligns with the framework's use of discrete parity constraints alongside the phi-ladder and forcing chain.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.