• Conjunctive forms of representation of logical functions
• Semiconductor resistors
• Quasar mass. Quasar - what is it? Gravity creates lenses
• History of Journalism The 26th Congress of the CPSU was held in
• Correct chronology in Rus'
• Scientific writings by James Maxwell
• Oleg Mityaev Oleg Mityaev biography briefly about the main thing
• The Grand Duchy of Lithuania in the 14th century The territory of Lithuania in the 14th century
• Presentation on the topic "savannas and woodlands" What animals are in savannas and woodlands
• Biography - Lermontov Mikhail Yurievich Merits and failures

Example. Find CNF formulas

~ ~

The perfect disjunctive normal form of SDNF can be constructed using the following algorithm:

1. = 1. DNF algorithm

2. = 2. DNF algorithm

3. = 3. DNF algorithm

4. = 4. DNF algorithm

5. Omit identically false terms, i.e., terms of the form

6. Fill in the remaining terms with the missing variables

7. Repeat point 4.

Example. Find sdnf formulas.

~

The following scheme can be used to construct the SKNF:

Example. Find sdnf formulas.

~

It is known (Theorems 2.11, 2.12) that SDNF and SKNF are uniquely defined by the formula and, therefore, they can be built according to the truth table of the formula .

The scheme for constructing SDNF and SKNF according to the truth table is given below, for the formula ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. Exercise.

2.2.1 Below are logical expressions. Simplify the expressions of your option as much as possible by using Boole's laws of logic. Then, using truth tables, compare your simplified expression with the original one.

2.2.2. Find out the question of the equivalence of f 1 and f 2 by reducing them to SDNF (Table 1).

2.2.3. Find the dual function for f 3 according to the generalized and Boolean principle (Table 1). Compare the results.

№	f1	f2	f 3

2.3. Control questions.

2.3.1. Define a statement.

2.3.2. List the basic operations on the statement.

2.3.3. What is a truth table?

2.3.4. Create truth tables for the following formulas:

~ ~ ~ ;

2.3.5. Taking into account the conventions on the order of operations, omit the "extra" brackets and the sign "" in the formulas:

;

2.3.6. Applying equivalent transformations, prove the identical truth of the formulas:

2.3.7. Find dual formulas:

)

2.3.8. Reduce the following formulas to the perfect DNF (SDNF) form:

~

2.3.9. Convert the following formulas to the perfect CNF (SKNF) form:

~

Lab #3

Subject:“Minimization of Boolean functions. Logic"

Target: Acquisition of practical skills in working with methods for minimizing Boolean functions.

3.1. Theoretical information.

Minimum Forms

As shown in , any Boolean function can be represented in perfect normal form (disjunctive or conjunctive). Moreover, such a representation is the first step in the transition from a tabular definition of a function to its analytical expression. In the future, we will start from the disjunctive form, and the corresponding results for the conjunctive form are obtained on the basis of the duality principle.

The canonical problem of synthesizing logic circuits in a Boolean basis is reduced to minimizing Boolean functions, i.e. to representing them in disjunctive normal form, which contains the smallest number of letters (variables and their negations). Such forms are called minimal. In canonical synthesis, it is assumed that both signals and their inversions are fed to the inputs of the circuit.

The formula presented in the disjunctive normal form is simplified by repeated application of the gluing operation and the absorption operation and (the dual identities for the conjunctive normal form are: and ). Here, by and can be understood any formula of Boolean algebra. As a result, we arrive at such an analytic expression when further transformations are no longer possible, i.e. we get a dead end form.

Among dead-end forms there is also a minimal disjunctive form, and it may not be unique. To make sure that this dead-end form is minimal, you need to find all dead-end forms and compare them by the number of letters they contain.

Let, for example, the function be given in perfect normal disjunctive form:

Grouping the members and applying the gluing operation, we have .

With another grouping method, we get:

Both dead end forms are non-minimal. To get the minimum form, you need to guess to repeat one term in the original formula (this can always be done, since). In the first case, such a member can be . Then . By adding the term , we get: . After going through all the possible options, we can make sure that the last two forms are minimal.

