For any logical formula, using identity transformations, one can construct infinitely many formulas equivalent to it. In the algebra of logic, one of the main tasks is the search for canonical forms (i.e., formulas constructed according to a single rule, the 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 (those forms in which functions are written in a unique way).

Perfect disjunctive normal form (PDNF)

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

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

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

The DNF is written in the following form: F 1 ∨ F 2 ∨ ... ∨ F n , where F i is the 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 (PDNF) 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 in the i-th place of this conjunction there is either a 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 (PCNF)

Definition. A formula is called an elementary disjunction if it is formed by the 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 a perfect conjunctive normal form (CPNF) 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 there is either a 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 an SDNF or SKNF.

Algorithm for constructing SDNF using a 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 with disjunction operations.

Algorithm for constructing SCNF using a truth table

1. Select all table rows in which the function value is 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 with conjunction operations.

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

Example: A truth table of a logical function of three variables is given. Construct a logical formula that implements this function.

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

Let's check the resulting formula. To do this, we will construct a truth table of the function.

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

Disjunctive and conjunctive normal forms of propositional algebra. For each propositional logic function, a truth table can be constructed. The inverse problem is also always solvable. Let us introduce several definitions.

Elementary conjunctions (conjuncts) are called conjunctions of variables or their negations in which each variable occurs at most

once.

Disjunctive normal form(DNF) is a formula that has the form of a disjunction of elementary conjunctions.

Elementary disjunctions (disjuncts) are called disjunctions of variables with or without negations.

Conjunctive normal form(CNF) is a formula that has the form of a conjunction of elementary disjunctions.

For each propositional algebra function one can find a set of disjunctive and conjunctive normal forms.

Algorithm for constructing DNF:

1. Go to Boolean operations using equivalent transformation formulas.

2. Go to formulas with close negations, that is, to a formula in which the negations are located no higher than above the variables - apply De Morgan’s laws.

3. Open the brackets - apply the laws of distributivity.

4. Take repeating terms one time at a time - the law of idempotency.

5. Apply the laws of absorption and half-absorption.

Example 6. Find DNF formulas: .

In Boolean algebra it is true principle of duality. It is as follows.

The function is called dual to the function if . Those. To find a function dual to a given one, it is necessary to construct the negation of the function from the negations of the arguments.

Example 7. Find the function dual to .

Among the elementary functions of the algebra of logic, 1 is dual to 0 and vice versa, x is dual to x, dual to , dual and vice versa.

If in the formula F 1 representing the function we replace all conjunctions

on disjunction, disjunction on conjunction, 1 on 0, 0 on 1, then we obtain the formula F *, representing the function * dual to .

Conjunctive normal form (CNF) is a dual concept for DNF, so it can be easily constructed according to the following scheme:

Example 8. Find the CNF formula: .

Using the result of Example 6, we have

Perfect disjunctive and perfect conjunctive normal forms. In each of the types of normal forms (disjunctive and conjunctive), one can distinguish a class of perfect forms SDNF and SCNF.

A perfect elementary conjunction is the logical product of all variables with or without negation, and each variable appears in the product only once.

Any DNF can be reduced to a SDNF by splitting conjunctions that do not contain all variables, i.e. by adding for the missing variable x i is multiplied using the distributive law

Example 9. Find the SDNF for the DNF of Example 6

Perfect elementary disjunction is the logical sum of all variables with or without negations, and each variable is included in the sum only once.

Any CNF can be reduced to SCNF by adding a conjunction term that does not contain any variable X i by the conjunction and applying the distributive law

Example 10. Bring KNF to SKNF:

To construct the SCNF, you can use the diagram

Example 11. Find the SCNF for the formula of example 6.

Every function has a SDNF and, moreover, a unique one. Each function has a SCNF and, moreover, a unique one.

Because SDNF and SKNF are uniquely defined by formulas; they can be constructed using the truth table of the formula.

To construct a SDNF, it is necessary to select the rows in which F takes the value 1 and write down perfect elementary conjunctions for them. If the value of a variable in the desired row of the truth table is equal to one, then in a perfect conjunction it is taken without negation, if zero, then with negation. Then perfect conjunctions (their number is equal to the number of units in the table) are connected by disjunction signs.

To construct a SCNF using a truth table, it is necessary to select the rows in it where F = 0, and write down perfect elementary disjunctions, and then connect them with conjunction signs. If in the required row of the truth table (F=0) the value of the variable corresponds to zero, then in the perfect clause it is taken without negation, if it is one, then with negation.

Example 12. Find SDNF and SCNF using the truth table for the formula of example 6.

Table 14 shows only the final value F=10101101. You should verify the validity of this statement yourself by constructing a detailed truth table.

Table 14

Normal forms of logical functions The 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 of all logical variables taken with or without negations, then this form of representation of a function is called a perfect disjunctive normal form SDNF of this function. As you can see, when composing a SDNF function, you need to create a disjunction of all minterms for which the function takes the value 1.

If this work does 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 (unit constituent) K i

, (2.7)

called disjunctive normal form(DNF) of this function.

If all conjunctive terms in DNF are minterms , i.e. contain exactly one of all logical variables, taken with or without negations, then this form of function representation is calledperfect disjunctive normal form(SDNF ) this function. It's called SDNF perfect , because each term in the disjunction includes all the variables; disjunctive , because the main operation in the formula is disjunction. Concept “normal shape” means an unambiguous way to write a formula that implements a given function.

Taking into account the above, the following theorem follows from Theorem 2.1.

Theorem 2. Any Boolean function(not identically 0) can be presented in SDNF, .

Example 3. Let us have a table given function f (x 1, x 2, x 3) (Table 10).

Table 10

Based on formula (2.6) we obtain:

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

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

, (2.8)

called conjunctive normal form(CNF) of this function.

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

Theorem 3. Any Boolean function(not identical to 1) may be submitted to SKNF, and 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 like this:

. (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 one). Depending on the situation, the representation of a function in one form or another may be shorter.

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

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

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

It should be noted that it is impossible to directly move from the SDNF of a function to its SCNF or vice versa. When attempting such transformations, the results are functions that are the opposite of the desired ones. Expressions for the SDNF and SCNF functions can be directly obtained only from its truth table.

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

Using the result of example 2.3 we get:

As you can see, under the general inversion we obtained the SCNF of a logical function, which is the inverse of the function obtained in example 2.4:

because it contains all the maxterms that are not in the expression for the SCNF of the function in question.

1. Using the properties of the operations (see Table 9) identity (), sum modulo 2 (), implication (), we move on 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 ensure that negation operations apply only to individual variables, and not to entire expressions.

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

4. If necessary, move on to perfect forms (SDNF or SKNF). For example, to obtain SCNF you often need to use the property: .

Example 6. Convert a logical function to SKNF

Carrying out the steps of the above algorithm in order, we get:

Using the absorption property, we get:

Thus, we have obtained the CNF function f (x 1 , x 2 , x 3 ). To obtain its SCNF, you need to repeat each disjunction in which any variable is missing, twice with this variable and with its negation:

2.2.6. Minimizing Logic Functions

Since the same logical function can be represented as h personal formulas, then finding the simplest form R mule defining a Boolean function, simplifies the logic circuit that implements the Boolean function to tion. Minimum form l O logical functionin some basis we can consider one that contains the minimum number of superpositions of fun To tions of the basis, allowing for parentheses. However, it is difficult to build an effective l algorithm for such minimization to obtain the minimum parenthesis r we.

Let's consider a simpler minimization problem in the synthesis of combinational circuits, in which we are looking not for the minimal parenthesized form of a function, but for its minimal DNF. There are simple, efficient algorithms for this task.

Quine's method

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

, (2.10)

and then absorption

, (2.11)

and this pair of steps is applied repeatedly. Thus, it is possible to reduce the rank of terms. This procedure is repeated until there is not a single term left that can be bonded to any other term.

Note that the left side of equation (2.10) could immediately be minimized in a simpler and more obvious way:

This method is bad because with such direct minimization, conjunctive terms either disappear, although there are still possible cases of their use for gluing and absorption with the remaining terms.

It should be noted that Quine’s method is quite labor-intensive, so the likelihood of making mistakes during transformations is quite high. But its advantage is that theoretically it can be used for any number of arguments and as the number of variables increases, the transformations become less complicated.

Karnaugh map method

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

Carnot map this is a two-dimensional tabular form of representing the truth table of a Boolean function, which allows you to easily find the minimum DNFs of logical functions in a graphical visual form. Each cell of the table is associated with the SDNF minterm of the function being minimized, and in such a way that any symmetry axes of the table correspond to zones that are mutually inverse with respect to some variable. This arrangement of cells in the table makes it easy to determine the sticking terms of the SDNF (differing in the inversion sign of only one variable): they are located symmetrically in the table.

Truth tables and Carnaugh maps for the AND and OR functions of two lanes e The variables are presented in Fig. 8. A value is written in each cell of the map A The value of a function on the set of argument values ​​corresponding to this cell N comrade

A) AND b) OR

