Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CookLevin CNF Satisfiability and Encoding

Definition
CookLevin_Satisfiability

by Rizwan G Mir · Sep 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

cnfencodingsatsatisfiability

CNF formulas, satisfiability (Satisfies, Satisfiable), numeric encoding (literalN, clauseN, formulaN), binary string encoding (encodeNat, encodeListNat, encodeFormula), and the language SAT.

Definition code
/-
  CookLevinLean/Satisfiability.lean

  CNF formulas, satisfiability, encoding of formulas as numbers / binary
  strings, and the language SAT.  Translated from the Isabelle/HOL theory
  `Satisfiability.thy` of the Cook–Levin formalization.
-/
import Definitions.Def_CookLevin_Basic
set_option autoImplicit true

namespace CookLevin

/-! ## Literals, clauses, formulas, assignments -/

/-- A set of elements of type α -/
def Set (α : Type) := α → Prop

/-- Set membership -/
def Set.mem (x : α) (s : Set α) : Prop := s x

/-- A literal is a negated or a positive propositional variable. -/
inductive Literal
  | Neg (n : Nat)
  | Pos (n : Nat)
  deriving DecidableEq, Repr, Inhabited

/-- The variable occurring in a literal. -/
def Literal.var : Literal → Nat
  | .Neg n => n
  | .Pos n => n

/-- The negation of a literal. -/
def Literal.negate : Literal → Literal
  | .Neg n => .Pos n
  | .Pos n => .Neg n

/-- A clause is a disjunction of literals, represented as a list. -/
abbrev Clause := List Literal

/-- A CNF formula is a conjunction of clauses, represented as a list. -/
abbrev Formula := List Clause

/-- An assignment maps variable indices to truth values. -/
abbrev Assignment := Nat → Bool

/-! ## Satisfaction -/

/-- Truth value of a literal under an assignment. -/
def satisfiesLiteral (α : Assignment) : Literal → Bool
  | .Neg n => !α n
  | .Pos n => α n

/-- A clause is satisfied if at least one of its literals is. -/
def satisfiesClause (α : Assignment) (c : Clause) : Bool :=
  c.any (satisfiesLiteral α)

/-- A formula is satisfied if all of its clauses are (`α ⊨ φ`). -/
def Satisfies (α : Assignment) (φ : Formula) : Prop :=
  ∀ c ∈ φ, satisfiesClause α c = true

/-- Notation `α ⊨ φ` for `Satisfies α φ`. -/
scoped infix:60 " ⊨ " => Satisfies

instance (α : Assignment) (φ : Formula) : Decidable (Satisfies α φ) := by
  unfold Satisfies; infer_instance

/-- Boolean version of `Satisfies`. -/
def satisfiesB (α : Assignment) (φ : Formula) : Bool :=
  φ.all (satisfiesClause α)

theorem satisfiesB_eq_true_iff (α : Assignment) (φ : Formula) :
    satisfiesB α φ = true ↔ Satisfies α φ := by
  simp [satisfiesB, Satisfies, List.all_eq_true]

theorem satisfiesClause_iff (α : Assignment) (c : Clause) :
    satisfiesClause α c = true ↔ ∃ x ∈ c, satisfiesLiteral α x = true := by
  simp [satisfiesClause, List.any_eq_true]

/-- A formula is satisfiable if some assignment satisfies it. -/
def Satisfiable (φ : Formula) : Prop :=
  ∃ α : Assignment, Satisfies α φ

/-- The set of variables occurring in a formula. -/
def variables (φ : Formula) : Set Nat :=
  fun n => ∃ c ∈ φ, Literal.Neg n ∈ c ∨ Literal.Pos n ∈ c

/-- The list of variables occurring in a formula (with repetitions). -/
def variablesList (φ : Formula) : List Nat :=
  φ.foldr (fun c acc => c.map Literal.var ++ acc) []

/-- The size of a formula: the total number of literal occurrences. -/
def fsize (φ : Formula) : Nat :=
  (φ.map List.length).sum

/-! ## Encoding literals, clauses and formulas as natural numbers -/

/-- Literals as numbers: `Neg i ↦ 2i`, `Pos i ↦ 2i + 1`. -/
def literalN : Literal → Nat
  | .Neg i => 2 * i
  | .Pos i => 2 * i + 1

