Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Mở đầu - Nguyễn Đức Nghĩa

Fall 2008 
Toán rời rạc 
Phần thứ nhất 
LÝ THUYẾT TỔ HỢP 
Combinatorial Theory 
Fall 2008 
Toán rời rạc 
Nội dung 
Mở đầu 
Bài toán đếm tổ hợp (Counting Problem) 
Bài toán tồn tại tổ hợp (Existence Problem) 
Bài toán liệt kê tổ hợp (Enumeration Problem) 
Bài toán tối ưu tổ hợp (Combinatorial Optimization Problem) 
Toán rời rạc 
0. Mở đầu 
NỘI DUNG 
0.1. Tổ hợp là gì? 
0.2. Sơ lược về lịch sử phát triển của tổ hợp 
0.3. Tập hợp và ánh xạ 
Toán rời rạc 
0.1 Tổ hợp là gì? 
Đối tượng nghiên cứu 
Nội dung nghiên cứu 
Toán rời rạc 
Đối tượng nghiên cứu của tổ hợp 
Lý thuyết tổ hợp gắn liền với việc nghiên cứu sự sắp xếp của các phần tử trong các tập hữu hạn và sự phân bố của các phần tử vào các tập hữu hạn. Mỗi cách sắp xếp hoặc phân bố như thế được gọi là một cấu hình tổ hợp. 
Có thể nói vắn tắt: Tổ hợp là lý thuyết về các tập hữu hạn. 
Toán rời rạc 
Phân loại bài toán 
Trong các tài liệu về tổ hợp, thường gặp các dạng bài toán dưới đây: 
1. Bài toán đếm tổ hợp (Counting Problem) 
2. Bài toán tồn tại tổ hợp (Existence Problem) 
3. Bài toán liệt kê tổ hợp (Enumeration Problem) 
4. Bài toán tối ưu tổ hợp (Combinatorial optimization Problem) 
Toán rời rạc 
Bài toán đếm – Counting Problem 
Đây là các bài toán nhằm trả lời câu hỏi: “ Có bao nhiêu cấu hình thoả mãn các điều kiện cho trước? ". 
Phương pháp đếm thường dựa vào một số nguyên lý cơ bản và một số kết quả đếm các cấu hình đơn giản. 
Bài toán đếm được áp dụng một cách có hiệu quả vào những công việc mang tính chất đánh giá như tính xác suất của một sự kiện, tính độ phức tạp của một thuật toán, ... 
Toán rời rạc 
 Bài toán tồn tại tổ hợp  (Existence Problem) 
Kh á c với bài to á n đếm, trong bài to á n tồn tại tổ hợp ch ú ng ta cần trả lời c â u hỏi: “Tồn tại hay chăng cấu h ì nh tổ hợp thoả m ã n c á c t í nh chất đ ã cho?” 
R õ ràng nếu c ó thể đếm được số lượng cấu h ì nh tổ hợp thoả m ã n c á c t í nh chất đó cho th ì ta cũng giải quyết được bài to á n tồn tại tương ứng! 
C ó thể coi bài to á n tồn tại như trường hợp ri ê ng của bài to á n đếm được kh ô ng? 
Toán rời rạc 
Ví dụ 
Bài toán phủ bàn cờ quốc tế bởi các quân bài domino: 
 “Cho bàn cờ quốc tế kích thước 8 8 bị đục đi 2 ô ở hai góc đối diện và bộ bài domino, mỗi quân bài phủ kín 2 ô của bàn cờ. Hỏi có thể phủ kín bàn cờ đã cho bởi 31 quân bài domino?” 
Toán rời rạc 
Bàn cờ quốc tế và quân bài domino 
Toán rời rạc 
Bàn cờ quốc tế và quân bài domino 
Toán rời rạc 
Có thể phủ bàn cờ như vậybởi 31 quân bài domino? 
Bàn cờ còn 62 ô 
31 quân bài có thể phủ kín được 62 ô 
Về diện tích là có thể phủ được 
Toán rời rạc 
Không tồn tại cách phủ bàn cờ như vậybởi 31 quân bài domino! 
Chứng minh 
Mỗi quân bài phủ kín 1 ô trắng và một ô đen. 
Suy ra số lượng ô trắng và ô đen bị phủ bởi 31 quân domino là bằng nhau. 
Thế nhưng số lượng ô trắng và ô đen trên phần còn lại của bàn cờ là khác nhau 
Từ đó suy ra không tồn tại cách phủ! 
Toán rời rạc 
Có bao nhiêu cách phủ bàn cờ bởi 32 quân bài domino? 
Sự tồn tại cách phủ là hiển nhiên. Dễ dàng có thể chỉ ra vài cách phủ 
Vấn đề “Có bao nhiêu cách phủ?” 
Không dễ dàng trả lời! 
Toán rời rạc 
Có bao nhiêu cách phủ bàn cờ bởi 32 quân bài domino? 
Nếu chỉ phân biệt hai cấu hình bởi dạng hình học của cách phủ thì có tất cả 
 12 988 816 
 cách phủ. 