Rice. 8. Example of Karnaugh maps for functions of two variables

In the Karnaugh map there is only one 1 for the And function, so it cannot be glued to anything. The expression for the minimal function will contain only the term corresponding to this 1:

f = xy.

In the Carnot map for the OR function there are already three 1s and you can make two gluing pairs, with the 1 corresponding to the term xy , is used twice. In the expression for the minimal function, you need to write down the terms for the pairs being glued together, 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 the truth tables of two functions of three variables ( A ) and their Carnot maps ( b and c). Function f 2 differs from the first in that it is not defined on three sets of variables (in the table this is indicated by a dash).

When determining the minimum DNF function, the following rules are used. All cells containing 1 are combined into closed rectangular areas called k-cubes, where k = log 2 K, K quantity 1 in a rectangular area. In this case, each area should be a rectangle with the number of cells 2 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 region of 2 3 = 8 units is called three-cube ; etc. Units that cannot be combined into rectangles can be called zero-cubes , which contain only one unit (2 0 = 1). As can be seen, for even k areas can have a square shape (but not necessarily), and if odd k only rectangles.

Rice. 9. Example of Karnaugh maps for functions of three variables

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

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

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

For the function according to the Karnaugh map in Fig. 9, b we find

since for the upper closed region the variables x 1 and x 2 have values ​​without inversions, for the lower x 1 matters with inversion, and x 3 without inversion.

