Conjunctive normal form of a logical function. "Textbook on discrete mathematics dnf, sdnf, knf, sknf

For any logical formula, with the help of identical transformations, it is possible to construct infinitely many formulas equivalent to it. In the algebra of logic, one of the main tasks is the search for canonical forms (that is, formulas constructed according to a single rule, a canon).

If a logical function is expressed through disjunction, conjunction and negation of variables, then this form of representation is called normal.

Among normal forms, perfect normal forms are distinguished (such forms in which functions are written in a unique way).

Perfect Disjunctive Normal Form (SDNF)

Definition. A formula is called an elementary conjunction if it is formed by the conjunction of a number of variables or their negations.

Examples: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definition. A formula is called a disjunctive normal form (DNF) if it is a disjunction of non-repeating elementary conjunctions.

DNF is written in the following form: F 1 ∨ F 2 ∨ ... ∨ F n, where F i is an elementary conjunction

Examples: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definition. A logical formula in k variables is called perfect disjunctive normal form (SDNF) if:
1) the formula is a DNF, in which each elementary conjunction is a conjunction of k variables x 1, x 2, ..., x k, and on i-th place this conjunction is either the variable x i, or its negation;
2) all elementary conjunctions in such a DNF are pairwise distinct.

Example: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Perfect conjunctive normal form (SKNF)

Definition. A formula is called an elementary disjunction if it is formed by a disjunction of a certain number of variables or their negations.

Examples: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definition. A formula is called conjunctive normal form (CNF) if it is a conjunction of non-repeating elementary disjunctions.

CNF is written in the following form: F 1 ∧ F 2 ∧ ... ∧ F n, where F i is an elementary disjunction

Examples: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definition. A logical formula in k variables is called perfect conjunctive normal form (CDNF) if:
1) the formula is CNF, in which each elementary disjunction is a disjunction of k variables x 1, x 2, ..., x k, and in the i-th place of this disjunction is either the variable x i or its negation;
2) all elementary disjunctions in such a CNF are pairwise distinct.

Example: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

notice, that any logical function that is not identically equal to 0 or 1 can be represented as SDNF or SKNF.

Algorithm for constructing SDNF according to the truth table

1. Select all table rows in which the function value is equal to one.
2. For each such line, write the conjunction of all variables as follows: if the value of some variable in this set is equal to 1, then we include the variable itself in the conjunction, otherwise - its negation.
3. We connect all the resulting conjunctions by disjunction operations.

Algorithm for constructing SKNF according to the truth table

1. Select all table rows in which the function value is equal to zero.
2. For each such line, write the disjunction of all variables as follows: if the value of some variable in this set is equal to 0, then we include the variable itself in the conjunction, otherwise - its negation.
3. We connect all the resulting disjunctions by conjunction operations.

Analysis of the algorithms shows that if on most of the rows of the truth table the value of the function is equal to 0, then to obtain its logical formula it is better to construct the SDNF, otherwise - SKNF.

Example: Given a truth table of a logical function of three variables. Build logical formula implementing this function.

Because on most rows of the truth table, the value of the function is 1, then we construct the SKNF. As a result, we get the following logical formula:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Let's check the resulting formula. To do this, let's build the truth table of the function.

Comparing the original truth table and the one built for the logical formula, we note that the columns of the function values ​​are the same. This means that the logical function is built correctly.

Normal form logical formula does not contain signs of implication, equivalence and negation of non-elementary formulas.

The normal form comes in two forms:

conjunctive normal form (CNF)- conjunction of several disjunctions, for example, $ \ left (A \ vee \ overline (B) \ vee C \ right) \ wedge \ left (A \ vee C \ right) $;

disjunctive normal form (DNF)- a disjunction of several conjunctions, for example, $ \ left (A \ wedge \ overline (B) \ wedge C \ right) \ vee \ left (B \ wedge C \ right) $.

SKNF

Perfect conjunctive normal form (SKNF) is a CNF that satisfies three conditions:

does not contain identical elementary disjunctions;

none of the clauses contains the same variables;

each elementary disjunction contains each variable from the given CNF.

Any Boolean formula that is not identically true can be represented in SKNF.

Rules for constructing SKNF according to the truth table

