Disjunctive normal form

Disjunctive normal form

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. 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 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:

A \and B
A\!
(A \and B) \or C
(A \and \neg B \and \neg C) \or (\neg D \and E \and F)

However, the following formulas are NOT in DNF:

\neg(A \or B) — NOT is the outermost operator
A \or (B \and (C \or D)) — 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.

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 2n terms:

(X_1 \or Y_1) \and (X_2 \or Y_2) \and \dots \and (X_n \or Y_n)

Any particular Boolean function can be represented by one and only one full disjunctive normal form, one of the two canonical forms.

The following is a formal grammar for DNF:

  1. disjunctconjunct
  2. disjunctdisjunctconjunct
  3. conjunctliteral
  4. conjunct → (conjunctliteral)
  5. literalvariable
  6. literal → ¬variable

Where variable is thought as any variable.

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • disjunctive normal form — norminė disjunkcinė forma statusas T sritis automatika atitikmenys: angl. disjunctive normal form; DNF vok. disjungtive Normalform, f rus. дизъюнктивная нормальная форма, f pranc. forme disjonctive normale, f …   Automatikos terminų žodynas

  • disjunctive normal form — noun The form of a boolean formula that the formula has if the formula is a disjunction of conjunctions of literals, such as (A and B and C) or (D and E and not F) …   Wiktionary

  • normal form — A well formed formula of the propositional calculus is in conjunctive normal form when it is of the form A & B &…where each of A, B…is a formula consisting of a disjunction of atomic propositions or negations of atomic propositions (e.g. p ∨q ∨ ¬ …   Philosophy dictionary

  • Conjunctive normal form — 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. As a normal form, it is useful in automated theorem proving. It is similar to the product of sums form …   Wikipedia

  • Negation normal form — A logical formula is in negation normal form if negation occurs only immediately above elementary propositions, and { } are the only allowed Boolean connectives. In classical logic each formula can be brought into this form by replacing… …   Wikipedia

  • Algebraic normal form — In Boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random… …   Wikipedia

  • Canonical form — Generally, in mathematics, a canonical form (often called normal form or standard form) of an object is a standard way of presenting that object. Canonical form can also mean a differential form that is defined in a natural (canonical) way; see… …   Wikipedia

  • Canonical form (Boolean algebra) — In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums… …   Wikipedia

  • Normal number — For the floating point meaning in computing, see normal number (computing). In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit… …   Wikipedia

  • Disjunctive sum — The disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. This is extended to disjunctive sums of any number of games by associativity,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”