In
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 variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
, a disjunctive normal form (DNF) is a
canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a
sum of products, 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 philosophic ...
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 a majo ...
.
Definition
A logical formula is considered to be in DNF if it is a
disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
of one or more
conjunctions 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 and each conjunction appears at most once (up to the order of variables). As in
conjunctive normal form (CNF), the only propositional operators in DNF are
and (
),
or (
), and
not (
). 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 sentence letter, 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 ...
.
The following is a
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules
can be applied to a nonterminal symbol regardless of its context.
In particular, in a context-free grammar, each production rule is of the fo ...
for DNF:
: ''DNF''
''Conjunct''
''Conjunct''
''DNF''
: ''Conjunct''
''Literal''
''Literal''
''Conjunct''
: ''Literal''
''Variable''
''Variable''
Where ''Variable'' is any variable.
For example, all of the following formulas are in DNF:
*
*
*
*
The formula
is in DNF, but not in full DNF; an equivalent full-DNF version is
.
The following formulas are not in DNF:
*
, since an OR is nested within a NOT
*
, since an AND is nested within a NOT
*
, since an OR is nested within an AND
Conversion to DNF
In
classical logic
Classical logic (or standard logic) or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this c ...
each propositional formula can be converted to DNF ...
... by syntactic means
The conversion 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, the double negation of a statement states that "it is not the case that the statement is not true". In classical logic, every statement is logically equivalent to its double negation, but this is not true in intuitionis ...
,
De Morgan's laws
In propositional calculus, 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 Validity (logic), valid rule of inference, rules of inference. They are nam ...
, and the
distributive law
In mathematics, the distributive property of binary operations is a generalization of 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 ...
. Formulas built from the
primitive connectives
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. Connectives can be used to connect logical formulas. For instance in the syntax of propositional logic, th ...
can be converted to DNF by the following
canonical term rewriting system:
:
... by semantic means
The full DNF of a formula can be read off its
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
. For example, consider the formula
:
.
The corresponding
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
is
:
* The full DNF equivalent of
is
:
* The full DNF equivalent of
is
:
Remark
A propositional formula can be represented by one and only one full DNF. In contrast, several ''plain'' DNFs may be possible. For example, by applying the rule
three times, the full DNF of the above
can be simplified to
. However, there are also equivalent DNF formulas that cannot be transformed one into another by this rule, see the pictures for an example.
Disjunctive Normal Form Theorem
It is a theorem that all consistent formulas in
propositional logic
The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...
can be converted to disjunctive normal form.
This is called the Disjunctive Normal Form Theorem.
The formal statement is as follows:
Disjunctive Normal Form Theorem: Suppose is a sentence in a propositional language with sentence letters, which we shall denote by . If is not a contradiction, then it is truth-functionally equivalent to a disjunction of conjunctions of the form , where , and .
The proof follows from the procedure given above for generating DNFs from
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
s. Formally, the proof is as follows:
Suppose is a sentence in a propositional language whose sentence letters are . For each row of 's truth table, write out a corresponding conjunction , where is defined to be if takes the value at that row, and is if takes the value at that row; similarly for , , etc. (the alphabetical order
Alphabetical order is a system whereby character strings are placed in order based on the position of the characters in the conventional ordering of an alphabet. It is one of the methods of collation. In mathematics, a lexicographical order is ...
ing of in the conjunctions is quite arbitrary; any other could be chosen instead). Now form the disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
of all these conjunctions which correspond to rows of 's truth table. This disjunction is a sentence in
This theorem is a convenient way to derive many useful
metalogic
Metalogic is the metatheory of logic. Whereas ''logic'' studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems. Logic concerns the truths that may be derived using a lo ...
al results in propositional logic, such as,
trivially, the result that the set of connectives
\ is
functionally complete.
Maximum number of conjunctions
Any propositional formula is built from
n variables, where
n \ge 1.
There are
2n possible literals:
L = \.
L has
(2^ -1) non-empty subsets.
[\left, \mathcal(L)\ = 2^]
This is the maximum number of conjunctions a DNF can have.
A full DNF can have up to
2^ conjunctions, one for each row of the truth table.
Example 1
Consider a formula with two variables
p and
q.
The longest possible DNF has
2^ -1 = 15 conjunctions:
:
\begin
(\lnot p) \lor (p) \lor (\lnot q) \lor (q) \lor \\
(\lnot p \land p) \lor
\underline \lor
\underline \lor
\underline \lor
\underline \lor
(\lnot q \land q) \lor \\
(\lnot p \land p \land \lnot q) \lor
(\lnot p \land p \land q) \lor
(\lnot p \land \lnot q \land q) \lor
( p \land \lnot q \land q) \lor \\
(\lnot p \land p \land \lnot q \land q)
\end
The longest possible full DNF has 4 conjunctions: they are underlined.
This formula is a
tautology. It can be simplified to
(\neg p \lor p) or to
(\neg q \lor q), which are also tautologies, as well as valid DNFs.
Example 2
Each DNF of the e.g. formula
(X_1 \lor Y_1) \land (X_2 \lor Y_2) \land \dots \land (X_n \lor Y_n) has
2^n conjunctions.
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) asks whether there exists an Interpretation (logic), interpretation that Satisf ...
on
conjunctive normal form formulas is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
. 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.
Conversely, a DNF formula is satisfiable if, and only if, one of its conjunctions is satisfiable. This can be decided in
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
simply by checking that at least one conjunction does not contain conflicting literals.
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.
See also
*
Algebraic normal form – an XOR of AND clauses
*
Blake canonical form – DNF including all prime implicants
**
Quine–McCluskey algorithm
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a gener ...
– algorithm for calculating prime implicants
*
Conjunction/disjunction duality
*
Propositional logic
The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...
*
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
Notes
References
*
*
*
*
*
*
*
*
*
*
{{Normal forms in logic
Normal forms (logic)
Knowledge compilation