cnf_not_satisfiable_of_has_empty_clause
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.
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 τ.
rintro ⟨τ, hτ⟩
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.
uses
List.not_mem_nilobtain ⟨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
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.
/-- 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