Working with formulas at this level is like wandering in the dark. The process of searching for minimal forms becomes more visual and purposeful if some graphic and analytical representations and symbols specially designed for this purpose are used.

Multidimensional cube

Each vertex of a -dimensional cube can be assigned a unit constituent. Therefore, the subset of marked vertices is a mapping on the -dimensional cube of a Boolean function of variables in perfect disjunctive normal form. On fig. 3.1 shows such a mapping for the function from Section 3.7.

Fig.3.1 Display on a three-dimensional cube of a function presented in SDNF

To display a function of variables presented in any disjunctive normal form, it is necessary to establish a correspondence between its miniterms and elements of the -dimensional cube.

The miniterm of the (-1)th rank can be considered as the result of gluing two miniterms of the -th rank (unit constituent), i.e. , On a -dimensional cube, this corresponds to replacing two vertices, which differ only in the values ​​of the coordinate connecting these vertices, with an edge (the edge is said to cover the vertices incident to it). Thus, the miniterms of the ( -1) order correspond to the edges of the -dimensional cube. Similarly, the miniterms of the ( -2)th order correspond to the faces of the -dimensional cube, each of which covers four vertices (and four edges).

Elements of a -dimensional cube characterized by dimensions are called -cubes. Thus, vertices are 0-cubes, edges are 1-cubes, faces are 2-cubes, and so on. Generalizing the above reasoning, we can assume that the miniterm of the ()-th rank in the disjunctive normal form for a function of variables is mapped by a -cube, and each -cube covers all those -cubes of the lowest dimension that are associated with its vertices. As an example, in fig. 3.2 shows the mapping of a function of three variables. Here miniterms and correspond to 1-cubes (), and miniterms are represented by 2-cubes ().

Fig.3.2 Function coverage

So, any disjunctive normal form is displayed on a -dimensional cube by a set of -cubes that cover all vertices corresponding to the unit constituents (0-cube). The converse statement is also true: if a certain collection of -cubes covers the set of all vertices corresponding to unit values ​​of a function, then the disjunction of miniterms corresponding to these -cubes is an expression of this function in disjunctive normal form. It is said that such a collection of -cubes (or miniterms corresponding to them) forms a covering of a function.

The desire for a minimal form is intuitively understood as a search for such a cover, the number of -cubes of which would be smaller, and their dimensions would be larger. The cover corresponding to the minimum shape is called the minimum cover. For example, for the coverage function in Fig. 3.3 corresponds to the minimum forms And .

Rice. 3.3 Function coverages.

left – ; on right –

The display of a function on a -dimensional cube is clear and simple when . A four-dimensional cube can be drawn as shown in Fig. 3.4, which displays a function of four variables and its minimum coverage corresponding to the expression . Using this method requires such complex constructions that all its advantages are lost.

Rice. 3.4 Function display on a four-dimensional cube

Karnot maps

Another method for graphing boolean functions uses Carnot cards, which are specially organized lookup tables. The columns and rows of the table correspond to all possible sets of values ​​of no more than two variables, and these sets are arranged in such an order that each subsequent set differs from the previous one by the value of only one of the variables. Due to this, the adjacent cells of the table both horizontally and vertically differ in the value of only one variable. Cells located at the edges of the table are also considered adjacent and have this property. On fig. 3.5 shows Karnaugh maps for two, three, four variables.

Rice. 3.5 Karnot maps for two, three and four variables

As in ordinary truth tables, the cells of the sets on which the function takes the value 1 are filled with ones (zeros usually do not fit in, they correspond to empty cells). For example, in fig. 3.6, A shows the Karnaugh map for the function, the display of which on a four-dimensional cube is given in fig. 3.4. To simplify, the rows and columns corresponding to the values ​​1 for some variable are highlighted with a curly bracket with the designation of this variable.

Rice. 3.6 Carnot chart display of a function of four variables

(a) and its minimum coverage (b)

