Tech moves fast! Stay ahead of the curve with Techopedia!
Join nearly 200,000 subscribers who receive actionable tech insights from Techopedia.
Disjunctive normal form (DNF) is the normalization of a logical formula in Boolean mathematics. In other words, a logical formula is said to be in disjunctive normal form if it is a disjunction of conjunctions with every variable and its negation is present once in each conjunction. All disjunctive normal forms are non-unique, as all disjunctive normal forms for the same proposition are mutually equivalent.
Disjunctive normal form is widely used in areas such as automated theorem proving.
A logical formula is in disjunctive normal form if and only if there is an existence of alternation of one or more conjunctions of one or more literals. A formula is considered as in full disjunctive normal form if all the variables involved are represented only once in every clause. Similar to conjunctive normal form, the propositional operators in disjunctive normal form are same: AND, OR and NOT.
All logical formulas can be converted into an equivalent disjunctive normal form. However, in some cases, exponential explosion of the logical function is possible due to conversion to disjunctive normal form. Another salient point is that any unique Boolean function can be represented by only one and a unique full disjunctive normal form. With the help of techniques such as the truth table method, truth trees or a table of logical equivalences, disjunctive normal form for logical formulas can be generated. K-DNF, a variation of disjunctive normal form, is widely used and popular in the study of computational complexity.