SAT 问题（布林可满足性问题）
定义：SAT问题是判定一个命题公式是否可满足的问题，通常这个命题公式是CNF公式。（the Boolean Satisfiability Problem）
CNF公式：C1 ∧… ∧ Cm为CNF公式，其中∧是逻辑上的合取连接词，Ci是子句； CNF公式也常被表示为子句的集合。
子句：l1∨… ∨ lk形式的式子称为子句，其中∨是逻辑上的析取连接词， li是文字；子句也常被表示为文字的集合。
文字：布尔变量x和布尔变量的非﹁x称为文字。
那么，SAT问题可以简化为：给定一个CNF公式F，判定它是否存在一个赋值t，使得t(F)=1。
SAT 问题通常被视为NPC问题（NPC(Nondeterministic Polynomial Complete)问题：只有把解域里面的所有可能都穷举了之后才能得出答案）
缺点：这类问题的求解，
- Truth table assisgnment grows exponentially。
- Important SAT problems have thousands of variables
Solution：对于 (p→q)→(r ∧ ¬(p ∨ ¬s))，先转化为Negation Normal Form，得到
(p ∧ ¬q) ∨ (r ∧ (¬p ∨ s))。再转化成Conjunctive Normal Form，得到(p ∨ r) ∧ (p ∨ ¬p ∨ s) ∧ (¬q ∨ r) ∧ (¬q ∨ ¬p ∨ s)。
常用：A↔B equivalent to (A∧B)∨(¬A∧¬B)，A→B equivalent to ¬A∨B
最后，通过方法{（p1 ∨ ... ∨ pn ∨ q）∨（¬q ∨ r1 ∨ ... ∨ rm） 等于 p1 ∨ ... ∨ pn ∨ r1 ∨ ... ∨ rm } deduce the unsatisfiable/satisfiable
Unit propagation
Definition: a procedure of automated theorem proving that can simplify a set of (usually propositional) clauses.
Iterating these inference moves is unit propagation
DPLL: a better way to solve the SAT Problem
它是一个回溯搜索算法
基本思想: 每次选中一个未被赋值的变量进行赋值，然后判断该赋值是否满足整个公式：
满足：结束搜索；
导致冲突（某个子句为0）：回溯；
否则：对下一个变量进行赋值
improve the DPLL:
1.Clause learning
2.Choosing good atoms for branching
3.Intelligent backtracking
4.Restarts
存在quantifiers（existential，universal）的logic formula
先将其化为 Prenex normal form（quantifiers are outside），再Removing the quantifiers（Variable replaced by a new name or function，delete existential and universal）最后调整为clause form，通过substituting terms for variables in order to make literals match，就可以正常推理了。
Example:
Γ = { ∀x(¬Q(x) → P(x)), ¬∃y P (y), Q(a) → ∃x(R(x) ∧ ¬Q(x)) }
1.Use normal-forming moves to transform Γ into a set ∆ of first order clauses such that ∆ is satisfiable if and only if Γ is satisfiable.
First get the quantifiers to the front (prenex normal form):
∀x(¬Q(x) → P(x)),
∀y ¬P (y),
∃x(Q(a) → (R(x) ∧ ¬Q(x)))
Next remove the existential quantifier and use a name (skolem constant) instead:
∀x(¬Q(x) → P(x)),
∀y ¬P (y),
Q(a) → (R(b) ∧ ¬Q(b))
Delete the universal quantifiers, and put the propositional parts into clause form:
∆ = { Q(x)∨P(x), ¬P (y), ¬Q(a) ∨ R(b), ¬Q(a) ∨ ¬Q(b) }
2.Write out a resolution proof by which the empty clause is derived from ∆. For each resolution inference in the proof, make a note of any unifier that is involved.
1. Q(x) ∨ P (x) given
2. ¬P(y) given
3. Q(x) from 1, 2 unifier {y ← x}
4. ¬Q(a) ∨ ¬Q(b) given
5. ¬Q(b) from 3, 4 {x ← a}
6. ⊥ from 3, 5 {x ← b}
