- ( , .). - .
19. . , , , -. , 5 : x 1, x 2, x 3, x 4, y (xi = 1 , i - (i = 1, 2, 3, 4), y = 1 , ). , x 1, x 2, x 3, x 4, y 1 , -, , . , - ( ) . Ÿ ■
, ( , ). , x 1, x 2, x 3, x 4, y , .. f (x 1, x 2, x 3, x 4, y) = 1. - , , , . - f (z 1, , zn) :
≤ (i = 1, 2, , n)→ f (, , ) ≤ f (, , ). (29)
, - . , .
.
1. 1 (.. -). , . - 1, , , , . - 0. , , .. .
2. , , , ( ) . - , , .
3. . , i - , ( ), , i - . , . , -.
|
|
4. , - ( ), , . , 01101 x 2 x 3 y ( - y ).
5. . - ■
20. , 19. - 13 1 . , x 1, x 2, x 3, x 4, y (. (1)). f. , , . , y = 0, f 0, . 0 - f . , y = 1, - , .. 1 , , .. 3, 4 5 ( 2, 1 0).
2. ( 14). 15.
3. , , , ( , ). 15 , 13 , 15. 23 , 21 , 23. 27 - - 25. 29 - 25. 31 1 , , . 6 16.
4. 16 6 : x 3 x 4 y, x 2 x 4 y, x 2 x 3 y, x 1 x 4 y, x 1 x 3 y, x 1 x 2 y.
5. - . f (x 1, x 2, x 3, x 4, y) = x 3 x 4 y Ú x 2 x 4 y Ú x 2 x 3 y Ú x 1 x 4 y Ú x 1 x 3 y Ú x 1 x 2 y ■
13.
|
|
|
|
14.
|
|
15. ,
| 16. ,
|
21. : , - , B, C D, . - -. .
|
|
B, C D x 1, x 2 x 3, - y. 1 17:
17.
|
|
, 3- , , , . ( 4 , ). .
2, , (. 18 19).
18.
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
19. ,
| 20. ,
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3 20 , 15, , . - 4 5, : f (x 1, x 2, x 3, y) = x 2 x 3 y Ú x 1 x 3 y Ú x 1 x 2 y ■
|
|
- . . α = (α 1, , αd) d, (, - ). , (.. 0 1 1 0). - , .. :
1. α = (α 1, , αd) β = (β 1, , βn).
2. β = (β 1, , βn) = ( 1, , n) = ( 1, , d), , = α, β.
. , αi -
, : 0, αi = 0, αi = 1. β ( ). , n d . , , d 1. , .
5.1. . , , . k. , .. , - :
00000
00001
00010 (30)
..
11110
11111
(. (1)). , i - ( 0) - (16), i. ek (i) (0 ≤ i ≤ 2 k 1). -, k = 3
e 3(0) = 000, e 3(1) = 001, e 3(2) = 010, e 3(3) = 011, e 3(4) = 100, e 3(5) = 101, e 3(6) = 110, e 3(7) = 111 (31a)
k = 4
e 4(0) = 0000, e 4(1) = 0001, e 4(2) = 0010, e 4(3) = 0011, e 4(4) = 0100, e 4(5) =0101, e 4(6) = 0110, e 4(7) = 0111,
e 4(8) = 1000, e 4(9) = 1001, e 4(10) = 1010, e 4(11) = 1011, e 4(12) = 1100, e 4(13) =1101, e 4(14) = 1110, e 4(15) = 1111. (31b)
j - ek (i) (j = 1, , k). , , . , e 3(3) = 011, = 0, = = 1.
ek (i) i = 2 m (m = 0, 1, , k 1).
1. m = 0, 1, , k 1 = 1,
2. p < 2 m = 0.
3. q > m = 0.
, k 2 m 00100, (k m)- . -, 1 = 20, m = 0, k m = k ek (1) = 0001 , .. k -, . , 2 = 21, m = 1, k m = k 1, ek (2) = 0010 , .. (k 1)-, . , ek (4) = 00100, ..
β = (β 1, , βn) n. h (β)
h (β) = , (32)
k ,
n < 2 k. (33)
, h (β) k . ek (i), 0 1. 2: 0Å0 = 1Å1 = 0, 0Å1 = 1Å0 = 1. (32)
hj (β) = (j = 1, , k). (34)
, (32) (34) 1, 0, - ek (0), , (32) (34) β 0. - 3) Å (. 2) (32) -, β 1 β 2
|
|
h (β 1 Å β 2) = h (β 1) Å h (β 2). (35)
5.2. . d α = (α 1, , αd) k , d + k < 2 k. - n = d + k. n < 2 k, 1 d + k k (. (30) (31)). 21 k n d. d ⁄ n: d 1.
5.2.1. . β = (β 1, , βn) α = (α 1, , αd) . β,
15.
d | k | n = d + k | 2 k |
: β 3, β 5, β 6, β 7, β 9, . , d. ,
β 3 = α 1, β 5 = α 2, β 6 = α 3, (36)
.. , , - α. β - ( ), , - . , - : 1, 2, 4, , .
22. α = (α 1, α 2, α 3, α 4) 4 (d = 4). k d + k < 2 k. 4 + 2 > 22, 4 + 3 < 23. k = 3, n = d + k = 7 (. 21). β = (β 1, β 2, β 3, β 4, β 5, β 6, β 7) 3, 5, 6 7 -. α 1, α 2, α 3, α 4) β = (β 1, β 2, α 1, β 4, α 2, α 3, α 4) ■
β 1, β 2, β 4, :
= (m = 1, , k). (37)
ek (i) i = 2 m (37) - βi,
1) i >2 m ( é 0 2);
2) i ≠ 2 q q > m (. 3).
, βi , i ≠ 2 q q, (37) . , (36) (37) , β = (β 1, β 2,, βn) α = (α 1, , αd). , - .
1. α β (36).
2. β (37).
23. β = (β 1, β 2, β 3, β 4, β 5, β 6, β 7) - α = (α 1, α 2, α 3, α 4) 4. d = 4 k = 3 (. 21), - (. (37)):
β 1 = β 3 Å β 5Å β 7;
β 2 = β 3 Å β 6Å β 7;
β 4 = β 5 Å β 6Å β 7.
β 3 = α 1, β 5 = α 2, β 6 = α 3, β 7 = α 4, - , β = (β 1, β 2, β 3, β 4, β 5, β 6, β 7) - ( ) α = (α 1, α 2, α 3, α 4) ■
. d k (, k , d + k < 2 k)
β 1 = β 3 Å β 5Å β 7 Å 1 n = d + k,
β 2 = β 3 Å β 6Å β 7 Å β 10Å β 11 Å 2 n = d + k,
β 4 = β 5 Å β 6Å β 7 Å β 12Å β 13 Å β 14Å β 15 Å 4 n = d + k, (38)
...
...
5. β = (β 1, , βn), - , (37), -
h (β) = 0, (39)
h (β) (32)
, (37) , (32), 0, Å = 0 ■
24. 23. α = 1011. β 11:
β 1 = β 3 Å β 5Å β 7 = 1 Å 0 Å 1 = 0;
β 2 = β 3 Å β 6Å β 7 = 1 Å 1 Å 1 = 1;
β 4 = β 5 Å β 6Å β 7 = 0 Å 1 Å 1 = 0.
, β = 0110011. (. 18) (17))
h (β) = 0×001Å1×010Å1×011Å0×100Å0×101Å1×110Å1×111=010Å011Å110Å111 = 000 = 0, (40)
5.
5.2.2. . β = (β 1, , βn), - α = (α 1, , αd) (36) (37) - . = ( 1, , n), β , . , .. β,
6. h () = (. (32)) 0, - , = ( 1, , n), β = (β 1, , βn). h () = 0, , .. = β.
. , β = (β 1, , βn) = ( 1, , n), : βs βs Å 1 (0 1 1 0). δ, , s -, 0, s - δs = 1. = β + δ. h (39) h () = h (β) Å h (δ) = h (δ) = ek (s). , ek (s) - s k, h () ≠ 0. h () = 0 = β, , h () = 0 ■
6
.
1. = ( 1, , n) (32) h ().
2. h () = 0, 4; 3.
3. ek (s) = h () ≠ 0 s, - ek (s), s - .
4. β. β, 1, 3, 5, 6, .., 2, α = (α 1, , αd) ■
25. 24. β = 0110011 3- , .. = 0100011 β = 0110011. h (). (. (40)):
h () = 0×001Å1×010Å0×011Å0×100Å0×101Å1×110Å1×111 = 010Å110Å111 = 011 = 3,
6 3- . 0 3- 1, = 0100011 β = 0110011 ■
26. = 01001001. n = 9, 15 , k = 4 d 5. -. (. (17b) e4(i)):
h () = 0010 Å 0101 Å 1001 = 1110 = 14
( , , 1). ,
14- . 14- 9 . ?
. , , . , 01001001 . α 4, 4.2.1 - , ■