IndisputableMonolith.Complexity.SAT.CNF

   1import Mathlib
   2
   3namespace IndisputableMonolith
   4namespace Complexity
   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)
  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
  51