Джумадильдаев А.С. Элементы дискретной математики (часть 1)
Подождите немного. Документ загружается.
A = {1, 2},B = {a, b}. A × B; B × A; B × B.
A = {1, 2},B = {a, b, c},C = {5, 6}. A × B × C.
A = {0, 1},B = {x, y, z},C= {x, w}. (A ×B) ∩(A × C) B ∩C.
(A × B) ∩ (A × C)=A × (B ∩ C).
A = {x, y, z} B = {0, 1}
6 A × B 2
6
=64
A × B. A B
n a)n =1,b)n =2,c)n =3,d)n =4.
n
n
m (n, m)=(4, 3), (3, 3), (3, 4)
n
m (n, m)=(4, 3), (3, 3), (3, 4)
n
n
a)n =1; b)n =2; c)n =3
R, S
• R ∪ S
• R ∩ S
• R ⊕ S
• R \ S
• R ◦ S
R R
n
= R
n ∈ N.
R R
n
n ∈ N.
R R
n
n ∈ N.
R R
−1
R R =
R
−1
.
R R
2
A B
R
1
R
2
A B aR
1
b,
a b aR
2
b, a
b. R
1
∪ R
2
R
1
∩ R
2
R
1
⊕R
2
R
1
\ R
2
R
2
\ R
1
.
R S aRb a
b aSb a b R ◦ S S ◦R.
R
1
R
2
A
M
R
1
=
010
111
100
M
R
2
=
010
011
111
R
1
∪ R
2
R
1
∩ R
2
R
1
⊕ R
2
R
1
◦ R
1
R
2
◦ R
1
M
R
=
110
011
,M
S
=
010
101
. M
R∪S
,M
R∩S
,M
¯
R
,
M
¯
R∪
¯
S
,M
R∩S
.
M
R
=
110
011
,M
S
=
01
10
11
. M
R◦S
.
R = {(a, b)|a>b} Z.
R = {(a, b)|a = b}
Z
M
R
R n
R
∗
M
R
∗
= M
R
∨M
[2]
R
∨M
[3]
R
∨···∨M
[n]
R
.
A = {1, 2, 3, 4},B= {x, y, z} R A B
R = {(1,y), (1,z), (3,y), (4,x), (4,z)}.
R
•
•
•
•
A = {1, 2, 3, 4, 6} A R x y (x, y) ∈
R ⇔ x|y
• R
• R.
•
R
−1
. R
−1
A = {1, 2, 3}
R = {(1, 1), (1, 2), (1, 3), (3, 3)},S= {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)},
T = {(1, 1), (1, 2), (2, 2), (2, 3)}, ∅ =
,
A ×A =
.
A = {a, b, c}
R = {(a, a), (a, b), (b, c), (c, c)}.
R
Z x ≡ y(mod n) n|x −
y.
Z Z/ ≡
A = {(a, b)|a, b ∈ Z,b =0} R
(a, b)R(c, d), ad = bc. R
A/R
Q.
A = {1, 2, 3, 4, 5, 6}
R = {(1, 1), (1, 5), (2, 2), (2, 3), (2, 6), (3, 2), (3, 3), (3, 6),
(4, 4), (5, 1), (5, 5), (6, 2), (6, 3), (6, 6)}.
A/R.
P = {(x, y) ∈ R
2
|x = y
2
} Q = {(x, y) ∈ R
2
|x · y>0}
P ◦ Q, Q ◦ P, P ◦ P P
−1
.
R
1
◦ (R
2
◦ R
3
)=(R
1
◦ R
2
) ◦ R
3
,
R
1
◦ (R
2
∪R
3
)=(R
1
◦ R
2
) ∪ (R
1
◦ R
3
),
R
1
◦ (R
2
∩R
3
)=(R
1
◦ R
2
) ∩ (R
1
◦ R
3
),
(R
1
∪R
2
) ◦ R
3
=(R
1
◦ R
3
) ∪ (R
2
◦ R
3
),
(R
1
∩R
2
) ◦ R
3
=(R
1
◦ R
3
) ∩ (R
2
◦ R
3
),
R
1
,R
2
,R
3
⊆ A × A.
A = R[x] A
f(x) ◦ g(x)=f(x)
∂g(x)
∂x
.
x ◦ x
4
=4x
4
(a ◦ b) ◦ c − a ◦ (b ◦ c)=(b ◦ a) ◦ c − b ◦ (c ◦ a),
(a ◦ b) ◦ c =(a ◦ c) ◦ b,
a, b, c ∈ A,
A = R[x] A
f(x) ◦ g(x)=f(x)
x
0
g(x) dx.
x ◦ x
4
= x
6
/5.
(a ◦ b) ◦ c = a ◦ (b ◦ c + c ◦ b),
a, b, c ∈ A,
T
1
T
2
n
1
n
2
T
1
T
2
,
T
1
T
2
n
1
+ n
2
T
1
T
2
.
T
1
,T
2
,...,T
k−1
T
k
n
1
,n
2
,...,n
k−1
n
k
n
1
+ ···+ n
k
k A
1
,A
2
,...,A
k
A
i
∩ A
j
= ∅ i = j.
|A
1
∪···∪A
k
| = |A
1
| + ···+ |A
k
|.
T
i
A
i
i =1,...,k. n
i
T
i
.
n
1
+ ···+ n
k
|A
1
∪···∪A
k
| = |A
1
| + ···+ |A
k
|.
T
T
1
,T
2
T
1
T
2
. T
1
n
1
T
2
n
2
T n
1
n
2
T
k T
1
,T
2
,...,T
k
T
1
T
2
T
1
n
1
T
2
n
2
T
k
n
k
T n
1
n
2
···n
k
|A
1
× A
2
×···×A
k
| = |A
1
||A
2
|···|A
k
|
2 × 3=6
F(A, B)={f : A → B}
n m F(A, B).
m
n
.
n m
n>m
n+1 2n
a
1
,...,a
n+1
< 2n a
i
=2
k
i
q
i
, 1 ≤ i ≤ n +
1,
q
i
q
1
,...,q
n+1
.
2n
n,
q
i
= q
j
= q. a
i
=2
k
i
q, a
j
=2
k
j
q. k
i
<k
j
, a
j
a
i
.
k
i
>k
j
, a
i
a
j
.
n ∈ Z
+
n
2
+1
n +1
a
1
,...,a
k
2
+1
n
2
+1
i
k
a
k
d
k
a
k
.
i
k
≤ n, d
k
≤ n, 1 ≤ k ≤ n
2
+1.
n
2
(i
k
,d
k
).
(i
s
,d
s
)=(i
t
,d
t
), s<t.
a
s
<a
t
,
a
t
a
s
i
t
+1 a
s
. i
s
= i
t
,
a
s
.
a
s
>a
t
,
a
t
a
s
i
s
+1
a
s
. i
s
= i
t
,
a
s
.
A
3 > 5/2 A A. B,C,D
A. B,C,D
A B,C,D
11
100 x, y
0 < |
√
x −
√
y| < 1.
a
1
,...,a
11
0 100.
√
a
1
,...,
√
a
11
.
1 10.
√
x,
√
y, 0 < |
√
x −
√
y| < 1.
S ⊂ Z
+
, |S| =25. S
6 S = {1, 2,...,9}
10.
1 1/2
n
2
+1 n
2
n
2
n +1.
|∪
n
i=1
A
i
| =
n
s=1
(−1)
s+1
1≤i
1
<···<i
s
≤n
|A
i
1
∪···∪A
i
s
|.
n. n =1
n =2.
A
1
∪ A
2
=(A
1
\ A
2
) ∪ A
2
.
|A
1
\ A
2
| = |A
1
|−|A
1
∩A
2
|,
(A
1
\ A
2
) ∩ A
2
= ∅.
|A
1
∪ A
2
| = |A
1
| + |A
2
|−|A
1
∩ A
2
|.
n ≥ 2.
A = ∪
n
i=1
A
i
.
A ∩A
n+1
=(A
1
∩A
n+1
) ∪ (A
2
∩A
n+1
) ∪···∪(A
n
∪ A
n+1
).
(A
i
1
∩ A
n+1
) ∩···∩(A
i
s
∩ A
n+1
)=A
i
1
∩···∩A
i
s
∩ A
n+1
.
|A ∩ A
n+1
| =
n
s=1
(−1)
s+1
0<i
1
<···<i
s
≤n
|A
i
1
∩···∩A
i
s
∩A
n+1
|.
n =2.
|A ∪ A
n+1
| = |A| + |A
n+1
|−|A ∩ A
n+1
| =
s=1
(−1)
s+1
0<i
1
<···<i
s
≤n
|A
i
1
∩···∩A
i
s
| + |A
n+1
|−
n
s=1
(−1)
s+1
|A
i
1
∩···∩A
i
s
∩ A
n+1
| =
n+1
s=1
(−1)
s+1
0<i
1
<···<i
s
≤n+1
|A
i
1
∩···A
i
s
|.
A
1
,A
2
A
3
A
1
⊆ A
2
,
A
1
∪ A
2
= A
2
,A
1
∪ A
2
∪A
3
= A
2
∪A
3
.
|A
3
| =60, |A
1
∪A
3
| =50,
|A
1
∪ A
2
∪ A
3
| =
|A
1
|+ |A
2
|+ |A
3
|−|A
1
∪ A
2
|−|A
1
∪ A
3
|−|A
2
∪ A
3
| + |A
1
∪A
2
∪A
3
| =
|A
1
| + |A
3
|−|A
1
∪A
3
|.
|A
1
| = 100 − 60 + 50 = 90.
n ∈ N.
n n. φ(n). φ : N →
N
φ(n)=n
k
i=1
(1 −
1
p
i
),
n = p
α
1
1
···p
α
k
k
n
A
i
= {p
i
m | m ∈ N, 0 <p
i
m<n}.
|A
i
| = n/p
i
.
0 <i
1
< ... < i
s
≤ k A
i
1
∩···∩A
i
s
p
i
1
···p
i
s
,
|A
i
1
∩···∩A
i
s
| = n/p
i
1
···p
i
s
.
|A
1
∪···∪A
k
| =
s≥1
(−1)
s+1
n/p
i
1
···p
i
s
=
n(1 −
k
s=1
(1 − 1/p
s
)).
k.
k x
1
,...,x
k
,
1+
k
s=1
(−1)
s
1≤i
1
<···<i
s
≤k
x
i
1
···x
i
s
=
k
s=1
(1 − x
s
).
A
1
∪···∪A
k
p
i
1 ≤ i ≤ k
{m | 0 <m<n, (m, n)=1}
A
1
∪···∪A
k
,
{1, 2,...,n}.
φ(n)=n
k
s=1
(1 − 1/p
s
).
f ∈ Sym
n
f(i) = i, i ∈{1, 2,...,n}.
D(n)=n!(1 −
1
1!
+
1
2!
−
1
3!
+ ···+(−1)
n
1
n!
).