Preprocessing¶
Unit clause propagation is
relatively efficient in pruning the search space
and
it can be implemented to work very efficiently by using proper data structures.
Thus many SAT solvers use it, and only it,
as the constraint propagation technique during the search.
However, there are other techniques that could prune the search space in different ways but are considered to be too slow to be used in the inner loop of the search.
One alternative for applying such techniques is to use them for preprocessing the formula before the search phase.
That is,
given a CNF fomula
is satisfiable if and only if is, from a model of
, it is possible to reconstruct a model for , and
is (hopefully) easier to solver that .
Thus they can be seen as transformations that preserves satisfiability and the process of SAT solving with preprocessing is as follows:

In the CDCL approach, such techniques can also be used interleaved with the search after restarts — in this case, one speaks about “inprocessing”.
In the following, we give examples of some simple preprocessing techniques. Please see, for instance, these slides by Marijn Heule for some other techniques used in modern SAT solvers as well.
Pure literal elimination¶
A literal
Example: Pure literal elimination
Consider the formula
The literal
Now the literal
The truth assignment
Blocked clause elimination¶
Blocked clause elimination [Kullmann1999] is another method
for removing “redundant” clauses in a satisfiability-preserving way.
We say that a clause
Theorem
If
Proof sketch
If a truth assignment
In the other direction, assume that an assignment
Thus one may remove a blocked clause from
Example
Consider the CNF formula
Observe that the formula has no pure literals and thus pure literal elimination cannot remove any clauses from it. However:
The clause
is blocked because for the literal in it, only the clause contains , and contains the lietral and contains the literal . We can thus remove the clause and get the formulaNow the clause
is blocked because for the literal in it, the clause with contains and contains its negation . Removing this blocked clause gives the formulaThe clause
is now blocked due to the (pure) literal and we get the formulaNow
is blocked because of the (pure) literal and, by removing it, we get the trivially satisfiable empty formula.
As the last formula is satisfiable, the original formula is satisfiable as well.
Let’s reconstruct a satisfying truth assignment for
the original formula by using the construction described in the proof above.
We start from the last formula and
select an arbitrary satisfying truth assignment for it;
however, we also assign arbitrary values for the variables
that appear in the original formula as well.
Suppose that we pick the truth assignment
The clause
was the last one that was removed, due to the blocking literal . The assignment satisfies the clause and thus the formula as well.The clause
was then the previous one removed, due to the blocking literal . The assignment satisties as well and thus also the formula .The clause
was removed due to the blocking literal . The assignment does not satisfy the clause and thus we flip the value of the blocking literal and obtain the assignment . Now satisfies not only the clause but also the clauses in the formula . Therefore, it satisfies the formula as well.Finally,
does not satisfy the first removed blocked clause . Thus we flip the value of the blocking literal and get the assignment . This assignment satisfies the clause and all the clauses in and thus the original formula as well.