Martynyuk_A_N_Diskretnaya_matematika

? 26. A# D ! B ! : ?

" %

& "% '` ( & % (

P ". & & ' ( ) n-

%, % _ ) '. )

& & & _ >, & % ' P

% &.

3 & & & :

26.1. d P " & % ( P " 26.2. .% " &

26.1. A /-E $* $ $. C G + ( / C E

9 C n-4 8 9 5 . 9, 9 6 C : 8 9 8 n 6

>2-z.

2 8 9 n 6, >2-z, 86

5 9 n-4 8.

* n-4 4 n-6 : C

n-4 8. * (n-1)-4 4 9 4 5 6

n-4 4, A + 5 :+ +:

Bn-1=(Bn-15xi) (Bn-15 xi).

- n- 8 : 6 C, A + 5

, 8, A ': : C. q 5, A 8

C. ? , (n-1)-4 + 5 8 n-4 8. M 4 +: 5 5 (n-2)-4 4 n-

4 8, 9 6 : C 8 8 ( ).

T n-4 8, A 6 + 5 <S< , + 5 s- 8. ? C + 5 0-8, 8 - 1-8, 4 - 2-8 . . ? , 8 5- 2-z 8 9 : 5 n-

8 + S-8, A + 5 C, + 5

«1» (0-8). q 5, A 5 S-8 5

P.

4 &. 0 P & ' ( ( y= x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3

x1 x2 x3 x1 x2 x3, & & N0E-, P " & & P & ymin= x3 x1x2

x1 x2 = x3 (x1 [ x2).

. 26.1. d ' % & P ymin = x3 x1 x2 x1 x2

P &

131

* n- 8 5 C 4 , S-8

4 8 5, 6 5 S 5. ? + 5

' , 2-z - '$ 0E- (A0E-).

M 4 9 + 4 8 -z, 5 4

86 5 >2-z 4 >-z . 2 n=3. . n44 .

26.2. G+-E $* $ $. C

v C 8 + 5 - 5

4 8 : 8 + 5

8 8 5C 6 6, 8 C , A 9 : 5 5 4 5 : 6. < D 5 4 + 5 5 :+ +.

, C 6 8 9 9 + 5

+ 5 :+ +. : + q. 2 2-z 8, 6 : «1» ++ 5 «1».

-5 ++ 5. 2 -z 8, 6 :

«0» ++ 5 «0». ++ 5.

M 4 n- 8, 6 6 : 1-8, 4-6

6 - 2-8 . .

< +: 5 : , A ++ 5 S-8 + 5 (n-s)-4 4, 6 5 (n-s) 6, 8 4 + 5

5 s-8. 2 2-z + «1» + 5 6,

+ «0» - 6 . 2 -z + «0» + 5

6, + «1» + 5 6 . <, A 8 4 + 5

s-8, ( -z) 6 5.

< 4 + +: 5 4

n- 8. 2 4 : *2-z 5

«1» *-z 5 «0».

4 &. _ _ & P " & & f1= x

(% . 26.1), & ( ( f2=x1 x2 (% . 26.2), ' ( ( f3= (x2 x3) (x1 x2) ( x1x2x3) (% . 26.3) ' ( ( f4=(x2 x3) (x1 x2x4) ( x1 x2x3) (% . 26.4)

								. % 26.1
								f1			x=0 1
						1
f2	x1,x2 00 01 11 10										. % 26.2
			1			1					1
														. % 26.3
			f3 x1,x2			00		01			11	10
			x3
			0			1						1
			1					1				1

132

. % 26.4

f4 x1,x2	00	01	11	10
x3x4
00		1	1
01		1	1	1
11	1			1
10	1

1 4 : 8 5C 6 8 (6), 8

4-6 6, 8 9 n- 8. 2

8 9 5- 6 + 5 4-6 6,

6- 6 + 5 , n45 5

4 8 5.

4 &. 0 _ & P & ' (, 8 &$'

x5		(% .				26.5,	26.6),
f5=( x2 x4) ( x1 x2 x3) ( x2 x3 x4) (x1 x2 x3) ( x1 x3 x4).							. % 26.5
	f5	x1,x2		00	01	11	10
	x3x4
	00			0		0	0
	01				0	0
	11
	10			0			0
x5=0
							. % 26.6
	f5	x1,x2		00	01	11	10
	x3x4
	00			0			0
	01			0
	11					0	0
	10			0			0

x5=1

. 8 1, A + 5 C 6 9

8 + 5 . . 1 C

5 .

4 &. _ > " & P " & ' ( ' (

f6=(x1x2) (x2 x3) ( x1 x2x3), f7=( x3 x5) ( x1x2x4) (x1x3 x4x5).

				. % 26.7
f6 x1,x2	00	01	10	11
x3
0		1		1
1	1			1

133

? 8 26.8

f7 x1,x2,x3	000		001	010		011		100		101	110		111
x4,x5
00	0			0				0			0
01	0									0			0
10		0			0		0		0			0
11					0		0

+H . % ,

1.S $' & & ' n- % P % P?

2.Y ' & % n- %?

3.Y ' % (n-k)- n- %?

4.Y s-% & n- %?

5.S ' s-% P?

6.S " ' P?

7.S P & & _E-?

8.S ' & _

?

9.Y & & & % _ ?

10.Y & & % (n-k)- _ ?

11.S ' &$ _ ?

12.o ' % &$ _ ?

13.Y $ > " ' &$ > "?

% +

+

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

N.550-564.

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

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

& " % b ` %, 1992. - N.146-161.

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

55.

0 &

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

N.215-220.

5.E -.9. 0 & . – N4%.: 4, 2001. - N.91-92.

0 ( '

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

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

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

134

-5-8

? 27. ! : ?. B : "

" %

% &

% ( P ". %, & ,

& _", % % " &. + & & "

%, % & % % $ $ % $

.

3 & & :

27.1.9 &

27.2.A & _"

27.3.9 % " & & ' ( 4)

27.1. +- $* $ $. C

27.1.1. $%+ G

M + 5 5

8 6 . 2 6 + 5 %.

>. _ % _( ) P y=f(x1, x2,..., xn) - %'& _s(y)

( s-%, & 0,s,n-1, & _s(y) ' % :

5( )= 5s(y)

9 s-8 8 9 : . 2 s-8 6

«n» 6 + 5 9 «n». 16

+ 5 ' + 5 + xi 8 6. - 6

( ) + 5 ' + 5 «× » (6), 8

«~» (5).
4 &.	n=5	x1 x2x3x4 x5'	00110 - 0-%
x1 x3x4'	1× 01×	- 2-%
x1x2 x5	'	01×× 0 - 2-%
x3 x5	'	×× 1× 0 - 3-%

(0-8) + 5 , 8 . > 5 6 s-8 : 5 9 {0, 1, × }, 8 {0, 1, ~}, A

+ 5 8 ' 5 .

4 &.	y = x1 x2 x3	x1 x2x3 x1 x2x3	x1x2x3 x1x2 x3 x1x2x3. _(y) =
_° _1 _2,		K1 = {1 0 ×	K2 = {× × 1}
& K° =	1 0 0
	1 0 1	× 0 1
	0 0 1	0 × 1
	0 1 1	× 1 1
	0 1 0	1 × 1
	1 1 1}	0 1 × }

8 +: 5 . 4, + +

5 4 S-8, A + 5 8 A , 9 :

. > : 9 6 5. - 9

6 5 + 5 5.

D A 8 , 9 8 9

9 5 -z.

135

27.1.2. . *-

* 6 8 8 5 C 5 2-z,

: 5 . 2 8 : 5

, A +: 5 :

: 6 / * . ) 0 2 / ) 5 *, + / E=kqs(n-s), qs - / S-+, 1 33 0 . ) 0

n , s - +.
* 5 6 : 5 5 + +.
4 &.	y=x1 x3x4 x1x2 x1x3	n=4
	C=15(4-1)+25(4-2)=3+4=7.

< +: 5 .

E ` 6 5 , A 5 S-8

5 : 9 4 8, A : 5 D-8 5 8 5 4 .

1 + 2-z + 5 $ 0E-, -

. 2 8 5-D 8 : :,

9 8 C 4, A 8 + 5

C 6 8.

E & +: 5 6 2-z 0E-,

2-z + 6 C 6 8, 8 6 5

8, A C, A 5 8 , 5C

+ 9 4 8 9 5 8 9 : +, 8 : 8 .

8 4 , A : C 8 ,

+ 5 D C 8 4 , 9

C 9 5 . ? 8,

, : 5 $ $ $, C, A

+ 5 , - & C. * 9 +: &

.

. 6 4 5 4 : 5

. D A 9 5 , +: 5

C 8 8 4 . - 9 6

6 5 8 : 5 5.

EM;G ' E M;G ' {M;G} ' {6M;G}

4 &. y = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3

K0 = 0 1 0	K1 = 0 1 ×		K2 =
0 1 1		× 1 1
1 0 0		1 0 ×
1 0 1		1 × 1
1 1 1
C0E- =_1		.0E-1 =	0 1 ×	.0E-2 =		0 1 ×
				1 0	×	× 1 1
				1 ×	1 `	1 0 ×
A0E-1 =	0 1 ×	A0E-2 =		0 1	×
	1 0 ×			× 1 1
	1 × 1			1 0	× .

136

27.2. * E

D 6 8 + 5

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

( +).

(( ) (a xi)=a

* 9 «1» : 5 0-8 0, +

: 8': 6 0-8, A + 5 5 :+ +. 0 5 4 8': : 1-8, 6 6 0-8 A

× .

4 &. 0-%: 1010 ' 1-%: 10× 0. 1000

D A 0-8, 9 : 9 1-8 1. < +

9 8 9 1 + +, 6 9 2-8 2. . . 9 : 5 , 9 S 4 9 S+1

5 9 5 + ( 8 n-8, A : + –

«1»). ( 5 : 8, A : 5 9 S:

={ 0, 1,..., S}, * s,n-1.

2 0 9 6 Z K 9 +

C 8 + 5 8, A : + 5 8 A .

, A 8 5 9 6 Z,

+ 2-z.

- 4 : 5 % '. ˜

+ 5 , - «1» (0-8)

. ( 8 5 , A , A :

, : C, : + . T + 5

8, A 5 : -8 5 . 1 +

, 6 + 5 , 9 : % $

5.

< 8 5 C 8 8 + 5

, A ++ 5 9 6 5. *

: 4 -8 5 . - 9 6

6 5 + 5 5 , 6 9 8 5.
4 &.	) & P y= 1(0,			1, 2, 5, 6, 7). _ % '
,		(	_1	&$		0E-,
% . 17.1 $ N 0E- 1.
_ = 000	_1 =	00×	_2 =
001	0× 0		N 0E- = _1
010	× 01
101	× 10

1101× 1

11111×

137

								. % 27.1
			000	001	010	101	110	111
	00×
	0× 0								>
	× 01								N
	× 10								D
	1× 1								E
	11×								F
			A B	A C	B D	C E	D F	E F
3 & & (W ' ' &
18). . 0E- $' &:
.0E-1=		00×		.0E-2=		00×	.0E-3=		0× 0
		0× 0				× 10			× 01
		1× 1				1× 1			11× .
		11×

A ' 0E- ( ' _" $' &:

A0E-1=.0E-2,

N & P1=3(n-1)=6, ymin1= x2 x3 x1 x2 x1 x3,

A0E-2=.0E-3,

N & P2=3(n-1)=6, ymin2= x1 x3 x1 x2 x2 x3.

27.3. +F G-E $* * ; , $ $+H F % , (+F$ )

1 8 5 4 + : 5 4 +

4 8 4 , A .. 1 6 4 – 8 5. . + 5 D-8 5 , ,

5 4 . ( 9 8 : 5 '+ 6

, A + 5 0-8. .+ : '+ 6

6 '+ .

D A 9 4 + 9 8 4 8,

9 : 2-z, 9 : +. 1 8 6

6, A 5 5 5 5 8 8 5 , : 9 5

5 .

4 &. ) & ' % & 8 ' &

:

A .0E-: (9 >)(9 N)(> D)(C E)(D F)(E F)=…=

=ADE ABEF BCDE BCEF ACDF ABCF BCDF BCF...

4 & '$ , 8 $' " ` & &$' & & & A0E-. . 8 & ( ") , & '$ "

$$' A0E-.

M 4 8 A + 5, A 6 8

5, A 9 A

6 6 , 8 +

28.

0 5 5 : 9 6 , A ++ 5 5

6 5. * 5 6 5 5

5 .

138

+H . % ,

1.Y % _( ) " % &?

2.S $' ' , S ', $' %' ' ?

3.o % ' ?

4.Y , 8 '?

5.o % & _E-?

6.Y $ _" % $'?

7.S " & ?

8.Y , 8 ?

9.	Y $, % $ $ & ?

10.S % ( & & &

'?

11.Y & _" ' & ' % ?

12.S &$' % $ ?

13.3 ' 4?

14.S & P _"-A_ ' & `

'?

% +

+

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

N.550-564.

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

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

& " % b ` %, 1992. - N.146-161.

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

55.

0 &

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

N.215-235.

5.E -.9. 0 & . – N4%.: 4, 2001. - N.91-92.

0 ( '

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

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

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

139

? 28. ! : ?. "

" %

& & & '

( ( % ( P ". & P " & _"- A_ , % ( P ". +

& & " %, ( & (

%, ( P . 3 & & & :

28.1.A & P " & _"-A_ .

28.2.A ( P ".

28.1. * E-+

- : 5, 6 86 9

9 4 8 S.

* -* : :+ , A : C

5. 2 ’ : 9 9 S 8 : 5 , 9 D 5 S-8 5. + 5,

, 5 8 . 5 + 9 5 5

S-8, 5 6 : 5 +, 5 8 9

								S-8			4
S-8 5 4 . 1 C +: ,
2-z, -z.
4 &. E ( " ' % & % P & ' ( (
= 1(3, 4, 5, 6, 7, 9, 11, 12, 13). _ ' ( K={_-0, _-1, _2} &
& & & 4 % ' (% . 28.1) $' " &:
_0=	0011			_-0= 0100					_-1=		010×			_2={× 10× } _3=
				0100					- - - -				× 100
				0101					0011				- - - -
				0111					0101				0× 11
				1001					1001				× 011
				1011					1100				01× 1
				1100					- - - -				× 101
				1101		1101			0111		110× .		10× 1
													. % 28.1
			0011		0100	0101		0111		1001	1011	1100		1101
		0× 11													9
		01× 1													>
		× 011													N
		10× 1													D
		1× 01													E
		× 10×													H
			A C					A B		D E	C D

140