Superposition of Boolean functions. Operations of superposition and closure. Completeness, basis of a system of functions What is a superposition of functions

Let there be a function f(x 1 , x 2 , ... , x n) and functions

then we will call the function superposition of a function f(x 1 , x 2 , ... , x n) and functions .

In other words: let F = ( f j ) - a set of logical algebra functions, not necessarily finite. A function f is called a superposition of functions from the set F or a function over F if it is obtained from a function by replacing one or more of its variables with functions from the set F.

Example.

Let a set of functions be given

F = (f 1 (x 1), f 2 (x 1 ,x 2 ,x 3), f 3 (x 1 ,x 2)).

Then superpositions of functions from F will be, for example, the functions:

j 1 (x 2 , x 3) = f 3 (f 1 (x 2), f 1 (x 3));

j 2 (x 1 , x 2) = f 2 (x 1 , f 1 (x 1), f 3 (x 1 , x 2)).

Perfect DNF - superposition of functions from a set

. ð

Definition.

The system of functions is called full, if using the operations of superposition and replacement of variables, any function of the algebra of logic can be obtained from the functions of this system. ð

We already have a certain set of complete systems:

;

Because ;

Because ;

(x+y, xy, 1). ð

How can we determine the conditions under which the system is complete? Closely related to the concept of completeness is the concept of a closed class.

Closed classes.

The set (class) K of functions of the algebra of logic is called closed class, if it contains all functions obtained from K by operations of superposition and change of variables, and does not contain any other functions.

Let K be some subset of functions from P 2 . The closure of K is the set of all Boolean functions that can be represented using the operations of superposition and change of variables of functions from the set K. The closure of a set K is denoted by [K].

In terms of closure, we can give other definitions of closure and completeness (equivalent to the original ones):

K is a closed class if K = [K];

K is a complete system if [K] = P 2 .

Examples.

* (0), (1) - closed classes.

* A set of functions of one variable is a closed class.

* - closed class.

* Class (1, x+y) is not a closed class.

Let's look at some of the most important closed classes.

1. T 0- class of functions that preserve 0.

Let us denote by T 0 the class of all functions of the algebra of logic f(x 1 , x 2 , ... , x n) preserving the constant 0, that is, functions for which f(0, ... , 0) = 0.

It is easy to see that there are functions that belong to T 0, and functions that do not belong to this class:

0, x, xy, xÚy, x+y О T 0 ;

From the fact that Ï T 0 it follows, for example, that it cannot be expressed through disjunction and conjunction.

Since the table for the function f from the class T 0 contains the value 0 in the first line, then for functions from T 0 you can set arbitrary values ​​only on 2 n - 1 set of variable values, that is

,

where is the set of functions that preserve 0 and depend on n variables.

Let us show that T 0 is a closed class. Since xÎT 0 , then to justify the closedness it is enough to show the closedness with respect to the operation of superposition, since the operation of changing variables is a special case of superposition with the function x.

Let . Then it is enough to show that . The latter follows from the chain of equalities

2. T 1- class of functions preserving 1.

Let us denote by T 1 the class of all functions of the algebra of logic f(x 1, x 2, ... , x n) preserving the constant 1, that is, functions for which f(1, ... , 1) = 1.

It is easy to see that there are functions that belong to T 1, and functions that do not belong to this class:

1, x, xy, xÚy, xºy О T 1 ;

0, , x+y Ï T 1 .

From the fact that x + y Ï T 0 it follows, for example, that x + y cannot be expressed in terms of disjunction and conjunction.

The results about the class T 0 are trivially transferred to the class T 1 . Thus we have:

T 1 - closed class;

.

3. L- class of linear functions.

Let us denote by L the class of all functions of the algebra of logic f(x 1 , x 2 , ... , x n) that are linear:

It is easy to see that there are functions that belong to L and functions that do not belong to this class:

0, 1, x, x+y, x 1 º x 2 = x 1 + x 2 + 1, = x+1 О L;

Let us prove, for example, that xÚy Ï L .

Let's assume the opposite. We will look for an expression for xÚy in the form of a linear function with undetermined coefficients:

For x = y = 0 we have a=0,

for x = 1, y = 0 we have b = 1,

for x = 0, y = 1 we have g = 1,

but then for x = 1, y = 1 we have 1v 1 ¹ 1 + 1, which proves the nonlinearity of the function xy.

The proof of the closedness of the class of linear functions is quite obvious.

Since a linear function is uniquely determined by specifying the values ​​n+1 of the coefficient a 0 , ... , a n , the number of linear functions in the class L (n) of functions depending on n variables is equal to 2 n+1 .

.

4. S- class of self-dual functions.

The definition of the class of self-dual functions is based on the use of the so-called principle of duality and dual functions.

