Circuit design. Analysis and synthesis of logic devices
The method is applicable for functions of any number of variables, but we will consider it for functions of 3 variables.
Let us represent it as a DNF with undetermined coefficientsk:
(**)
This DNF presents all possible elementary conjunctions that can be included in the function, and the coefficients k can take values 0 or 1. The values of the coefficients must be chosen so that this DNF is minimal.
We will consider the function given to us on all sets and equate the expression (**) on each of the sets (discarding zero conjunctions) to the corresponding value of the function. We obtain a system of equations of the form:
If in any of these equations the right-hand side is equal to 0, then all the terms on the left-hand side are also equal to 0. These coefficients can be eliminated from all equations whose right-hand sides are equal to 1. In these equations, the value 1 should be assigned to the coefficient that corresponds to the conjunction of the smallest rank. These coefficients will determine the MDNF.
Example
We compose the system using the expression (**).
After eliminating the zero terms we get
We assume that the remaining coefficients are considered zero. We get MDNF:
2.2. Quine-Mack-Clasky method
The considered method of indefinite coefficients is effective if the number of function arguments is no more than 5 - 6. This is due to the fact that the number of equations is 2n. It is more efficient to write down not all possible conjunctions for a function, but only those that may be present in the DNF of a given function. This is what Quine's method is based on. It is assumed that the function is specified in the form of SDNF. In this method, elementary conjunctions of rank n included in the DNF are called miniterms of rank n. Quine's method consists of sequentially performing the following steps.
1. Finding primary implicants
We look through each miniterm of the function sequentially and merge it with all miniterms with which this is possible. As a result of gluing together n-rank miniterms, we obtain (n-1)-rank miniterms. We mark the n-rank miniterms that participated in the gluing operation. Then we consider miniterms of (n-1) rank and apply the gluing operation to them. We mark the gluing miniterms of (n-1) rank and write down the resulting miniterms of (n-2) rank, etc. The stage ends if the newly obtained miniterms l-th rank no longer stick together. All unmarked miniterms are called prime implicants. Their disjunction is Abbr. DNF functions.
We glue together miniterms of the 4th rank and mark the glued miniterms with asterisks
We form miniterms of the 2nd rank:
The primary (simple) implicants are:
2. Placement of marks
For this function Abbr. DNF has the form:
To construct dead-end DNFs and Abbr. DNF needs to be thrown away extra intervals. We build a table whose rows correspond to the primary implicants, and the columns correspond to the SDNF miniterms. If one of the miniterms includes one of the implicants, then a mark is placed at the intersection of the corresponding row and column, for example, 1.
Continuation of the example
3. Finding essential implicants
If any column contains only one 1, then the primary implicant that defines that row is called essential. For example, the essential implicant is . The essential implicant cannot be removed from the Abbr. DNF, since only it is capable of covering some miniterms of SDNF. Therefore, we exclude from the table the rows corresponding to these implicants and the columns that have ones in these rows.
In this example, we exclude the row and columns.
As a result we get the table
4. Crossing out extra columns and rows
If the resulting table has identical columns, then cross out all but one. If after this the table appears empty lines, then we cross them out.
5. Selecting minimum coverage with maximum intervals
In the resulting table, select a set of rows that contains ones in all columns. Given several possible options for such a choice, preference is given to the option with the minimum number of letters in the lines that form the coverage.
Continuation of the example
The minimum table coverage is formed by the rows corresponding to the implicants. Then MDNF has the form:
Quine's method has one significant inconvenience associated with the need for a complete pairwise comparison of miniterms at the stage of constructing Abbr. DNF. In 1956, McCluskey proposed a modernization of the first stage of Quine's method, giving a significant reduction in the number of comparisons of miniterms.
The idea of the McCluskey method is as follows. All miniterms are written in the form of binary numbers, for example, as 1010. These numbers are divided into groups according to the number of units in the number, i.e. the i-th group includes numbers that have i units in their notation. Pairwise comparison is made only between groups adjacent in number, since the miniterms suitable for gluing differ from each other in only one digit. When miniterms with a rank higher than zero are formed, a dash is placed in the digits corresponding to the excluded variables.
Example
Let's find the MDNF for the function:
Miniterms of 4th rank by groups
Miniterms of the 3rd rank
Miniterms 2nd rank
Unlabeled miniterms or prime implicants
Building a table of labels
Both primary implicants are essential and determine the minimum coverage, i.e. MDNF has the form.
There are combinational and sequential logic devices.
Combinational Logic Devices- these are devices in which the values of the output signals depend only on the combination of input signals in this moment time.
Sequential logic devices - These are devices whose output signals depend on the values of the input signals not only at a given time, but also at previous times. These devices necessarily include memory elements - triggers. There are several types of triggers depending on what elementary memory function they implement.
When developing a logical device, a verbal description of its action algorithm is first formulated. Then they compose a logical function that satisfies this description (abstract synthesis) and then develop a structural logical diagram of the device (structural synthesis).
In the process of abstract synthesis transition from verbal description TP (its normal course and emergency situations) to compile a functioning algorithm in the form of a table, cyclogram, graph, etc. Cyclogram represents a series of horizontal lines equal to the number of inputs and outputs of a logical device. To draw up a logical algorithm for controlling technological equipment, you must have full information about the technical specifications of each technological operation and the equipment used. At this stage, the sequence of operations and the necessary time delays for all modes of operation of the control object are clarified, the parameters to be monitored and taken into account during the process are determined; formulate the requirements of the managed object for the logical device. These requirements are presented in the form of binary signal values that must be supplied to the control system actuators depending on the state of the controlled object.
In the process of structural synthesis there is a transition from a logical function describing the functioning algorithm to a block diagram of a logical device.
However, before you start designing the circuit, you must try to convert the original logic function to the maximum simple view. Based block diagram logical device design it schematic diagram using specific element base, for example, in the OR-HE or NAND basis. The final stage of creating a logical device circuit is the development and coordination of communication nodes of the device with the operator and the controlled object, protection against interference, etc.
Historically, the first devices that used logical functions to describe their actions were devices made on relay contact elements. To design such devices, the theory of relay contact circuits (TRC) was developed. Then contactless devices appeared, intended only for logical signal transformations and representing structurally designed products.
Automation devices, the operation of which is described by elementary logical functions, are usually called, in accordance with the logical operation they implement, elements NOT, AND, OR, AND-NOT, OR-HE (see Table 4.1).
Having the necessary elements, a logical device of any complexity can be synthesized using a logical function. However, the constructed circuit may turn out to be unreasonably complex, requiring the use of a large number of logic elements, which may affect the cost and reliability of the device. In many cases, it is possible to simplify a logical function so much that the corresponding device circuit turns out to be significantly simpler and performs the task.
Minimization methods logical functions. Methods for simplifying combinational devices are called methods for minimizing logical functions. The minimization method is based on the application of the laws of logical algebra, or Boolean algebra, which are given below for the minimum number of variables. The equivalence of the left and right sides of the equations is indicated by the equal sign. At the same time, relay equivalents of the laws of logical algebra under consideration are depicted.
Travel law. For a logical sum and product, the order of the variables is indifferent:
Combination law.The result of sequential addition or multiplication of variables does not depend on the order of these actions:
Law of absorption.Addition of a variable with the same variable, multiplied by another variable, or multiplying a variable by the sum of the same variable and another variable is equal to the first variable:
Distributive law.The general multiplier can be taken out of brackets, as in ordinary algebra:
Law of gluing.The sum of the products of the first and second variables and the second variable and the inverse of the first variable is equal to the second variable. The product of the sum of two variables and the sum of the inverse of the first variable with the second variable is equal to the second variable:
Law of Inversion (Morgan's law - Shannon).The negation of logical addition is equivalent to the product of the negations of the terms, And, vice versa, the negation of logical multiplication is equivalent to the sum of the negations of the factors:
Inverting an arbitrary combination of binary variables connected by a plus or multiplication sign is equivalent to replacing the values of the variables in it.
their inversions while simultaneously changing the “plus” sign to the “multiplication” sign and vice versa. For example, x t x 2 +x 3 x 4 =(x l x 2)(x 3 x 4) = (x l +x 2)(x 3 +x 4). The law of inversion is found only in the algebra of logic.
Thus, the inversion law allows you to replace the OR operation with the AND operation, and, if necessary, vice versa. This is especially important because when widespread use of integral logical elements in the construction of logical devices, the elements of the AND-NOT, OR-NOT bases are most often used.
Transformations of logical functions performed using the distributive law are the main method of simplification, since placing the common factor out of brackets reduces total number expression variables, therefore, allows you to reduce the number of elements in logic device circuits.
When performing minimization, they also use the consequences of the laws of logical algebra, the main ones of which are the following:
The last identity for minimization is obtained by double inversion of the expression being simplified. The first inversion gives
The second inversion gives
To move from the AND, OR, NOT basis to the OR-HE basis, as well as to the AND-NOT basis, a logical formula transformation is also performed using double negation. Let's look at an example of a transition for relay circuit in Fig. 4.5, A, implemented in the AND, OR, NOT basis (Fig. 4.5, b), in the OR-HE basis (Fig. 4.5, V):
and in the AND-NOT basis (Fig. 4.5, G):
The number of dashes at the top of the formulas is equal to the number of negation elements, i.e. OR-HE and NAND elements. There are six negatives in the first formula, and accordingly the diagram in Fig. 4.5, V contains six OR-HE elements. The second formula contains five negatives, and accordingly the diagram in Fig. 4.5, G contains five NAND elements.
Rice. 45.
A - on relay elements; b - on the elements OR, AND, NOT; V - on the elements
OR-HE; Mr. NAND elements
Example 4.1
Simplify the expression / = (X + y)(x + z) and draw the relay equivalent before and after simplification. Here/ is the output signal (state of the closing contact) of the relay element F.
Solution
Let us simplify the given expression in accordance with the laws of logical algebra: Considering that X X = X, let's write down
Considering that 1 + at + z= 1, we will finally write /= X + at z. After simplification, the relay equivalent looks like this:
Simplify the expression f = x-y + x y-z +y-z and draw the relay equivalent before and after simplification.
Solution
Before simplification, the relay equivalent in accordance with the given expression looks like this:
Let us simplify the given expression in accordance with the laws of logical algebra, taking out common multiplier outside of brackets:
The relay diagram of this expression will take the form
It is taken into account here that x-z =x + z ia + a = 1, or x+z+x+z= 1, where a = x + z; a = x+z. Therefore, after transformation, the simplified expression will take the form
After simplifying the expression, the relay equivalent looks like this:
Let's check the correctness of the transformation using the state table (Table 4.2), which shows all possible combinations of two variables X and 2, and make sure that the expression x + g + x-z always equal to one.
Table 4.2
Status table
|
X+Z+X-Z |
||
Let's consider an example of using the algebra of logic to create a system automatic regulation water level in tank P (Fig. 4.6). The IM actuator supplies water to the reservoir by full opening or closing supply valve A. The tank has two water level sensors: sensor top level B and lower level sensor H. When the water level reaches or exceeds the position of the sensor, its signal becomes equal to one. If the water level drops below the sensor level, the signal at its output becomes zero.
Rice. 4.6.
Let's analyze the working conditions automatic system. If the water level reaches the lower level H, then the supply must be turned on. If the water level reaches the upper level B, the supply must be turned off. If the water level is intermediate between B and H, then the supply should remain turned on if it was turned on by sensor H. If the supply was turned off by sensor B, then it should remain turned off. Timing diagram of signals from the output of sensors and the control signal Q shown in Fig. 4.7.
Rice. 4.7.
in Fig. 4.6
Working conditions, i.e. all combinations of input signals and control signals are translated into the language of logic algebra and presented in Fig. 4.7 in the top table in the form of ones and zeros. The table indicates at what ratios of input signals there is or is no signal Q at the output of the relay ACS. The output signal is the result logical operations over the input signals.
If, according to the data in the table, we try to write down the operating conditions in the form of logical functions, we will find that the switched on control signal corresponds to two different ratios of input signals. The same applies to the switched off control signal. The result is an ambiguity in the output signal depending on the combination of input signals. At B = 0 and H = 1 there is a situation when Q = 0 is the position when Q=l. This means that the circuit must have a memory element, which can be used as the already familiar RS trigger T. To turn on the trigger, we use the appearance of a zero signal at output 11 (II = 0). This signal is inverted and supplied to the setting input S of trigger T. Since signal B does not change, we will not take it into account and write the condition for turning on S = H. We write the conditions for resetting the trigger and removing the control signal as R = B.
Using the same principle, systems are built to regulate temperature when cooling electrical machines and transformers, as well as power plants of cars and tractors using fans. The circuit can also be used to automatically maintain temperature by heating in residential and livestock premises.
Let's consider another example of using logic algebra to create logical relay protection of electrical objects using the example relay protection power transformer shown in Fig. 4.8.
Electrical installation rules provide for primary and backup protection for critical facilities. The main protection should turn off the object without a time delay, and the backup protection - with a time delay.
Rice. 4.8.
A -power circuit;b -protection circuit diagram
The main protection of transformer T1 in case of a short circuit in the transformer (short circuit at point K1) is differential relay protection (it is not shown in the diagram). Backup protection in case of a short circuit on the outgoing buses of the substation behind the Q2 switch (short circuit at point K2) is the maximum current protection that operates when the current relays KL1-K AZ are triggered. Short circuit in transformer T1 must be disconnected by switch Q1 from the action of backup protection without a time delay, i.e. "instantly". A short circuit at point K2 must be switched off without a time delay by switch Q2 (the protection of switch Q2 is not shown in the diagram). If for some reason the protection acting on switch Q2 or switch Q2 itself does not operate, then the time-delay backup protection must trip switch Q1.
Let's consider how we can increase the performance of the backup protection in question if a short circuit occurs in the transformer and the main protection does not work. To do this, measuring elements are placed at the input and output of transformer T1. They perform the function of determining the location of the fault: on the protected object or on a section of the external network. In the event of a short circuit on the protected object (short circuit in the main zone), they allow the operation of backup protection without a time delay, and in the event of an external short circuit, they block the instantaneous shutdown circuit, and the protection operates as a backup with a time delay.
Determining the location of the short circuit is performed as follows. During a short circuit in T1 (point K1), the current transformers TA 1-TAZ are flown around by the short-circuit current, and the current relay KA1-KAZ is activated. Current transformers TA4-TA5 at the output of transformer T1 are not subject to short-circuit current. Current relays KA4 and KA5 do not operate, their opening contacts are closed. In such a situation, the protection should operate without delay. Intermediate relay KL sends a signal to open switch Q1.
The operating conditions of the intermediate relay KL for disconnecting without a time delay can be verbally formulated as follows: the KL relay will work if the KL1 relay works, OR the KA2 relay works OR, the KAZ relay works AND the KA4 relay AND the KA5 relay do not work.
In mathematical logic symbols, the KL relay operation condition is written as follows:
During a short circuit in a section of the external network (point K2), the current transformers TA4 and TA5 are flown around by the short-circuit current, which leads to the operation of the current relays KA4 and KA5 and the opening of their breaking contacts in the relay protection circuit without a time delay. Thus, the operation of the protection without a time delay is blocked. Backup protection for short circuit at point K2 operates with a time delay.
The condition for operation of the backup protection time relay is formulated verbally as follows: the KT time relay will operate if the KA1 relay operates, OR the KA2 relay operates, OR the KAZ relay operates.
In mathematical logic symbols, the triggering condition of a time relay is written as
The complete operating condition of the intermediate relay KL, which turns off the switch Q1 without a time delay and with a time delay, is written as follows:
Scheme in Fig. 4.8, b constructed in accordance with equations (4.13) and (4.14). The activation of protection without a time delay (logical protection) is recorded by the indicator relay KN1. The operation of the time-delay protection is recorded by the indicator relay KN2.
The student must:
Know:
· Methods for minimizing logical functions.
Be able to:
· Perform function minimization using direct transformation method; Perform function minimization using direct transformation method;
· Perform function minimization using Karnaugh maps.
Direct transformation method
Logical function that specifies the principle of constructing a circuit digital device, can, as shown above, be presented in the form of a truth table or in the form of SDNF or SKNF and can be used to obtain the logical circuit of the device. However, the resulting logic circuit will generally not be optimal. That's why important stage synthesis logic circuits is the minimization of logical functions.
Minimization(simplification of the notation form) of a function is an important operation in the synthesis of a logical circuit, since thanks to preliminary minimization, the circuit is implemented with the smallest number of elements.
A number of methods have been developed for minimization. One of simple methods minimization is a method of direct transformations, which is carried out using the basic theorems of the algebra of logic.
For example, a logical function
in the form of SDNF, can be minimized as follows:
1. Add to this function the term that is already in this function, using the rule x+x=x
2. Let us apply the method of gluing together equally underlined elementary conjunctions
3. Let us apply the gluing method for the last two elementary conjunctions 
The logical function obtained as a result of minimization is called a dead-end function. A logical function can have several dead-end forms.
Identifying and eliminating redundancies in the recording of a function by transforming it using axioms, laws, identities and theorems of the algebra of logic require cumbersome calculations and are associated with at great expense time.
Carnot maps
The direct transformation method is most suitable for simple formulas, when the sequence of transformations is obvious to the performer. Most often, this method is used for the final minimization of expressions obtained after minimizing them by other methods.
The desire to algorithmize the search for neighboring elementary products led to the development tabular methods minimizing logical functions. One of them is a method based on the use of Karnaugh maps.
Carnot maps were invented in 1952 by Edward W. Veitch and improved in 1953 by Maurice Carnot, a physicist at Bell Labs, and were intended to help simplify digital electronic circuits.
A Karnaugh map is a graphical representation of the truth table of logical functions. It is a table containing 2 n rectangular cells, where n is the number of logical variables.
For example, a Karnaugh map for a function of four variables has 2 4 = 16 cells.
The structure of a Karnaugh map for functions of two variables is shown in Figure 2.2. 2
Figure 2.2
Figure 2.3 shows the structure of the Karnaugh map for functions of three variables.
a) truth table; b) structure of the Karnaugh map
Figure 2.3
The map is marked with a coordinate system corresponding to the values of the input variables. For example, top line maps for a function of three variables (Figure 2.3) corresponds to zero value variable x1, and the lower one - its unit value.
Each column of this map is characterized by the values of two variables: x2 and x3. The combination of numbers that mark each column shows for what values of the variables x2 and x3 the function placed in the cells of this column is calculated.
If on the specified set variable function is equal to one, then its SDNF necessarily contains an elementary product that takes the unit value on this set. Thus, the cells of the Carnot map representing a function contain as many units as there are elementary products contained in its SDNF, and each unit corresponds to one of the elementary products.
Let us note that the coordinates of the rows and columns in the Carnaugh map do not follow the natural order of increasing binary codes, but in the order 00, 01, 11, 10. The change in the order of the sets is done so that neighboring sets are adjacent, i.e. . differed in the value of only one variable.
Cells where the function takes values are equal to one, are filled with units. The remaining cells are filled with zeros.
Let's consider the minimization process using the example presented in Figure 2.4.
a) truth table; b) Carnaugh map
Figure 2.4
First, we form rectangles containing 2k cells, where k is an integer.
Neighboring cells that correspond to adjacent elementary products are combined into rectangles.
For example, in Figure 2.4b, cells with coordinates 001 and 101 are combined. When these cells are combined, a rectangle is formed in which the variable x1 changes its value. Consequently, it will disappear when gluing together the corresponding elementary products and only x2 and x3 will remain, and we take the variable x2 in inverse form, because it is equal to 0.
The cells located in the first row (Figure 2.4 b) contain units and are adjacent. Therefore, they are all combined into a rectangle containing 2 2 = 4 cells.
Variables x2 and x3 within the rectangle change their value; therefore, they will disappear from the resulting elementary product. Variable x1 remains unchanged and equal to zero. Thus, the elementary product obtained by combining the cells of the first row of Figure 2.4 b contains only one x1, which we take in inverse form, because it is equal to 0.
This, in particular, follows from the fact that the four cells of the first row correspond to the sum of four elementary products:
The two cells of the second column correspond to the sum of two products
The function corresponding to Figure 2.4 has the form:
The collection of rectangles covering all units is called a covering. Note that the same cell (for example, cell with coordinates 001) can be covered two or more times.
So, we can draw the following conclusions:
1. The formula resulting from minimizing a logical function using Carnaugh maps contains the sum of as many elementary products as there are rectangles in the coverage.
2. The more cells there are in a rectangle, the fewer variables are contained in the corresponding elementary product.
For example, for the Carnot map shown in Figure 2.5 a, a rectangle containing four cells corresponds to the elementary product of two variables, and a square consisting of only one cell corresponds to the elementary product 
including all four variables.
a B C)
Figure 2.5
The function corresponding to the coverage shown in Figure 2.5 a has the form:
Despite the fact that Carnot maps are depicted on a plane, the neighborhood of squares is established on the surface of the torus. The upper and lower boundaries of the Carnaugh map seem to be “glued together”, forming the surface of a cylinder. When gluing the side boundaries, a toroidal surface is obtained. Following the above reasoning, we establish that the cells with coordinates 1011 and 0011, shown in Figure 2.5 b, are adjacent and are combined into a rectangle. Indeed, the indicated cells correspond to the sum of elementary products
The remaining four unit cells are combined in the same way. As a result of their combination, we obtain an elementary product.
Finally, the function corresponding to the coverage shown in Figure 2.5 b has the form
The Carnaugh map shown in Figure 2.5c contains single cells located at the corners. All four cells are adjacent, and after combining they will give the elementary product
The examples discussed above allow us to formulate the sequence of minimizing logical functions using Karnaugh maps:
1. A table for n variables is displayed and its sides are marked.
2. The table cells corresponding to sets of variables that turn the function to one are filled with ones, the remaining cells are filled with zeros.
3. The best coverage of the table is selected with regular rectangles, which we outline. Each rectangle must have 2 n cells.
4. The same cells with units can be included in different contours.
5. The number of rectangles should be minimal, and the area of the rectangles should be maximum.
6. For each rectangle, we write down the product of only those variables that do not change their value. If this variable is equal to zero, then it is written in inverse form.
7. We connect the resulting products with a logical addition sign.
1. What are called minterms and minterms?
2.Write down the functions, given by tables 2.9 and 2.10 in SDNF and SKNF.
Table 2.9
3. Simplify logical functions using the identity axioms and laws of logical algebra:
a) 
c) 
Logic elements
The student must
Know:
· Logic state tables for basic functional logic circuits;
· Basic principles of constructing logical circuits.
Be able to:
· Define logical states at the exits digital circuits by known states at the inputs;
· Perform logical design in microcircuit bases;
· Select a microcircuit from the directory, based on the specified parameters and conditions of use.
The logic device principle is based in the IC at work bipolar transistors in key mode (either closed or open).
The logical action is carried out as with one (single-input logic element) and with a set (multi-input logic element) of input variables.
When operating logical devices, three main actions are used according to Boolean algebra - “AND”, “OR”, “NOT”.
A logical function can be expressed verbally, in algebraic form, by a truth table called a switch table, using timing diagrams. Let's consider all options for representing logical functions.
8.3. Analytical methods minimizing switching functions
Quine's method.
The method is based on pairwise comparison and gluing together, if possible, all constituents (members of the SDNF). To do this, each constituent is compared with subsequent ones, which leads to obtaining an implicant. The resulting implicants are again compared and, if possible, glued together - etc. until the remaining implicants can no longer be glued together. These are simple implicants; their disjunction is a shortened DNF.
For ordering, it is advisable to divide the constituents into groups according to the number of non-inverted variables. In this case, each successive constituent, starting from the top, is compared only with the constituents of the group adjacent to the bottom, with the number of non-inverted variables one more.
Let there be a switching function defined by SDNF:
Let us divide the constituents into groups according to the number of non-inverted variables.
The Roman numeral of the group number corresponds to the number of non-inverse variables. Let us draw lines indicating the constituents to be glued together. The result of gluing is always an elementary conjunction, which is a common part of the original conjunctions (in particular, a constituent).
The resulting implicants also allow gluing, and the result is the same implicant 
.
Further gluing is impossible, therefore the resulting implicants are simple, and the abbreviated DNF has the form:
The first stage is completed. At the second stage, it is necessary to eliminate unnecessary prime implicants. This is done using a special Quine implicant table (covering table). The rows of the table are marked with simple implicants of the switching function, i.e. members of the abbreviated DNF, and the columns are constituents of the unit, i.e. members of the SDNF switching function.
As already noted, a simple implicant absorbs some constituent of a unit if it is its own part. The corresponding cell of the implicant table at the intersection of the row of a given simple implicant and the columns with the constituents of the unit is marked, for example, with a “+” sign. Minimal DNFs are constructed using the implicant table as follows:
1) columns of the implicant table are searched that have only one cross; the simple implicants corresponding to these crosses are called basic and form the so-called core of the switching function. The core is necessarily included in the minimal DNF;
2) various options are considered for choosing a set of simple implicants that will cover the remaining columns of the implicant matrix with crosses, and options with the minimum total number of letters are selected.
The core of our function (Table 35) are implicants 
and x 1 x 2 x 3, i.e. the function has a unique deadlock and minimal DNF:
Table 35
Quine's implicant table
|
Constituents 1 (SDNF members) |
|||||||
|
implicants |
|
|
|
|
|
|
|
|
| |||||||
It can be seen that the implicant x 2 x 3 x 4 is redundant, since it covers constituents already covered by implicants 
, x 1 x 2 x 3 .
The number of crosses in a line is a power of 2; Moreover, you can make sure that it is equal to N=2 n - k, where k is the number of letters in a simple implicant, n is the number of variables on which the function depends.
If the SDNF is not specified at first, then it must be obtained using, for example, methods already known to us.
It is clear that for large implicant tables it is difficult to visually identify options with a minimum number of letters. Therefore, Petrik’s method is used, which makes it possible to obtain all dead-end DNFs from an implicant table by constructing its so-called conjunctive representation. To do this, all simple implicants are denoted by different letters (A, B, C in Table 35), and then for each column a disjunction is constructed of all letters denoting rows of the table, the intersection of which with a given column is marked with a cross. The conjunctive representation of the implicant matrix is formed as a conjunction of the constructed disjunctions for all columns. All relations of the Boolean algebra of switching functions can be applied to the conjunctive representation of the implicant table in order to simplify it. After opening the parentheses and performing all possible absorptions, we obtain a disjunction of conjunctions, each of which contains all the implicants of the dead-end DNF.
This means that a dead-end DNF contains two prime implicants ( 
and at the same time C=x 1 x 2 x 3) and has the form:
Quine-McCluskey method.
The method is a formalization of Quine's method, oriented towards the use of computers. Formalization consists of recording the constituents of the unit (members of the SDNF) with their binary numbers. All numbers are divided into disjoint groups according to the number of ones in the binary number. Bondings are made only between adjacent groups. The category to be eliminated is indicated by the sign “–” (“dash”). Further groups from the resulting implicants are formed taking into account the identical location of the dash. This designation of implicants is called generalized codes. Let a logical function be given
111101001000110.
Let us group these constituents of a unit by the number of units:
No further gluing is possible. The minimal DNFs are then found using the implicant table (Table 36):
This means that dead-end DNFs contain three prime implicants and have the form:
(two inversions);
(three inversions).
Table 36
Quine-McCluskey implicant table
|
implicants |
Constituents of units |
|||||||
Note that gluing two implicants with a dash is possible only if they are positioned appropriately, for example:
|
|
|
|
|
You can choose any of the obtained TDNFs, and, taking into account the smaller number of inversions, the first one.
Blake-Poretsky method.
The method allows one to obtain a reduced DNF of a Boolean function from its arbitrary DNF, and not from the SDNF, as in the Quine and Quine-McCluskey methods, using the law of generalized gluing. The method is based on the following statement: if in an arbitrary DNF of a Boolean function all possible operations inverse to the generalized gluing are performed, and then all absorptions are performed, then the result is a reduced DNF of the function.
Let the DNF function be given:
It can be seen that the law of generalized gluing with respect to the variable x 1 can be applied to the first and second conjunctions; we get:
Similarly for the first and third conjunctions:
those. everything remains as it is!
The second and third conjunctions admit generalized gluing along x2:
Let's move on to DNF:
After applying the law of idempotency (repetition) and absorption we get:
Attempts to further use generalized bonding and absorption do not yield results. Consequently, a reduced DNF function is obtained.
Table 37
Implicant table to illustrate the Blake-Poretsky method
|
implicants |
Feature Sets and its meanings |
|||||||||
Thus, working (unit) sets can be covered by three prime implicants, e.g. 
,
,
. The core includes implicants 
,
. Then deadlock DNFs have the form:
(better in terms of the number of inversions).
Methods for searching for minima of functions. The search for maxima is reduced to the search for minima by changing the sign of the function. M. f. m. is a branch of computational mathematics that plays an important role in applications such as optimal selection. options in planning, design and operations research, management tasks technological processes, motion control of complex objects, etc. M.f. m. are also used to solve systems of equations and inequalities when finding the spectrum of operators, when solving boundary value problems, etc.
The most studied are M. f. m - in relation to functions defined in the entire -dimensional Euclidean space. Let us consider them without touching on discrete and discrete-continuous minimization problems, as well as minimization problems in the presence of restrictions. The latter in many cases can be reduced to the problem of unconditional minimization (for example, using penalty functions). We will not consider methods for finding the minimum based on the direct use necessary conditions extremum, since the solution of the resulting systems of nonlinear equations can be considered as the problem of minimizing the sum of squared residuals (or the maximum modulus of residuals). Possibility of application and comparative effectiveness of various M. f. m. is largely determined by the class of functions to which they are applied. Most M. f. m. make it possible to find a local minimum, and only a priori information about the properties of the function (convexity, unimodality) allows us to consider this minimum global. Methods that guarantee the search for a global minimum with a given accuracy for fairly general classes of functions are very labor-intensive. On
In practice, to find the global minimum, a combination of the Monte Carlo method and one of the local minimization methods is mainly used.
Wide class M. f. m. is described by the following computational scheme. Let the function to be minimized be defined at an arbitrarily chosen starting point. Let us assume that it has continuous partial derivatives up to the order inclusive, we will consider it as a derivative of zero order). For getting successive approximations to the local minimum, a sequence of points is constructed according to the following form:
where denotes the vector of partial derivatives of the order of computable functions of its arguments. The order of higher partial derivatives calculated to implement formula (1) is called. order of the method. Basic a group of methods used in practice has the peculiarity that the information necessary to calculate the next value is expressed through a limited number of parameters calculated on this step and previous steps in the process. A method is called -step if the algorithm scheme has, starting from some following structure: at the step we calculate the parameters where is a certain natural number, and a vector according to the following form:
(initial parameters are calculated using special procedures). In widely used descent methods, the operator is specified in the following form:
where is a real number, which is called step multiplier, the vector determines the direction of descent. Among the descent methods, monotonous descent methods or relaxation methods stand out. The method is relaxation, if at k Beli is continuously differentiable, then the relaxation of method (3) is ensured when the direction of descent forms sharp corner with the direction of the gradient and is quite small. The general theory of relaxation processes is most fully developed for the case of convex functions. As a basis parameters characterizing the process, relaxation angles between and the direction of the gradient are considered), as well as relaxation factors determined by the equality
where is the gradient of the function (for a quadratic functional with steepest descent). Let us denote by the reduced coefficient. relaxation. Necessary and sufficient condition convergence of the relaxation process for a strongly convex function:
Among relaxation methods, the most famous are gradient methods. Let's take a closer look at single-stage gradient methods. General scheme they are as follows:
Within this scheme, the following modifications can be distinguished:
a) gradient descent with a constant step: identity matrix;
b) fastest gradient descent: , where is determined from the minimum condition
c) Newton-Raphson method: , where is the Hessian at the point
d) intermediate circuits: . The most common two-stage gradient methods include conjugate gradient methods; An example of a two-stage scheme is the Fletcher-Reeves conjugate gradient method:
Methods a) and b) with sufficient general conditions(the first - for a sufficiently small a) converge to a local minimum with a speed geom. progression. Method c) under sufficiently general conditions converges from a sufficiently small neighborhood of the minimum with a quadratic speed. Intermediate scheme d) is more flexible and allows, with a certain adjustment of the sequences, to also obtain a quadratic rate of convergence with weaker requirements for the initial approximation.
The disadvantage of methods c), d) is the need to calculate the Hessian. Conjugate gradient methods and so-called variable metric algorithms, which have the properties of accelerated convergence for sufficiently smooth functions in the vicinity of a minimum, are free from this drawback. Variable metric algorithm schemes are in nature a combination of the conjugate gradient scheme and the Newton-Raphson method. Simultaneously with the movement according to a scheme such as conjugate gradients, an iterative approximation of the matrix occurs, which is the inverse of the Hessian at the minimum point. After every n steps of the process there is a step according to the Newton-Raphson method, where its approximation is used instead.
If the gradient is broken, the above methods do not apply. That's why great importance have methods for minimizing convex (not necessarily differentiable) functions; These methods can be divided into 2 groups: 1) gradient-type methods and 2) “cutting plane” methods. Group 1 includes various modifications of the generalized gradient method, as well as schemes with accelerated convergence based on space stretching. in the direction of the gradient or the difference of two successive gradients. Methods of the 2nd group include, for example, the Kelly method. Let the ZP be a convex (bounded) set on which a sequence of points is defined at which the generalized gradient is calculated. Then it is found as a solution to the problem: find
Kelly's method converges in the functional for any initial . Of the common minimization methods, it should be noted, in particular, the ravine method for minimizing functions with highly elongated level hypersurfaces; coordinate search methods variable system coordinates; methods random search; combined methods of fast descent and random search, when the direction of decreasing function is determined by the Monte Carlo method; differential descent methods, stochastic approximation methods, etc. In optimal problems. of regulation, zero order search methods are of great importance. Minimization algorithms for this case are usually based on the idea of linear or quadratic approximation of the function being minimized or difference approximation of the corresponding partial derivatives. A number of methods have been proposed to search for the global extremum. Basic of which: Monte Carlo method, a combination of the Monte Carlo method for determining the starting point with one of the algorithms local search, methods based on the construction of the lower envelope of a given function, methods of sequential cutting off subsets, methods of constructing trajectories that densely cover the domain of definition of the function everywhere, and minimization along these trajectories.
To solve special classes of multiextremal problems, dynamic programming methods are used.
Nowadays, optimal times are created. algorithms for minimizing functions different classes. Let be a class of functions defined in the cube and having partial derivatives up to the sth order, satisfying the Lipschitz condition with constant L. Any minimization algorithm from , using information about the values of f and its derivatives up to order inclusive at no more than N points is equivalent (in the sense of the result) to some algorithm A for obtaining a sequence of iterations (1) for and approximating the desired value using the final operation
where is some computable function. Let us introduce the following notation:
The algorithm for which the optimal is achieved. The conditions mean asymptotic optimality and order optimality of the algorithm, respectively. It can be shown that
Moreover, the choice of , affects only the constant in the specified estimate. In a particular case we have:
where is min. network in .
Another approach to building optimal. Minimization algorithms are associated with the generalization of ideas for sequential statistical solutions. The minimization algorithm is considered as a controlled sequence of experiments, each of which gives a particular outcome. An a priori probability measure is determined based on the set of outcomes. After obtaining a specific outcome of the next experiment, the probabilities are redistributed according to the Bayes formula and the next experiment is selected or the final decision is made. Algorithms differ from each other in the rule by which the next experiment is selected, the rules for stopping and choosing the final solution. The quality of the solution is determined by the loss function, which is averaged in accordance with the result obtained on at this stage probability distribution. In these terms, the problem of choosing the optimal is posed. algorithm as the construction of a sequential Bayesian rule for finding solutions. This formulation is interesting in that within its framework it is possible to take into account the statistical properties of the class of problems being solved and to compare the “average” losses associated with the error of the solution with the costs associated with refining the solution. Lit.: Lyubich Yu. I., Maistrovsky G. D. General theory of relaxation processes for convex functionals. “Uspekhi Matematicheskikh Nauk”, 1970, vol. 25, century. 1; Mikhalevich V. S. Sequential optimization algorithms and their application. "Cybernetics", 1965, N5 1-2; Ivanov V.V. About optimal algorithms minimizing the functions of some classes. "Cybernetics", 1972, No. 4; Wild D. Dk. Methods for searching for extremum. Per. from English M., 1967.
V. V. Ivanov, V. S. Mikhalevich, N. Z. Shor.