Có 2 cách phủ bàn cờ kích thước 2 2 
Toán rời rạc 
Phân biệt hai bài toán đếm và tồn tại 
Trong bài toán đếm, sự tồn tại cấu hình là hiển nhiên và vấn đề là cần đếm xem có bao nhiêu. 
Trong bài toán tồn tại, bản thân sự tồn tại cấu hình là vấn đề nghi vấn. Cần giải quyết vấn đề “có hay không có” cấu hình như vậy. 
Việc chỉ ra được một cấu hình là đủ để khẳng định là tồn tại 
Nhưng để chỉ ra sự không tồn tại cấu hình đòi hỏi phải đưa ra những lập luận tin cậy 
Toán rời rạc 
Bài toán liệt kê tổ hợp  (Enumeration Problem) 
Bµi to¸n nµy quan t©m ®Õn viÖc ®­a ra tÊt c¶ cÊu h×nh tho¶ m·n c¸c ®iÒu kiÖn cho tr­íc. 
V× thÕ lêi gi¶i cña nã cÇn ®­îc biÓu diÔn d­íi d¹ng thuËt to¸n "vÐt c¹n" tÊt c¶ c¸c cÊu h×nh. Lêi gi¶i trong tõng tr­êng hîp cô thÓ sÏ ®­îc m¸y tÝnh ®iÖn tö gi¶i quyÕt theo thuËt to¸n ®· nªu. 
Bµi to¸n liÖt kª ®­îc lµm "nÒn" cho nhiÒu bµi to¸n kh¸c. HiÖn nay, mét sè bµi to¸n ®Õm, tèi ­u, tån t¹i vÉn ch­a cã c¸ch nµo gi¶i, ngoµi c¸ch gi¶i liÖt kª. 
NÕu tr­íc ®©y, c¸ch gi¶i liÖt kª cßn mang nÆng tÝnh lý thuyÕt, th× b©y giê nã ngµy cµng kh¶ thi nhê sù ph¸t triÓn nhanh chãng cña m¸y tÝnh ®iÖn tö. 
Toán rời rạc 
Bài toán tối ưu tổ hợp  (Combinatorial Problem) 
Khác với bài bài toán liệt kê, bài toán tối ưu chỉ quan tâm đến một cấu hình "tốt nhất" theo một nghĩa nào đấy. 
Trong các bài toán tối ưu , mỗi cấu hình được gán cho một giá trị số (là giá trị sử dụng hoặc chi phí xây dựng cấu hình), và bài toán đặt ra là trong số những cấu hình thoả mãn các điều kiện cho trước hãy tìm cấu hình với giá trị số gán cho nó là lớn nhất hoặc nhỏ nhất. 
Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý thuyết tổ hợp đã đóng góp một phần đáng kể trong việc xây dựng được những thuật toán hữu hiệu. 
Toán rời rạc 
0. Mở đầu 
NỘI DUNG 
0.1. Tổ hợp là gì? 
0.2. Sơ lược về lịch sử phát triển của tổ hợp 
0.3. Tập hợp và ánh xạ 
Fall 2008 
Toán rời rạc 
0.2. Sơ lược về lịch sử phát triển 
Có thể nói là tổ hợp là một trong những lĩnh vực có lịch sử phát triển lâu đời nhất của toán học 
Nói về lịch sử phát triển của tổ hợp cũng chính là nói về lịch sử phát triển của toán học 
Vì vậy, chúng ta sẽ chỉ điểm qua vài nét về lịch sử, thông qua một số bài toán nổi tiếng trong lịch sử phát triển của tổ hợp 
Toán rời rạc 
Hình vuông thần bí - Ma phươngMagic Square 
4 
9 
2 
3 
5 
7 
8 
1 
6 
Toán rời rạc 
Hình vuông thần bí - Ma phươngMagic Square 
4 
9 
2 
3 
5 
7 
8 
1 
6 
Toán rời rạc 
Tổng theo mỗi hàng ngang, mỗi hàng dọc cũng như mỗi đường chéo đều bằng 15 
Toán rời rạc 
Ma phương 
Bảng số này được biết từ thời nhà Chu (quãng 2200 năm trước công nguyên) 
Hãy chú ý đến những tính chất đặc biệt của bảng số này để có thể thấy tại sao nó được gọi là ma phương và được người Trung hoa cổ đại tôn thờ 
Con số 5 nằm ở giữa biểu hiện Ngũ hành nằm ở trung tâm vũ trụ 
Các số lẻ biểu thị cho “dương”, các số chẵn biểu thị cho “âm” đều đối xúng nhau qua trung tâm 
Nếu tính định thức của ma trận cấp 3 này ta được giá trị 360 = số ngày trong một năm 
Giá trị tuyệt đối của các định thức con cũng là các con số đáng chú ý: 7, 23, 37, 53. 
Toán rời rạc 
Ma phương bậc tuỳ ý 
Ma phương cấp n là bảng gồm n 2 số 1, 2, ..., n 2 được xếp thành n hàng ngang và n hàng dọc sao cho tổng các số trên mỗi hàng ngang và mỗi hàng dọc cũng như hai đường chéo đều bằng nhau 
Hiện nay có thuật toán xây dựng ma phương mọi cấp. Thuật toán xây dựng ma phương bậc lẻ là đơn giản hơn rất nhiều so với thuật toán xây dựng ma phương bậc chẵn 
Toán rời rạc 
Thuật toán xây dựng ma phương bậc lẻ 
Thuật toán: 
 Điền lần lượt các giá trị số 1, 2, ..., n 2 vào các vị trí của bảng, bắt đầu từ ô ở giữa dòng thứ nhất điền số 1. Tiếp đến di chuyển lên trên và sang phải để điền số tiếp theo. 