/-- Numbers as literals: even numbers are negative, odd ones positive. -/
def nLiteral (n : Nat) : Literal :=
  if n % 2 = 0 then .Neg (n / 2) else .Pos (n / 2)

/-- Clauses as lists of numbers. -/
def clauseN (cl : Clause) : List Nat :=
  cl.map literalN

/-- Lists of numbers as clauses. -/
def nClause (ns : List Nat) : Clause :=
  ns.map nLiteral

/-- Formulas as lists of lists of numbers. -/
def formulaN (φ : Formula) : List (List Nat) :=
  φ.map clauseN

/-- Lists of lists of numbers as formulas. -/
def nFormula (nss : List (List Nat)) : Formula :=
  nss.map nClause

/-! ### Round-trip properties of the numeric encoding -/

@[simp] theorem nLiteral_literalN (x : Literal) : nLiteral (literalN x) = x := by
  cases x with
  | Neg i =>
    have h1 : (2 * i) % 2 = 0 := by omega
    have h2 : (2 * i) / 2 = i := by omega
    simp [nLiteral, literalN, h1, h2]
  | Pos i =>
    have _h1 : ¬ (2 * i + 1) % 2 = 0 := by omega
    have h2 : (2 * i + 1) / 2 = i := by omega
    simp [nLiteral, literalN, h2]

@[simp] theorem literalN_nLiteral (n : Nat) : literalN (nLiteral n) = n := by
  unfold nLiteral
  by_cases h : n % 2 = 0
  · simp [h, literalN]; omega
  · simp [h, literalN]; omega

@[simp] theorem nClause_clauseN (cl : Clause) : nClause (clauseN cl) = cl := by
  simp [nClause, clauseN, List.map_map, Function.comp_def]

@[simp] theorem clauseN_nClause (ns : List Nat) : clauseN (nClause ns) = ns := by
  simp [nClause, clauseN, List.map_map, Function.comp_def]

@[simp] theorem nFormula_formulaN (φ : Formula) : nFormula (formulaN φ) = φ := by
  simp [nFormula, formulaN, List.map_map, Function.comp_def]

@[simp] theorem formulaN_nFormula (nss : List (List Nat)) : formulaN (nFormula nss) = nss := by
  simp [nFormula, formulaN, List.map_map, Function.comp_def]

theorem literalN_injective : Function.Injective literalN :=
  Function.LeftInverse.injective nLiteral_literalN

theorem clauseN_injective : Function.Injective clauseN :=
  Function.LeftInverse.injective nClause_clauseN

theorem formulaN_injective : Function.Injective formulaN :=
  Function.LeftInverse.injective nFormula_formulaN

theorem length_clauseN (cl : Clause) : (clauseN cl).length = cl.length := by
  simp [clauseN]

theorem length_formulaN (φ : Formula) : (formulaN φ).length = φ.length := by
  simp [formulaN]

/-! ### Basic facts about `fsize` -/

@[simp] theorem fsize_nil : fsize [] = 0 := rfl

@[simp] theorem fsize_cons (c : Clause) (φ : Formula) :
    fsize (c :: φ) = c.length + fsize φ := by
  simp [fsize]

theorem fsize_append (φ ψ : Formula) : fsize (φ ++ ψ) = fsize φ + fsize ψ := by
  simp [fsize]

/-! ## Encoding formulas as binary strings -/

/-- A language is a set of binary strings. -/
abbrev Language := List Bool → Prop

