`CNF`

definition

show as: view math explainer →

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

open explainer

Read the cached plain-language explainer.

open lean source

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

browse module

All declarations in this module, on Recognition.

explainer page

A cached Ask Recognition explainer exists for this declaration.

open explainer

depends on

used by

formal source

  17abbrev Clause (n : Nat) := List (Lit n)
  18
  19/-- CNF: conjunction of clauses, parameterized by number of variables. -/
  20structure CNF (n : Nat) where
  21  clauses : List (Clause n)
  22deriving Repr
  23
  24/-- Total assignments for `n` variables. -/
  25abbrev Assignment (n : Nat) := Var n → Bool
  26
  27/-- Evaluate a literal under an assignment. -/
  28def evalLit {n} (a : Assignment n) : Lit n → Bool
  29  | .pos v => a v
  30  | .neg v => ! (a v)
  31
  32/-- Evaluate a clause (OR over its literals). Empty clause = false. -/
  33def evalClause {n} (a : Assignment n) (C : Clause n) : Bool :=
  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.