Satisfiability of CNF formulas of width two

Lax485149.TwoSat · concepts/Lax485149/TwoSat.lean · lax-485149

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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 cc is a pair (x,s)(x, s) of a variable and a sign such that xx occurs in cc with sign ss. 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
    4 concepts; 21 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.ModelTheory.Semantics
    2import Lax904597.Problems
    3import Lax904597.Sat
    4import Lax485149.Problems
    5
    6/-!
    7---
    8title: Satisfiability of CNF formulas of width two
    9type: definition
    10---
    11An instance is a CNF instance of the NP core: a structure whose elements
    12are clauses and variables, with the positive and negative occurrences of
    13variables in clauses. A literal occurrence of a clause cc is a pair (x,s)(x, s)
    14of a variable and a sign such that xx occurs in cc with sign ss. The
    15instance has width at most two when no clause has three distinct literal
    16occurrences, and it is a yes-instance of 2SAT when it has width at most two
    17and is satisfiable. 2SAT is the decision problem of the structures
    18isomorphic to such an instance. Instances of larger width are no-instances:
    19the width bound is part of the problem, not a promise.
    20-/
    21
    22namespace Lax485149.TwoSat
    23
    24open FirstOrder FirstOrder.Language FirstOrder.Language.Structure
    25open Lax904597.Problems Lax904597.Sat Lax485149.Problems
    26
    27namespace SatOcc
    28
    29variable {A : Type} [sat.Structure A]
    30
    31/-- `c` is a clause. -/
    32def IsCl (c : A) : Prop := RelMap satIsClause ![c]
    33
    34/-- `x` occurs positively in `c`. -/
    35def PosIn (c x : A) : Prop := RelMap satPosIn ![c, x]
    36
    37/-- `x` occurs negatively in `c`. -/
    38def 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
    41occurrence). Occurrences are restricted to actual clauses. -/
    42def OccIn (c x : A) (s : Bool) : Prop := IsCl c ∧ if s then PosIn c x else NegIn c x
    43
    44end SatOcc
    45
    46/-- Every clause has at most two literal occurrences: among any three
    47occurrences of a clause, two coincide (as signed occurrences). -/
    48def 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
    53literal occurrences and the CNF is satisfiable. -/
    54def 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? -/
    58def TwoSAT : DecisionProblem sat := DecisionProblem.ofPred fun A _ => TwoSatisfiable A
    59
    60end Lax485149.TwoSat
    61

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…