Between function mappings on n-dimensional cube and on the Karnaugh map there is a one-to-one correspondence. On the map of Carnot s-cube corresponds to a set of 2 adjacent cells placed in a row, column, square or rectangle (taking into account the proximity of opposite edges of the map). Therefore, all the provisions set out in the above (see paragraph multidimensional cube) are valid for Carnot maps. So, in fig. 3.6, b the coverage of map units is shown corresponding to the minimum disjunctive form the function in question.

The reading of miniterms from the Karnot map is carried out according to a simple rule. The cells that form s-cube, give miniter (n–s) rank, which includes those (n–s) variables that keep the same values ​​on this s-cube, where the value 1 corresponds to the variables themselves, and the value 0 corresponds to their negations. Variables that do not retain their values ​​on s-cube, are absent in the minitherm. Different ways of reading lead to different representations of the function in disjunctive normal form (the rightmost is minimal) (Fig. 3.7).

The use of Karnaugh maps requires simpler constructions compared to displaying on n-dimensional cube, especially in the case of four variables. To display functions of five variables, two Karnot maps for four variables are used, and for a function of six variables, four such maps are used. With a further increase in the number of variables, Karnot maps become practically unusable.

Known in Literature Veitch's cards differ only in a different order of the sets of variable values ​​and have the same properties as Karnaugh maps.

Complex of cubes

The failure of graphical methods for a large number of variables is compensated by various analytical methods for representing Boolean functions. One of these representations is complex of cubes, which uses the terminology of a multidimensional logical space in combination with specially designed symbolism.

). 0-cubes corresponding to the constituents of unity are represented by sets of variable values ​​on which the function is equal to unity. Obviously in the record

Rice. 3.8 Complex of cubes of functions of three variables ( A) and its symbolic representation ( b)

The complex of cubes forms maximum function coverage. Excluding all those s-cubes that are covered by cubes of higher dimension, we obtain coverings corresponding to dead-end forms. So, for the example under consideration (Fig. 3.8), we have a dead-end cover

,

which corresponds to the function . In this case, this coverage is also minimal.

For two Boolean functions, the disjunction operation corresponds to the union of their cube complexes, and the conjunction operation to the intersection of their cube complexes. The negation of a function corresponds to the addition of a complex of cubes, i.e., and is determined by all vertices at which the function takes the value 0. Thus, there is a one-to-one correspondence (isomorphism) between the algebra of Boolean functions and Boolean sets representing complexes of cubes.

The representation of a function in the form of complexes of cubes is less visual, but its most important advantages are that restrictions on the number of variables are removed and the coding of information when using computers is facilitated.

Minimizing Boolean Functions

Formulation of the problem. Minimization of a scheme in a Boolean basis is reduced to finding the minimum disjunctive form, which corresponds to the minimum coverage. The total number of letters included in the normal form is expressed by the cost of coverage , where is the number of - cubes forming the coverage of the given function in n variables. The minimum coverage is characterized by the lowest value of its price.

Usually, the minimization problem is solved in two steps. First, a reduced cover is searched for that includes all -cubes of maximum dimension, but does not contain any cube covered by any cube of this cover. The corresponding disjunctive normal form is called reduced, and its miniterms are called simple implicants. For this function, the reduced coverage is the only one, but it may be redundant due to the fact that some of the cubes are covered by collections of other cubes.

At the second step, the transition from reduced to dead-end disjunctive normal forms is carried out, from which minimal forms are chosen. Dead-end forms are formed by excluding all redundant cubes from the reduced coverage, without which the remaining set of cubes still forms a coverage of a given function, but with further exclusion of any of the cubes, it no longer covers the set of all vertices corresponding to unit values ​​of the function, i.e., ceases to be a coverage .

A reduced cover cube that covers vertices of a given function that are not covered by any other cubes cannot be redundant and will always be included in the minimum cover. Such a cube, as well as the implicant corresponding to it, is called an extremal (essential implicant), and the vertices covered by it are called canceled vertices. The set of extremals forms the core of the coverage, it is clear that when passing from a reduced to a minimal coverage, first of all, all extremals should be selected. If the set of extremals does not form a cover, then it is complemented to a cover by cubes from the reduced cover.

The given definitions are illustrated in fig. 3.9, where the reduced coverage (see Fig. 3.9a, ) and minimum coverages (Fig. 3.9b) and (see Fig. 3.9b) are expressed as follows.

