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

Proof of `The Satisfiability Criterion for 2-CNF Formulas`

groundedproofs/Lax117284Proofs/TwoSAT/Bridge.lean · lax-117284

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The formula is read as occurrence functions, under which satisfiability is Sat2Sat2, edges are EdgeEdge and contradictory variables are ContraContra; the criterion is then Math.sat2iffnocontraMath.sat2_iff_no_contra, with the direction from a satisfying assignment holding for every variable by Math.notcontraofsatMath.not_contra_of_sat. A formula with an empty clause is unsatisfiable outright.