AFTD Auto-Formalizing Theoretical Domains

is_resolution_refutation

def

A resolution refutation of F is a resolution derivation from F whose last clause is the empty clause; its length is the number of clauses in the sequence.

Statement

def is_resolution_refutation {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 refutation and its length)
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • is_resolution_derivationA 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, ...,…
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
Used by 5

Lean source view module on GitHub

/-- A resolution refutation of F: a resolution derivation from F ending in the empty clause. -/
def is_resolution_refutation {V : Type*} (F : Finset (Finset (CnfLit V))) (π : List (Finset (CnfLit V))) : Prop :=
  is_resolution_derivation F π ∧ π.getLast? = some ∅
See it in the graphDiscuss this resultChallenge it