resolution_refutation_of_pos_neg
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$.
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$.
refine ⟨[{CnfLit.pos x}, {CnfLit.neg x}, ∅], ⟨?_, rfl⟩, by simp⟩
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$.
intro i fin_cases iThe 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.
uses
Or.inl· exact Or.inl hposThe 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.
uses
Or.inl· exact Or.inl hnegThe 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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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