In boolean logic, a disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses. As a normal form, it is useful in automated theorem proving. A logical formula is considered to be in DNF if and only if it is a disjunction of one or more conjunctions of one or more literals. 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. For example, all of the following formulas are in DNF: Boolean logic is a complete system for logical operations. ... In logic and declarative programming, a clause is a disjunction of literals and can be interpreted as a (conditional) statement. ... The term normal form is used in a variety of contexts. ... Automated theorem proving (ATP), symbolic analysis, automated deduction, symbolic reasoning, or symbolic deduction, currently the most well-developed subfield of automated reasoning (AR), is the proving of mathematical theorems by a computer program. ... IFF, Iff or iff can stand for: Interchange File Format - a computer file format introduced by Electronic Arts Identification, friend or foe - a radio based identification system utilizing transponders iff - the mathematics concept if and only if International Flavors and Fragrances - a company producing flavors and fragrances International Freedom Foundation... OR logic gate. ... Look up literal, literally in Wiktionary, the free dictionary. ... In Boolean logic, a formula is in Conjunctive Normal Form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. ... AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ... OR logic gate. ... Negation, in its most basic sense, changes the truth value of a statement to its opposite. ...

However, the following formulas are not in DNF:

— NOT is the outermost operator

— an OR is nested within an AND

Converting a formula to DNF involves using logical equivalences, such as the double negative elimination, De Morgan's laws, and the distributive law. Note that all logical formulas can be converted into disjunctive normal form. However, in some cases conversion to DNF can lead to an exponential explosion of the formula. For example, in DNF form, logical formulas of the following form have 2ⁿ terms: In logic, statements p and q are logically equivalent if they have the same logical content. ... In logic and the propositional calculus, double negative elimination is a rule that states that double negatives can be removed from a proposition without changing its meaning: means the same as: Formally: ¬ ¬ A ∴ A The rule of double negative introduction states the converse, that double negatives can be added without... note that demorgans laws are also a big part in circut design. ... In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalises the distributive law from elementary algebra. ...

The following is a formal grammar for DNF: In computer science and linguistics, a formal grammar, or sometimes simply grammar, is a precise description of a formal language — that is, of a set of strings. ...

1. <or> → ∨
2. <and> → ∧
3. <not> → ¬
4. <disjunct> → <conjunct>
5. <disjunct> → <disjunct> <or> <conjunct>
6. <conjunct> → <literal>
7. <conjunct> → (<conjunct> <and> <literal>)
8. <literal> → <term>
9. <literal> → <not><term>

Where <term> is any variable.

See also

• Algebraic normal form
• Boolean function
• Boolean-valued function
• Conjunctive normal form
• Horn clause
• Logical graph
• Quine–McCluskey algorithm
• Truth table
• Zeroth-order logic