Disjunctive normal form
As a disjunctive normal form ( DNF, for short ) is in the Boolean algebra denotes a Boolean function in a particular way normalized representation functions.
Definition
A formula of propositional logic is in disjunctive normal form if it is a disjunction of Konjunktionstermen. One of conjunction is formed exclusively by the conjunctive combination of literals. Literals are nichtnegierte or negated variables. A formula in DNF thus has the form
Explanation
In the disjunctive normal form is a logical expression consisting of OR operations ( disjunction - not exclusive OR ) is. The logical expression is in the top level exclusively of OR operations.
Example: A OR B OR C OR D; A ∨ B ∨ C ∨ D
The individual elements of the OR function ( A, B, C, D) may be more complex expressions, which can then also comprise an AND gate ( conjunction).
Example:
As a formal notation:
Here is a disjunction (OR operation ) of three conjunctions ( AND operations ) and the statement D - this is exactly the disjunctive normal form.
By convention, the brackets and the characters (operators ) are not written for the AND operation.
Example:
Also, the NOT operator can occur in such expressions:
Example:
In addition to the above -mentioned requirement that the logical expression is in the top level exclusively of OR operations ( OR plane ), there shall be no further OR operations in deep bracketed levels. Only two levels are allowed: the upper level of OR operations ( OR plane ) and the lower level of the AND operations ( AND plane ). A deeper levels there is not. Only the negative may be used for the elements of the AND plane.
The whole thing goes the other way around: an AND operation of OR statements or individual statements. This is the conjunctive normal form (CNF ) - the counterpart of the disjunctive normal form ( DNF ).
Bring practical benefits such normal forms for large systems statements - for example, in the logical description of the aircraft electrical system with 50 input parameters and hundreds of possible combinations. The system is first of all converted from the literal description into logical formulas - for example, " if the landing gear sensor reports the landing, reverse thrust must be activated ". This collection of logical expressions is then converted into DNF. In this case, the logical expression is generally much longer. In a further step, a simplification of the logical expression using Karnaugh - Veitch - Diagram done. This logic duplication to be removed and taken into account overlaps. The finally calculated logical expression is then integrated in the control software or hardware implemented in the control electronics.
Education
Each formula of propositional logic can be transformed into the disjunctive normal form, as well as any Boolean function can be represented with a DNF. It is sufficient to read the lines of its truth table. For each row that returns 1 as a result, a conjunction is formed that links all the variables of the function ( the line). Variables that are occupied in the row with 1 are not negated and variables that are assigned the value 0 will be negated. These terms are also called minterms. By disjunction of minterms is finally obtained the disjunctive normal form.
In this way, however, one usually receives no minimal formula, ie a formula with the fewest possible terms. If you want to form a minimal formula, so you can do this by using Karnaugh - Veitch - diagrams or Quine - McCluskey using the method.
For example for the formation of the DNF
Wanted is a formula in DNF for a Boolean function with three variables x2, x1 and x0, the iff the truth value 1 (true) assumes when the binary number [ X2X1X0 ] 2 is a prime number.
The truth table for this function has the following form:
Note: The individual terms are listed as minterms. Moreover, one can easily see that every DNF has an equivalent CNF.
The function shown in DNF
Can be represented as a fully parenthesized Boolean expression:
Typically, the internal links be seen analogous to the multiplication operator, and can therefore be omitted. This results in a more compact notation, which is also called product term:
The determination of the truth value of a product term is the same as in mathematics by multiplying the values of the logical variables. If one of the variables involved zero, then the value of the entire product term is zero, the product term takes the value one if and only if all the variables have the value one in him.
CPLDs use disjunctive ( OR ) associated product terms to define their function.
Canonical disjunctive normal form
A canonical disjunctive normal form ( KDNF ), also called complete disjunctive normal form, is a DNF, which contains only minterms in which all variables are present, each variable appears exactly once and whose minterms are all different from each other. Every Boolean function has exactly one KDNF.
In the KDNF are those variable assignments for which the function takes the value 1, expressed by minterms.
Other normal forms
In addition to the disjunctive normal form, there are in SL more normal forms, such as the conjunctive normal form and the negation normal form.
Disjunctive minimal form
A disjunctive normal form is called disjunctive minimal form, if
- Has any equivalent representation of the same output function at least as many product terms
- In any equivalent representation of the same output function with the same number of product terms the number of inputs in the product terms is at least as large as the number of inputs in the product terms of f