Unit Propagation

释义 Definition

单子句传播（Unit Propagation）：在命题逻辑/可满足性问题（SAT）中，当某个子句只剩下一个未被赋值的文字（即“单子句”）时，为了使该子句为真，该文字的取值就被强制确定；随后这一新赋值会继续触发更多单子句，从而连锁“传播”出更多必然赋值。它是 DPLL/CDCL 类 SAT 求解器的核心推理步骤之一。

发音 Pronunciation (IPA)

/junt prpen/

例句 Examples

Unit propagation quickly forces several variables to be true or false.
单子句传播会很快迫使若干变量取真或取假。

In modern SAT solvers, unit propagation and conflict analysis work together to prune the search space efficiently.
在现代 SAT 求解器中，单子句传播与冲突分析相互配合，以高效地剪枝搜索空间。

词源 Etymology

unit 在这里指“单个的”，具体是“只含一个未定文字的子句（unit clause）”；propagation 源自“传播、扩散”，表示由一个强制赋值引发一连串必然赋值的过程。该术语主要形成于计算机科学中对布尔逻辑推理与 SAT 求解算法（如 DPLL、后来的 CDCL）的描述语境。

相关词 Related Words

• Unit Clause
• Boolean Satisfiability
• CNF
• DPLL
• CDCL
• Resolution
• Constraint Propagation
• Boolean Constraint Propagation
• Conflict Analysis
• Implication Graph
• Literal
• Clause Learning

文学/经典著作中的出现 Notable Works

• Handbook of Satisfiability（Biere, Heule, van Maaren, Walsh 编）：系统讨论 SAT 技术，包含对 unit propagation/BCP 的核心地位与实现细节的说明。
• Decision Procedures: An Algorithmic Point of View（Daniel Kroening, Ofer Strichman）：在决策过程与 SAT/SMT 语境中介绍单子句传播等关键推理步骤。
• The SAT Solver Handbook / Satisfiability Testing（与 SAT 求解相关的经典教材与综述文献中常见）：在 DPLL/CDCL 框架下反复使用并解释 unit propagation。