Джумадильдаев А.С. Элементы дискретной математики (часть 1)
Подождите немного. Документ загружается.
∅,A = {1},B = {1, 3},C = {1, 5, 9},D = {1, 2, 3, 4, 5},E =
{1, 3, 5, 7, 9},U = {1, 2,...,9}.
⊆ ⊆
∅,A; A, B; B,C; B,E; C, D; C, E; D, E; D,U
A ∪ B = A ∪ C B = C.
U = N,A= {1, 2, 3, 4},B = {3, 4, 5, 6, 7},C = {6, 7, 8, 9} E
•
¯
A,
¯
B,
¯
C
• A \ B, B \ C, C \ E,
• A ∪ B, B ∩ C, A ∩ B,
• A ⊕ B, A ⊕ C, B ⊕ C.
•{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
•{2, 4, 6, 8, 10}
•{1, 4, 9, 16, 25,...}
•{2, 3, 5, 7, 11, 13, 17, 19, 23,...}
•{−1, 1}
-
6
r
rr
r
@
@
@
@
r
rr
r
@
@
@
@
@
@
@
@
@
@
x
y
12
•{x ∈ Z :2x
2
− 3x +1=0}
•{x ∈ R :2x
2
− 3x +1=0}
•{x ∈ R :(x − 1)(x
3
+1)=0}
•{x ∈ C :(x − 1)(x
3
+1)=0}
nZ = {na : a ∈ Z} n
2Z, 3Z, 5Z, 6Z 0
2.
3Z ∪ 12Z 3Z ∩ 2Z, 3Z ∩
12Z, 12Z ∩15Z
{1, 2, 3, 4}
(A ∪ B) ∩ (A ∪
¯
B)=A
(A ∪ B) \ (A ∩ B)=(A \ B) ∪ (B \ A).
A⊕B
A = {a, b, c, d}.
a
A = {1, 2,...,9}
A
• [{1, 3, 5}, {2, 6}, {4, 8, 9}]
• [{1, 3, 5}, {2, 4, 6, 8}, {5, 7, 9}]
• [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}]
A
1
,A
2
,...,A
n
{(a
1
,a
2
,...,a
n
) | a
1
∈ A
2
,a
2
∈
A
2
,...,a
n
∈ A
n
} A
1
× A
2
×···A
n
n
i=1
A
i
i
A
i
.
A
1
= {x, y},A
2
= {p, q, r},A
3
= {1, 2}.
A
1
×A
2
×A
3
= {(x, p, 1), (x, p, 2), (x, q, 1), (x, q, 2),
(x, r, 1), (x, r, 2), (y, p, 1), (y, p, 2), (y,q,1), (y, q, 2), (y, r,1), (y, r, 2)}.
A B
R ⊂ A × B (a, b) ∈ R aRb. (a, b) ∈ R
a Rb
R = A ×A
R = ∅⊂A × A
A = { } B = { }.
R A B aRb, b a
R
R = { }.
R xRy, x
2
+ y
2
=
25.
R 5
&%
'$
x5
y
-
6
R A B
Dom(R)={a | (a, b) ∈ R, b ∈ B}.
Im(R)={b | (a, b) ∈ R, a ∈ A}.
• R = {(a, b), (a, c), (b, d)}
•
(λ
i,j
),λ
i,j
= {
1,a
i
Ra
j
0,
• aRb b a
• xRy, y = x/2.
-
6
R ⊆ A ×A
• R aRa, a ∈ A
• R a Ra a ∈ A
• R aRb ⇒ bRa
• R aRb, bRa ⇒ a = b
• R aRb, bRc ⇒ aRc
R
A = ∅ a ∈ A. (a, a) ∈∅
a ∈ A
R b ∈ A
R a
R(a)={b | (a, b) ∈ R}.
R(a) ∪ R(b) = ∅⇒R(a)=R(b),
A = ∪
a∈A
R(a).
R(a
1
),R(a
2
),...,
• R(a
1
),R(a
2
),...,
• A = ∪
i≥1
R(a
i
).
b ∈ A R(a), b ∈ R(a), (a, b) ∈
R.
R ρ(A)=
{R(a
1
),R(a
2
),...}
ρ(A)
A/R.
A = Z. (a, b) ∈ R a − b
n a ≡ b(mod n). n
R(0) = {nk | k ∈ Z},
R(1) = {1+nk | k ∈ Z},
R(n − 1) = {n − 1+nk | k ∈ Z}.
n
Z/nZ.
A A
A
i
,i ∈ I I
• A = ∪
i∈I
A
i
• A
i
∪A
j
= ∅ i = j.
• A
i
= ∅ i ∈ I.
{A
i
,i ∈ I} A
R = {(a, b) |∃i ∈ I a, b ∈ A
i
}.
R ⊆ A × A
{R(a
1
),R(a
2
),...} A
A = {1, 2, 3, 4, 5, 6}. A = A
1
∪ A
2
∪ A
3
A
1
= {1, 3},A
2
= {2, 4, 6},A
3
= {5}.
R = {(1, 3), (3, 1), (2, 4), (4, 2), (2, 6), (6, 2), (4, 6), (6, 4),
(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
A = {a, b, c, d, e, f}
R = {(a, a), (b, b), (c, c), (d, d), (e, e), (f,f), (a, b), (b, a), (c, e), (e, c),
(a, f), (f,a), (b, f), (f,b)}
A = A
1
∪A
2
∪
A
3
, A
1
= {a, b, f},A
2
= {c, e},A
3
= {d}
A = {a, b, c}
R
1
= A × A,
R
2
= {(a, a), (b, b), (c, c), (a, b), (b, a)},
R
3
= {(a, a), (b, b), (c, c), (a, c), (c, a)},
R
4
= {(a, a), (b, b), (c, c), (b, c), (c, b)},
R
5
= {(a, a), (b, b), (c, c)}.
A = A
1
,A
1
= {a, b, c},
A = A
1
∪ A
2
,A
1
= {a, b},A
2
= {c},
A = A
1
∪ A
2
,A
1
= {a, c},A
2
= {b},
A = A
1
∪ A
2
,A
1
= {b, c},A
2
= {a},
A = A
1
∪A
2
∪ A
3
,A
1
= {a},A
2
= {b},A
3
= {c}.
A = N aRb, a b
A R
2
aRb,
a b
A
aRb
A aRb, a b
R
a ≺ b a|b
N.
(P (A), ⊆)
(A, ≤) x ∈ A
y ∈ A x ≤ y z ∈ A x<y<z.
(A, ≤) A
x y y x x y
P ({a, b, c})
{a, b, c}
{a, b}{a, c}{b, c}
∅
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
(N, ≺), a ≺ b ⇔ a|b
(Z, ≺) a ≺ b ⇔ a|b
−3 ≺ 3,
3 ≺−3,
−3 =3.
R A a, b ∈ A
aRb bRa.
(N,<) <
R
1
,R
2
⊆ A ×B
R
1
∪ R
2
,R
1
∩ R
2
,R
1
\ R
2
,R
1
⊕ R
2
⊆ A × B
R ⊆ A × B
R
−1
= {(b, a) | (a, b) ∈ R}.
R
1
◦ R
2
.
R
1
∈ A × B, R
2
⊆ B × C,
R
1
◦ R
2
⊆ A × C
R
1
◦ R
2
= {(a, b) |∃b ∈ B, (a, b) ∈ R
1
, (b, c) ∈ R
2
}.
R ⊆ A × A
R
1
= R, R
n
= R ◦ R
n−1
, n>1.
A R ∈⊆ A × A
(a, b) ∈ R, a b aR
2
b a a
R ⊆ A × A
R
ref
= R ∪{(a, a)|a ∈ A} ,
R
sym
= R ∪ R
−1
,
R
∗
= ∪
∞
i=1
R
i
.
A = R,R= {(a, b)|a<b} R
ref
= {(a, b)|a ≤ b}.
A = R,R= {(a, b)|a<b} R
sym
= {(a, b)|a = b}
R
∗
= {(a, b) |∃k ∈ N, (a, c
1
), (c
1
,c
2
),...,(c
k
,b) ∈ R}.
|A| = n, R
∗
= ∪
n
i=1
R
i
.
x
0
,x
1
,...,x
m
∈
A
(x
0
,x
1
), (x
1
,x
2
),...,(x
m−1
,x
m
) ∈ R, x
0
= a, x
m
= b.
a, b ∈ A m m ≤ n
a = b m<m a = b.
a = b m ≥ n +1
m x
1
,x
2
,...,x
m
∈{a
1
,...,a
n
}
x
i
= x
j
, 0 <i<j≤ m.
x
0
= a, x
1
,x
2
,...,x
i
,x
j+1
,...,x
m
= a ∈ A <m
(a, x
1
),...,(x
i−1
,x
i
), (x
j
,x
j+1
),...,(x
m−1
,a) ∈ R.
m ≤ n
a = b
A = {x, y, z} R = {(x, y), (y,z), (z, z)},
R
(2)
= {(x, z), (y,z), (z, z)},
R
(3)
= {(x, z), (y,z), (z, z)} = R
(2)
.
R
∗
= R ∪ R
(2)
∪R
(3)
= {(x, y), (y, z), (z, z), (x, z)}.
f ⊆ A × B
• Dom f = A
• Imf ⊆ B
• (a, b
1
) ∈ f, (a, b
2
) ∈ f ⇒ b
1
= b
2
.
f A B
x ∈ A y ∈ B
y = f(x) f : A → B, A
f
→ B, f : x →
f(x).
f : A → B f(a)=
f(a
1
) ⇒ a = a
1
.
f : A → B
b ∈ B a ∈ A b = f(a).
f : A → B f
f : R → R,x→ x
2
,
f : R → R
+
,x→ x
2
,
f : Z → Z,x→ 2x,
f : R → R,x→ 2x
f : A → B, g : B → C
g ◦f : A → C, (g ◦f )(a)=g(f(a)).
f : R → R,x→ 2x +1 g : R → R ,x→ x
2
+2.
g ◦ f : R → R,x→ 4x
2
+4x +3,
f ◦ g : R → R ,x→ 2x
2
+5.
f ◦g = g ◦ f.
A
f
→
B,B
g
→ C, C
h
→ D
h ◦ (g ◦ f)=(h ◦ g) ◦ f.
(h ◦ (g ◦ f ))(a)=h(g ◦ f)(a)) = h(g(f(a))) = (h ◦ g)(f(a)) = ((h ◦ g) ◦ f)(a).
A B F(A, B) B
A
.
A
n
= A ×···×A
n
f : A
n
→ A n
n
f(a, b) a × b, a + b, a · b, a ◦ b
ab
f : A → A
A = F(X, X). X X
F(X, X).
A = Mat
n
Mat
n
.
h ◦ (g ◦ f)=(h ◦ g) ◦ f,
f,g,h
f ◦ g = g ◦ f
f,g.
Z
(a − b) − c = a − (b − c), 5 − (3 − 2) = 4 =0=(5− 3) − 2.
A \ (B \ C) =(A \ B) \ C.
A = {a, b, c},B = {b, c},C = {c},
A \ B = {a},B\C = {b}⇒(A \ B) \ C = {a} = A \ (B \ C)={a, c}.
A = R[x] ∂ : R[x] → R[x],f(x) →
∂f(x)
∂x
∂(x
2
−3x)=5x −3. a, b ∈ A
a ◦ b a ◦ b = a∂(b).
a ◦ (b ◦ c) =(a ◦ b) ◦ c,
a, b, c ∈ A.
1 ◦ (1 ◦ x
2
)=2, (1 ◦ 1) ◦x
2
=0,
1 ◦ (1 ◦ x
2
) =(1◦ 1) ◦ x
2
.
a ◦ (b ◦ c) − (a ◦ b) ◦ c = b ◦ (a ◦ c) − (b ◦ a) ◦ c,
a, b, c ∈ A.