代码术语:sat

一文讲清楚:SAT

先说结论:作为一个「代码术语」,SAT 最主流的含义是 Boolean Satisfiability Problem —— 布尔可满足性问题:给定一个由布尔变量、与、或、非组成的公式,问「是否存在一组真假取值,让整个公式为真」。答「存在」叫 SAT(可满足),答「不存在」叫 UNSAT(不可满足)。它是计算机科学里第一个被证明的 NP 完全问题,也是今天形式验证、约束求解、依赖解析背后的实际引擎。

不过 SAT 是个高度依赖语境的缩写,判断方法和 exp、blk 一样:看它出现在哪一层。

页面末尾附有全文结构的思维导图。

语境 SAT 指什么 典型长相
算法 / 论文 / 验证工具 Boolean Satisfiability,布尔可满足性问题 SAT solver、UNSAT、p cnf、3-SAT
芯片 / EDA / 形式验证 同上,指用 SAT 求解做等价性检查、模型检查 SAT sweeping、BMC
程序验证 / 安全 常常其实是 SMT(SAT 加理论),口语里被简写成 SAT z3、cvc5、SMT-LIB
网络设备 / 防火墙 Address Translation,地址转换(静态 / 源地址) 配置里的 SAT,与 SNAT、DNAT 并列
工程交付 / 制造 Site Acceptance Test,现场验收测试 与 FAT(出厂验收)成对出现
考试 / 留学 Scholastic Assessment Test,美国大学入学考试 分数区间 400–1600
前端 / 图形 saturation,饱和度 saturate()、HSL 里的 S
文件后缀 .sat 是 ACIS 的三维实体模型格式 part.sat
一句话判据:**代码、论文、验证工具里的 ''sat'' 就是「可满足性」;只有当它出现在网络配置或验收文档里,才轮到「地址转换」「现场验收」。**

下面只展开第一条 —— 它才是开发者日常真正会撞上 SAT 的地方。

SAT 问题的输入是一个命题逻辑公式,输出只有一个 bit:可满足,还是不可满足。

先记住这五个零件,读论文、看代码、调求解器都要用:

术语 英文 说明 例子
变量 variable 只能取真 / 假 x1、x2
文字 literal 变量本身,或它的否定 x1、¬x3
子句 clause 若干文字的或 (x1 ∨ ¬x3)
合取范式 CNF 若干子句的与 见下
赋值 / 模型 assignment / model 给每个变量定值;让公式为真的赋值叫模型 x1=T, x2=F, x3=T

标准形式是 CNF(Conjunctive Normal Form,合取范式):

(x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1)

变量:x1 x2 x3
子句:(x1 ∨ ¬x3)        ← 2 个文字
      (x2 ∨ x3 ∨ ¬x1)   ← 3 个文字

代入赋值 x1=T, x2=F, x3=T:
  子句 1:T ∨ F     = T  ✔
  子句 2:F ∨ T ∨ F = T  ✔
→ 整个公式为真,这个实例是 SAT

为什么要标准化成 CNF:任何布尔公式都能在多项式时间内转成 CNF(用 Tseitin 变换,见第 3 节),所以「一般 SAT」与「CNF-SAT」难度等价,教科书里的定义就统一写 CNF 了。

再补两个周边概念:

  • UNSAT:不存在任何能满足的赋值。它不是一个「没算出来」的中间状态,而是一个结论 —— 而且是可以被独立证明的结论(见第 6 节)。
  • 判定 vs 求解:SAT 这个名字问的是「有没有解」(判定问题);但多数场景还需要把那个解拿出来用,所以求解器在报 s SATISFIABLE 之后,通常会给一行 v … 的模型。

SAT 之所以有用,是因为大量组合问题都能表述成「一组布尔约束同时成立」。常见三招。

  • 「A 与 B 不能同时为真」→ (¬A ∨ ¬B)
  • 「A 蕴含 B」→ (¬A ∨ B)
  • 「至少选一个」→ (A ∨ B ∨ C)
  • 「恰好选一个」→ 至少一个,加两两互斥:(A ∨ B ∨ C) ∧ (¬A ∨ ¬B) ∧ (¬A ∨ ¬C) ∧ (¬B ∨ ¬C)