For each set of variables for which the function is equal to 0, the sum is written, and the variables that have the value 1 are taken with negation.

SDNF

Perfect Disjunctive Normal Form (SDNF) is a DNF that satisfies three conditions:

does not contain identical elementary conjunctions;

none of the conjunctions contains the same variables;

each elementary conjunction contains each variable from the given DNFs, moreover, in the same order.

Any Boolean formula that is not identically false can be represented in the SDNF, moreover, in a unique way.

Rules for constructing SDNF according to the truth table

For each set of variables for which the function is equal to 1, the product is written, and the variables that have the value 0 are taken with negation.

Examples of finding SKNF and SDNF

Example 1

Write a logical function according to its truth table:

Picture 1.

Solution:

Let's use the rule for constructing SDNF:

Figure 2.

We get SDNF:

Let's use the rule for constructing SKNF.

Simple conjunction called conjunction one or several variables, at this each one variable meets not more one times (or itself, or her negation).

For example, is a simple conjunction,

Disjunctive normal form(DNF) called disjunction simple conjunctions.

For example, the expression is DNF.

Perfect disjunctive normal form(SDNF) called so disjunctive normal the form, at which v every conjunction are included all variables given list (or themselves, or their denials), moreover v one and volume the sameokay.

For example, the expression is DNF but not SDNF. Expression is SDNF.

Similar definitions (with replacement of conjunction by disjunction and vice versa) are valid for CNF and SKNF. Here are the exact formulations.

Simple disjunction called disjunction one or several variables, at this each one variable enters not more one times (or itself, or her negation) For example, an expression is a simple disjunction,

Conjunctive normal form(CNF) called conjunction simple disjunctions(for example, the expression is CNF).

A perfect conjunctive normal form (SCNF) is a CNF in which each simple disjunction contains all the variables of the given list (either themselves or their negations), and in the same order.

For example, the expression is SKNF.

Here are the algorithms for transitions from one form to another. Naturally, in specific cases (with a certain creative approach), the use of algorithms is more laborious than simple transformations using a specific type of this form:

a) transition from DNF to CNF

The algorithm for this transition is as follows: we put two negations above the DNF and, using the de Morgan rules (without touching the upper negation), we bring the negation of the DNF back to the DNF. In this case, you have to open the brackets using the absorption rule (or Blake's rule). The negation (upper) of the obtained DNF (again according to the de Morgan rule) immediately gives us the CNF:

Note that the CNF can also be obtained from the initial expression, if we take out at outside the brackets;

b) transition from CNF to DNF

This transition is carried out by simple opening of the parentheses (in this case, again, the absorption rule is used)

Thus, we got DNF.

The reverse transition (from SDNF to DNF) is associated with the problem of minimizing DNF. This will be discussed in more detail in Sec. 5, here we will show how to simplify DNF (or SDNF) according to Blake's rule. This DNF is called abbreviated DNF;

c) abbreviation of DNF (or SDNF) by rule Blake

The application of this rule has two parts:

If among the disjoint terms in the DNF there are terms , then to the whole disjunction we add the term TO 1 TO 2. We do this operation several times (it can be sequential, it can be simultaneously) for all possible pairs of terms, and then, we apply the usual absorption;

If the added term was already contained in the DNF, then it can be discarded altogether, for example,

or

Of course, the abbreviated DNF is not uniquely defined, but they all contain the same number of letters (for example, there is a DNF , after applying Blake's rule to it, you can come to a DNF equivalent to this one):

c) transition from DNF to SDNF

If some simple conjunction lacks a variable, for example, z, insert the expression into it, and then expand the parentheses (in this case, we do not write repeated disjoint terms). For example:

d) transition from CNF to SKNF

This transition is carried out in a manner similar to the previous one: if a simple disjunction lacks some variable (for example, z, then we add an expression to it (this does not change the disjunction itself), after which we expand the brackets using the distribution law):

Thus, SKNF is obtained from CNF.

Note that the minimum or abbreviated CNF is usually obtained from the corresponding DNF.

Let's introduce the concept of elementary disjunction.

An elementary disjunction is an expression of the form

The conjunctive normal form (CNF) of a logical function is the conjunction of any finite set of pairwise different elementary disjunctions. For example, logical functions

