`evalCNF`

definition

show as: view math explainer →

module: IndisputableMonolith.Complexity.SAT.CNF
domain: Complexity
line: 37 · github
papers citing: none yet

open explainer

Generate a durable explainer page for this declaration.

open lean source

IndisputableMonolith.Complexity.SAT.CNF on GitHub at line 37.

browse module

All declarations in this module, on Recognition.

explainer page

Tracked in the explainer inventory; generation is lazy so crawlers do not trigger LLM jobs.

open explainer

depends on

used by

formal source

  34  C.any (fun l => evalLit a l)
  35
  36/-- Evaluate a CNF (AND over its clauses). Empty CNF = true. -/
  37def evalCNF {n} (a : Assignment n) (φ : CNF n) : Bool :=
  38  φ.clauses.all (fun C => evalClause a C)
  39
  40/-- Satisfiable CNF. -/
  41def Satisfiable {n} (φ : CNF n) : Prop :=
  42  ∃ a : Assignment n, evalCNF a φ = true
  43
  44/-- Uniquely satisfiable CNF. -/
  45def UniqueSolution {n} (φ : CNF n) : Prop :=
  46  ∃! (a : Assignment n), evalCNF a φ = true
  47
  48end SAT
  49end Complexity
  50end IndisputableMonolith

papers checked against this theorem

No papers in the current corpus map onto this theorem yet.