直接展开成 CNF 会指数膨胀(「或套与」这种形状尤其明显)。Tseitin 的做法是给每个子公式起一个辅助变量,用少量子句把它们钉在一起:

原始:(A ∧ B) ∨ (C ∧ D)
引入:t1 ↔ (A ∧ B)、t2 ↔ (C ∧ D),目标写成 t1 ∨ t2
结果:CNF 规模与公式大小成线性,代价是变量变多

工业界几乎所有编码都走这条路:用变量换结构。

两两互斥的写法在 n 个候选时会产生 C(n,2) 个子句,n 一上去就爆炸。替代方案:

编码 子句规模 特点
两两互斥(pairwise) O(n²) 最简单直白,n 小的时候照用
顺序编码(sequential / ladder) O(n) 引入辅助变量,通用性好
二进制 / 位向量编码 O(n log n) 候选本身是编号时最自然,但对单元传播不友好
commander 编码 O(n),常数更小 大规模 at-most-one 的常用选择

「x + y ≤ 10」「下标 i 的元素等于 v」这类约束手工编码成布尔子句能写,但极其痛苦且容易出错。这种情况直接用 SMT(SAT Modulo Theories)—— 底层还是 SAT,只是外面套了算术、位向量、数组、字符串等理论求解器。

SAT 工具的输入格式几乎都是 DIMACS CNF(.cnf 后缀),几行就能读完:

c 注释:(x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1)
p cnf 3 2
1 -3 0
2 3 -1 0

逐行解释:

  • c 开头是注释行
  • p cnf <变量数> <子句数> 是头信息,这两个数字必须和实际内容一致,多数求解器靠它预分配内存
  • 每个子句写一行,用 0 结尾;正数表示变量本身,负数表示取反,变量编号从 1 开始
  • 上面第二行数据 1 -3 0 就是 (x1 ∨ ¬x3)

命令行跑一下:

cadical example.cnf
# s SATISFIABLE
# v 1 -2 3 0
 
minisat example.cnf out.txt      # 结果写进 out.txt

用 Python 直接调(PySAT 把主流求解器封装成统一接口):

from pysat.formula import CNF
from pysat.solvers import Glucose3
 
cnf = CNF(from_clauses=[[1, -3], [2, 3, -1]])
with Glucose3(bootstrap_with=cnf) as g:
    print(g.solve())        # True
    print(g.get_model())    # [1, -2, 3]
 
# 也可以直接读 DIMACS 文件:
# cnf = CNF(from_file="example.cnf")

需要「不只是布尔」时用 Z3:

from z3 import Int, Solver, sat
 
x, y = Int("x"), Int("y")
s = Solver()
s.add(x + y <= 10, x > 3, y >= 0)
print(s.check())            # sat / unsat / unknown
print(s.model())

同样是「布尔公式可满足吗」,限制不同,难度天差地别:

问题 形状限制 复杂度 说明
2-SAT 每条子句至多 2 个文字 线性时间 建蕴含图求强连通分量(SCC)即可
Horn-SAT 每条子句至多 1 个正文字 线性时间 单元传播跑到底,不需要回溯
3-SAT 每条子句恰好 3 个文字 NP 完全 Karp 1972,SAT 最经典的特例
CNF-SAT 一般形式 NP 完全 Cook–Levin 定理(1971),第一个被证明的 NP 完全问题
#SAT 数有多少个解 #P 完全 比判定更难,模型计数用
MaxSAT 最多能同时满足多少子句 NP 难(优化版) 配置修复、软约束场景常用
QBF 公式里带 ∀ / ∃ 量词 PSPACE 完全 表达能力更强

2-SAT 的经典做法值得单独记一下:

子句 (¬a ∨ b) 等价于蕴含 (a → b)
对每条子句补出两条蕴含边,建成有向图
若某个变量 x 与 ¬x 落在同一个强连通分量里 → UNSAT
否则按 SCC 逆拓扑序取值即可得到解
注意:**「NP 完全」说的是最坏情况**。它意味着没有已知的多项式时间算法(且普遍认为不存在),但**不意味着实际算不动** —— 见第 7 节。

