Does propagation make guesses?

No. Search decisions can trigger propagation, but the propagated assignments are forced under those decisions.

Is it the same as unit resolution?

They are closely related; unit resolution derives clauses, while propagation usually describes assignment and simplification in a solver.

Can it solve every SAT problem alone?

No. General problems may require branching or additional reasoning.

AI Glossary / Graphs and symbolic AI / Advanced

Unit propagation

Definition

Unit propagation is a logical simplification process that repeatedly applies assignments forced by unit clauses. In a propositional formula, a unit clause contains one literal that must be true. Assigning it can simplify other clauses, create further units, or expose a contradiction. The process is central to many satisfiability solvers.

What it means

Suppose a requirement says A or B must hold, and A is already false. B is then forced: there is no remaining alternative for satisfying that requirement. If B subsequently forces C, the consequences continue to spread without another guess.
Unit propagation follows these immediate implications of the current assumptions. It is different from choosing a variable value as a search decision. A forced assignment within one search branch may depend on that branch's decisions and need not hold in every solution of the original problem.

How it works

For a formula in conjunctive normal form, every clause must be satisfied. When a unit literal is identified, the solver assigns the underlying variable so that the literal is true. It removes satisfied clauses from the remaining work and removes false literals from other clauses.
The solver repeats this until all clauses are satisfied, a clause becomes empty, or no units remain. An empty clause signals a conflict. If unsatisfied nonunit clauses remain, propagation has reached a stopping point but has not necessarily decided satisfiability.
Efficient solvers avoid rescanning every clause after every assignment. Watched-literal techniques track selected literals and revisit a clause when relevant changes could make it unit or conflicting. This changes how consequences are discovered, not which assignments logically follow from a particular unit step. A solver also records assignments and their reasons so it can backtrack and analyze conflicts correctly.

Three practical examples

In a product configurator, disabling one of two required alternative components forces selection of the other. That choice can trigger additional compatibility requirements.
In a scheduling problem, fixing one task to a resource can rule out conflicting assignments. If another task then has only one permissible encoded option, propagation can force it.
In a hardware-verification model, a proposed input assignment can force intermediate signal values. A contradiction with the tested output condition can refute that particular proposal.

Think of it this way

Imagine filling a puzzle where each placement leaves fewer options elsewhere. Some next moves become unavoidable, while others still require a choice. Following forced moves can reveal a mistake quickly, but reaching a position with no forced move does not show that the puzzle is solved.

Worked example

Consider four Boolean variables and these clauses:
C1=¬A∨B; C2=¬B∨C; C3=¬A∨¬C; C4=A∨D.
Initially, each clause has two literals. There are no unit clauses, so propagation alone makes no assignment.
Suppose the search chooses A=true. C1 becomes B, forcing B=true. C2 then becomes C, forcing C=true. But C3, with A=true, requires ¬C. This branch contains incompatible requirements and must be rejected. A different processing order may expose the same conflict earlier; it does not make the branch valid.
The conflict does not mean the original formula is unsatisfiable. Try A=false instead. C1 and C3 are satisfied, while C4 becomes D, forcing D=true. C2 remains ¬B∨C, which is not unit. Propagation stops with B and C undecided.
If the search next chooses B=false, C2 is satisfied and C can take either value. If B=true, C2 forces C=true. Thus the complete formula has exactly three solutions: (A,B,C,D)=(false,false,false,true), (false,false,true,true), and (false,true,true,true).
Checking all sixteen assignments confirms this count. Notice that every solution has A=false and D=true, although the initial unit-propagation pass discovered neither fact. Unit propagation is sound but does not find every logical consequence of a general clause set.

Illustrative case study

A fictional team encodes a device's fast mode as A, an added sensor as B, synchronization as C, and fallback operation as D. Its rules require fast mode to use the sensor, the sensor to use synchronization, fast mode to exclude synchronization, and either fast mode or fallback operation to be enabled.
These are the worked example's rules. Choosing fast mode triggers a contradiction, while choosing fallback permits several configurations. The team traces the conflict to the combination of requirements rather than reporting that no device configuration exists.
During review, engineers decide whether the fast-mode restriction is intentional or an encoding error. The solver cannot make that engineering judgment. The example shows how propagation and search can support diagnosis while keeping a failed branch distinct from failure of the entire specification; it is not a reported product deployment.

Common misconceptions and mistakes

No remaining unit clauses does not mean the formula is satisfied. Nonunit clauses may still require search, and some formulas with no units are unsatisfiable.
A conflict under a temporary decision does not automatically prove the original problem inconsistent. The decision or another branch assumption may be responsible.
Propagation is not a probabilistic prediction. A forced literal follows logically from the encoded clauses and current assignments; there is no confidence percentage attached to the rule itself.
Do not confuse an empty clause with an empty remaining clause collection. The first is a contradiction; the second means all clauses have been satisfied under the recorded assignments.

Business use

Unit propagation supports fast consistency checks and explanations in configuration, scheduling, planning, and verification. Preserve the reasons behind forced assignments so users can understand conflicts. Distinguish permanent requirements from temporary choices and optional preferences. Evaluate the surrounding solver as well as propagation: real value depends on correct encoding, appropriate search, and clear interpretation of success, conflict, and resource limits.

Check your understanding

Why does the initial pass make no assignments?

Answer: There are no unit clauses.

Why is A=true rejected?

Answer: It forces B and C while also requiring ¬C.

After A=false, what is forced?

Answer: D=true; B and C still have three permissible combinations.

Related terms

Unit clause
Satisfiability
Unit resolution
Boolean constraint propagation
DPLL
conflict-driven clause learning
watched literals
backtracking

Learn next

Trace a solver's decision trail, marking each assignment as chosen or propagated. Then study how conflict analysis derives reusable information and how watched literals reduce clause-inspection work.

Sources

Redundancy Rules for MaxSAT, SAT 2025, preliminaries defining unit propagation: https://drops.dagstuhl.de/storage/00lipics/lipics-vol341-sat2025/html/LIPIcs.SAT.2025.7/LIPIcs.SAT.2025.7.html Dixon, Ginsberg, and Parkes, Unit Propagation: The Inner Loop, implementation discussion: https://www.scs.cmu.edu/afs/cs/project/jair/pub/volume21/dixon04a-html/node3.html AIMA glossary, unit propagation: https://github.com/aimacode/aima-glossary

Previous: Unit production Next: Unit resolution