Martynyuk_A_N_Diskretnaya_matematika
.pdf
4 &. A={n2|n }, C ={8(1+14(2+32(3|(1, (2, (3 }.
<9 8 6 :, A
9 6 :.
2 9 + 5 4 4 - T 4 1 ( . 1.1.).
0. 1.1. T
1.2. % C * $;$ . D$+. ;
- 9 9 + 5 5 + 6
9.
+%'& 9 *1 *2 : 5 9 *1 2={m|m 1 m 2}. 4 9 *1 *2 : 5 9 *1 2={m|m 1 m 2}. * 9 *1 *2 + 5 &'$ , A *1 2= .
9 *1 *2 - 9 *1\*2={m|m 1 m 2}.
N$ $ |
9 |
*1 |
*2 : 5 9 |
*1-*2= {m|m 1\M2 m *2\*1}. |
|
|
|
D A *1 2, |
|
*2\*1 |
: 5 |
9 *1 9 *2. <, * = U\M - & A
& A. = C 9 - *.
4 &. ={1,2, 3, 4}; !={3, 4 5}; ) ={1, 3}; !={1, 2, 3 , 4, 5}; !={3, 4}; \) ={2, 4}; \!={1, 2}; !\ ={5}; #!={1,2,5}.
. - '
: 1) = ; 2) ; 3) $ ; 4) = ; 5) \ \
< 6 9 4 + , 9, 8
4 + P |
: 5 . |
|
|||
2 9 (9): |
|||||
1. |
!=!; |
|
|
!=!; |
$H |
2. |
(!:)=(!) :; |
|
(!:)=(!) C; |
C H |
|
3. |
(!C)=(!) ( C); |
(!C)=(!) ( C); |
|
||
* G H |
|
|
|
|
|
4. |
= ; |
|
U=U; |
|
|
= ; |
|
U= ; |
|
|
|
=U; |
|
U= ; |
|
+ F CH |
|
5. |
=U; |
|
= ; |
* % , |
|
6. |
= ; |
|
= ; |
*$% H |
|
7. |
(!)= ; |
|
|
(!)= ; |
% F+ , |
8. |
(!)=!; |
|
|
(!)=!; |
|
(A C) (B C)=(A C) (B C) (A B); |
|
|
|||
(A C) (B C)=(A C) (B C) (A B) |
B+ E-CH F |
||||
9. |
(!) (!)=!; |
|
|
(!) (!)=B |
+ ' , |
10. (!)=!; |
|
|
(!)=!; |
* F |
|
11. ? S !=U != A=! |
|
|
|||
11
12. |
= ; |
|
+' H |
13. |
A\B=! |
|
|
14. |
#!=!#; |
|
$H |
15. |
#(!#C)=(#!)#C; |
|
C H |
16. |
#=#= ; |
#U=U# = ; |
+ F CH |
17.A B, , S +H , S !=B A!=A !=
18.A=B, , S +H , S A#B=.
1.3.* , ; E. B + +F G $;
2 9 : 5 ' " &, 4
( ) 6 9. 9 5 : 5
9 5 4 “A 0, Q”, : 5 “P'Q” A + 5
“ ( : Q”. 9, A : 5 9 5 0, 01, 02, 03, ..., 0n, Q , A 0 : 01, 01 : 02,… 0n : Q, : , A “ 0 : Q”, 8 ('Q.
4 &. D= (!N) = (!) ( N)=E
) 0 &, 8 D*. S 8 d D, d d (!C), , (d d!), (d
d C). U ', 8 d! d C), % d (!) (A C), 8 '
d E. .%, D E.
%) 0 &, 8 W D. S 8 E ((!) ( N)), !)
C. U ', 8 (!C) % D. .%, W D. +, D=W.
2 9 9 5 8 C 9.
(!)= ; (!) = ( U) (!) = (U!) =
2 9 9 *, 8 ((*) " 8 & " , ,\,-, , 8
6 *1, *2!( ) 9, 9 5 *1 2,1 2, 1\ 2, 2\ 1,, 1- 2, 1, 2 : 8 1(*).
3 !(*) (8) 5 ++ 5 (% )
% . 9 9 M’ 8 1(*) (8 6)
, 5 9, A : 9 9 9 M’, 9, A
5 9 9 9 M’. ? , M’ (8)
9 : 5 (8 +) 4 8 +.
1.4. . F +H , % C E. * E H
< 8':, .
5 6 9 9 5 8 8 6 9.
1.1 2 …… n= { |1, , n}={m| N , * 1, ,n, , S m }.
2.1 2 …… n= { |1, , n}={m| *+, ; F ., * 1, ,n, m }.
3.1#2#…… #n=#{ |1 , , n }={m| N N* , * 1, ,n, , S m }.
B 4 5 ++ 5 , 9 *
' 9 * 8 1:
{ | * 5 : 1}.
4 &. { | !( ) 0= } # ( &'( ( .
< 5 { | } : 5 . M 4 - -- -- --#--.
. C 9 & " ( (& ' () C 5,
6 6 5 + C “ ” “ ” “ ” “ ”, 9 U U . 1 , , U + 5 & " (& ').
12
( ) *: ( +-* ( , . /)
0 / / * , 1 2 3
(3, . / 3).
? 9 9, 11 ++ 5 5 + 5
& ". . C +: 5 “\”, #, 9 9, A
+ + 5 “ ” ”$”, 6 5 6 9 5 + 5
“$” “ ”.
0 9 4 8 9 9 A + 4
4 4 + ( ', 8 5 6
(9) 9.
+H . % ,
1.Y , P- , ?
2.S % & $'?
3.S &$' & ?
4.S ' & & ?
5.S & " & $'?
6.S % & & " $'?
7.0 ( " ' ?
8.3 & "?
% +:
+
1.E -.9. 0 & . – N4%.: 4, 2001.- N.19-26.
2._` a.A. A b %. – A.: c-
&, 1987. - N.24-44.
0 &
3.N " >.4. A " . – _.: .(, 1975. -
N.86-97.
4.d % >.9. + b & " . – A.: >b ` ` , 1986 -
N.6-10.
0 ( '
5.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.4-6.
13
? 2. # " ? ?. # ? # :B ". @
" %
` . ’
', 8 ' P & &, 8 $' $,
% ' , . ) & % ’ ', ' % , % ,
& ' ( .
' & & :
2.2.4 %
2.3.4 ' . ) ' .
2.1.# , ,
M 4 8 9 9 4 : , A 5
9 9 , A & $' $. .8
, 6 6 : ’ . 0’ 5
:+ 8 + 9 + ] : 5 6 9 6 6:
1.1 9 18 5 5 + 4
, A +: 5 (.
2.5 4 (M X) (N X)= * N
9, A 5 `.
3.? A 8': 9 9 5, A 9 : 6 9
9 :, .2 9 + 6 5 *.=
.= .
4.1 9 17 5 .3 + 5 5 ,
... < 5 ’ - , ’ - 8 5-
9 ` , A ..
4 &. . N=D: 1. (.C)#D= .
2. |
(.C) D) ((X C) D)=... |
|
=( D.) ((C#D).)= . |
3. |
D.= |
|
(C#D).= . |
4. 3 (C#D) D C D; ’ (C#D).D. |
|
|
|
2.2. , .G
>. 4 ' A ' "
( &, %'& ( &$ A:
={ |1 , ,/ /, , , = }
>. %$ ' A ' R "
( ( &, %'& ( &$ A:
R={A |1 , , / /, , , = , = }
. 9 9 *, A 6 5 0 (8 R), 8 *1, *2, *3,..., *| |, + 5 % 0 (8 R) + 5
4 9: 0={{a, c}, {b, d, e}}, – 8 4 6 9. 0 8 9 : 5 $, A 9 -
9, 8 : 5 $, A : 5 : 4 , A +:
6 9. T 8 9 + 5 ', C, A
+ 5, - '.
4 &. A={a, b, c, d, e, f}
P={{a, b, c,}, {b, d, e, f}, {e, f, a}} R1={{a, b}}, {c}, {d, e, f}}
14
R2={{a}, {b}, {c}, {d}, {e}, {f}} R4={a, b, c, d, e, f}
2.3. ; H $;. :-+ +H $;
* 9 8 + 5 . , A ,
6 6 9.
. 9 ' & & &. T 9 *1 *2 6 5 & " & &, A 9
9 *1 : 9 *2 .
? 9 + 5 ( ). 4 &. A N N2.
* 9, 9 9 5 6 N, + 5 . ( 9 9 9 . * 9 6,
5 6 , 9 .
. 4+'2 0 / 0 /
2 / 3 3.
= + 5 9, 6 9 6.
5. 6 * / / (0,1) / 0
/.
( 9, 9 6 6 (0,1), : 5
'$ ( $ ).
4 &. A ' (, & ( .
. 6 B(6) 0 / 0 6 2
3 .
-6 F(M) - 9 6 M. 3 5- 9
L F(A) : 5 $ & P.
4 &. A ( & P $
.
_& ' 0 9 * - D 8':, A : 9 5
9 * ( 4 9). ( 9 *
5 0*=| | 9 9 4 : 5 , A : 5 9 + 9. 2 6
9 5 + 5 P.
2 5 6 6 9 9 C:
1.0 1=0 2.
2.0*1<0 2.
3.0*1>0 2.
4 &. 1={1, 2, 3}, 2={a, b, c}, \ 1\=\ 2\. 3={1, 2, 3, 4}, 4={a, b, c},
\ 3\>\ 4\.
. 6 9 4 9 :
1.* 9 *1 *2 9, 8 0*1=0*2
2.* 9 *1 *2 9, 6, *1, 9
9 C 4 - 0*1=0*2’ *2’ 2. ( 5 9 5 9 *1 C
9 9 *2, 0*1<0 2.
3. * 9 *1 ( 9) 9 9 *2 ,
, 9 *2 ( 9) 9 9 *1. 1
5 C 4.
5-9 *. : 1 61 / ( )
* 62 62 / ( )
* 61, 61 62 / ( ).
15
4. * 9 *1 (9) 9 9 *2
9 *2 (9) 9 9 *1, 8 *1 *2 - . B 9 9 6 5 6
&.
4 &. 1={m M\m N & m – & ' }, 2=N, c},
01=02, 3=(0, 2), 4=(0, 1), 03>04.
; /. : 1 / /3 6$ 1$ 2, 6 62 – /
( ), 6 61 / ( ).
4 &. =(0, 1), 1=(0, 1,5), 2=(0, 2), 0=02, A2$ 1$ , 0=02=01.
; /. : 1 613 2, 0614062.
; /. : 1 6 - / ) , 6<00, 00- /
/ / / N (+-0 / 0 ), / .- /.
. > * * 6 / /
.
. ( (6) +-0 0
6 + / 9 0 , + 0 (6)>06.
4 &. 1={0, 1}, 2=B(M)={{(0, 1}, {0}, {1}, }, 01<02.
; /. ; 2 *+ / 9 0 , /
/ 2 / ? /. 5 /
1.Y ? S ' ’ '?
2.S %$?
3.S % ' % ' %?
4.3 ( ( ?
5.o (?
6.S $$' ?
7.o "% '` , & &?
% +
+
1.E -.9. 0 & . – N4%.: 4, 2001. - N.23, 24.
2._` a.A. A b %. – A.: c &, 1987. - N.28-34.
3.N " >.4. A " . – _.: .(, 1975. -
N.89-91.
0 &
4.d ` >.A., U " d.W., a8 W. . 9 %, b, .
–_.:E. &, 1989. - N.22-35.
0 ( '
5. A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.6-7.
16
? 3. #? " @. A# D
" %
& (
P. & ( P, & ( ) & %, & , , , . ) &
" P ' P, (
".
' & & & :
3.1.3 &
3.2.d P
3.1.% ,* $;
( 9 9 , A 9
5 |
|
5 |
|
|
1 |
|
n, |
|
n - 9 5 9. ? 8 . |
|
|
|
|
||||
>. |
3 &$ $ |
|
' |
& ' |
||||
, " " ,
$' " , - n - " & 4 &. 9=<1, 2, 3>; B=<2, 1, 2>; C=(a, d, d)
< 4 5 9 h 6 <...>, 4 6 (...) 9,
6 + 5 4 9. 9,
9, + 5 5 M0, 14, >j, ..., 9
+ 5 5 a, b4, cj, ... .
9 9 + 5 , A 6 8 4 + 5 6 5 4
6 9 h M=1, C 9 h M 1.
9 9 5 8 9, 9, C 9. l
9 - n- ( , ,...).
>. 4 & & % 9 > '
9(>, 8 & ' ( & ( , ` " ( '
9, & " ' >.
M×1={<a, b> A×1| M b B}
4 &. 9={ , b}; !={1, 2}; ×>={< , 1>, < ,2>, <b, 1>,<b,2>}.
, A A / /=n, /!/=m, /61/=n5m.
>. 4 & & % 91, 92, ..., 9n '
91×92×...×9n, ( n- , ` " ( ' 91, & "
' 92, ..., n- ' 9n:
×M =M1×M2× ... ×Mn={< 1, 2, ..., n> A1×M2×...×Mn| a1 A1, a2 2, ..., an n}
>. 4 " & " & % 91×92× ... ×9n (
( 91=92= ... =9n=A ' n- & 9
' 9n:
Mn=A×M× ... ×M = {<a1, a2, ..., an> An|a1, a2,..., an A}
. n=0 n=1 + 9 : 5 M0={ } M1=M. 1 9 + 9 +
8 M×M : 9 6M={< , >| M}, & $, 8 : 5
9 EA.
2 9 9 9 9 : 5
.
>. 4$ 9 -$ ' ' -
9, 8 ' 9.
. 5 5 6 + .
17
4 &. 9=<1, 2, 3, 3, 4>; 29=2; 49=3; 1,49=<1, 3>.
>. 4$ A & n '
" ( " A
4 &. A={<1, 2, 2, 3>, < , b, c, d>, <a, 2, 4, c>}, 1A={1, }; 13A={<1, 2>, < ,
>, < , 4>}
. 8 5 + 5 :
1.×" "×
2.×("× ) ( ×") × ×"×
3.( ")× =( × ) ("× )
4.( ")× =( × ) ("× )
5.( \")× =( × )\("× )
6.× × ... × = n.
7.l× $ l+m.
8.l× $ $× l.
9.× = × = .
3.2. A /
>. A ' P, 8 " & "$
& A.
={ (| =< , b> , b A}
4 &. ={< , b>, <1, c>, <2, 3>}
D A * - 5 9, *2 - 4, 8 5- 9 9 *2 9
: 4.
>. A " P ` ' ' % $
P , " P & ' ' % $
' P.
D A ` 8 5 , Y 8 5 5,
4 5 A ( . 3.1.). D A 4 0= , 10= 20= .
0. 3.1. q 4 A
D A 4 + : 9 +, 4 9 5
, A 9, 8 , , \, , #.
>. 0 " < , d> ' $ & " <a, b>, 8
&$ b, d &$ a.
= =< , b> : 5 -1.
. ( -1)-1 +: ( -1)-1= .
>. r$ P , 8 ' -1, '
" (
-1={q -1|q=p-1 (}
4 &. ={<1, 2 >, < , b>}, P-1={<2, 1>, <b, a>}
. 4 0 1(-1= 20 2(-1= 10.
18
>. d P ' , 8 & $ $
' $( ' -1
4 &. ={<a, b>, <b, a>, <c, c>}
2 8 5- 9 * 9 *2 - 4, 8 5-4 4 0 0(-1 ( (-1 - 4.
>. d P R=P°Q ' $ P Q, 8 & " <(,> ' R & ' &, " z, 8 & " <(, z> '
& " <z, > ' Q:
R=P°Q={<(, > R| z ", 8 <(, z>( <z, >Q}
4 &. ={< , a>, <a, c>, <a, b>, <b, b>, <c, b>} Q={<a, b>, <a, c>, <c, >}
R=P° Q={<a, b>, <a, c>}
4 0 Q 9 , 2P1 1P2 = .
>. 0 & % 1 2 ' P
1× 2={<<a1, a2>, <b1, b2>>|< , b >( , =1,2}
>. d P ' P ', 8 '
& ` & ; P ' ’ , 8 ' & & ` .
4 &. |
(1={<a, b>, <a, >} |
P ' " |
|
(2={<a, c>, <b, c>} |
’" |
||
q *2 5 9 * : 5 ’:,
5 6 4 5, ’: 6 4 ’:,
5 5 4 ’:, ’: - 5.
4 + 5 5 :
1. |
#1°(2 (2°(1 |
$H |
2. |
(1°((2°(3)=((1°(2)°(3 |
C H |
3. |
(° = °(= |
+ F CH |
4. (#1°(2)-1=(2-1°(1-1
5 /
1.Y & '?
2.S & & % ?
3.S ' %?
4.S $' & & ?
5.Y P?
6.S & P?
7.S $' P & P?
19
% +
+
1.E -.9. 0 & . – N4%.: 4, 2001. - N.33, 38.
2._` a.A. A b %. – A.: c &, 1987. - N.44-51.
3.N " >.4. A " . – _.: .(, 1975. -
N.97-115.
0 &
4.d ` >.A., U " d.W., a8 W. . 9 %, b, .
–_.:E. &, 1989. - N.35-44.
0 ( '
5. A & &r & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.7-10.
20