Disjunctive normal form

In Boolean algebra, a function representation of Boolean functions that is standardized in a special way is called disjunctive normal form (DNF for short) .

definition

A propositional logic formula is in disjunctive normal form if it is a disjunction of conjunction terms . A conjunction term is formed exclusively from the conjunctive combination of literals. Literals are either non-negated or negated variables. So a formula in DNF has the form

${\displaystyle \bigvee _{i}\bigwedge _{j}(\neg )x_{ij}.}$

Explanation

The disjunctive normal form is a logical expression that consists of OR operations ( disjunction - non-exclusive OR). At the top level, the logical expression consists exclusively of OR links.

Example: A OR B OR C OR D; A∨B∨C∨D

The individual elements of the OR link (A, B, C, D) can be more complex expressions, which can then also contain one or more AND links ( conjunction ).

Example:

${\displaystyle ({A}\ \mathrm {und} \ {B})\ \mathrm {oder} \ ({A}\ \mathrm {und} \ {B}\ \mathrm {und} \ {C})\ \mathrm {oder} \ ({B}\ \mathrm {und} \ {C})\ \mathrm {oder} \ {D}}$

as formal notation:

${\displaystyle ({A}\wedge {B})\vee ({A}\wedge {B}\wedge {C})\vee ({B}\wedge {C})\vee {D}}$

This is a disjunction (OR link) of three conjunctions (AND links) and the statement D - that is exactly the disjunctive normal form.

As agreed, the brackets and the characters (operators) for the AND link are not recorded.

Example:

${\displaystyle {A}{B}\vee {A}{B}{C}\vee {B}{C}\vee {D}}$

The NOT operator can also appear in such expressions:

Example:

${\displaystyle {\bar {A}}{\bar {B}}{\bar {C}}\vee {\bar {A}}B{\bar {C}}\vee AB{\bar {C}}\vee {\bar {A}}{\bar {B}}C\vee {\bar {A}}BC\vee ABC}$

In addition to the requirement already mentioned above that the logical expression in the top level consists exclusively of OR links (OR level), there must be no further OR links in lower bracketed levels. Only two levels are permitted: the upper level of the OR links (OR level) and the lower level of the AND links (AND level). There is no deeper nesting. Only the negation may still be used for the elements of the AND level.

The whole thing also works the other way around: an AND connection of OR statements and individual statements. This is the conjunctive normal form (CNF) - the counterpart to the disjunctive normal form (DNF).

Such normal forms are of practical use in large systems of statements - for example, in the logical description of aircraft electrical systems with 50 input parameters and hundreds of possible combinations. The system is first converted from the literal description into logical formulas - e.g. B. "If the landing gear sensor reports the landing, the thrust reverser may be activated". This collection of logical expressions is then converted into the DNF. The logical expression usually becomes longer. In a further step, the logical expression is simplified using the Karnaugh-Veitch diagram or the Quine-McCluskey method . Logical duplications are removed and overlaps are taken into account. The logical expression ultimately calculated is then integrated into the control software or implemented in hardware in the control electronics.

education

Any propositional logic formula can be converted to the disjunctive normal form, since any Boolean function can also be represented with a DNF. All you have to do is read the lines of your truth table . For every line that delivers a 1 as a result, a conjunction is formed that links all the variables of the function (the line). Variables which are assigned 1 in the line are not negated and variables which are assigned 0 are negated. These terms are also called minter terms . By disjunctive linking of the minterms one finally obtains the disjunctive normal form.

In this way, however, you usually don't get a minimal formula, that is, a formula with as few terms as possible. If one wants to form a minimal formula, one can do this with the help of Karnaugh-Veitch diagrams or with the help of the Quine-McCluskey method .

Example of the formation of the DNF

We are looking for a formula in DNF for the Boolean function with three variables x ₂ , x ₁ and x ₀ , which takes the truth value 1 (true) if and only if the binary number [ x ₂ x ₁ x ₀ ] _{2 is} a prime number .

The truth table for this function has the following form:

Note: The individual terms are noted as minter terms . You can also see that every DNF has an equivalent KNF .

The function represented in DNF

${\displaystyle y={\bar {x_{2}}}x_{1}{\bar {x_{0}}}\vee {\bar {x_{2}}}x_{1}x_{0}\vee x_{2}{\bar {x_{1}}}x_{0}\vee x_{2}x_{1}x_{0}}$

can also be represented as a fully bracketed Boolean expression:

${\displaystyle e=(({\bar {x_{2}}})\wedge x_{1})\vee (x_{2}\wedge x_{0})}$

Usually, the inner -relationships are seen analogously to the multiplication operators and can therefore be omitted. This results in an even more compact notation, which is also called the product term: ${\displaystyle \wedge }$

${\displaystyle e={\bar {x_{2}}}x_{1}+x_{2}x_{0}}$

As in mathematics, the truth value of a product term is determined by multiplying the values ​​of the logical variables. If one of the variables involved is zero, the value of the entire product term is zero; the product term takes on the value one if and only if all the variables in it have the value one.

CPLDs use disjunctive (OR) linked product terms to define their function.

Canonical disjunctive normal form

A canonical disjunctive normal form (KDNF) is a DNF that contains mutually different minterms in pairs , in which each variable occurs exactly once. It is also called the complete disjunctive normal form . Each Boolean function has exactly one KDNF.

In the KDNF, those variable assignments for which the function takes the value 1 are expressed by minter terms.

Orthogonal disjunctive normal form

An orthogonal disjunctive normal form (ODNF) is a DNF whose conjunctions are pairwise disjoint, i.e. H. Result in zero. There are various orthogonalization methods to turn a non-orthogonal disjunctive normal form into an ODNF. For example, an ODNF is obtained if only non-overlapping blocks are read from a Karnaugh-Veitch diagram . In general, there are several ODNFs for each Boolean function. The canonical disjunctive normal form is “inherently” orthogonal and unambiguous. ODNF are algorithmically easier to process due to their orthogonality and are therefore often used in machine logic design. For example, an ODNF can be easily converted into an antivalent normal form by replacing all disjunction operators with antivalence operators and then simplifying them.

More normal forms

In addition to the disjunctive normal form, there are other normal forms in propositional logic , such as the conjunctive normal form and the negation normal form .

Disjunctive minimal form

A disjunctive normal form is called disjunctive minimal form or minimal disjunctive normal form , if

• every equivalent representation of the same output function has at least as many product terms
• for every equivalent representation of the same output function with the same number of product terms, the number of inputs into the product terms is at least as large as the number of inputs into the product terms of f.

Remarks

1. ↑ In some sources (for example: W. Oberschelp, G. Vossen: Computer structure and computer structures. ) DNF is precisely the canonical DNF. (See also: Canonical normal form ).
2. ↑ Dieter Bochmann , Bernd Steinbach : Logic Draft with XBOOLE: Algorithms and Programs . Verlag Technik, Berlin 1991, ISBN 3-341-01006-8 .
3. ↑ Manfred Peschel : Modern applications of algebraic methods . Verlag Technik, Berlin 1971, DNB  575635827 .

Web links

• Web form for creating the disjunctive and conjunctive normal form