2-SAT 问题的相关概念

SAT 问题： 给定 $n$ 个命题，$x_1,x_2,…,x_n$，每个命题有两种取值，可以取值为真或假（$0$ 或 $1$），我们假设 $x_i$ 表示第 $i$ 个命题为真，$-x_i$ 表示第 $i$ 个命题为假。对于这 $n$ 个命题，会有若干个条件，如 $x_1 \wedge x_2 \wedge -x_3$（$\wedge=$ 或），表示 $x_1$ 为真、$x_2$ 为真、$x_3$ 为假，这三个命题中至少有一个是成立的。我们需要给这 $n$ 个命题一个取值，使得每一个条件都是成立的。

SAT 问题是一个 NPC 问题（NP 完全问题），如果给我们一个一般的 SAT 问题，我们是无法在多项式的复杂度内把这个问题求解出来的。但是对于 2-SAT 问题，我们是有一些比较效率的解法的，最好的算法可以做到线性的时间复杂度。

2-SAT 问题： 区别于 SAT 问题，2-SAT 问题的每个条件中一定只有两个变量，举例如 $x_1 \wedge -x_2$，表示 $x_1$ 为真、$x_2$ 为假，这两个命题中一定有一个是成立的。相似的，2-SAT 问题中所有的条件都像这样只有两个变量。

2-SAT 问题的一般解法：

给定 $n$ 个命题，$x_1,x_2,…,x_n$，我们用 $x_i$ 表示 $x_i = 1$，用 $-x_i$ 表示 $x_i = 0$。

接下来我们想把这个问题放到图论里面，我们把每一个命题表示成图论里的一个点，然后把它们之间的推导关系看成边。

如何去推导，这里涉及到 离散数学 中的 数理逻辑，假设有两个变量 $a$ 和 $b$，$a\wedge b$ 表示如果 $a$ 是 $1$，那么 $b$ 一定是 $1$。

对于 $a\wedge b$ 进行列表。
1. $a=1,~b=1$ 得结果为 $1$ （$a$ 为 $1$，$b$ 一定要是 $1$）
2. $a=1,~b=0$ 得结果为 $0$
3. $a=0,~b=1$ 得结果为 $1$ （$a$ 不为 $1$，$b$ 为几都成立）
4. $a=1,~b=1$ 得结果为 $1$

可以发现，要么 $a$ 为 $0$，要么 $b$ 为 $1$，结果才能成立，因此得出 $a \rightarrow b \Leftrightarrow a \wedge b$，反之得出 $a \wedge b \Leftrightarrow -a \rightarrow b \Leftrightarrow -b \rightarrow a \Leftrightarrow b \wedge a$。

我们通过 $a \wedge b$ 和 $b \wedge a$ 得出两个推导公式 $-a \rightarrow b$ 和 $-b \rightarrow a$，我们就可以把这两个关系看作图论中的边，对于 $a \wedge b$，我们从 $-a$ 向 $b$ 连一条边，从 $-b$ 向 $a$ 连一条边，这两条边刚好对应两个推导公式。

通过上述方式，我们能将整个问题转化成一张有向图，每个变量的两种取值对应两个节点，每个条件对应两条边。这样对于图中一条路径 $a \rightarrow b \rightarrow c$，就表示如果 $a$ 取 $1$，那么一路上 $b$ 和 $c$ 都要取 $1$。因此图中任意一条路径都能对应原题的一段对照关系，而且这个对照关系是具有传递性的。

转化完之后，先考虑什么时候会无解，如果从 $x_1$ 沿着边走，会走到 $-x_1$，并且从 $-x_1$ 沿着边走，会走到 $x_1$，这意味着如果 $x_1$ 取 $1$，那么我们会推导出来 $x_1$ 取 $0$，反之如果 $x_1$ 取 $0$，那么我们会推导出来 $x_1$ 取 $1$。所以能得出 $x_1$ 不存在一个合理的取值，此时就一定无解。所以得出结论，如果 $x_i$ 和 $-x_i$ 能相互到达，即在同一个强连通分量中时，就一定无解。这是无解的一个必要条件。

