AFTD Auto-Formalizing Theoretical Domains

cnf_not_satisfiable_of_has_empty_clause

theoremverifiedformalization

A CNF formula containing the empty clause cannot be satisfied by any assignment because the empty clause contains no literals to be made true.

Statement

theorem cnf_not_satisfiable_of_has_empty_clause {V : Type*} (f : List (List (CnfLit V))) (h : [] ∈ f) : ¬ CnfSatisfiable f
Formalizes
standard textbook result (propositional logic: a CNF containing the empty clause is unsatisfiable)
Verified
06 Oct 2026
Axioms
none — Lean reports it depends on no axioms
Built on 2
  • CnfSatisfiableA CNF formula (a list of clauses, each a list of literals) is satisfiable if there is a truth assignment such that every clause contains…
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.

The proof, explained

The proof proceeds by contradiction, assuming that the CNF formula f admits a satisfying truth assignment τ. By the definition of satisfiability, every clause in f must contain at least one literal that is satisfied under τ. Since the empty clause is in f, it would have to contain such a literal, which contradicts the fact that the empty list has no elements.

  1. Assume for contradiction that f is satisfiable, with truth assignment τ

    To show that f is unsatisfiable (¬ CnfSatisfiable f), we assume for contradiction that there exists a satisfying assignment τ. Satisfiability provides the hypothesis that every clause in f contains at least one literal satisfied by τ.

    line 3

      rintro ⟨τ, hτ⟩
  2. A contradiction is derived from the requirement that the empty clause contains a literal

    Because the empty clause [] belongs to f by assumption h, the satisfiability condition requires that [] contains some literal l (that is, l ∈ []). But by List.not_mem_nil, the empty list contains no elements, which produces a contradiction.

    lines 4–5

    uses List.not_mem_nil

      obtain ⟨l, hl, -⟩ := hτ [] h
      exact List.not_mem_nil hl
List.not_mem_nil
No element belongs to the empty list: for any a, a ∉ []

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

/-- Any CNF formula containing an empty clause is unsatisfiable. -/theorem cnf_not_satisfiable_of_has_empty_clause {V : Type*} (f : List (List (CnfLit V))) (h : [] ∈ f) : ¬ CnfSatisfiable f := by  rintro ⟨τ, hτ⟩  obtain ⟨l, hl, -⟩ := hτ [] h  exact List.not_mem_nil hl
See it in the graphDiscuss this resultChallenge it