are the conjunctions of elementary disjunctions. Therefore, they are written in conjunctive normal form.

An arbitrary logical function given by an analytical expression can be reduced to CNF by performing the following operations:

Using the inversion rule if the negation operation is applied to a boolean expression;

Using the axiom of distributivity with respect to multiplication:

Uses of the absorption operation:

Exceptions in disjunctions of repeated variables or their negations;

Removing all the same elementary disjunctions, except for one;

Removing all clauses that simultaneously include a variable and its negation.

The validity of the listed operations follows from the basic axioms and identity relations of the algebra of logic.

A conjunctive normal form is called perfect if each elementary disjunction included in it contains, in direct or inverse form, all the variables on which the function depends.

Conversion of CNF to perfect CNF is carried out by performing the following operations:

Additions to each elementary disjunction of conjunctions of variables and their negations, if they are not included in this elementary disjunction;

Using the axiom of distributivity;

Removal of all identical elementary disjunctions, except for one.

Any logical function can be represented in a perfect CNF, except

identically equal to one(). A distinctive property of a perfect CNF is that the representation of a logical function in it is unique.

Elementary disjunctions included in the perfect CNF function are called zero constituents. Each constituent of zero included in the perfect CNF vanishes on a single set of values ​​of the variables, which is the zero set of the function. Consequently, the number of zero sets of a logical function coincides with the number of zero constituents included in its perfect CNF.

The logical function constant of zero in a perfect CNF is represented by the conjunction 2n constant of zero. Let us formulate a rule for compiling the SCNF of a logical function according to a correspondence table.

For each row of the lookup table, in which the function is equal to zero, an elementary disjunction of all variables is compiled. In this case, the variable itself is included in the disjunction if its value is equal to zero, or negation if its value is equal to one. The resulting elementary disjunctions are united by the conjunction sign.

Example 3.4. For the logical function z (x), given by the correspondence table 2.2, we define the perfect conjunctive form.

For the first row of the table, which corresponds to the zero set of the function 000, we find the constituent of zero. Having performed similar operations for the second, third and fifth lines, we define the desired perfect CNF function:

It should be noted that for functions, the number of unit sets of which exceeds the number of zero sets, it is more compact to write them in the form of SKNF and vice versa.

Normal forms of logical functions Representation of a Boolean function in the form of a disjunction of conjunctive terms of the constituents of the unit Ki 2.7 is called the disjunctive normal form of the DNF of this function. contain exactly one at a time all logical variables taken with negations or without them, then this form of the function representation is called the perfect disjunctive normal form of the SDNF of this function. As you can see, when compiling the SDNF function, you need to make a disjunction of all minterms for which the function takes on the value 1.

If this work did not suit you at the bottom of the page there is a list of similar works. You can also use the search button

Lecture 1.xx

Normal forms of logical functions

Representation of a Boolean function in the form of a disjunction of conjunctive terms (constituent unit) K i

, (2.7)

called disjunctive normal form(DNF) of this function.

If all conjunctive terms in DNF are minterms , that is, they contain exactly one at a time all logical variables, taken with negatives or without them, then this form of representation of the function is calledperfect disjunctive normal form(SDNF ) of this function. SDNF is called perfect because every term in disjunction includes all variables; disjunctive because the main operation in the formula is disjunction. The concept "normal form”Means an unambiguous way of writing a formula that implements a given function.

In view of the above, Theorem 2.1 implies the following theorem.

Theorem 2. Any boolean function(not identically equal to 0) can be submitted to SDNF, .

Example 3. Let we have a table-defined function f (x 1, x 2, x 3) (Table 10).

Table 10

Based on formula (2.6), we obtain:

As you can see, when compiling the SDNF function, you need to compose a disjunction of all minterms for which the function takes on the value 1.

Representation of a Boolean function in the form of a conjunction of disjunctive terms (constituent of zero) D i

, (2.8)

called conjunctive normal form(CNF) this function.

If all disjunctive CNF terms are makstermas , i.e., contain exactly one all logical function variables taken with or without negations, then such a CNF is calledperfect conjunctive normal form(SKNF) this function.

Theorem 3. Any boolean function(not equal identically 1) can be represented in SKNF, moreover, such a representation is the only one.