The function defined by the equality is called dual to the function .

Obviously, the table for the dual function (with the standard ordering of sets of variable values) is obtained from the table for the original function by inverting (that is, replacing 0 with 1 and 1 with 0) the column of function values ​​and turning it over.

It's easy to see that

(x 1 Ú x 2)* = x 1 Ù x 2 ,

(x 1 Ù x 2)* = x 1 Ú x 2 .

It follows from the definition that (f*)* = f, that is, the function f is dual to f*.

Let a function be expressed using superposition through other functions. The question is, how to construct a formula that implements ? Let us denote by = (x 1, ..., x n) all the different variable symbols found in the sets.

Theorem 2.6. If function j is obtained as a superposition of functions f, f 1, f 2, ..., f m, that is

a function dual to a superposition is a superposition of dual functions.

Proof.

j*(x 1 ,...,x n) = ` f(`x 1 ,...,`x n) =

The theorem has been proven. ð

The principle of duality follows from the theorem: if a formula A realizes the function f(x 1 , ... , x n), then the formula obtained from A by replacing the functions included in it with their dual ones realizes the dual function f*(x 1 , ... , xn).

Let us denote by S the class of all self-dual functions from P 2:

S = (f | f* = f )

It is easy to see that there are functions that belong to S and functions that do not belong to this class:

0, 1, xy, xÚy Ï S .

A less trivial example of a self-dual function is the function

h(x, y, z) = xy Ú xz Ú ​​yz;

Using the theorem on the function dual to superposition, we have

h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; h = h* ; h О S.

For a self-dual function, the identity holds

so on sets and , which we will call opposite, the self-dual function takes opposite values. It follows that the self-dual function is completely determined by its values ​​in the first half of the rows of the standard table. Therefore, the number of self-dual functions in the class S (n) of functions depending on n variables is equal to:

.

Let us now prove that the class S is closed. Since xÎS , then to justify the closedness it is enough to show the closedness with respect to the operation of superposition, since the operation of changing variables is a special case of superposition with the function x. Let . Then it is enough to show that . The latter is installed directly:

5. M- class of monotonic functions.

Before defining the concept of a monotonic function in the algebra of logic, it is necessary to introduce an ordering relation on the set of sets of its variables.

They say that set comes before set (or “not more than”, or “less than or equal to”), and use the notation if a i £ b i for all i = 1, ... , n. If and , then we will say that the set strictly precedes the set (or “strictly less”, or “less than” the set), and use the notation . Sets and are called comparable if either , or . In the case when none of these relations hold, the sets and are called incomparable. For example, (0, 1, 0, 1) £ (1, 1, 0, 1), but the sets (0, 1, 1, 0) and (1, 0, 1, 0) are incomparable. Thus, the relation £ (often called the precedence relation) is a partial order on the set B n. Below are diagrams of the partially ordered sets B 2, B 3 and B 4.

The introduced partial order relation is an extremely important concept that goes far beyond the scope of our course.

Now we have the opportunity to define the concept of a monotonic function.

The logic algebra function is called monotonous, if for any two sets and , such that , the inequality holds . The set of all monotone functions of the algebra of logic is denoted by M, and the set of all monotone functions depending on n variables is denoted by M(n).

It is easy to see that there are functions that belong to M and functions that do not belong to this class:

0, 1, x, xy, xÚy О M;

x+y, x®y, xºy Ï M .

Let us show that the class of monotone functions M is a closed class. Since xОМ, then to justify the closedness it is enough to show the closedness with respect to the operation of superposition, since the operation of changing variables is a special case of superposition with the function x.

Let . Then it is enough to show that .

Let be sets of variables, respectively, functions j, f 1 , ... , f m , and the set of variables of function j consists of those and only those variables that appear in the functions f 1 , ... , f m . Let and be two sets of values ​​of the variable, and . These sets define the sets variable values , such that . Due to the monotonicity of the functions f 1 , ... , f m

and due to the monotonicity of the function f

From here we get

The number of monotonic functions depending on n variables is not known exactly. The lower bound can be easily obtained:

where - is the integer part of n/2.

It also just turns out to be too high an estimate from above:

Refining these estimates is an important and interesting task of modern research.

Completeness criterion

Now we are able to formulate and prove a completeness criterion (Post's theorem), which determines the necessary and sufficient conditions for the completeness of a system of functions. Let us preface the formulation and proof of the completeness criterion with several necessary lemmas that have independent interest.

Lemma 2.7. Lemma on a non-self-dual function.

If f(x 1 , ... , x n)Ï S , then a constant can be obtained from it by substituting the functions x and `x.

Proof. Since fÏS, then there is a set of variable values
=(a 1 ,...,a n) such that

f(`a 1 ,...,`a n) = f(a 1 ,...,a n)

