A Boolean formula is in conjunctive normal form when it is a logical conjunction of Boolean clauses. It is true precisely when every Boolean clause is true under the same Boolean valuation; an empty logical conjunction is true. For example, has two Boolean clauses with widths two and one. Width counts Boolean literal occurrences within a Boolean clause, whereas the Boolean clause count counts the conjuncts. 2-SAT bounds width by two, and 3-SAT bounds width by three. A Boolean formula with an empty Boolean clause is an unsatisfiable Boolean formula.
A Boolean formula in conjunctive normal form with at most three Boolean literals per Boolean clause. A shorter nonempty Boolean clause can be padded by repeating a Boolean literal. The corresponding Boolean satisfiability problem is 3-SAT.
A Boolean formula in conjunctive normal form with at most two Boolean literals per Boolean clause. Shorter Boolean clauses are allowed. The Boolean satisfiability problem restricted to these Boolean formulas is 2-SAT.
Introduce a Boolean variable for each gate output and impose its equivalence to the gate's input function with a constant number of clauses. A final unit clause forces acceptance. For a bounded-fan-in Boolean circuit, the formula size is linear in the gate count and it is satisfiable exactly when some input makes the Boolean circuit output one. Auxiliary variables extend the satisfying assignments; this is equisatisfiability, not equality as functions of the enlarged variable set.
Articles by others on the same topic
There are currently no matching articles.