The proof of the theorem can be carried out similarly to the proof of Theorem 2.1 based on the following Shannon lemma on conjunctive decomposition.

Shannon's lemma ... Any boolean function f (x 1, x 2, ..., x m) from m variables can be represented as follows:

. (2.9)

It should be noted that both forms of representation of a logical function (DNF and CNF) are theoretically equal in their capabilities: any logical formula can be represented both in DNF (except for the identical zero) and in CNF (except for the identical unit). Depending on the situation, the representation of the function in one form or another may be shorter.

In practice, DNF is most often used, since this form is more familiar to a person: from childhood he is more accustomed to adding works than to multiplying sums (in the latter case he intuitively has a desire to open the brackets and thus go to the DNF).

Example 4. For the function f (x 1, x 2, x 3 ) given by table. 10, write it to SKNF.

Unlike SDNF, when compiling SCNF in the truth table of a logical function, you need to look at the combinations of variables for which the function takes the value 0, and compose the conjunction of the corresponding maxterms,but the variables must be taken with reverse inversion:

It should be noted that it is impossible to go directly from the SDNF function to its SKNF or vice versa. Attempting such transformations results in the inverse functions of the desired ones. Expressions for SDNF and SKNF functions can be directly obtained only from its truth table.

Example 5. For the function f (x 1, x 2, x 3 ) given by table. 10, try to move from SDNF to SKNF.

Using the result of Example 2.3, we get:

As you can see, under the general inversion, the SKNF of the logical function is obtained, which is inverse with respect to the function obtained in example 2.4:

since it contains all maxterms that are not in the expression for the SKNF of the function under consideration.

1. Using the properties of operations (see Table 9) identity (), sum mod 2 (), implication (), we pass to the operations AND, OR, NOT (in the Boolean basis).

2. Using the properties of negation and de Morgan's laws (see Table 9), we achieve that the negation operations refer only to individual variables, and not to whole expressions.

3. Using the properties of logical operations AND and OR (see Table 9), we obtain the normal form (DNF or CNF).

4. If necessary, go to the perfect forms (SDNF or SKNF). For example, to get SKNF, you often need to use the property:.

Example 6. Convert Boolean Function to SKNF

Performing the steps of the above algorithm in order, we get:

Using the absorption property, we get:

Thus, we have obtained the CNF functions f (x 1, x 2, x 3 ). To get its SKNF, you need to repeat each disjunction, which lacks any variable, twice - with this variable and with its negation:

2.2.6. Minimizing Boolean Functions

Since the same logical function can be represented as s personal formulas, then finding the simplest pho R mule, which defines a Boolean function, simplifies the logic circuit that implements the Boolean function. to tion. Minimum shape l O geological functionin some basis, we can assume that it contains the minimum number of superpositions of the function To basis, including parentheses. However, it is difficult to construct an effective a l an algorithm for such minimization with obtaining the minimum bracket r we.

Let us consider a simpler minimization problem in the synthesis of combinational circuits, in which not the minimum bracket form of a function is sought, but its minimum DNF. There are simple, efficient algorithms for this task.

Quine's method

The function to be minimized is represented in SDNF, and all possible operations of incomplete gluing are applied to it

, (2.10)

and then absorption

, (2.11)

and this pair of steps is applied multiple times. Thus, it is possible to lower the rank of the terms. This procedure is repeated until no term remains that can be glued to any other term.

notice, that left side Eqs. (2.10) could immediately be minimized in a simpler and more obvious way:

This method is bad in that, with such a direct minimization, the conjunctive terms either disappear, although there are still cases of their use for gluing and absorbing with the remaining terms.

It should be noted that Quine's method is quite time consuming, so the probability of making mistakes during transformations is quite high. But its advantage is that, in theory, it can be used for any number of arguments, and as the number of variables increases, conversions become less complicated.

Karnaugh map method

The method of Karnaugh maps (tables) is a more visual, less time-consuming and reliable way of minimizing logical functions, but its use is practically limited to functions of 3-4 variables, maximum - 5-6 variables.

