Sat Solver

释义 Definition（中文）

SAT solver：布尔可满足性（SAT, Boolean Satisfiability）求解器。一种算法/程序，用来判断一个布尔逻辑公式（通常以 CNF 合取范式表示）是否可满足，并在可满足时给出一组使其为真的变量赋值。常用于形式化验证、约束求解、规划、自动推理、EDA/芯片设计等领域。

发音 Pronunciation（IPA）

/ˌɛs eɪ ˈtiː ˈsɒlvər/

例句 Examples

The SAT solver found a solution in seconds.
SAT 求解器在几秒内就找到了一个解。

By encoding the scheduling constraints as a CNF formula, the team used a SAT solver to automatically search for a conflict-free timetable.
团队把排课约束编码成 CNF 公式后，使用 SAT 求解器自动搜索无冲突的时间表。

词源 Etymology（中文）

SAT 来自 Satisfiability（可满足性） 的缩写，指布尔逻辑公式“是否存在一种赋值使其为真”的问题；solver 源自英语动词 solve（解决）加上表示“执行者/工具”的后缀 -er。合起来即“用于解决 SAT 问题的工具/程序”。

相关词 Related Words

• Boolean
• Satisfiability
• CNF
• Clause
• Literal
• DPLL
• CDCL
• SMT
• Constraint
• Model Checking

文学与著作 Literary Works（出现或重点讨论）

• Handbook of Satisfiability（系统介绍 SAT 与 SAT solver 的经典参考书）
• Decision Procedures: An Algorithmic Point of View（涉及 SAT/SMT 与相关求解技术）
• Davis, Putnam, Logemann, Loveland 相关论文（DPLL 家族方法的奠基性工作，SAT solver 的核心思想来源之一）
• 形式化验证/模型检测方向的教材与专著（常以 SAT solver 作为底层引擎或关键组件进行讲解）