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

y 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ười sẽ có ít nh t 100/12 = 9 người cùng tháng sinh . Gv: Huỳnh Thị Thu Thủy 82 4- Nguyên lý Dirichlet (tt) • Ví dụ 2: – Cần phải có tối thiểu bao nhiêu sinh viên ghi tên vào lớp toán học rời rạc để chắc chắn rằng sẽ có ít nhất 6 người đạt cùng 1 điểm thi? – Nếu thang điểm gồm 5 bậc A, B, C, D và F. Gv: Huỳnh Thị Thu Thủy 83 4- Nguyên lý Dirichlet (tt) • Ví dụ 3: Số ã ù ầ thiết hỏ hất hải là– m v ng c n n n p bao nhiêu để đảm bảo 25 triệu máy điện thoại trong 1 bang có số điện thoại khác nhau. –Mỗi số gồm 10 chữ số. (Giả sử số điện Gv: Huỳnh Thị Thu Thủy 84 thoại có dạng NXX-NXX-XXXX. Trong đó 3 chữ số đầu tiên là mã vùng; N: 2..9 ; X: 0..9. 5/10/2013 22 Bài tập nguyên lý Dirichlet 1. Một ngăn tủ có chứa 1 tá chiếc tất màu nâu và 1 tá chiếc tất màu đen. Một người lấy các chiếc tất một cách ngẫu nhiên trong bóng tối. Anh ta cần phải lấy ra bao ế ấ ể ắ ắ ằ Gv: Huỳnh Thị Thu Thủy 85 nhiêu chi c t t đ ch c ch n r ng mình có ít nhất 2 chiếc tất cùng màu? Bài tập nguyên lý Dirichlet 2 Mỗi 1 sinh viên trong 1 trường đại. học đều có quê ở 1 trong 50 bang. Cần phải tuyển bao nhiêu sinh viên để đảm bảo có ít nhất 100 người Gv: Huỳnh Thị Thu Thủy 86 cùng bang? Bài tập nguyên lý Dirichlet 3. Một công ty giữ hàng hoá trong kho. Số các ở ốngăn chứa trong kho được xác định b i s gian hàng, số ô trong mỗi gian và số các giá ở mỗi ô. Biết nhà kho có 50 gian, mỗi gian có 80 ô, mỗi Gv: Huỳnh Thị Thu Thủy 87 ô có 5 giá. Hỏi hàng hoá phải tối thiểu bằng bao nhiêu để ít nhất có 2 sản phẩm được đặt trong cùng 1 ngăn? TỔNG KẾT CHƯƠNG 2 1. Nhắc lại 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 88 . . 5/10/2013 23 Chương 3: QUAN HỆ Gv: Huỳnh Thị Thu Thủy 89 NỘI DUNG 1. Định nghĩa 2. Quan hệ hai ngôi 3. Các tính chất của quan hệ 4. Quan hệ tương đương Gv: Huỳnh Thị Thu Thủy 90 5. Quan hệ thứ tự 1- Định nghĩa • Định nghĩa quan hệ: – Là một cách thức biểu diễn sự liên kết giữa những tập hợp. – Trường hợp đặc biệt của sự liên kết này là kết nối giữa các phần tử trong cùng 1 tập hợp Gv: Huỳnh Thị Thu Thủy 91 . 2- Quan hệ hai ngôi • Định nghĩa – Cho A và B là các tập hợp. Một quan hệ 2 ngôi từ A đến B là một tập con của A x B. • Kí hiệu: R  A x B – Phần tử (x,y) của quan hệ R có thể được biểu Gv: Huỳnh Thị Thu Thủy 92 diễn: (x,y)  R, hay xRy 5/10/2013 24 2- Quan hệ hai ngôi (tt) • Ví dụ: – Cho S={PhạmThái, CaoBáNhạ, PhạmThiênThư, NguyễnDu} – T= {ĐoạnTrườngVôThanh, TựTìnhKhúc, SơKínhTânTrang, ChiếnTụngTâyHồPhú, ChinhPhụNgâm} – R={ (PhạmThái, Sơkínhtântrang), (CaoBáNhạ, Gv: Huỳnh Thị Thu Thủy 93 Tựtìnhkhúc), (PhạmThiênThư, Đoạntrườngvôthanh), (PhạmThái, Chiếntụngtâyhồphú) } – Quan hệ R là quan hệ 2 ngôi: “là tác giả của tác phẩm” 3- Các tính chất của quan hệ • Tính phản xạ (tính chất phản hồi)-reflexive: – Quan hệ R trên tập A được gọi là có tính phản xạ nếu (a,a)  R với mọi phần tử a  A. – Ví dụ: Xét các quan hệ trên tập {1,2,3,4} • R1= {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)} Gv: Huỳnh Thị Thu Thủy 94 • R2={(1,1),(1,2),(2,1)} • R3={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)} • R4={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)} Quan hệ nào có tính phản xạ? 3- Các tính chất của quan hệ (tt) • Tính đối xứng - symmetric: – Quan hệ R trên tập A được gọi là đối xứng nếu (b,a)  R khi (a,b)  R với a,b  A. – Quan hệ R trên tập A sao cho (a,b)  R và (b,a)  R chỉ nếu a=b, với a,b  A được gọi là Gv: Huỳnh Thị Thu Thủy 95 phản đối xứng-antisymmetric. – Ví dụ: R = { (1,1),(1,2),(2,1) } 3- Các tính chất của quan hệ (tt) • Tính bắc cầu (tính chất truyền)-transitive: – Một quan hệ R trên tập A được gọi là có tính chất bắc cầu nếu (a,b)  R và (b,c)  R thì (a,c)  R với a,b,c  A. – Ví dụ: Gv: Huỳnh Thị Thu Thủy 96 • R1= {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)} • R2={(1,1),(1,2),(2,1)} • R3={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)} Quan hệ nào có tính bắc cầu? 5/10/2013 25 4- Quan hệ tương đương • Quan hệ R của SxS còn được gọi là quan hệ cấp 2. • Quan hệ cấp hai R là quan hệ tương đương nếu có các tính chất: – Phản xạ Gv: Huỳnh Thị Thu Thủy 97 – Đối xứng – Bắc cầu 4- Quan hệ tương đương(tt) • Ví dụ: – Cho tập X={a,b,c,d,e} – Quan hệ R trên tập X: R={(a,b),(a,c), (a,e), (b,c), (c,a), (e,a), (c,b), (b,e), (b,a), (e,b), (a,a), (b,b), (c c) (d d) (e e)} Gv: Huỳnh Thị Thu Thủy 98 , , , , , - R là quan hệ tương đương? 5- Quan hệ thứ tự • Quan hệ cấp hai P là quan hệ thứ tự nếu thõa các tính chất: – Phản xạ – Phản đối xứng – Bắc cầu Gv: Huỳnh Thị Thu Thủy 99 • Một tập X có một quan hệ thứ tự thì X được gọi là tập hợp thứ tự. 5- Quan hệ thứ tự (tt) • Ví dụ: – X={1,2,3,4,5,6,7,8} – R={(1,1),(2,2),(1,2),(6,1),(6,2),(3,5),(8,7),(3,3), (4,4),(5,5),(6,6),(7,7),(8,8)} là quan hệ trên X. – Dễ dàng kiểm tra quan hệ R là quan hệ thứ Gv: Huỳnh Thị Thu Thủy 100 tự. 5/10/2013 26 5- Quan hệ thứ tự (tt) • Quan hệ thứ tự toàn phần: Quan hệ thứ tự P là quan hệ toàn phần nếu:– (x,y) ( ((x,y)  P)  ((y,x)  P) ) • Ví dụ: – X={1,2,3,4} P {(2 3) (2 4) (2 1) (3 4) (3 1) (4 1) (1 1) (2 2) Gv: Huỳnh Thị Thu Thủy 101 – = , , , , , , , , , , , , , , , , (3,3),(4,4)} – Quan hệ P là quan hệ thứ tự toàn phần. 5- Quan hệ thứ tự (tt) • Quan hệ thứ tự riêng phần: – Quan hệ thứ tự không toàn phần được gọi là quan hệ thứ tự riêng phần. Đơn giản gọi là quan hệ thứ tự. (x,y) ( ((x,y)  P)  ((y,x)  P) ) • Ví dụ: X={1,2,3,4} R {(2 3) (3 4) (3 1) (4 1) (1 1) (2 2) (3 3) (4 4)} Gv: Huỳnh Thị Thu Thủy 102 – = , , , , , , , , , , , , , , , – Quan hệ R là quan hệ thứ tự hay quan hệ thứ tự riêng phần. Bài tập chương 3 1/. Cho biết quan hệ sau là quan hệ tương đương hay không, giải thích: a- Cho tập X={a,b,c,d,e} Quan hệ R trên tập X: R={(a,b),(a,c), (a,e), (b,c), (c,a), (e,a), (c,b), (b,e), (b,a), (e,b), (a,a), (b,b), (c,c),(d,d),(e,e)} b Ch tậ X { d f}- o p = a,c, ,e, Quan hệ R trên tập X: R={(a,c),(c,d),(c,e), (a,d),(d,a),(d,e), (c,a), (a,e),(e,a), (e,c), (e,d), (d,c), (c,c), (d,d), (e,e), (f,f), (a,a)} Gv: Huỳnh Thị Thu Thủy 103 Bài tập chương 3 2/. Cho biết quan hệ sau là quan hệ thứ tự hay không, ảgi i thích: a- Cho tập X={a,b,c,d,e} Quan hệ R trên tập X: R={(a,b), (a,c), (a,e), (b,c), (d,b), (b,e), (a,a), (b,b), (c,c),(d,d),(e,e)} b- Cho tập X={a,c,d,e,f} Quan hệ R trên tập X: R={(a,c),(c,d),(c,e), (a,d), (d,e), (a,e),(e,c),(e,d), (c,c), (d,d), (e,e), (f,f), (a,a)} Gv: Huỳnh Thị Thu Thủy 104 5/10/2013 27 Bài tập chương 3 3/. Hãy liệt kê các phần tử thuộc quan hệ thứ tự R được mô tả bởi dàn sau: Gv: Huỳnh Thị Thu Thủy 105 TỔNG KẾT CHƯƠNG 3 1. Định nghĩa 2. Quan hệ hai ngôi. 3. Các tính chất của quan hệ 4. Quan hệ tương đương. Gv: Huỳnh Thị Thu Thủy 106 5. Quan hệ thứ tự. Chương 4: ĐẠI SỐ BOOLE – HÀM BOOLE Gv: Huỳnh Thị Thu Thủy 107 NỘI DUNG 1. Đại số Boole 2. Biểu thức Boole và hàm Boole 3. Các hằng đẳng thức của đại số Boole 4. Tính đối ngẫu 5. Các cổng logic 6. Bộ cộng Gv: Huỳnh Thị Thu Thủy 108 7. Tối tiểu hoá hàm Boole 5/10/2013 28 1- Đại số Boole –Đại số Boole đưa ra các phép toán và i tắ là iệ ới tậ {0 1}qu c m v c v p , –Các chuyển mạch điện tử và quang học có thể được nghiên cứu bằng cách dùng tập này và các qui tắc của đại số Boole. Gv: Huỳnh Thị Thu Thủy 109 1- Đại số Boole (tt) • Ba phép toán trong đại số Boole mà ta sẽ dù hiề hấtng n u n : – Phép lấy phần bù – Phép lấy tổng Boole – Phép lấy tích Boole • Phần bù của 1 phần tử được kí hiệu Gv: Huỳnh Thị Thu Thủy 110 bằng 1 gạch ngang trên đầu 1- Đại số Boole (tt) • Phần bù của 1 phần tử được kí hiệu bằ 1 h t ê đầng gạc ngang r n u. • Phần bù được định nghĩa bởi: Gv: Huỳnh Thị Thu Thủy 111 1- Đại số Boole (tt) • Tổng Boole được kí hiệu là + hoặc OR (hoặc) có các giá trị sau: 1+1=1 ; 1+0=1 ; 0+1=1 ; 0+0=0 • Tích Boole được kí hiệu là . hoặc AND (và) có các giá trị sau: Gv: Huỳnh Thị Thu Thủy 112 1.1=1 ; 1.0=0 ; 0.1=0 ; 0.0=0 • VD: Tìm giá trị của 1.0 + (0 + 1) 5/10/2013 29 2- Biểu thức Boole và hàm Boole • Cho B={0,1}. ế ế ế• Bi n x được gọi là bi n Boole n u nó nhận các giá trị chỉ từ B. • Một hàm từ Bn tức là từ tập {(x1,x2,..,xn)/xiB, 1in} tới B được gọi là hàm Boole bậc n Gv: Huỳnh Thị Thu Thủy 113 . 2- Biểu thức Boole và hàm Boole(tt) • Ví dụ: Hàm Boole F(x y) với x y F(x,y) – , giá trị =1 khi x=1 và y=0; bằng 0 với mọi lựa chọn khác đối với các giá trị của x và y được biểu diễn bởi bảng: 1 1 0 1 0 1 0 1 0 Gv: Huỳnh Thị Thu Thủy 114 0 0 0 2- Biểu thức Boole và hàm Boole(tt) • Các biểu thức Boole với các biến x1, x2, đ đị h hĩ 1 á h đệ h, xn ược n ng a c c quy n ư sau: – 0,1, x1, x2, , xn là các biểu thức Boole. – Nếu E1 và E2 là các biểu thức Boole thì E, (E1.E2) và (E1+E2) cũng là các biểu thức Gv: Huỳnh Thị Thu Thủy 115 Boole. 2- Biểu thức Boole và hàm Boole(tt) • Mỗi biểu thức Boole biểu diễn 1 hàm B loo e. • Các giá trị của hàm Boole này nhận được bằng cách thay 0 và 1 cho các biến trong biểu thức đó. Gv: Huỳnh Thị Thu Thủy 116 5/10/2013 30 2- Biểu thức Boole và hàm Boole(tt) • Ví dụ: Tìm giá trị của hàm x y z xy z F 1 1 1 1 0 – Boole được biểu diễn bởi: F(x,y,z) = xy+z • Lưu ý: – Số các hàm Boole bậc n là 2n. 1 1 0 1 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 Gv: Huỳnh Thị Thu Thủy 117 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 3- Các hằng đẳng thức của đại số Boole Hằng đẳng thức Tên gọi x = x Luật phần bù kép x + x = x x.x = x Luật lũy đẳng x + 0 = x x 1 = x Luật đồng nhất Gv: Huỳnh Thị Thu Thủy 118 . x + 1 = 1 x.0 = 0 Luật nuốt 3- Các hằng đẳng thức của đại số Boole Gv: Huỳnh Thị Thu Thủy 119 Bài tập biểu thức boole hàm boole 1. Tìm khai triển tổng các tích của hàm B loo e sau: a) F(x,y)= x + y b) F(x,y)=x y c) F(x,y)=1 d) F(x,y)=y Gv: Huỳnh Thị Thu Thủy 120 2. Tìm khai triển tổng các tích của hàm Boole sau: F(x,y,z)=x+y+z 5/10/2013 31 4- Tính đối ngẫu • Đối ngẫu của 1 biểu thức Boole – Nhận được bằng cách các tổng và tích Boole đổi chỗ cho nhau, các số 0 và 1 đổi chỗ cho nhau. • Ví dụ: Tìm đối ngẫu của Gv: Huỳnh Thị Thu Thủy 121 x.(y + 0) x .1 + (y + z) Bài tập 1. Tìm giá trị các biểu thức sau: a) 1.0 b) 1+1 c) 0.0 d) (1+0) 2. Tìm đối ngẫu của các biểu thức sau: a) x+y b) x . y c) xyz + x . y . z d) x.z + x.0 + x.1 3 CM các hằng đẳng thức sau: Gv: Huỳnh Thị Thu Thủy 122 . a) xy=(x+y)(xy) b) x  y=(x.