Residue (complex analysis)

2013-11-20T04:21:51Z

80.133.115.129: /* Definition */

{{refimprove|date=November 2010}}In [[boolean logic]], a '''disjunctive normal form''' (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive [[clause (logic)|clauses]]; otherwise put, it is an OR of ANDs also known as a [[Sum of products]]. As a [[Normal form (abstract rewriting)|normal form]], it is useful in [[automated theorem proving]]. A logical formula is considered to be in DNF [[iff|if and only if]] it is a [[logical disjunction|disjunction]] of one or more [[logical conjunction|conjunctions]] of one or more [[literal (mathematical logic)|literals]]. A DNF formula is in '''full disjunctive normal form''' if each of its variables appears exactly once in every clause. As in [[conjunctive normal form]] (CNF), the only propositional operators in DNF are [[logical conjunction|and]], [[logical disjunction|or]], and [[logical negation|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:

:<math>A \and B</math>
:<math>A\!</math>
:<math>(A \and B) \or C</math>
:<math>(A \and \neg B \and \neg C) \or (\neg D \and E \and F)</math>

However, the following formulas are '''NOT''' in DNF:

:<math>\neg(A \or B)</math> — NOT is the outermost operator
:<math>A \or (B \and (C \or D))</math> — an OR is nested within an AND

Converting a formula to DNF involves using [[logical equivalence]]s, such as the [[double negative elimination]], [[De Morgan's laws]], and the [[distributivity|distributive law]].

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, logical formulas of the following form have 2<sup>n</sup> terms:

:<math>(X_1 \or Y_1) \and (X_2 \or Y_2) \and \dots \and (X_n \or Y_n)</math>

Any particular Boolean function can be represented by one and only one full disjunctive normal form, one of the two [[canonical form (Boolean algebra)|canonical form]]s.

The following is a [[formal grammar]] for DNF:
# ''disjunct'' → ''conjunct''
# ''disjunct'' → ''disjunct'' ∨ ''conjunct''
# ''conjunct'' → ''literal''
# ''conjunct'' → (''conjunct'' ∧ ''literal'')
# ''literal'' → ''variable''
# ''literal'' → ¬''variable''

Where ''variable'' is any variable.

==See also==

* [[Algebraic normal form]]
* [[Boolean function]]
* [[Boolean-valued function]]
* [[Conjunctive normal form]]
* [[Horn clause]]
* [[Karnaugh map]]
* [[Logical graph]]
* [[Propositional logic]]
* [[Quine–McCluskey algorithm]]
* [[Truth table]]

==External links==
{{No footnotes|date=November 2010}}
* {{springer|title=Disjunctive normal form|id=p/d033300}}
* [http://www.izyt.com/BooleanLogic/applet.php Java applet for converting boolean logic expressions to CNF and DNF, showing the laws used]

[[Category:Normal forms (logic)]]

formulasearchengine - User contributions [en]

Residue (complex analysis)