现代 SAT 求解器绝大多数属于 CDCL 系。理解它,先懂它的前身 DPLL。

简化流程:
  ① 单元传播:某子句只剩一个未赋值文字时,它就必须为真 → 立刻赋值
                 若产生空子句(冲突)→ 回退
  ② 分支:挑一个未赋值的变量,先试 true
  ③ 回溯:走不通就换 false;全部穷尽仍然冲突 → UNSAT

思路朴素,但光是单元传播这一步,就已经能砍掉绝大部分搜索空间。

CDCL(Conflict-Driven Clause Learning)在 DPLL 上加了四件关键的事:

  • 冲突分析 + 学习子句:每次冲突都分析出「究竟是哪几个赋值凑成了必然矛盾」,把它写成一个新子句加进公式。这条子句永久有效,后面不会再踩同一个坑
  • 非时序回溯:不是退一步,而是直接跳回真正导致冲突的那一层,一步跨很远
  • 分支启发:用 VSIDS 之类的策略,优先选「最近频繁出现在冲突里」的变量
  • 两文字监视(watched literals):每个子句只盯两个文字,单元传播时只需检查少量子句,速度提升巨大

再叠上周期性重启(Luby / 几何序列)和子句删除(防止子句库无限膨胀),就是今天工业级求解器的骨架。

术语时间线,看到别陌生:

名字 年份 贡献
DP / DPLL 1960 / 1962 单元传播 + 回溯的基础框架
GRASP 1996 冲突分析与学习子句
Chaff 2001 VSIDS + 两文字监视,速度飞跃
MiniSat 2003 极简开源实现,成为后来几乎所有求解器的起点
现代求解器 2010s– 预处理、inprocessing、更聪明的重启与启发
  • SATISFIABLE + 模型 v …:找到解
  • UNSATISFIABLE:无解,通常还附带一份可独立校验的证明(DRAT / DRUP 格式),第三方校验器能复核 —— 这是形式验证敢把安全性押在 SAT 上的底气
  • UNKNOWN:超时或触到资源上限。这不等于无解
工具 类型 适用场景
MiniSat / Glucose / CaDiCaL / Kissat 纯 SAT 工业与竞赛标准件,CaDiCaL、Kissat 常年在 SAT Competition 前列
CryptoMiniSat 纯 SAT 对 XOR 约束专门优化,密码学实例常用
PySAT Python 封装 一行代码切换求解器,适合实验与教学
Z3 / CVC5 / Yices SMT 支持整数、实数、位向量、数组、字符串等理论
商用求解器 SMT / 优化 带支持服务,强调工程集成与规模

解得动,而且常被低估。原因是最坏情况和实际实例是两回事:

  • 工业实例大多来自电路、程序、配置这类有结构的问题,CDCL 学习出的子句正好抓住这些结构
  • 现代求解器能处理百万级变量、千万级子句的实例;SAT Competition 的工业组就是拿真实 EDA / 验证问题当题面
  • 求解前还有成体系的预处理(变量消除、子句化简、等价变量合并),先把问题缩小再动手
  • 反过来说:无结构的随机 3-SAT 依然很难,接近相变阈值的地方尤其硬 —— 这才是「SAT 太慢」的真实来源

一句话:SAT 的难度不在规模,在结构。

领域 在做什么 为什么落到 SAT
硬件形式验证 等价性检查、模型检查、BMC 「两个电路在任意输入下输出相同」本身就是布尔公式
软件验证 限界模型检查、符号执行、测试生成 把路径条件编成 CNF,有解即存在触发该路径的输入
SMT / 程序验证 合约检查、类型推断、漏洞检测 在 SAT 之上加算术等理论(z3、cvc5)
自动规划 SATPLAN 一类规划器 把「第 t 步执行什么动作」编成变量,约束编成子句
依赖解析 包管理器选版本 版本约束本质是布尔组合问题(见下)
配置与排产 特性开关、装箱、排课、调度 大量互斥 / 蕴含约束,天然是 CNF
EDA 布局布线、时序与功耗约束 布尔约束 + 优化目标(MaxSAT)
谜题与游戏 数独、N 皇后、扫雷、图着色 经典教学案例:把规则写成子句即可
密码分析 对简化轮数密码搜原像 / 碰撞 密码本身可展开成布尔电路,求解器即搜索器
模型计数 #SAT / 概率推断 数解的个数,属 #P 难度
配置修复 MaxSAT 找「改动最小且满足全部硬约束」的方案

