quality:corruption, structural:summarization, linguistic:translation
Conjunctive normal form

A literal is either a variable (in which case it is called a positive literal) or the negation of a variable (called a negative literal). A clause is a disjunction of literals (or a single literal). A clause is called a Horn clause if it contains at most one positive literal. A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses (or a single clause).

For example, x is a positive literal, ¬ x is a negative literal, and x ∨ ¬ x is a clause. The formula (x ∨ ¬ x) ∧ (¬ x ∨ x ∨ x) ∧ ¬ x is in conjunctive normal form; its first and third clauses are Horn clauses, but its second clause is not. The formula is satisfiable, by choosing x = FALSE, x = FALSE, and x arbitrarily, since (FALSE ∨ ¬FALSE) ∧ (¬FALSE ∨ FALSE ∨ x) ∧ ¬FALSE evaluates to (FALSE ∨ TRUE) ∧ (TRUE ∨ FALSE ∨ x) ∧ TRUE, and in turn to TRUE ∧ TRUE ∧ TRUE (i.e. to TRUE). In contrast, the CNF formula a ∧ ¬ a, consisting of two clauses of one literal, is unsatisfiable, since for a =TRUE or a =FALSE it evaluates to TRUE ∧ ¬TRUE (i.e., FALSE) or FALSE ∧ ¬FALSE (i.e., again FALSE), respectively.

For some versions of the SAT problem, it is useful to define the notion of a generalized conjunctive normal form formula, viz. as a conjunction of arbitrarily many generalized clauses, the latter being of the form R (l,..., l) for some Boolean function R and (ordinary) literals l. Different sets of allowed Boolean functions lead to different problem versions. As an example, R (¬ x, a, b) is a generalized clause, and R (¬ x, a, b) ∧ R (b, y, c) ∧ R (c, d,¬ z) is a generalized conjunctive normal form. This formula is used below, with R being the ternary operator that is TRUE just when exactly one of its arguments is.

Using the laws of Boolean algebra, every propositional logic formula can be transformed into an equivalent conjunctive normal form, which may, however, be exponentially longer. For example, transforming the formula (x ∧ y) ∨ (x ∧ y) ∨... ∨ (x ∧ y) into conjunctive normal form yields

while the former is a disjunction of n conjunctions of 2 variables, the latter consists of 2 clauses of n variables.

However, with use of the Tseytin transformation, we may find an equisatisfiable conjunctive normal form formula with length linear in the size of the original propositional logic formula.