/-- Encode a natural number as a list of Bools (unary: `n` true's followed by a false). -/
def encodeNat : Nat → List Bool
  | 0 => [false]
  | n + 1 => true :: encodeNat n

@[simp] theorem encodeNat_length (n : Nat) : (encodeNat n).length = n + 1 := by
  induction n with
  | zero => rfl
  | succ n ih => simp [encodeNat, ih]

theorem encodeNat_append (n : Nat) (rest : List Bool) :
    encodeNat n ++ rest = match n with
      | 0 => false :: rest
      | n + 1 => true :: (encodeNat n ++ rest) := by
  cases n <;> rfl

/-- Decode a natural number from a list of Bools using fuel. -/
def decodeNatFuel : Nat → List Bool → Nat × List Bool
  | 0, bs => (0, bs)
  | _fuel + 1, false :: bs => (0, bs)
  | fuel + 1, true :: bs => let (r, rest) := decodeNatFuel fuel bs; (r + 1, rest)
  | _fuel + 1, [] => (0, [])

theorem decodeNatFuel_encodeNat (fuel : Nat) (n : Nat) (rest : List Bool) (h : n < fuel) :
    decodeNatFuel fuel (encodeNat n ++ rest) = (n, rest) := by
  induction n generalizing fuel with
  | zero =>
    cases fuel with
    | zero => omega
    | succ fuel => rfl
  | succ n ih =>
    cases fuel with
    | zero => omega
    | succ fuel =>
      have h1 : n < fuel := by omega
      rw [encodeNat_append]
      simp [decodeNatFuel, ih fuel h1]

/-- Encode a list of natural numbers. -/
def encodeListNat : List Nat → List Bool
  | [] => [false]
  | n :: ns => true :: (encodeNat n ++ encodeListNat ns)

@[simp] theorem encodeListNat_length (ns : List Nat) : (encodeListNat ns).length ≥ 1 := by
  cases ns <;> simp [encodeListNat]

theorem encodeListNat_append (ns : List Nat) (rest : List Bool) :
    encodeListNat ns ++ rest = match ns with
      | [] => false :: rest
      | n :: ns' => true :: (encodeNat n ++ (encodeListNat ns' ++ rest)) := by
  cases ns <;> simp [encodeListNat]

/-- Decode a list of natural numbers using fuel. -/
def decodeListNatFuel : Nat → List Bool → List Nat × List Bool
  | 0, bs => ([], bs)
  | _fuel + 1, false :: bs => ([], bs)
  | fuel + 1, true :: bs =>
    let (n, bs1) := decodeNatFuel fuel bs
    let (ns, bs2) := decodeListNatFuel fuel bs1
    (n :: ns, bs2)
  | _fuel + 1, [] => ([], [])

theorem decodeListNatFuel_encodeListNat (fuel : Nat) (ns : List Nat) (rest : List Bool)
    (h : (encodeListNat ns ++ rest).length ≤ fuel) :
    decodeListNatFuel fuel (encodeListNat ns ++ rest) = (ns, rest) := by
  induction ns generalizing fuel with
  | nil =>
    cases fuel with
    | zero =>
      rw [encodeListNat_append] at h
      simp at h
    | succ fuel =>
      rw [encodeListNat_append]
      rfl
  | cons n ns ih =>
    cases fuel with
    | zero =>
      rw [encodeListNat_append] at h
      simp at h
    | succ fuel =>
      rw [encodeListNat_append]
      have hlen : (encodeListNat (n :: ns) ++ rest).length = (encodeNat n).length + (encodeListNat ns ++ rest).length + 1 := by
        simp [encodeListNat]
      have hn : n < fuel := by
        rw [hlen, encodeNat_length] at h
        omega
      have hrest : (encodeListNat ns ++ rest).length ≤ fuel := by
        rw [hlen, encodeNat_length] at h
        omega
      simp [decodeListNatFuel, decodeNatFuel_encodeNat fuel n _ hn, ih fuel hrest]

/-! ### The encoding as a stream

A machine writes the encoding left to right, one piece per turn of a loop, so
what it needs is not the recursive definition but a *flat* description: the bits
of `encodeListNat (l.map f)` are exactly one `true` and one `encodeNat` per
element of `l`, then a closing `false`.  These two lemmas are the bridge between
"the bits a loop emits" and "`encodeFormula` of the CNF". -/

theorem encodeListNat_map {β : Type} (f : β → Nat) : ∀ l : List β,
    encodeListNat (l.map f) = l.flatMap (fun x => true :: encodeNat (f x)) ++ [false]
  | [] => rfl
  | x :: l => by
    rw [List.map_cons, encodeListNat, List.flatMap_cons, encodeListNat_map f l]
    simp [List.append_assoc]