包管理器那条多解释一句:「装 A 需要 B ≥ 2 且 C < 3,而 B ≥ 2 恰与 C < 3 互斥」 —— 这就是一个布尔约束求解问题。Dart 的 pub、Cargo 新版 resolver 用的 PubGrub 都属于 CDCL 风格求解;所以你在包管理器报错里看到的「回溯、冲突、无法找到兼容版本」,和 SAT 求解器的日志是同一套思路。

缩写 全称 一句话区分
SAT Boolean Satisfiability 布尔公式有没有解(本页主角)
SMT Satisfiability Modulo Theories SAT 加理论:算术、位向量、数组、字符串
SAST / DAST Static / Dynamic Application Security Testing 源码扫描 / 运行时扫描,与可满足性无关
3-SAT 3-CNF SAT SAT 的特例,子句恰好 3 个文字,仍是 NP 完全
SNAT / DNAT / SAT (Source / Destination) Address Translation 网络地址转换,出现在防火墙配置而非代码里
.sat ACIS 实体模型文件 三维建模格式,与求解器无关
saturate() 饱和度调整 CSS 滤镜 / HSL 色彩模型里的 S

另外还有两个纯生活语境,撞见了别多想:

  • SAT = Scholastic Assessment Test,美国大学入学考试(总分 400–1600)
  • SAT = Site Acceptance Test,工程交付里的现场验收测试,与 FAT(Factory Acceptance Test,出厂验收)配对
现象 原因 处理方向
求解器返回 UNKNOWN 就当无解 UNKNOWN 只是「没在预算内算完」 放宽时限、调参数、换求解器;别把三态压成两态
拿纯 SAT 求解器去解明显是整数规划的问题 硬把整数编码成布尔,变量爆炸 直接上 SMT 或专用求解器
CNF 文件头数字与内容不符 p cnf n m 改了一半 由生成器统一维护,不要手改
编码完变量一大就解不动 「恰好一个」用了 O(n²) 两两互斥 换顺序 / commander 编码
UNSAT 结果无法复核 没保留证明 让求解器输出 DRAT,用校验器独立验证
随机实例解不动,就断言「SAT 不行」 随机 3-SAT 本身就是最难的一类 换建模方式,减少对称性
换个求解器后模型不同 求解顺序受启发式影响 把 SAT / UNSAT 当结论,模型按需解读
把 SAT 与 SMT 混着说 口语化简写 明确写「布尔 SAT」还是「SMT」

倒数第二条展开一句:同一个公式,不同求解器、不同版本给出的模型可能完全不同,但 SAT / UNSAT 的结论必须一致。 若结论不一致,那是求解器或编码的 bug,不是「口味问题」。

SAT 就是问「**存不存在一组真假取值,让这个布尔公式为真**」:答「存在」给一个赋值(模型),答「不存在」给一份可校验的证明。它是历史上第一个被证明的 **NP 完全**问题(Cook–Levin 1971),却是工程上最成功的「难问题」之一 —— CDCL 求解器能从冲突中学习,把电路、程序、依赖关系这类**有结构**的问题解到百万变量规模。看到代码或工具里的 ''sat'' / ''SAT'' / ''UNSAT'',基本都在说这件事。

相关:exp · blk · hex · buffer


返回:代码术语

该主题尚不存在

您访问的页面并不存在。如果允许,您可以使用创建该页面按钮来创建它。

  • 代码术语/sat.1792125119.txt.gz
  • 最后更改: 2026/10/16 12:31
  • 由 张叶安