Correspondence G between sets AND and AT called a subset. If , then they say that b

corresponds a. The set of all matching elements

called way element a. The set of all that an element corresponds to is called

prototype element b.

Plenty of couples (b, a) such as is called reverse

towards G and is denoted. The concepts of image and prototype for

" G and are mutually inverse.

Examples. 1) Let's put in correspondence with a natural number P

set of real numbers . The image of the number 5

there will be a half-interval

(this is the largest integer less than or equal to X). The preimage of the number 5 in this correspondence is an infinite set: a half-interval.

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

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

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

Examples.

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

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

* - closed class.

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

Let us consider some of the most important closed classes.

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

Denote by T 0 the class of all functions of the logic algebra f(x 1 , x 2 , ... , x n) that preserve 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 W T 0 follows, for example, that cannot be expressed in terms of disjunction and conjunction.

Since the table for the function f from the class T 0 in the first line contains the value 0, then for functions from T 0 you can set arbitrary values ​​only on 2 n - 1 sets 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 , to justify the closedness, it suffices to show the closedness with respect to the operation of superposition, since the change of variables operation is a special case of superposition with the function x.

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

2.T1- class of functions that preserve 1.

Denote by T 1 the class of all functions of the logic algebra f(x 1 , x 2 , ... , x n) that preserve 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 .

The fact that x + y П T 0 implies, for example, that x + y cannot be expressed in terms of disjunction and conjunction.

The results about the class T 0 trivially carry over to the class T 1 . Thus, we have:

T 1 - closed class;

.

3. L- class of linear functions.

Denote by L the class of all functions of the logic algebra 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 undefined 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 1Ú 1 ¹ 1 + 1, which proves that the function xÚy is non-linear.

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

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

.

4.S- the 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 .

It is obvious that 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 flipping it.

It is 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 in terms of other functions. The question is how to construct a formula that implements ? Denote by = (x 1 , ... , x n) all different variable symbols occurring in 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 the formula A implements the function f(x 1 , ... , x n), then the formula obtained from A by replacing the functions included in it with their duals implements the dual function f*(x 1 , ... , xn).

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 superposition dual function theorem, 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 we have the identity

so on sets and , which we will call opposite, the self-dual function takes opposite values. It follows that a 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:

.

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

5. M- the class of monotone functions.

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

The set is said to precede the set (or “not greater than”, or “less than or equal to”), and the notation is used if a i £ b i for all i = 1, ... , n. If and , then we will say that the set strictly precedes the set (either “strictly less than” or “less than” the set ), and use the notation . The sets and are called comparable if either , or . In the case when none of these relations is satisfied, 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 partially ordered sets B 2 , B 3 and B 4 .

The introduced partial order relation is an exceptionally important concept, far beyond the scope of our course.

We are now in a position to define the notion of a monotone function.

The function of the algebra of logic is called monotonous, if for any two sets and , such that , the inequality . 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ОМ, to justify closedness, it suffices to show closedness with respect to the operation of superposition, since the operation of change of variables is a special case of superposition with the function x.

Let . Then it suffices to show that .

Let be sets of variables, respectively, of functions j, f 1 , ... , f m , and the set of variables of function j consists of those and only those variables that occur in functions f 1 , ... , f m . Let and be two sets of values ​​of the variable , and . These sets define 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 exactly known. The lower estimate can easily be obtained:

where there is whole part from n/2.

It's just as easy to get an overestimation from above:

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

Completeness criterion

Now we are in a position 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, which are also of independent interest.

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

If f(x 1 , ... , x n)П S , then we can obtain a constant from it by substituting the functions x and `x.

Proof. Since fÏS, there is a set of values ​​of the variables
=(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, we set , and consider the function

Thus, we got a constant (however, it is not known what kind of constant it is: 0 or 1). ð

Lemma 2.8. Lemma on a nonmonotone function.

If the function f(x 1 ,...,x n) is nonmonotone, f(x 1 ,...,x n) П M, then by changing the variables and substituting the constants 0 and 1 it can be negated.

Proof. Since f(x 1 ,...,x n) П M, there are sets and values ​​of its variables, , , such that , and for at least one value of i we have 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 j(x)=`x. The lemma is proven. ð

