The following "engineering-constructive" sense can be given to the representation of Boolean functions by formulas. We will consider the formula Ф (x 1, ..., xn) over some arbitrarily fixed set F as a "black box", a certain device, to the input of which all possible sets of values of variables are fed, and the output corresponding to these sets of values of the function f represented by the formula Ф (Fig. 6.22).
To understand how the "black box" works, we have to disassemble the process of constructing a formula from subformulas. Getting to the "basic" subformulas, i.e. elements of the set F, we come to the "building blocks", the structural elements from which the "black box" is assembled, which calculates the function f. Each function of the "basis" F is calculated by the corresponding "node", which is considered as the smallest structural unit of our "black box", and its internal structure is no longer analyzed.
Example 6.22. Let us choose a standard basis for the set F. Then the formula over the standard basis, representing the function ~ (equivalence), is constructed as follows:
The calculation according to this formula (and the process of constructing it from the elements of the standard basis) can be schematically depicted as shown in Fig. 6.23.
Variable x 1 (more precisely, the value of this variable) is fed to the input of a structural element called an inverter (Fig. 6.24, a) and calculating negation. The negative x 1 removed from the inverter output, i.e. function x 1, is fed to one of the inputs of the conjunctor (Fig. 6.24, b), to the second input of which the variable x 2 is fed. The function x 1 x 2 appears at the output of the conjunctor. The calculation of the function x 1 x 2 can be traced in a similar way, Both of these functions are fed to the inputs of the disjunctor (Fig. 6.24, c), from the output of which the function x 1 x 2 ∨ x 1 x 2 is removed (this is nothing but the sum modulo 2: x 1 ⊕ x 2). And finally, this function is fed to the input of the inverter, at the output of which the function ~ (equivalence) is already obtained. #
Thus, we come to the idea of a "circuit" - a mathematical model of the calculator of a Boolean function, represented by a certain formula, assembled from structural elements, each of which calculates one of the "basic" Boolean functions. In the general case, the "circuit" calculates a Boolean operator, and each coordinate function of this operator is removed from one of the outputs of the circuit.
Mathematically, a "schema" is defined as a directed graph of a special kind, in which both vertices and arcs are labeled.
Let us introduce the notation: if F is some set of Boolean functions, then by F (n) we denote the subset of F consisting of all functions of n variables (n≥0).
Definition 6.14. Let the sets be fixed: F (Boolean functions) and X (Boolean variables).
A diagram of functional elements over a basis F ∪ X (C Φ E), or simply contracted over the basis F ∪ X, also an (F, X) -scheme, is called an open-ended directed graph (i.e., a network), each vertex of which is labeled by one of the elements of the set FU X so that the following requirements are met:
- each input of the network is labeled either by some variable from X, or by some constant from F (0);
- if a vertex v of the network is labeled with a function f in n variables (that is, f ∈ F (n)), then its half-degree of entry is equal to n, and on the set of arcs entering the vertex v, a (one-to-one) numbering is given such that each the arc is numbered from 1 to n.
If the basis is implied, then we will say simply "scheme". In addition, if the set of variables is fixed "once and for all" and when considering various schemes we change only the set of functions F, then, as we did, introducing the concepts of a formula and superposition over a given basis, we will talk about an SFE over a basis F, assuming each times, which means once a fixed set of variables X, which (if this does not harm the accuracy) is not mentioned.
We now define by induction the notion boolean function computed by the top of the circuit .
Definition 6.15. Let the CFE be given S over a basis F ∪ X, the set of vertices of which is V.
- It is assumed that each input of the CFE calculates the Boolean function with which it is labeled (that is, some variable or constant).
- If a vertex v ∈ V is labeled with a function f ∈ F (n), the arc with the number i (1≤i≤n) entering it comes from the vertex ui ∈ V, which computes the function gi, then the vertex v computes the superposition f (g 1, ..., gn).
Thus, if each vertex of the CFE over F computes some function, then the order in which the functions g 1, ..., g n are enumerated, substituted in the places of the variables of the function f, is essential in the general case. It is natural to call a Boolean function f in n variables commutative if it preserves its value under an arbitrary permutation of its variables. In this case, we do not have to worry about the numbering of arcs entering the top of the circuit, marked with such a function.
Example 6.23. Consider the SPE in Fig. 6.25. The vertices v 1 and v 2 are the inputs of the SFE. These vertices calculate the functions x and y, respectively. Then the vertex v 3, as well as the vertex v 4, according to Definition 6.15, computes the function x | y (Schaeffer's stroke), and the vertex v 5 (output of the network) computes the function (x | y) l (x | y), which, is known to be equal to the conjunction x y.
The SPE shown in Fig. 6.26 has two outputs that compute the functions (x | x) | (y | y) = x ∨ y and (x | y) | (x | y) = x y.
Definition 6.16. Boolean function calculated by CFE over a basis F ∪ X, is a function calculated by any of its outputs.
Thus, the CFE calculates exactly how many Boolean functions, how many outputs. SFE in Fig. 6.25 calculates one function, and the SPE in Fig. 6.26 - two.
In the general case, if (x 1, ..., x n) is the set of all variables that serve as labels for the inputs of the circuit S over a basis F ∪ X with m outputs, CFE S defines the display of a boolean cube B n to boolean cube B m, i.e. boolean operator.
Remark 6.10. In some cases, the function calculated by a given SFE is defined somewhat differently, assuming that it is a function calculated by any vertex from the subset of the selected SFE vertices. In particular, it can be outputs. In any case, let us agree to draw an "output" arrow from the selected (in the just indicated sense) vertices of the circuit. #
Thus, each circuit of gates computes some Boolean operator, in particular, if the number of outputs of the circuit is equal to 1, then it computes some Boolean function.
The converse can also be proved: for any Boolean operator, a CFE can be constructed over a basis F, where F is a complete set that computes the given operator.
We represent the function y 1 in the Zhegalkin basis. Using de Morgan's laws, we get
(recall that the sum modulo 2 of any even number of equal terms is equal to 0).
y 1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE for the Boolean operator given in table. 6.9, over the Zhegalkin basis is shown in Fig. 6.27.
When designing a SFE, it is useful to keep in mind a numerical parameter called its complexity.
Complexity of SFE is the number of its vertices that are not inputs.
Shown in Fig. 6.27 The CFE over the Zhegalkin basis has complexity 5.
Let us now consider the CFE for the same operator over the standard basis.
According to the table (see Table 6.9), we construct the SDNF for the function y 2:
y 2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
The Karnot map for this function, shown in Fig. 6.28 shows that it cannot be minimized (more precisely, the above-written SDNF is the minimum DNF for this function). But you can go the other way. We can consider table. 6.9 as a table defining a partial boolean function y 2 = y 2 (x 1 x 2 x 3 y 1). By minimizing this function by
the Karnot map * shown in Fig. 6.29, we get
* On this map, we marked the sets on which the function takes the value 0, putting zeros in the corresponding cells. Thus, we want to once again draw attention to the fact that one should not confuse zeros with dashes: a dash in the cell of the map specifying a partial function means that the value of the function is not defined on this set, i.e. is neither 0 nor 1.
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
The CFE over the standard basis for the considered Boolean operator is shown in Fig. 6.30. The complexity of this SFE is 11. Note that the vertex calculating the function y 1 is not an output.
The Boolean operator in this example calculates the two-digit sum (modulo 2) of three one-digit terms. It can also be thought of as a one-bit binary adder — a functional block of a multi-bit binary adder — for two terms. Then the function y 1 is interpreted as a "carry signal" in the most significant bit. In fig. 6.31 shows the "connection" of three SFEs (such as shown in Fig. 6.30), with the help of which the sum of two three-digit binary numbers is calculated. The constant 0 is fed to the third input of the adder for the least significant bit, and the "carry signal" of the most significant bit is the most significant bit of the sum, which in the general case will be a four-digit number.
Remark 6.11. If we design the SFE over a standard basis and want to minimize its complexity, then we need to first of all construct the corresponding minimum DNF. In this case, we can take into account one more criterion by which the DNF itself is minimized - the number of negations. Among all minimal (in the sense of Definition 6.6) DNFs, one should select those in which the number of occurrences of variables under the negative sign is the smallest. From the point of view of the complexity of the SFE, which will be built on the basis of the minimum DNF, this means that it minimizes the number of "inverters" - the SFE vertices labeled with the negation function.
For example, for the function given by the Karnot map (Fig. 6.32), to the kernel consisting of simple implicants x 1 x 2 x 4 and x 1 x 3 x 4, you should add a simple implicant x 2 x 3 x 4, and not x 1 x 2 x 3 because it does not contain negatives.
In modern technology of control and computing devices, an important place is occupied by discrete converters, that is, devices that have a certain number of inputs and outputs. The sets of signals arriving at the inputs and arising at the outputs belong to known finite sets.
Share your work on social media
If this work did not suit you at the bottom of the page there is a list of similar works. You can also use the search button
Aranov Victor Pavlovich. Discrete Math. Section 5. DNF and FE circuits.
Lecture 28. Diagrams of functional elements. Analysis and synthesis problems
Lecture 28. DIAGRAMS FROM FUNCTIONAL ELEMENTS.
ANALYSIS AND SYNTHESIS PROBLEMS
Lecture plan:
1. The concept of a circuit of functional elements(FE).
2. Problems of analysis and synthesis of circuits from PV.
- The concept of a circuit from PV
In modern technology, control and computing devices occupy an important placediscrete converters, that is, devices that have a certain number of inputs and outputs. The sets of signals arriving at the inputs and arising at the outputs belong to known finite sets. The devices convert the input sets of signals to the output. The mathematical model of such devices is the so-calledfunctional element diagrams(SFE).
As an example, consider the electrical circuit of three diodes and resistance, shown in Fig. one.
Rice. 1. Electrical diagram and its symbol
At the points of the circuit shown in a circle, at different times, either a high level, approximately equal to 5 V, or a low level, approximately equal to zero, may appear. At the point in the circuit marked with a dash, the voltage level is constantly kept low.
The marked points will be interpreted as inputs, and the point - as an exit. The operation of the circuit can be described as follows: if all inputs have a low voltage level, then the output is also low, if at least one of the inputs has a high voltage level, then the output is high. If you designate a state with a high voltage level as one, and with a low voltage level - zero, then the dependence of the output on the inputs can be set using a Boolean function.
Based on this, the above circuit is called the logical element "OR".
Such circuits can be built from electronic tubes, electromechanical switches, pneumatic elements, etc. The dependence of the output on the inputs can be described not only as a disjunction, but also using conjunction, negation, and more complex Boolean functions.
We will consider logic gates with different dependences of the output on the inputs. These elements can be connected to each other, feeding the outputs of some elements to the inputs of others. As a result, we get SFE.
The definition of the concept of SFE can be divided into two stages. At the first stage, the structural part of this concept is revealed, at the second - the functional one.
I stage. Let's break this stage into a number of points.
1 ... There is a finite set of objects () calledlogical elements.Each element has inputs and one output. The element is graphically depicted as shown in Fig. 2.
2 ... By induction, we define the concept logical network as an object in which there is a certain number of inputs and a certain number of outputs (Fig. 3).
a) Basis of induction. An isolated vertex is called a trivial logical network. By definition, it is both an input and an output (Fig. 4).
… …
…
Rice. Fig. 2 Fig. 3 4
b) Inductive transition. This part is based on the use of three operations.
I ... The operation of combining disjoint networks. Let and be two disjoint networks (without common elements, inputs and outputs), having inputs and outputs, respectively. Set-theoretic network interconnection is a logical network that has inputs and outputs.
II ... The operation of attaching an element. Let the network and the element be such that in the selected different outputs with numbers. Then the figure is called the logical network, which is the result of the connection of the element to the network. Inputs are all inputs, outputs are all network outputs, except for outputs with numbers, as well as the output of an element. The network has inputs and outputs (Fig. 5).
… …
Rice. 6.
Rice. 5
III ... Splitting output operation. Let an outlet with a number be highlighted in the network. Then the figure is called the logical network obtained by splitting the output. Inputs are all inputs, outputs are all outputs of the network with numbers 1,…,…, and two more outputs that have arisen from the output with the network number (Fig. 6). Hence it has inputs and outputs.
3 ... Let alphabets and be given.
Diagram of functional elementsis called a logical network with inputs from the alphabet and outputs from the alphabet, which is denoted
. (1)
Here are some examples of circuits.
1. Let the set consist of three elements AND (conjunctor), OR (disjunctor) and NOT (inverter).
Then the figure (Fig. 6) will be a diagram, since it can be constructed using the operations I - III .
Rice. 6 Fig. 7
2. The figure shown in fig. 7 is also a schematic.
II stage. Determination of the functioning of the circuit.
4 ... Let us compare the CFE (1) with the system of functions of the Boolean algebra
(2)
also calledthe conductivity of this circuit.
Example. a) For the scheme, we have a system consisting of one equation
Or.
b) For the circuit, we similarly obtain
- Implementation of Boolean functions by FE circuits. Analysis and synthesis problems
circuits from PV
Analysis task: for a given SFE (1) to obtain a system of Boolean equations (2).
Algorithm for solving the problem: following the operations of building a network I - III , we sequentially calculate the functions at the outputs of the network elements.
The synthesis problem: for a given basis of functional elements and an arbitrary system of Boolean equations (2), construct a circuit (1) from the given FE that implements this system of equations.
The existence of a solution to the synthesis problem is determined by Post's theorem, according to which the system of functions that implement basic FEs must be complete. Functions can be represented as a superposition of functions, and each step of the superposition corresponds to a certain combination of elements.
Example. For function
(3)
The diagram corresponding to the superposition on the right-hand side of formula (3) is shown in Fig. eight.
Rice. eight
The synthesis problem lies in the fact that for a given system of Boolean equations it is possible to construct many FE circuits that implement this system. In this regard, the problem of optimal synthesis arises: from all kinds of schemes that implement a given function, choose the best one according to one or another criterion, for example, with the smallest number of elements. Such schemes will be called minimal.
The following statement is true.
Theorem. There is an algorithm that builds a minimal circuit for each system of Boolean functions.
This algorithm for constructing minimal circuits belongs to the class of algorithms of the "brute force" type, since it is based on viewing all circuits up to a certain complexity. Exhaustive search algorithms, as a rule, are very laborious and unsuitable for practical purposes. Therefore, we consider below a simpler problem for which the original system of equations contains one equation
and, therefore, the desired circuit has one output.
The complexity of the minimal circuit is denoted by. We will consider the synthesis problem not for a separate function, but for the entire class of functions of variables. The quality of the synthesis algorithms is compared by comparing the so-called Shannon functions. Let
- the minimum complexity of the schemes that implement, which are obtained using the algorithm.
Functions are called Shannon functions, and it is obvious that
The synthesis problem is to find an algorithm for which it would be as close as possible to, and so that the complexity of the algorithm would be significantly less than the complexity of the exhaustive search algorithm. With this formulation of the problem, it is not required that the algorithm finds the minimum circuit for each function, it is only necessary that the simplest circuit obtained with the help has a complexity that does not greatly exceed.
Other similar works that may interest you. Wshm> |
|||
| 9013. | METHODS FOR SYNTHESIS OF SCHEMES FROM FE. DECODER AND BINARY ADDER DIAGRAMS | 153.07 KB | |
| The general theory of CFE synthesis leads to the conclusion that the majority of Boolean functions for large values have complex minimal circuits. This means that a very narrow class of Boolean functions is of practical value from the point of view of synthesis. | |||
| 5321. | Types and values of automatic protection parameters for various elements of a given design scheme | 526.7 KB | |
| To ensure the normal operation of the power system and electricity consumers, it is necessary to identify and separate the place of damage from the undamaged network as soon as possible, restoring normal operating conditions for the power system and consumers. | |||
| 5384. | Development of an electrical circuit of the stand for analyzing the operation of a clocked decoder for 4 inputs and 16 outputs | 626.63 KB | |
| To improve the operation of the ATP rolling stock, the organizational structure of the maintenance and repair system for the ATP rolling stock has been developed, and a set of equipment for diagnostics and maintenance has been proposed. The main task of the functioning of the enterprise's repair facilities is to ensure the uninterrupted operation of the equipment. It includes: repair and restoration base of the enterprise, warehouses, shops and general departments of the repair facilities, technological equipment, dispatching. Organization... | |||
| 1886. | Stages of system analysis, their main goals, objectives | 27.44 KB | |
| The theory of optimal systems allows us to estimate the limit that can be reached in the optimal system, compare it with the indicators of the current non-optimal system and find out whether it is advisable in the case under consideration to develop an optimal system. For an automatically controlled process of an automatically controlled system, two optimization stages are distinguished: static and dynamic. Static optimization solves the issues of creating and implementing an optimal process model and dynamic ... | |||
| 5123. | Development of functional strategies | 35.44 KB | |
| HR strategy. Functions and management structure. Management functions and their role in the formation of management structures. Hierarchical type of management structure. | |||
| 20368. | Influence of the composition of recipe components and technologies on the consumer properties of functional products | 742.05 KB | |
| The concept of optimal nutrition is accepted by modern medical science. This means that a transition has been made from the concept of adequate nutrition, when macronutrients were mainly regulated and normalized - sources of fat, sources of energy, plastic material (lipids, proteins, fats), to the concept of optimal nutrition, when the spectrum of nutrients necessary for the vital activity of the body and others minor components that were previously overlooked are greatly expanded. | |||
| 4706. | Methods for the synthesis of Me carboxylates | 9.26 MB | |
| The essence of the method is to dissolve a metal oxide, hydroxide or carbonate in an aqueous solution of the corresponding acid. The product is isolated by evaporation of the solution prior to crystallization or by filtration of the precipitate if the carboxylate is insoluble or limitedly soluble in water. | |||
| 15923. | Basic methods for the synthesis of pyrazalodiazepines | 263.39 KB | |
| New methods for the synthesis of pyrazolodiazepine derivatives. The development of new synthesis strategies is of considerable interest. Systematic and generalizing studies of the synthesis of pyrazolodiazepine derivatives have not been carried out, some issues remain unaffected by controversy or completely unresolved. | |||
| 11978. | Energy technology installations based on hydrothermal oxidation of aluminum for the production of electricity, heat, hydrogen and functional nanomaterials | 49.89 KB | |
| The development is based on the reaction of hydrothermal oxidation of aluminum, during which a large amount of thermal energy is released and aluminum oxides and hydrogen are formed: l2H2O → lOOH boehmite15H2415. Distilled water and micron-sized aluminum powders are used as initial reagents. Installation KEU10 Installation ETK100 Technical characteristics of the ETK100 installation: Parameter Value Aluminum consumption kg h 101 Water consumption at the inlet to the water treatment device kg h 484 Productivity for hydrogen nm3 110 Thermal power ... | |||
| 6605. | Expert systems. TP design by synthesis method | 11.67 KB | |
| Representing the accumulation of knowledge and keeping it up to date is a complex task investigated in the section of informatics called knowledge engineering. The knowledge engineer participates in the development of the knowledge base - the core of systems called intelligent. Most often, intelligent systems are used to solve complex problems where the main complexity of the solution ... | |||
Size: px
Start showing from page:
Transcript
1 Lecture 2. Schemes of functional elements (SFE) in a certain basis. The complexity and depth of the scheme. Examples. Method for the synthesis of SFE from DNP. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Lectures on Discrete Mathematics 2. 1st year, group 141, Faculty of Computational Mathematics and Cybernetics, Moscow State University named after M.V. Lomonosov Lectures on the site
2 Diagrams of functional elements Let us define diagrams of functional elements in a certain basis. Let us be given some set of Boolean functions B = (g 1 (x 1, ..., x n1), ..., gs (x 1, ..., x ns)) P 2, where n 1, .. ., ns 0. We call this set a basis. Note that this concept of a basis has nothing to do with the concept of a basis P 2, which was considered in the algebra of logic. As a rule, we will consider the standard basis B 0 = (x & y, x y, x).
3 Definition of a circuit of functional elements A circuit of functional elements (CFE) in the basis B 0 = (x & y, xy, x) is 1) a directed acyclic graph G = (V, E), each vertex v V of which has a half-degree of entry d (v ) not exceeding two (d (v) 2); 2) each vertex v with a half-degree of entry equal to 0 (d (v) = 0) is called an input (or circuit input) and some Boolean variable x i is assigned to it; 3) all other nodes (except for inputs) are called internal nodes of the circuit;
4 Definition of a circuit of functional elements (continuation) 4) each vertex v with a half-degree of entry equal to 1 (d (v) = 1) is assigned a (functional) negation element; all such vertices are called inverters; 5) each vertex v with a half-degree of entry equal to 2 (d (v) = 2) is assigned either a (functional) conjunction element &, or a (functional) disjunction element; all the vertices to which the conjunction elements are assigned are called conjunctors, all the vertices to which the disjunction elements are assigned are called disjunctors;
5 Definition of a circuit of functional elements (continuation) 6) in addition, pairwise different output variables y 1, ..., y m are assigned to some of the vertices. If an SPE S is given, the inputs of which are assigned only the variables x 1, ..., xn, and with the output variables y 1, ..., ym, then we will denote this SPE by S (x 1, ..., xn; y 1, ..., ym).
6 Example of SFE Example 1. SFE S (x 1, x 2, x 3; y 1, y 2, y 3):
7 Example of SFE Example 1. As a rule, SFEs are depicted as follows S (x 1, x 2, x 3; y 1, y 2, y 3):
8 Determination of the complexity of the SFE The complexity L (S) of the SFE S is the number of internal vertices of this SFE, i.e. the number of functional elements in SFE S.
9 Complexity of SFE Example 2. Complexity of SFE S:
10 Determination of the depth of the vertex of the CFE By induction, we determine the depth d (v) of the vertex v in the CFE S. 1. Basis of induction. Each input v SFE S has a depth equal to 0: d (v) = Inductive transition. 1) If an arc from the vertex v 1 leads to the inverter v of the CFE S, then d (v) = d (v 1)) If the arcs from the vertices v 1 and v 2 lead to the conjunctor or disjunctor v of the CFE S, then d (v) = max (d (v 1), d (v 2)) + 1. The depth D (S) of the SFE S is called the maximum of the depths of its vertices.
11 Depth of the SFE Example 3. The depth of the tops of the SFE S and the depth of the SFE S:
12 Definition of the functioning of the SFE At each vertex of the SFE, a certain Boolean function is realized (or calculated). By induction, we define a Boolean function that is realized at the vertex v of the CFE S. 1) If v is the input vertex, and the variable x i is assigned to it, then the function f v = x i is realized at the vertex v. 2) If an arc from the vertex v 1 leads to the inverter v, and the function f v1 is realized at the vertex v 1, then the function f v = f v1 is realized at the vertex v. 3) If arcs from the vertices v 1 and v 2 lead to the conjunctor (or disjunctor) v, and the functions f v1 and f v2 are realized at the vertices v 1 and v 2, respectively, then at the vertex v the function fv = f v1 & f v2 ( respectively fv = f v1 f v2).
13 Functioning of the CFE It is believed that the CFE S (x 1, ..., xn; y 1, ..., ym) implements the system of Boolean functions FS = (f 1, ..., fm), which are realized at its output vertices y 1, ..., y m.
14 Functioning of the SFE Example 4. Boolean functions realized at the vertices of the SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 Linear program A linear program with inputs x 1, ..., xn over a basis B 0 = (x & y, xy, x) is a sequence z 1, z 2, ..., zt, in which for each number j, j = 1, ..., t, it holds that 1) either zj = xi; 2) either z j = z k for k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.
16 SFE and linear programs It is clear that the calculation in SFE can be rewritten as a linear program. Conversely, each linear program can be represented in the form of some SFE.
17 CFE and linear programs Example 5. CFE S corresponds to a linear program z 1 = x 1 & x 2, z 2 = x 3, z 3 = z 1 z 2.
18 SFE and their characteristics Schemes of functional elements are a computational model. The characteristics of the CFE that we have introduced show different aspects of the computational efficiency. The complexity of the CFE corresponds to the time of the sequential computation. The CFE depth corresponds to the parallel computation time. The maximum number of vertices with the same depth in the SFE corresponds to the number of processors in parallel computation.
19 Example: the sum of two bits Example 6. Construct an SPE in a standard basis that implements (calculates) the sum of two bits x and y. Solution. Let's write a table of the sum of two bits x and y. This sum can be a number with two binary digits, so we introduce two Boolean variables z 0, z 1, such that x + y = 2z 1 + z 0: x y z 1 z
20 Example: sum of two bits Solution (continued). Then z 0 = x y, z 1 = xy. Taking into account that x y = (x y) (x y), we obtain SPE: It is clear that L (S 1) = 3, and D (S 1) = 3.
21 SFE in an arbitrary basis The concept of SFE in an arbitrary basis B P 2 is introduced in a similar way.
22 Example: the sum of three bits Example 7. Construct the CFE in the basis P2 2 (that is, from all Boolean functions depending on two variables), realizing (calculating) the sum of three bits x, y and z.
23 Example: sum of three bits Solution. Similarly to example 6, we write a table of the sum of three bits x, y and z. This sum can also be a number with two binary digits, so we introduce two Boolean variables u 0, u 1, such that x + y + z = 2u 1 + u 0: x y z u 1 u
24 Example: sum of three bits Solution (continued). Then u 0 = x y z, u 1 = xy xz yz. Taking into account that xy xz yz = xy z (x y), we obtain the CFE: We see that L (S) = 5, and D (S) = 3.
25 Implementation of the Boolean function CFE Is it possible to implement an arbitrary Boolean function (or a system of Boolean functions) in the basis B 0 = (x & y, x y, x)? Can. How can this be justified? For example, like this. Because (x & y, x y, x) is a complete system in P 2, an arbitrary Boolean function f can be represented by a formula only through conjunction, disjunction and negation. For example, in the form of a perfect DNF, if f 0, and in the form of x & x, if f = 0. And then, using this DNF (formula), construct the corresponding SFE. This method of constructing the CFE for Boolean functions is called the DNF synthesis method.
26 Synthesis of SFEs from DNF And what complexity is obtained from SFE S from DNF for a Boolean function f (x 1, ..., x n), depending on n variables? A perfect DNF for a function f will contain at most 2 n elementary conjunctions. Each elementary conjunction is the conjunction of n variables or their negations.
27 Synthesis of SFE according to DNF Therefore, the circuit will contain: n inverters to implement all negations of variables x 1, ..., x n; by (n 1) conjunctor for the implementation of each of at most 2 n elementary conjunctions in a perfect DNF; at most (2 n 1) disjunctors to implement the disjunction of elementary conjunctions of DNF. We get that L (S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Complexity of a Boolean function The complexity L (f) of a Boolean function f (x 1, ..., x n) in the class of CFEs is the minimum complexity among all CFEs that implement the function f. Thus, we have proved the theorem: Theorem 1. For an arbitrary function f (x 1, ..., x n) P 2, L (f) n 2 n + n is true.
29 Problems for independent solution 1. For a Boolean function f (x 1, x 2, x 3) = (), construct an SPE in the standard basis of complexity. For a Boolean function f (x 1, x 2, x 3) = (), construct an SPE in standard basis of complexity For a Boolean function f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4, construct the CFE in the standard basis of depth Prove that in the standard basis L (xy) = 4.
30 Literature for the lecture 4 1. Yablonskiy S.V. An introduction to discrete mathematics. M .: Higher School, Part V, Ch. 2, with Gavrilov G.P., Sapozhenko A.A. Problems and exercises in discrete mathematics. Moscow: Fizmatlit, Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
31 End of Lecture 4
Lecture: Schemes of functional elements with delays (SPEZ), the automatism of the mappings carried out by them. Representation of KAV SFEZ. Simplifications of KAV. Distinctness and indistinguishability of CAV states. Moore's theorem
Lecture: Ansel's theorem on the partition of an n-dimensional cube into chains. A theorem on the number of monotone functions in the algebra of logic. A theorem on decoding monotone functions of the algebra of logic. Lecturer - Associate Professor Svetlana Selezneva
Lecture: Finite state machines with an exit (KAV). Automatic functions, methods of their assignment. A theorem on the transformation of periodic sequences by automatic functions. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva
Lecture: Partially ordered sets (PNS). CHUM diagram. Maximum, minimum, largest and smallest items. Chains and antichains, the length and width of the final PLS. A theorem on the decomposition of the PN into antichains.
Lecture 2. Properties of binomial coefficients. Calculation of sums and the method of generating functions (final case). Polynomial Coefficients. Estimates for binomial and polynomial coefficients. Sum estimates
Lecture: Algorithm for recognizing completeness in P k. Closed classes. Classes of functions preserving sets and preserving partitions, their closedness. Kuznetsov's theorem on functional completeness. Pre-complete classes.
Lecture 2. Combinatorics. Properties of binomial coefficients. Calculation of sums and the method of generating functions. Polynomial Coefficients. Estimates for binomial and polynomial coefficients. Asymptotic
Lecture: Finite-valued functions. Elementary k-valued functions. Methods for specifying k-valued functions: tables, formulas, 1st and 2nd forms, polynomials. Completeness. The theorem on the completeness of the Post system. Webb function.
Lecture 3. Sequences defined by recurrence relations. Homogeneous and inhomogeneous linear recurrent equations (LORU and LNRU). General solutions of LORU and LNRU. Lecturer - Associate Professor Svetlana Selezneva
Lecture 15. Functions of finite-valued logics. Elementary functions of k-valued logic. Methods for specifying k-valued logic functions: tables, formulas, I and II forms, polynomials. Completeness. Lecturer - Associate Professor Selezneva
Lecture: Functions of finite-valued logics. Elementary functions of k-valued logic. Methods for specifying k-valued logic functions: tables, formulas, I and II forms, polynomials. Completeness. Lecturer - Associate Professor Svetlana Selezneva
Lecture: The Möbius function on the PLM. Möbius function on the n-dimensional cube. Mobius inversion formula. Inclusion-exclusion principle. The problem of calculating the number of permutations-disturbances. Lecturer - Associate Professor Svetlana Selezneva
Lecture 2. Properties of binomial coefficients. The method of generating functions, the calculation of sums and the proof of identities. Polynomial Coefficients. Inclusion-exclusion principle. Lecturer - Associate Professor Svetlana Selezneva
Lecture: Essential functions. Three lemmas on essential functions. Yablonsky's completeness criterion. Slupecki's completeness criterion. Scheffer functions. Lecturer Associate Professor Svetlana Nikolaevna Selezneva [email protected]
Lecture: Basic combinatorial numbers. Estimates and asymptotics for combinatorial numbers. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva, Faculty of Computational Mathematics and Cybernetics, Moscow State University named after M.V. Lomonosov Lectures on the website http://mk.cs.msu.su
Lecture: Properties of binomial coefficients. Calculation of sums and the method of generating functions (final case). Polynomial Coefficients. Estimates for binomial and polynomial coefficients. Estimates for the sums of binomial
Lecture: Finite state machines with an exit. Transformation of periodic sequences by finite state machines with output. Distinctness of states in finite state machines with output. Simplification of machines. Lecturer Selezneva
Lecture: Set covering and matrix covering. Gradient coating. Gradient Cover Lemma. Estimates for the cardinality of the shading set of an n-dimensional cube. Estimates for the Length of Polynomial Normal Forms of Functions
Lecture 5. Covering a set and covering a matrix. Gradient coating. Gradient Cover Lemma. Estimates for the cardinality of the shading set of the Boolean cube. Length Bounds for Boolean Polynomial Normal Forms
Lecture 3. Sequences defined by recurrence relations. Homogeneous and inhomogeneous linear recurrent equations (LORU and LNRU). General solutions of LORU and LNRU. Examples Lecturer - Associate Professor Selezneva
Lecture 3. Relations on sets. Properties. Inclusion-exclusion formula. Equivalence relation. Partial order relation. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Lectures on Discrete Models.
Lecture 4. Features of multivalued logics. Closed class, closed class basis. Yanov and Muchnik's theorems on the existence in multivalued logics of closed classes without a basis and closed classes with countable
Lecture. Functions of natural argument (sequence). Homogeneous and inhomogeneous linear recurrent equations (LORU and LNRU). General solutions of LORU and LNRU. Examples Lecturer - Associate Professor Svetlana Selezneva
Lecture: Chromatic number of a graph. Criterion for two-color graph. Theorems on upper and lower bounds for the chromatic number of a graph. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Lectures on Discrete Models.
Lecture: Graphs and Networks. Estimate of the number of pseudographs with q edges. Estimate for the number of trees with q edges. Planar graphs. Euler's formula for planar graphs. The largest number of edges in planar graphs. Nonplanarity
Lecture 1. Combinatorics. Placements, permutations, placements with repetitions, combinations, combinations with repetitions. Their number. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Department of Mathematical Cybernernetics
Lecture: Sequences. Homogeneous and inhomogeneous linear recurrent equations. General solutions of linear recurrent homogeneous and inhomogeneous equations. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva
Lecture 8. Coloring. Equivalence of colorings relative to the group. Productive functions. An enumeration series for shapes and an enumeration series for functions. Polya's theorem. Lecturer Selezneva Svetlana Nikolaevna
Lecture: Coloring. Equivalence of colorings with respect to a permutation group. Polya's theorem (special case). Productive functions. An enumeration series for shapes and an enumeration series for functions. Theorem
Lecture 2. Conjunctive normal forms. Implicent, a simple implicent of a function. Abbreviated CNF function of the algebra of logic. Methods for constructing an abbreviated CNF. Lecturer Selezneva Svetlana Nikolaevna [email protected]
Mathematical models and methods of logical synthesis of VLSI Fall 2015 Lecture 4 Lecture plan Logical optimization of combinational logic circuits Various ways of representing functions of logic algebra (FAL)
Lecture: Non-deterministic finite automata (NFA) without exit. A theorem on the coincidence of the classes of sets of words admitted by finite deterministic and finite nondeterministic automata. Procedure
Lecture 1. Samples. Placements, permutations, placements with repetitions, combinations, combinations with repetitions, their number. Examples. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Lectures on the course Discrete
Lecture 1. Combinatorial objects: selections, arrangements, permutations, arrangements with repetitions, combinations, combinations with repetitions, their number. Combinatorial numbers: factorial, decreasing factorial, binomial
LECTURE 4 SCHEMES FROM FUNCTIONAL ELEMENTS 1. Basic definitions First of all, it is necessary to consider the composition. A function can be thought of as a "black box" that has an input and an output. Let
Lecture 2. Algorithm for recognizing completeness in P k. Kuznetsov's theorem. Closed classes. Classes of set-preserving functions. Classes of split-preserving functions. Pre-complete classes. Lecturer Doctor of Physical and Mathematical Sciences Selezneva
Lecture 3. Zhegalkin polynomial. Methods for constructing the Zhegalkin polynomial for a function. Linear implication of the function. Linear conjunctive normal form (LCNF). Finding all linear implications of the function. Examination
Lecture 2. Generating functions: calculating combinatorial sums and proving identities, enumerating combinatorial objects. Inclusion-exclusion principle. Counting the number of permutations-disturbances. Lecturer -
Lecture 5. Graphs. Graph coloring. The chromatic number of the graph. Criterion for two-color graph. Upper Bounds for the Chromatic Number of a Graph. Lecturer Doctor of Physical and Mathematical Sciences Selezneva Svetlana Nikolaevna [email protected] Lectures
Lecture: Finite automata (KA) without exit (finite automata recognizers). Transition diagrams. Automata sets (languages). Lemma on the properties of automatic sets. An example of a non-automatic set. Lecturer
Lecture 1. Finite-valued functions. Elementary k-valued functions. Methods for specifying k-valued functions: tables, formulas, 1st and 2nd forms, polynomials. Completeness. The theorem on the completeness of the Post system. Webb function.
Lecture 7. The problem of choosing routes and its special case is the problem of distribution of flights by day. Graph model for the flight distribution problem. The chromatic number of the graph. Criterion for two-coloration of a graph.
Course "Fundamentals of Cybernetics" for students of specialization 02/01/09/01 (mathematical and software for computers) 1. General information (study load, forms of control, etc.). The course is
Lecture 6. Graphs. Inherited properties of graphs. Estimate of the number of edges in graphs with hereditary property. Extreme graphs. The largest number of edges in planar and triangle-free graphs with a given
Math-Net.Ru All-Russian Mathematical Portal D. S. Romanov, A method for the synthesis of easily testable circuits that admit single checking tests of constant length, Diskr. Mat., 2014, Volume 26, Issue 2,
Lecture: Finite state machines without exit, deterministic and non-deterministic. A theorem on the coincidence of the classes of sets of words admitted by finite deterministic and non-deterministic automata. Procedure
Practical work 2 Construction of normal forms of a logical function Purpose of work: To learn to build conjunctive, disjunctive, perfect normal forms of a logical function Content of work: Basic
Seminar on the complexity of Boolean functions Lecture 1: Introduction A. Kulikov Computer Science club at POMI http://compsciclub.ru 09/25/2011 09/25/2011 1/26 Lecture plan 1 Boolean functions 2 Boolean circuits 3 Almost
Practical work 1 Analysis and synthesis of logic and relay control systems INTRODUCTION Discrete-acting devices made on the elements of hydro-, pneumo- and electroautomatics, and control microprocessors
Lecture: Regular expressions and regular sets. Kleene's theorem on the coincidence of classes of automatic sets and regular sets. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Lectures on Discrete Mathematics
Lecture 3 Boolean algebras and Boolean functions Boolean algebras The concept of algebraic systems Algebraic system or algebraic structure a set of symbols of a certain alphabet (support) with a given
Lecture 5. Graphs. Examples of applications of graphs. Transport problem. Network flow, Ford and Fulkerson's theorem on the maximum network flow. Algorithm for constructing the maximum flow in the network. Lecturer
Lecture: Graphs. Examples of applications of graphs. Transport problem. Network flow, Ford and Fulkerson's theorem on the maximum network flow. Algorithm for constructing the maximum flow in the network. Lecturer -
Lesson 8 Recall that for arbitrary sets A and B there are sets A B = (x x A and x B); (intersection of A and B) A B = (x x A or x B); (union of A and B) A \ B = (x x A and x / B) (difference of A and B).
Lecture 7. Ramsey numbers. Upper bound for the Ramsey number. Lower bound for the Ramsey number. Lecturer Selezneva Svetlana Nikolaevna [email protected] Faculty of CMC, Moscow State University named after M.V. Lomonosov Lectures on the website http://mk.cs.msu.ru
Lecture: Graphs. Basic concepts. Connected graphs. Trees. Spanning tree. The number of dangling vertices in the spanning tree. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Lectures on Discrete Models. Master,
Lecture 11. Boolean schemes. Discrete Mathematics, HSE, Faculty of Computer Science (Fall 2014 Spring 2015) By a Boolean circuit in variables x 1, ..., x n we mean a sequence of Boolean functions g
APPROVED Vice-Rector for Academic Affairs Yu. A. Samarskiy June 10, 2008 PROGRAM AND TASKS for the course DISCRETE STRUCTURES in the direction 010600 Faculty of FIET Department of Data Analysis Course II semester 4 Two
Lomonosov Moscow State University Faculty of Computational Mathematics and Cybernetics S. A. Lozhkin ELEMENTS OF THE THEORY OF SYNTHESIS OF DISCRETE CONTROL SYSTEMS Moscow 2016 Table of contents
Lecture: Inherited properties of graphs. Extreme graphs. Ramsey numbers. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva, Faculty of Computational Mathematics and Cybernetics, Moscow State University named after M.V. Lomonosov Lectures on the website http://mk.cs.msu.su Hereditary
Lecture: Operations on finite automata sets. Complement, union, intersection, product and iteration of automaton sets, their automaticity. Lecturer - Associate Professor Svetlana Nikolaevna Selezneva Lectures
Ministry of the Russian Federation for Communications and Informatization Volga Region State Academy of Telecommunications and Informatics Department of Higher Mathematics Approved by the Methodical Council of PSATI March 29, 2002
Lecture 5. Coloring of graph edges. The chromatic index of the graph. Chromatic index of bipartite graphs. Upper and lower bounds for the chromatic index of a graph. Lecturer Selezneva Svetlana Nikolaevna [email protected]
Math-Net.Ru All-Russian mathematical portal NP Red'kin, On circuits that admit short single diagnostic tests, Diskr. Mat., 1989, volume 1, issue 3, 71 76 Use of the All-Russian
MATHEMATICAL LOGIC (1) Tasks for practical exercises 1. Algebra of statements A statement is a quantity that can take on two meanings: true and false. Utterances are indicated in large Latin
Functional diagrams (FS) are designed to transform logical information. Initial information, encoded in the form of discrete signals, is fed to the inputs of the circuit `x n... Then this information is processed and in discrete form is read from the outputs of the circuit `at m(n, m- the number of its inputs and outputs). Consider FS that operate in two-valued logic and have one output ( m= 1). The transformation of information in them can be specified as a function of the algebra of logic at=f(x n). Instead of relay elements in FS, functional elements (FE) are used, which, as a rule, implement elementary logical functions.
Definition.Analysis is called the construction of a formula for the algebra of logic (if necessary, its truth table) for a given FS.
To construct a formula according to a given scheme, it is necessary to represent the relationship between the FE in the FS in the form of substitutions in the corresponding elementary functions. It is assumed that the processing of information is carried out in stages from inputs to outputs. In real circuits, additional elements are used to ensure the temporal coordination of the operation of all FS.
FS analysis can be performed in two ways - from inputs to outputs and from outputs to inputs. Let's consider the first method, using additional designations for intermediate circuit connections.
Example 1.(&, Ú, Ø) are taken as FE. Analyze the FE, the physical structure of which is given in Fig. 1.19.
Solution. Having designated the intermediate connections of the PV as shown in the figure, we determine the signals corresponding to them step by step . In this case, we move from the inputs of the circuit to its output.
Figure 1.19
STEP 1. R=`y, Q = `z.
STEP 2. X=x&R= x&`y, P=x& y, W=P&Q= x&y&`z.
STEP 3. Y=X&z=x&`y& z, U=P&z = x&y&z.
STEP 4. Z = YÚ U=x&`y&zÚ x&y&z.
STEP 5. F = ZÚ W=x&`y& zÚ x&y&zÚ x&y&`z.
Thus, the considered FS implements the following formula of the algebra of logic:
F(x,y,z) = x&`y&zÚ x&y&zÚ x&y&`z.
The found formula is SDNF. The vector of its truth values has the form (00000111) .
Depending on the initial data, among the tasks of synthesis (design) of the FS can be distinguished:
1) synthesis of circuits according to the given formulas,
2) synthesis of circuits for given functions.
Definition.By the synthesis of PS according to the given formula is called the construction of the FS structure corresponding to a given formula of the algebra of logic.
The solution of such problems is carried out according to the algorithm inverse to the method of analysis. As noted in Section 1.7, the structure of Boolean formulas allows only systems with parallel and sequential connections of elements to be mapped isomorphically. Therefore, the FS, which is isomorphic to the corresponding formula, should contain only compounds of this type.
Definition.By the synthesis of a PS for a given function is called the construction of a structural diagram that implements a given function of the algebra of logic.
Since the representation of functions by formulas is ambiguous, this problem has a non-unique solution. As in the case of relay circuits, the optimal ones are FS, consisting of a minimum number of PVs and connections between them. Such FS can be obtained using formulas with a minimum number of variables.
As for PC, we will separately consider formulas that are optimal in the class of normal forms (which are equal to the corresponding minimal forms), as well as absolutely optimal formulas obtained from minimal normal forms by further reducing them using the laws of logic algebra. The methods for obtaining optimal formulas are the same as in relay circuits. Example 1 considers the FS that implements the function (00000111) . This FS is not optimal, since the corresponding formula describes the SDNF F = x`y z Ú x y zÚ x y`z which is not minimal. Minimizing it, we get an MDNF of the following form: F = x yÚ x z. It corresponds to the FS in Fig. 1.20.
Figure 1.20
If we apply the distributive law to the MDNF, then we get a formula with even fewer variables: f = x(yÚ z). For this function, it coincided with the MCNF. An absolutely optimal scheme corresponds to it.
Figure 1.21
Obviously, this scheme is much simpler than the original one (Figure 1.19). Since the synthesis of optimal FS is reduced to the construction of minimal formulas, the optimal schemes in other bases are also constructed in a similar way. Analogs of the first and second distributive laws of the algebra of logic for Scheffer and Web forms can be obtained by replacing in these laws:
&(x,y)= Ø ½ ( x,y) = ¯ (Ø x,Ø y);
Ú ( x,y)= ½ (Ø x, Ø y) =Ø ¯ ( x,y).
Example 2. Construct an FS that implements a one-bit binary adder of two numbers using an FE corresponding to the basis (Ø, ¯), as well as in the basis (¯).
Solution. Let us denote one-bit binary numbers supplied to the input through ( X,at). The output should be their sum in the binary system. If x = 1, y = 1, then S = 2 10 = 10 2, therefore, to display it, in the general case, it is necessary to use two binary signs, and the FS must have two outputs. Let's denote them f(the most significant digit of the sum) and g(least significant bit). Function truth tables f (X,at),g(X,at):
| x | y | f(x,y) | g(x,y) |
We construct SVNF of functions in the basis (Ø, ¯). f has one unit in the truth vector, therefore its form consists of one constituent: f= ¯ (Ø x, Ø at). The function g SVNF has the form: g=د(¯( X,Ø at),¯(Ø X,at)). These forms are minimal. When combining the inputs of the elements, the functional diagram can be represented as follows:
Figure 1.22
In the considered example, it is impossible to simplify Web normal forms using the laws of logic algebra. In a single-function basis (¯) FS, we obtain, using the substitution Ø X= ¯ ( X,X). The corresponding circuit is shown in Figure 1.23.
Figure 1.23
TASKS
1. Construct using FE (&, Ú, Ø) optimal in the class of normal forms and absolutely optimal FS that implement the following functions:
a) ( x® y)Å zy; b) ( xÅ y)|z,v) xy® yz;G) x|(yÚ z); e) x®( y® z) ;
f) (10011101); g) (01101011); h) (1110101111111110) .
2. Construct using FE (Ú, Ø) FS functions 1.a) -g).
3. Construct using FE (&, Ø) FS functions 1.a) -g).
4. Construct an FS that implements a one-bit binary adder (Example 2) using an FE of the following form:
a) (&, Ú, Ø), b) (Ú, Ø) , c) (&, Ø), d) ( x | y} .
5. With the help of FE (&, Ú, Ø), construct the FS of the following devices:
a) a converter with binary inputs ( X,at), and exit f which works like this: when feeding x = 0 at the exit f =at, and when serving x = 1 at the entrance f =`y;
b) a selective device with binary inputs ( X,at) and outputs f 0 , f 1 , f 2 , f 3, which accepts at the input a combination of values ( x y) as a binary number i, lying in the range from 0 to 3. The values of the outputs for each i the following: f i= 1, and all the others f j= 0, (0 £ j£ 3, j¹ i).
6. Is it possible to take the following sets of functions as a basis for constructing FS:
a) (1001), (10001110),
b) (0101), (1011), (1101),
c) (1010), (01110001)?
Justify the answer.
7. Give examples of control functions, the FS of which cannot be constructed from only FE of the type (®).
8. Give examples of control functions, the FS of which cannot be constructed from only FE of the type (M, º).
9. Dana FS from FE (&, Ú, Ø).
Figure 1.24
Is it possible to exclude from it by equivalent conversions:
a) all elements (Ø)?
b) all elements (&)?
c) all elements (Ú)?
10. Optimize the FS from the FE (&, Ú, Ø), shown in Fig. 1.25.
Figure 1.25
Build FS:
a) optimal in the class of normal forms and
b) absolutely optimal.
31. Diagrams of functional elements, rules of construction and functioning, the method of synthesis of the SFE, based on SDNF and SKNF.
DefinitionDefinition. A functional element is a mathematical model of an elementary discrete converter, which, according to a certain law, converts the signals coming to it at the input into a signal at the output of the converter. From functional elements, with the help of some rules, it is possible to build models that are more complex in structure and functioning - diagrams from functional elements. In these models, the input and output signals are encoded with the characters 0 and 1.
Construction rules. To obtain complex SFEs from simpler ones, the operations of splitting the input or output of the circuit, connecting the functional element to the circuit and connecting the functional element to the input or output of the circuit are sequentially applied. These operations resemble the rules for obtaining a complex formula from simpler ones using superposition.
Synthesis of SFE. Since disjunction, conjunction and negation form a complete system in the class R 2, then any Boolean function of n arguments can be implemented by a circuit of functional elements - disjunctors, conjunctors and inverters - with n inputs and one output. To do this, you can, for example, express this Boolean function through SDNF or SKNF and then "synthesize" the resulting formula in the form of a circuit of functional elements, sequentially applying the above splitting, joining and connecting operations.
32. The method of synthesis of the SFE, based on the compact implementation of all conjunctions using a universal multipole, the complexity of the resulting circuits.
Definition... An argument function is called a Boolean function (or a Boolean function) if it assigns a number to each set.
To define Boolean functions, we will use tables, vectors, formulas and graphs. Let us take the following notation: is the set of all sets, where.
Definition. A functional element is a mathematical model of an elementary discrete converter, which, according to a certain law, converts the signals coming to it at the input into a signal at the output of the converter. From functional elements, with the help of some rules, it is possible to build models that are more complex in structure and functioning - diagrams from functional elements. In these models, the input and output signals are encoded with the characters 0 and 1.
Method for the synthesis of SFE, based on the compact implementation of all conjunctions using a universal multipole. This method is also based on the representation of a function in the form of SDNF, but it allows one to build less complex circuits due to a more compact implementation of conjunctions. The decomposition of a function in SDNF can contain conjunctions that have common factors. If two such conjunctions are implemented in one subcircuit in a block, then this will require at least one fewer conjunctors than were required before, with the independent implementation of all conjunctions by the first synthesis method. A compact implementation of all possible conjunctions of length n can be achieved using an inductively built universal multipole, which has n inputs and 2 n outputs where n = 1,2,3, ... The advantages of the method are especially noticeable when one circuit needs to implement a system of several Boolean functions. In this case, it would be possible to split and then pass through the disjunctors those outputs of the universal multipole that correspond to the conjunctions included in the SDNF of the functions of the given system. This would make it possible to get by with fewer conjunctors than if each function of a given system was independently implemented by its own subcircuit.
The complexity of such a multipole is L() =.
If a circuit of gates Σ contains exactly r functional elements, then they say that it has complexity r and write it in the form of equality L(Σ) = r.
| " |
