Tseytin transformation

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 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 on any circuit (including any formula) to the satisfiability problem on 3-CNF formulas.

Motivation

The naive approach is to write the circuit as a Boolean expression, and use De Morgan's law and the distributive property to convert it to CNF. However, this can result in an exponential increase in equation size. The Tseytin transformation outputs a formula whose size has grown 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 $\phi$ .

\phi := ((p \lor q) \land r) \to (\neg s)

Consider all subformulas (without variables):

\begin{align} &\neg s\\ &p \lor q\\ &(p \lor q) \land r\\ &((p \lor q) \land r) \to (\neg s) \end{align}

Introduce a new variable for each subformula:

\begin{align} x_1 &\leftrightarrow \neg s\\ x_2 &\leftrightarrow p \lor q\\ x_3 &\leftrightarrow x_2 \land r\\ x_4 &\leftrightarrow x_3 \to x_1 \end{align}

Conjunct all substitutions and the substitution for $\phi$ :

T(\phi) := x_4 \land (x_4 \leftrightarrow x_3 \to x_1) \land (x_3 \leftrightarrow x_2 \land r) \land (x_2 \leftrightarrow p \lor q) \land (x_1 \leftrightarrow \neg s)

All substitutions can be transformed into CNF, e.g.

\begin{align} x_2 \leftrightarrow p \lor q &\equiv x_2 \to (p \lor q) \land ((p \lor q) \to x_2) \\ &\equiv (\neg x_2 \lor p \lor q) \land (\neg(p \lor q) \lor x_2) \\ &\equiv (\neg x_2 \lor p \lor q) \land ((\neg p \land \neg q) \lor x_2) \\ &\equiv (\neg x_2 \lor p \lor q) \land (\neg p \lor x_2) \land (\neg q \lor x_2) \end{align}

Gate Sub-expressions

Listed is 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.

Type	Operation	CNF Sub-expression
AND	$C = A \cdot B$	$(\overline{A} \vee \overline{B} \vee C) \wedge (A \vee \overline{C}) \wedge (B \vee \overline{C})$
NAND	$C = \overline{A \cdot B}$	$(\overline{A} \vee \overline{B} \vee \overline{C}) \wedge (A \vee C) \wedge (B \vee C)$
OR	$C = A+B$	$(A \vee B \vee \overline{C}) \wedge (\overline{A} \vee C) \wedge (\overline{B} \vee C)$
NOR	$C = \overline{A + B}$	$(A \vee B \vee C) \wedge (\overline{A} \vee \overline{C}) \wedge (\overline{B} \vee \overline{C})$
NOT	$C = \overline{A}$	$(\overline{A} \vee \overline{C}) \wedge (A \vee C)$
XOR	$C = A \oplus B$	$(\overline{A} \vee \overline{B} \vee \overline{C}) \wedge (A \vee B \vee \overline{C}) \wedge (A \vee \overline{B} \vee C) \wedge (\overline{A} \vee B \vee C)$

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 $y = \overline{x1}\cdot x2 + x1\cdot \overline{x2} + \overline{x2}\cdot x3$ . A variable is introduced for each gates' output; here each is marked in red:

Notice that the output of the inverter with $x_2$ 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:

