While this submission is a draft, it cannot be used by other submissions.

The Satisfiability Criterion for 2-CNF Formulas

Lax117284.TwoSatCriterion · concepts/Lax117284/TwoSatCriterion.lean · lax-117284

proven

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

    Lemma

    A 2-CNF formula is satisfiable exactly when it has no empty clause and no variable is contradictory in its implication graph: no variable xx with a path from xx to ¬x\lnot x and a path from ¬x\lnot x to xx. This is the criterion of Aspvall, Plass and Tarjan, on which every polynomial-time algorithm for 2-SAT rests.

    Concept map
    8 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax117284.TwoSatImplicationGraph
    2
    3/-!
    4---
    5title: The Satisfiability Criterion for 2-CNF Formulas
    6type: lemma
    7---
    8A 2-CNF formula is satisfiable exactly when it has no empty clause and no variable is
    9contradictory in its implication graph: no variable xx with a path from xx to ¬x\lnot x and a
    10path from ¬x\lnot x to xx. This is the criterion of Aspvall, Plass and Tarjan, on which every
    11polynomial-time algorithm for 2-SAT rests.
    12
    13# Formalization Notes
    14
    15The direction from a satisfying assignment is by induction along the paths: an edge preserves
    16truth, so a true literal reaches only true literals, and a variable cannot be true together with
    17its negation. The other direction builds an assignment. The graph is skew-symmetric — an edge
    18a→ba \to b gives an edge ¬b→¬a\lnot b \to \lnot a — and so a set of literals closed under successors
    19that never contains a literal together with its negation can be extended by any variable not yet
    20decided: one of its two literals does not reach its own negation, and that literal together with
    21everything it reaches joins the set consistently. When every variable is decided the set is a
    22satisfying assignment.
    23
    24The empty clause is stated separately because it has no literal and so no edge; the criterion
    25about paths says nothing about it.
    26-/
    27
    28namespace Lax117284.TwoSatCriterion
    29
    30open Lax429075.CNF Lax117284.TwoSatCNF Lax117284.TwoSatImplicationGraph
    31
    32/-- **The criterion of Aspvall, Plass and Tarjan.** -/
    33axiom satisfiable_iff (F : Formula) (h : IsTwoCNF F) :
    34 Satisfiable F ↔ [] ∉ F ∧ ∀ x : ℕ, ¬ Contradictory F x
    35
    36end Lax117284.TwoSatCriterion
    37
    Show Proof
    Formalization Notes

    The direction from a satisfying assignment is by induction along the paths: an edge preserves truth, so a true literal reaches only true literals, and a variable cannot be true together with its negation. The other direction builds an assignment. The graph is skew-symmetric — an edge a→ba \to b gives an edge ¬b→¬a\lnot b \to \lnot a — and so a set of literals closed under successors that never contains a literal together with its negation can be extended by any variable not yet decided: one of its two literals does not reach its own negation, and that literal together with everything it reaches joins the set consistently. When every variable is decided the set is a satisfying assignment.

    The empty clause is stated separately because it has no literal and so no edge; the criterion about paths says nothing about it.

    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…