Xem mẫu
- TOÁN RỜI RẠC
Chương 2:
Lý thuyết tập hợp
Giảng viên: ThS. Trần Quang Khải
- Nội dung
1. Giới thiệu tập hợp.
2. Tích Descartes.
3. Các phép toán tập hợp.
4. Hỏi đáp.
5. Bài tập.
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 2
- TOPIC 1
Giới thiệu Tập hợp
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 3
- Giới thiệu
Tập hợp (set):
Cấu trúc rời rạc cơ bản các cấu trúc rời rạc khác.
Mục đích:
Nhóm (group) các đối tượng lại với nhau.
Các đối tượng thường có tính chất tương tự nhau.
Ví dụ:
Các sinh viên trong lớp Toán Rời Rạc.
Các con cọp thích ăn chay.
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 4
- Định nghĩa Tập hợp (set)
Một tập hợp là một “nhóm” (collection)
các đối tượng.
(Discrete Mathematics and Its Applications)
Các đối tượng trong tập hợp:
phần tử, hoặc
thành viên/thành phần
(elements, members)
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 5
- Biểu diễn
Kiểu liệt kê:
S = {a,b,c,d } : tập hợp các ký tự a,b,c,d.
a S : a là một phần tử S.
e S : e không phải là một phần tử của S.
∅ hoặc {} : tập rỗng.
Kiểu kí hiệu builder (xây dựng tập hợp):
= {x | x là số thực }
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 6
- Tập hợp “bằng nhau”
Equality: 2 tập hợp A và B là bằng nhau nếu và
chỉ nếu chúng có các phần tử giống nhau.
A = B ⇔ ∀x(x ∈A ↔ x ∈B)
Ví dụ:
{1,4,5} = {4,1,5}
{1,3,5,5,1} = {1,3,5}
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 7
- Biểu đồ Venn
John Venn (1834 - 1923)
Không gian (universe):
Hình chữ nhật. Tên tập hợp
Thường kí hiệu: U.
Các tập hợp:
Hình tròn, hoặc T
Các hình khép kín khác.
Các phần tử:
Điểm.
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 8
- Lượng số (Cardinality)
Nếu tập S có chính xác n (n ≥0, n Z) phần tử
phân biệt nhau thì:
S là tập hữu hạn (finite).
Lượng số của S là n.
Kí hiệu: |S| = n.
Ví dụ:
A là tập các số tự nhiên lẻ nhỏ hơn 10: |A| = ?
B là tập các sinh viên lớp Toán Rời Rạc: |B| = ?
|∅| = 0.
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 9
- Lượng số (Cardinality)
Tập vô hạn (infinite)?
Ví dụ:
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 10
- Tập con (Subset)
Tập A là con của tập B nếu mọi phần tử
của A cũng là phần tử của B.
Kí hiệu: A B
Nếu A B và A là tập con của B thì A B.
Ví dụ:
{1,3,5,5,1} {1,3,5}
{a, b, c} {a, x, y, b, d, c, e}
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 11
- Tập lũy thừa (Power set)
Power set: tổ hợp tất cả các phần tử.
Cho tập S, tập lũy thừa của S là tập tất cả các
tập con của S.
Ký hiệu: P(S) hay 2S.
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 12
- Tập lũy thừa (Power set)
Lượng số của tập lũy thừa:
|P(S)| = 2|S|
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 13
- TOPIC 2
Tích Descartes
(Cartesian product)
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 14
- Tập có thứ tự
Ordered n-tuples (n-bộ): A = (a1, a2, …, an)
a1 là phần tử thứ NHẤT.
a2 là phần tử thứ HAI.
…
an là phần tử thứ n.
Nếu thay đổi thứ tự, A không còn là A.
Hai tập có thứ tự bằng nhau?
A = (a1, a2, …, an) và B = (b1, b2, …, bn)
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 15
- Tích Descartes
René Descartes (1596-1650).
Cartesian Product:
Cho 2 tập A, B. tích Descartes của 2 tập A và B được
định nghĩa như sau:
A × B = {(a,b)|a ∈ A, b ∈ B}
Ví dụ: A = {0,1} và B = {a, b, c}
A × B = {(0, a), (0, b), (0, c), (1, a), (1, b),(1, c)}
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 16
- Tích Descartes
Tích Descartes của n tập hợp:
A1×A2×...×An=
{(a1, a2, …, an)| a1A1, a2A2,…, anAn }
Ví dụ:
A = {0,1}, B = {1, 2}, C = {0,1,2)
A×B×C=?
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 17
- TOPIC 3
Các phép toán tập hợp
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 18
- Union
Phép tuyển: A ∪ B
A ∪ B = {x|x A x B}
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 19
- Intersection
Phép hội: A ∩ B
A ∩ B = {x|x A x B}
Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 20
nguon tai.lieu . vn
