Bài giảng Toán rời rạc - Chương II: Các phương pháp đếm

TOÁN RỜI RẠC 
CHƯƠNG II: 
CÁC PHƯƠNG PHÁP ĐẾM 
CÁC PHƯƠNG PHÁP ĐẾM 
Tập hợp các tập hợp con. Biểu diễn tập hợp trên máy tính. Các phép toán tập hợp và các tính chất liên quan. T ập hợp tích Descartes. 
Nguyên lý cộng. Nguyên lý nhân. Nguyên lý chuồng bồ câu . 
Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton. 
Hoán vị và tổ hợp lặp. 
2 
TẬP HỢP 
1. Khái niệm 
2. Quan hệ giữa các tập hợp 
 3. Các cách xác định tập hợp 
4. Tập hợp các tập hợp con (Tập hợp lũy thừa) 
3 
 Một tụ tập của vô hạn hay hữu hạn các đối tượng có một tính chất chung nào đó gọi là một tập hợp. 
Các đối tượng trong một tập hợp được gọi là các phần tử của tập hợp đó. 
Tập hợp thường gọi vắn tắt là tập . 
Định nghĩa tập hợp: 
KHÁI NIỆM 
4 
 Ví dụ: 
R là tập các số thực. 
Z là tập các số nguyên. 
N là tập các số tự nhiên. 
Ghi chú: 
x ∈ A để chỉ x là phần tử của tập A 
x ∉ A để chỉ x không phải là phần tử của tập A 
∅ (tập rỗng): là tập không chứa bất kì phần tử nào 
KHÁI NIỆM 
5 
 Tập hợp bằng nhau: Hai tập hợp A và B được gọi là bằng nhau khi và chỉ 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. Kí hiệu: A=B. 
	 Ví dụ : {1, 3, 5} và {3, 5, 1} 
 Tập con: Tập A được gọi là tập con của tập B khi 
và chỉ khi mọi phần tử của A đều là phần tử của B. 
Kí hiệu : A  B. 
Nhận xét: (A  B) x (x A x B) là đúng 
QUAN HỆ GIỮA CÁC TẬP HỢP 
6 
Ví dụ: Tập các số nguyên dương lẻ nhỏ hơn 10 là một tập con của tập các số nguyên dương nhỏ hơn 10 . 
Ghi chú: Khi muốn nhấn mạnh tập A là tập con của tập B nhưng A≠B, ta viết A⊂B và nói rằng A là tập con thật sự của B . 
Nhận xét: 
 Nếu A⊆B và B⊆A thì A=B . 
 Tập rỗng là con của mọi tập hợp . 
 Mọi tập hợp đều là tập con của chính nó. 
QUAN HỆ GIỮA CÁC TẬP HỢP 
7 
 Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử của nó. Chúng ta sẽ dùng ký hiệu trong đó tất cả các phần tử của một tập hợp được liệt kê ở giữa hai dấu móc. 
 Ví dụ: 
 V = {a, e, i o, u} 
 O = { 1, 3, 5, 7, 9} 
 N = {0, 1, 2, 3, } 
 Z = {., 0, 1, 2, 3, }. 
1. Liệt kê các phần tử 
CÁC CÁCH XÁC ĐỊNH TẬP HỢP 
8 
 Một tập hợp cũng có thể được xác định bằng cách chỉ ra rõ các thuộc tính đặc trưng của các phần tử của nó. 
Cách viết: A={x U | p(x)} (A ={x U :p(x)}) hay vắn tắt A={x| p(x)} (A ={x: p(x)}) 
 Ví dụ: 
V = {x | x là nguyên âm} 
O = { x | x là số nguyên dương nhỏ hơn 10} 
A = { x | x = 2n, n N } 
B = { n N | n là số nguyên tố } . 
2. Chỉ ra các thuộc tính đặc trưng của phần tử 
CÁC CÁCH XÁC ĐỊNH TẬP HỢP 
9 
Cách viết: A={f(x)| x B } (A ={f(x): x B }) 
 Ví dụ: 
