Correspondence G between sets A And IN called a subset. If , then they say that b

corresponds A. The set of all corresponding elements

Called way element a. The set of all to which the element corresponds is called

prototype element b.

Lots of couples (b, a) such that is called inverse

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

"G and are mutually inverse.

Examples. 1) Let’s match it with a natural number P

set of real numbers . Image of the number 5

there will be a half interval

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

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 simply turns out that the estimate above is too high:

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 about 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 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, 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 mod 2 polynomial (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:

.

We'll replace everything variable functions 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 accepts 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 gives a constructive and effective method clarification of the completeness of systems of functions of 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, the following table 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 ) follows that either non-self-dual or does not preserve unity and is not monotonic. Therefore, no more than four functions are needed.

Build function

We offer to your attention a service for constructing graphs of functions online, all rights to which belong to the company Desmos. Use the left column to enter functions. You can enter manually or using the virtual keyboard at the bottom of the window. To enlarge the window with the graph, you can hide both the left column and the virtual keyboard.

Benefits of online charting

• Visual display of entered functions
• Building very complex graphs
• Construction of graphs specified implicitly (for example, ellipse x^2/9+y^2/16=1)
• The ability to save charts and receive a link to them, which becomes available to everyone on the Internet
• Controlling scale and line color
• Possibility of plotting graphs by points, using constants
• Plotting several function graphs simultaneously
• Plotting in polar coordinates (use r and θ(\theta))

With us it’s easy to build charts of varying complexity online. Construction is done instantly. The service is in demand for finding intersection points of functions, for depicting graphs for their further movement into Word document as illustrations when solving problems, to analyze the behavioral features of function graphs. The optimal browser for working with charts on this page of the site is Google Chrome. Correct operation is not guaranteed when using other browsers.

Topic: “Function: concept, methods of assignment, main characteristics. Inverse function. Superposition of functions."

Lesson epigraph:

“Study something and not think about it

learned - absolutely useless.

Thinking about something without studying it

preliminary subject of thought -

Confucius.

Purpose and psychological and pedagogical objectives of the lesson:

1) General educational (normative) goal: Review with students the definition and properties of a function. Introduce the concept of superposition of functions.

2) Objectives of students' mathematical development: using non-standard educational and mathematical material to continue the development of students’ mental experience, the meaningful cognitive structure of their mathematical intelligence, including the abilities for logical-deductive and inductive, analytical and synthetic reversible thinking, algebraic and figurative-graphic thinking, meaningful generalization and concretization, to reflection and independence as a metacognitive ability of students; to continue the development of a culture of written and oral speech as psychological mechanisms of educational and mathematical intelligence.

3) Educational tasks: to continue personal education in students of cognitive interest in mathematics, responsibility, sense of duty, academic independence, communicative ability to cooperate with the group, teacher, classmates; autogogic ability for competitive educational and mathematical activity, striving for high and highest results (acmeic motive).

Lesson type: learning new material; according to the criterion of leading mathematical content - a practical lesson; according to the criterion of the type of information interaction between students and the teacher - a lesson of cooperation.

Lesson equipment:

1. Educational literature:

1) Kudryavtsev mathematical analysis: Textbook. for university and university students. In 3 volumes. T. 3. – 2nd ed., revised. and additional – M.: Higher. school, 1989. – 352 p. : ill.

2) Demidovich problems and exercises in mathematical analysis. – 9th ed. – M.: Publishing house “Nauka”, 1977.

2. Illustrations.

During the classes.

1. Announcement of the topic and main educational goal of the lesson; stimulating a sense of duty, responsibility, and cognitive interest of students in preparation for the session.

2.Repetition of material based on questions.

a) Define a function.

One of the basic mathematical concepts is the concept of function. The concept of a function is associated with establishing a relationship between elements of two sets.

Let two non-empty sets and be given. A match f that matches each element with one and only one element is called function and writes y = f(x). They also say that the function f displays many upon many.

https://pandia.ru/text/79/018/images/image003_18.gif" width="63" height="27">.gif" width="59" height="26"> is called multiple meanings function f and is denoted by E(f).

b) Numerical functions. Function graph. Methods for specifying functions.

Let the function be given.

