Why search through truth assignments?
A knowledge base may contain disjunctions such as “at least one sensor is working”. Forward chaining for definite Horn rules does not directly represent every such choice. Enumerating every truth assignment would decide a finite propositional problem, but many assignments can be ruled out together: once all but one option in a clause are false, the remaining option is forced. Unit propagation uses exactly that observation. Search is still needed when no clause forces a choice.
This section constructs a small, precise version of DPLL. It connects logical inference with the earlier search notes and complements the resolution unit's elimination method. The procedure below decides finite propositional formulas, not arbitrary first-order formulas.
Clauses, partial assignments and propagation
Definition 24.1.1
(Literals, clauses and CNF)
Fix finitely many Boolean atoms. A literal is an atom or its negation . A clause is a finite disjunction of literals; a CNF formula is a conjunction of clauses. Regard a clause as a set of literals, so repeated literals do not matter. The empty conjunction is true and the empty clause is false. A model of a CNF is a total assignment that makes every clause true; the CNF is satisfiable if it has a model and unsatisfiable otherwise.
Definition 24.1.2
(Partial assignments and simplification)
A partial assignment maps some atoms to true or false. To simplify a formula under it, delete every clause with a true literal, and delete false literals from each remaining clause. A formula containing the empty clause has no extension of that assignment; if no clauses remain, every extension satisfies the original formula. An unassigned atom has neither a true nor a false literal yet.
Definition 24.1.3
(Unit clause and unit propagation)
A unit clause contains exactly one literal. Any satisfying extension must make that literal true. Unit propagation assigns that literal, simplifies, and repeats until either a contradiction occurs or no unit clause remains.
The order of forced assignments does not affect the existence of a satisfying extension, although a particular implementation may report a different first conflict. A clause containing both and is always true and may be removed beforehand; the algorithm remains correct if such clauses are left in.
Consider the following recursive procedure on a simplified CNF and its current partial assignment:
- Propagate unit clauses to a fixed point, stopping if an empty clause appears.
- If an empty clause appears, return unsatisfiable for this branch. If no clauses remain, return the current assignment, completing any unassigned atoms arbitrarily.
- Otherwise choose an unassigned atom occurring in the remaining formula. Recursively try it true. If that branch returns a model, return it; otherwise restore the parent assignment and try it false. Return unsatisfiable only if both branches fail.
Each recursive call has its own assignment, or equivalently an implementation must undo all assignments made in a failed branch, including propagated ones. The choice of atom and the order of truth values affect work, not the final satisfiability answer. No pure-literal rule, clause learning or particular heuristic is assumed here.
Concept lensGeometric
Clauses as forbidden faces of the cube
Regard the total assignments as the corners of the -dimensional cube. A clause with literals is false exactly at the assignments that falsify each of its literals, and these form a face of dimension . A CNF is satisfiable exactly when its forbidden faces fail to cover every corner. A unit clause forbids half the cube, the empty clause forbids all of it, and a branching decision restricts attention to one half. On two atoms, the four clauses of the later four-clause example forbid one corner each, so nothing remains.
Theorem 24.1.4
(Soundness and completeness of finite DPLL)
For a finite CNF, the procedure terminates. If it returns an assignment, that assignment satisfies the original CNF. It returns unsatisfiable exactly when the original CNF has no satisfying assignment. The worst-case search can be exponential in the number of atoms.
Proof
(Induction on the number of unassigned atoms)
Simplification preserves exactly the satisfying extensions of the current partial assignment: a true clause imposes no further restriction, and a false literal cannot help satisfy its clause. A unit literal is true in every satisfying extension, so assigning it preserves that set of extensions. An empty clause has no satisfying extension; an empty set of clauses is satisfied by every completion.
If neither stopping case applies, the chosen atom is unassigned. Every total extension gives it either true or false, and these two cases cover all possibilities. Each branch assigns at least one previously unassigned atom, so no branch can have depth greater than the number of atoms. Induction on the number of unassigned atoms proves that a branch returns a model exactly when one exists in that branch. Taking the union of its two cases gives the same statement for the parent, establishing both soundness and completeness. Propagation is finite because every successful propagation assigns a previously unassigned atom. A binary tree of assignments may have exponentially many nodes; the theorem promises a decision, not a polynomial-time bound.
Proof X-ray
Why a failed branch is not a global refutation
The proof turns on one invariant: simplification and propagation preserve exactly the satisfying extensions of the current partial assignment. A unit literal is forced only relative to the assignment already made, so propagation is compulsory conditional on the current branch. A conflict therefore proves that no model extends the branch's choices, not that the original formula has no model. The two-way split is exhaustive because every total extension gives the chosen atom a value; only after both truth values of every relevant decision have been excluded can the root be declared unsatisfiable. Finiteness enters last: each branch assigns a previously unassigned atom, so the search terminates.
Entailment by refutation
Definition 24.1.5
(Entailment)
A formula entails a formula if every model of makes true.
Proposition 24.1.6
(Entailment as unsatisfiability)
For formulas and over the same atoms, entails if and only if has no model.
Proof
(Unfold the definition)
A model of is exactly a model of that makes false. Hence has no model if and only if no model of falsifies , which says that every model of makes true.
The search above therefore decides entailment: run it on a CNF form of and read the answer “unsatisfiable” as “entailed”.
Worked traces
Worked example 24.1.7
(An implication chain and a model)
Let
There is initially no unit. Try . The first clause forces ; then forces ; finally forces . The clause is already true because is false. All clauses have disappeared, so is a model. Choosing instead can also produce a model. A model proves satisfiability, but finding just one does not list every model.
Worked example 24.1.8
(Refutation proves an entailment)
The same entails . To test this, add the unit clause : propagation sets , then from . The next two clauses force and , leaving the empty clause from . Hence has no model. By definition this means every model of satisfies . For an arbitrary propositional query , the general test is satisfiability of ; a CNF conversion must preserve satisfiability. If the original conjunction is satisfiable, its model is a counterexample to entailment. A model returned for an equisatisfiable encoding with auxiliary variables need not automatically be such a counterexample: use a conversion whose models project to models of the original conjunction, or separately reconstruct and check a countermodel.
Worked example 24.1.9
(A refutation with no decisions, and the empty formula)
Let . The clause is a unit, so and the second clause becomes the unit . Assigning makes the clause empty. The conflict arises at the root before any decision, so every extension is excluded: is unsatisfiable and no branching was needed. At the other extreme, the empty CNF has no clauses, so the second stopping rule applies at once and any total assignment is a model. These boundary cases show that both stopping rules of step 2 can be reached without making a decision.
Counterexample mode
A stale branch assignment changes the answer
Let . Trying makes the first clause the unit , so propagation sets , and then the second clause becomes empty: the branch fails. After restoring the parent, makes the third clause the unit and the other two clauses true, so and is a model. If the failed branch's assignment is accidentally retained, the third clause is false in the second branch, and is wrongly reported unsatisfiable. Backtracking must undo propagated assignments as well as the decision itself.
What the answer means
A returned model is a concrete checkable witness: substitute its values into every original clause. An unsatisfiable result means every possible assignment has been excluded by the proof-bearing search; an implementation may need a separate certificate format if another program must verify a large run. A satisfiable knowledge base can entail a query even though many variables remain undetermined. Conversely, failure to derive a query by one incomplete rule system is not itself proof of its negation.
If the knowledge base is itself inconsistent, it has no models and classically entails every query. That is a consequence of the definition “true in every model”, not useful evidence for every conclusion. Check consistency separately when inconsistent data are possible. Computational complexity depends on representation and search choices; a fast result on one example does not establish fast worst-case performance.
Common mistakes
Common mistake
(Propagation that stops quietly is not a verdict)
The formula has no unit clause and no empty clause, so propagation does nothing and reports no conflict. Reading this as “satisfiable” is wrong: branching on makes both branches conflict, and the formula is unsatisfiable. A fixed point with clauses remaining only says that a decision is needed.
Common mistake
(Testing the query instead of its negation)
For and , the conjunction is satisfiable, for example by . A model of shows only that and are compatible, not that entails . The test is whether has a model: it does, , so does not entail .
Exercises
Quick check
(Run the stated procedure on , choosing first. Give a model and identify all forced assignments.)
Look for the unit clauses after each simplification.
Solution · Answer
With , the first clause is unit , so . The last clause then forces . The second clause is true because is true. Thus satisfies every clause.
Quick check
(For , branch on and demonstrate that both branches conflict.)
Simplify each branch and look for a pair of unit clauses and .
Solution · Answer
If , the second and fourth clauses become and , respectively, so propagation conflicts. If , the first and third become and , again a conflict. The two values exhaust all assignments to , hence the formula is unsatisfiable.
Quick check
(Does entail ? Exhibit either a refutation of or a countermodel.)
Try to make false while keeping both clauses true.
Solution · Answer
No. Set . The first clause is true through , the second through , and is false. This satisfies and is a countermodel to the entailment.
Quick check
(The formula has no unit clause initially. Is it valid to declare it satisfiable merely because propagation stops without conflict? Determine whether it entails and justify the answer.)
Test entailment by adding the unit clause .
Solution · Answer
No: absence of a unit or a detected conflict alone is not a satisfiability certificate; unresolved clauses remain. Here is entailed: adding makes the two original clauses into and , a conflict. The original formula is satisfiable, for example with ; the refutation of its conjunction with proves entailment, while the model establishes consistency.