Conjunctive normal form (CNF) is a standard representation of a logical formula as a conjunction of clauses, where each clause is a disjunction of literals. In propositional logic, a literal is a propositional variable or its negation. Thus, a CNF formula is an “AND of ORs,” such as
Every formula of classical propositional logic has a logically equivalent CNF formula, although obtaining one without introducing additional variables can require an exponential increase in size. CNF is a central representation in Boolean algebra, automated theorem proving, and algorithms for the Boolean satisfiability problem.
Definition and conventions
A propositional CNF formula has the general form
where each is a literal. A positive literal is a variable ; a negative literal is its negation .
A truth assignment satisfies a clause if at least one of its literals is true. It satisfies the entire formula if every clause is satisfied. Consequently:
- A single literal, such as , is a unit clause and is itself a CNF formula.
- A single disjunction, such as , is a CNF formula with one clause.
- A conjunction of literals, such as , is a CNF formula whose clauses are all unit clauses.
- A formula such as is not syntactically in CNF, even though it has an equivalent CNF representation.
Two conventions make the definition work uniformly for constant truth values:
- The conjunction of no clauses is true.
- A clause containing no literals is false.
Therefore, a CNF formula containing an empty clause is unsatisfiable.
Clauses are often treated as sets of literals, and a CNF formula as a set of clauses. This suppresses ordering and repetition: represents the same clause as . A clause containing both and is tautological and can be removed from a conjunction without changing its truth value.
CNF is a syntactic form, not a guarantee of simplicity or uniqueness. Many different CNF formulas can represent the same Boolean function.
Conversion by logical equivalences
A standard conversion procedure first eliminates connectives other than conjunction, disjunction, and negation:
Negations are then moved inward using De Morgan’s laws and double-negation elimination:
The resulting formula, in which negation applies only to variables, is in negation normal form.
Finally, disjunction is distributed over conjunction:
For example,
Similarly,
These transformations preserve truth under every assignment to the original variables. They rely on classical logic; unrestricted double-negation elimination, in particular, is not valid in intuitionistic logic.
Exponential growth
Distribution can produce many clauses. Consider
where all variables are distinct. Distributing disjunction over conjunction yields
There are clauses, one for each choice of one variable from every pair.
For this family, the growth is unavoidable if the CNF must be logically equivalent and use only the original variables. Thus, the difficulty is not merely an inefficient implementation of distribution: some Boolean functions have compact formulas but require exponentially large CNF representations over the same variables.
Canonical conjunctive normal form
A canonical CNF, also called a principal conjunctive normal form, can be constructed directly from a truth table.
Fix a finite list of variables. For each assignment at which the formula is false, construct a clause that is false on precisely that assignment:
- If a variable is false in the assignment, include it positively.
- If a variable is true in the assignment, include its negation.
The conjunction of these clauses represents the original Boolean function.
For example, suppose is false exactly when
The corresponding clauses are and , giving
This is the exclusive OR of and .
Each canonical clause contains every variable exactly once and is often called a maxterm. For a fixed variable list, canonical CNF is unique up to ordering and repetition. Ordinary CNF is not canonical: it can contain shorter clauses and may be much more compact.
The dual representation is disjunctive normal form (DNF), an OR of ANDs of literals. Canonical DNF is constructed from the true rows of a truth table, whereas canonical CNF is constructed from the false rows.
Compact encodings with auxiliary variables
In satisfiability applications, preserving the existence of a satisfying assignment is often sufficient; exact equivalence over the original variable set is not required. This permits compact encodings that introduce new variables.
The standard example is the Tseitin transformation, associated with Grigori Tseitin’s work in the 1960s. It introduces a variable for each relevant compound subformula and adds clauses expressing the variable’s relationship to that subformula.
For instance, the definition
is expressed by
Likewise,
is expressed by
A unit clause asserts the variable representing the whole formula. For formulas built from bounded-arity connectives, the resulting number of clauses and literal occurrences is linear in the size of the represented formula.
Equivalence versus equisatisfiability
If is the original formula and is a full definitional encoding, then
Here the existential notation means that suitable Boolean values can be assigned to the auxiliary variables.
Thus, an assignment to the original variables satisfies exactly when it can be extended to satisfy . However, and are not ordinarily called logically equivalent formulas over their combined free-variable set: additionally constrains the auxiliary variables.
The weaker property of equisatisfiability means only that either both formulas have a satisfying assignment or neither does. Full definitional encodings preserve more information than this weaker condition: each satisfying assignment of the original formula has a unique extension to the defined auxiliary variables. Other satisfiability-preserving encodings need not have this uniqueness property, which matters when counting satisfying assignments.
Satisfiability and restricted clause classes
CNF-SAT asks whether a given CNF formula has a satisfying assignment. It is NP-complete. Restricting clause structure can, however, change the computational complexity substantially.
| Class | Restriction | Satisfiability |
|---|---|---|
| 1-CNF | At most one literal per clause | Solvable in linear time |
| 2-CNF | At most two literals per clause | Solvable in linear time |
| 3-CNF | At most three literals per clause | NP-complete |
| Horn CNF | At most one positive literal per clause | Solvable in linear time |
| Dual-Horn CNF | At most one negative literal per clause | Solvable in linear time |
Time bounds here are measured in the total input size.
For 2-CNF, a clause can be represented by the implications
A directed graph of these implications allows satisfiability to be decided through its strongly connected components: the formula is unsatisfiable exactly when some variable and its negation belong to the same component.
A Horn clause can often be read as a rule. For example,
is equivalent to
This structure supports efficient forward-chaining procedures.
The phrase “-CNF” can mean either clauses of at most literals or clauses of exactly literals, depending on convention. The distinction should be stated explicitly, especially when repeated literals are forbidden.
Resolution and SAT solving
CNF is particularly suited to resolution, a rule that derives
from
where and stand for disjunctions of other literals.
For example, resolving
produces . Deriving the empty clause demonstrates unsatisfiability. Propositional resolution is refutation-complete: every unsatisfiable finite clause set has a resolution derivation of the empty clause. Such derivations can nevertheless be exponentially long.
Practical SAT solvers exploit CNF through operations such as:
- Unit propagation: a unit clause forces its literal to be true; the assignment can simplify other clauses and produce further unit clauses.
- Branching: a variable is assigned tentatively when propagation alone does not decide the problem.
- Conflict analysis and clause learning: a conflict is analyzed to derive a clause that prevents related unsuccessful assignments.
- Backtracking and restarts: the solver revises its search while retaining useful learned information.
CNF serves as a common target representation for formal verification, planning, configuration, and constraint encodings. It does not by itself remove the underlying worst-case difficulty. Different encodings of the same problem can also lead to very different solver performance.
First-order clausal form
In first-order logic, literals are atomic formulas or their negations, rather than merely propositional variables. For example,
is a first-order clause.
Conversion to clausal form generally includes eliminating implications, moving negations inward, renaming bound variables where necessary, and handling quantifiers. Skolemization removes existential quantifiers by introducing new constants or function symbols that represent witnesses. Remaining variables in a clause set are conventionally understood as universally quantified.
For example,
has the Skolemized form
The resulting clause is , with implicitly universally quantified.
Skolemization preserves satisfiability in an expanded vocabulary, not ordinary logical equivalence in the original vocabulary. This is distinct from propositional conversion by distribution, which preserves equivalence without changing the variable set. First-order resolution also requires unification to match terms across clauses.