Let's replace the arguments in the function f:

x i is replaced by ,

that is, let's put and consider the function

Thus, we have obtained a constant (although it is not known which constant it is: 0 or 1). ð

Lemma 2.8. Lemma about non-monotonic function.

If the function f(x 1 ,...,x n) is non-monotonic, f(x 1 ,...,x n) Ï M, then a negation can be obtained from it by changing variables and substituting the constants 0 and 1.

Proof. Since f(x 1 ,...,x n) Ï M, then there are sets of values ​​of its variables, , , such that , and for at least one value i, a i< b i . Выполним следующую замену переменных функции f:

x i will be replaced by

After such a substitution we obtain a function of one variable j(x), for which we have:

This means that j(x)=`x. The lemma is proven. ð

Lemma 2.9. Lemma about nonlinear function.

If f(x 1 ,...,x n) Ï L , then from it by substituting the constants 0, 1 and using the function `x we can obtain the function x 1 &x 2 .

Proof. Let us represent f as a DNF (for example, a perfect DNF) and use the relations:

Example. Let us give two examples of the application of these transformations.

Thus, a function written in disjunctive normal form, after applying the indicated relations, opening parentheses and simple algebraic transformations, becomes a polynomial mod 2 (Zhegalkin polynomial):

where A 0 is a constant, and A i is a conjunction of some variables from the number x 1,..., x n, i = 1, 2, ..., r.

If each conjunction A i consists of only one variable, then f is a linear function, which contradicts the condition of the lemma.

Consequently, in the Zhegalkin polynomial for the function f there is a term that contains at least two factors. Without loss of generality, we can assume that among these factors there are variables x 1 and x 2. Then the polynomial can be transformed as follows:

f = x 1 x 2 f 1 (x 3 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., x n) + f 4 (x 3 ,..., x n),

where f 1 (x 3 ,..., x n) ¹ 0 (otherwise the polynomial does not include a conjunction containing the conjunction x 1 x 2).

Let (a 3 ,...,a n) be such that f 1 (a 3 ,...,a n) = 1. Then

j(x 1 ,x 2) = f(x 1 ,x 2 , a 3 ,...,a n) = x 1 x 2 +ax 1 +bx 2 +g ,

where a, b, g are constants equal to 0 or 1.

Let's use the negation operation that we have and consider the function y(x 1 ,x 2) obtained from j(x 1 ,x 2) as follows:

y(x 1 ,x 2) = j(x 1 +b, x 2 +a)+ab+g.

It's obvious that

y(x 1 ,x 2) =(x 1 +b)(x 2 +a)+a(x 1 +b)+b(x 2 +a)+g+ab+g = x 1 x 2.

Hence,

y(x 1 ,x 2) = x 1 x 2 .

The lemma is completely proven. ð

Lemma 2.10. The main lemma of the completeness criterion.

If the class F=( f ) of logical algebra functions contains functions that do not preserve unity, do not preserve 0, are non-self-dual and non-monotonic:

then from the functions of this system, by operations of superposition and replacement of variables, one can obtain the constants 0, 1 and the function.

Proof. Let's consider the function. Then

.

There are two possible cases of subsequent considerations, designated in the following presentation as 1) and 2).

1). The function on the unit set takes the value 0:

.

Let's replace all the variables of the function with the variable x. Then the function

there is, because

And .

Let's take a non-self-dual function. Since we have already obtained the function, then by the lemma on a non-self-dual function (lemma 2.7. ) you can get a constant from. The second constant can be obtained from the first using the function. So, in the first case considered, constants and negation are obtained. . The second case, and with it the main lemma of the completeness criterion, are completely proven. ð

