AFTD Auto-Formalizing Theoretical Domains

is_resolution_refutation_mono

theoremverified

Monotonicity of resolution refutations: if F1 is a subset of F2, any resolution refutation of F1 is also a resolution refutation of F2 of identical length.

Statement

theorem is_resolution_refutation_mono {V : Type*} (F₁ F₂ : Finset (Finset (CnfLit V))) (π : List (Finset (CnfLit V))) (hsub : F₁ ⊆ F₂) (href : is_resolution_refutation F₁ π) : is_resolution_refutation F₂ π
Source
step towards resolution_fpt_incidence_treewidth
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • 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.

The proof, explained

A resolution refutation is a derivation of clauses whose final clause is the empty clause. Because the sequence π is unchanged, its final clause is still empty. For each clause π[i] in the derivation, if it is an axiom from F₁, the hypothesis F₁ ⊆ F₂ ensures it is also an axiom of F₂; if it is justified by weakening or resolution, the inference references only earlier clauses in π and therefore remains valid.

  1. To show that π is a resolution refutation of F₂, it suffices to show that π is a resolution derivation from F₂.

    A resolution refutation of F₁ consists of a derivation from F₁ together with the condition that the last clause of π is the empty clause ∅. Since the sequence π itself is unchanged, its last clause remains ∅, reducing the goal to verifying that π is a valid derivation from F₂.

    lines 3–4

      rcases href with ⟨hder, hlast⟩
      refine ⟨?_, hlast⟩
  2. Every step π[i] in π was justified in F₁ as an axiom, by weakening, or by resolution.

    Consider an arbitrary index i in π. By the definition of a resolution derivation from F₁, the clause π[i] satisfies one of three cases: it is an initial clause π[i] ∈ F₁, it weakens an earlier clause π[j] with j < i, or it is the resolvent of two earlier clauses π[j] and π[k] with j, k < i.

    lines 5–6

      intro i
      rcases hder i with h1 | h2 | h3
  3. If π[i] is an axiom of F₁, it is also an axiom of F₂.

    By the hypothesis F₁ ⊆ F₂, any clause π[i] ∈ F₁ also belongs to F₂.

    lines 7–8

      · left
        exact hsub h1
  4. If π[i] was derived by weakening an earlier clause, the step remains valid for F₂.

    The weakening condition requires some earlier clause π[j] (j < i) with π[j] ⊆ π[i]. This depends only on the sequence π and not on the ambient set of clauses, so the existing witness remains valid.

    lines 9–10

      · right; left
        exact h2
  5. If π[i] was derived by resolution, the step remains valid for F₂.

    The resolution condition asserts that π[i] resolves two earlier clauses π[j] and π[k] (j, k < i). This depends entirely on clauses within π, so the inference remains valid for F₂.

    lines 11–12

      · right; right
        exact h3

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Monotonicity of resolution refutations under clause addition. -/theorem is_resolution_refutation_mono {V : Type*} (F₁ F₂ : Finset (Finset (CnfLit V))) (π : List (Finset (CnfLit V))) (hsub : F₁ ⊆ F₂) (href : is_resolution_refutation F₁ π) : is_resolution_refutation F₂ π := by  rcases href with ⟨hder, hlast⟩  refine ⟨?_, hlast⟩  intro i  rcases hder i with h1 | h2 | h3  · left    exact hsub h1  · right; left    exact h2  · right; right    exact h3
See it in the graphDiscuss this resultChallenge it