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 #
Literal X,Clause X,CNF X– syntactic CNF infrastructure withevalsemantics.Circuit.gateClauses– per-gate Tseitin clauses encodingaux(c) ↔ ...(no recursion into sub-circuits).Circuit.tseitinClauses– the full recursive clause set covering every sub-circuit.Circuit.tseitin– the Tseitin CNF: gate clauses plus a unit clause asserting that the root's aux variable istrue.Circuit.tseitinValuation– the canonical lift of a valuationv : X → Boolto(X ⊕ Circuit X) → Bool(aux variables receive their sub-circuit's evaluation underv).
Main results #
Circuit.tseitin_eval_tseitinValuation–CNF.eval c.tseitin (tseitinValuation v) = c.eval v: the lifted valuation always satisfies the per-gate clauses, and the root assertion exactly tracks the circuit's truth value.Circuit.tseitin_models_restrict– any modelwofc.tseitinrestricts (viaSum.inl) to a model ofc.Circuit.tseitin_equisat– the bidirectional equisatisfiability theorem.
References #
- Sen, Maniu & Senellart (Section V-D step 3)
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:
truefor positive,falsefor negative.
Instances For
Dependency graph
Equations
- instReprLiteral = { reprPrec := instReprLiteral.repr }
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Evaluate a literal under a valuation.
Instances For
Dependency graph
A clause: a disjunction of literals, represented as a List. The
empty clause is unsatisfiable.
Instances For
Dependency graph
A clause is satisfied iff some literal in it evaluates to true.
Instances For
Dependency graph
A CNF formula: a conjunction of clauses. The empty conjunction is
satisfied vacuously (equal to true).
Instances For
Dependency graph
A CNF formula is satisfied iff every clause is satisfied.
Instances For
Dependency graph
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
- One or more equations did not get rendered due to their size.
- (Circuit.const true).gateClauses = [[{ var := Sum.inr (Circuit.const true), isPos := true }]]
- (Circuit.const false).gateClauses = [[{ var := Sum.inr (Circuit.const false), isPos := false }]]
- c'.not.gateClauses = [[{ var := Sum.inr c'.not, isPos := false }, { var := Sum.inr c', isPos := false }], [{ var := Sum.inr c'.not, isPos := true }, { var := Sum.inr c', isPos := true }]]
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
- (Circuit.const b).tseitinClauses = (Circuit.const b).gateClauses
- (Circuit.var x_1).tseitinClauses = (Circuit.var x_1).gateClauses
- c'.not.tseitinClauses = c'.not.gateClauses ++ c'.tseitinClauses
- (c₁.and c₂).tseitinClauses = (c₁.and c₂).gateClauses ++ c₁.tseitinClauses ++ c₂.tseitinClauses
- (c₁.or c₂).tseitinClauses = (c₁.or c₂).gateClauses ++ c₁.tseitinClauses ++ c₂.tseitinClauses
Instances For
Dependency graph
The Tseitin CNF encoding: a unit clause asserting that the root's
aux variable is true, followed by all per-gate sub-circuit clauses.
Instances For
Dependency graph
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
- Circuit.tseitinValuation v (Sum.inl x_1) = v x_1
- Circuit.tseitinValuation v (Sum.inr c) = c.eval v
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.
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 #
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.