Documentation

Provenance.Tseitin

Tseitin CNF encoding of Boolean circuits #

This file formalizes the Tseitin transformation, which encodes a Boolean circuit c : Circuit X as an equisatisfiable CNF over the extended variable set X ⊕ Circuit X. Each sub-circuit becomes an auxiliary variable, and the CNF clauses encode aux(g) ↔ <gate operation on aux variables of children>.

The transformation is purely structural and produces a CNF whose size is linear in the size of the circuit. It is the standard pre-processing step used before feeding a Boolean formula to a SAT solver or a knowledge compiler (c2d, d4, DSHARP); see Section V-D step 3 of Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data.

The main correctness result is Circuit.tseitin_equisat: a circuit is satisfiable iff its Tseitin CNF encoding is satisfiable. The proof is the explicit bijection between models of the circuit and models of the CNF: each valuation v : X → Bool lifts uniquely to a (X ⊕ Circuit X) → Bool that satisfies the CNF iff c.eval v = true, and any model of the CNF restricted to the original variables is a model of the circuit.

Main definitions #

Main results #

References #

structure Literal (X : Type) :

A literal: a variable together with a polarity flag. isPos = true means the positive literal var, isPos = false means the negative literal ¬var.

  • var : X

    The variable underlying the literal.

  • isPos : Bool

    Polarity: true for positive, false for negative.

Instances For
    Dependency graph
    @[instance_reducible]
    instance instReprLiteral {X✝ : Type} [Repr X✝] :
    Repr (Literal X✝)
    Equations
    Dependency graph
    def instReprLiteral.repr {X✝ : Type} [Repr X✝] :
    Literal X✝ → ℕ → Std.Format
    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      Dependency graph
      def Literal.eval {X : Type} (l : Literal X) (v : X → Bool) :

      Evaluate a literal under a valuation.

      Equations
      Instances For
        Dependency graph
        @[reducible, inline]
        abbrev Clause (X : Type) :

        A clause: a disjunction of literals, represented as a List. The empty clause is unsatisfiable.

        Equations
        Instances For
          Dependency graph
          def Clause.eval {X : Type} (c : Clause X) (v : X → Bool) :

          A clause is satisfied iff some literal in it evaluates to true.

          Equations
          Instances For
            Dependency graph
            @[reducible, inline]
            abbrev CNF (X : Type) :

            A CNF formula: a conjunction of clauses. The empty conjunction is satisfied vacuously (equal to true).

            Equations
            Instances For
              Dependency graph
              def CNF.eval {X : Type} (φ : CNF X) (v : X → Bool) :

              A CNF formula is satisfied iff every clause is satisfied.

              Equations
              Instances For
                Dependency graph
                def CNF.toBoolFunc {X : Type} (φ : CNF X) :

                The Boolean function denoted by a CNF formula.

                Equations
                Instances For
                  Dependency graph

                  Per-gate Tseitin clauses encoding aux(c) ↔ <gate operation on aux of children>. Does not recurse into sub-circuits – see Circuit.tseitinClauses for the full recursive collection.

                  Equations
                  Instances For
                    Dependency graph

                    The full recursive Tseitin clause set: per-gate clauses for the current node, plus all the clauses for its sub-circuits.

                    Equations
                    Instances For
                      Dependency graph
                      def Circuit.tseitin {X : Type} (c : Circuit X) :

                      The Tseitin CNF encoding: a unit clause asserting that the root's aux variable is true, followed by all per-gate sub-circuit clauses.

                      Equations
                      Instances For
                        Dependency graph
                        def Circuit.tseitinValuation {X : Type} (v : X → Bool) :
                        X ⊕ Circuit X → Bool

                        The canonical lift of an original-variable valuation v : X → Bool to the Tseitin variable space X ⊕ Circuit X: original variables map to their v-value, aux variables map to the corresponding sub-circuit's evaluation under v.

                        Equations
                        Instances For
                          Dependency graph

                          Forward direction: every model of the circuit lifts to a model of #

                          the Tseitin CNF.

                          The Tseitin CNF evaluates under the lifted valuation to exactly the circuit's truth value: the unit root clause [(aux(c), +)] is satisfied iff c.eval v = true, and all other clauses are tautologically satisfied under the lift.

                          Dependency graph

                          Backward direction: every model of the Tseitin CNF restricts to a #

                          model of the circuit.

                          theorem Circuit.tseitin_models_restrict {X : Type} (c : Circuit X) (w : X ⊕ Circuit X → Bool) (hw : c.tseitin.eval w = true) :
                          (c.eval fun (x : X) => w (Sum.inl x)) = true

                          Any model w of the full Tseitin CNF c.tseitin restricts (via Sum.inl) to a model of the original circuit c. The root unit clause forces w (Sum.inr c) = true, and the gate clauses force this to equal c.eval (w ∘ Sum.inl) via tseitinClauses_imp_root.

                          Dependency graph

                          Equisatisfiability #

                          theorem Circuit.tseitin_equisat {X : Type} (c : Circuit X) :
                          (∃ (v : X → Bool), c.eval v = true) ↔ ∃ (w : X ⊕ Circuit X → Bool), c.tseitin.eval w = true

                          Tseitin equisatisfiability. A Boolean circuit c : Circuit X is satisfiable iff its Tseitin CNF encoding c.tseitin : CNF (X ⊕ Circuit X) is satisfiable. The forward direction lifts a circuit-satisfying valuation v via tseitinValuation v; the backward direction restricts a CNF-satisfying valuation w via Sum.inl.

                          Dependency graph