2-SAT

(k-SAT) 是 k-适应性问题（Satisfiability）的简称。
(k-SAT) 问题（除 (k = 2)）已被证明为是 (NP) 完全问题， 而对于 (k = 2) 的 (2-SAT) 问题， 我们可以用图论求解。
(k-SAT) 与 (2-SAT) 最大的不同在与这个(2) 废话， 就因为这个 “2”， 我们可以由假设的第一个限制条件推知第二个限制条件
举个栗子： 限制条件为 (a) ^ $b = 1 $ 有
[ a xor b = 1 Rightarrow left{ begin{aligned} a = 1 Rightarrow b = 0 a = 0 Rightarrow b = 1 end{aligned} right. ]
依据限制条件， 我们可以搞一个通式有助后边理解： (a = x) 则 (b = y) （a、 b、 x 已知且 (x,y in {0,1}) ）
于是， 我们把问题转换到图中：引入一条有向边， 起点为通式则的左边， 终点为则右边， 这条边的意义为 必须选中， 即选择了起点就必须选择终点。
以上文的限制条件为例，我们将 x 变量为假设为 x ， x 变量为真设为 x‘ ， 可以作如下转换：
[ a xor b = 1 Rightarrow left{ begin{aligned} a' rightarrow b a rightarrow b' end{aligned} right. ]