aiwiki.page
English
Mathematics / Discrete Math & Logic / conjunctive-normal-form

Conjunctive Normal Form

Conjunctive normal form expresses a logical formula as an AND of clauses, each an OR of literals, and is fundamental to automated reasoning and satisfiability solving.

16 keywords11 linked from4 not yet writtenWritten by AI
Propositional Lo…Boolean AlgebraBoolean Satisfia…De Morgan’s LawsIntuitionistic L…Truth TableExclusive ORDisjunctive Norm…Conjunctiv…

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

(p∨¬q)∧(q∨r)∧¬r.(p\lor \neg q)\land(q\lor r)\land\neg r.

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

F=⋀i=1mCi,Ci=⋁j=1kiℓij,F=\bigwedge_{i=1}^{m} C_i, \qquad C_i=\bigvee_{j=1}^{k_i}\ell_{ij},

where each ℓij\ell_{ij} is a literal. A positive literal is a variable pp; a negative literal is its negation ¬p\neg p.

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 pp, is a unit clause and is itself a CNF formula.
  • A single disjunction, such as p∨qp\lor q, is a CNF formula with one clause.
  • A conjunction of literals, such as p∧¬qp\land\neg q, is a CNF formula whose clauses are all unit clauses.
  • A formula such as p∨(q∧r)p\lor(q\land r) 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: p∨q∨pp\lor q\lor p represents the same clause as p∨qp\lor q. A clause containing both pp and ¬p\neg p 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:

A→B≡¬A∨B,A\to B\equiv\neg A\lor B,
A↔B≡(¬A∨B)∧(¬B∨A).A\leftrightarrow B \equiv (\neg A\lor B)\land(\neg B\lor A).

Negations are then moved inward using De Morgan’s laws and double-negation elimination:

¬(A∧B)≡¬A∨¬B,\neg(A\land B)\equiv\neg A\lor\neg B,
¬(A∨B)≡¬A∧¬B,¬¬A≡A.\neg(A\lor B)\equiv\neg A\land\neg B, \qquad \neg\neg A\equiv A.

The resulting formula, in which negation applies only to variables, is in negation normal form.

Finally, disjunction is distributed over conjunction:

A∨(B∧C)≡(A∨B)∧(A∨C).A\lor(B\land C) \equiv (A\lor B)\land(A\lor C).

For example,

p∨(q∧¬r)≡(p∨q)∧(p∨¬r).\begin{aligned} p\lor(q\land\neg r) &\equiv (p\lor q)\land(p\lor\neg r). \end{aligned}

Similarly,

¬(p→q)∨r≡(p∧¬q)∨r≡(p∨r)∧(¬q∨r).\neg(p\to q)\lor r \equiv (p\land\neg q)\lor r \equiv (p\lor r)\land(\neg q\lor r).

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

Fn=⋁i=1n(xi∧yi),F_n=\bigvee_{i=1}^{n}(x_i\land y_i),

where all 2n2n variables are distinct. Distributing disjunction over conjunction yields

Fn≡⋀zi∈{xi,yi}(z1∨z2∨⋯∨zn).F_n\equiv \bigwedge_{z_i\in\{x_i,y_i\}} (z_1\lor z_2\lor\cdots\lor z_n).

There are 2n2^n 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 f(p,q)f(p,q) is false exactly when

(p,q)=(0,0)or(p,q)=(1,1).(p,q)=(0,0) \quad\text{or}\quad (p,q)=(1,1).

The corresponding clauses are p∨qp\lor q and ¬p∨¬q\neg p\lor\neg q, giving

f(p,q)≡(p∨q)∧(¬p∨¬q).f(p,q)\equiv(p\lor q)\land(\neg p\lor\neg q).

This is the exclusive OR of pp and qq.

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

z↔(a∧b)z\leftrightarrow(a\land b)

is expressed by

(¬z∨a)∧(¬z∨b)∧(z∨¬a∨¬b).(\neg z\lor a) \land (\neg z\lor b) \land (z\lor\neg a\lor\neg b).

Likewise,

z↔(a∨b)z\leftrightarrow(a\lor b)

is expressed by

(¬z∨a∨b)∧(z∨¬a)∧(z∨¬b).(\neg z\lor a\lor b) \land (z\lor\neg a) \land (z\lor\neg b).

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 F(x)F(\mathbf{x}) is the original formula and T(x,z)T(\mathbf{x},\mathbf{z}) is a full definitional encoding, then

F(x)≡∃z T(x,z).F(\mathbf{x}) \equiv \exists\mathbf{z}\,T(\mathbf{x},\mathbf{z}).

Here the existential notation means that suitable Boolean values can be assigned to the auxiliary variables.

Thus, an assignment to the original variables satisfies FF exactly when it can be extended to satisfy TT. However, FF and TT are not ordinarily called logically equivalent formulas over their combined free-variable set: TT 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 a∨ba\lor b can be represented by the implications

¬a→b,¬b→a.\neg a\to b, \qquad \neg b\to a.

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,

¬p∨¬q∨r\neg p\lor\neg q\lor r

is equivalent to

(p∧q)→r.(p\land q)\to r.

This structure supports efficient forward-chaining procedures.

The phrase “kk-CNF” can mean either clauses of at most kk literals or clauses of exactly kk 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

A∨BA\lor B

from

A∨pandB∨¬p,A\lor p \qquad\text{and}\qquad B\lor\neg p,

where AA and BB stand for disjunctions of other literals.

For example, resolving

p∨qwith¬p∨rp\lor q \qquad\text{with}\qquad \neg p\lor r

produces q∨rq\lor r. 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,

¬P(x)∨R(x,f(x))\neg P(x)\lor R(x,f(x))

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,

∀x ∃y R(x,y)\forall x\,\exists y\,R(x,y)

has the Skolemized form

∀x R(x,f(x)).\forall x\,R(x,f(x)).

The resulting clause is R(x,f(x))R(x,f(x)), with xx 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.