Chú ý: 
Trên dòng 1 là dòng n , bên phải cột n là cột 1. 
Nếu gặp vị trí đã có số thì số tiếp theo điền xuống ngay dưới số vừa điền. 
Số lượng ma phương (loại trừ những cấu hình thu được bởi phép quay và phản xạ) 
Fall 2008 
Toán rời rạc 
n 
# Magic Squares 
Chú thích 
1 
1 
2 
0 
3 
1 
4 
880 
Frénicle de Bessy (1693) 
5 
275 305 224 
R. Schroeppel (1973) 
6 
(1.7745 0.0016)10 19 
Berlekamp et al. (1982) 
Approximation by Monte Carlo Backtracking 
7 
(3.79809 ± 0.00050) · 10 34   
Approximation by Monte Carlo Backtracking 
Number of distinct magic squares (excluding those obtained by rotation and reflection) 
Fall 2008 
Toán rời rạc 
8 
(5.2225 ± 0.0018) · 10 54   
0.035 % 
9 
(7.8448 ± 0.0038) · 10 79   
0.049 % 
10 
(2.4149 ± 0.0012) · 10 110 
0.049 % 
11 
(2.3358 ± 0.0014) · 10 146 
0.059 % 
12 
(1.1424 ± 0.0010) · 10 188 
0.087 % 
13 
(4.0333 ± 0.0054) · 10 235 
0.14 % 
14 
(1.5057 ± 0.0024) · 10 289 
0.16 % 
15 
(8.052 ± 0.022) · 10 348 
0.27 % 
16 
(8.509 ± 0.027) · 10 414 
0.31 % 
17 
(2.314 ± 0.009) · 10 487 
0.39 % 
18 
(2.047 ± 0.008) · 10 566 
0.40 % 
19 
(8.110 ± 0.035) · 10 651 
0.44 % 
20 
(1.810 ± 0.008) · 10 744 
0.44 % 
To determine the numbers of magic squares following methods were used: 
 Exhaustive search by Standard Backtracking: orders 4 and 5 
 Approximation by Monte Carlo Backtracking: orders 6 to 20 
 Estimation by statistical considerations on magic series combined with extrapolations of known approximations: orders greater than 20 
Toán rời rạc 
Các tính chất đặc biệt của các con số 
36 = 1+2+3+4+5+6+7+8 
 (Tổng của 4 số lẻ và 4 số chẵn đầu tiên) 
36 = 1 3 +2 3 +3 3 
Con số 36 được người Trung hoa rất tôn sùng = Số quẻ trong Kinh dịch 
Các nhà triết học Ai cập cổ đại cũng rất tôn sùng các con số: “ Mọi hiện tượng trong tự nhiên cũng như trong xã hội đều cố gắng giải thích bằng các con số ” 
Toán rời rạc 
Số hoàn hảo 
Biểu thị tính hoàn hảo: Dùng số hoàn hảo ( perfect number ) . Số tự nhiên a được gọi là số hoàn hảo, nếu số này bằng tổng các ước số của nó. 
Ví dụ: 
6 = 1+2+3 
28 = 1+2+4+7+14 
So sánh: Số lượng số hoàn hảo và Số lượng số nguyên tố trên đoạn [ a, b ] 
Fall 2008 
Toán rời rạc 
Cặp số hữu nghị 
Biểu thị tình hữu nghị: Dùng cặp số hữu nghị ( pair of friendship numbers ). Hai số tự nhiên a, b được gọi là cặp số hữu nghị nếu số này bằng tổng các ước số của số kia và ngược lại 
Ví dụ: (220, 284), (1184, 1210), 
 (2620,2924), (5020, 5564), (6232, 6368) 
