See what "Superposition of functions" is in other dictionaries. See pages where the term function superposition is mentioned Find graphical superposition of lines

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

In general, let us assume that the function is defined in some region and the function is defined in the region, and its values are all contained in the region Then the variable z, as they say, through y, and is itself a function of

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

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

The assumption that the values of the function do not go beyond the region Y in which the function is defined is very important: if it is omitted, then it can turn out to be absurd. For example, assuming we can consider only those values of x for which, otherwise, the expression would not make sense.

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

Here the function turned out to be given in the form of a complex function.

Now that the concept of superposition of functions has been fully clarified, 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 operations and superpositions , successively applied a finite number of times. They are said to be expressed in terms of elementary ones in a finite form; sometimes they are all also called elementary.

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

Build function

We bring to your attention a service for drawing function charts online, all rights to which belong to the company Desmos... Use the left column to enter functions. You can enter it 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 charting online

Visual display of entered functions
Building very complex graphs
Creation of graphs, given 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
Scale control, line color
Possibility of plotting graphs by points, using constants
Simultaneous construction of several graphs of functions
Plotting in polar coordinates (use r and θ (\ theta))

It is easy to build charts of varying complexity online with us. Construction is done instantly. The service is in demand for finding intersection points of functions, for displaying graphs for their further movement in a Word document as illustrations when solving problems, for analyzing the behavioral features of function graphs. The optimal browser for working with charts on this page of the site is Google Chrome. Operation is not guaranteed with other browsers.

In the scientific community, there is a well-known joke on this topic, "nonlinearity" is compared with "non-elephant" - all creatures, except for "elephants", are "non-elephants." The similarity lies in the fact that most of the systems and phenomena in the world around us are nonlinear, with a few exceptions. Despite this, in school we are taught "linear" thinking, which is very bad, in terms of our readiness to perceive the all-pervading 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 consequences, in their total mass, are not proportional to the causes, the two causes, when interacting, are not additive, that is, the consequences are more complex than a simple superposition, functions of causes. That is, the result resulting from the presence and impact of two causes acting simultaneously is not the sum of the results obtained in the presence of each of the reasons separately, in the absence of another cause.

Definition 9.Its in on some interval X a function rf (x) with a set of values Z is defined and a function y = f (z) is defined on the set Z, then the function y is a complex function of x (or a superposition of a function), and the variable z - an intermediate variable of a complex function.

Controlling can be viewed 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 solution, but also to ensure control of its implementation using appropriate management tools.

As you know / 50 /, any temporal 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 response is determined experimentally. When they are used by the superposition method, the selected model of the input action is first expanded into elementary "time functions, and then the responses to them are summed. The last operation is sometimes called convolution, and the integrals in expressions (24).. (29) are convolution integrals. From the one for which the integrand function is simpler is chosen.

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

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

Example 3.28. Let's go back to Example 3.27. In fig. 3.24 shows as a dash-dotted curve the result of the superposition of two membership functions corresponding to those quantifiers that are available in this example. Fuzzy intervals on the abscissa are obtained using a cutoff value of 0.7. Now we can say that the dispatcher should wait for the plan change

Another way of defining the function F, different from the superposition method, is that when a quantifier is applied to another quantifier, a certain monotonic transformation of the original membership function occurs, which reduces 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 with superposition and stretch-shift for the case where XA and X correspond to a frequently quantifier. The difference is, apparently, in the fact that superposition isolates in the membership function those values that are often encountered. In the case of shearing and stretching, we can interpret the result as the appearance of a new quantifier with a value of often-often, which can be approximated if desired, for example, by a 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 this 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 non-decreasing 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 М0 is continuous as a superposition of continuous functions. To prove the second part of the statement, consider the function

Complex e functions (superposition)

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 in information theory. Let operator В be a superposition of operators of multiplication by a function, (.) And shift by a function К0 (), operator С is an operator

Here, in general terms, the results of solving a number of variational problems (1) - (3) will be presented. 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 dwell 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 the table. Therefore, when solving the adjoint system φ = -fx using the functions specified in the table. Typically, such tables contain a small number of values for a set of nodes in the range of an 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, the tables specify functional dependences of an experimental nature). However, for our purposes we need differentiable functions f (x, u), so we should prefer smooth methods for completing a table-given function (for example, using splines).