/-- Encode a list of lists of natural numbers (`formulaN`). -/
def encodeFormulaN : List (List Nat) → List Bool
  | [] => [false]
  | ns :: nss => true :: (encodeListNat ns ++ encodeFormulaN nss)

theorem encodeFormulaN_map {β : Type} (f : β → List Nat) : ∀ l : List β,
    encodeFormulaN (l.map f) = l.flatMap (fun x => true :: encodeListNat (f x)) ++ [false]
  | [] => rfl
  | x :: l => by
    rw [List.map_cons, encodeFormulaN, List.flatMap_cons, encodeFormulaN_map f l]
    simp [List.append_assoc]

theorem encodeFormulaN_append (nss : List (List Nat)) (rest : List Bool) :
    encodeFormulaN nss ++ rest = match nss with
      | [] => false :: rest
      | ns :: nss' => true :: (encodeListNat ns ++ (encodeFormulaN nss' ++ rest)) := by
  cases nss <;> simp [encodeFormulaN]

/-- Decode a list of lists of natural numbers using fuel. -/
def decodeFormulaNFuel : Nat → List Bool → List (List Nat) × List Bool
  | 0, bs => ([], bs)
  | _fuel + 1, false :: bs => ([], bs)
  | fuel + 1, true :: bs =>
    let (ns, bs1) := decodeListNatFuel fuel bs
    let (nss, bs2) := decodeFormulaNFuel fuel bs1
    (ns :: nss, bs2)
  | _fuel + 1, [] => ([], [])

theorem decodeFormulaNFuel_encodeFormulaN (fuel : Nat) (nss : List (List Nat)) (rest : List Bool)
    (h : (encodeFormulaN nss ++ rest).length ≤ fuel) :
    (decodeFormulaNFuel fuel (encodeFormulaN nss ++ rest)).1 = nss := by
  induction nss generalizing fuel with
  | nil =>
    cases fuel with
    | zero =>
      rw [encodeFormulaN_append] at h
      simp at h
    | succ fuel =>
      rw [encodeFormulaN_append]
      rfl
  | cons ns nss ih =>
    cases fuel with
    | zero =>
      rw [encodeFormulaN_append] at h
      simp at h
    | succ fuel =>
      rw [encodeFormulaN_append]
      have hlen : (encodeFormulaN (ns :: nss) ++ rest).length = (encodeListNat ns).length + (encodeFormulaN nss ++ rest).length + 1 := by
        simp [encodeFormulaN]
      have hns : (encodeListNat ns ++ (encodeFormulaN nss ++ rest)).length ≤ fuel := by
        rw [hlen] at h
        simp at h ⊢
        omega
      have hnss : (encodeFormulaN nss ++ rest).length ≤ fuel := by
        rw [hlen] at h
        have := encodeListNat_length ns
        omega
      simp [decodeFormulaNFuel, decodeListNatFuel_encodeListNat fuel ns _ hns, ih fuel hnss]

/-- Decoding formula from binary string. -/
def decodeFormula (bs : List Bool) : Formula :=
  nFormula (decodeFormulaNFuel (bs.length + 1) bs).1

/-- Encoding of a formula as a binary string. -/
def encodeFormula (φ : Formula) : List Bool :=
  encodeFormulaN (formulaN φ)

theorem decodeFormula_encodeFormula (φ : Formula) :
    decodeFormula (encodeFormula φ) = φ := by
  dsimp [decodeFormula, encodeFormula]
  have hlen : (encodeFormulaN (formulaN φ) ++ []).length ≤ (encodeFormulaN (formulaN φ)).length + 1 := by
    simp
  have hdec := decodeFormulaNFuel_encodeFormulaN ((encodeFormulaN (formulaN φ)).length + 1) (formulaN φ) [] hlen
  simp at hdec
  rw [hdec]
  exact nFormula_formulaN φ

theorem encodeFormula_injective : Function.Injective encodeFormula :=
  Function.LeftInverse.injective decodeFormula_encodeFormula

/-- A binary string is a (valid) encoding of some formula. -/
def IsFormulaString (x : List Bool) : Prop :=
  ∃ φ : Formula, x = encodeFormula φ

/-! ## The language SAT -/

