AFTD Auto-Formalizing Theoretical Domains

is_resolution_derivation

def

A resolution derivation from a CNF formula F (a finite set of clauses, each a finite set of literals) is a sequence of clauses C_1, ..., C_s in which each C_i is in F, or is a weakening C_i = C_j or E (C_j a subset of C_i) of an earlier clause, or is the resolvent C or D of earlier clauses C_j = C or x and C_k = D or not x.

Statement

def is_resolution_derivation {V : Type*} (F : Finset (Finset (CnfLit V))) (π : List (Finset (CnfLit V))) : Prop
Defined in
Short Resolution Refutations for CNFs with Bounded Weighted Incidence Treewidth, arXiv:2610.02047, Sec. 3.1 (resolution derivations with weakening; standard textbook notion in proof complexity)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
Used by 5
  • resolution_refutation_of_pos_negBase case for unit contradiction: a formula containing complementary unit clauses {x} and {not x} admits a resolution refutation of length…
  • is_resolution_refutation_monoMonotonicity of resolution refutations: if F1 is a subset of F2, any resolution refutation of F1 is also a resolution refutation of F2 of…
  • resolution_refutation_exists_of_unsatCompleteness of resolution, the length-free part of the problem: every unsatisfiable CNF formula has a resolution refutation.
  • resolution_refutation_of_empty_memBase case: if a formula contains the empty clause, it admits a resolution refutation of length 1 (namely [∅]).
  • is_resolution_refutationA resolution refutation of F is a resolution derivation from F whose last clause is the empty clause; its length is the number of clauses…

Lean source view module on GitHub

/-- A resolution derivation from F: a sequence of clauses each of which is in F, or a weakening of an earlier clause, or the resolvent of two earlier clauses. -/
def is_resolution_derivation {V : Type*} (F : Finset (Finset (CnfLit V))) (π : List (Finset (CnfLit V))) : Prop :=
  ∀ i : Fin π.length,
    π[i] ∈ F ∨
    (∃ j : Fin π.length, j < i ∧ π[j] ⊆ π[i]) ∨
    (∃ j k : Fin π.length, j < i ∧ k < i ∧ ∃ (x : V) (C D : Finset (CnfLit V)),
      (∀ l, l ∈ π[j] ↔ l ∈ C ∨ l = CnfLit.pos x) ∧ (∀ l, l ∈ π[k] ↔ l ∈ D ∨ l = CnfLit.neg x) ∧
      (∀ l, l ∈ π[i] ↔ l ∈ C ∨ l ∈ D))
See it in the graphDiscuss this resultChallenge it