In boolean logic

Boolean logic

Boolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...

, a disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses

Clause (logic)

In logic, a clause is a finite disjunction ofliterals. Clausesare usually written as follows, where the symbols l_i areliterals:l_1 \vee \cdots \vee l_nIn some cases, clauses are written as sets of literals, so that clause above...

. As a normal form

Normal form

Normal form may refer to:* Normal form * Normal form * Normal form * Normal form In formal language theory:* Beta normal form* Chomsky normal form* Greibach normal form* Kuroda normal form...

, it is useful in automated theorem proving

Automated theorem proving

Automated theorem proving or automated deduction, currently the most well-developed subfield of automated reasoning , is the proving of mathematical theorems by a computer program.- Decidability of the problem :...

. A logical formula is considered to be in DNF if and only if

IFF

IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

 it is a disjunction

Logical disjunction

In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...

 of one or more conjunctions

Logical conjunction

In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....

 of one or more literals

Literal (mathematical logic)

In mathematical logic, a literal is an atomic formula or its negation.The definition mostly appears in proof theory , e.g...

. 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

Conjunctive normal form

In Boolean logic, a formula is in conjunctive normal form 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...

 (CNF), the only propositional operators in DNF are and

Logical conjunction

In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....

, or

Logical disjunction

In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...

, and not. The not operator can only be used as part of a literal, which means that it can only precede a propositional variable

Propositional variable

In mathematical logic, a propositional variable is a variable which can either be true or false...

. For example, all of the following formulas are in DNF:


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 equivalence

Logical equivalence

In logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other...

s, such as the double negative elimination

Double negative elimination

In propositional logic, the inference rules double negative elimination allow deriving the double negative equivalent by adding or removing a pair of negation signs...

, De Morgan's laws, and the distributive law

Distributivity

In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...

.

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ⁿ terms:


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

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 because they are the logical OR of a set of variables In...

s.

The following is a formal grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 for DNF:

1. disjunct → conjunct
2. disjunct → disjunct ∨ conjunct
3. conjunct → literal
4. conjunct → (conjunct ∧ literal)
5. literal → variable
6. literal → ¬variable

Where variable is thought as any variable.

See also

• Algebraic normal form
  Algebraic normal form
  In Boolean logic, the algebraic normal form is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving , but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers...
  
  
• Boolean function
• Boolean-valued function
  Boolean-valued function
  A boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....
  
  
• Conjunctive normal form
  Conjunctive normal form
  In Boolean logic, a formula is in conjunctive normal form 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...
  
  
• Horn clause
  Horn clause
  In mathematical logic, a Horn clause is a clause with at most one positive literal. They are named after the logician Alfred Horn, who first pointed out the significance of such clauses in 1951...
  
  
• Logical graph
  Logical graph
  A logical graph is a special type of diagramatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic....
  
  
• Propositional logic
• Quine–McCluskey algorithm
  Quine–McCluskey algorithm
  The Quine–McCluskey algorithm is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey...
  
  
• Truth table
  Truth table
  A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
  
  

External links

• Java applet for converting boolean logic expressions to CNF and DNF, showing the laws used