/-- The language SAT: the encodings of satisfiable CNF formulas, and nothing
else.  A string that encodes no formula is *not* in SAT. -/
def SAT : Language := fun x => ∃ φ : Formula, x = encodeFormula φ ∧ Satisfiable φ

theorem SAT_of_satisfiable {φ : Formula} (h : Satisfiable φ) : SAT (encodeFormula φ) :=
  ⟨φ, rfl, h⟩

/-- A string that encodes no formula is not in SAT. -/
theorem not_SAT_of_not_formulaString {x : List Bool} (h : ¬ IsFormulaString x) : ¬ SAT x := by
  rintro ⟨φ, rfl, -⟩
  exact h ⟨φ, rfl⟩

/-- Every member of SAT is an encoding. -/
theorem isFormulaString_of_SAT {x : List Bool} (h : SAT x) : IsFormulaString x := by
  obtain ⟨φ, rfl, -⟩ := h
  exact ⟨φ, rfl⟩

/-- On valid encodings, membership in SAT is exactly satisfiability of the
encoded formula. -/
theorem SAT_encodeFormula_iff (φ : Formula) : SAT (encodeFormula φ) ↔ Satisfiable φ := by
  constructor
  · rintro ⟨ψ, hψ, hsat⟩
    have hψφ : ψ = φ := encodeFormula_injective hψ.symm
    exact hψφ ▸ hsat
  · exact SAT_of_satisfiable

/-! ## Basic facts about satisfaction -/

@[simp] theorem satisfies_nil (α : Assignment) : Satisfies α [] := by
  intro c hc
  simp at hc

theorem satisfies_cons (α : Assignment) (c : Clause) (φ : Formula) :
    Satisfies α (c :: φ) ↔ satisfiesClause α c = true ∧ Satisfies α φ := by
  simp [Satisfies]

theorem satisfies_append (α : Assignment) (φ ψ : Formula) :
    Satisfies α (φ ++ ψ) ↔ Satisfies α φ ∧ Satisfies α ψ := by
  simp [Satisfies, or_imp, forall_and]

@[simp] theorem satisfiesClause_nil (α : Assignment) : satisfiesClause α [] = false := rfl

theorem satisfiesClause_cons (α : Assignment) (x : Literal) (c : Clause) :
    satisfiesClause α (x :: c) = (satisfiesLiteral α x || satisfiesClause α c) := by
  simp [satisfiesClause]

theorem satisfiesLiteral_negate (α : Assignment) (x : Literal) :
    satisfiesLiteral α x.negate = !satisfiesLiteral α x := by
  cases x <;> simp [satisfiesLiteral, Literal.negate]

/-- The empty formula is satisfiable. -/
theorem satisfiable_nil : Satisfiable [] :=
  ⟨fun _ => true, satisfies_nil _⟩

/-- A formula containing the empty clause is unsatisfiable. -/
theorem not_satisfiable_of_nil_mem {φ : Formula} (h : [] ∈ φ) : ¬ Satisfiable φ := by
  rintro ⟨α, hα⟩
  have := hα [] h
  simp at this

/-- Removing clauses preserves satisfaction. -/
theorem satisfies_of_subset {α : Assignment} {φ ψ : Formula} (hsub : ∀ c ∈ ψ, c ∈ φ)
    (h : Satisfies α φ) : Satisfies α ψ :=
  fun c hc => h c (hsub c hc)

theorem satisfiable_of_subset {φ ψ : Formula} (hsub : ∀ c ∈ ψ, c ∈ φ)
    (h : Satisfiable φ) : Satisfiable ψ := by
  obtain ⟨α, hα⟩ := h
  exact ⟨α, satisfies_of_subset hsub hα⟩

/-! ## Variables -/

theorem var_mem_variables {φ : Formula} {c : Clause} {x : Literal}
    (hc : c ∈ φ) (hx : x ∈ c) : variables φ x.var := by
  exact ⟨c, hc, by cases x with | Neg n => exact Or.inl hx | Pos n => exact Or.inr hx⟩

theorem satisfiesLiteral_congr {α β : Assignment} {x : Literal} (h : α x.var = β x.var) :
    satisfiesLiteral α x = satisfiesLiteral β x := by
  cases x <;> simp [satisfiesLiteral, Literal.var] at h ⊢ <;> rw [h]

