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.
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.

Ancestors (10)

  1. Boolean formula
  2. Boolean satisfiability problem
  3. NP-completeness
  4. NP-hardness
  5. Polynomial-time many-one reduction
  6. Polynomial-time reduction
  7. Computational complexity theory
  8. Theoretical computer science
  9. Computer science
  10. Home

Synonyms (1)

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.