gate	CNF sub-expression
$gate1$	$(gate1\vee x1)\wedge (\overline{gate1}\vee \overline{x1})$
$gate2$	$(\overline{gate2}\vee gate1)\wedge (\overline{gate2}\vee x2)\wedge (\overline{x2}\vee gate2\vee \overline{gate1})$
$gate3$	$(gate3\vee x2)\wedge (\overline{gate3}\vee \overline{x2})$
$gate4$	$(\overline{gate4}\vee x1)\wedge (\overline{gate4}\vee gate3)\wedge (\overline{gate3}\vee gate4\vee \overline{x1})$
$gate5$	$(gate5\vee x2)\wedge (\overline{gate5}\vee \overline{x2})$
$gate6$	$(\overline{gate6}\vee gate5)\wedge (\overline{gate6}\vee x3)\wedge (\overline{x3}\vee gate6\vee \overline{gate5})$
$gate7$	$(gate7\vee \overline{gate2})\wedge (gate7\vee \overline{gate4})\wedge (gate2\vee \overline{gate7}\vee gate4)$
$gate8$	$(gate8\vee \overline{gate6})\wedge (gate8\vee \overline{gate7})\wedge (gate6\vee \overline{gate8}\vee gate7)$

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\vee x1)\wedge (\overline{gate1}\vee \overline{x1})\wedge (\overline{gate2}\vee gate1)\wedge (\overline{gate2}\vee x2)\wedge$ $(\overline{x2}\vee gate2\vee \overline{gate1})\wedge (gate3\vee x2)\wedge (\overline{gate3}\vee \overline{x2})\wedge (\overline{gate4}\vee x1)\wedge$ $(\overline{gate4}\vee gate3)\wedge (\overline{gate3}\vee gate4\vee \overline{x1})\wedge (gate5\vee x2)\wedge$ $(\overline{gate5}\vee \overline{x2})\wedge (\overline{gate6}\vee gate5)\wedge (\overline{gate6}\vee x3)\wedge$ $(\overline{x3}\vee gate6\vee \overline{gate5})\wedge (gate7\vee \overline{gate2})\wedge (gate7\vee \overline{gate4})\wedge$ $(gate2\vee \overline{gate7}\vee gate4)\wedge (gate8\vee \overline{gate6})\wedge (gate8\vee \overline{gate7})\wedge$ $(gate6\vee \overline{gate8}\vee gate7)\wedge (gate8) = 1$

One possible satisfying assignment of these variables is:

variable	value
gate2	0
gate3	1
gate1	1
gate6	1
gate7	0
gate4	0
gate5	1
gate8	1
x2	0
x3	1
x1	0

The values of the introduced values are usually discarded, but they can be used to trace the logic path in the original circuit. Here, $(x1,x2,x3) = (0,0,1)$ indeed meets the criteria for the original circuit to output true. To find a different answer, the clause $(x1\vee x2\vee \overline{x3})$ 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

The OR gate is operating properly when the following conditions hold:

if the output C is true, then one (or both) of its inputs A, B is true
if the output C is false, then both its inputs A, B are false

express these conditions as an expression that must be satisfied:
$(C \rightarrow (A \vee B)) \wedge (\overline{C} \rightarrow (\overline{A} \wedge \overline{B}))$
convert the implications to AND's and OR's
$(\overline{C} \vee (A \vee B)) \wedge (C \vee (\overline{A} \wedge \overline{B}))$
it's nearly CNF already; distribute the rightmost clause twice
$(\overline{C} \vee A \vee B) \wedge ((C \vee \overline{A}) \wedge (C \vee \overline{B}))$
associativity of conjunction
$(\overline{C} \vee A \vee B) \wedge (C \vee \overline{A}) \wedge (C \vee \overline{B})$

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:
$(C \rightarrow \overline{A}) \wedge (\overline{C} \rightarrow A)$
$(\overline{C} \vee \overline{A}) \wedge (C \vee A)$

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:
$(C \rightarrow \overline{(A \vee B)}) \wedge (\overline{C} \rightarrow (A \vee B))$
$\overline{\overline{(\overline{C} \vee (\overline{A} \wedge \overline{B}))}} \wedge (C \vee A \vee B))$
$\overline{(C \wedge (A \vee B))} \wedge (C \vee A \vee B))$
$\overline{(A \wedge C) \vee (B \wedge C)} \wedge (C \vee A \vee B))$
$(\overline{A} \vee \overline{C}) \wedge (\overline{B} \vee \overline{C}) \wedge (C \vee A \vee B))$

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.

This article is issued from Wikipedia - version of the Sunday, February 07, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.