theorem satisfiesClause_congr {α β : Assignment} {c : Clause}
    (h : ∀ x ∈ c, α x.var = β x.var) :
    satisfiesClause α c = satisfiesClause β c := by
  induction c with
  | nil => rfl
  | cons x c ih =>
    rw [satisfiesClause_cons, satisfiesClause_cons,
      satisfiesLiteral_congr (h x (by simp)),
      ih (fun y hy => h y (by simp [hy]))]

/-- Satisfaction of a formula only depends on the assignment's values on the
formula's variables. -/
theorem satisfies_congr {α β : Assignment} {φ : Formula}
    (h : ∀ n, variables φ n → α n = β n) : Satisfies α φ ↔ Satisfies β φ := by
  have key : ∀ c ∈ φ, satisfiesClause α c = satisfiesClause β c := fun c hc =>
    satisfiesClause_congr fun x hx => h x.var (var_mem_variables hc hx)
  constructor
  · intro hα c hc; rw [← key c hc]; exact hα c hc
  · intro hβ c hc; rw [key c hc]; exact hβ c hc

theorem mem_variablesList_iff (φ : Formula) (n : Nat) :
    n ∈ variablesList φ ↔ ∃ c ∈ φ, ∃ x ∈ c, x.var = n := by
  induction φ with
  | nil => simp [variablesList]
  | cons c φ ih =>
    simp only [variablesList, List.foldr_cons, List.mem_append, List.mem_map]
    change (∃ x ∈ c, x.var = n) ∨ n ∈ variablesList φ ↔ ∃ c' ∈ c :: φ, ∃ x ∈ c', x.var = n
    rw [ih]
    constructor
    · rintro (⟨x, hx, rfl⟩ | ⟨c', hc', x, hx, rfl⟩)
      · exact ⟨c, List.mem_cons_self, x, hx, rfl⟩
      · exact ⟨c', List.mem_cons_of_mem _ hc', x, hx, rfl⟩
    · rintro ⟨c', hc', x, hx, rfl⟩
      cases List.mem_cons.mp hc' with
      | inl hhead =>
        subst hhead
        left
        exact ⟨x, hx, rfl⟩
      | inr htail =>
        right
        exact ⟨c', htail, x, hx, rfl⟩

/-- The set of variables of a formula is finite. -/
theorem variables_finite (φ : Formula) : ∃ (L : List Nat), ∀ n, variables φ n ↔ n ∈ L := by
  refine ⟨variablesList φ, ?_⟩
  intro n
  constructor
  · rintro ⟨c, hc, hx | hx⟩
    · rw [mem_variablesList_iff]
      exact ⟨c, hc, Literal.Neg n, hx, rfl⟩
    · rw [mem_variablesList_iff]
      exact ⟨c, hc, Literal.Pos n, hx, rfl⟩
  · intro hn
    rw [mem_variablesList_iff] at hn
    rcases hn with ⟨c, hc, x, hx, rfl⟩
    cases x with
    | Neg m => exact ⟨c, hc, Or.inl hx⟩
    | Pos m => exact ⟨c, hc, Or.inr hx⟩

def listBound : List Nat → Nat
  | [] => 0
  | a :: bs => max (a + 1) (listBound bs)

theorem le_listBound {L : List Nat} {n : Nat} (h : n ∈ L) : n < listBound L := by
  induction L with
  | nil => contradiction
  | cons a bs ih =>
    cases h with
    | head =>
      dsimp [listBound]
      omega
    | tail _ h' =>
      dsimp [listBound]
      have := ih h'
      omega

/-- Every variable of a formula is bounded by the numeric encoding of the
formula (used later for bounding the size of assignments). -/
theorem variables_bounded (φ : Formula) : ∃ N, ∀ n, variables φ n → n < N := by
  obtain ⟨L, hL⟩ := variables_finite φ
  refine ⟨listBound L, ?_⟩
  intro n hn
  rw [hL] at hn
  exact le_listBound hn

/-! ## Bounding variable indices by the length of the encoding