Now let (YES and (q be arbitrary functions corresponding to some values of 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 is rare, and (q - often,

The advantage of this method for determining F is that with monotonic transformations, the form of the membership function does not change dramatically. Its unimodality or monotonicity is preserved, and the transition from the new form of function (2.16) has a trapezoidal shape, then the linear superposition (2.15) is also a trapezoidal fuzzy number (which is easily proved using the segment rule of computation). And it is possible to 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 abscissas of the vertices of the trapezoid, then

Definition of function, scope and value set. Definitions related to function designation. Definitions of a complex, numeric, real, monotone, and multivalued function. Definitions of maximum, minimum, upper and lower bounds for limited functions.

Content

Function y = f (x) the law (rule, mapping) is called, 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 function scope.
Set of elements y ∈ Y that have preimages in the set X are called set of function values(or range).

Domain functions are sometimes called many definitions or many tasks functions.

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

The mapping f itself is called function characteristic.

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

The characteristic symbol can be the same as the function value element symbol. That is, you can write it like this:. It should be remembered that y is an element from the set of values of the function, and this is the rule according to which the element y is associated with the element x.

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

The particular value of the function call the value of the function at the selected (private) value of its argument.

The graph of the function f called a set of pairs.

Complex functions

Definition
Let the functions and are 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 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 like this:.

In mathematical analysis, it is generally accepted that if the characteristic of a function is indicated by one letter or symbol, then it sets the same correspondence. However, in other disciplines, there is another way of notation, according to which mappings with one characteristic, but different arguments, are considered different. That is, the mappings and are considered to be different. Let's take an example from physics. Suppose we are considering the dependence of the momentum on the coordinate. And let us have a dependence of the coordinate on time. Then the dependence of the momentum 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. In mathematics, this designation is not accepted. If a reduction is required, a new characteristic must be entered. For example . Then it is clearly seen that and are different functions.

Valid functions

The domain of the function and the set of its values can be any sets.
For example, numerical sequences are functions whose domain of definition 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 vector value. Here the domain of definition is the set of all possible pairs of vectors. A set of values is the set of all vectors.
A boolean expression is a function. Its scope 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 operator. Therefore, the set of values of the real function can be limited and have the largest and smallest values.

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

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

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

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

The upper bound of the function unbounded from above

Bottom edge or exact lower bound A real, lower-bounded function is called the largest of the numbers, which limits the range of its values from below. That is, it is such a number i, for which, for all and for any, there is such an argument, the function value of which is less than i ′:.
The lower bound of a function can be denoted as follows:
.

The lower bound of a function unbounded from below is the point at infinity.

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

As an example, consider a function set on an open interval.
It is limited, on this interval, from above by the value 1 and below - the value 0 :
for all .
This function has top and bottom edges:
.
But it has no maximum and minimum.

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

Monotone 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 inequality holds:
.

Definition of a monotone 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 marked with different colors. Each branch is a function.

As follows from the definition of the function, each element x from the domain of definition is assigned only one element from the set of values. But there are such 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, infinitely many values of y satisfy this equation (see figure).

Let us impose a restriction on the solutions of Eq. (1). Let be
(2) .
Under this condition, only one solution of equation (1) corresponds to a given value. That is, the correspondence defined by equation (1) subject to 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 get our own function that is different from the others. Many similar functions are multivalued function... And the function determined from (1) under condition (2.n) is branch of multivalued function.

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

Multivalued function branch is one of the functions included in the multivalued function.

Unique function is a function.

References:
O.I. Demons. Lectures on mathematical analysis. Part 1. Moscow, 2004.
L. D. Kudryavtsev. The course of mathematical analysis. Volume 1.Moscow, 2003.
CM. Nikolsky. The course of mathematical analysis. Volume 1.Moscow, 1983.

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

then the function will be called superposition function f (x 1, x 2, ..., x n) and functions .

In other words: let F = (f j) - the set of functions of the algebra of logic, 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, 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)).

A perfect DNF is a superposition of functions from the set

. ð

Definition.

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

We already have a set of complete systems:

;

Because ;

(x + y, xy, 1). ð

How to 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 Boolean functions 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 representable by the operations of superposition and change of variables of functions from the set K. The closure of the set K is denoted by [K].

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

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

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

Examples.

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

* Many functions of one variable - a closed class.

* - closed class.

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

Let's consider some of the most important closed classes.

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

We denote by T 0 the class of all Boolean functions 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 belonging 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 in terms of disjunction and conjunction.

Since the table for a function f from class T 0 in the first row contains the value 0, then for functions from T 0 arbitrary values can be specified only on 2 n - 1 set of values of variables, that is

where is the set of functions preserving 0 and depending on n variables.

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

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

2.T 1- a class of functions that preserve 1.

Let T 1 denote the class of all Boolean functions 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 belonging 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.

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

T 1 - closed class;

3. L- a class of linear functions.

Let L denote the class of all functions of the Boolean 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.

Suppose 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 the nonlinearity of the function xÚy.

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 of 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- a class of self-dual functions.

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

The function defined by equality is called dual to function .

Obviously, the table for the dual function (with the standard ordering of the 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 the function values and reversing 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 the function be expressed using superposition in terms of other functions. The question is, how to build a formula that implements? We denote by = (x 1, ..., x n) all different symbols of variables that occur in the sets.

Theorem 2.6. If the function j is obtained as a superposition of the 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 is proved. ð

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

We 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 belonging 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 the 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

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

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

5.M- a 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 sets of its variables.

The set is said to precede the set (or “not more”, 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. The sets and are called comparable if either, or. In the case when none of these relations holds, 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 £ (it is often called the precedence relation) is a partial order on the set В n. Below are diagrams of 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.

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

The logic algebra function is called monotonous if for any two sets and, such that, the inequality ... The set of all monotone functions of the Boolean algebra 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 belonging 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 the closedness it is sufficient to show that it is closed with respect to the superposition operation, since the change of variables operation is a special case of superposition with the function x.

Let be . 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 occur in the functions f 1, ..., f m. Let and be two sets of variable values, and. These sets define sets variable values such that ... Since the functions f 1, ..., f m

and due to the monotonicity of the function f

From this we get

The number of monotone 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 is just as easy to get too high an estimate from above:

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

Completeness criterion

We are now 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. We precede the formulation and proof of the completeness criterion with several necessary lemmas of independent interest.

Lemma 2.7. Lemma on 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 f function:

x i is replaced by ,

that is, we put and consider the function

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

Lemma 2.8. Lemma on a non-monotonic function.

If the function f (x 1, ..., x n) is non-monotone, f (x 1, ..., x n) Ï M, then it is possible to obtain negation from it by changing variables and substituting constants 0 and 1.

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

x i is replaced by

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

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

Lemma 2.9. Lemma on a 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... We represent f in the form of 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 brackets, and simple algebraic transformations, transforms into a mod 2 polynomial (Zhegalkin polynomial):

where A 0 is a constant, and A i is the 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, the Zhegalkin polynomial for the function f contains a term containing 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, ..., xn) + x 1 f 2 (x 3, ..., xn) + x 2 f 3 (x 3, ..., xn) + f 4 (x 3, ..., xn),

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), 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 proved. ð

Lemma 2.10. The main lemma of the completeness criterion.

If the class F = (f) of Boolean 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 the operations of superposition and change of variables, we can obtain the constants 0, 1 and the function.

Proof... Let's consider a function. Then

There are two possible cases of subsequent considerations, hereinafter designated as 1) and 2).

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

