AFTD Auto-Formalizing Theoretical Domains

resolution_refutation_of_pos_neg

theoremverified

Base case for unit contradiction: a formula containing complementary unit clauses {x} and {not x} admits a resolution refutation of length at most 3.

Statement

theorem resolution_refutation_of_pos_neg {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) (x : V) (hpos : {CnfLit.pos x} ∈ F) (hneg : {CnfLit.neg x} ∈ F) : ∃ π : List (Finset (CnfLit V)), is_resolution_refutation F π ∧ π.length ≤ 3
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…
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
  • 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, ...,…

The proof, explained

The proof explicitly constructs the three-step resolution refutation $\pi = [\{x\}, \{\neg x\}, \emptyset]$. It verifies that $\pi$ has length at most 3 and ends with the empty clause, and then checks each clause in turn: the unit clauses $\{x\}$ and $\{\neg x\}$ are initial axioms from the formula $F$, and the empty clause $\emptyset$ is derived from them by a single resolution step on the variable $x$.

  1. The candidate refutation $\pi = [\{x\}, \{\neg x\}, \emptyset]$ has length at most 3 and ends with the empty clause, reducing the goal to showing that $\pi$ is a valid resolution derivation.

    We provide the explicit list $\pi = [\{x\}, \{\neg x\}, \emptyset]$ as a witness for the existential quantifier. By definition, its last clause is $\emptyset$ (verified by reflexivity), and its length is 3, which is at most 3 (verified by simplification). This leaves the remaining obligation to verify that $\pi$ is a valid resolution derivation from $F$.

    line 3

      refine ⟨[{CnfLit.pos x}, {CnfLit.neg x}, ∅], ⟨?_, rfl⟩, by simp⟩
  2. It suffices to verify the derivation condition for each clause index $i \in \{0, 1, 2\}$ in $\pi$.

    We introduce an index $i$ into the list $\pi$. Because $\pi$ has length 3, a finite case analysis breaks the problem into three cases: $i = 0$, $i = 1$, and $i = 2$.

    lines 4–5

      intro i
      fin_cases i
  3. The first clause $\pi[0] = \{x\}$ is valid because it belongs to the formula $F$.

    The clause at index 0 is the positive unit clause $\{x\}$. By assumption $hpos$, this clause belongs to $F$, which satisfies the axiom alternative (the first disjunct) of the resolution derivation rule.

    line 6

    uses Or.inl

      · exact Or.inl hpos
  4. The second clause $\pi[1] = \{\neg x\}$ is valid because it belongs to the formula $F$.

    The clause at index 1 is the negative unit clause $\{\neg x\}$. By assumption $hneg$, this clause belongs to $F$, which also satisfies the axiom alternative of the resolution derivation rule.

    line 7

    uses Or.inl

      · exact Or.inl hneg
  5. The third clause $\pi[2] = \emptyset$ is valid because it is the resolvent of $\pi[0]$ and $\pi[1]$ on the variable $x$.

    The empty clause at index 2 is justified by the resolution alternative of the derivation rule. We choose the premise clauses at earlier indices $j = 0$ and $k = 1$ with pivot variable $x$ and empty remainder clauses $C = \emptyset$ and $D = \emptyset$. The index inequalities $0 < 2$ and $1 < 2$ hold by comparing their underlying natural numbers, and for any literal $l$, the set-theoretic conditions $l \in \{x\} \leftrightarrow l \in \emptyset \lor l = x$, $l \in \{\neg x\} \leftrightarrow l \in \emptyset \lor l = \neg x$, and $l \in \emptyset \leftrightarrow l \in \emptyset \lor l \in \emptyset$ are all solved by simplification.

    lines 8–9

    uses Or.inr, Fin.lt_def

      · refine Or.inr (Or.inr ⟨⟨0, by simp⟩, ⟨1, by simp⟩, by simp [Fin.lt_def],
          by simp [Fin.lt_def], x, ∅, ∅, ?_, ?_, ?_⟩) <;> intro l <;> simp
Or.inl
A proof of $a$ implies a proof of the disjunction $a \lor b$.
Or.inr
A proof of $b$ implies a proof of the disjunction $a \lor b$.
Fin.lt_def
The strict inequality $a < b$ between elements of $\mathrm{Fin}(n)$ is defined as the inequality $a < b$ between their underlying natural numbers.

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

/-- A formula containing complementary unit literals admits a resolution refutation of length at most 3. -/theorem resolution_refutation_of_pos_neg {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) (x : V) (hpos : {CnfLit.pos x} ∈ F) (hneg : {CnfLit.neg x} ∈ F) : ∃ π : List (Finset (CnfLit V)), is_resolution_refutation F π ∧ π.length ≤ 3 := by  refine ⟨[{CnfLit.pos x}, {CnfLit.neg x}, ∅], ⟨?_, rfl⟩, by simp⟩  intro i  fin_cases i  · exact Or.inl hpos  · exact Or.inl hneg  · refine Or.inr (Or.inr ⟨⟨0, by simp⟩, ⟨1, by simp⟩, by simp [Fin.lt_def],      by simp [Fin.lt_def], x, ∅, ∅, ?_, ?_, ?_⟩) <;> intro l <;> simp
See it in the graphDiscuss this resultChallenge it