resolution_refutation_pos_neg_example
Sanity 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 length 3.
Statement
theorem resolution_refutation_pos_neg_example : is_resolution_refutation (Finset.cons ({CnfLit.pos 0} : Finset (CnfLit ℕ)) {{CnfLit.neg 0}} (by simp)) [{CnfLit.pos 0}, {CnfLit.neg 0}, ∅]
- Source
- sanity check of the definition is_resolution_refutation (arXiv:2610.02047 Sec. 3.1)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
- Used by 5
- TensorSpecies.Tensor.IsReindexing.succAbove_succSuccAbove_commRemoving one entry and then a pair of entries from
cin either order gives the same colour list: removing thek-th entry and then the… - TensorSpecies.Tensor.IsReindexing.append_succAbove_castAddTensorSpecies.Tensor.IsReindexing.append_succAbove_castAdd
- Fin.succSuccAbove_succAbove_comm_applyPointwise form of commuting deletion of one slot with deletion of a pair.
- Physlib.List.insertIdx_getElem_finPhyslib.List.insertIdx_getElem_fin
- TensorSpecies.Tensor.IsReindexing.append_succAbove_natAddTensorSpecies.Tensor.IsReindexing.append_succAbove_natAdd
- TensorSpecies.Tensor.IsReindexing.succAbove_succSuccAbove_commRemoving one entry and then a pair of entries from
The proof, explained
To verify that $[\{x_0\}, \{\neg x_0\}, \emptyset]$ is a resolution refutation of the formula $\{\{x_0\}, \{\neg x_0\}\}$, we check that the derivation ends in the empty clause and that every clause in the sequence is legally derived. The first condition holds immediately by definition because the final entry is $\emptyset$. For the second condition, we inspect each index: the first two clauses $\{x_0\}$ and $\{\neg x_0\}$ are axioms present in the input formula, and the final clause $\emptyset$ is obtained by resolving the first two clauses on the variable $0$.
The refutation requirement reduces to showing that the list of clauses is a valid resolution derivation.
A resolution refutation is defined as a resolution derivation whose final clause is the empty clause $\emptyset$. Since the last element of the list $[\{x_0\}, \{\neg x_0\}, \emptyset]$ is syntactically $\emptyset$, the second conjunct holds by definition (`rfl`), leaving only the requirement to verify that the sequence of clauses forms a valid resolution derivation.
refine ⟨?_, rfl⟩
It suffices to verify the derivation condition for each of the three clause positions $0, 1, 2$.
A list of length 3 is a valid resolution derivation if every index $i \in \{0, 1, 2\}$ satisfies the derivation property. We introduce an arbitrary index $i : \mathrm{Fin}\; 3$ and exhaust all three possibilities ($i = 0$, $i = 1$, and $i = 2$).
intro i fin_cases iThe first clause $\{x_0\}$ is an initial clause from the input formula.
For $i = 0$, the clause is $\{x_0\}$. We take the first disjunct (`Or.inl`) of the derivation condition, which requires the clause to belong to the input formula $\{\{x_0\}, \{\neg x_0\}\}$. This membership holds directly by the definition of insertion into a finite set (`Finset.mem_cons`).
uses
Finset.mem_cons· exact Or.inl (by simp [Finset.mem_cons])
The second clause $\{\neg x_0\}$ is an initial clause from the input formula.
For $i = 1$, the clause is $\{\neg x_0\}$. As with the first clause, we select the axiom alternative (`Or.inl`), verifying that $\{\neg x_0\}$ belongs to the input formula $\{\{x_0\}, \{\neg x_0\}\}$ via finite set membership (`Finset.mem_cons`).
uses
Finset.mem_cons· exact Or.inl (by simp [Finset.mem_cons])
The third clause $\emptyset$ is derived by resolving the first two clauses on variable $0$.
For $i = 2$, the clause is $\emptyset$. We select the resolution rule (`Or.inr (Or.inr ...)`), specifying clause 0 ($\{x_0\}$) and clause 1 ($\{\neg x_0\}$) as the premises. Both indices precede 2, as confirmed by translating the ordering on $\mathrm{Fin}\; 3$ to natural numbers (`Fin.lt_def`). Choosing the pivot variable $0$ and empty residual clauses $C = \emptyset$ and $D = \emptyset$, the derivation condition reduces to the three set equalities $\{x_0\} = \emptyset \cup \{x_0\}$, $\{\neg x_0\} = \emptyset \cup \{\neg x_0\}$, and $\emptyset = \emptyset \cup \emptyset$, all of which are closed by simplification.
uses
Fin.lt_def· refine Or.inr (Or.inr ⟨⟨0, by simp⟩, ⟨1, by simp⟩, by simp [Fin.lt_def], by simp [Fin.lt_def], 0, ∅, ∅, ?_, ?_, ?_⟩) <;> intro l <;> simp
Finset.mem_cons- An element $a$ belongs to $\mathrm{cons}(b, s)$ if and only if $a = b$ or $a \in s$.
Fin.lt_def- For finite indices $a, b \in \mathrm{Fin}\; n$, the relation $a < b$ holds if and only if their underlying natural values satisfy $a.\mathrm{val} < b.\mathrm{val}$.
- In line 7, the tactic script provides explicit witnesses for the resolution rule (the premise indices 0 and 1, the resolved variable 0, and the empty residual clauses), while `<;> intro l <;> simp` dispatches the three resulting literal-level set equivalences by simplification.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). 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.
theorem resolution_refutation_pos_neg_example : is_resolution_refutation (Finset.cons ({CnfLit.pos 0} : Finset (CnfLit ℕ)) {{CnfLit.neg 0}} (by simp)) [{CnfLit.pos 0}, {CnfLit.neg 0}, ∅] := by refine ⟨?_, rfl⟩ intro i fin_cases i · exact Or.inl (by simp [Finset.mem_cons]) · exact Or.inl (by simp [Finset.mem_cons]) · refine Or.inr (Or.inr ⟨⟨0, by simp⟩, ⟨1, by simp⟩, by simp [Fin.lt_def], by simp [Fin.lt_def], 0, ∅, ∅, ?_, ?_, ?_⟩) <;> intro l <;> simp