Boolean-satisfiability

释义 Definition

布尔可满足性：指一个由布尔变量（取值为真/假）组成的逻辑公式，是否存在某种变量赋值使得整个公式为真。它常简称为 SAT，是计算机科学与算法、复杂性理论中的核心问题之一（也有更具体的变体，如 3-SAT）。

发音 Pronunciation (IPA)

/ˈbuːliən ˌsætɪsfəɪəˈbɪləti/

例句 Examples

We used a SAT solver to check the boolean-satisfiability of the formula.
我们使用 SAT 求解器来检查该公式的布尔可满足性。

Boolean-satisfiability is central to modern verification because many hardware and software bugs can be reduced to SAT instances.
布尔可满足性在现代验证中非常核心，因为许多硬件与软件缺陷都可以归约为 SAT 实例来处理。

词源 Etymology

该术语由 Boolean（“布尔的”，源自英国数学家 George Boole 的姓氏）和 satisfiability（“可满足性”，来自 satisfy “满足” + -ability “……的能力/性质”）构成，字面意思就是“布尔（公式）的可满足性”。

相关词 Related Words

• Boolean
• Satisfiable
• Satisfiability
• Clause
• Conjunction
• CNF
• 3-SAT
• NP-Complete
• Reduction
• SAT-Solver

文学与经典著作 Literary Works

• Stephen A. Cook, The Complexity of Theorem-Proving Procedures（1971）——提出 Cook 定理，奠定 SAT 在复杂性理论中的地位。
• Richard M. Karp, Reducibility Among Combinatorial Problems（1972）——展示多种问题向 SAT/相关形式的归约思想。
• Michael R. Garey & David S. Johnson, Computers and Intractability（1979）——经典 NP 完全性著作，系统讨论 SAT 等问题。
• Donald E. Knuth, The Art of Computer Programming（部分卷册与相关讨论中涉及 SAT/可满足性思想）——在算法与组合结构背景下提及相关概念。