The Satisfiability Criterion for 2-CNF Formulas
Lax117284.TwoSatCriterion · concepts/Lax117284/TwoSatCriterion.lean · lax-117284
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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 with a path from to and a path from to . This is the criterion of Aspvall, Plass and Tarjan, on which every polynomial-time algorithm for 2-SAT rests.
Concept map
Lean source view on GitHub
| 1 | import Lax117284.TwoSatImplicationGraph |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The Satisfiability Criterion for 2-CNF Formulas |
| 6 | type: lemma |
| 7 | --- |
| 8 | A 2-CNF formula is satisfiable exactly when it has no empty clause and no variable is |
| 9 | contradictory in its implication graph: no variable with a path from to and a |
| 10 | path from to . This is the criterion of Aspvall, Plass and Tarjan, on which every |
| 11 | polynomial-time algorithm for 2-SAT rests. |
| 12 | |
| 13 | # Formalization Notes |
| 14 | |
| 15 | The direction from a satisfying assignment is by induction along the paths: an edge preserves |
| 16 | truth, so a true literal reaches only true literals, and a variable cannot be true together with |
| 17 | its negation. The other direction builds an assignment. The graph is skew-symmetric — an edge |
| 18 | gives an edge — and so a set of literals closed under successors |
| 19 | that never contains a literal together with its negation can be extended by any variable not yet |
| 20 | decided: one of its two literals does not reach its own negation, and that literal together with |
| 21 | everything it reaches joins the set consistently. When every variable is decided the set is a |
| 22 | satisfying assignment. |
| 23 | |
| 24 | The empty clause is stated separately because it has no literal and so no edge; the criterion |
| 25 | about paths says nothing about it. |
| 26 | -/ |
| 27 | |
| 28 | namespace Lax117284.TwoSatCriterion |
| 29 | |
| 30 | open Lax429075.CNF Lax117284.TwoSatCNF Lax117284.TwoSatImplicationGraph |
| 31 | |
| 32 | /-- **The criterion of Aspvall, Plass and Tarjan.** -/ |
| 33 | axiom satisfiable_iff (F : Formula) (h : IsTwoCNF F) : |
| 34 | Satisfiable F ↔ [] ∉ F ∧ ∀ x : ℕ, ¬ Contradictory F x |
| 35 | |
| 36 | end Lax117284.TwoSatCriterion |
| 37 |
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 gives an edge — 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.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments