The Tseytin transformation, alternatively written Tseitin transformation, takes as input an arbitrary
combinatorial logic circuit and produces a
boolean formula in
conjunctive normal form (CNF), which can be solved by a
CNF-SAT
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies ...
solver. The length of the formula is linear in the size of the circuit. Input vectors that make the circuit output "true" are in
1-to-1 correspondence with assignments that satisfy the formula. This reduces the problem of
circuit satisfiability
In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output tru ...
on any circuit (including any formula) to the
satisfiability
In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...
problem on 3-CNF formulas.
Motivation
The naive approach is to write the circuit as a Boolean expression, and use
De Morgan's law
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...
and the
distributive property
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmetic, ...
to convert it to CNF. However, this can result in an exponential increase in equation size. The Tseytin transformation outputs a formula whose size grows linearly relative to the input circuit's.
Approach
The output equation is the constant 1 set equal to an expression. This expression is a conjunction of sub-expressions, where the satisfaction of each sub-expression enforces the proper operation of a single gate in the input circuit. The satisfaction of the entire output expression thus enforces that the entire input circuit is operating properly.
For each gate, a new variable representing its output is introduced. A small pre-calculated
CNF expression that relates the inputs and outputs is appended (via the "and" operation) to the output expression. Note that inputs to these gates can be either the original literals or the introduced variables representing outputs of sub-gates.
Though the output expression contains more variables than the input, it remains equisatisfiable, meaning that it is satisfiable if, and only if, the original input equation is satisfiable. When a satisfying assignment of variables is found, those assignments for the introduced variables can simply be discarded.
A final clause is appended with a single literal: the final gate's output variable. If this literal is complemented, then the satisfaction of this clause enforces the output expression's to false; otherwise the expression is forced true.
Examples
Consider the following formula
.
:
Consider all subformulas (excluding simple variables):
:
Introduce a new variable for each subformula:
:
Conjunct all substitutions and the substitution for
:
:
All substitutions can be transformed into CNF, e.g.
:
Gate Sub-expressions
Listed are some of the possible sub-expressions that can be created for various logic gates. In an operation expression, C acts as an output; in a CNF sub-expression, C acts as a new Boolean variable. For each operation, the CNF sub-expression is true if and only if C adheres to the contract of the Boolean operation for all possible input values.
Simple combinatorial logic
The following circuit returns true when at least some of its inputs are true, but not more than two at a time. It implements the equation . A variable is introduced for each gate's output; here each is marked in red:
![Comb logic tseitin](https://upload.wikimedia.org/wikipedia/commons/b/b8/Comb_logic_tseitin.svg)
Notice that the output of the inverter with x as an input has two variables introduced. While this is redundant, it does not affect the equisatisfiability of the resulting equation. Now substitute each gate with its appropriate
CNF sub-expression:
The final output variable is gate8 so to enforce that the output of this circuit be true, one final simple clause is appended:
(gate8). Combining these equations results in the final instance of SAT:
: (gate1 ∨ x1) ∧ ( ∨ ) ∧ ( ∨ gate1) ∧ ( ∨ x2) ∧
: ( ∨ gate2 ∨ ) ∧ (gate3 ∨ x2) ∧ ( ∨ ) ∧ ( ∨ x1) ∧
: ( ∨ gate3) ∧ ( ∨ gate4 ∨ ) ∧ (gate5 ∨ x2) ∧
: ( ∨ ) ∧ ( ∨ gate5) ∧ ( ∨ x3) ∧
: ( ∨ gate6 ∨ ) ∧ (gate7 ∨ ) ∧ (gate7 ∨ ) ∧
: (gate2 ∨ ∨ gate4) ∧ (gate8 ∨ ) ∧ (gate8 ∨ ) ∧
: (gate6 ∨ ∨ gate7) ∧ (gate8) = 1
One possible satisfying assignment of these variables is:
The values of the introduced variables are usually discarded, but they can be used to trace the logic path in the original circuit. Here,
indeed meets the criteria for the original circuit to output true. To find a different answer, the clause (x1 ∨ x2 ∨ ) can be appended and the SAT solver executed again.
Derivation
Presented is one possible derivation of the
CNF sub-expression for some chosen gates:
OR Gate
An OR gate with two inputs ''A'' and ''B'' and one output ''C'' is satisfies the following conditions:
# if the output ''C'' is true, then at least one of its inputs ''A'' or ''B'' is true,
# if the output ''C'' is false, then both its inputs ''A'' and ''B'' are false.
We can express these two conditions as the conjunction of two implications:
:
Replacing the implications with equivalent expressions involving only conjunctions, disjunctions, and negations yields
:
which is nearly in
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
already. Distributing the rightmost clause twice yields
:
and applying the associativity of conjunction gives the CNF formula
:
NOT Gate
The NOT gate is operating properly when its input and output oppose each other. That is:
# if the output C is true, the input A is false
# if the output C is false, the input A is true
express these conditions as an expression that must be satisfied:
:
NOR Gate
The NOR gate is operating properly when the following conditions hold:
# if the output C is true, then neither A or B are true
# if the output C is false, then at least one of A and B were true
express these conditions as an expression that must be satisfied:
:{{comma separated entries
,
,
,
,
,
References
*
G.S. Tseytin: On the complexity of derivation in propositional calculus. In: Slisenko, A.O. (ed.) Studies in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics, pp. 115–125. Steklov Mathematical Institute (1970). Translated from Russian: Zapiski Nauchnykh Seminarov LOMI 8 (1968), pp. 234–259.
G.S. Tseytin: On the complexity of derivation in propositional calculus. Presented at the Leningrad Seminar on Mathematical Logic held in September 1966.
Logic gates
Logic in computer science