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

Disjunctive Normal Form

Disjunctive normal form expresses a Boolean formula as a disjunction of conjunctions of literals, providing a standard representation for logical analysis and digital circuit design.

12 keywords3 linked fromWritten by AI
Propositional Lo…Boolean AlgebraExclusive ORTruth TableDe Morgan’s LawsDouble-Negation…IdempotenceMathematical opt…Disjunctiv…

In propositional logic, disjunctive normal form (DNF) is a way of writing a formula as a disjunction (“OR”) of one or more conjunctions (“ANDs”) of literals, where a literal is a propositional variable or its negation. For example, (p∧¬q)∨(q∧r)(p\land\neg q)\lor(q\land r) is in DNF. Every Boolean function of finitely many variables can be represented in this form, although the representation need not be unique or compact. DNF is used in logical reasoning, Boolean algebra, and digital circuit design.

Definition and notation

A DNF formula has the general form

F=⋁i=1m(⋀j=1kiℓij),F=\bigvee_{i=1}^{m}\left(\bigwedge_{j=1}^{k_i}\ell_{ij}\right),

where each ℓij\ell_{ij} is a literal. The symbols ∨\lor, ∧\land, and ¬\neg denote disjunction, conjunction, and negation, respectively. Each conjunction is called a term or product term.

For instance,

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

is in DNF. A single literal counts as a term, so the final disjunct need not contain an explicit conjunction. A single conjunction, such as p∧¬qp\land\neg q, also qualifies as DNF.

By contrast,

p∧(q∨r)p\land(q\lor r)

is not syntactically in DNF because a disjunction occurs inside a conjunction. It is logically equivalent to the DNF formula

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

Negation in DNF applies only to individual variables. Thus, ¬(p∧q)\neg(p\land q) is not itself in DNF, even though it can be converted to ¬p∨¬q\neg p\lor\neg q.

In switching algebra, conjunction is often written as multiplication, disjunction as addition, and negation with an overbar. Under this notation,

pq+p‾rpq+\overline{p}r

is a sum of products. Here “addition” means Boolean OR, not ordinary arithmetic addition and not exclusive OR.

Constants and empty expressions

It is useful to allow an empty disjunction to denote false and an empty conjunction to denote true:

⋁∅=⊥,⋀∅=⊤.\bigvee\varnothing=\bot, \qquad \bigwedge\varnothing=\top.

With these conventions, constant Boolean functions have DNF representations without special exceptions. If empty expressions are excluded, equivalent representations include p∧¬pp\land\neg p for false and p∨¬pp\lor\neg p for true.

Logical meaning

A DNF formula is true precisely when at least one of its terms is true. Each term specifies a sufficient condition for the whole formula.

For example,

F=(p∧¬q)∨rF=(p\land\neg q)\lor r

is true whenever pp is true and qq is false, or whenever rr is true. Its terms can overlap: an assignment may satisfy both simultaneously.

A conjunction of literals fixes the values of the variables it mentions and leaves other variables unrestricted. For a fixed collection of nn variables, a consistent term mentioning kk distinct variables therefore describes 2n−k2^{n-k} assignments. A DNF formula represents the union of the assignment sets described by its terms.

This gives a geometric interpretation on the Boolean cube {0,1}n\{0,1\}^n: each consistent term describes a subcube, and a DNF representation covers exactly those vertices where the function is true.

Canonical disjunctive normal form

A minterm over a specified set of variables is a conjunction in which every variable appears exactly once, either positively or negatively. Each minterm is true on exactly one assignment.

For variables p,q,rp,q,r, the minterm

p∧¬q∧rp\land\neg q\land r

corresponds to the assignment (p,q,r)=(1,0,1)(p,q,r)=(1,0,1).

The canonical DNF, also called full DNF or principal DNF, of a Boolean function is the disjunction of the minterms corresponding to all assignments on which the function is true. It can be constructed directly from a truth table:

  1. Select every row whose output is true.
  2. For each selected row, form a conjunction containing a variable positively if its value is true and negatively if its value is false.
  3. Take the disjunction of those conjunctions.

For example, the exclusive OR of two variables is true on (1,0)(1,0) and (0,1)(0,1), giving

p⊕q≡(p∧¬q)∨(¬p∧q).p\oplus q \equiv (p\land\neg q)\lor(\neg p\land q).

For a fixed variable set, canonical DNF is unique apart from the ordering of terms and literals. General DNF is not unique. For example,

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

The right-hand side is canonical over the variable set {p,q}\{p,q\}; the left-hand side is a shorter DNF for the same function.

Canonical DNF is not generally a minimal representation. For example, the constant true function has 2n2^n minterms over nn variables, although it can be represented simply by ⊤\top.

Conversion to DNF

Every formula of classical propositional logic has an equivalent DNF. One construction proceeds through standard logical equivalences.

Eliminate derived connectives

Implication and biconditional can first be rewritten using negation, conjunction, and disjunction:

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

Move negations inward

