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))