Hệ quả. Số nghiệm nguyên không âm [x1,x2,n,xn] [mỗi xi đều nguyên không âm] của phương trình Số cách chia k vật đồng chất nhau vào n hộp phân biệt cũng chính bằng số tổ hợp lặp chập k của n
Bạn đang xem trước 20 trang tài liệu Toán rời rạc - Chương 2: Phép đếm, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
LOGO Chương 2. Phép đếm TOÁN RỜI RẠC Chương 2 1 Nội dung - Các nguyên lý - Giải tích tổ hợp - Hoán vị lặp, tổ hợp lặp - Hệ thức đệ qui 2 I. Các nguyên lý 1. Nguyên lý cộng Giả sử để làm công việc A có 2 phương pháp - Phương pháp 1 có n cách làm - Phương pháp 2 có m cách làm Khi đó số cách làm công việc A là n+m Ví dụ. An có 3 áo tay dài, 5 áo tay ngắn. Để chọn 1 cái áo thì An có mấy cách 3 I. Các nguyên lý 2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước - Bước 1 có n cách làm - Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m Phép đếm Ví dụ: A B C Có 3.2 =6 con đường đi từ A đến C 4 I. Các nguyên lý Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Giải. Gọi số có 3 chữ số là abc TH1 . c=0. Khi đó c có 1 cách chọn a có 5 cách chọn [ a∈X\{0} ] b có 4 cách chọn [ b∈X\{a, 0} ] TH1 có 1.4.5 =20 TH2 . c≠0. Khi đó c có 2 cách chọn a có 4 cách chọn [ a∈X\{c, 0} ] b có 4 cách chọn [ b∈X\{a, c} ] TH2 có 2.4.4 =32 Vậy có 20+32 =52 5 I. Các nguyên lý 3. Nguyên lý chuồng bồ câu [Derichlet] Gọi là số nguyên nhỏ nhất lớn hơn hay bằng x. Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ bồ câu trở lên. /n k x Ví dụ. Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên - Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày 6 Ví dụ. Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có hai phần tử có tổng bằng 10. Giải. I. Các nguyên lý Ta lập các chuồng như sau: {1,9} {2,8} {3,7} {4,6} {5} Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Suy ra đpcm 7 4. Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đó |A ∪ B|= |A|+|B| - |A ∩ B| I. Các nguyên lý A∩ B BA 8 I. Các nguyên lý A∩ C B∩C A∩ B ∩ C C A∩ B A B |A∪ B ∪ C|=? 9 I. Các nguyên lý Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người Giải. Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh Khi đó. Số học sinh của lớp là |A∪ B |. Theo nguyên lý bù trừ ta có |A∪ B|= |A|+|B| - |A∩ B|=24+26-15=35 10 II. Giải tích tổ hợp 1. Hoán vị Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là Pn Pn = n! = n.[n-1].[n-2]n1 Quy ước 0! =1 Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc,acb, bac,bca, cab,cba 11 Ví dụ. Nếu A là tập hợp n phần tử thì số song ánh từ A vào A là n! Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được tạo từ tập X 5! 12 II. Giải tích tổ hợp 2. Chỉnh hợp. Định nghĩa. Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử [1 ≤ k ≤n] sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. Số các chỉnh hợp chập k của n ký hiệu là k nA - Công thức [ ] ! ! k n n A n k = − Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb. 13 II. Giải tích tổ hợp Ví dụ. Có bao nhiêu số tự nhiên gồm 3 chữ số được tạo thành từ 1,2,3,4,5,6. Kết quả: 3 6 A 14 II. Giải tích tổ hợp 3.Tổ hợp. Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử. Số tổ hợp chập k của n phần tử được kí hiệu là hay k nC k n [ ] ! ! ! k n n C k n k = − Tính chất n k k n nC C − = 1 1 k k k n n nC C C − ++ = 15 II. Giải tích tổ hợp Ví dụ. Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử của X là {1,2,3}, {1,2,4}, {1,3,4} , {2,3,4} Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn 10C- Số cách chọn là tổ hợp chập 10 của 30. 30 16 III. Hoán vị lặp, tổ hợp lặp 1. Hoán vị lặp Định nghĩa. Cho n đối tượng trong đó có ni đối tượng loại i giống hệt nhau [i =1,2,n,k ; n1+ n2,n+ nk= n]. Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2,n, nk đối tượng giống nhau thuộc loại k, là 1 2 ! ! !... !k n n n n 17 II. Giải tích tổ hợp Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS? Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Do đó số chuỗi có được là . 7! 420 3!1!2!1! = 18 III. Hoán vị lặp, tổ hợp lặp 2. Tổ hợp lặp Định nghĩa. Mỗi cách chọn ra k vật từ n loại vật khác nhau [trong đó mỗi loại vật có thể được chọn lại nhiều lần] được gọi là tổ hợp lặp chập k của n Số các tổ hợp lặp chập k của n được ký hiệu là kKn 1 k k n n kK C + −= 19 Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn. Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể AA, AB, AC, BB, BC, CC 2 2 2 6K C C= = = III. Hoán vị lặp, tổ hợp lặp 3 3 2 1 4+ − 20 Hệ quả. Số nghiệm nguyên không âm [x1,x2,n,xn] [mỗi xi đều nguyên không âm] của phương trình x1+ x2+n+ xn = k là 1 k k n n kK C + −= Số cách chia k vật đồng chất nhau vào n hộp phân biệt cũng chính bằng số tổ hợp lặp chập k của n 1 k k n n kK C + −= 21 Ví dụ. Tìm số nghiệm nguyên không âm của phương trình x1+ x2 + x3 + x4 = 20 [1] Thỏa điều kiện x1 ≤ 3; x2 ≥ 2; x3 > 4 [∗]. Giải. Ta viết điều kiện đã cho thành x1 ≤ 3; x2 ≥ 2; x3 ≥ 5. III. Hoán vị lặp, tổ hợp lặp Xét các điều kiện sau: x2 ≥ 2; x3 ≥ 5 [∗∗] x1 ≥ 4; x2 ≥ 2; x3 ≥ 5 [∗∗∗] Gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình [1] thỏa các điều kiện [∗], [∗∗], [∗∗∗]. Ta có: 22 p = q – r. Trước hết ta tìm q. Đặt x1’ = x1; x2’ = x2 – 2; x3’ = x3 - 5; x4’ = x4 Phương trình [1] trở thành x ’+ x ’ + x ’ + x ’ = 13 [2] III. Hoán vị lặp, tổ hợp lặp 1 2 3 4 Số nghiệm nguyên không âm của phương trình [1] thỏa điều kiện [∗∗] bằng số nghiệm nguyên không âm của phương trình [2] 23 Số nghiệm đó là Vậy . Lý luận tương tự, ta có . 13 13 13 4 4 13 1 16 K C C+ −= = 13 16 q C= 9 9 9 4 4 9 1 12 r K C C+ −= = = III. Hoán vị lặp, tổ hợp lặp Suy ra. Vậy số nghiệm nguyên không âm của phương trình [1] thỏa điều kiện [∗] là 340 13 9 16 12 560 220 340.p q r C C= − = − = − = 24
Các file đính kèm theo tài liệu này:
- 06_phepdem_1089.pdf
Bài này có thể đưa về dạng toán đã biết trước là đếm số nghiệm nguyên không âm của phương trình x1+x2+x3+x4=30 với x1>=a,x2>=b,x3>=c x+y+z+t=30-a-b-c=m với x=x1-a,y=x2-b,z=x3-c
thì số nghiệm là C[m+3,3] { C là tổ hợp } [1]
đặt F[a,b,c] tương ứng là kết quả của bài toán trên. Thì kết của của bài toán đề ra F[0,0,0]-F[18,0,0]-F[0,11,0]-F[0,0,9]+F[18,11,0]+F[18,0,9]+F[0,11,9]-F[18,11,9]
tính kết quả dựa trên công thức [1] thì kết quả bài toán = C[33,3]-C[33-18,3]-C[33-11,3]-C[33-9,3]+C[33-18-11,3]+C[33-18-9,3]+C[33-11-9,3] =1747
Đang xem: Tìm số nghiệm nguyên không âm của phương trình x1 x2 x3 x4=20
7 Comments 69 Likes Statistics Notes
12 hours ago Delete Reply Block
Bo de toan roi rac [on thi cao hoc khmt]
1. ĐẠI HỌC QUẢNG NGÃI BỘ ĐỀ TOÁN RỜI RẠC Dùng cho sinh viên khoa Công nghệ thông tin và cho thí sinh luyện thi cao học ngành Khoa học máy tính Biên soạn: BÙI TẤN NGỌC – 10/2011 – 2. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 1 Bài toán đếm Bài 1. Đếm số n gồm 2 chữ số, nếu: a. n chẵn Gọi AB là số thỏa mãn yêu cầu Vậy A có 9 cách chọn [không chọn 0, vì chọn 0 thì số này có 1 chữ số] B có 5 cách chọn Theo nguyên lý nhân, ta có : 9 x 5 = 45 số b. n lẻ gồm 2 chữ số khác nhau Gọi AB là số thỏa mãn yêu cầu Vì là số lẻ, nên B có 5 cách chọn Sau khi ta chọn B, thì A có 8 cách chọn Theo nguyên lý nhân, ta có : 5 x 8 = 40 số c. n chẵn gồm 2 chữ số khác nhau Gọi AB là số thỏa mãn yêu cầu Khi B = . A có 9 cách chọn Số cách chọn trong trường hợp này là : 9 cách Khi B = . A có 8 cách chọn Số cách chọn trong trường hợp này là : 4 x 8 = 32 cách Theo nguyên lý cộng, ta có : 9 + 32 = 41 số Cách khác: Theo câu a ta có 45 số n chẵn. Ta có 4 chữ số chẵn gồm 2 chữ số giống nhau: 22, 44, 66, 88. => 45 – 4 = 41 số n chẵn gồm 2 chữ số khác nhau. : a. abc a . 3. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 2 a xong, b a] Sau k a, b c a, b] b. abc c : . + Khi c a b như sau: c =0, a . a, c b + Khi c c a b như sau: c, a c a, c b c a] Bài 3. Có bao nhiêu xâu khác nhau có thể lập được từ các chữ cái trong từ MISSISSIPI, COMPUTER yêu cầu phải dùng tất cả các chữ? Từ MISSISSIPI có chứa : 1 từ M, 4 từ I, 4 từ S và 1 từ P Số xâu khác nhau là : !1!.4!.4!.1 !10 Xâu COMPUTER , nên lập được 8! xâu. 4. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 3 Bài 4. Có bao nhiêu xâu nhị phân độ dài 8 không chứa 6 số 0 liền? Gọi A là số xâu nhị phân độ dài 8 có chứa 6 số 0 liền nhau. B là số xâu nhị phân độ dài 8. => Số xâu cần đếm là : ][][][ ANBNAN N[B] = 2.2.2.2.2.2.2.2 =28 = 256. N[A] = 10 [00x, 11x, 1×1, x11, x10 ,1×0, 10x, x01,0x1, 01x : x=000000] Vậy số xâu cần đếm là : 256 – 10 = 246 Bài 5. Đếm số byte a. Bất kỳ Số byte là một dãy số có dạng: xxxxxxxx, x có 2 cách chọn 0 hoặc 1. Theo nguyên lý nhân ta có : 2.2.2.2.2.2.2.2 = 28 = 256 b. Có đúng hai bít 0. Có nghĩa là chuỗi luôn có 2 bit 0 và các bit còn lại là 1. Bài toán này tương đương với tính số cách sắp xếp các xâu từ: 00111111 Đây là hoán vị lặp của 8 phần tử với 2 loại: 2 số 0 và 6 số 1. 8!/2!.6! = 7.8/2 = 28 xâu c. Có ít nhất 2 bit 0 = Số xâu bất kỳ [a] – Số xâu không có bit 0 – Số xâu có 1 bit 0 Số xâu không có bit 0 = 1 trường hợp [11111111] Số xâu có 1 bit 0 = 8!/1!7!= 8 256 – 1 – 8 = 247 d. Bắt đầu 00 và kết thúc 00 Xâu này có dạng : 00xxxx00 Theo nguyên lí nhân, ta có : 1. 2.2.2.2 = 24 = 16 e. Bắt đầu 11 và kết thúc không phải 11 5. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 4 Gọi A là số xâu bắt đầu 11, có dạng 11xxxxxx Theo nguyên lý nhân, ta có : A= 1.1.2.2.2.2.2.2 = 26 = 64 Gọi B là số xâu bắt đầu là 11 và kết thúc là 11, có dạng 11xxxx11 Theo nguyên lý nhân, ta có : B= 1.1.2.2.2.2.1.1 = 24 = 16 Gọi C là số xâu bắt đầu 11 và kết thúc không phải 11 => C = A – B = 64 – 16 = 48 Bài 6. a. Mật khẩu máy tính gồm 1 chữ cái và 3 hoặc 4 chữ số. Tính số mật khẩu tối đa có thể. Dãy gồm 1 chữ cái và 3 chữ số có dạng: LNNN, NLNN, NNLN, NNNL Trong đó L là chữ cái có 26 cách chọn và mỗi N là chữ số có 10 cách chọn. Vì vậy theo nguyên lý nhân, ta có : 4 × 26 × 10 × 10 × 10 = 104000. Tương tự dãy có 1 chữ cái và 4 chữ số : 5 × 26 × 10 × 10 × 10 × 10 = 1300000. Theo nguyên lý cộng, ta có: 104000+ 1300000 = 1404000 [mật khẩu]. b. Như trên nhưng không lặp chữ số Số mật khẩu gồm 1 chữ cái và 3 chữ số = 4 × 26 × 10 × 9 × 8 = 74880 Số mật khẩu gồm 1 chữ cái và 4 chữ số = 5 × 26 × 10 × 9 × 8 × 7 = 655200 Theo nguyên lý cộng, ta có: 74880 + 655200 = 730080 [mật khẩu]. Bài 7. Đoäi boùng ñaù ACB coù 20 caàu thuû. Caàn choïn ra 11 caàu thuû, phaân vaøo 11 vò trí treân saân ñeå thi ñaáu chính thöùc. Hoûi coù maáy caùch choïn neáu : a. Ai cuõng coù theå chôi ôû baát cöù vò trí naøo ? Choïn ra 11 cầu thủ trong 20 caàu thuû , xeáp vaøo 11 vò trí treân saân. Soá caùch choïn baèng chænh hôïp khoâng laëp chaäp 11 cuûa 20 phaàn töû : 0006704425728 !9 !20 ]!1120[ !20 ]![ ! kn n Ak n caùch. b. Chæ coù moät caàu thuû ñöôïc chæ ñònh laøm thuû moân, caùc caàu thuû khaùc chôi ôû vò trí naøo cuõng ñöôïc ? 6. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 5 Moät caàu thuû ñaõ chæ ñònh laøm thuû moân, vaäy ta caàn choïn ra 10 caàu thuû trong 19 caàu thuû coøn laïi xeáp vaøo 10 vò trí. Soá caùch choïn baèng chænh hôïp khoâng laëp chaäp 10 cuûa 19 phaàn töû : 003352212864 !9 !19 ]!1019[ !19 ]![ ! kn n Ak n caùch. c. Coù 3 caàu thuû chæ coù theå laøm thuû moân ñöôïc, caùc caàu thuû khaùc chôi ôû vò trí naøo cuõng ñöôïc ? Coù 3 caùch choïn 1 caàu thuû ñeå laøm thuû moân töø 3 caàu thuû. Sau khi ta choïn thuû moân xong, keá ñeán choïn 10 caàu thuû trong 17 caàu thuû coøn laïi ñeå xeáp vaøo 10 vò trí, coù: 07057290240 !7 !17 ]!1017[ !17 ]![ ! kn n Ak n caùch Theo nguyeân lyù nhaân, ta coù: 3 07057290240 = 211718707200 caùch. Bài 8. Coù 8 ngöôøi ñi vaøo 1 thang maùy cuûa moät toøa nhaø 13 taàng. Hoûi coù bao nhieâu caùch ñeå : a. Moãi ngöôøi ñi vaøo 1 taàng khaùc nhau. Soá caùch ñi vaøo 8 taàng khaùc nhau cuûa 8 ngöôøi naøy laø soá caùch choïn 8 trong soá 13 taàng khaùc nhau [moãi taàng ñöôïc ñaùnh soá töø 1 ñeán 13]. Ñoù laø soá chænh hôïp khoâng laëp chaäp 8 cuûa 13 phaàn töû: 51891840 !5 !13 ]!813[ !13 ]![ ! kn n Ak n b. 8 ngöôøi naøy, moãi ngöôøi ñi vaøo 1 taàng baát kì naøo ñoù. Moãi ngöôøi coù 13 caùch löïa choïn töø taàng 1 ñeán 13. Maø coù 8 ngöôøi. Vaäy soá caùch choïn laø 813 . Bài 9. Có bao nhiêu xâu có độ dài 10 được tạo từ tập thỏa mãn ít nhất 1 trong 2 điều kiện: – Chứa đúng 3 chữ a & chúng phải đứng cạnh nhau – Chứa đúng 4 chữ b & chúng phải đứng cạnh nhau Gọi A là số xâu có độ dài 10 có chứa đúng 3 chữ a đứng cạnh nhau. B là số xâu có độ dài 10 có chứa đúng 4 chữ b đứng cạnh nhau. Như vậy: A B là số xâu mà ta phải tìm. 7. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 6 Theo nguyên lý bù trừ, ta có: N[AUB] = N[A] + N[B] – N[A∩B] Ta tính N[A] như sau: Xét trường hợp aaa ở đầu: aaaX1X2X3X4X5X6X7. – Xi [i=1..7] chỉ có 2 giá trị là b, c, vậy số trường hợp đối với 7 ký tự này giống như xâu nhị phân có độ dài 7, hay bằng 27 trường hợp. – Xâu aaa, có thể được xếp vào 8 vị trí [aaaX1X2X3X4X5X6X7, X1aaaX2X3X4X5X6X7, X1X2aaaX3X4X5X6X7, X1X2X3aaaX4X5X6X7, X1X2X3X4aaaX5X6X7 X1X2X3X4X5aaaX6X7, X1X2X3X4X5X6aaaX7, X1X2X3X4X5X6X7aaa]. Vì vậy: N[A] = 8.27 + Tương tự, số lượng xâu có 4 chữ b đứng cạnh nhau, N[B] = 7.26 + N[A∩B] được tính bằng cách gộp aaa = X, bbbb = Y, còn lại là 3 chữ c. Ta tính số xâu từ dãy: XcccY có: 5!/1!3!1! = 4.5 = 20 trường hợp. Vậy số xâu cần tính là: 8.27 + 7.26 – 20 = 2476. Bài 10. [Đề thi cao học ĐH CNTT TP HCM-2010] Xét biển số xe: A1A2A3N1N2N3N4N5N6 Ai[i=1..3]: A->Z; Nj[j=1..6]: 0->9 a. Hỏi có bao nhiêu biển số khác nhau? b. Hỏi có bao nhiêu biển số thỏa điều kiện: ba mẫu tự khác nhau đôi một và trong biển số có đúng 1 chữ số 3 và 1 chữ số 5? c. Hỏi có bao nhiêu biển số thỏa điều kiện: trong biển số có ít nhất 1 chữ số 3 và 1 chữ số 5? a. Ai [i=1..3] có 26 cách chọn từ 26 chữ cái tiếng Anh từ A .. Z Nj[j=1..6] có 10 cách chọn từ 10 chữ số từ 0 .. 9 Theo nguyên lý nhân ta có: 26.26.26.10.10.10.10.10.10 = 263 .106 biển số. b. Số cách chọn 3 mẫu tự A1A2A3 khác nhau: A1 có 26, A2 có 25, A3 có 24 cách. Số cách chọn 4 chữ số N1N2N3N4 không có số 3 và số 5: 8.8.8.8 = 84 cách. Số cách đặt số 3 vào dãy 4 chữ số N1N2N3N4 là 5 cách, đó là: 3N1N2N3N4, N13N2N3N4, N1N23N3N4, N1N2N33N4, N1N2N3N43. 8. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 7 Tương tự số cách đặt số 5 vào 5 dãy có 5 chữ số đã liệt kê ở trên là : 5.6=30 Theo nguyên lý nhân, ta có : 24. 84 .30 cách. c. Gọi A là số biển số không có chứa chữ số 3 và chữ số 5. NA = 263 .86 biển số Gọi B là số là số biển số có chứa chữ số 3 và không có chứa chữ số 5. NB = 263 .96 biển số Gọi C là số là số biển số có không chứa chữ số 3 và có chứa chữ số 5. NC = 263 .96 biển số Gọi D số biển số có ít nhất 1 chữ số 3 và 1 chữ số 5 ND = N – NA – NB – NC Theo câu a: N= 263 .106 = 263 .106 – 263 .96 – 263 .96 – 263 .86 = 263 [106 – 2.96 – 86 ]. Bài 11. a. Có bao nhiêu số có n chữ số mà có m chữ số đầu và m chữ số cuối tương ứng giống nhau. [n>2m>2, n,m N]. Gọi A dãy số cần tìm, A có dạng: Số cách chọn m chữ số đầu tiên và m chữ số cuối tương ứng giống nhau bằng chỉnh hợp lặp chập m của 10 phần tử [0..9]: 9.10m-1 [Chữ số đầu có 9 cách chọn, vì bỏ số 0 đứng đầu]. Số cách chọn dãy số ở giữa: Dãy này gồm có n-2m chữ số. Số cách chọn là: 10n-2m . Theo nguyên lý nhân, ta có: 9. 10m-1 .10n-2m chữ số. b. Ứng dụng tính số chữ số có 10 chữ số mà 3 chữ số đầu và 3 chữ số cuối tương ứng giống nhau. Số chữ số thỏa mãn đề bài bằng: 9.102 .1010-6 = 9.102 .104 = 9000000. xx…xbb…bxx…x n m 9. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 8 Bài 12. [Đề thi cao học Đà Nẵng – 8/2008] a. Trong một lớp học có 30 người. Cho biết có bao nhiêu cách cử một ban đại diện gồm 1 lớp trưởng, 1 lớp phó và 1 thủ quỹ. Có 30 cách chọn 1 lớp trưởng. Sau khi chọn 1 lớp trưởng xong, có 29 cách chọn 1 lớp phó. Sau khi chọn 1 lớp trưởng, 1 lớp phó xong, có 28 cách chọn 1thủ quĩ. Theo nguyên lý nhân, ta có : 30.29.28 = 24360 cách chọn. Cách khác: Số cách chọn chính bằng số chỉnh hợp không lặp chập 3 của 30 phần tử : A[30,3] = 30!/[30-3]!= 24360. b. Cho biết có thể nhận bao nhiêu xâu ký tự khác nhau bằng cách sắp xếp lại các chữ cái của từ SUCCESS. Từ SUCCESS có: 3 chữ S, 2 chữ C, 1 chữ U và 1 chữ E. Vậy có : 4207.6.5.2 2 7.6.5.4 !1!.2!.1!.3 !7 xâu khác nhau. Bài 13. [Đề thi cao học Đà Nẵng – 2/2009] a. Giả sử chúng ta có 5 viên bi giống nhau và 3 chiếc túi khác màu là xanh, vàng và đỏ. Cho biết có bao nhiêu cách bỏ bi vào các túi? Ví dụ: cách 1 -> túi xanh 5 viên, túi vàng và túi đỏ không có bi; cách 2 -> túi xanh 3 viên, túi vàng và túi đỏ mỗi túi 1 viên, … Số cách bỏ bi tương ứng chính bằng số tổ hợp lặp chập 5 từ tập có 3 phần tử là: 21 2 7.6 !2]!.27[ !72 7 13 153 1 1 CCCn kn b. Giả sử chúng ta có 5 viên bi [2 bi sắt, 2 bi chai và 1 bi đất] và 3 chiếc túi màu xanh, vàng và đỏ. Cho biết có bao nhiêu cách bỏ bi vào các túi? Ví dụ: Cách 1 túi xanh chứa 2 bi sắt, túi vàng 2 bi chai và túi đỏ 1 bi đất; cách 2 -> túi xanh 1 bi sắt, túi vàng 2 bi chai + 1 bi sắt và túi đỏ 1 bi đất, … Ta bỏ lần lượt từng loại vào 3 cái túi: + Bỏ 2 viên bi sắt vào 3 cái túi, có 6 2 4.3 !2]!.2[ !42 4 13 123 1 1 CCCn kn cách bỏ 10. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 9 + Bỏ 2 viên bi chai vào 3 cái túi, có 6 2 4.3 !2]!.2[ !42 4 13 123 1 1 CCCn kn cách bỏ bi + Bỏ 1 viên bi chai vào 3 cái túi, có 3 !2!.1 !32 3 13 113 1 1 CCCn kn cách bỏ bi Theo nguyên lý nhân, ta có: 6.6.3 = 108 cách bỏ bi. c. Giả sử chúng ta có 5 viên bi [2 bi sắt, 2 bi chai và 1 bi đất. Cho biết có bao nhiêu cách sắp chúng thành hàng? Ví dụ: sắt sắt chai chai đất, sắt chai sắt chai đất,… Cách sắp các viên bi thành hàng chính bằng hoán vị lặp của 5 phần tử, trong đó 2 bi sắt, 2 bi chai và 1 bi đất, vậy có: 30 2 5.4.3 !1!.2!.2 !5 cách sắp bi. 14. [Đề thi cao học ĐH CNTT TPHCM -5/2001] a. Tìm số các chuỗi 8 bits thỏa mãn điều kiện: bit đầu tiên là 1 hay 2 bit cuối là 0 Gọi A là số chuỗi 8bits có bit đầu tiên là 1 B là số chuỗi 8bits có 2 bit cuối là 0. Theo nguyên lý bù trừ, ta có N[A B] = N[A] + N[B] – N[A B] Tính N[A]: Gọi S=s1s2s3s4s5s6s7s8 là chuỗi 8bits có bit đầu tiên là 1. Vậy s1 có 1 trường hợp, si[i=2..8] có 2 trường hợp 0 và 1. Theo nguyên lý nhân, ta có: N[A] = 1.2.2.2.2.2.2.2 = 27 Tương tự: N[B] = 26 . N[A B] = 25 Vậy: N[A B] = 27 + 26 – 25 = 160 b. Mỗi người sử dụng một hệ thống máy tính của một công ty X phải sử dụng một password dài từ 6 đến 8 ký tự, trong đó mỗi ký tự là một chữ cái hoặc là một chữ s Mỗi password phải có ít nhất một chữ số. Hỏi có thể lập được bao nhiêu password khác nhau? n . 11. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 10 n . n – 52n 6 – 526 7 – 527 8 – 528 Theo 6 – 526 ] + [627 – 527 ] + [628 – 528 ] 6 – 266 ] + [367 – 267 ] + [368 – 268 ] 15. [Đề thi cao học ĐH KHTN-1999] Xét 3 chuỗi ký tự trên tập mẫu tự [ với a < b < c] : s1 = ac, s2 = aacb, s3 = aba. a. Hãy sắp xếp chúng theo thứ tự tăng đối với thứ tự từ điển. a < b < c, nên s2 < s3 < s1] b. Cho biết giữa s1 và s3 có bao nhiêu chuỗi ký tự có chiều dài 6. s3 = aba < ab * * * * < s1 = ac Bài 16. Cho trước một đa giác lồi P có 10 đỉnh lần lượt là A, B, C, D, E, F, G, H, I, J. Giả sử rằng trong đa giác không có 3 đường chéo nào cắt nhau tại một điểm. Hãy cho biết đa giác có tổng bao nhiêu đường chéo. Vì đa giác lồi P có 10 đỉnh, nên tổng số các đường nối 2 đỉnh bất kỳ của P chính bằng tổ hợp chập 2 [đỉnh] của 10 [đỉnh]. 45 2 10.9 !2]!.210[ !102 10C cạnh. Theo đề bài đa giác lồi P có 10 cạnh, vậy số đường chéo của đa giác P là: 45 -10 =35 12. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 11 Bài 17. Tìm số nghiệm nguyên không âm của: a. Phương trình 204321 xxxx với x1 0 ; x2 0; x3 0; x4 0 Ta nhận thấy mỗi nghiệm của phương trình ứng với một cách chọn 20 phần tử từ một tập có 4 loại, sao cho có x1 phần tử loại 1, x2 phần tử loại 2, x3 phần tử loại 3, x4 phần tử loại 4 được chọn. Vậy số nghiệm bằng số tổ hợp lặp chập 20 từ tập có 4 phần tử là: 177123.11.7 3.2 23.22.21 !3!.20 !23 !3]!.323[ !233 23 14 1204 1 1 CCCn kn b. Phương trình 204321 xxxx với x1 6 ; x2 3; x3 9; x4 -2 x1 > 6 x1 – 6 0 Đặt : a = x1 – 6 => x1 = a + 6 x2 > 3 x2 – 3 0 b = x2 – 3 => x2 = b + 3 x3 > 9 x3 – 9 0 c = x3 – 9 => x3 = c + 9 x4>-2 x4 + 2 0 d = x4 + 2 => x4 = d – 2 204321 xxxx a + 6 + b + 3 + c + 9 + d – 3 = 20 a + b + c + d = 5 với a 0; b 0; c 0; d 0 Vậy có : 56 3.2 8.7.6 !3!.5 !8 !3]!.38[ !83 8 14 154 1 1 CCCn kn nghiệm c. Bất phương trình x1 + x2 + x3 ≤ 11 với x1 0; x2 0; x3 0. Thêm ẩn phụ x4 0. ương đương x1 + x2 + x3 + x4 = 11 với x1 0; x2 0; x3 0; x4 0. 364 3.2 14.13.12 !3!.11 !143 14 14 1114 1 1 CCCn kn . d. Phương trình x + y + z = 10 với 0 x 2, 0 y 4, 0 z 6. Gọi U là tập tất cả các nghiệm nguyên không âm của phương trình x + y + z = 10, ta có: 66 2 12.11 !2!.10 !122 12 13 1103 1 1 CCCUN n kn . Gọi: A là tập nghiệm với x 3, y 0, z 0. 13. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 12 B là tập nghiệm với x 0, y 5, z 0. C là tập nghiệm với x 0, y 0, z 7. Theo nguyên lý bù trừ, số nghiệm nguyên của phương trình là: N* = N – A B C A B C = A + B + C + A B + A C + B C – A B C A là tập nghiệm với x 3, y 0, z 0, đặt x’=x-3, y’=y, z’=z, phương trình đã cho tương đương với x’ + y’ + z’ = 7 với x’ 0, y’ 0, z’ 0. => A = C[9,2] = 9!/7!.2! = 8.9/2 = 36. Tương tự : B = C[7,2] = 7!/5!.2! = 6.7/2 = 21. C = C[5,2] = 5!/3!.2! = 4.5/2 = 10. A B : x 3, y 5, z 0 : => x’ + y’ + z’ = 2 với x’ 0, y’ 0, z’ 0. A B =C[4,2] = 4!/2!2!= 3.4/2 = 6. A C : x 3, y 0, z 7 : => x’ + y’ + z’ = 0 với x’ 0, y’ 0, z’ 0. A C =C[2,2] = 2!/0!2! = 1. B C : x 0, y 5, z 7 : => x’ + y’ + z’ = -2 với x’ 0, y’ 0, z’ 0. => B C =0. A B C : x 3, y 5, z 7 : => x’ + y’ + z’ = -5 với x’ 0, y’ 0, z’ 0. => A B C =0. Vậy : A B C = 28 + 21 + 10 + 6 + 1 + 0 – 0 = 60 => N* = 66 – 60 = 8. Đó là các nghiệm: [0,4,6]; [1,3,6]; [1,4,5]; [2,2,6]; [2,3,5]; [2,4,4]; N [x 0, y 0, z 0] A x 3 B y 5 C z 7 N* 14. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 13 e. Phương trình 204321 xxxx [1] thỏa mãn x1 ≤ 3; x2 ≥ 2; x3 > 4 Vì các biến nhận giá trị nguyên. Nên điều kiện x1 ≤ 3; x2 ≥ 2; x3 > 4 được viết lại là: x1 ≤ 3; x2 ≥ 2; x3 ≥ 5 [*]. Xét các điều kiện sau: x2 ≥ 2; x3 ≥ 5 [**] x1 ≥ 4; x2 ≥ 2; x3 ≥ 5 [***] Ta gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình thỏa mãn [*], [**], [***]. Ta có: p = q – r Trước hết, ta tìm q như sau: Đặt: x1’= x1, x2’ = x2 – 2, x3’ = x3 – 5, x4’ = x4. Phương trình [1] trở thành: x1’ + x2’ + x3’ + x4’ = 13 [2] Số nghiệm nguyên không âm của [2] chính bằng số nghiệm của [1] thỏa mãn [**]. Mà số nghiệm của [2] là .56016.5.7 3.2 16.15.14 !3!.13 !163 16 14 1134 1 1 CCCn kn Ta tìm r như sau: Đặt: x1’= x1 – 4, x2’ = x2 – 2, x3’ = x3 – 5, x4’ = x4. Phương trình [1] trở thành: x1’ + x2’ + x3’ + x4’ = 9 [3] Số nghiệm nguyên không âm của [3] chính bằng số nghiệm của [1] thỏa mãn [***]. Mà số nghiệm của [3] là: 2204.11.5 3.2 12.11.10 !3!.9 !123 12 14 194 1 1 CCCn kn => P = q – r = 560 – 220 = 340. Vậy số nghiệm nguyên nguyên không âm của phương trình [1] thỏa điều kiện [*] là 340. . [Đề thi cao học ĐH Đà Nẵng – 10/2010]. [1] : 15. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 14 12650 4.3.2 25.24.23.22 !4!.21 !25 !4]!.425[ !254 25 15 1215 1 1 CCCn kn b. n x1>2, x51]. Gọi X là số từ có độ dài n chỉ có chữ số: X= 4n Y là số từ có độ dài n chỉ có ký tự: Y= 7n Vậy số từ thỏa mãn đề bài là: 11n – 4n – 7n 19. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 18 Bài 23. [Đề thi cao học Đà Nẵng – 10/2010] Cho X=. Chứng tỏ rằng nếu S là một tập con gồm 9 phần tử của X thì có ít nhất 2 phần tử của S có tổng bằng 15. Phân hoạch X thành 8 tập con, mỗi tập con đều có tổng bằng 15, như sau: , , , , , , , Phân 9 phần tử của S vào 8 tập con trên. Theo nguyên lý Dirichlet, có 2 phần tử của S thuộc một tập nào đó, mà tổng 2 phần tử này sẽ bằng 15. Bài 24. [Đề thi cao học Đà Nẵng – 3/2011] Trong mặt phẳng cho 6 điểm phân biệt nối nhau từng đôi một bởi các đoạn thẳng màu xanh hoặc đỏ. Chứng tỏ rằng có 3 điểm nối nhau bởi các đoạn thẳng cùng màu. Gọi A, B, C, D, E, F là 6 điểm phân biệt nằm trong một mặt phẳng. Giả sử ta chọn điểm A, nối điểm A với 5 điểm còn lại B, C, D, E, F bởi các đoạn thẳng màu xanh hoặc đỏ. + Ngược lại, tam giác BCD không có cạnh màu đỏ, thì tam giác này phải màu xanh. Vậy luôn luôn tồn tại 3 điểm nối với nhau từng đôi 1 bởi các đoạn thẳng cùng màu A B C D E F Giả sử ta chọn điểm A, nối điểm A với 5 điểm còn lại B, C, D, E, F bởi các đoạn thẳng màu xanh hoặc đỏ. Theo nguyên lý Dirichlet phải có 3 đoạn thẳng cùng màu xanh hoặc đỏ. Giả sử là 3 đoạn thẳng AB, AC và AD có màu đỏ [như hình vẽ]. + Nếu trong tam giác BCD có cạnh màu đỏ, giả sử là cạnh BC, thì tam giác ABC là tam giác có các cạnh màu đỏ [hay 3 điểm nối nhau cùng màu]. 20. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 19 Bài 25. Một võ sĩ quyền anh thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ đấu ít nhất một trận, nhưng toàn bộ không quá 125 trận. Chứng tỏ rằng có những giờ liên tiếp đã đấu 24 trận. Gọi ai là số trận đấu cho đến hết giờ thứ i [i=1..75] của võ sĩ quyền anh. Ta có : 1 a1 < a2 …< a75 125. [1] 25 a1 +24 < a2+24 …< a75+24 149. [2] Như vậy ta có 150 số trong 2 dãy [1] và [2] nhận giá trị trong . Theo nguyên lý Dirichlet phải có 2 hai số bằng nhau. Vì 2 dãy trên là dãy tăng, nên hai số bằng nhau thuộc 2 dãy khác nhau. Hay, ta có: ai+24 = aj aj – ai =24. Như vậy, từ giờ i đến hết giờ j võ sĩ đã thi đấu 24 trận. Bài 26. [Đề thi cao học Đà Nẵng – 8/2009] a. Một mạng máy tính có n [n>1] máy tính. Mỗi máy tính được nối trực tiếp hoặc không nối với các máy khác. CMR có ít nhất hai máy tính mà số các máy tính khác nối với chúng là bằng nhau. Gọi q1, q2, q3, … qn là số máy tính kết nối với máy 1, 2, 3 .. n. Như vậy ta có: 0 qi n-1 i=1..n Tuy nhiên, không thể xảy ra đồng thời: có 1 máy không kết nối với máy nào cả, tức là qi=0 và có một máy kết nối với tất cả các máy còn lại [qj=n-1]. Vậy chỉ xảy ra 1 trong hai trường hợp sau: 0 qi n-2 i=1..n 1 qi n-1 i=1..n Cả hai trường hợp trên n có qi nhận n-1 giá trị. Theo nguyên lý Dirichlet, có i j sao cho qi=qj. Hay có ít nhất 2 trong số n máy tính có số máy kết nối với chúng bằng nhau. b. Trong một mặt phẳng có 17 điểm phân biệt được nối với nhau từng đôi một bởi các đoạn thẳng màu xanh, hoặc màu đỏ, hoặc màu vàng. CMR luôn tồn tại ba điểm nối với nhau bởi các đoạn thẳng cùng màu Chọn 1 điểm bất kỳ, giả sử là P, từ P ta nối với 16 điểm còn lại bởi các đoạn thẳng là màu xanh, hoặc màu đỏ, hoặc màu vàng. Theo nguyên lý Dirichlet, trong 16 đoạn thẳng này sẽ có 6 đoạn thẳng có cùng màu. Giả sử 6 đoạn thẳng đó nối P với 6 điểm A, B, C, D, E, F có 2 trường hợp: 21. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 20 + Sáu điểm A, B, C, D, E, F được nối với nhau từng đôi một bởi các đoạn thẳng, trong đó có ít nhất 1 đoạn thẳng có màu đỏ. Khi đó, đoạn thẳng màu đỏ này cùng với điểm P tạo thành 3 điểm nối với nhau bởi các đoạn thẳng có màu đỏ. + Sáu điểm A, B, C, D, E, F được nối với nhau từng đôi một bởi các đoạn thẳng không có màu đỏ, tức là các đoạn thẳng này có màu xanh hoặc vàng. Khi đó, chọn điểm bất kỳ [chẳng hạn điểm A] nối với 5 điểm còn lại bởi các đoạn thẳng màu xanh hoặc vàng. Theo nguyên lý Dirichlet, tồn tại ít nhất 3 trong 5 đoạn thẳng có cùng màu, giả sử đó là màu xanh. Giả sử đó là các cạnh AB, AC và AD. Nếu có ít nhất một trong 3 đoạn thẳng BC, CD và DB có màu xanh thì cùng với điểm A tạo thành 3 điểm được nối với bởi màu xanh. Ngược lại, thì B, C, D là điểm được nối với nhau bởi màu vàng. Như vậy, luôn tồn tại ba điểm nối với nhau bởi các đoạn thẳng cùng màu Bài 27. Trong mặt phẳng xOy lấy ngẫu nhiên 5 điểm tọa độ nguyên. Chứng tỏ rằng có ít nhất một trung điểm của các đoạn nối chúng có tọa độ nguyên. Giả sử trong mặt phẳng xOy có A[x1,y1], B[x2,y2]. Vậy trung điểm của đoạn thẳng AB sẽ là: 2 21 , 2 21 yyxx . Các tọa độ này nguyên khi: [x1,x2] đều chẵn hoặc đều lẻ, [y1,y2] đều chẵn hoặc đều lẻ. Vì có 4 bộ bao gồm 2 phần tử có tính chẵn lẻ với nhau. Nên theo nguyên lý Dirichlet thì trong 5 điểm sẽ có ít nhất 2 điểm có tính chẵn lẻ như nhau. Do dó, trung điểm của 2 điểm này sẽ có tọa độ nguyên. Bài 28. Cho trước các tập hợp gồm các phần tử xác định nào đó. a. Hãy cho biết các cách mô tả, hay biểu diễn một tập hợp? Cho ví dụ. + Nếu A là một tập hợp gồm một số hữu hạn phần tử, để biểu diễn tập A, ta có thể liệt kê hết các phần tử của A. – Ví dụ biểu diễn A là tập hợp 4 chữ cái hoa đầu tiên: A= + Nếu A là một tập hợp vô hạn các phần tử, để biểu diễn tập A, ta dùng cách biểu diễn tính chất của các phần tử, có dạng: A= là tập hợp các phần tử x, sao cho x thỏa mãn tính chất P 22. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqn
gmail.com 21 – Ví dụ biểu diễn A là tập hợp các số thực: A= b. Hãy cho biết thế nào là một tập hợp đếm được, một tập hợp không đếm được? Cho ví dụ. + Nếu A là một tập hợp có hữu hạn phần tử, thì tập A được gọi là tập đếm được. Ví dụ: A=, A là tập đếm được vì nó có 9 phần tử, từ 1 đến 9 + Nếu A là một tập hợp có vô hạn phần tử, thì tập A có thể là tập đếm được hoặc không đếm được. Để xác định A có đếm được hay không ta chỉ cần xây dựng song ánh giữa tập A với tập các số tự nhiên N. Ví dụ: Cho A là tập hợp các số phức. A là tập vô hạn không đếm được. c. Cho A là tập không đếm được, B là tập đếm được. Hãy cho biết tập hợp A-B [hiệu] có đếm được hay không? Giả sử A-B là tập đếm được, khi đó A=[A-B] B cũng là tập hợp đếm được, vì: [A-B] : là tập đếm được theo giả thiết. B : là tập đếm được theo đề bài. Mâu thuẩn với đề bài đã cho là A là tập không đếm được. Vậy A-B là tập không đếm được. d. CMR tích Decac của hai tập hợp vô hạn đếm được cũng là một tập vô hạn đếm được? Tích Decac AxB là tập tất cả các cặp phần tử có trật tự sắp xếp [a,b] được tạo ra bởi một phần tử a A với các phần tử đứng kế tiếp b B. Giả sử A=; B= Ta xây dựng một [bảng] ma trận hai chiều, đầu mỗi hàng là một phần tử của A, đầu mỗi cột là phần tử của B. Khi đó, các phần tử của tích Decac AxB là các phần tử của ma trận. 23. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqn
Xem thêm: Chuyên De Giải Bài Toán Bằng Cách Lập Phương Trình Lớp 8 Nâng Cao ]
gmail.com 22 b1 b2 … bn a1 a1b1 a1b2 .. a1bn a2 a2b1 a2b2 … a1bn … .. .. .. .. an anb1 anb2 … anbn Từ ma trận trên ta suy ra AxB là đếm được. Bài 29. [Đề thi cao học Đà Nẵng – 5/2007] Cho dãy u = trong đó ai là các ký tự tùy ý, i 1..n, n là độ dài của dãy u đã cho. Một dãy v = được gọi là dãy con của dãy u nếu tìm được dãy các chỉ số 1 i1 < i2 < … < im n và bk=aik với mọi k 1..m. Chẳng hạn dãy v = < B, C, D, B> là dãy con của dãy u = < A, B, C, B, D, A, B> với dãy chỉ số là . Một dãy w được gọi là dãy con chung của hai dãy u và v đã cho, nếu w vừa là dãy con của u và vừa là dãy con của v. Một dãy con chung được gọi là lớn nhất nếu có độ dài lớn nhất trong số các dãy con của các dãy đã cho. Chẳng hạn, các dãy và đều là dãy con chung lớn nhất của hai dãy và . Gọi C[i,j] là độ dài của một dãy con chung lớn nhất của hai dãy X= và Y= [0 i n, 0 j m]. Người ta tìm được công thức đệ quy tính C[i,j] như sau: 24. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqn
gmail.com 23 a, Hãy giải thích công thức đệ quy trên: – Nếu i=0 hoặc j=0 thì C = 0. – Nếu i>0, j>0: + Nếu Xi = Yj thì dãy con chung dài nhất của Xi và Yj sẽ thu được bằng việc bổ sung Xi vào dãy con chung dài nhất của hai dãy Xi-1và Yj-1 + Nếu Xi Yj thì dãy con chung dài nhất của Xi và Yj sẽ là dãy con dài nhất trong hai dãy con chung dài nhất của [Xi và Yi-1] và của [Xi-1 và Yj]. b, Viết hàm RecMaxSubSeq dùng phương pháp lặp tính độ dài dãy con chung lớn nhất của hai dãy trên. Type Mang= array of byte; Function RecMaxSubSeq [X,Y,m,n]: Mang; Var i,j: Byte; C: Mang; Begin for i :=1 to n do c:=0; for j: =1 to m do c:=0; for i: =1 to n do for j: = 1to m do if x = y then c:=c+1 else if c c then c:=c else c:=c; RecMaxSubSeq :=C; End; 25. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 24 Kỹ thuật đếm nâng cao Bài 1. Cho dãy số thỏa mãn hệ thức truy hồi: an = 5an-1 – 6an-2 ; a0=0 và a1=1. a. Giải hệ thức truy hồi trên. Ta có phương trình đặt trưng : x2 = 5x – 6 x2 – 5x + 6 =0 có 2 nghiệm phân biệt : x1 = 3 và x2 = 2 Hệ thức truy hồi có dạng: an = b3n + d2n [1] Với a0=0, a1=1thay lần lượt vào [1], ta có hệ phương trình sau: b + d =0 3b + 2d = 1 => b = 1, d = -1 Vậy hệ thức truy hồi là : an = 3n – 2n b. Viết hàm A[n] để tính an Function A[n: integer]: Integer; Begin If n=0 then A:=0 Else if n=1 then A:=1 Else A:=5*A[n-1] – 6*A[n-2]; End; Bài 2. Giải hệ thức truy hồi an = 6an-1 – 9an-2 ; a0=1, a1=6 Ta có phương trình đặt trưng : x2 = 6x – 9 x2 – 6x + 9 =0 PT có nghiệm kép : x = 3 Hệ thức truy hồi có dạng: an = b3n + d.n.3n Thay a0=1 và a1=6, ta có hệ phương trình : 633 1 db b => b = 1, d = 1 Vậy hệ thức truy hồi là : an = 3n + n3n = [1+n] 3n 26. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 25 Bài 3. Giải hệ thức truy hồi an = 2an-1 + 5an-2 – 6an-3; a0=0, a1=-4 và a2=8 Ta có phương trình đặt trưng : x3 =2×2 +5×2 -6 x3 – 2×2 -5x+ 6 =0 [x-1][x2 – x – 6] = 0 có 3 nghiệm phân biệt : x1 = 1 ; x2 = 3 ; x3 = -2 Hệ thức truy hồi có dạng: an = b + d.3n + c.[-2]n Thay a0 = 0, a1=-4, a2 = 8, ta có hệ phương trinh : 849 423 0 cdb cdb cdb => b = -24/15, d = 1/5, c=22/15 Vậy : n n na ]2[ 15 22 5 3 15 24 Bài 4. [Đề thi cao học ĐH KHTN TP HCM 2010] a.Tìm nghiệm tổng quát của hệ thức đệ qui: an = an-1 + 6an-2 Phương trình đặc trưng là: x2 = x + 6 x2 – x – 6 = 0 Phương trình có 2 nghiệm phân biệt: x1 = -2 và x2 = 3. Nên nghiệm tổng quát là: an = c[-2]n + d3n b. Tìm nghiệm thỏa điều kiện đầu a0 = 8, a1 = 5 của hệ thức đệ qui: an = an-1 + 6an-2 + 10n[-2]n – 3[-2]n-1 Đặt fn = 10n[-2]n – 3[-2]n-1 = [-2]n [10n + 3/2]. Vì -2 là 1 nghiệm của phương trình đặc trưng nên nghiệm riêng có dạng: n[-2]n [An + B]. [*] Thế [*] vào hệ thức ban đầu, ta có: n[-2]n [An + B] = [n-1][-2]n-1 [A[n-1] + B] + 6[n-2][-2]n-2 [A[n-2] + B] + [-2]n [10n + 3/2] [**]. 27. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 26 Thế n = 2 vào [**], ta có: 2[-2]2 [2A + B] = [-2][A + B] + [-2]2 [10.2 + 3/2] ⇔ 16A + 8B = -2A – 2B + 86 ⇔ 18A + 10B = 86 ⇔ 9A + 5B = 43 [***] Thế n = 1 vào [**], ta có: [-2][A + B] = 6[-1][-2]-1[B – A] + [-2][10 + 3/2] ⇔ -2A – 2B = 3B – 3A – 23 ⇔ A – 5B = -23 [****] Từ [***] và [****] ta có hệ phương trình: 23-=5B-A 43=5B+9A => A = 2 và B = 5 Vậy nghiệm tổng quát của hệ thức là: an = b[-2]n + c3n + n[-2]n [2n + 5] Với a0 = 8, ta có: 8 = b[-2]0 + c30 + 0[-2]0 [2.0 + 5] ⇔ b + c = 8 [1] Với a1 = 5, ta có: 5 = b[-2]1 + c31 + 1[-2]1 [2.1 + 5] ⇔ -2b + 3c = 19 [2] Từ [1] và [2] ta có hệ phương trình: 19=3c+2b- 8=c+b => b = 1 và c = 7. Vậy nghiệm của hệ thức đệ qui là: an = [-2]n + 7.3n + n[-2]n [2n + 5] 28. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 27 Bài 5. Gọi an là số dãy bit độ dài n không có 2 bit 0 liền nhau. a. Tìm hệ thức truy hồi cho an Dãy bit độ dài n không có 2 bit 0 liền nhau có 1 trong 2 dạng : – A1 : A có n-1 bit và không có 2 bit 0 liền nhau. Có a[n-1] trường hợp – B10: B có n-2 bit và không có 2 bit 0 liền nhau. Có a[n-2] trường hợp Vậy hệ thức truy hồi : an = a[n-1] + a[n-2] b. Biết giá trị đầu a1=2, a2=3, giải hệ thức truy hồi trên Phương trình đặc trưng: x2 = x + 1 x2 – x -1 = 0 Phương trình có 2 nghiệm riêng biệt là: 2 51 2, 2 51 1 xx Vậy an có dạng: nn n dba ] 2 51 [] 2 51 [ [1] Theo hệ thức truy hồi, ta có : a2 = a1 +a0 => a0 = a2 – a1 = 1 Với a0=1 và a1=2, ta có hệ phương trình: 2] 2 51 [] 2 51 [ 1 db db ] 2 51 [ 5 1 ], 2 51 [ 5 1 db Vậy: 11 2 51 5 1 2 51 5 1 nn nF c. Tìm hệ thức truy hồi cho số các xâu nhị phân chứa xâu 00 Gọi Sn là số chuỗi nhị phân độ dài n [n 2] có 2 bit 0 n sẽ có một trong các dạng sau: A1: – , số chuỗi là: S[n-1] B10: B -2 , số chuỗi là: S[n-2] 29. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 28 C00: C tùy ý có độ dài n-2, số chuỗi là: 2[n-2] Ta có công thức truy hồi: Sn=S[n-1]+S[n-2]+ 2[n-2] Bài 6. [Đề thi cao học Đà Nẵng – 9/2010] Cho biết dân số của Việt Nam năm 2007 là 86 triệu người. Giả sử tốc độ tăng dân số hằng năm là 0,2% mỗi năm. Gọi Dn là dân số của Việt Nam n năm sau 2007 a. Lập hệ thức truy hồi tính Dn. Gọi: D0 là tổng dân số Việt Nam năm 2007, D0 = 86 triệu người D1 là tổng dân số Việt Nam năm 2008 : D1 = D0 + 0,002.D0=1,002.D0 ………………………….. Dn là tổng dân số Việt Nam n năm sau năm 2007 Dn = Dn-1 + 0,002Dn-1 = 1,002.Dn-1 b. Dân số Việt Nam năm 2020 là bao nhiêu? Thế lần lượt Dn-1 = 1,002.Dn-2 vào Dn Dn-2 = 1,002Dn-3 vào Dn-1 …….. Cuối cùng ta có : Dn = [1,002]n .D0 = 86.[1,002]n triệu người. Theo đề bài, ta có: n = 2020 – 2007 = 13 Như vậy sau 13 năm dân số Việt Nam là: D13 =86.[1,002]13 triệu người. Bài 7. Giả sử lãi suất ngân hàng là 2% một năm. Tính tổng số tiền có trong tài khoản sau 10 năm, nếu tiền gửi ban đầu tài 10 triệu. P0 là số tiền ban đầu : P0 = 10 triệu P1 là tổng số tiền sau 1 năm gửi: P1 = P0 + 0,02P0 = 1,02P0 P2 là tổng số tiền sau 2 năm gửi: P2 = P1 + 0,02P1 =1,02P1 = 1,02 . 1,02 P0 = [1,02]2 P0 30. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 29 ….. Pn là tổng số tiền sau n năm gửi: Pn = Pn-1 + 1,02Pn-1 …. = [1,02]n P0 Với n=10, ta có: P10 = [1,02]10 P0 = [1,02]10 .10 = 12,189 triệu đồng. Bài 8. Tìm hệ thức truy hồi và điều kiện đầu để tính số chuỗi nhị phân độ dài n có 4 bít 0 liên tiếp. Ứng dụng tính số chuỗi với n=8. Gọi Sn là số chuỗi nhị phân độ dài n [n 4] có 4 bit 0 liên tiếp. Sn sẽ có một trong các dạng sau: A1: Trong đó A chứa 4 bit 0 liên tục, số chuỗi là: S[n-1] B10: B chứa 4 bít 0 liên tục, số chuỗi là: S[n-2] C100: C chứa 4 bít 0 liên tục, số chuỗi là: S[n-3] D1000: D chứa 4 bít 0 liên tục, số chuỗi là: S[n-4] E0000: E tùy ý có độ dài n-4, số chuỗi là 2[n-4] Ta có công thức truy hồi: Sn=S[n-1]+S[n-2]+S[n-3]+S[n-4]+2[n-4] Điều kiện đầu là: S1=S2=S3=0; S4=1 [Nghĩa là, với n=1, 2, 3 không có chuỗi nào, n=4 có duy nhất 1 chuỗi, đó là: 0000]. Dùng phương pháp thế để giải, như sau: s5 = s4+s3+s2+s1+2 = 1+0+0+0+2 = 3 [chuỗi độ dài 5 có 3 trường hợp 0000 kề nhau: 00000, 10000, 00001] s6 = s5 + s4 + s3 + s2 + 22 = 3 + 1 + 0 +0+4 = 8 s7 = s6 + s5 + s4 + s3 + 23 = 8 + 3 + 1+0 + 8 = 20 s8 = s7 + s6 + s5 + s4 + 24 = 20 + 8 + 3 + 1 + 16 = 48 Vậy có 48 chuỗi nhị phân có độ dài 8 chứa 4 bits 0 kề nhau. 31. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 30 Bài 9. Tìm HTTH mà Rn thỏa mãn, trong đó Rn là số miền của mặt phẳng bịphân chia bởi n đường thẳng nếu không có hai đường nào song song và không có 3 đường nào cùng đi qua 1 điểm. – Nếu không có đường thẳng nào, tức n=0 thì có 1 mặt phẳng: Rn = 1. – Nếu có 1 đường thẳng, tức n=1 thì nó chia mặt phẳng thành 2: Rn =2. – Nếu n > 1, giả sử n-1 đường thẳng chia mặt phẳng thành Rn-1 miền. Theo đề bài không có 2 đường thẳng nào song song với nhau, nên đường thẳng thứ n sẽ cắt n-1 đường thẳng còn lại tại n-1 giao điểm. Vì không có 3 đường thẳng đi qua một 1 điểm, nên n-1 giao điểm trên khác nhau từng đôi một và chúng tạo ra n-2 đoạn và 2 nửa đoạn trên đường thẳng thứ n. Mỗi đoạn và nửa đoạn này chia miền mà nó đi qua thành 2 miền mới, nghĩa là làm tăng thêm 1 miền. Do đó đường thẳng thứ n làm tăng thêm [n-2] + 2 = n miền. Vậy HTTH là: Rn = Rn-1 + n. Bài 10. Viết HTTH của cos[nx] và sin[nx] sin[nx] = 2sin[[n − 1]x]cos[x] − sin[[n − 2]x] cos[nx] = 2cos[[n − 1]x]cos[x] − cos[[n − 2]x] 32. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 31 Logic mệnh đề Bài 1. Viết bảng giá trị chân lý của các phép toán mệnh đề Bài 2. Hãy nêu các công thức trong logic mệnh đề 33. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqn
gmail.com 32 Bài 3. Chứng minh a. rqprpqp ][][ ][][][][ rpqprpqp [Đ/n ] ]][][[][ rprpqp [Luật De Morgan và Đ/n ] ]][][[][ rprppq [Luật De Morgan và giao hoán] ]][][[[ rprppq [Luật kết hợp] ]]][[]][[[ rpprppq [Luật phân phối] ]]]][[]][[[ rpprppq [Luật kết hợp] ]][][[ rprTq [Luật bù] ]][[ rpTq [Luật nuốt] ][ rpq [ Luật đồng nhất] rqp [ Luật giao hoán] b. ][]>[[][]]gmail.com 33 c. 1]>[][0[]gmail.com 34 – Khử phép kéo theo và rút gọn mệnh đề F. F = [P [R Q]] [ P [Q [R P]]] = [ P [R Q]] [ P [Q [R P]]] = [ P [R Q]] [ [ P Q ] [ P [R P]]] = P [R Q] [ P Q ] [ P P=F [Luật đúng], F R=F [Luật trội]] = P [ P Q ] [R Q] [Luật giao hoán]. = P [T [T Q ] [R Q] = P [R Q] – Tìm dạng chuẩn hội chính tắc của mệnh đề F. Ta có : ][ QRPF ][ QRP [Luật bù kép] ][ QRP [Luật De Morgan] ][ QRP [Luật De Morgan] ][][ QPRP [Luật phân phối] ][][ QPRP [Luật De Morgan] ][][ QPRP [Luật De Morgan] b. Biết rằng mệnh đề P[x,y] được phát biểu là “x + y = 0”, với x, y là các số thực. hãy cho biết chân trị của các mệnh đề dưới đây và giải thích tại sao? *. x y P[x,y] Mệnh đề x y P[x,y] luôn luôn có giá trị đúng [True], vì với mọi x, luôn tồn tại một giá trị y=-x, làm cho biểu thức x+y=0, ví dụ: P[1,-1], P[2,-2]… *. x y P[x,y] Mệnh đề x y P[x,y] luôn luôn có giá trị sai [False], vì không có giá trị nào của y làm cho biểu thức x+y=0 với mọi x. 36. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 35 Bài 6. Dùng bảng chân trị chứng minh rằng : CBACBA A B C CBA CBA A B C CBA 0 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 Bài 7.Trình bày các quy tắc suy diễn trong logic mệnh đề 37. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 36 Bài 8.Viết suy luận của phát biểu sau: Ông Minh đã khẳng định rằng nếu không được tăng lương thì ông sẽ nghỉ việc. Mặt khác nếu ông ta nghỉ việc và vợ ông ta bị mất việc thì phải bán xe. Biết rằng nếu vợ ông Minh hay đi làm trễ thì sẽ mất việc. Cuối cùng ông đã được tăng lương. Vậy suy ra nếu ông Minh không bán xe thì vợ ông không đi làm trễ. Ta đặt các biến mệnh đề như sau: q: Ông Minh được tăng lương; r: Ông Minh nghỉ việc s: Vợ ông Minh mất việc; t: Ông Minh phải bán xe. p: Vợ ông Minh hay đi làm trễ. Suy luận trên được viết lại như sau: q r [r s] t p s q —————- t p Bài 9. [Đề thi cao học Đà Nẵng – 2/2009] a. Suy luận sau đúng hay sai: Nếu bò sữa nhiều và sữa tốt thì sẽ được cho ăn thêm nhiều cỏ non. Bò ăn thêm nhiều cỏ non thì sẽ mập lên. Nhưng thực tế bò không mập lên. Kết luận bò không cho nhiều sữa hoặc không cho sữa tốt. Ta đặt các biến mệnh đề như sau: q: bò cho sữa nhiều. r: bò cho sữa tốt. p: bò được cho ăn thêm nhiều cỏ non. s: bò mập lên. Suy luận được viết lại như sau: q r p [1] p s [2] s [3] ——————– q r 38. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 37 q r s [4] [Tam đoạn luận 1 và 2] s [5] [Tiền đề] rq [Do 4, 5 và luật phủ định] q r [Luật De Morgan ] Vậy suy luận trên là đúng. b. Cho biết biểu thức nào trong số các biểu thức sau đây là đồng nhất đúng 1. pqr p+q là đồng nhất đúng: p q r pqr p+q pqr p+q 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 2. [p q[q r]] [p r] là đồng nhất đúng: p q r q r q[q r] p q[q r]] p r [p q[q r]] [p r] 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 3. [p q] p không đồng nhất đúng: p q p q [p q] p 0 0 1 0 0 1 1 0 39. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 38 1 0 0 1 1 1 1 1 4. [p [q+r]] [q pr] không đồng nhất đúng: p q r q+r p [q+r] q pr q pr [p [q+r]] [q pr] 0 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 c. Tìm giá trị các biến Boole x và y thỏa mãn phương trình xy = x + y x y xy x + y 0 0 0 0 1 1 1 1 Bài 10. Hãy kiểm tra các suy luận sau và cho biết đã sử dụng quy tắc suy diễn nào? c, a. [[p q] q] p [Quy tắc phủ định] r p [r p] [De Morgan] 40. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 39 b. r q q r [Luật phản đảo] p r [Luật tam đoạn] p r [Đ/n ] p [Luật rút gọn] c. t u [1] r [s t] [2] [ p q ] r [3] [s u ] [4] ______________ p s u [ Do tiền đề [4] và luật De Morgan ] [5] u [Do [5] và luật đơn giản nối liền] [6] t [Do [1], [6] và luật phủ định] [7] s [Do [5] và luật đơn giản nối liền] [8] t s [Do [7], [8] và phép nối liền] [9] [s t] [Do [9] và luật De Morgan] [10] r [Do [2], [10] và luật phủ định] [11] [ p q] [Do [3], [11] và luật phủ định] [12] p q [Do [12] và luật De Morgan] [13] p [Do [13] và luật đơn giản nối liền] 41. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 40 Đại số Boole Bài 1. Trình bày các tính chất của các phép toán Boole 1. Tính giao hoán: a.b = b.a a+b = b+a. 2. Tính kết hợp: [a.b].c = a.[b.c] [a+b]+c = a+[b+c]. 3. Tính phân phối: a.[b+c] = [a.b]+[a.c] a+[b.c] = [a+b].[a+c]. 4. Tính đồng nhất: a.1 = 1.a = a a+0 = 0+a = a. 5. Tính bù: 0.. aaaa 0aaaa 6. Tính nuốt a.0 = 0 a+1 = 1 7. Tính luỹ đẳng a.a = a a+a = a. 8. Hệ thức De Morgan baab baba 9. Tính bù kép aa 10. Tính hút a.[a+b] = a a+[a.b] = a. 42. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 41 Bài 2. Tối thiểu hàm Bool bằng bảng Karnaugh a] zyxyzxzyxzxyzyxF ],,[ Việc nhóm thành các khối cho thấy rằng: Có 2 cặp hình vuông kề nhau, cặp ngang biểu diễn cho zx , cặp đứng biểu diễn cho zy và 1 hình vuông cô lập biểu diễn cho yzx ; vì vậy: zx , zy và yzx là các nguyên nhân nguyên tố của F[x,y,z]. Do đó, ta có hàm tuyển chuẩn tắc tối thiểu là: yzxzyzxzyxF ],,[ zxyzyxF ],,[ zyxzyxF ],,[ 43. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 42 Bài 3. [Đề thi cao học Đà Nẵng – 8/2008] a. Tìm các giá trị của hàm Boole được biểu diễn: zxyzyxF ],,[ x y z z xy zxy 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 b. Tối thiểu hàm Boole yxyxyxyxF ],[ yxyyxyyxxxy 1.][ yx c. Tối thiểu hóa hàm Boole bằng bảng Karnaugh : zyxyzxzyxzxyyxF ],[ yz zy zy zy x 1 1 x 1 1 zxzxyxF ],[ 44. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 43 Bài 4: Tìm dạng chuẩn tắc của hàm zyxzyxF ][],,[ Ta lập bảng giá trị của hàm F như sau: x y z z x+y zyx ][ 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 Ta thấy F[x,y,z] bằng 1 khi : x=0, y=1, z=0 hoặc x=1, y=0, z=0 hoặc x=1, y=1, z=0 Vậy dạng chuẩn tắc của hàm F : zxyzyxzyxzyxF ],,[ Bài 5: Vẽ mạch logic của các hàm sau: a. xyxyxF ][],[ b. zyxzyxyxF ][],[ 45. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 44 Bài 6. a, Dạng tuyển đầy đủ của F Tập các thể hiện làm cho giá trị của F[x,y,z] bằng 1 là: . Từ tập các thể hiện này ta lập các từ tối thiểu tương ứng : zyx , zyx , zyx , zxy , xyz. Như vậy, dạng tuyển chuẩn tắc đầy đủ của F như sau: F[x,y,z] = zyx + zyx + zyx + zxy + xyz b, Dạng chuẩn tắc tối thiểu F[x,y,z] = zyx + zyx + zyx + zxy + xyz = zx [ y + y ] + zx [ y + y ] + xyz = zx + zx + xyz = [ x + x ] z + xyz = z + xyz Bài 7. a, Dạng tuyển đầy đủ của F Tập các thể hiện làm cho giá trị của F[w,x,y,z] bằng 1 là: . Từ tập các thể hiện này ta lập các từ tối thiểu tương ứng : wxyz, zywx , zywx , zyxw , zyxw , zxyw , zyxw , zyxw , zyxw . Như vậy, dạng tuyển chuẩn tắc đầy đủ của F như sau: F[x,y,z] = wxyz + zywx + zywx + zyxw + zyxw + zxyw + zyxw + zyxw + zyxw b, Dạng chuẩn tắc tối thiểu F[x,y,z] = wxyz + zywx + zywx + zyxw + zyxw + zxyw + zyxw + zyxw + zyxw = wxz[ y + y ] + zwx [ y + y ] + zyxw + z [ xyw + yxw ] + yxw [z + z ] 46. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 45 = wxz + zwx + zyxw + z [ yw [ x + x ]] + yxw = wx[ z + z ] + zyxw + zyw + yxw = wx + zyxw + zyw + yxw Bài 8. Tìm dạng chuẩn tắc của biểu thức ]][[][],,[ zyzxzxyzyxf = [ zxy ][ ][ zx + ][ zy ] [Luật De Morgan] = [ zxy ][ zx + yz] [Luật De Morgan] = zyzzzxxyyzzxyx [Luật phân phối] = zxxzyzxy + 0 [Luật lũy đẳng: x.x = x Luật bù: 0zz Luật nuốt 0.x = 0] = zxzzxy ][ = zxxy [Luật bù 1zz ] Bài 9. Tìm dạng chuẩn tắc đầy đủ của biểu thức a, zxyzzyxf ],,[ = ][][ yyzxxxyz = zyxzxyyzxxyz b, zxyxzyxf ],,[ = zxyzzx ][ = zxyzxxz = yzxxz 47. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 46 = ]][[][][ zxxzyyyzxyyxz = zyyxxyzzyxzxyzyxxyz = ][][ xxzyzzyxzyxzxyzyxxyz = zyxzxyzyxyzxzyxzxyzyxxyz = zyxyzxzyxzyxzxyxyz Cách khác: Giải bằng lập bảng chân trị của biểu thức zxyxzyxf ],,[ X Y Z Z’ XZ’ X+Y X+Y+XZ’ 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 Tập các thể hiện làm cho giá trị của F[x,y,z] bằng 1 là: . Từ tập các thể hiện này ta lập các từ tối thiểu tương ứng : zyx , yzx , zyx , zyx , zxy , xyz . Như vậy, dạng tuyển chuẩn tắc đầy đủ của F như sau: zyxyzxzyxzyxzxyxyzzyxF ],,[ Bài 10. Tìm biểu thức tối thiểu của: a, xxyyxyxxyE 1.][1 [Luật bù 1yy ] [Luật đồng nhất x.1=x] b, ][2 yyxxyyxyxxyE yxxxyxxyE 1.2 [Luật hấp thụ yxyxx , xxyx , xyxx ][ , xyyxx ][ ] 48. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqngmail.com 47 c, yxyxyxE4 ][ yyxyx xyx yx Bài 11. Tìm biểu thức tối thiểu của: a, xzyyxzyzxE1 ]1[]1[1 xyzzyxE ]1[]1[1 xyzzyxE 1.1.1 yzxE [Luật nuốt 1 + x = 1] yzxE1 [Luật đồng nhất 1.x =x] b, zyxzyxzxyxyzE2 zyxzyxzxy ]1[ zvyxzyxxy zyxzxxy ][ zyxzxy ][ [Luật hấp thụ yxyxx ] zyxzyxy c, zyxyzxzyxzxyxyzE3 ][][ yyzxzyxzzxy zxzyxxy zxzyyx ][ 49. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqn
gmail.com 48 zxzyx ][ zxxzxy zxxxy ][ zxy d, zyxzyxzxyxyzE3 zyxzyxzzxy ][ zyxzyxxy zyxzxxy ][ zyxzxy ][ zyxzyxy zyxzyxy Bài 12. Tìm biểu thức tối thiểu của: A, zxywyxwwxyxwE1 ][][ zwwxyywwx ][][ zwxyywx zxyxywyxwx zxyyxxyxw ][ zxyyxyxw ][ zxyyxywwx 50. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqn
Xem thêm: các hàm trong excel và ví dụ
gmail.com 49 b, zyxwzyxwzwxywxyzE2 zyxwzyxwzzwxy ][ zyxwzyxwwxy Bài 13. Cho bảng giá trị x y z F[x, y, z] 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 a. Tìm dạng tuyển chuẩn tắc hoàn toàn [đầy đủ] của f. Tập các thể hiện làm cho giá trị của F[x,y,z] bằng 1 là: . Từ tập các thể hiện này ta lập các từ tối thiểu tương ứng : zyx , zyx , zyx , zxy , xyz. Như vậy, dạng tuyển chuẩn tắc đầy đủ của F như sau: xyzzxyzyxzyxzyxzyxF ],,[ b. Tìm dạng tuyển chuẩn tắc thu gọn của f bằng bảng Karnaugh. yz zy zy zy x 1 1 1 x 1 1 zxyzyxF ],,[ 51. Toán rời rạc – Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính ấn Ngọc buitanngocqn
gmail.com 50 Bài 14. [Đề thi cao học ĐH CNTT TP HCM-2010] a. Tìm công thức dạng chính tắc và công thức tối thiểu của hàm Boole sau: xyzttxytzxzyxtzytzyxxztzyxtzyxF ],,,[ xyztzztxyyytzxttzyxxxtzytzyxyyxztzyx ][][][][][
Xem thêm bài viết thuộc chuyên mục: Phương trình