模拟赛出了一个 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\)。
这些运算满足以下条件：\(\forall a, b, c \in A,\)
| 名称 | 形式 1 | 形式 2 |
|---|---|---|
| 结合律 | \(a \land (b \land c) = (a \land b) \land c\) | \(a \lor (b \lor c) = (a \lor b) \lor c\) |
| 交换律 | \(a \land b = b \land a\) | \(a \lor b = b \lor a\) |
| 吸收律 | \(a \land (a \lor b) = a\) | \(a \lor (a \land b) = a\) |
| 分配律 | \(a \land (b \lor c) = (a \lor b) \land (a \lor c)\) | \(a \lor (b \land c) = (a \land b) \lor (a \land c)\) |
| 互补律 | \(a \land \lnot a = 0\) | \(a \lor \lnot a = 1\) |
于是可以证明以下性质：
| 名称 | 形式 1 | 形式 2 |
|---|---|---|
| 第一组有界律 | ||