Undefined values ​​in the map in Fig. 9, V can be further defined by replacing it with zero or one. For this function, it is clear that it is more profitable to replace both undefined values ​​with 1. In this case, two areas are formed, which are different types of 2-cubes. Then the expression for the minimum DNF function will be as follows:

When constructing closed areas, it is allowed to fold the Carnot map into a cylinder both horizontally and vertically. R tick axes with the union of opposite faces R you, i.e. units located along the edges of the Carnot symmetry map h but can also be combined.

Carnaugh maps can be drawn in different ways (Fig. 10).

a b

Rice. 10. Different ways to depict Carnaugh maps
for a function of 3 variables

But the most convenient options for Karnaugh maps for functions of 2-4 variables are those shown in Fig. 11 tables, because they show for each cell A We have all variables in direct or inverse form.

a b

Rice. eleven. The most convenient image of Carnaugh maps
for functions 3 ( a) and 4 (b) variables

For functions of 5 and 6 variables, the method shown in Fig. 10, V .

Rice. 12. Image of a Karnaugh map for a function of 5 variables

Rice. 13. Image of a Karnaugh map for a function of 6 variables

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

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)-- 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 (PCNF) is a CNF that satisfies three conditions:

does not contain identical elementary disjunctions;

none of the disjunctions contain the same variables;

each elementary disjunction contains each variable included in a given CNF.

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

Rules for constructing SKNF using a truth table

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

SDNF

Perfect disjunctive normal form (PDNF) 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 every variable included in a given DNF, and in the same order.

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

Rules for constructing SDNF using a truth table

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

Examples of finding SCNF and SDNF

Example 1

Write a logical function using 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 the SCNF.