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 more than a 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, an SFE 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.
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 with 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.
| " |
Lecture 2. Diagrams of functional elements
(SFE) in a certain basis. Complexity and depth
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 CMC, Moscow State University named after M.V. Lomonosov
Lectures on the site http://mk.cs.msu.su
SFE Examples Synthesis of SFE from DNP
Diagrams of functional elements
Let's define circuits of functional elements in a certain basis.
Let us be given some set of Boolean functions B = (g1 (x1, ..., xn1), ..., gs (x1, ..., xns)) P2, where n1, ..., ns 0.
Let's call this set a basis.
Note that this concept of a basis has nothing to do with the concept of a basis P2, which was considered in the algebra of logic.
As a rule, we will consider the standard basis B0 = (x & y, x y, x).
SFE Examples Synthesis of SFE according to DNF Determination of a circuit from functional elements A circuit from functional elements (SFE) in the basis B0 = (x & y, x y, x) is
1) 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 xi is assigned to it;
3) all other nodes (except for inputs) are called internal nodes of the circuit;
4) each vertex v with a half-degree of approach 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;
SFE Examples Synthesis of SFE according to DNF Determination of a circuit from functional elements (continued)
6) in addition, pairwise different output variables y1, ..., ym are assigned to some of the vertices.
If an SPE S is given, the inputs of which are assigned only the variables x1, ..., xn, and with the output variables y1, ..., ym, then we will denote this SPE by S (x1, ..., xn; y1, .. ., ym).
SFE Examples Synthesis of SFE from DNP
- & nbsp– & nbsp–
Determination of the depth of the SPE vertex By induction, we determine the depth d (v) of the vertex v in the SPE S.
1. Basis of induction. Each input v of the SFE S has a depth equal to 0: d (v) = 0.
- & nbsp– & nbsp–
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.
SFE Examples Synthesis of SFE from DNF 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
u0, u1 such that x + y + z = 2u1 + u0:
- & nbsp– & nbsp–
Literature for lecture 4
1. Yablonsky S.V. An introduction to discrete mathematics. M .:
Higher School, 2001. Part V, Ch. 2, p. 336-355.
2. Gavrilov G.P., Sapozhenko A.A. Problems and exercises in discrete mathematics. Moscow: Fizmatlit, 2004. Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
SFE Examples Synthesis of SFE from DNP
The following "engineering-constructive" sense can be given to the representation of Boolean functions by formulas. We will consider a formula over some arbitrarily fixed set as a "black box", a kind of device, to the input of which all sorts of sets of variable values are fed, and the output corresponding to these sets of values of the function 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 a set, we come to "building blocks", structural elements from which a "black box" is assembled that calculates a function. Each function of the "basis" 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 as a set. Then a formula over a standard basis representing a 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.
A variable (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 removed from the inverter output, i.e. function is fed to one of the inputs of the conjunctor (Fig. 6.24.5), to the second input of which a variable is fed. A function appears at the output of the conjunctor. The calculation of the function 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 is removed (this is nothing more than a sum modulo 2:). Finally, this function is fed to the input of the inverter, the output of which is already a function (equivalence).
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 is some set of Boolean functions, then by denotes the subset consisting of all functions of variables.
Definition 6.14. Let the sets be fixed: (Boolean functions) and (Boolean variables).
A circuit of functional elements over a basis (SFE), or simply a circuit over a basis, also (F, X) -scheme, is called an open-ended directed graph (i.e., a network), each vertex of which is labeled with one of the elements of the set so that the following requirements:
1) each input of the network is labeled either by some variable from, or by some constant from;
2) if a vertex v of the network is labeled with a function of variables (i.e.), then its half-degree of entry is equal, and on the set of arcs entering the vertex, a (one-to-one) numbering is given, in which each arc gets a number from 1 to.
When drawing diagrams, inputs are denoted by circles, and vertices that are not inputs are denoted by triangles, inside which is written the designation of the function that marks this vertex. Exits are marked with "exit" arrows. In fig. 6.25 shows the SPE over the basis.
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 a set of functions, 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, assuming each time, which implies a once fixed set of variables, which (if this does not harm the accuracy) is not mentioned.
Let us now define by induction the notion of a Boolean function computed by a vertex of a circuit.
Definition 6.15. Let the CFE be given over the basis, the set of vertices of which is.
1. It is assumed that each input of the CFE calculates the Boolean function with which it is labeled (that is, some variable or constant).
2. If a vertex is marked with a function, an arc with a number entering it comes from the vertex that evaluates the function, then the vertex v computes the superposition.
Thus, if each vertex of the CFE over computes a certain function, then the order in which the functions substituted in place of the function variables are enumerated is essential in the general case. It is natural to call a Boolean function of 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 and are the inputs of the SFE. These vertices calculate the functions and, respectively. Then the vertex, as well as the vertex, according to Definition 6.15, calculates the function (Schaeffer's stroke), and the vertex (output of the network) calculates the function, which is known to be equal to the conjunction.
The SPE shown in Fig. 6.26, has two outputs that calculate the functions and.
Definition 6.16. A Boolean function calculated by the CFE over a basis is a function calculated by any of its outputs.
Thus, the CFE calculates exactly as many Boolean functions as it has outputs. SFE in Fig. 6.25 calculates one function, and the SPE in Fig. 6.26 - two.
In the general case, if is the set of all variables that serve as labels for the inputs of a circuit over a basis that has g outputs, the CFE defines a mapping from a Boolean cube to a Boolean cube, 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, an SFE can be constructed over a basis, where is the complete set that computes the given operator.
Example 6.24. Let's set the table to a Boolean operator that maps to (Table 6.9).
It is easy to see from the table that (a function is nothing but a majority function of variables, and the minimum DNF for it is written above, see Example 6.12). We represent the function in the Zhegalkin basis. Using de Morgan's laws, we get
Considering that, we will have
(recall that the sum modulo 2 of any even number of equal terms is equal to 0). So,
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.
The complexity of the SPE 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. Using the table (see Table 6.9), we construct the SDNF for the function
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. By minimizing this function according to the Karnot map * shown in Fig. 6.29, we get
* On this map, we have explicitly marked the sets on which the function takes on the value 0 by 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.
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 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 r / 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.
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 Determination of a circuit of functional elements A circuit of functional elements (CFE) in the basis B 0 = (x & y, xy, x) is 1) an oriented 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 an 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 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 (ie, 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 Povolzhskaya 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 allow 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
