Martynyuk_A_N_Diskretnaya_matematika

!

" #

$%’' ( $

" # )

*+, * - .- /$ -,

% ,$ 6.0804 6.0915

- 2009

!

" #

$%’' ( $

" # )

*+, * - .- /$ -,

% ,$ 6.0804 6.0915

: *;. * / *

, % + = 3 * 14.10.09

- 2009

2

« »

6.0804 6.0915/(.: * + . – : -.(, 2009. – 194 .

0: .1. 2, . . ., , .3. 4, . . .,

« » 5

6 5, ’ 8 6 –

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

<*=>?
"....................................................................................................................................	9
# : 1. # ? @ A B# )! ................................	10
? 1. " ? ? # ) @..............................................	10
" % .................................................................................................................................	10
1.1. % , , . * , $;...................................................................	10
1.2. % C * $;$ . D$+. ; .............................................	11
1.3. * , ; E. B + +F G $; ............................................	12
1.4. . F +H , % C E. * E H ..................................................................	12
+H . % ,...................................................................................................13
% +: ........................................................................................................	13
? 2. # " ? ?. # ? # :B ". @....................	14
" % .................................................................................................................................	14
2.1. # , ,....................................................................................................................14
2.2. , .G...............................................................................................	14
2.3. ; H $;. :-+ +H $;..............................	15
% + .........................................................................................................	16
? 3. #? " @. A# D ............................................	17
" % .................................................................................................................................	17
3.1. % ,* $;..........................................................................................	17
3.2. A /......................................................................................................................	18
% + .........................................................................................................	20
? 4. " ", B# : # B# :. " B# @ ?.
A#......................................................................................................................................	21
" % .................................................................................................................................	21
4.1. " *% * ............................................................................................................	21
+H . % ,...................................................................................................24
% + .........................................................................................................	25
? 5. " J ? .............................................................................................	26
" % .................................................................................................................................	26
5.1. % , , * K H..................................................................................	26
5.2. ; % C * K H..............................................................................	28
+H . % ,...................................................................................................28
% + .........................................................................................................	29
? 6. # ) " J ?............................	30
" % .................................................................................................................................	30

3

6.1. , ; ,, % % , / * ............	30
6.2. :F * F, % % . C ,.......................................................................32
+H . % ,...................................................................................................33
% + .........................................................................................................	33
? 7. " " " " J.............................................	34
" % .................................................................................................................................	34
7.1. % * + * K H ...................................................................	34
7.2. % C +H + * K H ......................................................................	36
+H . % ,...................................................................................................37
% + .........................................................................................................	38
? 8. " " J.........................................................	39
" % .................................................................................................................................	39
8.1. + H.......................................................................................................	39
8.2. ,*.....................................................................................................................	41
8.3. + H ..........................................................................................................	43
8.4. . % ,*............................................................................................................	44
+H . % ,...................................................................................................44
% + .........................................................................................................	45
? 9. : ?. D ). # ) .........................	46
" % .................................................................................................................................	46
9.1. :$, * K H ............................................................................................	46
9.2. % C +H / C..................................................................................................	47
9.3. % C.....................................................................................................................	48
+H . % ,...................................................................................................50
% + .........................................................................................................	51
? 10. : : )...........................................................................	52
" % .................................................................................................................................	52
10.1 $% . C , G'N...............................................................................................	52
10.2. " K E . $% . C..............................................................................	54
+H . % ,...................................................................................................55
% + .........................................................................................................	56
? 11. A B# )! ......................................................................	57
" % .................................................................................................................................	57
11.1 +F G- $ ($* +) ...............................................................................	57
11.2. A % % * +HC $;..................................................................	59
+H . % ,...................................................................................................60
% + .........................................................................................................	61
# : II. B #......................................................................................	62
? 12. B #. B : " ................................................	62
" % .................................................................................................................................	62
12.1. " G +$ .................................................................................................	62
12.2. + $ * G........................................................................................	63
12.3. .........................................................................................................	63

12.4.% +-,.............................................................................................................64

12.5.# % * K ,.................................................................................64

12.6. B$ H'.......................................................................................................	65
+H . % ,...................................................................................................66
% + .........................................................................................................	66
? 13. B #. " ......................................	67
" % .................................................................................................................................	67
13.1. +$+H / C..............................................................................	67

4

