SAT 3-SAT
Key Idea: use boolean logic to convert SAT in to the form of 3-SAT, since they are logically equivalent, hence the iff relationship.
Example: consider this SAT , convert it into a parse tree.
similar to the gate in Circuit SAT, we treat each node as a gate and convert the tree into the following formula:
Note that variable is created by us, they do not exists in the original SAT formula, unlike the circuit-SAT, in here, the clause are not always true, because is not the real outcome, it is just like some dummy variable, so we have to construct a truth table, to determine which value makes the clause to evaluate to true.
use those value equals in the truth table to construct DNF, and then use DeMorgan’s Law to convert it to CNF, add dummy variable if needed, then the formula is in the form of 3-SAT.
Take for example, according truth table, the DNF form is
which always evaluated to .
convert it into CNF using DeMorgan’s Law, which always evaluate to . The CNF form is
in this case, the 3-SAT form is satisfied.
If the clause after converting to CNF has less than 3 variable, then we can use the following technique to convert it into 3-SAT form. For those that only have : . For those that only have 1:
Since are all dummies, SAT is satisfiable 3-SAT is satisfiable.
Links
Reference
- Introduction to Algorithm