Tseitin-Transformation

The Tseitin transformation ( or Tseitin the method) is a method, with the formulas from propositional logic to a conjunctive normal form (CNF ) can be accommodated. The resulting conjunctive normal form is not approximately equivalent, but only erfüllbarkeitsäquivalent.

• 3.1 polarity

Motivation

Usually equivalence transformations such as De Morgan's laws, the distributive and others used to bring any propositional formulas in conjunctive normal form.

By using the distributive can generally occur in an exponential increase in the number of conjunctions. To limit this increase, the formula is moved to a satisfiability form.

For an example with two clauses, each with 4 variables to which the distributive law is applied, you can see the thereby resulting exponential increase in conjunctions:

Idea

By using a erfüllbarkeitsäquivalenten forming, it is now possible during the transformation to introduce variables.

The basic idea is to introduce a variable for each subformula. Using the propositional equivalence, these subformulae are then connected to the new variables and all resulting conditions conjugated to each other. After each of these conditions is housed separately in CNF.

Example

The example should be shown on the formula here.

First of all sub-formulas are listed length by:

Now four variables are introduced and linked by the biconditional with the subformulae. On this occasion, the sub-formulas are already substituted by the corresponding variables:

Now all these substitutions are conjugated. It is important that the variable that was used for the original formula, is added as a separate conjunct.

The corresponding new formula looks like this:

Now only all conjuncts have to be converted separately in CNF, which are carried out with the usual equivalent transformations. This is an example shown at a conjunct:

Note that in the last step again the distributive was applied, but in this step, there is only a constant increase of conjunctions.

At the end of this transformation is applied to all conjuncts and the resulting CNF is erfüllbarkeitsäquivalent to the original formula, and generally has fewer clauses. It may happen that this is not true for smaller formulas.

Extension by Plaisted and Greenbaum

This extension to the classic Tseitin method uses the concept of polarity (NV Murray, 1982) as an essential component.

Polarity

Polarity refers to the parity of the number of negations in the syntax tree of a propositional formula from the root node to the desired node. It follows that a node that has an odd number of negations from the root symbol to him, a negative polarity (corresponding to even number of negations and positive polarity).

When expanding by Plaisted and Greenbaum, there are two major differences to normal Tseitin transformation:

The direction of the inserted implication depends on the polarity from:

In a sub-formula with positive polarity, the new variable as follows is introduced:

The same sub-formula with negative polarity:

Generally cause these two changes, that the resulting KNF is smaller than in the Tseitin transformation, as long as all of the sub-formulas do not occur in both polarities.

Future research is concerned with heuristics for the appropriate introduction of new variables, thus, not all subformulae to an increase in the number of variables.

Swell

• G. Tseitin p. On the complexity of derivation in propositional calculus. Leningrad Seminar on Mathematical Logic, 1970.
• D. A. Plaisted and S. Greenbaum. A Structure- Preserving Clause form translation. Journal of Symbolic Computation, 1986.

• Mathematical Logic
• Theoretical computer science
• Transformation