浅谈布尔代数基础与 2-SAT

Hootime · 2026-03-30 15:51:57 · 算法·理论

模拟赛出了一个 2-SAT，但是我连布尔代数基础都不会，如何做非模板 2-SAT……

由于笔者初三，且布尔代数基础是跟着 Wikipedia 自学的，因此可能有不严谨之处，请指教。

布尔代数基础

本节参考了 Wikipedia 上的相关页面。

布尔代数是一个集合 A，其上定义了如下结构：

• 二元运算 \land：A \times A \to A；
• 二元运算 \lor：A \times A \to A；
• 一元运算 \lnot：A \to A；
• 以及常数 0, 1。

于是可以证明以下性质：（证明只给出形式 1，形式 2 同理）

::::success[简要证明] :::info[第一组有界律]{open}

::: :::info[第二组有界律]{open}

::: :::info[幂等律]{open}

::: :::info[逆的唯一性]{open} 反证法，假设 \exists b \neq \lnot a, [(a \land b = 0) \land (a \lor b = 1)].

综上，b = b \land \lnot a = \lnot a，与假设矛盾，故原命题成立。 ::: :::info[0 与 1 互补]{open}

::: :::info[德·摩根定律]{open}

由 (a \land b)\land(\lnot a \lor \lnot b) = 0, (a \land b)\lor(\lnot a \lor \lnot b) = 1，得 (a \land b) 的逆为 (\lnot a \lor \lnot b)。 ::: :::info[对合律]{open}

::: ::::

值得注意的是，布尔代数并没有规定集合 A 的大小，它不一定是 2。事实上，你可以把 \land 视为取并集、\lor 视为取交集、\lnot 视为取补集、0 视为空集、1 视为全集，容易证明 A 的大小是 2^n。

以下在 2-SAT 相关内容中讨论的布尔代数均为二元素布尔代数，即 A = \{ 0, 1 \}。

2-SAT

2-SAT 问题，全称 2-Satisfiability 问题，即给出 n 个布尔方程，每个方程形如 a \lor b，你需要给出它的一个可行解。2-SAT 的 2 得名于每个方程只与两个未知数有关，但是 k \ge 3 的 k-SAT 问题是 NPC 问题，故在此不作讨论。

我们观察单个方程 a \lor b = 0。思考我们能从这个方程中得到什么。我们发现如果 a = 0，那么 b = 1；类似地，如果 b = 0，那么 a = 1。也就是说我们得到了两组推导关系，即 \lnot a \implies b , \lnot b \implies a。

于是我们对 a_i, \lnot a_i 建点，对每一个方程的推导关系建边，建出了一个图。我们对这张图跑一个 Tarjan SCC。如果对于某一个 i，a_i 和 \lnot a_i 在同一个 SCC 中那么这个方程无解，因为 a_i 可以直接或间接地推导出 \lnot a_i，同理 \lnot a_i 可以推导出 a_i。否则，根据 SCC 编号顺序是拓扑序逆序的性质，我们选择 SCC 编号较小的一个作为解，因为其不可能推导出另一个状态。（当然如果你想较真，如果你能保证编号较大的一个不能推导出编号较小的一个那也可以，但是编码较为复杂所以一般不这么写。）

于是我们做完了。时空复杂度均为 \mathrm O(n)。

例题

似乎很多 2-SAT 的题都需要把限制转化成 \bigwedge_{i = 1}^{n}(a \lor b) 的形式。

P4782 【模板】 2-SAT

有 n 个布尔变量 x_1\sim x_n，另有 m 个需要满足的条件，每个条件的形式都是 「x_i 为 true / false 或 x_j 为 true / false」。比如 「x_1 为真或 x_3 为假」、「x_7 为假或 x_2 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。