13.2. % / C .................................................................................	68
13.3. C % +'-, +'-, ..................................................................69
13.4. # .G..................................................................................................................	71
+H . % ,...................................................................................................71
% + .........................................................................................................	72
# : III. A# D...........................................................................................................	73
? 14. " : ! ? # " ? A# D " ...................................	73
" % .................................................................................................................................	73
14.1. .-,..............................................................................................73
14.2. % G % * + , F / ..........................................................................	76
+H . % ,...................................................................................................79
% + .........................................................................................................	79
? 15. " : ! ? A# D ". :" @ A# D .......................................	80
" % .................................................................................................................................	80
15.1. .-, (% * ; ,) ..................................................................	80
15.2. : ; (*.- ) F / ..................................................................................	83
+H . % ,...................................................................................................83
% + .........................................................................................................	84
? 16. #-@ # ) A# D................	85
" % .................................................................................................................................	85
16.1. % C * F /$ ...........................................................................................	85
16.2. "+ G . ( % C E * F /$ .....................................................	87
+H . % ,...................................................................................................88
% + .........................................................................................................	88
? 17. # # A# D ". # " ? " ............	89
" % .................................................................................................................................	89
17.1. ! +H ( F /.......................................................................	89
17.2. * + , F / %$', ..............................................................	92
+H . % ,...................................................................................................93
% + .........................................................................................................	93
# : IV. ! ".........................................................................	94
? 18. D " ? B # A " ....................	94
" % .................................................................................................................................	94
18.1. G E $ ...........................................................................................	94
18.2. % G . * , $ ...............................................................................	95
18.3. # .K , / C E ....................................................................................	97
+H . % ,...................................................................................................97
% + .........................................................................................................	97
? 19. # # ". # " # ?98
" % .................................................................................................................................	98
19.1. ( E ( $ .....................................................................	98
19.2. ( $ , S ' H ,..............................................................99
19.3. , $ + ................................................................	99
19.4. % +- $* +H $ – - $ .....................................................	102
+H . % ,.................................................................................................102
% + .......................................................................................................	103
? 20. : ) " " .................................................................	104
" % ...............................................................................................................................	104
20.1. $% . C , $ ........................................................................................	104
20.2. :'N* , $ . ( * ' / C N'.....................................................	108
+H . % ,.................................................................................................109

5

% + .......................................................................................................	109
? 21. # @ " "............................................................................	110
" % ...............................................................................................................................	110
21.1. ; $ ................................................................................................	110
21.2. + $ $; .........................................................................	111
+H . % ,.................................................................................................112
% + .......................................................................................................	112
# : V. B " A B# ....................................................................................	113
? 22. B " D )....................................................................................	113
" % ...............................................................................................................................	113
22.1. F- / C ....................................................................................................	113
22.2. B + / C......................................................................................................	113
22.3. F- /$+..................................................................................................	115
+H . % ,.................................................................................................115
% + .......................................................................................................	115
? 23. : " ? B " D. # " ? D # ....	116
" % ...............................................................................................................................	116
23.1. % G . * , G + ( / C E ................................................................	116
23.2. * , /$+ G + +F G * * + /$ .......................	119
+H . % ,.................................................................................................119
% + .......................................................................................................	119
? 24. B " A B#. # U ?. ".....................	120
" % ...............................................................................................................................	120
24.1. B + +F G.....................................................................................................	120
x1 0=0; x1 0=x1; x1 1=x1; x1 1=1; 0=1; 1=0; ..........................................	120
24.2. % S , . % /$+................................................................................	121
24.3. * E H /$+ G + +F G ..............................................................	122
24.4. B + +F G $; .....................................................................................	123
+H . % ,.................................................................................................124
% + .......................................................................................................	124
? 25. A B# @ A. D. A ! ..125
" % ...............................................................................................................................	125
25.1. +F G @ F + .............................................................................................	125
25.2. % G + ( / C E........................................................................................	126
25.3. D C +H %.....................................................................................	127
25.4. F- (%$+H) ($ ...........................................................................	128
25.5. - . *- . + F-( ($........................................................	129
+H . % ,.................................................................................................129
% + .......................................................................................................	130
? 26. A# D ! B ! : ? .....................................	131
" % ...............................................................................................................................	131
26.1. A /-E $* $ $. C G + ( / C E..............................................	131
26.2. G+-E $* $ $. C.............................................................................	132
+H . % ,.................................................................................................134
% + .......................................................................................................	134
? 27. ! : ?. B : " ..........................	135
" % ...............................................................................................................................	135
27.1. +- $* $ $. C ..........................................................................	135
27.2. * E.......................................................................................................	137
27.3. +F G-E $* * ; , $ $+H F % , (+F$
).....................................................................................................................................	138

6

+H . % , .................................................................................................139
% + .......................................................................................................		139
? 28. ! : ? . " ................		140
" % ...............................................................................................................................		140
28.1. * E - + .................................................................................		140
28.2. $ . C , - . - ( / C E ....................................................		141
+H . % , .................................................................................................143
% + .......................................................................................................		143
? 29. # ! D # ...............................................................................		144
" % ...............................................................................................................................		144
29.1 . - , .............................................................................................144
29.2 +H % * + , $ - E / $ ............................................		145
29.3. % S , D . $ - ' / $ ' : H F .............................		146
+H . % , .................................................................................................148
% + .......................................................................................................		148
? 30. A # B " #" " .......		149
" % ...............................................................................................................................		149
30.1. D $ +' , +F $ % G * $ $ +H ( + *+, -
......................................................................................................................................................		149
30.2. +F $ *+, D .............................................................................................		152
30.3. * B+ E .......................................................................................................		152
+H . % , .................................................................................................155
% + .......................................................................................................		155
? 31. : ? B "	D..............................	156
" % ...............................................................................................................................		156
31.1. . - , ............................................................................................156
32.2. " , $ G + ( / C E *+, . ..........................		157
31.3 - E $ * $ $ . C $ G + ( / C E B - +, H F ...		158
31.4. E $ * % S , $ D . $ - ' / $ ' ......		159
+H . % , .................................................................................................160
% + .......................................................................................................		160
? 32. #" D # ) # " # ? ......................		161
" % ...............................................................................................................................		161
32.1. +H % * + , .................................................................		161
32.2. % C * +H $ % * + , $ ..................................		162
+H . % , .................................................................................................168
% + .......................................................................................................		168
? 33. " # ? #"	# ...........................	169
" % ...............................................................................................................................		169
33.1. " , % C E +H F % * + , ..............................169
33.2. - + * . ' ' $ +H / $ ..........................		174
+H . % , .................................................................................................175
% + .......................................................................................................		176
? 34. B " # " ? ? # " ..................................................		177
" % ...............................................................................................................................		177
34.1 B + , , ....................................................................................................177
34.2. B + .................................................................................................		178
34.3. % +H $ E , H ...........................................................		180
+H . % , .................................................................................................181
% + .......................................................................................................		181
? 35. B " # : ? , D # .........................		182

7

" % ...............................................................................................................................	182
35.1. "+ G + E . C .............................................................................	182
35.2. * . ( *; , G + E . C .............................................................	183
35.3. * E G + . C,....................................................................................185
35.4. B + % ( * E * / C +..........................................................................	186
+H % , ....................................................................................................188
% + .......................................................................................................	189
? 36. A # "...........................................................................	190
" % ...............................................................................................................................	190
36.1. " + + , % *....................................................................................	190
36.2. F % * ...............................................................................................	190
36.3. + . , .....................................................................	191
+H . % ,.................................................................................................192
% + .......................................................................................................	193
# # ................................................................................................	194

8

"

. A + 4 , A 8

+ 5 4 '+ 6 9, : 5

4. 8 5 : 6 , 6

9, 8 4 8, 4 , A : + +

4 5 6 8 4 . B

, : 8 + 8.

< « »

4 4 , A : 5

'+ 6 -.(. -86 5 8 , A

5 6 8, 6 6

6 6 , : -.(. 2 :

8 8 5C 4 8 4 :

6 6 5, 9 4C 4

5.

2 + 9 4 8 6 , 8, 4, 6 8 4 8. ?

' 5, 8 5C 5 6

6 6. , + 86 4 C , A

5 5 4, 9 + 5 , , 5

+. 9 4 5 86 , A + 5

, , . . , A 5,

+ , 5 5 8 4, D 9

.

( 4 4 5 : . (

: 5 4 , A C 9 6 [1-6] - 1; [2, 3] - 2, [1, 2, 3, 6, 10] – 3, [1, 2, 5, 6, 7, 12] – 4, [1, 2, 4, 6-9] – 5.

2 4 + 5 C 9: 1 - [1-3, 5] - , [4-6, 12]- ; 2 - [3] - , [1] - ; 3 - [1, 2, 10]- , [11] – ; 4 - [2, 7, 12]- , [11] – . ;

5 - [1, 9] - , [8, 14] – . 3 5C (

8 4) 9 C 9 6 [20-23].

9

# : 1. # ? @ A B# )!

? 1. " ? ? # ) @

" %

.

’ ", $ % & ' "

% ( & &. ) & ' " "

& ".

' & & :

1.1.+ &

1.2.+ & . - . .

1.3.0 & ". 1 %

1.4.3 ' ". 4 & " '

1.1.% , , . * , $;

. 4 & $ ' %'& (, & ( & & & %' ( ' ( $(), 8 $' ( "

.

4 &. 9={ 1,2, ,b} - , >={ ,b,c,b} - .

< 4 5 9 - 4 9 {...}, 6 + 5

9. 9 + 5 M, 14, > , ...,

9 + 5 5 a, b4, ... .

< m M : «m A» «m '

A». < m M : m M.

< *1 *2 : « A1

A2», «M1 &$ A2, A2 – &$ A1», «M1 ' ' A2».

< *1 *2 - *1 *2.

< *1=*2 : «M1 M2 *2 *1» «9 *1 *2

( )».

< *1 *2 - *1=*2.

< *1 *2 + «M1 M2 *1 *2» «M1 : $

9 + 9 *2». E 9 5 - 9 *2

9 - : 9, A 5 - 9 : *.

* 9 9, A 4 9 : 9 4 U ( 6 - 5).

. A, & A, '

$ &, $- , % A '

(A) >(A).

4 &. A={1,2,3}, P(M)={ , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

< |*| : 9 *, |0(*)|= 2|*|. < 9 +: 5 5 8:

1. . :4 ( 6 , A 6 5 9.

4 &. 9={ 1, 2, 3 }, B={1, 2, b, c}, C={ }1 3

2.< ( , A : 9

, A C 9.

4 &. N={n|n n>0}, A={m M|m=n2 n }

3. &, 8 9 :, 9, A 8 4 + 5

: .

10