Toán rời rạc 
Trò chơi với con súc sắc 
Người chơi sẽ gieo một (một vài) con súc sắc và đặt cá cược vào khả năng xuất hiện của các mặt. 
Hầu tước de Mere phát hiện khi gieo các con súc sắc số khả năng có thể xuất hiện của các tổng điểm là khác nhau: 
Ví dụ: Gieo hai con súc sắc, 
Tổng điểm 7 có 6 khả năng: (1, 6), (2, 5), (3, 4) 
Tổng điểm 6 có ? khả năng: (1, 5), (2, 4), (3, 3) 
Toán rời rạc 
Các khả năng xuất hiện tổng điểm khi gieo hai con súc sắc 
Toán rời rạc 
Tôn Tẫn đấu ngựa 
Có 3 vòng đấu 1, 2, 3. Người thắng cuộc là người thắng ở nhiều vòng đấu hơn 
Vua: Có 3 con ngựa A (loại 1), B (loại 2) và C (loại 3) 
Tôn Tẫn: Có 3 con ngựa a (loại 1), b (loại 2) và c (loại 3) 
Toán rời rạc 
Lịch thi đấu của Tôn Tẫn 
Vòng đấu 
Vua 
Điểm 
Tôn Tẫn 
Điểm 
Vòng 1 
A 
1 
c 
0 
Vòng 2 
B 
0 
a 
1 
Vòng 3 
C 
0 
b 
1 
Tổng điểm 
1 
2 
Toán rời rạc 
Bài toán tối ưu tổ hợp 
Trong số tất cả các cách tổ chức thi đấu hãy tìm cách đem lại nhiều điểm nhất 
Có tất cả bao nhiêu cách tổ chức thi đấu ? 
=> Dễ dàng tìm được cách đạt được nhiều điểm nhất và may thay đó cũng là cách dẫn đến thắng lợi! 
Nếu số lượng vòng đấu nhiều hơn, cách tính điểm phức tạp hơn thì không dễ dàng nhẩm ra được cách đem lại nhiều điểm nhất! 
Fall 2008 
Toán rời rạc 
0. Mở đầu 
NỘI DUNG 
0.1. Tổ hợp là gì? 
0.2. Sơ lược về lịch sử phát triển của tổ hợp 
0.3. Tập hợp và ánh xạ 
Toán rời rạc 
TẬP HỢP 
Các khái niệm cơ bản 
Các phép toán tập hợp 
Sơ đồ Venn 
Các đẳng thức 
Toán rời rạc 
Tập hợp 
Ta hiểu: Tập hợp như là sự tụ tập của các phần tử. 
Ta nói tập hợp chứa các phần tử của nó. 
Các tập hợp được ký hiệu bởi A-Z , các phần tử a-z 
Thông thường phải có một tập vũ trụ U mà tất cả các phần tử được xét trong nó. Tập U có thể được chỉ rõ hoặc được ngầm định. 
Xác định tập hợp: 	 
Danh sách các phần tử: 
	 S = a, b, c, d  = b, c, a, d, d  
	(Chú ý: Việc liệt kê lặp lại một phần tử không dẫn đến tập mới. Thứ tự liệt kê là không có vai trò.) 
Toán rời rạc 
Tập hợp 
Xác định tập hợp (tiếp): 
Mô tả cách xây dựng tập hợp bằng việc sử dụng mệnh đề lôgic: 
	 S = x | P (x) } 
	 S chứa các phần tử thoả mãn mệnh đề P . 
Ví dụ, S = { x  x là sinh viên ĐHBK HN} 
	đọc là “ S là tập tất cả các phần tử x sao cho x là sinh viên ĐHBK HN.” 
Liệt kê các phần tử: 
 S =  , -3, -2, -1  - tập các số nguyên âm . 
Toán rời rạc 
Tập hợp 
Các tập vũ trụ thường dùng 
R = tập số thực 
N = tập số tự nhiên = 0,1, 2, 3,   
Z = tập các số nguyên =  , -3, -2, -1, 0, 1, 2, 3,   
Z + tập các số nguyên không âm 
Toán rời rạc 
Tập hợp 
Nhận biết các phần tử của tập hợp 
Ký hiệu: 
x là phần tử của S hay còn nói x thuộc S : x S 
x không là phần tử của S : x S 
Ví dụ: Gọi S là tập các số nguyên từ 1 đến 12. Khi đó 
	5 S 	nhưng 15 S 
Chú ý: V iệc biết một phần tử có thuộc một tập cho trước hay không là vấn đề không phải lúc nào cũng là dễ dàng: 
 Ví dụ: Gọi P là tập các số nguyên tố. Hỏi 
 x =12121212121212121212111111111111111111111 
 có thuộc P ? 
Toán rời rạc 
Tập con 
Tập A được gọi là tập con của tập B nếu mỗi phần tử của A đều là phần tử của B , nghĩa là 
	 x [ x A x B ] 
Ký hiệu: 
	 A  B 	 hoặc B  A 