那么如果规避这个必要条件，如果任意一个变量的真值和假值不在同一个强连通分量中，那么是不是一定有解呢？

这里用构造法，如果任意一个变量的真值和假值在不同的强连通分量里的话，我们用一个特定的方式去构造一组合法的解。首先在求完强连通分量后进行缩点，这样原图就变成一个拓扑图，并求一下拓扑图的拓扑排序，我们可以按照任意顺序枚举所有命题，然后看一下 $x_i$ 和 $-x_i$ 所在的强连通分量，我们看一下这两个强连通分量在拓扑排序中哪一个更靠前哪一个更靠后，我们每次都选择所在强连通分量更靠后的一个取值，就能得出一组合法的解。

而在我们求完强连通分量并缩点后，所有强连通分量的编号其实就是拓扑排序的逆序（具体请看强连通分量相关证明），所以对于每个变量，我们要想知道哪个取值在拓扑排序中更靠后，我们只需要看哪个取值所在的强连通分量编号更靠前，因为是倒序，所以编号越小越靠后。

为什么这样构造是正确的呢，首先确定每个变量都只有一种取值，然后对于一个强连通分量，如果选了这个连通分量中的一个点，那么由于推导关系，就需要把该连通分量中的其他点都选上，我们要看一下按照这个构造方法是否能满足这个要求。

对于任意一个命题都存在一个与它等价的逆否命题，即 $a \rightarrow b \Leftrightarrow -b \rightarrow -a$。由于这个性质，我们可以发现，如果存在一个强连通分量，其中 $a$ 能走到 $b$，$b$ 能走到 $a$。那么一定存在一个与之对应的强连通分量，其中 $-a$ 能走到 $-b$，$-b$ 能走到 $-a$。因此我们建的有向图中所有的强连通分量一定都是成对出现的。由于两个强连通分量的关系是等价的，等于是两个方案，我们只需要选其一即可，而这两个强连通分量在拓扑排序中一定会有一个先后顺序，靠后的那个强连通分量中所有变量 $x_i$ 在拓扑序中的顺序也一定比对应的反变量 $-x_i$ 靠后，这就能保证我们一定能选到同一个强连通分量中的变量。按照这个方式其实能构造出两组合法解，每次选靠后的取值能得出一组合法解，按照这个原理每次选靠前的取值也一定能得出一组合法解。

最后我们再回归原题，我们证明 $a \wedge b$ 的合法性，即如果 $a$ 取 $0$，则 $b$ 一定取 $1$。如果我们取了 $-a$，就意味着 $-a$ 所在的强连通分量比 $a$ 所在的强连通分量更靠后，根据我们的建图方式，$-a$ 会连向 $b$，$-b$ 会连向 $a$，所以 $b$ 和 $-a$ 在同一个强连通分量中，$-b$ 和 $a$ 在同一个强连通分量中，所以 $b$ 所在的强连通分量也比 $-b$ 所在的强连通分量更靠后，所以就会取 $b$，即 $b$ 取 $1$。

综上所述，我们证明能用强连通分量求 2-SAT 问题，并且得出构造合法解的方法。由于用 Tarjan 算法能在线性复杂度 $O(NM)$ 内求强连通分量，所以一般 2-SAT 问题的时间复杂度也是线性的。

注意： 在一般的 2-SAT 问题中，通常不会给出 $a \wedge b$ 这样直接的关系，这里给出常见的几种条件和转化方式

$$a \wedge b = \begin{cases} a \wedge b \newline a \rightarrow b \Leftrightarrow -a \wedge b \newline a = 1 \Leftrightarrow a \wedge a \newline a = 0 \Leftrightarrow -a \wedge -a \end{cases}$$