Disjunctive Normal Form

What Does Disjunctive Normal Form Mean?

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.

Advertisements

Disjunctive normal form is widely used in areas such as automated theorem proving.

Techopedia Explains Disjunctive Normal Form

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.

Advertisements

Related Terms

Latest Computer Science Terms

Related Reading

Margaret Rouse

Margaret Rouse is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical, business audience. Over the past twenty years her explanations have appeared on TechTarget websites and she's been cited as an authority in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine and Discovery Magazine.Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages. If you have a suggestion for a new definition or how to improve a technical explanation, please email Margaret or contact her…