Carnot Map Is a two-dimensional tabular form of representing the truth table of a Boolean function, which allows you to easily find the minimum DNF of logical functions in a graphical visual form. Each cell of the table is associated with the minterm of the SDNF function to be minimized, and so that any axis of symmetry of the table corresponds to zones that are mutually inverse in any variable. This arrangement of cells in the table makes it easy to determine the gluing SDNF terms (differing in the inversion sign of only one variable): they are arranged symmetrically in the table.

Truth tables and Karnot maps for AND and OR functions of two lane e variables are shown in Fig. 8. In each cell of the card, a sign is written a function on the argument corresponding to this cell n Comrade

A) AND b) OR

Rice. eight. An example of Karnot maps for functions of two variables

There is only one 1 in the Karnot map for the function And, so it cannot be glued to anything. The expression for the minimum function will contain only the term corresponding to this 1:

f = x y.

In the Karnot map for the OR function, there are already three 1s and it is possible to make two gluing pairs, with 1 corresponding to the term xy , is used twice. In the expression for the minimum function, you need to write the terms for the pairs to be glued, leaving in them all the variables that do not change for this pair, and removing the variables that change their value. For horizontal gluing we get x , and for vertical - y , as a result we get the expression

f = x + y.

In fig. 9 shows truth tables of two functions of three variables ( a ) and their Karnot maps ( b and c). Function f 2 differs from the first one in that it is not defined on three sets of variables (this is indicated by a dash in the table).

When determining the minimum DNF of a function, the following rules are used. All cells containing 1 are combined into closed rectangular areas, which are called k -cubes, where k = log 2 K, K - quantity 1 in a rectangular area. Moreover, each area should be a rectangle with 2 cells k, where k = 0, 1, 2, 3,…. For k = 1 rectangle is called one is a cube and contains 2 1 = 2 units; for k = 2 rectangle contains 2 2 = 4 units and is called two-cube; for k = 3 the region of 2 3 = 8 units is called three-cube ; and so on. Units that cannot be combined into rectangles can be called zero-cubes that contain only one unit (2 0 = 1). As you can see, with even k areas can be square (but not necessary), and for an odd k - only rectangles.

Rice. nine. An example of Karnot maps for functions of three variables

These areas can overlap, that is, the same cells can enter different areas... Then the minimum DNF of the function is written as a disjunction of all conjunctive terms corresponding to k - cubes.

Each of the indicated regions on the Karnot map is represented in the minimal DNF by a conjunction, the number of arguments in which is k less than the total number of function arguments m , that is, this number is equal to m - k ... Each conjunction of the minimum DNF is composed only of those arguments that for the corresponding area of ​​the map have values ​​either without inversions, or only with inversions, that is, do not change their values.

Thus, when covering the cells of the map with closed areas, one should strive to ensure that the number of areas is minimal, and each area contains the largest possible number of cells, since in this case the number of members in the minimum DNF will be minimal and the number of arguments in the corresponding conjunction will be minimal.

For the Karnot map function in Fig. nine, we find

since for the upper closed area the variables x 1 and x 2 matter without inversions, for the lower x 1 matters with inversion, and x 3 - no inversion.

The undefined values ​​in the map in Fig. nine, v can be extended by replacing it with zero or one. For this function, it can be seen that it is more advantageous to replace both undefined values ​​by 1. In this case, two regions are formed, which are different kinds 2 cubes. Then the expression for the minimum DNF function will be as follows:

When constructing closed areas, it is allowed to collapse the Karnaugh map into a cylinder both horizontally and vertically. R tical axes with the union of opposite edges of the R you, that is, the units located at the edges of the Carnot symmetry map h but, can also be combined.

Karnaugh maps can be drawn in different ways (Figure 10).

a b

Rice. ten. Different ways of drawing Karnaugh maps
for a function of 3 variables

But the most convenient variants of Karnot maps for functions of 2-4 variables are shown in Fig. 11 tables, because in them, for each cell, a all variables are in direct or inverse form.

a b

Rice. eleven. Most Convenient Image of Karnot Maps
for functions 3 ( a) and 4 (b) variables

For functions of 5 and 6 variables, the method shown in Fig. ten, v .

Rice. 12. Image of the Karnot map for a function of 5 variables

Rice. 13. Image of the Karnot map for a function of 6 variables