The SAT verifier of `CookLevinLean.Theorem` accepts only certificates of
length at most `|x|`.  For that bound to be attainable we must know that every
variable index occurring in `φ` is smaller than `|encodeFormula φ|`: the index
`n` is written out in *unary* inside the encoding, so it costs at least `2n+1`
bits there. -/

theorem le_length_encodeListNat {ns : List Nat} {m : Nat} (h : m ∈ ns) :
    m + 2 ≤ (encodeListNat ns).length := by
  induction ns with
  | nil => cases h
  | cons n ns ih =>
    have hlen : (encodeListNat (n :: ns)).length
        = 1 + (n + 1) + (encodeListNat ns).length := by
      simp [encodeListNat]
      omega
    cases h with
    | head => omega
    | tail _ h' => have := ih h'; omega

theorem le_length_encodeFormulaN {nss : List (List Nat)} {ns : List Nat} (h : ns ∈ nss) :
    (encodeListNat ns).length + 1 ≤ (encodeFormulaN nss).length := by
  induction nss with
  | nil => cases h
  | cons ms nss ih =>
    have hlen : (encodeFormulaN (ms :: nss)).length
        = 1 + (encodeListNat ms).length + (encodeFormulaN nss).length := by
      simp [encodeFormulaN]
      omega
    cases h with
    | head => omega
    | tail _ h' => have := ih h'; omega

/-- Every variable of `φ` has an index strictly below the length of the
encoding of `φ`. -/
theorem variables_lt_length_encodeFormula {φ : Formula} {n : Nat}
    (h : variables φ n) : n < (encodeFormula φ).length := by
  obtain ⟨c, hc, hlit⟩ := h
  -- the literal on `n` occurring in `c` encodes to a number `≥ 2 * n`
  obtain ⟨v, hv, hvn⟩ : ∃ v ∈ clauseN c, 2 * n ≤ v := by
    cases hlit with
    | inl hneg =>
      exact ⟨literalN (Literal.Neg n), List.mem_map_of_mem hneg, by simp [literalN]⟩
    | inr hpos =>
      exact ⟨literalN (Literal.Pos n), List.mem_map_of_mem hpos, by simp [literalN]⟩
  have h1 : v + 2 ≤ (encodeListNat (clauseN c)).length := le_length_encodeListNat hv
  have h2 : (encodeListNat (clauseN c)).length + 1 ≤ (encodeFormulaN (formulaN φ)).length :=
    le_length_encodeFormulaN (List.mem_map_of_mem hc)
  have h3 : (encodeFormula φ).length = (encodeFormulaN (formulaN φ)).length := rfl
  omega

/-- A bound on all variable indices of `φ`, computed from `φ` itself. -/
def assignmentBound (φ : Formula) : Nat := listBound (variablesList φ)

theorem lt_assignmentBound {φ : Formula} {n : Nat} (h : variables φ n) :
    n < assignmentBound φ := by
  obtain ⟨c, hc, hlit⟩ := h
  refine le_listBound ?_
  rw [mem_variablesList_iff]
  cases hlit with
  | inl hneg => exact ⟨c, hc, Literal.Neg n, hneg, rfl⟩
  | inr hpos => exact ⟨c, hc, Literal.Pos n, hpos, rfl⟩

theorem listBound_le {L : List Nat} {B : Nat} (h : ∀ n ∈ L, n < B) : listBound L ≤ B := by
  induction L with
  | nil => exact Nat.zero_le _
  | cons a bs ih =>
    have ha : a < B := h a List.mem_cons_self
    have hb : listBound bs ≤ B := ih fun n hn => h n (List.mem_cons_of_mem _ hn)
    dsimp [listBound]
    omega

theorem assignmentBound_le_length_encodeFormula (φ : Formula) :
    assignmentBound φ ≤ (encodeFormula φ).length := by
  refine listBound_le ?_
  intro n hn
  rw [mem_variablesList_iff] at hn
  obtain ⟨c, hc, x, hx, rfl⟩ := hn
  exact variables_lt_length_encodeFormula (var_mem_variables hc hx)

end CookLevin
Source
https://github.com/Rizvonium/cook_levin_lean_v1/blob/main/CookLevinLean/Satisfiability.lean
Human review
  • Endorsed by Community (Bot) · Oct 4, 2026

  • Endorsed by wurtle · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me