Let us 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 distinct elementary disjunctions. For example, logical functions

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

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

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

Uses of the axiom of distributivity with respect to multiplication:

Using the absorb operation:

Exceptions in disjunctions of repeating variables or their negations;

Removal of all identical elementary disjunctions, except for one;

Deleting all disjunctions 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.

The transformation 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;

Use of 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.

The elementary disjunctions included in a perfect CNF function are called zero constituents. Each zero component in a perfect CNF vanishes on the only set of variable values, 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 zero constant in perfect CNF is represented by the conjunction 2nconstituent of zero. Let us formulate a rule for compiling the SKNF of a logical function according to the correspondence table.

For each line of the correspondence table in which the function is equal to zero, an elementary disjunction of all variables is compiled. The disjunction includes the variable itself, if its value is equal to zero, or negation, if its value is equal to one. The resulting elementary disjunctions are combined by the conjunction sign.

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

For the first row of the table, which corresponds to the zero function set 000, we find the null component . Performing similar operations for the second, third and fifth rows, we determine the desired perfect CNF function:

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

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

Normal form exists 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 (SKNF) is a CNF that satisfies three conditions:

does not contain identical elementary disjunctions;

none of the disjunctions contains the same variables;

each elementary disjunction contains every variable in 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 0, the sum is recorded, with variables that have a value of 1 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 from the given DNF, moreover, in the same order.

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

Rules for constructing SDNF according to the truth table

For each set of variables in which the function is equal to 1, the product is written, and the variables that have a value of 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 SKNF construction rule.

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

Share work on social networks

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

Lecture 1.xx

Normal Forms of Boolean Functions

Representation of a Boolean function in the form of a disjunction of conjunctive terms (a 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 by one all logical variables, taken with or without negations, then this form of representation of the function is calledperfect disjunctive normal form(SDNF ) of this function. SDNF is called perfect , because each term in the 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 represented in SDNF, .

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

Table 10

			f (x 1 , x 2 , x 3 )

Based on formula (2.6), we obtain:

As you can see, when compiling an SDNF function, you need to make 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 (constituent zero) D i

, (2.8)

called conjunctive normal form(CNF ) of this function.

If all disjunctive terms of CNF are maxterms , i.e., contain exactly one by one 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 identically equal to 1) can be submitted to SKNF, and this representation is unique.

The proof of the theorem can be carried out similarly to the proof of Theorem 2.1 on the basis of 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:

. (2.9)

It should be noted that both forms of representing 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., 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 wants to open the brackets and thereby go to DNF).

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

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

It should be noted that it is impossible to go directly from the SDNF of a function to its SKNF or vice versa. When attempting such transformations, functions are obtained that are inverse to those desired. 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 in 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 get the SKNF of a logical function, which is inverse with respect to the function obtained in example 2.4:

since it contains all the 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 modulo 2 (), implication (), we pass to the operations AND, OR, NOT (to the Boole basis).

2. Using the properties of negation and the laws of de Morgan (see Table 9), we achieve that the 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, we pass to perfect forms (SDNF or SKNF). For example, to get the SKNF, you often need to use the property: .

Example 6 Convert to SKNF Boolean Function

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

Using the absorption property, we get:

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

2.2.6. Minimization of Boolean Functions

Since the same logical function can be represented by h personal formulas, then finding the simplest pho R mule that defines a Boolean function simplifies the logic circuit that implements the Boolean func to tsyu. Minimum shape l O logical functionin some basis, we can consider such a basis that contains the minimum number of superpositions of func To basis, allowing and parentheses. However, it is difficult to construct an efficient l the algorithm of such minimization with obtaining the minimum bracketed fo r we.

Consider a simpler minimization problem in the synthesis of combinational circuits, in which not the minimal bracketed form of a function is sought, but its minimal DNF. There are simple efficient algorithms for this task.

Quine 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 repeatedly. Thus, it is possible to reduce the rank of terms. This procedure is repeated until no term remains that can be glued with 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 a direct minimization, 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 errors during the 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.

Carnot map method

