boolean logic In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...

, a disjunctive normal form (DNF) is a

canonical normal form In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form (CCNF) or maxterm canonical form. Other canonical forms include ...

of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a

sum of products In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...

, or (in

philosophical logic Understood in a narrow sense, philosophical logic is the area of logic that studies the application of logical methods to philosophical problems, often in the form of extended logical systems like modal logic. Some theorists conceive philosophical ...

) a ''cluster concept''. As a normal form, it is useful in

automated theorem proving Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was ...

Definition

A logical formula is considered to be in DNF if it is a

disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...

of one or more

conjunctions Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy) In astronomy, a conjunction occ ...

of one or more literals. A DNF formula is in full disjunctive normal form if each of its variables appears exactly once in every conjunction. As in

conjunctive normal form In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a cano ...

(CNF), the only propositional operators in DNF are and (

\wedge

), or (

\vee

), and not (

\neg

). The ''not'' operator can only be used as part of a literal, which means that it can only precede a

propositional variable In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of propos ...

. The following is a

context-free grammar In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...

for DNF: # ''DNF'' → (''Conjunction'')

\vee

''DNF'' # ''DNF'' → (''Conjunction'') # ''Conjunction'' → ''Literal''

\wedge

''Conjunction'' # ''Conjunction'' → ''Literal'' # ''Literal'' →

\neg

''Variable'' # ''Literal'' → ''Variable'' Where ''Variable'' is any variable. For example, all of the following formulas are in DNF: *

(A \land \neg B \land \neg C) \lor (\neg D \land E \land F)

(A \land B) \lor (C)

(A \land B)

(A)

However, the following formulas are not in DNF: *

\neg(A \lor B)

, since an OR is nested within a NOT *

\neg(A \land B) \lor C

, since an AND is nested within a NOT *

A \lor (B \land (C \lor D))

, since an OR is nested within an AND The formula

A \lor B

is in DNF, but not in full DNF; an equivalent full-DNF version is

(A \land B) \lor (A \land \lnot B) \lor (\lnot A \land B)

Conversion to DNF

Converting a formula to DNF involves using

logical equivalence In logic and mathematics, statements p and q are said to be logically equivalent if they have the same truth value in every model. The logical equivalence of p and q is sometimes expressed as p \equiv q, p :: q, \textsfpq, or p \iff q, depending ...

s, such as

double negation elimination In propositional logic, double negation is the theorem that states that "If a statement is true, then it is not the case that the statement is not true." This is expressed by saying that a proposition ''A'' is logically equivalent to ''not (no ...

De Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...

, and the

distributive law In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic ...

. All logical formulas can be converted into an equivalent disjunctive normal form. However, in some cases conversion to DNF can lead to an exponential explosion of the formula. For example, converting the formula

(X_1 \lor Y_1) \land (X_2 \lor Y_2) \land \dots \land (X_n \lor Y_n)

to DNF yields a formula with 2^''n'' terms. Every particular

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...

can be represented by one and only oneIgnoring variations based on associativity and commutativity of AND and OR. ''full'' disjunctive normal form, one of the

canonical form In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical expression. Often, it is one which provides the simplest representation of an ob ...

s. In contrast, two different ''plain'' disjunctive normal forms may denote the same Boolean function; see the illustrations.

Computational complexity

The

Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies ...

formulas is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

; by the duality principle, so is the falsifiability problem on DNF formulas. Therefore, it is co-NP-hard to decide if a DNF formula is a tautology.

Variants

An important variation used in the study of

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

is ''k-DNF''. A formula is in ''k-DNF'' if it is in DNF and each conjunction contains at most k literals.

Definition

Conversion to DNF

Computational complexity

Variants

See also

Notes

References

External links