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
- 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 [∅]).
- resolution_refutation_pos_neg_exampleSanity check: the formula consisting of the clauses {x_0} and {not x_0} has the resolution refutation x_0, not x_0, empty clause, of…
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 ∅