Definition
The procedure is based on unit clauses, i.e. clauses that are composed of a single literal. If a set of clauses contains the unit clause, the other clauses are simplified by the application of the two following rules:
- every clause containing is removed;
- in every clause that contains this literal is deleted.
The application of these two rules lead to a new set of clauses that is equivalent to the old one. For example, the following set of clauses can be simplified by unit propagation because it contains the unit clause .
Since contains the literal, this clause can be removed altogether. Since contains the negation of the literal in the unit clause, this literal can be removed from the clause. The unit clause is not removed; this would make the resulting set not equivalent to the original one; this clause can be removed if already stored in some other form (see section "Using a partial model"). The effect of unit propagation can be summarized as follows.
| (removed) | ( deleted) | (unchanged) | (unchanged) | ||
The resulting set of clauses is equivalent to the above one. The new unit clause that results from unit propagation can be used for a further application of unit propagation, which would transform into .
Read more about this topic: Unit Propagation
Famous quotes containing the word definition:
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)