If the elements of sets and are real numbers, then the function f is called numerical function . The variable x is called argument or independent variable, and y – function or dependent variable(from x). Regarding the quantities x and y themselves, they are said to be in functional dependence.

Function graph y = f(x) is the set of all points of the Oxy plane, for each of which x is the value of the argument, and y is the corresponding value of the function.

To specify the function y = f(x), it is necessary to specify a rule that allows, knowing x, to find the corresponding value of y.

The most common three ways of specifying a function are: analytical, tabular, and graphical.

Analytical method: A function is specified as one or more formulas or equations.

For example:

If the domain of definition of the function y = f(x) is not specified, then it is assumed that it coincides with the set of all values ​​of the argument for which the corresponding formula makes sense.

The analytical method of specifying a function is the most advanced, since it includes methods of mathematical analysis that make it possible to fully study the function y = f(x).

Graphic method: Sets the graph of the function.

The advantage of a graphic task is its clarity, the disadvantage is its inaccuracy.

Tabular method: A function is specified by a table of a series of argument values ​​and corresponding function values. For example, the well-known value tables trigonometric functions, logarithmic tables.

c) Main characteristics of the function.

1. The function y = f(x), defined on the set D, is called even , if the conditions and f(-x) = f(x) are met; odd , if the conditions and f(-x) = -f(x) are met.

The graph of an even function is symmetrical about the Oy axis, and an odd function is symmetrical about the origin. For example, – even functions; and y = sinx, https://pandia.ru/text/79/018/images/image014_3.gif" width="73" height="29"> – functions of general form, i.e. neither even nor odd .

2. Let the function y = f(x) be defined on the set D and let . If for any values ​​of the arguments the following inequality follows: , then the function is called increasing on the set; If , then the function is called non-decreasing at https://pandia.ru/text/79/018/images/image021_1.gif" width="117" height="28 src=">then the function is called. decreasing on ; - non-increasing .

Increasing, non-increasing, decreasing and non-decreasing functions on the set https://pandia.ru/text/79/018/images/image023_0.gif" width="13" height="13">D value (x+T)D and the equality f(x+T) = f(x) holds.

To plot a graph of a periodic function of period T, it is enough to plot it on any segment of length T and periodically continue it throughout the entire domain of definition.

Let us note the main properties of a periodic function.

1) The algebraic sum of periodic functions having the same period T is a periodic function with period T.

2) If the function f(x) has period T, then the function f(ax) has period T/a.

d) Inverse function.

Let a function y = f(x) be given with a domain of definition D and a set of values ​​E..gif" width="48" height="22">, then a function x = z(y) with a domain of definition E and a set of values ​​D is defined Such a function z(y) is called reverse to the function f(x) and is written in the following form: . The functions y = f(x) and x = z(y) are said to be mutually inverse. To find the function x = z(y), inverse to the function y = f(x), it is enough to solve the equation f(x) = y for x.

Examples:

1. For the function y = 2x the inverse function is the function x = ½ y;

2. For function the inverse function is the function .

From the definition of an inverse function it follows that the function y = f(x) has an inverse if and only if f(x) specifies a one-to-one correspondence between the sets D and E. It follows that any a strictly monotonic function has an inverse . Moreover, if a function increases (decreases), then the inverse function also increases (decreases).

3. Studying new material.

Complex function.

Let the function y = f(u) be defined on the set D, and the function u = z(x) on the set, and for the corresponding value . Then the function u = f(z(x)) is defined on the set, which is called complex function from x (or superposition specified functions, or function from function ).

The variable u = z(x) is called intermediate argument complex function.

For example, the function y = sin2x is a superposition of two functions y = sinu and u = 2x. A complex function can have several intermediate arguments.

4. Solving several examples at the board.

5. Conclusion of the lesson.

1) theoretical and applied results practical lesson; differentiated assessment of the level of mental experience of students; their level of mastery of the topic, competence, quality of oral and written mathematical speech; level of creativity demonstrated; level of independence and reflection; level of initiative, cognitive interest in individual methods of mathematical thinking; levels of cooperation, intellectual competition, desire for high levels of educational and mathematical activity, etc.;

2) announcement of reasoned grades, lesson points.