De Morgan’s laws transform negated conjunctions and disjunctions:

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

Together with double-negation elimination, these produce a formula in which negations apply only to variables.

Distribute conjunction over disjunction

Repeatedly apply

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

For example,

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

The contradictory term p∧¬pp\land\neg p has been removed. The remaining expression is in DNF, but it is not minimal: the term q∧rq\land r is redundant, leaving

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

Truth-table construction provides an alternative conversion method and directly produces canonical DNF.

Simplification and minimization

A DNF expression can often be shortened using Boolean identities:

  • Contradiction: a term containing both pp and ¬p\neg p is always false and can be removed.
  • Idempotence: repeated literals or repeated terms can be deleted.
  • Absorption: A∨(A∧B)≡AA\lor(A\land B)\equiv A.
  • Combination: (A∧p)∨(A∧¬p)≡A(A\land p)\lor(A\land\neg p)\equiv A.

An implicant of a function FF is a consistent product term TT such that every assignment satisfying TT also satisfies FF. A prime implicant is an implicant from which no literal can be deleted while preserving this property.

An irredundant DNF contains no term that can be removed without changing the represented function. Irredundancy does not imply global minimality: another collection of terms may represent the same function more economically.

Minimization requires a cost criterion. Minimizing the number of terms, minimizing the total number of literal occurrences, and minimizing physical circuit cost are different optimization problems and need not yield the same preferred representation.

Karnaugh maps provide a visual method for simplifying functions with a small number of variables. The Quine–McCluskey algorithm systematically generates prime implicants and selects a covering collection. Larger practical problems commonly use heuristic methods because exact minimization can be computationally expensive.

Representation size and computational properties

Conversion to DNF can cause an exponential increase in formula size. Consider

Fn=⋀i=1n(xi∨yi).F_n=\bigwedge_{i=1}^{n}(x_i\lor y_i).

Distributing conjunction over disjunction produces 2n2^n terms, one for each choice of xix_i or yiy_i from every pair.

For this family, the increase is unavoidable for equivalent DNF formulas over the same variables. Consider the 2n2^n satisfying assignments that set exactly one variable in each pair to true. Any consistent term implying FnF_n must contain at least one positive literal from each pair; otherwise, some pair could be set entirely false while satisfying the term. Consequently, such a term can cover at most one of these assignments. At least 2n2^n terms are therefore necessary.

Several reasoning tasks have markedly different behavior on DNF:

  • Satisfiability is easy to test: a DNF is satisfiable if at least one term contains no complementary pair of literals.
  • Falsity is easy to test: a DNF is identically false if every term is contradictory.
  • Tautology testing is harder: determining whether an arbitrary DNF is true on every assignment is coNP-complete.
  • Exact model counting can be difficult: terms may overlap, so adding the numbers of assignments satisfying individual terms generally overcounts.

Canonical DNF avoids overlap because distinct minterms describe distinct assignments, but its explicit size may already be exponential in the number of variables.

Relationship to other normal forms

Conjunctive normal form (CNF) reverses the arrangement: it is a conjunction of disjunctions of literals. DNF emphasizes alternative sufficient conditions; CNF emphasizes conditions that must all hold.

Negation exchanges the two forms. Negating a DNF and applying De Morgan’s laws produces a CNF for the negated function:

¬((p∧q)∨(¬p∧r))≡(¬p∨¬q)∧(p∨¬r).\neg\bigl((p\land q)\lor(\neg p\land r)\bigr) \equiv (\neg p\lor\neg q)\land(p\lor\neg r).

Neither form is uniformly more compact. Some functions have short CNFs but require large DNFs; others have short DNFs but require large CNFs.

DNF also differs from algebraic normal form, which uses exclusive OR of products rather than ordinary OR. Since exclusive OR permits cancellation, algebraic normal form has different identities and representation properties.

The universal conversion result is a result of classical Boolean logic. It does not transfer unchanged to intuitionistic logic, where principles such as p∨¬pp\lor\neg p are not generally valid.

Development and applications

DNF belongs to the algebraic study of logic associated with George Boole. Its interpretation as a sum of products became central to switching theory and digital circuit design, in which Boolean operations describe networks of switches and logic gates.

A DNF naturally specifies a two-level AND–OR circuit: one layer computes product terms, and another combines their outputs. Negated inputs may require additional inverters. Equivalent representations can nevertheless differ in gate count, wiring, delay, and susceptibility to transient hazards, so minimum symbolic size is not the only design consideration.

In rule-based systems, each term can represent a sufficient rule condition, while the disjunction collects alternative ways for a conclusion to hold. In database filtering, DNF can organize alternative combinations of selection conditions. Such applications require attention to semantics: database null values, for example, can introduce behavior beyond ordinary two-valued Boolean logic.

In formal verification, DNF can explicitly describe sets of satisfying states or input conditions. This is useful when the set has a small cover by product terms, but exponential growth can make explicit DNF unsuitable for large problems.