CnfSatisfiable
def
A CNF formula (a list of clauses, each a list of literals) is satisfiable if there is a truth assignment such that every clause contains at least one true literal.
Statement
def CnfSatisfiable {V : Type*} (f : List (List (CnfLit V))) : Prop
- Defined in
- standard textbook definition (propositional logic: satisfiability of a CNF formula)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 1
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- Used by 7
- cnf_not_satisfiable_of_has_empty_clauseA CNF formula containing the empty clause cannot be satisfied by any assignment because the empty clause contains no literals to be made…
- cnf_satisfiable_append_sum_iffLet f be a CNF formula over a variable type V and g a CNF formula over a variable type W. Replace every literal of f by the literal of the…
- cnf_satisfiable_subsetIf every clause of a CNF formula
f1is contained in a CNF formulaf2(that is,f1 ⊆ f2), andf2is satisfiable (… - cnf_single_clause_satisfiable_iffA CNF formula consisting of a single clause
c, namely[c], is satisfiable (CnfSatisfiable [c]) if and only if the clausecis… - resolution_refutation_exists_of_unsatCompleteness of resolution, the length-free part of the problem: every unsatisfiable CNF formula has a resolution refutation.
- cnf_satisfiable_of_appendIf the concatenation
f1 ++ f2of two CNF formulas is satisfiable (CnfSatisfiable (f1 ++ f2)), then bothf1andf2are satisfiable… - cnf_empty_satisfiableThe empty CNF formula has no clauses to satisfy, hence is satisfiable under any truth assignment.
Lean source view module on GitHub
/-- A CNF formula is satisfiable if there exists a truth assignment satisfying at least one literal in each clause. -/ def CnfSatisfiable {V : Type*} (f : List (List (CnfLit V))) : Prop := ∃ τ : V → Bool, ∀ c ∈ f, ∃ l ∈ c, match l with | CnfLit.pos v => τ v = true | CnfLit.neg v => τ v = false