AFTD Auto-Formalizing Theoretical Domains

resolution_refutation_pos_neg_example

theoremverified

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

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$.

  1. 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.

    line 2

      refine ⟨?_, rfl⟩
  2. 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$).

    lines 3–4

      intro i
      fin_cases i
  3. The 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`).

    line 5

    uses Finset.mem_cons

      · exact Or.inl (by simp [Finset.mem_cons])
  4. 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`).

    line 6

    uses Finset.mem_cons

      · exact Or.inl (by simp [Finset.mem_cons])
  5. 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.

    line 7

    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}$.

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

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
See it in the graphDiscuss this resultChallenge it