`Var`

definition

show as: view math explainer →

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

open explainer

Read the cached plain-language explainer.

open lean source

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

browse module

All declarations in this module, on Recognition.

explainer page

A cached Ask Recognition explainer exists for this declaration.

open explainer

used by

formal source

   5namespace SAT
   6
   7/-- Variable indices are `Fin n` for a given problem size. -/
   8abbrev Var (n : Nat) := Fin n
   9
  10/-- Literals over `n` variables. -/
  11inductive Lit (n : Nat) where
  12  | pos (v : Var n) : Lit n
  13  | neg (v : Var n) : Lit n
  14deriving DecidableEq, Repr
  15
  16/-- A clause is a disjunction of literals. -/
  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)

papers checked against this theorem

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