Bài giảng Toán rời rạc - Chương 2: Tập hợp và ánh xa - Nguyễn Anh Thi

Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Bài giảng môn học Toán Rời Rạc
Nguyễn Anh Thi
Trường Đại học Khoa học Tự nhiên, Tp Hồ Chí Minh
2017
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Chương 2
Tập hợp và ánh xạ
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Định nghĩa
Tập hợp được dùng để chỉ một nhóm các đối tượng nào đó mà
chúng ta đang quan tâm xem xét, và nhóm này phải được xác
định tốt.
Ví dụ
• Tập hợp sinh viên của một trường đại học.
• Tập hợp các số nguyên tố.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Các đối tượng trong tập hợp được gọi là phần tử hay thành viên
của tập hợp. Khi đối tượng là một phần tử của tập hợp, ta nói
đối tượng thuộc về, (ký hiệu ∈), tập hợp. Khi đối tượng không
phải là một phần tử của tập hợp, ta nói đối tượng không thuộc
về tập hợp.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Định nghĩa
Số phần tử của một tập hợp A được gọi là lực lượng của tập
hợp, ký hiệu |A|.
Nếu A có hữu hạn phần tử, ta nói A là tập hữu hạn. Ngược lại,
nếu A có vô hạn phần tử, ta nói A là tập vô hạn.
Ví dụ
• N,Z,R là các tập hợp vô hạn.
• A = {1, 2, 3, 4, 5, 6} là tập hợp hữu hạn có số phần tử là
|A| = 6.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Định nghĩa
Tập hợp A và B được xem là bằng nhau khi chúng có cùng các
phần tử, tức là mỗi phần tử thuộc A đều là phần tử thuộc B và
ngược lại. Ta viết A = B.
Tập hợp không có phần tử nào được gọi là tập hợp rỗng, và
được ký hiệu là ∅.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Cách xác định tập hợp
• Cách liệt kê
Ta liệt kê tất cả các phần tử của tập hợp giữa hai dấu
ngoặc ′′{′′ và ′′}′′.
Ví dụ
A = {1, 2, 3, 4}
• Cách nêu đặc trưng của các phần tử.
Ví dụ
B = {n ∈ N|n chia hết cho 3}.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Định nghĩa
Cho A và B là hai tập hợp mà các phần tử của chúng đều
thuộc một tập hợp lớn U (hay còn gọi là tập vũ trụ). Ta nói tập
A bao hàm trong (hay chứa trong) tập B nếu mỗi phần tử của
tập hợp A đều thuộc tập hợp B. Ta cũng nói rằng B bao hàm
A (hay B chứa A), và viết là: A ⊂ B (hay B ⊃ A).
Khi A ⊂ B chúng ta nói A là một tập hợp con của B.
Ví dụ
• {0, 1, 2} ⊂ {n ∈ N : n < 10}
• N ⊂ Z ⊂ Q ⊂ R ⊂ C
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Định nghĩa
Cho X là một tập hợp. Nhóm tất cả các tập hợp con của X
được ký hiệu là P(X), là một tập hợp mà mỗi phần tử của nó
là một tập hợp con của X.
Tính chất
• ∅ ⊂ A và A ⊂ A, với mọi tập hợp A.
• (A ⊂ B) ∧ (B ⊂ A) ⇒ (A = B).
• (A ⊂ B) ∧ (B ⊂ C) ⇒ (A ⊂ C).
• X ⊂ Y ⇒ P(X) ⊂ P(Y).
• Nếu tập hợp X có n phần tử thì tập hợp P(X) có 2n phần
tử.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Các phép toán tập hợp
• Giao của hai tập hợp A và B, ký hiệu bởi A ∩ B, là tập hợp
gồm tất cả các phần tử vừa thuộc tập A, vừa thuộc tập B.
A ∩ B = {x : (x ∈ A) ∧ (x ∈ B)}
• Hội của hai tập hợp A và B, ký hiệu bởi A ∪ B, là tập hợp
gốm tất cả các phần tử sao cho nó thuộc tập A hay thuộc
tập B.
A ∪ B = {x : (x ∈ A) ∨ (x ∈ B)}
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
• Hiệu của hai tập hợp A và B, ký hiệu bởi A\B (hay A-B), là
tập hợp gồm tất cả các phần tử sao cho nó thuộc tập A và
không thuộc tập B.
• Phần bù của tập A (trong U), ký hiệu bởi Ac, là tập hợp tất
cả các phần tử của U mà không thuộc A. Nói cách khác,
Ac = U− A.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Các tính chất của phép toán
• Tính giao hoán: A ∩ B = B ∩ A, A ∪ B = B ∪ A
• Tính chất kết hợp: A ∩ (B ∩ C) = (A ∩ B) ∩ C,
A ∪ (B ∪ C) = (A ∪ B) ∪ C
• Tính phân bố: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
• Luật De Morgan: (A ∩ B)c = Ac ∪ Bc, (A ∪ B)c = Ac ∩ Bc
• Phần tử trung hòa: A ∪ ∅ = A, A ∩ U = A
• Phần bù: A ∪ Ac = U, A ∩ Ac = ∅
• Tính thống trị: A ∪ U = U, A ∩ ∅ = ∅
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Tập hợp
Định nghĩa
Tích Descartes của hai tập hợp A và B, ký hiệu là A× B, là tập
hợp gồm tất cả các cặp (a, b) sao cho a ∈ A và b ∈ B. Tức là
A× B = {(a, b) : (a ∈ A) ∧ (b ∈ B)}.
Trong trường hợp B = A, ta ký hiệu A× B là A2.
Định nghĩa
Tích Descartes của n tập hợp A1,A2, . . . ,An, ký hiệu là
A1 × A2 × · · · × An là tập hợp gồm tất cả các bộ n phần tử
(a1, a2, . . . , an) với ai ∈ Ai (∀i = 1, . . . ,n,n > 1).
Nếu A1 = A2 = . . .An = A thì tập hợp tích A1 × A2 × · · · × An
sẽ được viết là An.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Ánh xạ
Định nghĩa
Cho hai tập hợp X, Y 6= ∅. Ánh xạ giữa hai tập hợp X và Y là
một quy tắc sao cho mỗi x ∈ X tồn tại duy nhất một y ∈ Y để
f(x) = y. Ta viết
f : X −→ Y
x 7−→ y = f(x)
Nghĩa là với mỗi x ∈ X, tồn tại duy nhất y ∈ Y sao cho y = f(x).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Ánh xạ
Ví dụ
a. Ánh xạ đồng nhất trên X
idX : X −→ X
x 7−→ x.
b. Cho A ⊂ X, ta có ánh xạ bao hàm (ánh xạ nhúng) từ A vào
X,
iA : A −→ X
a 7−→ a.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Ánh xạ
Định nghĩa
Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau nếu
∀x ∈ X, f(x) = g(x).
Ví dụ
Xét ánh xạ f(x) = (x− 1)(x + 1) và g(x) = x2 − 1
Định nghĩa
Cho f : X −→ Y và g : Y −→ Z, lúc đó g ◦ f : X −→ Z là ánh xạ
hợp của g và f, được xác định bởi g ◦ f(x) = g(f(x)).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Ánh xạ
Định nghĩa
Cho f : X −→ Y,
a. Cho A ⊂ X, ảnh của A bởi f là tập
f(A) = {f(x)|x ∈ A} ⊂ Y;
b. Cho V ⊂ Y, ảnh ngược của V bởi f là tập
f−1(V) = {x ∈ X|f(x) ∈ V} ⊂ X.
c. Ta ký hiệu Im(f) = f(X), gọi là ảnh của f.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Các loại ánh xạ
Định nghĩa
Cho f : X → Y là ánh xạ từ X và Y.
a. f được gọi là một đơn ánh khi và chỉ khi
∀x1, x2 ∈ X, f(x1) = f(x2) ⇒ x1 = x2. Hay nói cách khác, f
được gọi là một đơn ánh khi và chỉ khi
x1 6= x2 ⇒ f(x1) 6= f(x2)
b. f được gọi là một toàn ánh khi và chỉ khi
∀y ∈ Y,∃x ∈ X : f(x) = y. Hay nói cách khác, f được gọi là
một toàn ánh khi và chỉ khi Im(f) = Y.
c. f được gọi là một song ánh khi và chỉ khi f vừa là đơn ánh
vừa là toàn ánh. Hay nói cách khác, f được gọi là một song
ánh khi và chỉ khi ∀y ∈ Y,∃! x ∈ X : f(x) = y.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Ánh xạ
Ví dụ
• Cho
f : N −→ R
x 7−→ x2 + 1
khi đó f là một đơn ánh.
• Cho
g : R −→ R
x 7−→ x3 + 1
khi đó f là một toàn ánh.
• Cho
g : R −→ R
x 7−→ x3 + 1.
khi đó f là một song ánh.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Ánh xạ
Định nghĩa
Khi f là một song ánh từ X vào Y, quy tắc với mỗi phần tử
y ∈ Y, ta xác định được duy nhất một x ∈ X (thỏa f(x) = y) là
một ánh xạ từ Y vào X, gọi là ánh xạ ngược của f, ký hiệu f−1.
Ví dụ
Cho
f : [0; 2] −→ [0; 4]
x 7−→ x2
thì
f−1 : [0; 4] −→ [0; 2]
y 7−→ √y
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc