一、SAT问题以及2-SAT问题的定义
SAT问题就是给出n个bool变量，(变量只可能是0或1)。m个限制条件。限制条件的描述可能为a₁ and a₂ = 1, a₂ or a₃ xor a₄ = 0等，要求构造出一个合法的包含n个bool元素的序列，满足所有的限制条件。
退而求其次，2-SAT问题同SAT问题的条件几乎一样，唯一不同的是对于所有的限制条件只会描述2个bool变量，比如a₁ and a₂ = 1, a₂ or a₃ = 0等。
二、实际问题
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 问题的目标是给每个变量赋值使得所有条件得到满足。