The Carnot method of maps (tables) is a more visual, less time-consuming 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 makes it easy to 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 of the minimized function, moreover, in such a way that any symmetry axes of the table correspond to zones that are mutually inverse in some variable. Such an arrangement of cells in the table makes it easy to determine the sticking SDNF terms (which differ in the inversion sign of only one variable): they are arranged symmetrically in the table.

Truth tables and Karnaugh maps for AND and OR functions of two lanes e The variables are shown in fig. 8. A value is written in each cell of the map. A value of the function on the set of values ​​of the argument corresponding to this cell n tov.

A ) AND b ) OR

Rice. 8. An example of Karnaugh maps for functions of two variables

There is only one 1 in the Karnaugh map for the And function, so it cannot be glued with anything. In the expression for the minimum function, there will only be a term corresponding to this 1:

f = x y .

There are already three 1s in the Karnaugh map for the OR function, and two gluing pairs can be made, 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 .

On fig. 9 shows the 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 called k-cubes , where k = log 2 K , K number 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 area of ​​2 3 = 8 units 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 the regions may be square (but not necessarily), and if odd k only rectangles.

						b c

Rice. 9. An example of Karnaugh maps for functions of three variables

These areas can overlap, i.e. the same cells can be included in different areas. Then the minimal DNF of the function is written as a disjunction of all conjunctive terms corresponding to k - cubes.

Each of these areas on the Karnaugh map is represented in the minimum 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 m k . Each conjunction of the 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 value.

Thus, when covering map cells with closed regions, one should strive to ensure that the number of regions is minimal, and each region 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 Karnot 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 redefined by replacing with zero or one. For this function, it is clear that it is more advantageous to replace both uncertain values ​​with 1. In this case, two regions 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 collapse the Karnot map into a cylinder both horizontally and vertically. R to the vertical axes with the union of opposite faces ka R you, i.e., units located along the edges of the Carnot map symmetrically h but, can also be combined.

Karnot maps can be drawn in a variety of ways (Figure 10).

									x 2 x 3

a b

Rice. 10. Different Ways to Depict Carnot Maps
for a function of 3 variables

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

a b

Rice. eleven. The most convenient image of Carnot 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. Picture of a Karnaugh map for a function of 5 variables

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

Other related works that may interest you.vshm>
9020.		PRINCIPLE OF DUALITY. EXPANSION OF BOOLEAN FUNCTIONS IN VARIABLES. PERFECT DISJUNCTIVE AND CONJUNCTIVE NORMAL FORMS	96.34KB
	This theorem is constructive, since it allows us to construct for each function a formula realizing it in the form of a perfect d.s. f. To do this, in the truth table for each function, we mark all the lines in which
6490.		Description and minimization of logic functions	187.21KB
	In verbal form, the relationship between the arguments of a function and its values ​​is expressed. Example: A three-argument function evaluates when any two or more of the function's arguments are equal. It consists in constructing a truth table containing the values ​​of the function for all sets of argument values. In this example, according to the truth table, we get such an entry in the form of DNF ...
6707.		Designing relational databases. Design problems in the classical approach. Normalization principles, normal forms	70.48KB
	What is a relational database design? It is a set of interrelated relationships in which all attributes are defined, the primary keys of the relationship are set, and some additional relationship properties are set that relate to the principles of maintaining integrity. Therefore, the design of the database must be very precise and verified. In fact, the database project is the foundation of the future software package that will be used for a long time and by many users.
4849.		Forms and methods of implementation of the functions of the state	197.3KB
	The term "function" has a different meaning in domestic and foreign scientific literature. In philosophical and general sociological terms, it is considered as "an external manifestation of the properties of an object in a given system of relations"; as a set of ordinary or specific actions of individuals or bodies
17873.		Formation of logical UUD in 3rd grade students	846.71KB
	Psychological and pedagogical aspects of the problem of the formation of logical universal actions in younger schoolchildren. Methods for assessing the formation of logical UUD. The development of a concept for the development of universal educational activities in the system of general education meets new social demands. The most important task of the modern education system is the formation of universal educational activities UUD. The formation of universal educational activities is the key to the prevention of school difficulties.
