AFTD Auto-Formalizing Theoretical Domains

NAEtoColor.naeColoring

defimported Lean

Given a Boolean assignment $\mathit{assign} : V \to \mathtt{Bool}$, defines a coloring of all vertices of the reduction graph by: $\mathtt{groundNode} \mapsto 0$; $\mathtt{varNode}\;v \mapsto 1$ if $\mathit{assign}(v) = \mathtt{true}$, else $2$; $\mathtt{clauseNode}\;c\;k \mapsto \texttt{NAEtoColor.clauseNodeColor}\;(\mathit{assign}(c.v_0))\;(\mathit{assign}(c.v_1))\;(\mathit{assign}(c.v_2))\;k$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
def NAEtoColor.naeColoring {V : Type} (assign : V → Bool) : OutputVertex V → Fin 3
Defined in
TCSlib, `NAEtoColor.naeColoring`
Lean proof
By CS 294-268 course staff (UC Berkeley, Spring 2026), from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 UC Berkeley CS 294. 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 3
  • NAEtoColor.NAEclauseA Not-All-Equal Clause
  • NAEtoColor.clauseNodeColorGiven three Boolean values $a, b, c$ (the truth values of a clause's three literals) and an index $k \in \mathrm{Fin}\,3$, returns the…
  • NAEtoColor.OutputVertexThe vertex set of the reduction graph is an inductive type with three constructors:
    • $\mathtt{groundNode}$ --- a…
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
/-- Coloring of entire simple graph obtained via reduction from NAE-SAT. Coloring constructed from NAE-SAT assignment. • groundNode ↦ 0 • varNode v ↦ 1 if assign v = true, else 2 • clauseNode c k ↦ clauseNodeColor (assign values of the 3 variables) -/
def NAEtoColor.naeColoring {V : Type} (assign : V → Bool) : OutputVertex V → Fin 3
  | .groundNode => 0
  | .varNode v => if assign v then 1 else 2
  | .clauseNode c k => clauseNodeColor (assign c.v0) (assign c.v1) (assign c.v2) k
See it in the graphDiscuss this resultChallenge it