Satisfiability of CNF formulas of width two
Lax485149.TwoSat · concepts/Lax485149/TwoSat.lean · lax-485149
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An instance is a CNF instance of the NP core: a structure whose elements are clauses and variables, with the positive and negative occurrences of variables in clauses. A literal occurrence of a clause is a pair of a variable and a sign such that occurs in with sign . The instance has width at most two when no clause has three distinct literal occurrences, and it is a yes-instance of 2SAT when it has width at most two and is satisfiable. 2SAT is the decision problem of the structures isomorphic to such an instance. Instances of larger width are no-instances: the width bound is part of the problem, not a promise.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.ModelTheory.Semantics |
| 2 | import Lax904597.Problems |
| 3 | import Lax904597.Sat |
| 4 | import Lax485149.Problems |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Satisfiability of CNF formulas of width two |
| 9 | type: definition |
| 10 | --- |
| 11 | An instance is a CNF instance of the NP core: a structure whose elements |
| 12 | are clauses and variables, with the positive and negative occurrences of |
| 13 | variables in clauses. A literal occurrence of a clause is a pair |
| 14 | of a variable and a sign such that occurs in with sign . The |
| 15 | instance has width at most two when no clause has three distinct literal |
| 16 | occurrences, and it is a yes-instance of 2SAT when it has width at most two |
| 17 | and is satisfiable. 2SAT is the decision problem of the structures |
| 18 | isomorphic to such an instance. Instances of larger width are no-instances: |
| 19 | the width bound is part of the problem, not a promise. |
| 20 | -/ |
| 21 | |
| 22 | namespace Lax485149.TwoSat |
| 23 | |
| 24 | open FirstOrder FirstOrder.Language FirstOrder.Language.Structure |
| 25 | open Lax904597.Problems Lax904597.Sat Lax485149.Problems |
| 26 | |
| 27 | namespace SatOcc |
| 28 | |
| 29 | variable {A : Type} [sat.Structure A] |
| 30 | |
| 31 | /-- `c` is a clause. -/ |
| 32 | def IsCl (c : A) : Prop := RelMap satIsClause ![c] |
| 33 | |
| 34 | /-- `x` occurs positively in `c`. -/ |
| 35 | def PosIn (c x : A) : Prop := RelMap satPosIn ![c, x] |
| 36 | |
| 37 | /-- `x` occurs negatively in `c`. -/ |
| 38 | def NegIn (c x : A) : Prop := RelMap satNegIn ![c, x] |
| 39 | |
| 40 | /-- The literal `(x, s)` occurs in the clause `c` (`s = true` for a positive |
| 41 | occurrence). Occurrences are restricted to actual clauses. -/ |
| 42 | def OccIn (c x : A) (s : Bool) : Prop := IsCl c ∧ if s then PosIn c x else NegIn c x |
| 43 | |
| 44 | end SatOcc |
| 45 | |
| 46 | /-- Every clause has at most two literal occurrences: among any three |
| 47 | occurrences of a clause, two coincide (as signed occurrences). -/ |
| 48 | def WidthAtMostTwo (A : Type) [sat.Structure A] : Prop := |
| 49 | ∀ (c : A) (x : Fin 3 → A) (s : Fin 3 → Bool), |
| 50 | (∀ i, SatOcc.OccIn c (x i) (s i)) → ∃ i j, i ≠ j ∧ x i = x j ∧ s i = s j |
| 51 | |
| 52 | /-- A CNF instance is a yes-instance of 2SAT if every clause has at most two |
| 53 | literal occurrences and the CNF is satisfiable. -/ |
| 54 | def TwoSatisfiable (A : Type) [sat.Structure A] : Prop := |
| 55 | WidthAtMostTwo A ∧ Satisfiable A |
| 56 | |
| 57 | /-- 2SAT: is the CNF instance of width at most two and satisfiable? -/ |
| 58 | def TwoSAT : DecisionProblem sat := DecisionProblem.ofPred fun A _ => TwoSatisfiable A |
| 59 | |
| 60 | end Lax485149.TwoSat |
| 61 |
Used by
Lax485149.DeterministicReachabilityInvarianceLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ReachabilityInvarianceLax485149.ReachdLCompleteLax485149.ReachNLCompleteLax485149.TransitiveClosureClosureLax485149.TwoSatInvarianceLax485149.TwoSatNLCompleteLax485149.UnreachdLCompleteLax485149.UnreachNLComplete
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments