BÀI GIẢNG
TOÁN RỜI RẠC
HỆ ĐẠI HỌC
TRƯỜNG ĐẠI HỌC KINH TẾ KĨ THUẬT CÔNG NGHIỆP
KHOA CÔNG NGHỆ THÔNG TIN
GV: Nguyễn Thùy Dung
Phần I: Lý thuyết tổ hợp
Chương 1: Mở đầu ( 4t)
1.1. Sơ lược về lý thuyết tổ hợp
- Bài toán đếm
-Bài toán liệt kê
- Bài toán tồn tại
-Bài toán tối ưu
1.2. Những kiến thức cơ bản về lý thuyết tổ hợp (1/2)
Khái niệm về tập hợp:
Tập hợp là kết hợp các đối tượng có cùng bản chất (hay thuộc
tính) tùy ý, nhưng các phần tử có cùng một số tính chất và dấu
hiệu chung nào đó.
Ví dụ:
Các số tự nhiên của một tập hợp,kí hiệu là N.
Các số nguyên trong khoảng từ 1đến 250 mà chia hết cho
một trong các số nguyên tố 2, 3, 5, 7 là một tập hợp.
Sinh viên khoa CNTT là một tập hợp.
Ký hiệu:
Tập hợp được kí hiệu bằng A, B, …,X, Y, …còn phần tử
được kí hiệu bằng a, b, …,x, y, …
xlà phần tử của X, ta viết xX, ngược lại, ta viết xX.
Khái niệm
•Tập Ađược gọi là bằng tập B, nếu mọi phần tử của Alà phần
tử của Bvà ngược lại mọi phần tử của Bđều là phần tử của A.
Kí hiệu: A = B
•Số các phần tử của tập hợp A: Kí hiệu N(A)
1.2.2. Các phép toán trên tập hợp
-Phần bù:
-Hợp (phép cộng) của A và B: AB = {x: x A hoặc xB}
- Giao của A và B: AB = {x: x A và x B}
-Hiệu của A và B: A –B = {x: x A và xB}
Tính chất của các phép toán tập hợp
-Kết hợp:
-Giao hoán: