Bài giảng Môn học Toán rời rạc - Huỳnh Thị Thu Thủy

5/10/2013 1 Môn học: TOÁN RỜI RẠC Số Tiết LT: 45 Gv: Huỳnh Thị Thu Thủy Tài liệu tham khảo 1. Toán rời rạc ứng dụng trong tin học - Kenneth H. Rosen 2. Đại số quan hệ - Nguyễn Thanh Sơn Gv: Huỳnh Thị Thu Thủy 2 Nội dung 1. Chương 1: CƠ SỞ LOGIC 2. Chương 2: PHÉP ĐẾM 3. Chương 3: QUAN HỆ 4. Chương 4: ĐẠI SỐ BOOLE – HÀM BOOLE Gv: Huỳnh Thị Thu Thủy 3 5. Chương 5: ĐỒ THỊ Chương 1: CƠ SỞ LOGIC Gv: Huỳnh Thị Thu Thủy 4 5/10/2013 2 NỘI DUNG 1. Giới thiệu 2. Mệnh đề. 3. Các quy tắc suy diễn. 4 Vị từ - lượng từ Gv: Huỳnh Thị Thu Thủy 5 . . 5. Nguyên lý quy nạp. 1- Giới thiệu • Các qui tắc của logic cho biết ý nghĩa chính xác của các mệnh đề. • Ứng dụng các qui tắc logic trong tin học: – Thiết kế mạng máy tính Gv: Huỳnh Thị Thu Thủy 6 – Xây dựng chương trình máy tính – Kiểm tra tính đúng đắn của chương trình 2- Mệnh đề • Là câu đúng hoặc sai, không thể vừa đú ừ ing, v a sa • Ví dụ: – Mặt trời mọc ở phương Đông – 1+2 = 3 – 2+2 = 5 Gv: Huỳnh Thị Thu Thủy 7 • Những câu không là mệnh đề: – Bây giờ là mấy giờ? 2- Mệnh đề(tt) • Kí hiệu mệnh đề: – Dùng kí tự chữ cái. – Qui ước: p, q, r, s… • Các toán tử logic tác dụng đối với mệnh Gv: Huỳnh Thị Thu Thủy 8 đề: , , , , ,  5/10/2013 3 2- Mệnh đề(tt) • p  q: Đúng khi cả 2 đều đúng và sai trong các trường hợp còn lại. • p  q: Sai khi cả 2 đều sai và đúng trong các trường hợp còn lại. Gv: Huỳnh Thị Thu Thủy 9 • p  q: đúng khi 1 trong p và q là đúng và sai trong các trường hợp còn lại. 2- Mệnh đề(tt) • p  q: sai khi p đúng q sai, đúng trong các trường hợp còn lại • p  q: đúng khi p và q cùng chung giá trị chân lý, sai trong các trường hợp còn lại Gv: Huỳnh Thị Thu Thủy 10 2- Mệnh đề(tt) • Bảng chân trị cho các toán tử logic: p q p p  q pq p q p q pq T T T F Gv: Huỳnh Thị Thu Thủy 11 F T F F 2- Mệnh đề(tt) • Dịch câu thông thường thành biểu thức logic ế• Ví dụ: “Bạn không được lái xe máy n u bạn cao dưới 1,5m trừ khi bạn trên 18 tuổi”. • p: “Bạn được lái xe máy” • r: “Bạn cao dưới 1,5m” ổ Gv: Huỳnh Thị Thu Thủy 12 • s: “Bạn trên 18 tu i” Biểu thức logic: (r  s)  p 5/10/2013 4 2- Mệnh đề(tt) • Các phép toán trên bit: – OR, AND, XOR • Ví dụ: – 01101 10110 – 11000 11101 11101 11111 OR bit Gv: Huỳnh Thị Thu Thủy 13 – – 01000 10100 AND bit – 10101 01011 XOR bit Bài tập mệnh đề 1. Cho p và q là 2 mệnh đề: p: nhiệt độ dưới 0 q: tuyết rơi Dùng p, q và các liên từ logic viết các mệnh đề sau: a) Nhiệt độ dưới 0 và tuyết rơi Gv: Huỳnh Thị Thu Thủy 14 b) Có tuyết rơi hoặc nhiệt độ dưới 0 hoặc cả 2 c) Nếu nhiệt độ dưới 0 thì cũng có tuyết rơi Bài tập mệnh đề 2. Cho p, q và r là những mệnh đề: ốp: Bạn bị cúm ; q: Bạn bị trượt kỳ thi cu i khoá r: Bạn được lên lớp Hãy diễn đạt những mệnh đề sau thành câu thông thường: a) p  q Gv: Huỳnh Thị Thu Thủy 15 b) q r c) (p r ) (q r) Bài tập mệnh đề 3. Cho p và q là 2 mệnh đề: p: Bạn lái xe với tốc độ > 65 km/h q: Bạn bị phạt vì vượt quá tốc độ cho phép Dùng p, q và các liên từ logic viết các mệnh đề sau: a) Bạn không lái xe với tốc độ > 65 km/h b) Bạn lái xe với tốc độ > 65 km/h nhưng bạn ố Gv: Huỳnh Thị Thu Thủy 16 không bị phạt vì vượt quá t c độ cho phép c) Bạn sẽ bị phạt vì vượt quá tốc độ cho phép nếu bạn lái xe với tốc độ > 65 km/h 5/10/2013 5 Bài tập mệnh đề 4. Lập bảng chân lý cho các mệnh đề: a) p  p b) p  p c) p  q d) (p  q) q e) (p  q)  (p  q) Gv: Huỳnh Thị Thu Thủy 17 f) (p  q)  (q  p) g) p  q  r h) (p  q)  (p   q) Bài tập mệnh đề 5. Tìm các OR bit, AND bit, XOR bit của các cặp xâu bit sau: a) 1011110 ; 0100001 b) 11110000 ; 10101010 c) 0001110001 ; 1001001000 d) 1111111111 ; 0000000000 6. Xác định các biểu thức sau: Gv: Huỳnh Thị Thu Thủy 18 a) 11000  (01011  11011) b) (01111  10101)  01000 c) (01010  11011)  01000 3- Các qui tắc suy diễn • Một mệnh đề phức hợp mà luôn luôn đúng bất kể các giá trị chân lý của những mệnh đề thành phần của nó được gọi là hằng đúng. Gv: Huỳnh Thị Thu Thủy 19 • Một mệnh đề luôn sai: hằng sai. 3- Các qui tắc suy diễn(tt) • Các mệnh đề p và q được gọi là tương đương logic nếu p  q là hằng đúng. • Kí hiệu: p  q • Xác định 2 mệnh đề là tương đương logic: Gv: Huỳnh Thị Thu Thủy 20 – Bảng giá trị chân lý – Dùng các tương đương logic 5/10/2013 6 3- Các qui tắc suy diễn(tt) CÁC TƯƠNG ĐƯƠNG LOGIC Tương đương Tên gọi p T  L ật đồng nhất p p  F  p u p  T  T p  F  F Luật nuốt p  p  p Luật lũy đẳng Gv: Huỳnh Thị Thu Thủy 21 p  p  p  ( p)  p Luật phủ định kép p  q  q  p p  q  q  p Luật giao hoán 3- Các qui tắc suy diễn(tt) CÁC TƯƠNG ĐƯƠNG LOGIC (p  q)  r  p  (q  r) (p  q)  r  p  (q  r) Luật kết hợp p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) Luật phân phối Gv: Huỳnh Thị Thu Thủy 22  (p  q)   p   q  (p  q)   p   q Luật De Morgan 3- Các qui tắc suy diễn(tt) • Một số tương đương tiện ích: p   p  T p   p  F p  q  ( p  q) • Ví dụ: Gv: Huỳnh Thị Thu Thủy 23 – CMR: (p  ( p  q ))   p  q – CMR: (p  q)  (p  q) là hằng đúng Bài tập các qui tắc suy diễn 1. Dùng bảng chân lý, CM các tương đương sau: a) p  T  p b) p  F  p c) p  F  F d) p  T  T ) Gv: Huỳnh Thị Thu Thủy 24 e p  p  p f) p  p  p g) (pq)  (p   q) 5/10/2013 7 Bài tập các qui tắc suy diễn 2. CM các mệnh đề kéo theo sau là hằng đúng: a) (p  q ) p b) p  (p  q) c)  p  (p  q) d) (p  q) (p q) Gv: Huỳnh Thị Thu Thủy 25 e)  (p  q)   q f) [p (p  q)]  q Bài tập các qui tắc suy diễn 3. CM các mệnh đề sau là tương đương: a) p  q và q  p b)  p  q và p   q c)  (p  q) và p  q d)  (p  q) và  p  q 4 Xác định mệnh đề sau có là hằng đúng Gv: Huỳnh Thị Thu Thủy 26 . không: ( p  (p  q))   q 4- Vị từ - Lượng từ • Vị từ: – Là hàm nhận giá trị đúng hoặc sai tùy thuộc hàm tác dụng vào cá thể nào. – VD: VN(x): “x là người Việt nam”. – Boolean Gv: Huỳnh Thị Thu Thủy 27 4- Vị từ - Lượng từ (tt) • Lượng từ: – Lượng từ “với mọi” của P(x) là mệnh đề P(x) đúng với mọi giá trị của x trong không gian”. – Kí hiệu: x P(x) – VD: “Tất cả sinh viên ở lớp này đều đã học Gv: Huỳnh Thị Thu Thủy 28 giải tích”. • P(x) kí hiệu cho câu: “x đã học giải tích”. • Khi đó: x P(x) 5/10/2013 8 4- Vị từ - Lượng từ (tt) – Lượng từ “tồn tại” của P(x) là mệnh đề “Tồn tại một phần tử x trong không gian sao cho P(x) là đúng”. – Kí hiệu: x P(x) – VD: Cho câu P(x): “x>3”. Gv: Huỳnh Thị Thu Thủy 29 • Tìm giá trị chân lý của x P(x) với không gian là tập số thực? 4- Vị từ - Lượng từ (tt) • Dịch câu thông thường thành biểu thức logic – VD1: “Mọi người đều có chính xác một người bạn tốt nhất.” Giải: B(x,y): “y là bạn tốt nhất của x”. Gv: Huỳnh Thị Thu Thủy 30  x y z [ B(x,y)  (z ≠ y)  B(x,z) ] 4- Vị từ - Lượng từ (tt) • VD2: “Tất cả sư tử đều hung dữ”– . – “Một số sư tử không uống cà phê”. – “Một số sinh vật hung dữ không uống cà phê”. Giải: Đặt P(x): “x là sư tử”; Q(x): “x hung dữ”; R(x): “x uống cà phê” Gv: Huỳnh Thị Thu Thủy 31 x ( P(x)  Q(x) ) x ( P(x)   R(x) ) x ( Q(x)   R(x) ) 5- Nguyên lý quy nạp • Quy nạp toán học – Dùng để chứng minh mệnh đề dạng nP(n) – Quá trình chứng minh bao gồm: 1. Bước cơ sở: Chỉ ra mệnh đề P(1) là đúng. 2 Bước quy nạp: CM phép kéo theo: Gv: Huỳnh Thị Thu Thủy 32 . P(n)  P(n+1) đúng với mọi số nguyên dương n. Với P(n) là giả thiết quy nạp. 5/10/2013 9 5- Nguyên lý quy nạp (tt) • VD: Bằng quy nạp toán học, hãy CM: 1. “Tổng n số nguyên dương lẻ đầu tiên là n2”. 2. “n < 2n với mọi số nguyên dương n”. 3. “n3 – n chia hết cho 3 n nguyên dương”. 4 “1+2+22+ +2n 2n+1 1 n nguyên không âm” Gv: Huỳnh Thị Thu Thủy 33 . ... = – . 5. “1+2+3+…+n = [n(n+1)] / 2, n nguyên dương”. 6. “2n < n!, n nguyên n  4”. TỔNG KẾT CHƯƠNG 1 1. Giới thiệu. 2. Mệnh đề. 3. Các quy tắc suy diễn. 4 Vị từ - lượng từ Gv: Huỳnh Thị Thu Thủy 34 . . 5. Nguyên lý quy nạp. Chương 2: PHÉP ĐẾM Gv: Huỳnh Thị Thu Thủy 35 NỘI DUNG 1. Lý thuyết tập hợp và ánh xạ 2. Phép đếm. 3. Giải tích tổ hợp. 4 Nguyên lý Dirichlet Gv: Huỳnh Thị Thu Thủy 36 . . 5/10/2013 10 1- Lý thuyết tập hợp và ánh xạ • Định nghĩa 1: – Các đối tượng trong 1 tập hợp được gọi là các phần tử của tập hợp – VD: Tập V của tất cả các nguyên âm trong Gv: Huỳnh Thị Thu Thủy 37 bảng chữ cái tiếng Anh. – V={ a, e, i, o, u } 1- Lý thuyết tập hợp và ánh xạ(tt) • Định nghĩa 2: – Hai tập hợp là bằng nhau nếu và chỉ nếu chúng có cùng các phần tử. – VD: Gv: Huỳnh Thị Thu Thủy 38 • Các tập {1,3,5} và {3,5,1} là bằng nhau. • Các tập {1,3,3,3,5,5,5} và {1,3,5} là bằng nhau. 1- Lý thuyết tập hợp và ánh xạ(tt) • Một cách khác để mô tả các tập hợp: – Chỉ rõ các thuộc tính đặc trưng của các phần tử thuộc tập hợp đó. – Ví dụ: Tập O của tất cả các số nguyên dương lẻ và nhỏ Gv: Huỳnh Thị Thu Thủy 39 • hơn 10 có thể viết như sau: • O = { x / x là số nguyên dương lẻ nhỏ hơn 10} 1- Lý thuyết tập hợp và ánh xạ(tt) • Định nghĩa 3: Tập A được gọi là tập con của B nếu và chỉ– nếu mỗi phần tử của A đều là 1 phần tử của B. – Kí hiệu: A  B – Ví dụ: A { / là ố ê d } Gv: Huỳnh Thị Thu Thủy 40 = x x s nguy n ương B={x/ x là số nguyên tố không vượt quá 100 A ? B 5/10/2013 11 1- Lý thuyết tập hợp và ánh xạ(tt) • Định nghĩa 4: ế– Cho S là một tập hợp. N u có chính xác n phần tử phân biệt trong S, với n là số nguyên không âm, thì ta nói rằng S là một tập hữu hạn và n là bản số của S. – Bản số của S kí hiệu: |S| ỗ ầ Gv: Huỳnh Thị Thu Thủy 41 – Ví dụ: Tập r ng không chứa ph n tử  ||=0 A={ 1,2,3,1,2,3,4,5} ; B= {1,{2,3},{1,2,3},4,5} |A|= ? |B|= ? 1- Lý thuyết tập hợp và ánh xạ(tt) • Định nghĩa 5: ế– Một tập được nói là vô hạn n u nó không phải là hữu hạn. – Ví dụ: Tập hợp các số nguyên dương là tập vô hạn. Gv: Huỳnh Thị Thu Thủy 42 1- Lý thuyết tập hợp và ánh xạ(tt) • Định nghĩa 6: ấ– Cho tập S, tập lũy thừa của S là tập của t t cả các tập con của S. – Tập lũy thừa của S được kí hiệu: P(S) – Ví dụ: • Xác định tập lũy thừa của tập {0,1,2}. Gv: Huỳnh Thị Thu Thủy 43 • P({0,1,2}) = {,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}} • Cho S={a,b,c} • Tìm P(S)=? 1- Lý thuyết tập hợp và ánh xạ(tt) • Định nghĩa 7: ề– Cho A và B là hai tập hợp. Tích đ các của A và B là tập hợp của tất cả các cặp (a,b) với aA và bB. – Kí hiệu: A x B – Ví dụ: A={1,2} ; B={a,b,c} Gv: Huỳnh Thị Thu Thủy 44 AxB={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)} BxA=? 5/10/2013 12 1- Lý thuyết tập hợp và ánh xạ(tt) • Định nghĩa 8: ề– Tích đ các của các tập A1, A2, .., An là tập hợp của các dãy sắp thứ tự (a1, a2,..,an) với aiAi (i=1,2,..,n) – Kí hiệu: A1 x A2 x..x An={(a1, a2,..,an)| aiAi (i=1,2,..,n)} Gv: Huỳnh Thị Thu Thủy 45 Bài tập 1. Liệt kê các phần tử của tập hợp sau: ốo S1={x| x là s thực và x2=1} o S2={x| x là bình phương của 1 số nguyên và x <100} 2. Cho biết mỗi mệnh đề sau là Đúng /sai: o {0}  {0} o {0}  {0} o   {a,b,c} Gv: Huỳnh Thị Thu Thủy 46 Bài tập 3. Liệt kê các phần tử của tập lũy thừa của S: o S={a,b} o S={a,{a}} 4. Cho biết bản số của tập hợp sau: o S={a a b b }, 1, , 1 o S={a,{a,b},a,{a,b}} o S={a,{a},{{a}},{a,b}} Gv: Huỳnh Thị Thu Thủy 47 2- Phép đếm • Quy tắc cộng: Giả sử có 2 công việc. – Công việc thứ 1 có thể làm bằng n1 cách – Công việc thứ 2 có thể làm bằng n2 cách – Và nếu 2 việc này không thể làm đồng thời Gv: Huỳnh Thị Thu Thủy 48 – Khi đó sẽ có n1+n2 cách làm 1 trong 2 công việc đó 5/10/2013 13 2- Phép đếm (tt) • Ví dụ: ầ– Giả sử c n chọn hoặc là 1 cán bộ của khoa Toán hoặc 1 sinh viên Toán làm đại biểu trong hội đồng của 1 trường Đại học. – Hỏi có bao nhiêu cách chọn vị đại biểu này nếu khoa Toán có 27 cán bộ và 83 sinh viên. Gv: Huỳnh Thị Thu Thủy 49 2- Phép đếm (tt) • Quy tắc cộng mở rộng (trong trường hợp ó hiề h 2 ô iệ )c n u ơn c ng v c : – Giả sử các việc T1, T2,..,Tm có thể làm tương ứng bằng n1, n2, ..,nm cách và giả sử không có 2 công việc nào có thể làm đồng thời. – Khi đó số cách làm 1 trong m công việc đó là Gv: Huỳnh Thị Thu Thủy 50 n1 + n2 + ...+ nm 2- Phép đếm (tt) • Ví dụ: ể– Một sinh viên có th chọn bài thực hành máy tính từ 1 trong 3 danh sách tương ứng có 24,15,19 bài. – Hỏi, có bao nhiêu cách chọn bài thực hành? Gv: Huỳnh Thị Thu Thủy 51 2- Phép đếm (tt) • Quy tắc nhân: Giả sử một nhiệm vụ nào đó được tách làm 2 công việc . – Việc thứ 1 có thể làm bằng n1 cách. – Việc thứ 2 có thể làm bằng n2 cách sau khi việc thứ 1 đã được làm. – Khi đó sẽ có n1.n2 cách thực hiện nhiệm vụ Gv: Huỳnh Thị Thu Thủy 52 này. 5/10/2013 14 2- Phép đếm (tt) • Ví dụ 1: ể ế– Người ta có th ghi nhãn cho những chi c ghế trong 1 giảng đường bằng 1 chữ cái và 1 số nguyên dương không vượt quá 100 – Hỏi nhiều nhất có bao nhiêu chiếc ghế được ghi nhãn khác nhau. Gv: Huỳnh Thị Thu Thủy 53 2- Phép đếm (tt) • Ví dụ 2: ế– Trong trung tâm máy tính có 32 chi c máy vi tính. – Mỗi máy có 14 cổng. – Hỏi có bao nhiêu cổng khác nhau trong trung tâm này. Gv: Huỳnh Thị Thu Thủy 54 2- Phép đếm (tt) • Ví dụ 3: – Có bao nhiêu xâu nhị phân có độ dài 7? Gv: Huỳnh Thị Thu Thủy 55 2- Phép đếm (tt) • Ví dụ 4: Có nhiều nhất bao nhiêu biển đă ký ô tô ế ỗi biể hứ ộtng xe n u m n c a m dãy 2 chữ cái tiếp sau là 3 chữ số (không bỏ dãy chữ nào cả)? Gv: Huỳnh Thị Thu Thủy 56 5/10/2013 15 2- Phép đếm (tt) • Quy tắc nhân mở rộng: Giả sử 1 nhiệm à đó đ thi hà h bằ á h thvụ n o ược n ng c c ực hiện các việc T1, T2, … , Tm. – Nếu việc Ti có thể làm bằng ni cách sau khi các việc T1, T2, … , Ti-1 đã được làm. – Khi đó có n1x n2x …x nm cách thi hành các Gv: Huỳnh Thị Thu Thủy 57 nhiệm vụ đã cho. 2- Phép đếm (tt) • Nguyên lý bù trừ: ể ồ– Khi 2 công việc (CV) có th được làm đ ng thời. Ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả 2 việc. – Số cách thực hiện nhiệm vụ: Cộng số cách làm mỗi 1 trong 2 CV trừ đi số cách làm đồng thời ả 2 CV N ê lý bù t ừ Gv: Huỳnh Thị Thu Thủy 58 c guy n r 2- Phép đếm (tt) • Ví dụ: – Có bao nhiêu xâu nhị phân có độ dài 8 bít hoặc được bắt đầu bằng bít 1 hoặc kết thúc bằng 2 bít 00? Gv: Huỳnh Thị Thu Thủy 59 Bài tập 1. Một phiếu trắc nghiệm đa lựa chọn gồm 10 â hỏi Mỗi â hỏi ó 4 h á c u . c u c p ương n trả lời. a) Có bao nhiêu cách điền 1 phiếu trắc nghiệm nếu mọi câu hỏi đều được trả lời? b) Có bao nhiêu cách điền 1 phiếu trắc nghiệm Gv: Huỳnh Thị Thu Thủy 60 nếu có thể bỏ trống? 5/10/2013 16 Bài tập 2. Từ NewYork đến Denver có 6 hãng hàng khô à ó 7 hã b từ D đếng v c ng ay enver n San Francisco. Có bao nhiêu khả năng khác nhau để bay từ NewYork đến San Francisco qua Denver? 3. Có bao nhiêu người có tên họ viết tắt Gv: Huỳnh Thị Thu Thủy 61 bằng 3 chữ cái khác nhau?( CÁC chữ cái có thể lặp lại) Bài tập 4. Có bao nhiêu người có tên họ viết tắt bằ 3 hữ ái khá h t đóng c c c n au rong không chữ cái nào được lặp lại? 5. Có bao nhiêu xâu nhị phân có độ dài bằng 16, có bít đầu tiên và bít cuối cùng là 1? Gv: Huỳnh Thị Thu Thủy 62 6. Có bao nhiêu xâu nhị phân có độ dài bằng 6 hoặc ít hơn? Bài tập 7. Có bao nhiêu xâu chữ thường có độ dài bằ 4 à hứ 1 hữ ?ng v c a c x 8. Có bao nhiêu xâu chữ thường có độ dài bằng 4 hoặc ít hơn (tính cả xâu rỗng)? 9. Trong các số nguyên dương có đúng 3 chữ số có bao nhiêu số: Gv: Huỳnh Thị Thu Thủy 63 , a) Lẻ? b) Có 3 chữ số như nhau? Bài tập 10.Có bao nhiêu xâu gồm 3 chữ số thập phân: a) Không chứa cùng 1 chữ số 3 lần? b) Bắt đầu bằng chữ số lẻ? c) Có đúng 2 chữ số 4? 11.Có bao nhiêu xâu gồm 4 chữ số thập hâ Gv: Huỳnh Thị Thu Thủy 64 p n: a) Không chứa cùng 1 chữ số 2 lần? b) Kết thúc bằng chữ số chẵn(0?)? 5/10/2013 17 3- Giải tích tổ hợp • Hoán vị: ố– Hoán vị của 1 tập các đ i tượng khác nhau là một cách sắp xếp có thứ tự các đối tượng này. • Ví dụ: S = { 1, 2, 3 } – Cách sắp xếp 3,2,1 là 1 hoán vị của S. Gv: Huỳnh Thị Thu Thủy 65 3- Giải tích tổ hợp (tt) • Chỉnh hợp: ắ ế ầ– Một cách s p x p có thứ tự r ph n tử của 1 tập n phần tử được gọi là 1 chỉnh hợp chập r của n phần tử.(r<=n) • Ví dụ: S = { 1, 2, 3 } – Cách sắp xếp 3,2 là 1 chỉnh hợp chập 2 của Gv: Huỳnh Thị Thu Thủy 66 S. 3- Giải tích tổ hợp (tt) • Định lý 1: ố ầ– S chỉnh hợp chập r của tập S có n ph n tử là: – Đặc biệt: )!( !),( rn nrnP  Gv: Huỳnh Thị Thu Thủy 67 !),( nnnP  3- Giải tích tổ hợp (tt) • Ví dụ 1: ầ– Có bao nhiêu cách chọn 4 c u thủ khác nhau trong 10 cầu thủ của đội bóng quần vợt để chơi 4 trận đấu đơn. – Các trận đấu là có thứ tự. Gv: Huỳnh Thị Thu Thủy 68 5/10/2013 18 3- Giải tích tổ hợp (tt) • Ví dụ 2: Giả sử có 8 vận động viên chạy thi. ắ– Người th ng sẽ nhận được huy chương vàng. – Người về đích thứ 2 nhận huy chương bạc. – Người về đích thứ 3 nhận huy chương đồng. – Có bao nhiêu cách trao các huy chương này nếu các kết cục của cuộc thi đều có thể xảy ra? Gv: Huỳnh Thị Thu Thủy 69 3- Giải tích tổ hợp (tt) • Ví dụ 3:Giả sử một thương nhân định đi bán hà t i 8 thà h hống ạ n p . – Anh ta bắt đầu cuộc hành trình của mình tại 1 thành phố nào đó nhưng có thể đến 7 thành phố kia theo bất kỳ thứ tự nào mà anh ta muốn. – Hỏi, anh ta có thể đi qua tất cả các thành phố Gv: Huỳnh Thị Thu Thủy 70 này theo bao nhiêu lộ trình khác nhau? 3- Giải tích tổ hợp (tt) • Tổ hợp: ổ– Một t hợp chập r của một tập hợp là 1 cách chọn không có thứ tự r phần tử của tập hợp đã cho. – Vậy, 1 tổ hợp chập r chính là 1 tập con r phần tử của tập ban đầu. Gv: Huỳnh Thị Thu Thủy 71 3- Giải tích tổ hợp (tt) • Ví dụ: Cho S là tập {1, 2, 3, 4 } ổ– Khi đó {1, 3, 4} là 1 t hợp chập 3 của S. • Số tổ hợp chập r của tập n phần tử: C(n,r) Gv: Huỳnh Thị Thu Thủy 72 5/10/2013 19 3- Giải tích tổ hợp (tt) • Định lý 2: – Số tổ hợp chập r từ tập có n phần tử trong đó n là số nguyên dương và r là số nguyên với 0≤ r ≤ n được cho bởi công thức sau: Gv: Huỳnh Thị Thu Thủy 73 3- Giải tích tổ hợp (tt) • Hệ quả 1: – Cho n và r là các số nguyên không âm sao cho r ≤ n. Khi đó: C(n, r) = C(n, n-r) Gv: Huỳnh Thị Thu Thủy 74 3- Giải tích tổ hợp (tt) • Ví dụ: ể ố ầ– Có bao nhiêu cách tuy n 5 trong s 10 c u thủ của 1 đội bóng quần vợt để đi thi đấu tại một trường khác? Gv: Huỳnh Thị Thu Thủy 75 Bài tập giải tích tổ hợp 1. Có bao nhiêu thứ tự có thể xảy ra trong cuộc thi chạy giữa 5 vận động viên . 2. Một nhóm sinh viên gồm n nam, n nữ. Có bao nhiêu cách xếp thành 1 hàng sao cho nam và nữ đứng xen nhau? 3. Có bao nhiêu cách chọn 1 tập hợp 2 số ê d khô t á 100? Gv: Huỳnh Thị Thu Thủy 76 nguy n ương ng vượ qu 4. Có bao nhiêu cách chọn 1 tập hợp 5 chữ cái từ bảng chữ cái tiếng Anh? 5/10/2013 20 4- Nguyên lý Dirichlet • Định lý 1( Nguyên lý lồng chim bồ câu): – Nếu có K+1 hoặc nhiều hơn đồ vật được đặt trong K hộp thì có ít nhất 1 hộp chứa 2 hoặc nhiều hơn 2 đồ vật. Gv: Huỳnh Thị Thu Thủy 77 4- Nguyên lý Dirichlet (tt) • Ví dụ 1: ấ– Một nhóm b t kỳ có 367 người. – Chắc chắn có ít nhất 2 người trùng ngày sinh. – Vì? Gv: Huỳnh Thị Thu Thủy 78 4- Nguyên lý Dirichlet (tt) • Ví dụ 2: ấ ế–Cho 1 nhóm b t kỳ có 27 từ ti ng Anh. –Chắc chắn có ít nhất 2 từ bắt đầu bằng cùng 1 chữ cái. –Vì? Gv: Huỳnh Thị Thu Thủy 79 4- Nguyên lý Dirichlet (tt) • Ví dụ 3: – Bài thi các môn học trong 1 trường Đại học được chấm theo thang điểm là các số nguyên từ 0 100. – Một lớp học cần phải có bao nhiêu sinh viên để đảm bảo trong mọi môn thi đều có ít nhất 2 Gv: Huỳnh Thị Thu Thủy 80 sinh viên cùng điểm thi? 5/10/2013 21 4- Nguyên lý Dirichlet (tt) • Định lý 2 (Nguyên lý Dirichlet tổng quát): – Nếu có N đồ vật được đặt vào trong K hộp, sẽ tồn tại một hộp chứa ít nhất vật.   K N Gv: Huỳnh Thị Thu Thủy 81 4- Nguyên lý Dirichlet (tt) • Ví dụ1: ấ  – Trong 100 ngườ