A function f obtained from the functions f 1 , f 2 ,…f n using the operations of substitution and renaming of arguments is called superposition functions.
Any formula that expresses a function f as a superposition of other functions specifies a method for its calculation, i.e., the formula can be calculated if the values of all its subformulas are calculated. The value of a subformula can be calculated from a known set of binary variable values.
Using each formula, you can restore the table of a logical function, but not vice versa, because Each logical function can be represented by several formulas in different bases
Formulas F i and F j representing the same logical function f i are called equivalent . So, the equivalent formulas are:
1. f 2 (x 1 ; x 2)=(x 1 ×`x 2)=ù(`x 1 Úx 2)= ù(x 1 ®x 2);
2. f 6 (x 1 ; x 2)=(`x 1 ×x 2 Úx 1 ×`x 2)= ù(x 1 “x 2)=(x 1 Åx 2);
3. f 8 (x 1 ; x 2)=(`x 1 ×`x 2)= ù(x 1 Úx 2)=(x 1 ¯x 2);
4. f 14 (x 1 ;x 2)=(`x 1 Ú`x 2)= ù(x 1 ×x 2)=x 1 ½x 2 ;
5. f 9 (x 1 ;x 2)=((`x 1 ×`x 2)Ú(x 1 ×x 2))=(x 1 “x 2) ;
6. f 13 (x 1 ;x 2)= (`x 1 Úx 2)=(x 1 ®x 2).
If any formula F contains a subformula F i , then replacing F i with an equivalent F j does not change the value of the formula F for any set of Boolean vectors, but changes the form of its description. The newly obtained formula F` is equivalent to the formula F.
To simplify complex algebraic expressions, Boolean functions are performed equivalent transformations using the laws of Boolean algebra and substitution rules And substitution ,
When writing Boolean algebra formulas, remember:
· the number of left parentheses is equal to the number of right parentheses,
· there are no two adjacent logical connectives, i.e. there must be a formula between them,
· there are no two adjacent formulas, i.e. there must be a logical connection between them,
· the logical connective “×” is stronger than the logical connective “Ú”,
· if “ù” refers to the formula (F 1 ×F 2) or (F 1 Ú F 2), then first of all these transformations should be performed according to De Morgan’s law: ù(F 1 ×F 2) = `F 1 Ú` F 2 or ù(F 1 ÚF 2)=`F 1 ×`F 2 ;
· operation " × ” is stronger than “Ú”, which allows you to omit the parentheses.
Example: perform equivalent transformations of the formula F=x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 .
· according to the law of commutativity:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×`x 2 Úx 3 ×x 4 ;
· according to the law of distributivity:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×(`x 2 Úx 4);
· according to the law of distributivity:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×(`x 1 Ú`x 2 Úx 4);
· according to the law of distributivity:
F=x 3 ×((x 1 ×x 2 ×`x 4)Ú(`x 1 Ú`x 2 Úx 4));
· according to De Morgan's law:
F=x 3 ×((x 1 ×x 2 ×`x 4)Úù(x 1 ×x 2 ×`x 4));
· according to the law of contradiction:
Thus x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 =x 3 .
Example: perform formula transformations
F=(x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2 );
· according to De Morgan's law
F=(x 1 ×`x 2 Ú`x 1 ×x 2)×(`x 1 Ú`x 2)Ú(x 1 ×x 2)×(`x 1 Úx 2)×(x 1 Ú`x 2);
· according to the law of distributivity:
F=x 1 ×`x 2 Ú`x 1 ×x 2 Úx 1 ×x 2 ;
· according to the laws of commutativity and distributivity:
F= `x 1 ×x 2 Úx 1 ×(`x 2 Úx 2);
· according to the law of contradiction:
F= `x 1 ×x 2 Úx 1 ;
· according to Poretsky's law
Thus (x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2 )= (x 2 Úx 1).
Example: transform the formula F=ù(`x 1 Úx 2)Ú((`x 1 Úx 3)×x 2).
· according to De Morgan's law:
F= ù(`x 1 Úx 2)×ù((`x 1 Úx 3)×x 2);
· according to De Morgan's law:
F=x 1 ×`x 2 ×(ù(`x 1 Úx 3)Ú`x 2);
· according to De Morgan's law:
F=x 1 ×`x 2 ×(x 1 ×`x 3 Ú`x 2);
· according to the law of distributivity:
F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ;
· according to the law of absorption:
Thus ù(`x 1 Úx 2)×((`x 1 Úx 3)×x 2)= x 1 ×`x 2 .
Example: Convert the formula:
F=ù(x 1 ®x 2)×(`x 3 Ú`x 4)Ú(x 1 ¯x 2)×ù(x 3 ×x 4).
1) transform the formula into a basis of Boolean algebra:
F=ù(`x 1 Úx 2)×(`x 3 Ú`x 4)Úù(x 1 Úx 2)× ù(x 3 ×x 4);
2) omit the “`” sign before binary variables:
F=(x 1 ×`x 2)×(`x 3 Ú`x 4)Ú(`x 1 ×`x 2)×(`x 3 Ú`x 4);
3) transform the formula according to the distributive law:
F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ×`x 4 Ú`x 1 ×`x 2 ×`x 3 Ú`x 1 ×`x 2 ×`x 4 ;
4) put `x 2 out of brackets according to the distributive law:
F=`x 2 ×(x 1 ×`x 3 Úx 1 ×`x 4 Ú`x 1 ×`x 3 Ú`x 1 ×`x 4);
5) transform according to the law of distributivity:
F=`x 2 ×(`x 3 ×(x 1 Ú`x 1)Ú`x 4 ×(x 1 Ú`x 1));
6) use the law of contradiction:
F=`x 2 ×(`x 3 Ú`x 4)
Properties of Boolean Functions
The question often arises: is every Boolean function representable by a superposition of the formulas f 0, f 1,..f 15? In order to determine the possibility of forming any Boolean function using a superposition of these formulas, it is necessary to determine their properties and conditions for using a functionally complete system.
Self-dual Boolean functions
self-dual , if f(x 1 ;x 2 ;…x n)=`f(`x 1 ;`x 2 ;…`x n).
For example, the functions f 3 (x 1 ;x 2)=x 1 , f 5 (x 1 ;x 2)=x 2 , f 10 (x 1 ;x 2)=`x 2 and f 12 (x 1 ;x 2)=`x 1 are self-dual, because when the value of the argument changes, they change their value.
Any function obtained by superposition operations from self-dual Boolean functions is itself self-dual. Therefore, the set of self-dual Boolean functions does not allow the formation of non-self-dual functions.
Monotonic Boolean functions
The function f(x 1 ; x 2 ;…x n) is called monotonous , if for each s 1i £s 2i Boolean vectors (s 11 ; s 12 ;……;s 1n) and (s 21 ;s 22 ;……;s 2n) the following condition is satisfied: f(s 11 ;s 12 ;… ;s 1i ;…;s 1n)£f(s 21 ;s 22 ;…;s 2i ;…;s 2n).
For example, for functions f(x 1 ; x 2) monotonic functions are:
if (0; 0) £ (0; 1), then f(0; 0) £ f (0; 1),
if (0; 0)£(1; 0), then f(0; 0)£f(1; 0),
if (0; 1)£(1; 1), then f(0; 1)£f(1; 1),
if (1; 0) £ (1; 1), then f(1; 0) £ f(1; 1).
The following functions satisfy these conditions:
f 0 (x 1 ; x 2)=0; f 1 (x 1 ; x 2)=(x 1 ×x 2); f 3 (x 1 ; x 2)=x 1 ; f 5 (x 1 ; x 2)=x 2 ; f 7 (x 1 ;x 2)=(x 1 Úx 2); f 15 (x 1 ; x 2)=1.
Any function obtained using the superposition operation from monotonic Boolean functions is itself monotonic. Therefore, the set of monotonic functions does not allow the formation of non-monotonic functions.
Linear Boolean functions
The Zhegalkin algebra, based on the basis F 4 =(×; Å; 1), allows any logical function to be represented by a polynomial, each term of which is a conjunction of I Boolean variables of a Boolean vector within 0£i£n:
P(x 1 ; x 2 ;…x n)=b 0 ×1 Å b i ×x i Å 1 £ j ¹ k £ n b j ×x j ×x k Å……Å b 2n-1 ×x 1 ×x 2 ×... ×x n.
For example, for logical functions f 8 (x 1 ; x 2)
The Zhegalkin polynomial has the form: P(x 1; x 2)=1Å x 1 Å x 2 Å x 1 ×x 2.
The advantages of Zhegalkin algebra are the “arithmetization” of logical formulas, while the disadvantages are complexity, especially with a large number of binary variables.
Zhegalkin polynomials that do not contain conjunctions of binary variables, i.e. P(x 1 ; x 2 ;…;x n)=b 0 ×1Åb 1 ×x 1 Å…Åb n ×x n is called linear .
For example, f 9 (x 1 ; x 2) = 1Åx 1 Åx 2 , or f 12 (x 1 ; x 2) = 1Åx 1 .
The main properties of the addition operation modulo 2 are given in Table 1.18.
If a logical function is specified by a table or formula in any basis, i.e. If you know the values of a Boolean function for various sets of Boolean variables, then you can calculate all
coefficients b i of the Zhegalkin polynomial, compiling a system of equations for all known sets of binary variables.
Example: given a Boolean function f(x 1 ;x 2)=x 1 Úx 2. The values of this function are known for all sets of Boolean variables.
F(0;0)=0=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;
f(1;0)=1=b 0 ×1Å b 1 ×1Å b 2 ×0Å b 3 ×1×0;
f(1;1)=1=b 0 ×1Å b 1 ×1Å b 2 ×1Å b 3 ×1×1;
Where do we find b 0 =0; b 1 =1; b 2 =1; b 3 =1.
Therefore, (x 1 Úx 2)=x 1 Åx 2 Åx 1 ×x 2, i.e. the disjunction is a nonlinear Boolean function.
Example: given a Boolean function f(x 1 ;x 2)=(x 1 ®x 2). The values of this function are also known for all sets of binary variables.
F(0;0)=1=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;
f(0;1)=1=b 0 ×1Å b 1 ×0 Å b 2 ×1Å b 3 ×0×1;
f(1;0)=0=b 0 ×1Åb 1 ×1Åb 2 ×0Åb 3 ×1×0;
f(1;1)=1=b 0 ×1Åb 1 ×1Åb 2 ×1Åb 3 ×1×1;
Where do we find b 0 =1; b 1 =1; b 2 =0; b 3 =1.
Therefore, (x 1 ®x 2)=1Å x 2 Å x 1 ×x 2.
Table 1.19 shows the Zhegalkin polynomials for the main representatives of Boolean functions from Table 1.15.
If an analytical expression for a logical function is given and its values are unknown for various sets of binary variables, then it is possible to construct a Zhegalkin polynomial based on the conjunctive basis of the Boole algebra F 2 =(` ; ×):
Let f(x 1 ; x 2)=(x 1 Úx 2).
Then (x 1 Úx 2)=ù(`x 1 ×`x 2)=((x 1 Å 1)×(x 2 Å 1))Å 1=x 1 ×x 2 Å x 1 ×1Å x 2 × 1Å 1×1Å1=
(x 1 Åx 2 Åx 1 ×x 2).
Let f(x 1 ;x 2)=(x 1 ®x 2).
Then (x 1 ®x 2)=(`x 1 Úx 2)=ù(x 1 ×`x 2)=x 1 ×(x 2 Å 1)Å 1=x 1 ×x 2 Å x 1 ×1Å 1 = =(1Åx 1 Åx 1 ×x 2).
Let f(x 1 ;x 2)=(x 1 “x 2).
Then (x 1 “x 2)=(`x 1 ×`x 2 Úx 1 ×x 2)=ù(ù(`x 1 ×`x 2)×ù(x 1 ×x 2))=((( x 1 Å1)×(x 2 Å1))Å1)× ×(x 1 ×x 2 Å)Å1=(x 1 ×x 2 Åx 1 Åx 2 Å1Å1)×(x 1 ×x 2 Å1)Å1=x 1 ×x 2 Åx 1 ×x 2 Åx 1 ×x 2 Åx 1 Å
x 1 ×x 2 Åx 2 Å1=(1Åx 1 Åx 2).
Any function obtained using the superposition operation from linear logical functions is itself linear. Therefore, the set of linear functions does not allow the formation of nonlinear functions.
1.5.6.4. Functions that store “0”
The function f(x 1 ; x 2 ;...x n) is called preserving “0” if for sets of values of binary variables (0; 0;...0) the function takes the value f(0; 0;…0)=0 .
For example, f 0 (0; 0)=0, f 3 (0; 0)=0, f 7 (0; 0)=0, etc.
Any function obtained using the superposition operation from functions that preserve “0” is itself a function that preserves “0.” Therefore, the set of functions that preserve “0” does not allow the formation of functions that do not preserve “0.”
1.5.6.5. Functions that store “1”
The function f(x 1 ; x 2 ;…x n) is called preserving “1” if for sets of values of binary variables (1; 1;…1) the function takes the value f(1;1;…1)=1.
For example, f 1 (1; 1)=1, f3(1; 1)=1, f 5 (1; 1)=1, etc.
Any function obtained using the superposition operation from functions that preserve “1” is itself preserving “1”. Therefore, the set of functions that preserve “1” does not allow the formation of functions that do not preserve “1”.
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 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 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:
.
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:
| 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 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:
| T0 | T 1 | L | S | M | |
| + | - | + | - | + | |
| - | + | + | - | + | |
| - | - | + | + | - |
Corollary 3. From any complete system of functions it is possible to distinguish 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 
is either non-self-dual or does not preserve unity and is not monotonic. Therefore, no more than four functions are needed.
Let's get acquainted with the concept of superposition (or imposition) of functions, which consists of substituting a function from another argument instead of the argument of a given function. For example, a superposition of functions gives a function, and functions are similarly obtained
In general, suppose that a function is defined in a certain domain and the function is defined in a domain and its values are all contained in the domain. Then the variable z, as they say, through y, is itself a function of
Given a given value, they first find the value y corresponding to it (according to the rule characterized by a sign), and then set the corresponding value y (according to the rule
characterized by a sign, its value is considered corresponding to the selected 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 the function do not go beyond the limits of the region Y in which the function is defined is very significant: if it is omitted, then absurdity may result. For example, by assuming we can only consider 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 not related to the nature of the functional dependence of z on x, but only to the way this dependence is specified. For example, let for y in for Then
Here the function turned out to be specified as a complex function.
Now that the concept of superposition of functions is fully understood, 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 through the elementary in their final form; sometimes they are also called elementary.
Subsequently, having mastered a more complex analytical apparatus (infinite series, integrals), we will become acquainted with other functions that also play an important role in analysis, but already go beyond the class of elementary functions.
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 of 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 set of 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, well-known tables of values of 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 of the 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.