Lemma 2.9. Lemma on a non-linear function.

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

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

Example. Let us give two examples of applying these transformations.

Thus, a function written in disjunctive normal form, after applying the above relations, opening brackets and simple algebraic transformations, turns into a mod 2 polynomial (Zhegalkin polynomial):

where A 0 is a constant, and A i is a conjunction of some variables from 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.

Therefore, the Zhegalkin polynomial for the function f contains 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 the 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) resulting 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 .

Consequently,

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

The lemma is completely proved. ð

Lemma 2.10. The main lemma of the completeness criterion.

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

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

Proof. Let's consider a function. Then

.

Two cases of subsequent considerations are possible, in what follows, denoted as 1) and 2).

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

.

Let's replace everything function variables variable x . Then the function

is, because

and .

Take a non-self-dual function . Since we have already obtained the function, by the non-self-dual function lemma (lemma 2.7. ) from you can get a constant. The second constant can be obtained from the first one using the . Thus, 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 proved. ð

Theorem 2.11. Completeness criterion for systems of functions of 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. Assume that F is contained in one of the specified classes, 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 system of functions F = (f i ) not be entirely contained in any of the five closed classes T 0 , T 1 , L , S, M. Take in F functions:

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-monotone functions, you can get the constants 0, 1 and the negation function:

.

Based on the non-linear function lemma (Lemma 2.9 ) from constants, negation and a non-linear function, you can get a conjunction:

.

Function system - a complete system according to the theorem on 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 proved completely. ð

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:

x	y	x|y

f(0,0) = 1, hence x | ypT 0 .

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

f(0,0) = 1, f(1,1) = 0, hence x | yupm .

f(0,1) = f(1,0) = 1, - on opposite sets x | y takes the same values, hence x | yops.

Finally, , which means the non-linearity of the function
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 have found: a function that does not preserve 0, a function that does not preserve 1, non-self-dual, non-monotone and nonlinear functions. Based on the completeness criterion, it can be argued that the system of functions forms a complete system. ð

Thus, we have seen that the completeness criterion gives a constructive and effective method clarification of the completeness of systems of functions of the algebra of logic.

Let us now formulate three corollaries of the completeness criterion.

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

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

It follows from the definition that a precomplete class is closed.

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

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

	T0	T1	L	S	M
	+	-	+	-	+
	-	+	+	-	+
	-	-	+	+	-

Consequence 3. From any complete system of functions, one can single out a complete subsystem containing no more than four functions.

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