Ví dụ: 
Nếu S = 1, 2, 3,  , 11, 12  và T = 1, 2, 3, 6  
 Thế thì T  S . 
Toán rời rạc 
Tập con 
Một số định nghĩa: 
Một tập luôn là tập con của chính nó. 
Hai tập là bằng nhau khi và chỉ khi mỗi phần tử của tập thứ nhất đều là phần tử của tập thứ hai và ngược lại, nghĩa là 
	 A = B khi và chỉ khi A  B và B  A 
Nếu A  B , nhưng A B khi đó ta nói A là tập con thực sự của B . Ký hiệu: A  B . 
Ví dụ: 
Giả sử A = { 1, 2, 3 }, B = { 2, 3, 1 }, C = { 3 } 
Khi đó 
 B = A, C  A, C  B . 
Toán rời rạc 
Tập con 
Một số định nghĩa: 
Tập rỗng ( trống ) là tập không có phần tử nào cả. 
Ký hiệu:  . 
 là tập con của mọi tập 
Tập tất cả các tập con ( Power set ) của tập A 
Ký hiệu: 2 A (đôi khi dùng ký hiệu: P ( A )) 
Ví dụ, nếu A = {1} thì 2 A = { ,{1} } 
Tập gồm n phần tử có 2 n tập con. 
Toán rời rạc 
Tập con 
Lực lượng ( cardinality ) của tập A là số phần tử trong A . 
Ký hiệu: | A | (đôi khi còn ký hiệu là # A , N ( A )). 
Nếu lực lượng của một tập hợp là số tự nhiên thì nó được gọi là tập hữu hạn , nếu trái lại nó là tập vô hạn . 
Ví dụ: N (tập các số tự nhiên) là vô hạn, bởi vì | N | không là số tự nhiên. 
Chú ý: Nếu | A | = n thì	 | P ( A )| = 2 n . 
Toán rời rạc 
Tập con 
Ví dụ: 
Nếu A = a, b  thì 
Tập các tập con của A : 
	2 A = , a , b , a, b  
Lực lượng của A : 
	| A | = | a, b  | = 2 
	|2 A | = 4 
A và 2 A là các tập hữu hạn. 
Toán rời rạc 
Lý thuyết tập hợp là không hoàn chỉnh 
Nghịch lý Russell (Russell’s paradox): 
Xét S là tập các tập hợp không chứa chính nó như là phần tử của nó : 
 S = { x | x x }. 
Câu hỏi: Có phải S S ? 
Bertrand Russell1872-1970 
Toán rời rạc 
Nghịch lý Russell 
Cho S = { x | x x }. Hỏi S S ? 
Nếu S S , thì S không là đối tượng x thoả mãn x x. 
 Suy ra , S S ?! 
Nếu S S , thì S là một đối tượng x thoả mãn x x. 
 Suy ra , S S ?! 
 Vì vậy ta không thể kết luận được S S và cũng không thể kết luận được S S ?! 
Paradox! 
Toán rời rạc 
Các phép toán tập hợp 
Giao ( intersection ) của 2 tập A và B : 
là tập các phần tử vừa thuộc vào A vừa thuộc vào B . 
Ký hiệu: A  B 
	 	 A  B = x  x A  x B  
Nếu giao là tập rỗng, thì A và B được gọi là không giao nhau . 
Toán rời rạc 
Các phép toán tập hợp 
Hợp ( union ) của 2 tập A và B : 
là tập tất cả các phần tử hoặc thuộc A hoặc thuộc vào B . 
Ký hiệu: A  B 
	 	 A  B = x  x A  x B  
Lực lượng của hợp của hai tập A và B : 
	Có quan hệ so sánh nào ? 
 | A  B | ? | A | ? | B | ? | A  B | 
Toán rời rạc 
Các phép toán tập hợp 
Hiệu ( difference ) của A và B : 
là tập hợp các phần tử của A không thuộc vào B . 
Ký hiệu: A – B hoặc A \ B 
	 A – B = x  x A  x B  
Hiệu đối xứng ( symmetric difference ) của A và B : 
là tập ( A – B )  ( B – A ) 
Ký hiệu: A  B 
Toán rời rạc 
Các phép toán tập hợp 
Phần bù ( complement ) của tập A : 
là tập U – A , trong đó U là tập vũ trụ. 
phần bù của A là phụ thuộc vào U ! 
Ký hiệu:  A 
	  A = x  ( x A )  
Cách ký hiệu khác: A c . 
Toán rời rạc 
Các phép toán tập hợp 
Ví dụ: 
U = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10  
A= 1, 2, 3, 4, 5  , B = 4, 5, 6, 7, 8  . 
Khi đó 
Toán rời rạc 
Tích Đề các 
Tích Đề-các ( Cartesian product ) của A với B : 
Là tập bao gồm tất cả các cặp có thứ tự ( a, b ), trong đó a thuộc A và b thuộc B . 
Ký hiệu: A B. Theo định nghĩa 
	 A B = ( a , b )  a A  b B  
Ví dụ: 
Cho A = 1, 2, 3  và B = 3, 4 . Khi đó 
	 A B = (1,3), (1,4), (2,3), (2,4), (3,3), (3,4)  
	 B A = (3,1), (3,2), (3,3), (4,1), (4,2), (4,3)  
Thông thường A B B A 
| A B | = ? 
René Descartes (1596-1650) 
Toán rời rạc 
Tích Đề các 
Ví dụ: 
A = { Thắng, Mạnh, Hùng, Cường }; 
B = { Mai, Mơ, Mận, Me, Muỗm } 
A B = { (T, Mai), ..., (T, Muỗm}, ...,(C, Muỗm) } 
Tích Đề các được mở rộng cho nhiều tập: 
Cho A 1 , A 2 , ..., A m là các tập hợp 
A 1 A 2 ... A m = {( a 1 , a 2 , ..., a m ): a i A i , i = 1, 2,..., m } 
Toán rời rạc 
Tích Đề các 
Ví dụ: 
A = { Thắng, Mạnh, Hùng, Cường }; 
B = { Mai, Mơ, Mận, Me, Muỗm } 
C = { P30 - B4, P55-B3, P17-A1 } 
A B C = {(Thắng, Mai, P30-B4), ... } 
Ký hiệu 
Toán rời rạc 
SƠ ĐỒ VENN (John Venn 1834-1923) 
Venn diagrams: 
Là cách biểu diễn rất trực quan giúp chỉ ra mối liên hệ giữa 2 hoặc 3 tập hợp. 
Tập vũ trụ U được biểu diễn bởi hình chữ nhật. 
Mỗi tập con của U được biểu diễn bởi phần trong của một vòng kín. 
Ví dụ: 
Cho 2 tập 
Cho 3 tập 
Toán rời rạc 
Ví dụ: Nhiều tập sẽ rất rối mắt! 
0 
-1 
1 
2 
3 
4 
5 
6 
7 
8 
9 
Sè nguyªn d­¬ng nhá h¬n 10 
Sè ch½n tõ 2 ®Õn 9 
Sè lÎ tõ 1 ®Õn 9 
Sè nguyªn tè <10 
Sè nguyªn tõ -1 ®Õn 9 
Toán rời rạc 
SƠ ĐỒ VENN 
Ví dụ: Vẽ sơ đồ Venn cho thấy tác động của các phép toán tập hợp. 
Các miền tương ứng với kết quả sẽ tô đen để chỉ ra tác động của phép toán tập hợp. 
Toán rời rạc 
Sơ đồ Venn 
Toán rời rạc 
Sơ đồ Venn 
Toán rời rạc 
Sơ đồ Venn 
Câu hỏi: 
Hãy vẽ sơ đồ Venn của A  B 
Phép  được sử dụng trong logic như là phép toán Exclusive OR? 
Toán rời rạc 
Các đẳng thức tập hợp 
Các đẳng thức tập hợp tương tự như các đẳng thức logic. 
Các đẳng thức quan trọng: 
Đẳng thức 
Tên gọi 
A   = A 
A  U = A 
Đồng nhất 
(Identity laws) 
A  U = U 
A   =  
Trội 
(Domination laws) 
A  A = A 
A  A = A 
Đồng nhất 
Idempotent laws 
Bù (Complementation laws) 
Toán rời rạc 
Các đẳng thức tập hợp 
Tiếp theo: 
Đẳng thức 
Tên gọi 
A  B = B  A 
A  B = B  A 
Giao hoán 
Commutative laws 
A  ( B  C ) = ( A  B )  C 
A  ( B  C ) = ( A  B )  C 
Kết hợp 
Associative laws 
A  ( B  C ) = ( A  B )  ( A  C ) 
A  ( B  C ) = ( A  B )  ( A  C ) 
Phân phối 
Distributive laws 
Luật De Morgan 
De Morgan’s laws 
Toán rời rạc 
Chứng minh các đẳng thức tập hợp 
Để chứng minh đẳng thức tập hợp  A = B , 
 có thể sử dụng các kỹ thuật thường dùng sau: 
1. Chứng minh A  B và B  A . 
2. Sử dụng định nghĩa và sự tương đương của các mệnh đề logic xác định tập hợp. 
3. Sử dụng bảng quan hệ thành viên. 
Toán rời rạc 
Ví dụ 1. 
CM đẳng thức: A ( B  C )=( A  B )( A  C ). 
Phần 1: CM A ( B  C )( A  B )( A  C ). 
Giả sử x A ( B  C ), cần chỉ ra x ( A  B )( A  C ). 
Ta biết x A , và hoặc là x B hoặc là x C. 
TH 1: x B . Khi đó x A  B , vì thế x ( A  B )( A  C ). 
TH 2: x C. Khi đó x A  C , do đó x ( A  B )( A  C ). 
Suy ra, x ( A  B )( A  C ). 
Vậy A ( B  C )( A  B )( A  C ). 
Phần 2: CM ( A  B )( A  C )  A ( B  C ). (tương tự) 
Toán rời rạc 
Ví dụ 2 
Chứng minh rằng 
CM: 
Q.E.D. 
Toán rời rạc 
Bảng quan hệ thành viên 
Xây dựng bảng: 
Các cột ứng với các biểu thức tập hợp. 
Các dòng ứng với mọi tổ hợp có thể về quan hệ thành viên trong các tập đang xét. 
Điền vào bảng: 
Sử dụng “1” để ghi nhận là thành viên, “0” để chỉ ra không là thành viên. 
Đẳng thức là được chứng minh nếu hai cột tương ứng với hai biểu thức ở hai vế là giống hệt nhau . 
Toán rời rạc 
Ví dụ 3 
Chứng minh: ( A  B ) B = A B . 
Toán rời rạc 
Ví dụ 4 
Sử dụng bảng quan hệ thành viên, chứng minh rằng 
	A  (B  C) = (A  B)  (A  C) 
A B C 
B C 
A ( B C) 
A B 
A C 
( A B)( A C) 
1 1 1 
1 1 0 
1 0 1 
1 0 0 
0 1 1 
0 1 0 
0 0 1 
0 0 0 
1 
1 
1 
0 
1 
1 
1 
0 
Toán rời rạc 
Các đẳng thức tập hợp 
Ví dụ 5: 
Cho A , B , và C là các tập hợp. Chứng minh rằng 
CM: 
Toán rời rạc 
Hợp của nhiều tập 
Hợp của hai tập: A  B 
Hợp của n tập: A 1  A 2  A n  (((( A 1  A 2 ) ) A n ) (ghép nhóm và thứ tự là không quan trọng) 
Ký hiệu:  
Toán rời rạc 
Giao của nhiều tập 
Giao của hai tập: A  B 
Giao của n tập: A 1  A 2  A n  (((( A 1  A 2 )) A n ) (ghép nhóm và thứ tự là không quan trọng) 
Ký hiệu: 
Toán rời rạc 
Biểu diễn tập hợp bởi xâu nhị phân 
Đối với tập vũ trụ U = { x 1 , x 2 , , x n } gồm không quá nhiều phần tử. Ta có thể sử dụng biểu diễn tập S  U bởi xâu nhị phân b 1 b 2  b n trong đó 
 b i =1  x i S . 
Ví dụ. U = {1,...,11}. Xét các tập con S, T  U . 
S = {2,3,5,7,11}  01101010001. 
T = {1,2,4,11}  11010000001. 
Trong cách biểu diễn này các phép toán tập hợp , , được thực hiện nhờ phép toán logic OR, AND, NOT với từng bít! 
Ví dụ: S  T = 01101010001 
  11010000001 
 = 11111010001 
Toán rời rạc 
Phân hoạch 
Giả sử X 1 , X 2 , ..., X m là các tập con của X . Ta nói X 1 , X 2 , ..., X m tạo thành một phân hoạch của X (hoặc X được phân hoạch thành các tập X 1 , X 2 , ..., X m ) nếu: 
 X = X 1  X 2  ...  X m ; 
 X i  X j = , i j . 
ÁNH XẠ 
Định nghĩa 
Cách xác định ánh xạ 
Đơn ánh, toàn ánh, song ánh 
Fall 2008 
Toán rời rạc 
Toán rời rạc 
Ánh xạ 
Ta nói f là ánh xạ từ tập X vào tập Y nếu nó đặt tương ứng mỗi một phần tử x X với một phần tử y Y nào đó. 
Ký hiệu: f : X Y hoặc y = f ( x ) 
x gọi là gốc, y gọi là ảnh. 
Trong giáo trình giải tích chúng ta đã làm quen với hàm số thực f đặt tương ứng mỗi số thực x R với một giá trị thực y = f ( x ). 
Toán rời rạc 
Xác định ánh xạ 
Cho hai tập hữu hạn X và Y . 
Để xác định một ánh xạ f từ X vào Y ( f : X Y ) ta có thể sử dụng một trong các cách sau: 
Bảng giá trị đầy đủ 
Sơ đồ ánh xạ 
Ma trận ánh xạ 
Toán rời rạc 
Xác định ánh xạ: Bảng giá trị đầy đủ 
Giả sử 
X = { x 1 , x 2 ,..., x m }, Y = { y 1 , y 2 ,..., y n }, 
Một ánh xạ f từ X vào Y ( f : X Y ) có thể xác định bởi bảng giá trị đầy đủ sau đây 
x 
x 1 
x 2 
... 
x m 
y=f ( x ) 
f ( x 1 ) 
f ( x 2 ) 
... 
f ( x m ) 
Như vậy mỗi ánh xạ từ tập m phần tử X vào tập n phần tử Y hoàn toàn xác định bởi bộ ảnh 
( f ( x 1 ), f ( x 2 ), ..., f ( x m )) 
Toán rời rạc 
Sơ đồ ánh xạ 
Ánh xạ có thể xác định bởi sơ đồ như sau: 
• 
• 
X 
Y 
x 
y 
f 
f 
• 
• 
• 
• 
• 
• 
• 
• 
• 
x 
y 
Đồ thị hàm số 
Sơ đồ 
X 
Y 
Toán rời rạc 
Ma trận ánh xạ 
Giả sử 
X = { x 1 , x 2 ,..., x m }, 
Y = { y 1 , y 2 ,..., y n }, 
Một ánh xạ f từ X vào Y ( f : X Y ) có thể xác định bởi ma trận A f = { a ij } kích thước m n với các phần tử được xác định theo qui tắc sau đây: 
Toán rời rạc 
Ví dụ 
X = { Thắng, Mạnh, Hùng, Cường }; 
Y = { Mai, Mơ, Mận, Me, Muỗm } 
Xét ánh xạ f từ X vào Y xác định bởi bảng giá trị đầy đủ sau: 
x 
Thắng 
Mạnh 
Hùng 
Cường 
y=f(x) 
Mai 
Mai 
Mận 
Muỗm 
 Ánh xạ nói trên có thể cho bởi sơ đồ và ma trận như sau: 
Thắng 
Mạnh 
Hùng 
Cường 
Mai 
Mơ 
Mận 
Me 
Muỗm 
Thắng 
Mạnh 
Hùng 
Cường 
Toán rời rạc 
Một số loại ánh xạ hay dùng 
Xét 3 loại ánh xạ hay dùng 
Đơn ánh 
Toàn ánh 
Song ánh 
Giả sử X, Y là các tập hợp. 
Đơn ánh: Ánh xạ f : X Y được gọi là đơn ánh ( injection) nếu nó đặt tương ứng hai phần tử khác nhau của X với hai phần tử khác nhau của Y . 
 x 1 , x 2 X , x 1 x 2  f ( x 1 ) f ( x 2 ) 
Toán rời rạc 
Một số loại ánh xạ hay dùng 
Toàn ánh: Ánh xạ f từ X vào Y được gọi là toàn ánh ( surjection ) nếu mỗi phần tử của Y đều là ảnh của ít nhất một phần tử nào đó của X qua ánh xạ f . 
	  y Y ,  x X : y = f ( x ). 
Song ánh: Ánh xạ f từ X vào Y được gọi là song ánh ( bijection, one to one ) hay còn gọi là tương ứng 1-1( one-to-one correspondence ) , sánh , nếu nó vừa là đơn ánh vừa là toàn ánh. 
Toán rời rạc 
V í dụ 
Sơ đồ của một số ánh xạ: 
• 
• 
• 
• 
• 
• 
• 
• 
Song ánh 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Đơn ánh 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Toàn ánh 
Toán rời rạc 
Ứng dụng 
Xét bài toán: Đếm số phần tử của tập X . Giả sử Y là tập mà số phần tử của nó là đã biết:  n y = | Y |. Giả sử ta có thể xây dựng được ánh xạ f từ X vào Y . Khi đó 
Nếu f là đơn ánh, thì ta có | X | n y 
Nếu f là toàn ánh, thì ta có | X |  n y 
Nếu f là song ánh, thì ta có | X | = n y 
Trong tình huống thứ ba ta giải được bài toán đếm đặt ra, nhờ xây dựng được song ánh từ tập các cấu hình tổ hợp cần đếm (tập X ) vào tập các cấu hình tổ hợp mà ta đã biết trước số phần tử (tập Y ). 
Fall 2008 
Toán rời rạc 
Ví dụ 
Hỏi có bao nhiêu số có 5 chữ số mà mỗi chữ số đứng sau lại lớn hơn chữ số đứng trước? 
Giải: Mỗi một số cần đếm tương ứng với một cách chọn ra 5 chữ số từ 9 chữ số 1, 2, ..., 9, và ngược lại mỗi một cách lấy ra 5 chữ số từ 1, 2, ..., 9 sau khi sắp xếp theo thứ tự tăng dần cho ta đúng một số cần đếm. Vậy số lượng số cần đếm là C(9, 5). 
Lập luận tương tự ta cũng có số lượng số cần đếm chính bằng số cách loại bỏ 4 chữ số từ dãy 1 2 3 ... 9. Vậy số lượng số cần đếm là C(9, 4) 
Như vậy bằng lập luận tổ hợp ta đã chứng minh được C(9,5) = C(9,4). 
Toán rời rạc 
Ask questions! 
Toán rời rạc 
Toán rời rạc