Replace all the variables of the function with the variable x. Then the function

is, because

and .

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

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

For the system of functions F = (fi) 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.

Need... Let F be a complete system. Suppose that F is contained in one of the indicated classes; we denote it by K, that is, 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) be entirely contained in none of the five closed classes T 0, T 1, L, S, M. Take in F the 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, a non-self-dual and non-monotonic function, we can obtain the constants 0, 1 and the negation function:

Based on the nonlinear function lemma (lemma 2.9 ) from constants, negation and nonlinear function, you can get the 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 a disjunction can be expressed through conjunction and negation in the form ).

The theorem is completely proved. ð

Examples.

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

x	y	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 non-linearity of the function mean
x | y.

Based on the completeness criterion, it can be argued 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-monotonic and non-linear functions. Based on the completeness criterion, it can be argued that the system of functions forms a complete system. ð

Thus, we made sure that the completeness criterion provides a constructive and effective way to clarify the completeness of systems of functions of the algebra of logic.

Let us now formulate three consequences of the completeness criterion.

Corollary 1... Any closed class K of Boolean functions that does not coincide with the entire set of Boolean functions (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.

It follows from the definition 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, it is only necessary to check that none of these classes is contained in the other, which is confirmed, for example, by the following table of the belonging of functions to different classes:

T 0	T 1	L	S	M
+	-	+	-	+
-	+	+	-	+
-	-	+	+	-

Corollary 3. From any complete system of functions, a complete subsystem can be distinguished, 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 not unit-preserving and not monotone. Therefore, no more than four functions are needed.