Martynyuk_A_N_Diskretnaya_matematika
.pdf
8.2. ,*
>. 1 & ` @9 & " 9, 8 & '
P , , & `
& (49).
* 9 M 5 C 4 @ : 5
&$. T a, b , A a4b a,b, + 5
9, 9 9 5 6 .
- 9, 9 ,
: 5 " &$ $ $ . ( 5 :
" " " &. ? , C 4
5 , ’ , C 4
: 5 ".
1 C <,< 9 M : C <<< , A , b a<b 5 , ,b b. 1 C <<< 9 M : 5 C & :
, 5 , . 1 C <<<
9 M : + 4 C <,< 9
<,<=<<< <<<=<,< \ . 2 4 9 5
& , ( , " & (5
’ ) &.
4 &. > & ` & <% & '< {1, 2, 3, 4, 5, 6, 7}
|
|
|
|
|
) |
|
. % 8.2. |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
1 |
|
|
|
|
|
|
|
2 |
1 |
1 |
|
|
|
|
|
|
3 |
1 |
|
1 |
|
|
|
|
|
4 |
1 |
1 |
|
1 |
|
|
|
|
5 |
1 |
|
|
|
1 |
|
|
|
6 |
1 |
1 |
1 |
|
|
1 |
|
|
7 |
1 |
|
|
|
|
|
1 |
|
%)
. 8.2. > & ` &
41
-6 0(M2) - 9 6 8 6 C 5, 6 9 M. -6 <,< - 8 C 9 0(M2) , A C 5 @,C 0(M2)
@,C 5 , @b : Cb, ,b , 8 6
4 @M CM : 5 + @ C . ? , 9 0(M2) :
+ A C <,< .
-6 ?(M2) (( 2) - 5 6 C 5 9 M. 1 5 <,< 9 0(M2) : 5
9 ?(M2), A 6 C
8 9 M, @,C :, A 8 M/@={Sa(@)/a } 8 5C 8, 9 8 M/C={Sa(C)/a }, 8 9 4 9 4 Sa(C) /C
: 8 R(Sa(C))={Sa-(@)|a- Sa(C)} /@. ( 5 8 M/@ 5
& %$ 8 M/C.
-6 F(M)=M* - 9 6 ( ) 9
(9) M 9 M C 4 (4) .
A. M/ ,E F(A) 2 E
/ , / 32 E, + /E/=/!/
bi – 2
E. 2 E, 1 / 1
9 ? 2 * bi
, 1 2 ci E. |
|
|
|
|
|||||||
4 &. 9={1, 2, 3}, 93 - & 3. |
|
|
|
|
|||||||
<1, |
2, |
3> |
, |
<1, |
2, |
3>; |
<1, |
2, |
3>,<1, |
3, |
3>; |
<1, 2, 3> < <2, 2, 3>; <1, 2, 3>>|< <2, 1, 3>.
A. 9 ? (?) 2
9 ? (?) 0 .
-6 F(A)=M* - 9 6 ( ) 9
(9) M 9 M C 4 4 . ( 5
9 P " & 9 F(A), 9
<Q<.
2 6 1, > F(A) 1 4 : > (1Q>)
5 , : 5 6 :) : , 1, ,min (/!/, /C/), A 6 1,j, : 5 bj=cj, bi<ci; 8)
6 , 1, ,m n (/!/, /C/), bi=ci, /!/</>/.
4 &. N Q ; %Q%, & .
42
8.3. + H
>. > & ` @ 9 ' & ` , 8 P .
> : '. 2 C
C 5 8' , 9, C
- C .
>. _ ' & 9- , 8 % &'- &
1 2, " , .
: 5 ', A : 9 + 4
C 4 . 0 9 5 , 9, : 9, A . + 5.
. > 9 / @ 2
, +/ ) 2 / , ,
{ 1, 2,..., n} 2 /
? 9 /.
. 9 9 8 :, ' 9 : C 5 5, 6 5, 5,
+ 5 4 . , A C
8 + 5 : 8 - 5
5 +: 9 9 / /. |
|
|
|
||||||||
4 &. |
9={ , |
, , |
, }. |
4 ' & `$ @, |
|||||||
8 $' ' %. |
|
) |
|
|
. % 8.3. |
||||||
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
1 |
|
2 |
|
3 |
4 |
5 |
|
|
|
1 |
|
1 |
|
1 |
|
|
1 |
|
|
|
|
2 |
|
1 |
|
1 |
|
1 |
1 |
1 |
|
|
|
3 |
|
|
|
1 |
|
1 |
|
1 |
|
|
|
4 |
|
1 |
|
1 |
|
|
1 |
1 |
|
|
|
5 |
|
|
|
1 |
|
1 |
1 |
1 |
|
%)
. 8.3. > & ` :
) {1, 2, 4}, {2, 3, 5}, {2, 4, 5} - ' , {1, 2}, {2, 4}, {2, 5}, {3, 5}, {4, 5} - '.
4 {{1, 2, 4}, {2, 3, 5}, {2, 4, 5}} & & & & `$
@={(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 1), (1, 4), (4, 1), (2, 3), (3, 2), (2, 4), (4, 2), (2, 5), (5, 2), (3, 5), (5, 3), (4, 5), (5, 4)}.
43
8.4. . % ,*
>. > & ` @ 9 ' & ` &, 8 P .
> : & & & &.
2 C C 5 4
8' , 9,
C 4 - C .
4 &. |
> & ` |
& ' |
|
|
( |
((, |
||||||
( ) & ` & |
) |
|
|
. % 8.4. |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|||
|
|
- |
|
0 |
|
1 |
2 |
|
3 |
|
4 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
- |
1 |
|
1 |
|
1 |
1 |
|
1 |
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
1 |
|
1 |
1 |
|
1 |
|
1 |
|
|
2 |
|
|
1 |
|
|
1 |
|
|
|
1 |
|
|
3 |
|
|
1 |
|
|
|
|
1 |
|
|
|
8) |
4 |
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. 8.4. > & ` &
+H . % ,
1.S & ` ?
2.S " ’ % & ` ?
3.Y P- $ 9/@9, & `$
@9?
4.Y & & % 9 P- 9/@
$ & & & & ` ?
5.S &?
6.o ? Y $ ?
7.Y %$ 9/@? Y & %$ % 9/C?
8.Y & P &?
9.Y $, % $,
?
10.Y , ' ?
11.S &?
12.0 ( & ` ' & '?
44
% +
+
1.E -.9. 0 & . – N4%.: 4, 2001. - N.42-47.
2._ 0., 1 " d. _'$ . – A.: E, 1990. - N.46-64.
3.d ` >.A., U " d.W., a8 W. . 9 %, b, .
–_.:E &, 1989. -N.50-56.
4.N " >.4. A " . – _.: .(, 1975. -
N.115-137.
5._` a.A. A b %. – A.: c-
&, 1987. - N.6366.
0 &
6.d % >.9. + b & " . – A.: >b `.`., 1986. -N.13-
20.
7.>.d. A b %. – _.: > 8 `., 1974. - N.26-
30.
8.1 P d., 1 .. N & %. – A.: A, 1976. - N.46-
54.
0 ( '
9.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.17-18.
45
? 9. : ?. D ). # )
" %
', ' ( P " ".
P & ` ' '
&$ & > ` . . ' P: &,
&, P P, 8 %$' % . ) & ", & P, P P P
", & " ".
' & & :
9.1.) & ` '
9.2.N ' P
9.3.+
9.1. :$, * K H
>. . R+ & ` R ' 4 (
( & ` ', 8 ' R &.
>. P ( ) R* & ` R
' 4 ( P ( & ( & ` ', 8 ' R
&.
> :
1.R*=E R+
2.R+={((, ) 2| F / * K , R N K+,( . ( }.
> , A R+ : C, R* -
. D A 9 M , |
|
C R 9 8 4 + & > ` |
: |
P : R*=R0 R (R°R) … (R°R°…° R),
: R+=R (R°R) … (R°R°…° R)
R0=E , / /=n, n -C 5 R.
>. E ( " 9 - , n :=( n, A, G) - & & '. 4 & 9-
9 ' $ 8 & & & :, 8 :((9-)n) .
A. M/ 0 - 2 2 <
, 1 2 * 9 3 3 - 1
:, < :-.$,$ - - :.
A. E / <= { ^| - ^ ^ -
:}, 1, 1 - ^ ^ - :, < ^.
5 :-5 : 5 6 6, A 8
9 M, 5 + 5 , + 5
9 M- : 9 + 5 + 9 M M- A 6
.
4 &. A= (9) :=(A2, A, G) - & & ', 8 & & 9- < 9 9- <, 9- < 9-\9<. N’ , 8
' & 9 & :.
4 &. 9=>2 :=(92, 9, {((((, ), ( , z)), (( , z)) | (, , z !}). 0 % &'-
& ` @ > ' & @+ - @ & :.
46
9.2. % C +H / C
9.2.1. *
>. 4 &$ 9 ' % 9 (% & & ' 9).
v 6 6 9 9 4 8.
-6 / /=n 6 nPn - 6 . nPn=n! 5 MN n, 9 9 M 9 n. 3 5- n
8 9 4 n, A : 8 : C 6 (5 5, 5 5 ’: 5).
-6 P - n, P 9 9 n P={(1, x1), (2,
x2),..., (n, xn)}, (x1, x2,..., xn}=Nn. |
|
|
|
|
|
|||
4 &. |
P1 |
1 |
2 |
3 |
4 |
5 |
6> |
|
R> |
5 |
6 |
3 |
1 |
4 |
2 |
R |
P1SP2 |
P2 |
5 |
6 |
3 |
1 |
4 |
2 |
R |
|
R> |
4 |
5 |
6 |
3 |
1 |
2T |
U |
|
-6 M={ 1, 2,..., n}.
>. 4 & @ ' ( $ &$), 8
@={(a1, a2), (a2, a3),..., (an-1, an), (an, a1)}.
q 5 9 9 n, A 8 5 (9) M : 9 5 n. -6 M 1 1 – 9. 0 C @ + 9 1 :
C:
C: x= V@(x), A x ; Wx, A x ,
5 C - 5 8 @ 6 6, 1 «C + 5
». - 9 5 8 .
4 &. P1 & ' & % , ' - (1, 5, 4), (2, 6), (3).
. 5 @ * 2 3
) /, ) / ) 9 +-
.
T 9 M, 4 @( ) : 5 ( P1 - <3< -
). D A / /=m, /!/=n,m, +’6 ’: 6
M 1 5 6 8 9 5 1 M +: n(m (
% '), n(m=n!/(n-m)! D A 5 1 M, 6
9 1 ( ' % ' n m) +: >nm=nPm/m(m= n!/m!(n-m)!
>nm=Cnn-m.
9.2.2. + *
>. 4 &$ 9 ' & % 9.
D A C: > - 5 C(n)=an, + 5 5
C, ( n) ( 1, 2,..., n,...). ( 5 n + 5 n- .
4 &. C: > C = {(1, "), (2, "), (3, "), (4, "), (5,
%"), (6, & % "), (7, P ")}.
9.2.3.D C +
-6 9 M, 1, > [1>>] - 9 1 >.
>. - f:A>[!>C] ' P , % & % &'-
f(a) - P - f(a):B>C, & % &'- b ! f(a)(b) C.
-86 , A 9 [!>>] 9 5 4 8 5-
C 9, 8 4 , A + 5 5
8 5.
47
4 &. E ( " P f:A>[!>C] ' &, P - f(a):B>C – % % & ( , ,...).
9.2.4. D C, S .G F ' H +F G- +
= + 5 P, 8 %$' % .
>. E ( " X Z - , @x @ – & & ` ( ( " f:X>Z -
& %, 8 & ` x1@xx2 & ` (f(x1))@ (f(x2)), % f & %, 8 % & ` @x & ` @ .
-C - .
4 &. E ( " X Z - , @x @ - & ` ( ( " f:X>Z - & %. E ( " & f:./@(>Z/@ , 8 f={([x][y])/y=f(x), x ., y Z}, & [x][y] - & & x y. S 8 f - P, x1@x2 , 8
f([x1])=f([x2]), f & %, 8 % '. 3 ' & ', 8 f:.>Z & & % f:./@.>Z/@Z.
9.3.% C
9.3.1.: F +H .-, % C E
2 + 5 5.
>. +$ & $ S ' P f: Sn>S, & n &
( : ) & ' /f(1)/,1; %) ' S.
Sn>S : n. D A n=1, & ( , &), A n=2, & (%, & &). s1, s2,…,si,…,sn 8 ( ) (s1, s2,…,si,…,sn) Sn + 5 &, + 5
. = C 6, , 4, : ,' .
4 &. 1$ $ & &, % & % & " ( D,
$ $ ' D. N- $ $ & &
" ` ( .
( 6 5 , 8
, 6 9 8: ) infix ( ) -
A : 5 9 ; 8) prefix ( ) - A : 5 ; ) postfix ( ) -
A : 5 .
4 &. a+b - infix ; +ab - prefix ;
ab+ - postfix
z prefix postfix 4 + 5 9 8 5
6 9 5, A 8 5 6 8 8.
4 &. |
a+bLc+(d+eL(f+g)) |
- infix; |
|
++aLbc+dLe+fg |
- prefix; |
||
abcL+defg+L++ |
- postfix |
||
) (((a+(bLc))+(d+(eL(f+g)))) |
- infix: |
||
48
. 9.1. r P P
%) ++aLbc+dLe+fg - prefix:
. 9.2. 4 P P
) abcL+defg+L++ - postfix:
. 9.3. 4 P P
-6 [ : 5 ( ), \ -
5 ( 9). |
|
||
9.3.2. / ) * |
|
||
1. |
a[b=b[a; |
a\b=b\a |
$H. |
2. |
a[(b[c)=(a[b)[c; |
a\(b\c)=(a\b)\c C H. |
|
3. |
[(b\c)=(a[b)\(a[c);a\(b[c)=(a\b)[(a\c) |
* G H. |
|
4. |
[ = ; |
\ = |
*$% H. |
5. |
? S *+, ( +$ N b E, S ) b\a=a (b[a=a), b – |
||
+ * C, (+ E +H); G) a\b=a (a[b=a), b – % * C, (% E +H); )
49
*- a\b=a (a[b=a) b\a=a (b[a=a), b – * , * C, (+H) % % C \ ([).
6.? S – * C, (+H) (\ = (([ = ), ( – + E G E +$ * ,
– % E G E +$ * (, , S (\ = (([ = ) \(= ( [(= ), ( – G +$ % * K ' * F * * F.
A. ; * \ ([) – / / ( ) ) 2
) (/) ) * \ ([). 4 * (/ *) / / . A. ; * \ ([) – ) ) – ) (/)
\ ([). , 1 2 + * /, + * / /
) * \ ([). |
|
|
|
|
|
|
|
|
|
4 &. |
={1, 2, 3, 4}; !={3, 4, 5}; |
N ={1, 3}; |
|
|
|
|
|||
!=!={1, 2, 3, 4, 5} |
|
|
|
|
|
!=!={3, 4} |
|||
– '; |
|
|
|
|
|
|
|
|
|
(!N)=(!) N={1, 2, 3 ,4, 5} (!N)=(!) N={3} – '; |
|
||||||||
(!C)=(!) ( C)={1, 2 |
,3, |
4} |
(!C)=(!) ( C)={1, 3, |
4} |
|||||
– & % '; |
|
|
|
|
|
|
|
|
|
= ={1, |
2, |
3, |
4} |
|
= ={1, |
|
2, |
3, |
4} |
– & '; |
|
|
|
|
|
|
|
|
|
= ={1, |
2, |
3, |
4} |
|
= ={1, |
|
2, |
3, |
4} |
– & " '; |
|
|
|
|
|
|
|
|
|
U= ={1, |
2, |
3, |
4} |
|
U = ={1, |
|
2, |
3, |
4} |
– & &; |
|
|
|
|
|
|
|
|
|
=U |
|
= , |
|
|
|
|
|
|
|
– % & `$ & & &. |
|
|
|
|
|
||||
+H . % ,
1.S $' P ?
2. |
3 ' & > ` ? |
3.S & 9- 9 ' $ 8 & & & :?
4.Y &$, ? S ?
5.Y & ' P ?
6.S P ' % % ?
7.S ' ?
8.Y &$, &$, n- $ ?
9.3 P, P P P "?
10.o % & ' P?
11.S $' ?
12.Y , , & &, % '?
13.Y % " ?
50