Martynyuk_A_N_Diskretnaya_matematika

21.2. + $ $;

2 9 n 6 9 8 M

9

. 21.2. A n (

AN = (SN, XN, YN, N, N, {s0N}),

XN = X, SN = (× i=1nSi), {1, n}, YN = Y. z N : 5 8

N: SN× XN>SN (SN× XN) = {snj = (s'nj, x) (SN× XN)| snj = <s1j, snj, … sij, … snj> & s’ij = <s’1j, s’2j, … s’ij, … s’nj> & sij, s’ij Si 6 {1, n}, & sij = (s' j, <fi(y1k, y2k, …yik, …ynk), B(XN)) & yik v s’ij, 6 {1, n}}.

z N * : 5 8

N: SN× XN>YN N(SN× XN) = {y = N(s'nj, XN N(SN× XN)| y YN & XN XN & s'nj = <s'1j, s'2j, …s’ij, …s’nj> & s’ij Si 6 {1, n} & y = g(< '1k, '2k, …y’ik, …y’nk>, XN) & y’ik v s’ij 6 {1, n}}.

z N * : 5 8

N: SN× XN>YN N(SN) = {y = N(s'nj N(SN)| y YN & s'nj =<s'1j, s'2j, …s’ij, …s’nj> & s’ij Si 6 {1, n} & y = g<s'1j, s'2j, …s’ij, …s’nj> = gN(<y’1k, y’2k, …y’ik, … y’nk > & y’ik v s’ij

4 &. A ' . f1 = ( )

f2:Y1× Y3>X’2 X’2 = f2(Y1× Y3) f3:Y2>X’3 X’3 = f3(Y2)

g:Y2× Y3>Y Y = g(Y2× Y3)

. 21.3. A '

111

+H . % ,

1.Y $ , 8 '$ ?

2.Y ?

3.S " ?

4.Y & ?

5.S P ( & ( & &

?

% +

+

21.1.A ( 9.E. + b Pb b b. – A.: E, 1971. – N.305-335.

21.2.1 ˜ >. > & $ b( . – A.: & ', 1987. -

N.33-41; 74-82; 118-132.

21.3._ ., 1 " d. _'$ . – A: E, 1990. -N.302-335. 0 &

21.4.d % >.9. + b & " . – A.: >b `.`., 1986. -

N.160-204.

21.5.1 P d., 1 .. N & %. – A.: A, 1976. - N.75-

80.

0 ( '

21.6.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2002. –N. 54-57.

21.7.d d.4., N 9.9. N% & & " . –

A.: E, 1973. - N.190-208.

112

# : V. B " A B#

? 22. B " D )

" %

% % ( P ". , & & P, ' % P & & & ( . )

% P , 8 % &$' &$ , '

P .

3 & & :

22.6.P

22.7.1 P

22.8.P

22.1. F- / C

1 4 6 4 : , A + 5

6 9 6, 8 8 5 5 4 - 9 9. D A 8 5 5 4 5 k 6 ,

: 5 k- $.

… 4 9 5 9 :, 6 8 5C 6 (4) x1, x2,..., xn, A 9 5

6, 6 9. ( -9 4

<n< 6 y=f(x1, x2,..., xn) : 8 + 8 9 9 8 (n-6

9, ) 4 <x1, x2,..., xn>, A : 8 + , 9 5

Z={y1, y2,..., yk}.

D A 4 + 5 : 9 9, A ,

+ 5 & &$.

22.2. B + / C

-8 5C 8 5C 9 6 4 6 :

6 8 6 .

>. 1 $ P$ ' & & P, 8 "

& % >={0, 1}, % >={&, }.

? A 8 - , 8 5-D 4 :

1={0, 1} 1={6 8 5, }, 8 5 8 <n< 6

(4) - 9 9 <n<. < 4 5 6 6 8

9 <n< +: 2n . v 6 8 6 <n< 4 +: 22^n (2^n – n) . 3 5- 8 9 8 8 +

( ), 6 2n 8 5 6,

- 6 8 6.

113

Y0 Y3 - - (Y0 - <0<, Y3 - <1<), A + 5

6 8 6 4. z Z1 +: 4. z Z0, Z1, Z3 - 5 . — 5 - Z2, : 5

, :+, 8 y2= x : 5 < 2 +: x<. 3 6 6

n=2, 8 22=4, - 24=16

< 6 C 5 9 5 61, 62, 8 6 . B 0=0 -

, 15=1 - , 3=61 5=62, 9

10= 62 12= 61. = C 8 9 5 6 6. v 6 : C + 5 8 4 8.

1. 1 P ’$ ( )

1=61 62, 1=61&62, =61562, =6162, =61 62.

2 + + 5 4 9, A 8

8 4 : 5 8 + 9 <0< <1<, 8 +: 5

6 4 6.

2. 1 P &'$ ( & &)

7=61 62, 7=61+62, 7=61, 62

2 +: , A 6 8 4 +: .

3. 1 P & & & ( )

6 =61[ 62, 6=( 61 62), (61 62)

2 +: 8 9 6 8 6 61 62. 4. 1 P ( )

9 =61N62, 9=61w62, 9=( 61 62), (62 61).

2 +: 8 9 6 8 6 61 62.

5. 1 P ( ( &)

13=61>62 : 5, «A 61, 62 », 13= 61, 62.

2 +: 61, ++ + +:

62 61, ++ , 11=62>61, : 5 «A 62, 61» . 6.1 P (%)

2=(61T62), 2=61 62.

1 C : 2= (61>62), 5

+ 5 , 8 61T62 = x2>x1.

2 +: 5 61 ++ 1 62 ++ 0. M 4, 4=62T61 C +: 5 62 ++

1 x1 ++ 0.

7. 1 P « 4» ( &'$ )

8=61R62, 8= 61 62.

2 : 5 5 6 6 61 62. ( 5 ' 8 : '+, 8 = 7 .

8. 1 P «` ( • PP» ( '$ )

114

14=61/62 14= 61 62.

2 : , A 6 8 61 62 +: +. ( 5 ' 14 : '+, 14= 1.

22.3. F- /$+

v : 8 = 6 ( ), '+=61 62 (8), '+ =61 62 (8).

1 9, 4 + 6 + 5 8 , + 5

P - 8 , ' 4 6 . >

5 $ (8, &$) 6 6 6 6 C

.

4 &. E ( " =(1 (2, & (1= , (2=b5c, & ' = b5c

9 : 8 +. ˜ 6 6

6 9 8 6 6.

4 &. =0, b=0, c=1, (1= = 0=1; (2=b5c=051=0; =(1 (2=1 0=1

2 8 , , + 5 ', A 8 5-6

6 4 8 + 5 . 0 5

': + 5 .

+H . % ,

1.Y &$ $ ( P "?

2.S P k- $?

3.Y & & P?

4.Y ' % $ P$?

5.N ' % ( P " & n ?

6.S ’$ $ &’$ $, $ & &

& &?

7.Y P 4 ` ( • PP?

8.S % &$' % P ?

9.S P '?

% +

+

1.E -.9. 0 & . – N4%.: 4, 2001. - N.79-85.

2.N " >.4. A " . – _.: .(, 1975. -

N.504-522.

3.d % >.9. + b & " . – A.: >b `.`., 1986. - N.47-

50.

0 &

4.S% " N.>. > & &$ . – A.: E, 1979. - N.7-

15.

5.1 P d., 1 .. N & %. – A.: A, 1976. -

N.139-150.

0 ( '

6.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.24-25.

7.d d.4., N 9.9. N% & & " . –

A.: E, 1973. - N.9-20.

115

? 23. : " ? B " D. # " ? D #

" %

% & % ( P ".

% ", ", P " ' " %, ) & % '

%. E ` & P % % & & P.

3 & & & :

23.1.N % & % ( P "

23.2.4 & P % % & & P

23.1. % G . * , G + ( / C E

= + 5 8 8 6 : 8, , 4 5.

23.1.1. G+-E % G

> 8 : 5 8 ( ).

4 &. .% P & 3-( ( y=f(x1, x2, x3)).

. % 23.1

23.1.2. +-E % G

-5

>. 0'$ ' P (0E-) - &'$

( , " ( %$ '$ $ ( ( ( (

', 8 ( & ' & " % '` & .

>. _ '$ ' P (_E-) - '$

( , " S " %$ &'$ $ ( ( ( (

', 8 ( & ' & " % '` & .

4 &. =((1 (2) ((2(3 (4) 0E-, =((1 (2)5((2 (3 (4) _E-, =(15(2 (25 ((35(4) 0E- _E-.

>. o 0E-, 8 $' %$ '$ <?< %,

$' - . o _E-, 8 $' %$ &'$

<?< %, $' - .

4 &. (15(2 - 2- , (25(35(4 - 3- , ((1 (2) –

2- , ((1 (2) ((2 (3 (4) – 3- .

>. S 8 ' &'$ '$ P

& <n< ( ( &), & ( ' %

P, P ' & $ &'$ $ '$ $

'$ P$ (N0EN_E- – ).

A: - + / . ), 2 3, 1 32 /3, 2

/ EM;G. - + / . ), 2 3, 1

32 ), 2 / E5;G.

116

* >2-z + 5 <1<. * >-z + 5

<0<. <1< +: 5 + 5

8 5 6, 6 5, A

, A ++ 5 , 6

, A ++ 5 +. <0< +: 5 5 5

8 5 6, 6 5, A

, A ++ 5 +, 6

, A ++ 5 .

4 &. (1 (2(3 (4=1505150=1, (1 (2 (3 (4= 1 0 0 1=0

>2-z : '+ :+ <1<, 8 f(x1, x2,..., xn), A

:, +: 5 + 5 8 6 5 6, 6

6 8 6 . - C 6 8 6 +: 5 5. >-z : '+ <0<, 8 f(x1, x2,..., xn) +: 5 5

5 8 6 5 6, 6 6 8 + 6 . - C 6 8 6 +: 5 +.

2 8 4 >2-z + 5 '+ +

“1” 6 8 6, 6 : .

2 8 4 >-z + 5 '+ +

<0< 6 8 6, 6 : .

? 8 + 5 4 >2-z >-z.

4 &. .% , N0EN_E- P & 3-( (

. % 23.2

=( (1 (2 (3) ( (1(2 (3) ( (1(2(3) ((1 (2 (3) – N0E-,=((1 (2 (3)( (1 (2 (3)( (1 (2 (3)( (1 (2 (3) - N_E-

2 5 8 >2-z >-z 5. M

9 2-z, -z, 6 C 6 6.

23.1.3. A$ -E % G

8 + 8 6 <n< 6 : 9 9 + 2n n-

6 . D A 5 9 C n-

%, 8 5 8 : 5 4 n-

4 4.

3 : 5 n- 8 C, A + 5

<61, 62,..., 6n>, 6 +: +. 9 n 6

: 5 5 , : 5 . .

: + «0», 5 – + «1».

4 &.

# n = 1, ' ` &$ 2, & P - = (

(&. .13.1, );

117

#n = 2, ' ` &$ 4, P &

& & & `, & P – y = x1 x2 x1 x2

(&. .13.1,%);

#n = 3, ' ` &$ 8, P & %

& & `, & P – y = x3 x1 x2 x1 x2.(&.

.13.1, ).

. n 4 4 4 8 : 5.

118

23.2. * , /$+ G + +F G * * + /$

D A -8 5 Bj 2-z 5 6 , 5

9 :

Bj=Bj 1=Bj (xi xi)=(Bj xi) (Bj xi).

D A -8 5 Bj -z 5 6 , 5

9 :

Bj=Bj 0=Bj (xi xi)=(Bj xi) (Bj xi).

4 &.

=(1(2 (3=(1(2(3 (1(2 (3 (1(3 (1(3=(1(2(3 (1(2 (3 (1(2(3 (1 (2(3 (1(2(3 (1 (2(3

=((1 (2)(3=(((1 (2) (3 (3)(((3 (1 (1) (2 (2)=((1 (2) (3)5(((1 (2) (3)5((((3 (1)((3 (1) ) (2)5((((3 (1)((3 (1)) (2)=((1 (2 (3)((1 (2

(3)5((3 (1) (2)5(((3 (1) (2)5(((3 (1) (2)5(((3 (1) (2)=((1 (2 (3)((1 (2 (3)((1 (2 (3)( (1(2 (3)5((1 (2 (3)5( (1 (2 (3).

+H . % ,

1.Y % % & % ( P "?

2.Y 0E- _E-, N0E- N_E-?

3.S ?

4.Y “ $ &” “ $ ”?

5.S & " % & % ( P "?

6.Y ' % & % ( P "?

7.S &$ "-% &' 0E- % _E-?

8.Y & P & & P?

% +

+

1.E >.d., N 9.>. 4 & & -

(. 0 & ( (. – _.: 3 %-

& " % b ` %, 1992. - N.116-137.

2.E -.9. 0 & . – N4%.: 4, 2001. - N.88-91.

3.N " >.4. A " . – _.: .(, 1975. -

N.504-522.

0 &

4.S% " N.>. > & &$ . – A.: E, 1979. - N.19-

23.

5.d % >.9. + b & " . – A.: >b `.`., 1986. - N.47-

50.

0 ( '

6.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.25-27.

7.d d.4., N 9.9. N% & & " . –

A.: E, 1973. - N.20-38.

119

? 24. B " A B#. # U ?. "

" %

% %.

` & ' " " % % { , , }, 8 P , & " ' P % %, & " & " P. ) & % % % % & " ( , & P (

%.

3 & & :

24.1.1 %

24.2.N 8 P

24.3.4 & " ' P % %

24.4.1 %

24.1. B + +F G

-6 9 * 8 z, A + 5 9

z = {B1, B2,..., Bn}, 9 M = (*, z) : 5 %$. * 9 *

: 5 $, $ $. * 9 z : 5 $

", $.

>. 1 $ %$ > = (A, { , , } 0, 1) ' A & % “ ” “ ”, &$ $ $ “ ”

& & ( ' ) “0” “1”, & % &'-

( x1, x2, x3, 8 ' M, % " & &

=(x1 x3) (x2 x3) (x1 x2); =(x1 x3) (x2 x3) (x1 x2);

+ ' ,;

120