Theorem 2.11. A criterion for the completeness of systems of functions in the algebra of logic (Post's theorem).

In order for the system of functions F = (f i) to be complete, it is necessary and sufficient that it is not entirely contained in any of the five closed classes T 0, T 1, L, S, M, that is, for each of the classes T 0 , T 1 , L , S, M in F there is at least one function that does not belong to this class.

Necessity. Let F be a complete system. Let us assume that F is contained in one of the indicated classes, let us denote it by K, i.e. F Í K. The last inclusion is impossible, since K is a closed class that is not a complete system.

Adequacy. Let the entire system of functions F = (f i ) not be contained in any of the five closed classes T 0 , T 1 , L , S , M . Let us take the following functions in F:

Then, based on the main lemma (lemma 2.10 ) from a function that does not preserve 0, a function that does not preserve 1, non-self-dual and non-monotonic functions, one can obtain the constants 0, 1 and the negation function:

.

Based on the lemma on nonlinear functions (lemma 2.9 ) from constants, negation and a nonlinear function we can obtain the conjunction:

.

Function system - a complete system according to the theorem about the possibility of representing any function of the algebra of logic in the form of a perfect disjunctive normal form (note that disjunction can be expressed through conjunction and negation in the form ).

The theorem is completely proven. ð

Examples.

1. Let us show that the function f(x,y) = x|y forms a complete system. Let's build a table of values ​​of the function x½y:

f(0,0) = 1, therefore x | yÏT 0 .

f(1,1) = 0, therefore x | yÏT 1 .

f(0,0) = 1, f(1,1) = 0, therefore x | yÏM.

f(0,1) = f(1,0) = 1, - on opposite sets x | y takes the same values, therefore x | yÏS .

Finally, what does the nonlinearity of the function mean?
x | y.

Based on the completeness criterion, we can state that f(x,y) = x | y forms a complete system. ð

2. Let us show that the system of functions forms a complete system.

Really, .

Thus, among the functions of our system we found: a function that does not preserve 0, a function that does not preserve 1, non-self-dual, non-monotonic and nonlinear functions. Based on the criterion of completeness, it can be argued that the system of functions forms a complete system. ð

Thus, we are convinced that the completeness criterion provides a constructive and effective way to determine the completeness of systems of functions in the algebra of logic.

Let us now formulate three corollaries from the completeness criterion.

Corollary 1. Any closed class K of functions of the algebra of logic that does not coincide with the entire set of functions of the algebra of logic (K¹P 2) is contained in at least one of the constructed closed classes.

Definition. The closed class K is called pre-full, if K is incomplete and for any function fÏ K the class K È (f) is complete.

From the definition it follows that the precomplete class is closed.

Corollary 2. In the algebra of logic there are only five precomplete classes, namely: T 0, T 1, L, M, S.

To prove the corollary, you only need to check that none of these classes is contained in the other, which is confirmed, for example, by the following table of functions belonging to different classes:

Corollary 3. From any complete system of functions one can select a complete subsystem containing no more than four functions.

From the proof of the completeness criterion it follows that no more than five functions can be distinguished. From the proof of the main lemma (Lemma 2.10 ) it follows that either non-self-dual or does not preserve unity and is not monotonic. Therefore, no more than four functions are needed.

In the scientific community, a widely known joke on this topic is that “nonlinearity” is compared to a “non-elephant” - all creatures other than “elephants” are “non-elephants”. The similarity lies in the fact that most systems and phenomena in the world around us are nonlinear, with a few exceptions. Contrary to this, in school we are taught "linear" thinking, which is very bad in terms of our readiness to perceive the pervasive nonlinearity of the Universe, be it its physical, biological, psychological or social aspects. Nonlinearity concentrates in itself one of the main difficulties of cognition of the surrounding world since the effects, in their total mass, are not proportional to the causes, two causes, when interacting, are not additive, that is, the effects are more complex than a simple superposition, functions of the causes. That is, the result resulting from the presence and influence of two causes acting simultaneously is not the sum of the results obtained in the presence of each of the causes separately, in the absence of the other cause.  

Definition 9. If, on a certain interval X, a function z-φ(lz) with a set of values ​​Z is defined and a function y =/(z) is defined on the set Z, then the function y is a complex function of x (or a superposition of the function), and the variable z - an intermediate variable of a complex function.  

Controlling can be represented as a superposition of three classical management functions - accounting, control and analysis (retrospective). Controlling as an integrated management function makes it possible not only to prepare a decision, but also to ensure control over its implementation using appropriate management tools.  

As is known /50/, any time function can be represented as a superposition (set) of simple harmonic functions with different periods, amplitudes and phases. In general, P(t) = f(t),  

The transient or impulse characteristics are determined experimentally. When they are used using the superposition method, the selected model of the input influence is first decomposed into elementary "functions of time, and then the responses to them are summed up. The latter operation is sometimes called convolution, and the integrals in expressions (24) ... (29) are convolution integrals. From They choose the one whose integrand is simpler.  

This theorem reduces the conditional extremum problem to a superposition of unconditional extremum problems. Indeed, let us define the function R (g)  

Superposition ((>(f(x)), where y(y) is a non-decreasing convex function of one variable, /(x) is a convex function, is a convex function.  

Example 3.28. Let's return to Example 3.27. In Fig. Figure 3.24 shows in the form of a dashed-dotted curve the result of the superposition of two membership functions corresponding to the quantifiers that are present in this example. Using a cutoff level of 0.7, fuzzy intervals are obtained on the x-axis. Now we can say that the dispatcher should expect a change in plan  

Another way of defining the function F, different from the superposition method, is that when any quantifier is applied to another quantifier, a certain monotonic transformation of the original membership function occurs, which comes down to stretching and shifting the maximum of the function in one direction or another.  

Example 3.29. In Fig. Figure 3.25 shows two results obtained using superposition and stretch shift for the case where XA and X correspond to the quantifier often. The difference seems to be that superposition isolates in the membership function those values ​​that occur frequently. In the case of shift and stretch, we can interpret the result as the appearance of a new quantifier with the value often-often, which can, if desired, be approximated, for example, by the value very often.  

Show that the superposition of a strictly increasing function and a utility function representing some preference relation > is also a utility function representing that preference relation. Which of the following functions can act as such a transformation?  

The first of relations (2) is nothing more than a record of the rule according to which each function F(x) belonging to the family of monotonically nondecreasing absolutely continuous functions is associated with one and only one continuous function w(j). This rule is linear, i.e. the principle of superposition is true for him  

Proof. If the mapping F is continuous, the function M0 is continuous as a superposition of continuous functions. To prove the second part of the statement, consider the function  

Complex functions (superpositions)  

The method of functional transformations also involves the use of a heuristic approach. For example, the use of logarithmic transformations as operators B and C leads to information criteria for constructing identifiable models and the use of a powerful tool of information theory. Let operator B represent a superposition of the operators of multiplication by the function, (.) and shift by the function K0(), operator C is the operator  

Here we will outline the results of solving a number of variational problems (1)-(3). They were solved by the method of sequential linearization (19-21) back in 1962-1963, when the technology of the method was just beginning to take shape and was being tested. Therefore, we will focus only on some details. First of all, we note that the functions C and C2 were specified by rather complex expressions, which are a superposition of auxiliary functions, including those specified in tables. Therefore, when solving the conjugate system φ = -fx using functions specified in a table. Typically, such tables contain a small number of values ​​for a set of nodes in the range of changes in the independent argument, and between them the function is interpolated linearly, since the use of more accurate interpolation methods is not justified due to the inaccuracy of the table values ​​themselves (as a rule, functional dependencies of an experimental nature are specified by tables). However, for our purposes we need differentiable functions /(x, u), so we should prefer smooth methods of completing a table-specified function (for example, using splines).  

Let now (DA and (q) be arbitrary functions corresponding to some values ​​of the frequency quantifiers. Figure 3.23 shows two one-humped curves corresponding to these functions. The result of their superposition is a two-humped curve, shown by a dashed line. What is its meaning If, for example, (YES there is rarely, and (d - often,  

The advantage of this method of determining F is that during monotonic transformations the form of the membership function does not change dramatically. Its unimodality or monotonicity is preserved, and the transition from a new type of function (2.16) has a trapezoidal shape, then the linear superposition (2.15) is a trapezoidal fuzzy number (which is easily proven when using the segment calculation rule). And we can reduce operations with membership functions to operations with their vertices. If we denote the trapezoidal number (2.16) as (ab a2, az, a4), where a correspond to the abscissa of the vertices of the trapezoid, then  

- (Late Lat. superpositio, - overlay, from Lat. superpositus - placed on top) (composition) - logical-mathematical operation. calculus, which consists in obtaining from k.l. given functions f and g given calculus of a new function g (f) (expression g... ... Philosophical Encyclopedia

The term superposition (superposition) can refer to the following concepts: Superposition composition of functions (complex function) The principle of superposition is a principle in physics and mathematics that describes the superposition of processes (for example, waves) and, as a consequence, ... ... Wikipedia

Composition of functions, composing a complex function from two functions... Mathematical Encyclopedia

This term has other meanings, see Superposition. Quantum mechanics ... Wikipedia

This article or section contains a list of sources or external references, but the sources of individual statements remain unclear due to the lack of footnotes... Wikipedia

In the theory of discrete functional systems, a Boolean function is a function of type, where is a Boolean set and n is a non-negative integer, which is called the arity or locality of the function. Elements 1 (one) and 0 (zero) are standardly interpreted ... ... Wikipedia

One of the most important for the foundations of mathematics and mathematics. logic classes of concepts that serve as clarifications contain. the concepts of an effectively computable arithmetic function and an effectively decidable arithmetic predicate, and ultimately, and... ... Philosophical Encyclopedia

Function, the calculation of the values ​​of a swarm can be carried out using a predetermined efficient procedure, or algorithm. A characteristic feature of computational processes is the calculation of the required quantities of problems occurs sequentially from the initial data... ... Mathematical Encyclopedia

It is necessary to transfer the contents of this article to the article “Differentiation of a complex function”. You can help the project by combining articles. If it is necessary to discuss the feasibility of merging, replace this template with the template ((to merging)) ... Wikipedia

- (lat. compositio composition, linking, addition, connection): Wiktionary has an article “composition” Art Composition (fine art) is an organizing component of an artistic form that gives pro... Wikipedia

Books

• Discrete mathematics. Basic set-theoretic constructions. Part VI, A.I. Shirokov. The manual is part VI of the section “Basic set-theoretic constructions of discrete mathematics”. In ch. XI considers the following concepts: compositions of functions (§1); functions,...

Definition of function, scope and value set. Definitions related to function notation. Definitions of complex, numeric, real, monotonic and multivalued functions. Definitions of maximum, minimum, upper and lower bounds for bounded functions.

Function y = f (x) is called a law (rule, mapping), according to which, each element x of the set X is associated with one and only one element y of the set Y.

The set X is called domain of the function.
Set of elements y ∈ Y, which have preimages in the set X, is called set of function values(or range of values).

Domain of definition functions are sometimes called definition set or many tasks functions.

Element x ∈ X called function argument or independent variable.
Element y ∈ Y called function value or dependent variable.

The mapping f itself is called characteristic of the function.

The characteristic f has the property that if two elements and from the definition set have equal values: , then .

The symbol denoting the characteristic may be the same as the symbol of the function value element. That is, you can write it like this: . It is worth remembering that y is an element from the set of function values, and is the rule by which the element x is associated with the element y.

The process of calculating a function itself consists of three steps. In the first step, we select an element x from the set X. Next, using the rule, the element x is associated with an element of the set Y. In the third step, this element is assigned to the variable y.

Private value of the function call the value of a function given a selected (particular) value of its argument.

Graph of function f called a set of pairs.

Complex functions

Definition
Let the functions and be given. Moreover, the domain of definition of the function f contains a set of values ​​of the function g. Then each element t from the domain of definition of the function g corresponds to an element x, and this x corresponds to y. This correspondence is called complex function: .

A complex function is also called composition or superposition of functions and sometimes denoted as follows: .

In mathematical analysis, it is generally accepted that if a characteristic of a function is denoted by one letter or symbol, then it specifies the same correspondence. However, in other disciplines, there is another way of notation, according to which mappings with the same characteristic, but different arguments, are considered different. That is, the mappings are considered different. Let's give an example from physics. Let's say we consider the dependence of momentum on coordinates. And let us have a dependence of coordinates on time. Then the dependence of the impulse on time is a complex function. But, for brevity, it is designated as follows: . With this approach, and are different functions. Given the same argument values, they can give different values. This notation is not accepted in mathematics. If a reduction is required, a new characteristic must be introduced. For example . Then it is clearly visible that and are different functions.

Valid functions

The domain of a function and the set of its values ​​can be any set.
For example, number sequences are functions whose domain is the set of natural numbers, and the set of values ​​is real or complex numbers.
The cross product is also a function, since for two vectors and there is only one value of the vector. Here the domain of definition is the set of all possible pairs of vectors. The set of values ​​is the set of all vectors.
A Boolean expression is a function. Its domain of definition is the set of real numbers (or any set in which the comparison operation with the element “0” is defined). The set of values ​​consists of two elements - “true” and “false”.

Numerical functions play an important role in mathematical analysis.

Numeric function is a function whose values ​​are real or complex numbers.

Real or real function is a function whose values ​​are real numbers.

Maximum and minimum

Real numbers have a comparison operation. Therefore, the set of values ​​of a real function can be limited and have the largest and smallest values.

The actual function is called limited from above (from below), if there is a number M such that the inequality holds for all:
.

The number function is called limited, if there is a number M such that for all:
.

Maximum M (minimum m) function f, on some set X, the value of the function is called for a certain value of its argument, for which for all,
.

Top edge or exact upper bound A real function bounded above is the smallest number that bounds its range of values ​​from above. That is, this is a number s for which, for everyone and for any, there is an argument whose function value exceeds s′: .
The upper bound of a function can be denoted as follows:
.

The upper bound of an upper bounded function

Bottom edge or exact lower limit A real function bounded from below is the largest number that bounds its range of values ​​from below. That is, this is a number i for which, for everyone and for any, there is an argument whose function value is less than i′: .
The infimum of a function can be denoted as follows:
.

The infimum of a lower bounded function is the point at infinity.

Thus, any real function, on a non-empty set X, has an upper and lower bound. But not every function has a maximum and a minimum.

As an example, consider a function defined on an open interval.
It is limited, on this interval, from above by the value 1 and below - the value 0 :
for everyone.
This function has an upper and lower bound:
.
But it has no maximum and minimum.

If we consider the same function on the segment, then on this set it is bounded above and below, has an upper and lower bound and has a maximum and a minimum:
for everyone;
;
.

Monotonic functions

Definitions of increasing and decreasing functions
Let the function be defined on some set of real numbers X. The function is called strictly increasing (strictly decreasing)
.
The function is called non-decreasing (non-increasing), if for all such that the following inequality holds:
.

Definition of a monotonic function
The function is called monotonous, if it is non-decreasing or non-increasing.

Multivalued functions

An example of a multivalued function. Its branches are indicated by different colors. Each branch is a function.

As follows from the definition of the function, each element x from the domain of definition is associated with only one element from the set of values. But there are mappings in which the element x has several or an infinite number of images.

As an example, consider the function arcsine: . It is the inverse of the function sinus and is determined from the equation:
(1) .
For a given value of the independent variable x, belonging to the interval, this equation is satisfied by infinitely many values ​​of y (see figure).

Let us impose a restriction on the solutions of equation (1). Let
(2) .
Under this condition, a given value corresponds to only one solution to equation (1). That is, the correspondence defined by equation (1) under condition (2) is a function.

Instead of condition (2), you can impose any other condition of the form:
(2.n) ,
where n is an integer. As a result, for each value of n, we will get our own function, different from others. Many similar functions are multivalued function. And the function determined from (1) under condition (2.n) is branch of a multivalued function.

This is a set of functions defined on a certain set.

Multivalued function branch is one of the functions included in the multi-valued function.

Single-valued function is a function.

Used literature:
O.I. Besov. Lectures on mathematical analysis. Part 1. Moscow, 2004.
L.D. Kudryavtsev. Course of mathematical analysis. Volume 1. Moscow, 2003.
CM. Nikolsky. Course of mathematical analysis. Volume 1. Moscow, 1983.

Single-cycle (not containing memory elements) discrete logic devices implement at the output a certain set of logic algebra functions `F m =(F 1 ,F 2 ,…,F m), which at each moment of time depend only on the state of the device inputs `x n =(x 1 ,x 2 ,…,x n): `F m = `F m(`x n). In practice, such devices are designed and manufactured from separate indivisible elements that implement a certain set (system) ( f) elementary functions of algebra by connecting the outputs of some elements to the inputs of others.

When designing logic devices, the following questions are relevant.

1. A system of elementary functions is given ( f). What are the output functions? F i can be obtained using functions from ( f}?

2. A set of output Boolean functions ( F) (in particular, equal to the entire set of functions of the algebra of logic R 2). What should be the initial system of elementary functions ( f), providing the possibility of obtaining at the output any of the functions of the set ( F}?

To provide a reasonable answer to these questions, the concepts of superposition, closedness and completeness of systems of functions are used.

Definition. Let's consider a set of logical connectives ( F), corresponding to some system of functions ( f} . Superposition over{f) is any function j that can be realized by a formula over ( F}.

In practice, superposition can be represented as the result of substituting functions from ( f) as arguments to a function from the same set.

Example 1. Consider a system of functions ( f} = {f 1 (X) =`x, f 2 (x,y)= X&y, f 3 (x,y)=XÚ y). Substituting into the function f 3 (x,y) instead of the first argument X function f 1 (X), instead of the second - f 2 (x,y), we get the superposition h(x,y)=f 3 (f 1 (X),f 2 (x,y))=`xÚ X& at. The physical implementation of the substitution is given in Fig. 1.18.

Definition. Let M-certain set of logical algebra functions( P 2). The set of all superpositions over M called short circuit sets M and is denoted by [ M]. Receiving [ M]by the original set M called closure operation. Many M called functionally closed class, If [ M] = M. Subset mÍ M called functionally complete system in M, If [ m] = M.

Closure [ M] represents the entire set of functions that can be obtained from M by applying the superposition operation, i.e. all possible substitutions.

Notes. 1. Obviously, any system of functions ( f) is functionally complete in itself.

2 . Without loss of generality, we can assume that the identity function f(X)=x, which does not change the truth values ​​of variables, is initially part of any system of functions.

Example 2. For the systems of functions discussed below ( f) do the following:

1) find the closure [ f],

2) find out whether the system ( f) closed class,

3) find functionally complete systems in ( f}.

Solution.

I. ( f}={0} . When substituting the function ( fº 0) we receive it into ourselves, i.e. no new functions are created. It follows: [ f] = {f). The considered system is a functionally closed class. The functionally complete system in it is one and equal to the whole ( f}.

II. ( f} = {0,Ø } . Substitution Ø (Ø X)gives an identical function that does not formally extend the original system. However, when substituting Ø (0) we obtain an identical unit - a new function that was not in the original system: Ø (0)=1 . Application of all other substitutions does not lead to the appearance of new functions, for example: ØØ 0 = 0, 0(Ø X)=0.

Thus, the use of the superposition operation made it possible to obtain a wider set of functions than the original one [ f]=(0,Ø ,1). This implies a strict entry: ( f} Ì [ f]. Source system ( f) is not a functionally closed class. In addition to the system itself ( f) there are no other functionally complete systems in it, since in the case of its narrowing from one function f= 0 cannot be negated by substitution, and identical zero cannot be obtained from the negation function alone.

III. ( f) = (& ,Ú ,Ø ).The closure of this system is the entire set of functions of the algebra of logic P 2, since the formula of any of them can be represented as DNF or CNF, which uses elementary functions ( f) = (& ,Ú ,Ø). This fact is a constructive proof of the completeness of the considered system of functions in P 2: [f]=P 2 .

Since in P 2 contains an infinite number of other functions other than ( f) = (& ,Ú ,Ø ), then this implies a strict occurrence: ( f}Ì[ f]. The considered system is not a functionally closed class.

In addition to the system itself, subsystems will be functionally complete ( f) 1 = (& ,Ø ) and ( f) 2 = (Ú ,Ø ). This follows from the fact that, using De Morgan's rules, the logical addition function Ú can be expressed through (& , Ø), and the logical multiplication function & through (Ú, Ø):

(X & at) = Ø (` XÚ` at), (X Ú at) = Ø ( X &`at).

Other functionally complete subsystems in ( f) No.

Checking the completeness of the function subsystem ( f) 1 М ( f)throughout the system ( f)can be produced by mixing ( f) 1 to another, obviously complete in ( f)system.

Incompleteness of the subsystem ( f) 1 in ( f)can be verified by proving the strict occurrence of [ f 1 ] М [ f].

Definition. Subset mÍ M called functional basis(basis)systems M, If [ m] = M, and after excluding any function from it, the set of remaining ones is not complete in M .

Comment. Bases of the system of functions (f) are all its functionally complete subsystems (f) 1, which cannot be reduced without loss of completeness in (f).

Example 3. For all systems considered in Example 2, find bases.

Solution.In cases 1 and 2, only the systems themselves are functionally complete and it is impossible to narrow them down. Consequently, they are also bases.

In case 3 there are two functionally complete ones in ( f)subsystems ( f) 1 = (&,Ø ) and ( f) 2 =(Ú,Ø ), which cannot be reduced without loss of completeness. They will be the bases of the system ( f} = {&,Ú,Ø}.

Definition. Let the system ( f) is a closed class. Its subset ( f) 1 М ( f) are called junior class in{f), If ( f) 1 is not complete in ( f} ([f 1 ] М [ f]), and for any function j from the system( f), not included in ( f) 1 (jО( f} \ {f) 1) true: [ jÈ { f} 1 ] = [f], i.e. adding jк ( f) 1 makes it complete in ( f} .

Tasks

1. Check the closedness of sets of functions:

a) (Ø); b) (1, Ø ); c) ((0111); (10));d) ((11101110); (0110));e) ((0001); (00000001); (0000000000000001); … ).

2. Check the completeness of the function systems in P 2:

a) (0,Ø); b) ((0101) , (1010) ); V ); d) ((0001) , (1010) ).

3. Find the closure of the system of functions and its basis:

a) (0, 1, Ø); b) ((1000) , (1010), (0101) ); c) ((0001) , (1110), (10) ); d) ((1010) , (0001), (0111) ).

1.10.2 Functions that store constants. Classes T 0 and T 1

Definition. Function f(`x n) saves 0 if f(0,..., 0) = 0. Function f(`x n) saves 1 if f(1, ... , 1) = 1.

Lots of features n variables that store 0 and 1 are denoted, respectively, T 0 n And T 1 n. All sets of logical algebra functions that preserve 0 and 1 , denote T 0 And T 1. Each of the sets T 0 and T 1 is a closed precomplete class in R 2 .

From elementary functions to T 0 and T 1 are simultaneously included, for example, & and Ú. Belonging of any function to classes T 0 , T 1 can be checked by the first and last value of its vector of values ​​in the truth table or by directly substituting zeros and ones into the formula when specifying the function analytically.

Definition.Duplicate is a substitution in which the same variable is substituted into a function instead of several independent variables. In this case, the values ​​of variables in sets that previously took values ​​independently of each other will always be the same.

TASKS

1.Check class membership T 0 And T 1 functions:

a) generalized addition, b) generalized multiplication, c) constants, d) xyÚ yz, d) X® at® xy, e) XÅ at, and)( X 1 Å … Å X n) ® ( y 1 Å … Å y m) at n,mÎ N.

2. Prove the closedness of each class T 0 And T 1 .

3. Prove that if f(`x n) Ï T 0, then from it, by duplicating substitution, you can get the constant 1 or negation.

4. Prove that if f(`x n) Ï T 1 , then from it, by duplicating substitution, you can get the constant 0 or negation.

5. Prove the precompleteness of each of the classes T 0 And T 1 (for example, by reducing the augmented system to ( f} = {& ,Ú ,Ø }).

6. Find the power of classes T 0 n And T 1 n.