zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:46

Báo xấu

216
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng môn học Toán rời rạc gồm 4 chương. Các nội dung chính của bài giảng bao gồm: Cơ sở logic, phép đếm, quan hệ, đại số Boole, hàm Boole, đồ thị. Mời bạn đọc tham khảo tài liệu để hiểu rõ hơn về các nội dung trên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng môn học Toán rời rạc - GV. Huỳnh Thị Thu Thủy

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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.