2638.		Technical implementation of logical connections in automatic blocking systems	1.04MB
	Technical implementation of logical connections in automatic blocking systems Technical implementation of three-digit and four-digit AB control algorithms can be achieved using relay contact and non-contact discrete and integral logic elements...
10203.		APPLICATION OF THE CONCEPT OF THE RISK-ORIENTED APPROACH FOR CONSTRUCTION OF STRUCTURAL AND LOGICAL MODELS OF THE ORIGIN AND DEVELOPMENT OF EMERGENCIES	70.8KB
	General risk analysis The production environment is saturated with powerful technological systems and technologies that make human labor productive and less physically difficult, but more dangerous. Risk is characterized by the unexpectedness and suddenness of the onset of a dangerous situation. Every day we are faced with numerous risks, but most of them remain potential. Risk theory provides for a quantitative assessment of the negative impact on a person, as well as damage to his health and life.
11576.		The concept, types and forms of transactions. Consequences of non-compliance with the required form of transactions	49.82KB
	Recognition of the transaction as invalid types of invalid transaction. The applied value of the course work is to simplify the concept of a transaction, that is, its public presentation in a more accessible form.
6213.		Approximation of functions	3.08MB
	The first one consists in replacing some function given analytically or tabularly by another function close to the original one, but simpler and more convenient for calculations. For example, replacing a function with a polynomial allows one to obtain simple formulas for numerical integration and differentiation; replacing a table with an approximating function makes it possible to obtain values ​​at its intermediate points. There also arises the second problem of restoring a function on a certain segment from the values ​​of the function given on this segment in a discrete set of points. The answer to such a question...
14058.		The evolution of the functions of the state	29.99KB
	The Russian state as a legal phenomenon, first of all, must ensure the implementation of the purpose of the state, as well as its basic constitutional characteristics as a democratic federal legal social secular state with a republican form of government. The main purpose of the state is determined by Art.

For any logical formula, with the help of identical transformations, it is possible to construct an infinite number of formulas equivalent to it. In the algebra of logic, one of the main tasks is the search for canonical forms (i.e., formulas built according to a single rule, 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 stand out (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 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 a 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 the i-th place of 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 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 a 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 (KDNF) if:
1) the formula is a CNF, in which each elementary disjunction is a disjunction of k variables x 1 , x 2 , …, x k , and 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 rows of the table in which the value of the function 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 rows of the table in which the value of the function is equal to zero.
2. For each such row, write the disjunction of all variables as follows: if the value of some variable in this set is 0, then we include the variable itself in the conjunction, otherwise, its negation.
3. We connect all obtained disjunctions by conjunction operations.

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

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

x	y	z	F(x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Because on most rows of the truth table, the value of the function is equal to 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, we construct a truth table of the function.

x	y	z	x	¬ x ∨ y ∨ z	¬z	¬ x ∨ y ∨ ¬ z	F(x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

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

• Scenario of the holiday "Day of Cosmonautics" in the preschool educational institution methodological development on the topic The teacher checks the children for the assimilation of the material
• Radio amateur constructions and sale of radio equipment Varicap frequency modulation
• Type Annelids: characteristics, organ systems, the value of worms in nature
• Deviant behavior and its types
• School of Pythagoras, Pythagoreans
• Kostroma State University named after N
• Ural Federal University
• Great quotes from great people about entrepreneurship and entrepreneurs
• mediocrity mediocre mediocre personality
• Tikhonov Nikolai Alexandrovich

• Conjunctive forms of representation of logical functions
• Semiconductor resistors
• Quasar mass. Quasar - what is it? Gravity creates lenses
• History of Journalism The 26th Congress of the CPSU was held in
• Correct chronology in Rus'
• Scientific writings by James Maxwell
• Oleg Mityaev Oleg Mityaev biography briefly about the main thing
• The Grand Duchy of Lithuania in the 14th century The territory of Lithuania in the 14th century
• Presentation on the topic "savannas and woodlands" What animals are in savannas and woodlands
• Biography - Lermontov Mikhail Yurievich Merits and failures