2005
, , .
- ( ). , ( ), , : ( 1) ( 0). . , , ( : 0 1).
. (X0, 1,... n1) , Y
Y = f (X0, 1,...n1).
:
();
();
().
.
()
, λ ( ( .) -). Ú (+) :
Y = 1+ 2
:
Y = 1 Ú 2.
: Y 1 2. , 1+ 2 1, 1 2. , 0, Y 0.
, X Y. . () :
= 2n; : ,
n (, ). 1 2 = 4 .
1
1 | 2 | Y = 1 + 2 |
, Y = 0 : 1 = 2 = 0.
, . 1.
( ) XI 2. 1, 0. , . . 1 2 , , (1 , 2). ij, ( ) Y (Y = 1) HL . 1 = 0 2 = 0 1 2 , , (Y = 0).
|
|
()
( -) 璺 Ù () :
Y = 1 Ù 2
:
Y = 12.
: Y XI 2. Y = 12
1 | 2 | Y = 12 |
2
1 (1=2 = 1). 0, . :
, . , , , . 1, , . HL Y , (1 1) , (1=1 2 = 1) (. 2).
()
( ) . :
: Y . , Y , ( = 0) .
3
Y | |
(. 3), ( ), ( =0) , , , X ( =1) .
, - .
, . , :
1. , , ( , , );
2. , , , , , ;
3. .
.
+ :
4
+ = | = | |
+ 1 = 1 | 1 = | |
+ = | 0 = 0 | |
= |
:
1 + 2 = 2 + 1; 1 2 = 2 1.
:
(1 + 2) + 3 = 1 + (2 + 3); (1 2) 3 = 1 (2 3).
|
|
:
+ :
(Y + Z) = Y + Z;
+:
+ (Y Z) = ( + Y) ( + Z);
, , : , ᒺ .
:
: X + X Y = X,
: X Y + X = X.
( ):
,
.
, - , Ż λ Ż.
.
: , , . ֳ .
, . . , . , (, + ). . . . , , . ʳ , , . , 0 1, 2. , 25 :
2510 = 2101 + 5100 = 124 + 123 + 022 + 021 + 120.
. , , , .
. 10 2, 2 , , 2 , 2. , ( ). 䳿 .
.
. 5.
5
0 + 0 = 0 | 0 0 = 0 | 0 0 = 0 |
0 + 1 = 1 | 1 0 = 1 | 0 1 = 0 |
1 + 0 = 1 | 1 1 = 0 | 1 0 = 0 |
1 + 1 = 10 | 10 1 = 1 | 1 1 = 1 |
, , .
, , . , , . ˳ , .
|
|
, , :
,
,
Ż,
λ ()
:
= X1 + X2.
. 4 . . 0 1 ( . 1 U 1 = 2,4 5 , 0 U 0 = 0 0,4 . -:
U 1 = 0,7U ;
U 0 = 0,3U .
1 Y, - 1; 0 , X 0.
()
:
Y = X1 X2.
ʳ X - ( ). Y 1 , X 1. 0 0.
. 5.
Ż ()
:
.
³ . 1 Y , 0; 1, Y 0.
. 6 .
, , . ֳ . (. 7).
, , - . ֳ . , , , , - . -Ż -Ż.
-Ż
:
.
³ Ȼ Ż, (. 8).
. X 1, X1 X2 Y 0, Y , , 1. X 1, Y 1, Y 0.
, Ż 1 0 X 1 0.
,
,
Ŗ,
(. . 9).
, - .
( ϳ)
( ). ³ (. 10).
. 1 Y 1, Y 0, , 0, Y 0, Y 1.
, 1 , 0; Y 0.
|
|
ϳ - -, (. 11).
-, . . , - + U , , -, 2 .
, , . .
, . ϳ 䳺 . .
, - . 䳿 , .
.
, , : Q, , , . Q 1, 0; .
, . , , ,
().
, . , , . , , , ( ).
:
S ( Q);
R ( );
D ( , );
;
.
. RS - , D- -.
.
RS-
RS- : R 0 1 .
RS- , . 12 13 .
:
2- (. . 12)
2- (. . 13).
, , , .
?
, 2- ϳ (-).
S 1, R 0, - ( 2 1 Y () 0, 1 (. . 14).
S 0 1, 2 , , 1, ( . . 15).
R 0 1 S , , 0 0 , 0 2, 1, 0. R ( 1 0) , , 0 (. . 16).
|
|
R S 1, 0, , . , , . , , , .
6, Qt , ( ). , 䳺 ( , ); Qt+1 .
6
S | R | Qt | Qt+1 | ||
* | * | ||||
* | * |
: , 0 , , 1 , , . 1 S 1, 1 R Q 0. , 1.
:
1. S = 1, R = 0 (Qt+1 = 1, = 0, 1);
2. S = 0, R = 1 (Qt+1 = 0, = 1, 0);
3. S = 0, R =0 ( );
S = R = 1 , 䳿 (Q t +1 = = 0), 䳿 - . .
S = 1, R = 0 1 ( Qt+1 = 0); S = 0, R = 1 0. S = 0, R = 0 ,
1 , 0 , 0 , , 1. , 0. 7 :
7
Qt | Qt+1 | ||||
* | * | ||||
* | * | ||||
1 , , = 0, = 1; 0 = 1, = 0. = = 1 . = = 0 .
D -
. : (D) , 1. D - . 17.
0- 0 1 1. D , 1. .
D - , - .
= 0, 1 2 ( ) - 1. , (. 18).
= 0 , D. , , D 1, 1 1 0, 2 1 0, , 1. , 1 (Q = 1, = 0, . . 19).
D 0, 1 2 0, 1
1 . , 0 (. 20)
8 D- :
8
D | Qt | Qt+1 |
: Qt ;
Qt+1 .
: , = 0 Qt+1 = Qt, = 1 Qt+1 = D.
. 21 D- . , , , . , .
D- . , = 1. . . , , . .
-
- : Q . ( , , . , - , . - .
, . 22.
-, , , . D- , 璺 (. 22). .
1, Q 1, 0. , D 0. 0, . : Q 0, 1. ; = 0, 1. () 0 ..
( ) ( ), , , (. . 22). .
, , JK, RS-, D- - (. 23).
, ( ).
().
D- ( . 24) , , . , Q1 Q4, .
. , .
.
.
D- 1011. , , . 25.
0. () D 1. 1, ,
0. 1. 1, . , , 1. , ( 1), 0.
D 0 ( ), 1, 2- 1,, 3- 1.
, D 1- 1, 1- 1, 2- 1- 0, 3- 1, 4- 1.
, 1011 (1 Q4, (1 Q3, (0 Q2, (1 Q1).
, D 1- 1, 1- 1, 2- 1- 0, 3- 1, 4- 1.
, N - N . QN Q1 ( 1011 Q4 Q1) N+1 (5-) . , , , N- (5-) N ( 5 9) 9N + 1 2N + 1).
˳
˳ , , . , , . , - (. 26).
ϳ , ( ). , n RST- ( ), f = f /2n.
R 0 ( 0), S 0 ( R S 1).
, , . ³ 1 , , 0 . , . . ³ 1, , , , 0, . , , .
(. 27).
. 13 , 1 ( 13), 0 ( 6), 1 ( 3), 1 ( 1). , 1101 13.
(), 2, , = 2 . , , , . 15 , 16- 0 . , 9-) 111112 = 3110 . .
, 2n. , 6 ( ), 10 ( ), 7 ( ), 24 (). ≠ 2 n n , 2 n > . , (2 n ) , , . , = 10 (23 < 10 < 24). ˳ 10 N = 0, 1,..., 8, 9. , 11- , .
, . , i- 2 ( , i, ) i+1.
3, 23 = 8. (. . 9). S i+1 , S = 1 i+1 =1.
(. 28). . 28.
9
i | S | i+1 | ||
, 璺 (. 28).
()
, n- .
( ) .
?
0 9. - , 10 (0 9). (Y1, Y2,...). , , , (. . 10).
10
Y8 | Y4 | Y2 | Y1 | Y8 | Y4 | Y2 | Y1 | ||
20 Y1 - : 1, 3, 5, 7, 9, 1 3 5 7 9. , Y1 :
Y1 = 1 Ú 3 Ú 5 Ú 7 Ú 9.
21 Y2, 22 Y4, 23 Y8. :
Y2 = 2 Ú 3 Ú 6 Ú 7,
Y4 4 Ú 5 Ú 6 Ú 7,
Y8 = 8 Ú 9.
, . 20 5 ( 1, 3, 5, 7, 9),
21 22 ( 2, 3, 5, 7; 4, 5, 6, 7)
23 ( 8 9). (. 29):
) () .
()
, , : , , . , .. , 1551 . , . , - , . :
) 1551
, , 10 -. - (0 9) 4- :
11
- ( ) | - | ||||||||||||||
8 | 4 | 2 | 1 | Y0 | Y1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||