A = { (2n+1) | n N } . 
B = { 2x | x R } 
3. Cách xác định tập hợp dưới dạng ảnh của một tập hợp khác 
CÁC CÁCH XÁC ĐỊNH TẬP HỢP 
10 
 Cho tập X, tập tất cả các tập con của X (còn gọi là tập lũy thừa của X) được kí hiệu là P(X). Nói cách khác, 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. 
Ví dụ: X = {0, 1, 2} 
TẬP HỢP CÁC TẬP HỢP CON 
 P( X ) = {∅, { 0 }, {1}, {2}, {0,1}, {0,2},{ 1 , 2 },{ 0,1,2 3}}. 
Chú ý : 
 X  Y P(X)  P(Y). 
Nếu X có n phần tử ( n N) thì P(X) có 2 n phần tử. 
11 
 Có nhiều cách biểu diễn tập hợp trên máy tính. 
Ở đây chúng ta sẽ nói đến một phương pháp lưu trữ các phần tử bằng cách dùng sự sắp xếp tùy ý các phần tử của tập vũ trụ. 
1. Phương pháp biểu diễn 
BIỂU DIỄN TẬP HỢP TRÊN MÁY TÍNH 
12 
BIỂU DIỄN CÁC TẬP HỢP TRÊN MÁY TÍNH  
1. Phương pháp biểu diễn 
 Giả sử tập vũ trụ U là hữu hạn. Trước hết sắp 
xếp tuỳ ý các phần tử của U, ví dụ a 1 , a 2 , ,a n , 
sau đó biểu diễn tập con A của U bằng một 
xâu bit có chiều dài n, trong đó bit thứ i là 1 
nếu a i thuộc A và là 0 nếu a i không thuộc A. 
13 
 Cho U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} và sự sắp xếp các phần tử trong U theo thứ tự tăng dần, tức là a i = i. 
 Khi đó, chuỗi bit biểu diễn tập con A = {1, 2, 3, 4, 5} là 11111 00000; xâu bit biểu diễn tập con B = {1, 3, 5, 7, 9} là 10101 01010. 
 Để nhận được xâu bit cho các tập là hợp và giao của hai tập hợp, ta sẽ thực hiện phép toán Boole trên các xâu bit biểu diễn hai tập hợp đó. 
 Xâu bit đối với hợp của hai tập là : 
11111 00000 ∨ 10101 01010 = 11111 01010 
	 A∪B = {1, 2, 3, 4, 5, 7, 9}. 
 Xâu bit đối với giao của hai tập này là : 
11111 00000 ^ 10101 01010 = 10101 00000 
	 A∩B = {1, 3, 5}. 
2. Ví dụ 
BIỂU DIỄN CÁC TẬP HỢP TRÊN MÁY TÍNH 
14 
1. Phép hợp 
2. Phép giao 
3. Phép hiệu 
4. Các tính chất liên quan 
CÁC PHÉP TOÁN TẬP HỢP 
15 
 Định nghĩa: Cho A và B là hai tập hợp. Hợp của hai tập hợp A và B, được ký hiệu là A∪B, là tập hợp chứa các phần tử, hoặc thuộc A hoặc thuộc B hoặc thuộc cả hai. 
Ví dụ: 
 Cho A = {1, 2, 3} và B = {1, 3, 5} thì A∪B = {1, 2, 3, 5}. 
A∪B ={x| ( x ∈A ) ∨ ( x ∈B ) } 
Giản đồ Venn biểu diễn hợp của A và B 
1 . Phép hợp 
CÁC PHÉP TOÁN TẬP HỢP 
16 
Định nghĩa: Hợp của n tập hợp là một tập hợp chứa tất cả các phần tử thuộc ít nhất một trong số n tập hợp đó. 
Ta ký hiệu: 
để chỉ hợp của các tập hợp A 1 , A 2, ..., A n .