- (late lat. superpositio, - overlay, from lat. superpositus - laid on top) (composition) - logical mathematical operation. calculus, which consists in obtaining from c.l. given functions f and g of given calculus new feature g (f) (expression g ... ... Philosophical Encyclopedia

The term superposition (overlay) 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 result, ... ... Wikipedia

The composition of functions, the composition of two functions of a complex function ... Mathematical Encyclopedia

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

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

In the theory of discrete functional systems boolean function call 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 mathematical. logic classes of concepts that serve as refinements contain. concepts of an effectively computable arithmetic function and an effectively decidable arithmetic predicate, and ultimately, and ... ... Philosophical Encyclopedia

A function that calculates 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 desired values ​​​​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 consolidating the articles. If you need to discuss the advisability of merging, replace this template with the template ((to merge)) ... Wikipedia

- (lat. compositio composition, binding, addition, connection): Wiktionary has an entry for “composition” Art Composition (fine art) is an organizing component of an art form that gives design ... Wikipedia

Books

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

Superposition of functions

A superposition of functions f1, …, fm is a function f obtained by substituting these functions into each other and renaming variables.

Let there be two mappings and, moreover, a non-empty set. Then a superposition or composition of functions is a function defined by equality for any.

The domain of definition of a superposition is a set.

The function is called the outer, and the inner function for superposition.

Functions presented as a composition of "simpler" ones are called complex functions.

Examples of the use of superposition are: solving a system of equations by the substitution method; finding the derivative of a function; finding the value of an algebraic expression by substituting the values ​​of given variables into it.

Recursive functions

Recursion is such a way of defining a function, in which the values ​​of the function being defined for arbitrary values ​​of the arguments are expressed in a known way through the values ​​of the function being defined for smaller values ​​of the arguments.

Primitive recursive function

The definition of the concept of a primitive recursive function is inductive. It consists of specifying a class of basic primitive recursive functions and two operators (superposition and primitive recursion) that allow building new primitive recursive functions based on existing ones.

The basic primitive recursive functions include the following three types of functions:

Zero function-- function no arguments, always returning 0 .

A one-variable succession function that assigns any natural number to the immediately following natural number.

Functions, where, from n variables, which assign to any ordered set of natural numbers a number from this set.

The substitution and primitive recursion operators are defined as follows:

Superposition operator (sometimes a substitution operator). Let be a function of m variables, and be an ordered set of functions of non-variables each. Then the result of the superposition of functions into a function is a function of variables that assigns a number to any ordered set of natural numbers.

Primitive recursion operator. Let be a function of n variables, and be a function of variables. Then the result of applying the primitive recursion operator to a pair of functions is the function of the type variable;

AT this definition variable can be understood as an iteration counter, -- as original function at the beginning of the iterative process, issuing a certain sequence of functions of variables, starting with, and -- as an operator that accepts as input variables, the iteration step number, the function at this iteration step, and returning the function at the next iteration step.

The set of primitive recursive functions is the minimum set containing all basic functions and closed under the specified substitution and primitive recursion operators.

In terms of imperative programming -- primitive recursive functions correspond to program blocks that use only arithmetic operations, and also conditional operator and an arithmetic loop operator (a loop operator in which the number of iterations is known at the start of the loop). If the programmer starts using the operator while loop, in which the number of iterations is not known in advance and, in principle, can be infinite, then it passes into the class of partially recursive functions.

Let us point out a number of well-known arithmetic functions that are primitively recursive.

The function of adding two natural numbers () can be considered as a primitive recursive function of two variables, obtained as a result of applying the primitive recursion operator to the functions and, the second of which is obtained by substituting the main function into the main function:

The multiplication of two natural numbers can be considered as a primitive recursive function of two variables, obtained as a result of applying the primitive recursion operator to the functions and, the second of which is obtained by substituting the main functions and into the addition function:

The symmetric difference (the absolute value of the difference) of two natural numbers () can be considered as a primitive recursive function of two variables, obtained by applying the following substitutions and primitive recursions:

Let's get acquainted with the concept of superposition (or imposition) of functions, which consists in the fact that instead of an argument of a given function, some function of another argument is substituted. For example, the superposition of functions gives a function; similarly, functions are obtained

In general terms, suppose that a function is defined in a domain and a function is defined in a domain and all its values ​​are contained in the domain Then the variable z, as they say, through y, is itself a function of

For a given from, first find the value y corresponding to it (according to the rule characterized by the sign of the value y from Y, and then set the corresponding value y (according to the rule,

characterized by a sign and its value is considered corresponding to the chosen x. The resulting function from a function or a complex function is the result of a superposition of functions

The assumption that the values ​​of a function do not go beyond the region Y in which the function is defined is quite significant: if it is omitted, then absurdity may result. For example, assuming we can consider only those values ​​of x for which otherwise the expression would not make sense.

We consider it useful here to emphasize that the characterization of a function as complex is not connected with the nature of the functional dependence of z on x, but only with the way this dependence is specified. For example, let for y in for Then

Here the function turned out to be given as a complex function.

Now that the concept of superposition of functions has been fully elucidated, we can accurately characterize the simplest of those classes of functions that are studied in analysis: these are, first of all, the elementary functions listed above and then all those that are obtained from them using four arithmetic actions and superpositions successively applied a finite number of times. They say about them that they are expressed through elementary ones in the final form; sometimes they are all also called elementary.

Subsequently, having mastered a more complex analytical apparatus (infinite series, integrals), we will also get acquainted with other functions that also play an important role in analysis, but already go beyond the class of elementary functions.