Bài giảng môn học Toán học rời rạc

Nội dung text: Bài giảng môn học Toán học rời rạc

1. TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN KHOA HỌC MÁY TÍNH o0o BÀI GIẢNG MÔN HỌC TOÁN HỌC RỜI RẠC HỆ ĐẠI HỌC Số tín chỉ: 3TC Hệ đào tạo: ĐHCQ Ngành: CNTT, HTTTQL, TMĐT. Bộ môn giảng dạy: Bộ môn KHMT – Khoa CNTT. Thái Nguyên, năm 2015 0
2. MỤC LỤC Mục Trang Chương 1: TẬP HỢP VÀ LOGIC MỆNH ĐỀ 2 1.1 Tập hợp và các phép toán trên tập hợp 2 1.2. Quan hệ 5 1.3. Logic mệnh đề 8 1.4. Suy luận toán học và các phương pháp chứng minh 16 Chương 2: GIẢI THUẬT VÀ CÁC PHƯƠNG PHÁP ĐẾM . 22 2.1. Thuật toán và các đặc trưng cơ bản của thuật toán 22 2.2. Thuật toán đệ quy . 28 2.3. Thuật toán quay lui . 33 2.4. Các nguyên lý đếm cơ bản 37 2.5. Hoán vị và tổ hợp 40 Chương 3: LÝ THUYẾT ĐỒ THỊ VÀ CÂY 50 3.1. Đồ thị và các khái niệm cơ bản trong đồ thị . 50 3.2. Bậc, đường đi, chu trình và tính liên thông của đồ thị 54 3.3. Các phương pháp duyệt đồ thị 57 3.4. Một số đơn đồ thị đặc biệt . 59 3.5. Đồ thị Euler . 63 3.6. Đồ thị Hamilton 68 3.7. Thuật toán tìm đường đi ngắn nhất. 73 3.8. Cây và cây khung của đồ thị . 80 TÀI LIỆU THAM KHẢO 90 1
3. CHƯƠNG 1 TẬP HỢP & LOGIC MỆNH ĐỀ 1.1.Tập hợp 1.1.1 Khái niệm chung về tập hợp Tập hợp là một trong những khái niệm quan trọng nhất của toán học, nó là gốc rễ của các ngành toán học khác nhau. Vào nửa đầu thế kỷ 19, nhà toán học người Đức Geory Cautar (1845 – 1918) đã nghiên cứu các tập hợp và ứng dụng của chúng như là nền tảng của các ngành toán học (các công trình được công bố vào những năm từ 1871 – 1883) . Lý thuyết tập hợp sau khi xuất hiện đã thống nhất được nhiều quan niệm toán học và đã xây dựng nên các cơ sở logic của nhiều ngành toán học khác nhau. Tập hợp được coi là 1 cấu trúc rời rạc bao gồm nhiều đối tượng được nhóm lại với nhau, thông thường các đối tượng trong một tập hợp có một vài tính chất tương tự nhau. Các đối tượng trong tập hợp được gọi là các phần tử của tập hợp đó. Trật tự của các các phần tử trong tập hợp là không quan trọng, quan trọng là phần tử đó có mặt trong tập hợp hay không. Ví dụ: Tập hợp các số tự nhiên N. Tập N+ các số tự nhiên khác 0 Tập các số nguyên Z Tập các số hữu tỷ Q Tập các số thực R Ký hiệu: Phần tử tập hợp dùng chữ in thường. Tập hợp dùng chữ in hoa. Để ký hiệu x là phần tử của tập A, ta viết: x A (x thuộc A hay x là phần tử của A). Nếu x không là phần tử của tập A thì ta viết: x A (x không thuộc A). 1.1.2.Một số tập hợp đặc biệt a.Tập con Cho 2 tập hợp A và B. Nếu mọi phần tử của A đều là phần tử của B thì ta viết: AB hoặc BA và gọi là A là tập con của B (A được chứa trong B; A được bao hàm trong B; A là bộ phận của B; B bao hàm A ). Ví dụ: N*NZQR Hai tập A và B được gọi là bằng nhau nếu AB và BA. Ký hiệu là A=B Nếu AB và A B thì ta nói A là tập con thực sự của B, ký hiệu A B. Nếu A không là tập con thực sự của B thì ta viết AB b.Tập hợp rỗng:Tập hợp không chứa phần tử nào gọi là tập rỗng. Tập rỗng được ký hiệu là .Với mọi tập A ta có A.Tập rỗng là duy nhất. c.Tập hợp các tập con của một tập hợp: Cho X là một tập hợp. Tập hợp các tập con của tập X ký hiệu là P(X) hay 2X. P(X) = {A | AX} Ví dụ: X =  thì P(X) = {} X = {a, b} thì P(X) = {, {a}, {b}, {a,b}} d. Tập hợp bù: Với mỗi AX đặt AC = X\A hay X X \ A gọi là phần bù của A trong X. Ta có: AAC = X hay A A X ; AAC =  hay A  A  2
4. Theo tính chất ta có: (AB)C = ACBC (AB)C = ACBC 1.1.3 Cách xác định tập hợp a. Liệt kê các phần tử của tập hợp trong cặp ngoặc { } Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử của nó: A = {a, e, o, i, u}: tập tất cả các nguyên âm (của bảng chữ cái Aab) A = {1, 2, 3, 5, 7} Khi không liệt kê hết ta dùng dấu A = {0, 1, 2, , 99}: Tập tất cả các số tự nhiên từ 0 đến 99. B = {0, 2, 4, 6, }: Tập tất cả các số tự nhiên chẵn. b. Chỉ ra thuộc tính đặc trưng của các phần tử trong tập hợp bằng một mệnh đề (x) nào đó. Nếu A là tập gồm các phần tử x của tập X có tính chất P(x) thì ta viết: A = {x X | P(x)} Ví dụ : A = {x R | x2 – 4x + 3 = 0} B = {n N | n là ước của 20} C = {n N* | xn + yn = zn có nghiệm nguyên dương} c. Dùng giản đồ Venn Qui ước: Tập hợp vũ trụ U: tập chứa tất cả các phần tử đang xét, được biểu diễn bằng một hình chữ nhật. Bên trong hình chữ nhật, dùng hình tròn, hình elip để biểu diễn cho các tập hợp. Các điểm được dùng để biểu diễn cho các phần tử của tập hợp. Ví dụ : U = N A = {2, 4, 6, 8, 10} N A .2 .10 .8 .4 .6 1.1.4 Phép toán trên tập hợp a. Phép hợp: Cho hai tập hợp A, B. Ta gọi A hợp B là tập gồm các phần tử thuộc A hoặc thuộc B. Ký hiệu là AB, như vậy AB = {a | a A hoặc a B}. b. Phép giao: Cho hai tập hợp A, B. Ta gọi A giao B là tập gồm các phần tử vừa thuộc A vừa thuộc B. Ký hiệu là AB, như vậy AB = {a | a A và a B}. Nếu không có phần tử nào vừa thuộc A vừa thuộc B thì AB = . Trong trường hơp này ta nói A và B rời nhau hoặc không giao nhau. c. Phép hiệu: Cho hai tập hợp A, B. Ta gọi A trừ B (hay hiệu của A và B) là tập gồm các phần tử thuộc A nhưng không thuộc B. Ký hiệu là A\B. 3
5. A\B = {a | a A và a B}. Lưu ý: A\B khác B\A. d. Phép hiệu đối xứng: Cho hai tập hợp A, B. Ta gọi hiệu đối xứng của A và B là tập gồm các phần tử chỉ thuộc A hoặc chỉ thuộc B, không đồng thời thuộc cả A và B. Ký hiệu là A B. A B = {(A\B) (B\A)}. Ví dụ 1: Cho A ={0, 1, 2, 4, 6} B = {1, 3, 5, 6} AB = {0, 1, 2, 3, 4, 5, 6} AB = {0,6} A\B = {1, 2, 4} B\A = {3, 5} A B = {1, 2, 4, 3, 5} Ví dụ 2: A = {x N | x chia hết cho 2}; B = {x N | x chia hết cho 3} AB = {x N | x chia hết cho 2 và chia hết cho 3} 1.1.4 Các tính chất trên tập hợp Với A, B, C là các tập hợp bất kỳ ta có: 1.Tính chất giao hoán: AB = BA và AB = BA 2.Tính chất kết hợp: (AB)C = A(BC) (AB)C = A(BC) 3.Tính chất phân phối: A(BC) = (AB)(AC) A(BC) = (AB)(AC) 4.Luật đối ngẫu Demorgan: A  B A  B A  B A  B 5.Luật nuốt: nếu AB thì AB = B, AB = A Chứng minh: Các tính chất 1, 2, 5 là hiển nhiên. Các tính chất còn lại được chứng minh tương tự nhau. Chứng minh tính chất 3: A(BC) = (AB)(AC) Thật vậy với a A(BC) a A hoặc a BC a A hoặc a B và a C a A hoặc a B và a A hoặc a C a AB và a AC a (AB)(AC) Tức là có tính chất 3. Lưu ý: Vì A và AA với A nên: A = A, A = , AA = A, AA = A 1.1.5 Mở rộng các phép toán tập hợp a. Mở rộng tính chất 2 Với các tập A1, A2, , An ta có:  A1A2 A3 = (A1A2)A3 n   Ai A1  A2  An = (A1  A2  An 1 )  An i 1  A1A2 A3 = (A1A2)A3 n   Ai A1  A2  An = (A1  A2  An 1 )  An i 1 b.Mở rộng tính chất 3 Cho các tập hợp X, A1, A2, , An ta có: 2
6. n n  X   Ai  X  Ai i 1 i 1 n n  X   Ai  X  Ai i 1 i 1 c.Mở rộng tính chất 4 Cho các tập hợp X, A1, A2, , An ta có: n n  Ai  Ai i 1 i 1 n n  Ai  Ai i 1 i 1 1.1.7 Tích đề các a. Tích đề các của 2 tập hợp Cho A, B là 2 tập hợp. Với mỗi a A, b B. Ta gọi (a, b) là một cặp. Hai cặp (a, b) và (c, d) gọi là bằng nhau nếu a = c và b = d. Ta gọi tích đề các của A và B là tập A B gồm các cặp (a, b) với a A, b B A B = {(a,b) | a A, b B} Tích đề các A A ký hiệu là A2 (Bình phương đề các) Ví dụ: = {1, 2, 3}; B = {a, b} thì: A B = {(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)} B A = {(a, 1); (a, 2); (a, 3); (b, 1); (b, 2); (b, 3)} A A = A2 = {(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3)} B B = B2 = {(a,a); (a,b); (b,a); (b,b)} b.Tích đề các của n tập hợp Cho n tập hợp A1, A2, , An. Khi đó tích đề các của n tập hợp này ký hiệu là n A1 A2 An =  Ai a1 ,,an / a1 A1 ,,an An  i 1 Hai bộ (a1, a2, , an) và (b1,b2, , bn) gọi là bằng nhau nếu: a1 = b1; a2 = b2 ; ; an = bn n n Nếu A1 = A2 = = An thì ký hiệu  Ai A và gọi là luỹ thừa đề các bậc n của tập hợp i 1 A. 1.1.8 Tập hợp hữu hạn a. Bản số của tập hữu hạn Tập A được gọi là hữu hạn nếu nó là tập  hoặc liệt kê được tất cả các phần tử của tập A, như vậy tập A là hữu hạn nếu: A =  A = {a1, a2, , an) với các ai là khác nhau ( i = 1, ,n). Trong trường hợp 1 ta nói A có bản số 0. Trong trường hợp 2 ta nói A có bản số n. Kí hiệu: A =0; hay N(A)=0; A =n; hay N(A)=n Nhận xét: Bản số của một tập hữu hạn chính là số phần tử của tập đó. Hai tập hữu hạn cùng bản số có cùng số phần tử. b.Tính chất của bản số hữu hạn Định lý 1: Cho A, B là hai tập hữu hạn, khi đó: 1. |AB| = |A| + |B| – |AB| 2. |A\B| = |A| – |AB| 3
7. 3. |A B| = |A| + |B| – 2|AB| Chứng minh: 1.Giả sử |A| = m; |B| = n. A = {a1, a2, , am} và B = {b1, b2, , bn} Xét trường hợp AB = : AB = {a1, a2, , am, b1, b2, , bn} do đó |AB| = m + n = |A| + |B| Trường hợp AB có k phần tử. Đặt AB = {a1, a2, , ak}. Khi đó: A = {a1, a2, , ak, ak+1, , am}; B = {b1, b2, , bk, bk+1, , bn} Vì AB = {a1, a2, , ak, ak+1, , am, bk+1, , bn} nên: |AB| = m + (n – k) = m + n – k = |A| + |B| – |AB| 1.Do A = (A\B)  (AB) mà (A\B)  (AB) =  nên theo (1) ta có: |A| = |A\B| + |AB| |A\B| = |A| – |AB| 2.Vì (A\B)(B\A) =  nên áp dụng (1) và sau đó áp dụng (2) ta có: |A B| = |(A\B)(B\A)| = |A\B| + |B\A| = |A| – |AB| + |B| – |BA| = |A| + |B| – 2|AB| Lưu ý theo tính chất (2) nếu BA thì |A\B| = |A| – |B| Các tập hợp A1, A2, , An gọi là đôi một rời nhau nếu 2 tập bất kỳ trong chúng đều rời nhau, tức là AiAj = . Với i j. Theo định lý 1, nếu A1A2 =  thì |A1A2|= |A1| + |A2| Áp dụng tính chất (1) (n-1) lần, ta có: Định lý 2: Cho A1, A2, , An là các tập đôi một rời nhau. Khi đó, |A1A2  An| = |A1| + |A2| + + |An| Định lý 3: Với  tập hợp A, B ta có: |A B| = |A|.|B| Chứng minh: Giả sử A = {a1, a2, , am} |A| = m B = {b1, b2, , bn} |B| = n Với ai, ta có: m | {ai} B| = n vì A B = ({ai } B) và các tập {a1} B; {a2} B; ; {am} B i 1 đôi một rời nhau nên theo định lý 2 ta có: |A B| = |{a1} B| + |{a2} B| + + |{am} B | = m n = |A|.|B| Định lý 4: Cho A1, A2, , An là các tập hợp bất kỳ. Khi đó |A1 A2 An| = |A1| |A2| |An| 1.2.Quan Hệ 1.2.1 Khái niệm về quan hệ Trong thực tế, ta thường gặp mối quan hệ giữa các phần tử của tập hợp này với các phần tử của tập hợp khác, hoặc ngay trong cùng một tập hợp. Nếu gọi A là tập các đối tượng (phần tử) mà ta đang xét thì mỗi nhóm gồm m phần m tử có quan hệ với nhau là một phần tử của A A A  A . Các nhóm gồm m phần tử m như vậy tạo thành một tập con của Am. Ta có các định nghĩa: a. Quan hệ 2 ngôi: Một quan hệ 2-ngôi từ tập A đến tập B là tập con của tích đề các A x B. Nếu R là một quan hệ 2-ngôi từ A đến B thì R{(a,b) a A , b B }. Nếu (,)a b R hay aRb thì ta nói a,b có R-quan hệ với nhau. Nếu (,)a b R thì ta nói a,b không có R-quan hệ với nhau. Trong trường hợp A=B thì quan hệ R được gọi là quan hệ 2 ngôi trên chính tập A. Quan hệ 2-ngôi được gọi tắt là quan hệ. 4
8. b. Tương tự ta có khái niệm về quan hệ m-ngôi: Một quan hệ m-ngôi trên tập hợp A là m tập con của tích đề các A . Nếu R là một quan hệ m-ngôi trên A thì khi (a1, a2, , am) R ta nói a1, a2, , am có R-quan hệ với nhau. Ví dụ: Cho A: Tập các nước; B: Tập các thủ đô R  A B = {(a, b) | nếu a có thủ đô là b} Ta có: (Việt Nam, Hà nội) R; (Lào, Viêng chăn) R (Thái Lan, Băng cốc) R; (Singapo, Hà nội) R Ví dụ 2: A: Tập các cán bộ trong khoa CNTT R = {(a, b) | a, b A và a, b có cùng tuổi}  A A R là một quan hệ trên A. 1.2.2 Tính chất của quan hệ Cho quan hệ R trên A. Nếu (x,y) R thì ta nói x có R quan hệ với y (x có quan hệ với y) viết là : xRy hay (x, y) R. Nếu (x, y) R thì hiểu là x không có quan hệ với y. Quan hệ R trên tập A có các tính chất sau: i.Tính chất phản xạ nếu với x A ta có xRx ii.Tính chất đối xứng nếu: vớix, y A: xRy thì yRx. iii.Tính chất phản đối xứng nếu : vớix, y A: xRy  yRx thì x=y. iv.Tính chất bắc cầu nếu: vớix, y, z A: xRy  yRx thì xRz. Ví dụ 1 : + Xét trong tập số tự nhiên N: Quan hệ xRy nếu x y là quan hệ có tính chất phản xạ, phản đối xứng, bắc cầu. + Xét tập các tam giác, quan hệ R: đồng dạng, có tính chất phản xạ, đối xứng, bắc cầu. Ví dụ 2: Cho tập A={1, 2, 3, 4} Quan hệ R trên tập hợp A được định nghĩa a, b A :aRb a+b =2k k Z, khi đó: 1. R có tính chất phản xạ: a A ta có a+a=2a aRa hay (a,a) R 2. R có tính chất đối xứng: a, b A và a+b=2k thì cũng có b+a=2k hay nếu có aRb thì cũng có bRa 3. R có tính chất bắc cầu : a, b,c A nếu a+b=2k, b+c=2k’ thì a+c=(2k-b)+(2k’-b)= 2k+2k’-2b=2k’’ hay (a,c) R 1.2.3 Quan hệ tương đương a.Định nghĩa Một quan hệ R trên tập A gọi là quan hệ tương đương nếu R có các tính chất phản xạ, đối xứng, và bắc cầu. Nếu R là quan hệ tương đương thì thay cho cách viết xRy ta viết xy (x tương đương y). Vậy  là một quan hệ tương đương trên A nếu với x, y, z A ta có: xx (tính phản xạ) xy yx (tính đối xứng) xy  yz xz (tính bắc cầu) b. Ví dụ : Cho tập A={1, 2, 3, 4, 5, 6, 7} Quan hệ R trên tập hợp A được định nghĩa a, b A :aRb a-b =3k k Z, khi đó R là quan hệ tương đương, thực vậy: 1. R có tính chất phản xạ: a A ta có a-a=0=3.0 aRa hay (a,a) R 2. R có tính chất đối xứng: a, b A và a-b=3k b-a=3(-k)=3k’ bRa 5
9. 3. R có tính chất bắc cầu : a, b,c A nếu a-b=3k, b-c=3k’ thì a-c= 3k+b+3k’-b=3(k+k’)=3k’’ hay (a,c) R c.Lớp tương đương Cho A là một tập và R là một quan hệ tương đương trên A. Với x A, tập xR x y x | yRxgọi là lớp tương đương chứa x. Định lý 1: Các lớp tương đương là , hoặc bằng nhau, hoặc rời nhau. Chứng minh: Xét lớp tương đương bất kỳ [x]:  Vì xRx nên x [x] [x] .  Để chứng minh phần còn lại ta giả sử 2 lớp x và y có xy =  ta chỉ cần chứng minh = . Chọn z  vì z nên xRz, vì z nên zRy. t tRx tRy t . Vậy = . Từ định lý ta có:  y x x y và xRy x y  Các lớp tương đương chia A thành các tập con rời nhau (các phân hoạch tập A).  Tập hợp mà mỗi phần tử là 1 lớp tương đương của tập A theo quan hệ tương đương R () gọi là tập thương của A theo quan hệ R (). Ký hiệu là X/R  X/. Vậy X/R = {[x] | x X}. Ví dụ: Trên tập Z các số nguyên xét quan hệ aRb nếu a – b 3. Ta có R là một quan hệ tương đương trên Z. Thật vậy: x, y, z Z: a/x – x = 0 3 aRa suy ra R có tính chất phản xạ. b/xRy x – y 3 –(y – x) 3 hay yRx suy ra R có tính chất đối xứng. c/ xRy x – y 3 và yRz x – y 3 (x – z) 3 suy ra R có tính chất bắc cầu. Ta xét các lớp tương đương theo quan hệ này ta có xRy x – y 3 x và y chia cho 3 có cùng số dư. Khi chia cho 3 số dư có thể là 0, 1, 2. Do đó ta có các lớp tương đương đúng là: 0R 3k | k Zcác số chia hết cho 3 1R 3k 1| k Zcác số chia cho 3 dư 1 2R 3k 2 | k Z các số chia cho 3 dư 2 Vậy Z = 0R ,1R ,2R  Quan hệ tương đương trên gọi là quan hệ đồng dư theo modul 3, ký hiệu là ab (mod 3). 1.2.4 Quan hệ thứ tự a. Định nghĩa quan hệ thứ tự Một quan hệ R trên tập A gọi là quan hệ thứ tự nếu R có các tính chất phản xạ, phản đối xứng và bắc cầu. Nếu R là quan hệ thứ tự trên A thì thay cho cách viết xRy ta viết x y (x nhỏ hơn hay bằng y). Vậy là một quan hệ thứ tự trên A nếu với x, y, z A, ta có: 1.x x (tính phản xạ) 2.x y  y x thì x = y (tính phản đối xứng) 3.x y  y z thì x z (tính bắc cầu) Ký hiệu x < y có nghĩa là x y và x y: đọc là x nhỏ hơn y. Tập A cùng với một quan hệ thứ tự trên nó gọi là tập được sắp thứ tự, khi đó ký hiệu là (A, ). 6
10. Ví dụ 1: Trong N, Z, Q, R quan hệ thông thường là quan hệ thứ tự. Ví dụ 2: Quan hệ bao hàm (  ) trong tập P(A) = 2A ( tập các tập con của tập A) là quan hệ thứ tự. Thật vậy: 1. X P(A): A  A  có tính chất phản xạ. 2. X, Y P(A): A  B  B  A A = B nên  có tính chất phản đối xứng. 3. X, Y, Z P(A): A  B  B  C A C nên  có tính chất bắc cầu. b. Quan hệ thứ tự toàn phần và bộ phận Cho A là một tập hợp được sắp thứ tự. Nếu với x, y A ta có x y hoặc y x thì ta nói x và y so sánh được với nhau. Nếu mọi x, y A đều so sánh được với nhau thì ta nói A là tập sắp thứ tự toàn phần (sắp thứ tự tuyến tính). Trong trường hợp ngược lại, nói rằng A là tập sắp thứ tự bộ phận. Ví dụ :  Quan hệ thông thường trên N, Z, Q, R là quan hệ thứ tự toàn phần.  Quan hệ “chia hết” trong N* là quan hệ thứ tự bộ phận (2 và 3 không so sánh được với nhau). c.Phần tử lớn nhất, nhỏ nhất, tối đại và tối thiểu Cho A là một tập được sắp thứ tự:  Phần tử a A gọi là phần tử lớn nhất (nhỏ nhất) nếu với x A đều có x a (a x).  Phần tử a A gọi là phần tử tối đại (tối thiểu) nếu với x A đều có a x a = x ( x a kéo theo x = a). Ví dụ : Trong tập N với quan hệ ta có 0 là phần tử nhỏ nhất; 0 là phần tử tối thiểu. Không có phần tử lớn nhất, phần tử tối đại.  Trong tập P(A) với quan hệ  có  là phần tử nhỏ nhất, A là phần tử lớn nhất. 1.3.Logic mệnh đề 1.3.1.Khái niệm mệnh đề và giá trị chân lý Một mệnh đề là một câu đúng hoặc sai, không thể vừa đúng vừa sai. Giá trị đúng hoặc sai của một mệnh đề được gọi là giá trị chân lý của mệnh đề. Về ký hiệu, ta thường dùng các chữ cái như p, q, r để ký hiệu cho các biến nhận giá trị đúng hoặc sai. Giá trị chân lý “đúng – true” thường được viết là 1 hoặc T và giá trị chân lý “sai – false” được viết là 0 hoặc F. Ví dụ 1: Các phát biểu sau đây là các mệnh đề 1. 6 là một số nguyên tố 2. 5 là số lẻ 3. 4<-2 4. Tam giác cân có 2 góc bằng nhau 5. H2O là một axit. Các mệnh đề 2, 4 có giá trị chân lý “đúng” hay là các mệnh đề đúng. Các mệnh đề 1, 3, 5 có giá trị chân lý “sai” hay là các mệnh đề sai. Ví dụ 2: Các phát biểu sau đây không phải là các mệnh đề vì tính đúng sai của chúng không xác định. 1. Hãy đóng cửa sổ lại! 2. Ai đang đọc sách? 3. Cô ấy rất thông minh 4. Cho x là một số nguyên dương. 5. x là một số lẻ 6. x + y = z 7
11. Mệnh đề có hai loại: (1)Mệnh đề sơ cấp (elementary): mệnh đề sơ cấp là các “nguyên tử” theo nghĩa là nó không thể phân tích được thành một hay nhiều (từ 2 trở lên) mệnh đề thành phần đơn giản hơn. (2) Mệnh đề phức hợp (compound): mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác bằng cách sử dụng các liên kết logic như từ “không” dùng trong việc phủ định một mệnh đề, các từ nối: “và”, “hay”, “hoặc”, “suy ra”, vv Ví dụ : xét các mệnh đề sau: p: “15 chia hết cho 3” ; q: “2 là một số nguyên tố và là một số lẻ” Ta có: p là mệnh đề sơ cấp, q là mệnh đề phức hợp, vì q được tạo thành từ 2 mệnh đề: p1 : “2 là một số nguyên tố” ; P2: “2 là một số lẻ” nhờ vào liên kết logic “và”. 1.3.2.Các phép toán mệnh đề Khi có các mệnh đề phức hợp theo các mệnh đề sơ cấp thì việc tính toán giá trị chân lý sẽ được thực hiện như thế nào? Để trả lời được cần có các phép toán logic, các phép toán logic ở đây là các ký hiệu được dùng thay cho các từ liên kết logic như từ “không”, “và”, “hay”, “hoặc”, “suy ra”, “nếu thì ”, “nếu và chỉ nếu ” Các phép toán logic được định nghĩa bằng bảng giá trị chân lý (truth table). a.Phép phủ định Ký hiệu là:  Giả sử p là một mệnh đề, phủ định của p được ký hiệu là  p hay p . Bảng giá trị chân lý của phép phủ định được cho bởi bảng: p p 0 1 1 0 Ví dụ 1: Cho mệnh đề p: 5<3 : 5 3 Giá trị chân lý của p là 0 Giá trị chân lý của là 1 Ví dụ 2: Chỉ ra rằng p và p luôn có cùng giá trị chân lý: Giải: lập bảng giá trị chân lý của mệnh đề (p) p 0 1 0 1 0 1 Qua bảng giá trị chân lý của mệnh đề ta nhận thấy rằng p và luôn có cùng giá trị chân lý nên ta có thể nói rằng là tương đương logic với b.Phép hội Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề “p và q” là pq. Phép hội được định nghĩa bởi bảng giá trị chân lý sau đây. p q pq 0 0 0 0 1 0 1 0 0 1 1 1 8
12. Ví dụ 1: Cho các mệnh đề p: “5>2” ; q: “6 là số nguyên tố” r: “Một tam giác đều cũng là tam giác cân” Giá trị chân lý của p, q, r là 1, 0, 1. Khi đó ta có: pq = 0; pr = 1 qr = 0; Ví dụ 2: Bằng cách lập bảng giá trị chân lý ta có: 1.Các mệnh đề p và pp luôn có cùng giá trị chân lý. 2.Mệnh đề p  p luôn có giá trị chân lý bằng 0 (tức là một mệnh đề luôn sai) c.Phép tuyển Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề p hoặc q (p hay q) là pq. Phép tuyển hay phép hoặc được định nghĩa bởi bảng chân lý sau: p q pq 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ 1: Với các mệnh đề p, q, r đã cho ta có: pq = 1; pr = 1 Ví dụ 2: Lập bảng giá trị chân lý ta luôn có mệnh đề p  p là luôn đúng. Nhận xét: Một mệnh đề phức hợp mà luôn đúng bất kể các giá trị chân lý của các mệnh dề thành phần của nó được gọi là hằng đúng. Một mệnh đề mà luôn luôn sai được gọi là mâu thuẫn. Một mệnh đề không phải hằng đúng, cũng không phải mâu thuẫn được gọi là tiếp liên Ví dụ 3 : là luôn đúng nó là hằng đúng.  là luôn luôn sai nó là mâu thuẫn. Phép loại trừ ký hiệu là XOR. p XOR q được định nghĩa bởi bảng chân lý sau: p q p XOR q 0 0 0 0 1 1 1 0 1 1 1 0 p XOR q đúng khi trong 2 mệnh đề p và q có một mệnh đề đúng, một mệnh đề sai. d.Phép kéo theo, ký hiệu là Cho p và q là 2 mệnh đề. Mệnh đề p kéo theo q ký hiệu là p q dùng để diễn đạt phát biểu: nếu p thì q và được định nghĩa bởi bảng chân lý sau: p q p q 0 0 1 0 1 1 1 0 0 1 1 1 9
13. Ví dụ : với n N, ta xét mệnhđề: p: n chia hết cho 5 q: n chia hết cho 9 Lúc đó mệnh đề p q có giá trị xác định cụ thể: n = 45 p: 1 q: 1 p q: 1 n = 15 p: 1 q: 0 p q: 0 n = 16 p: 0 q: 0 p q: 1 Xét mệnh đề p q (1). Khi đó các mệnh đề sau đây gọi là các mệnh đề liên kết với (1) q p (2) p q (3) q p (4) Mệnh đề (1) được gọi là mệnh đề thuận Mệnh đề (2) được gọi là mệnh đề đảo Mệnh đề (3) được gọi là mệnh đề phản Mệnh đề (4) được gọi là mệnh đề phản đảo Các mệnh đề liên kết chia thành 2 cặp tương đương: i/ p q q p ii/ q p p q với mệnh đề (1): Nếu có p thì có q do đó còn nói: p là điều kiện đủ để có q. Mệnh đề (1) tương đương mệnh đề (4) nghĩa là không q thì không p, do đó có thể nói: q là điều kiện cần để có p. e.Phép kéo theo hai chiều (phép tương đương). Ký hiệu là  Cho p, q là 2 mệnhđề. Mệnh đề p tương đương q dùng để diễn đạt phát biểu: p nếu và chỉ nếu q và được định nghĩa bởi bảng giá trị chân lý sau: P q p  q 0 0 1 0 1 0 1 0 0 1 1 1 Mệnh đề p  q được đọc là: p nếu và chỉ nếu q hay còn được phát biểu dưới các dạng khác:  p khi và chỉ khi q  p là điều kiện cần và đủ cho q Độ ưu tiên của các toán tử logic 1.  2. ,  3. ,  Trong đó các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. Ví dụ : 1. x  y có nghĩa là x  y 2. x  y p  q có nghĩa x  y p  q 1.3.3.Biểu thức logic (công thức logic) Trong đại số ta có các biểu thức số học được xây dựng từ các hằng số, các biến số và các phép toán số học. Khi thay thế các biến trong một biểu thức số học bởi các hằng số 10
14. thì kết quả thực hiện các phép toán trong biểu thức là một hằng số. Trong đại số mệnh đề ta có biểu thức logic cũng được xây dựng như sau: a.Định nghĩa: Các mệnh đề chưa xác định p, q, r gọi là các biến mệnh đề. 1.Các biến mệnh đề là các biểu thức 2.Nếu P, Q là các (công thức) biểu thức logic thì P , P  Q, P  Q, P Q , P  Q là các (công thức) biểu thức. 3.Mọi ký hiệu khác không được xác định theo 2 qui tắc 1, 2 đều không là các biểu thức. Ví dụ: p(x, y, z) = x  p q  r là một biểu thức logic với các biến mệnh đề x, p, q, r. b.Sự tương đương logic Hai biểu thức logic E và F theo bộ biến mệnh đề nào đó được gọi là tương đương logic khi E và F luôn có cùng giá trị chân lý trong mọi trường hợp giá trị chân lý của bộ biến mệnh đề. Khi đó ta viết E F hay E  F và đọc là “E tương đương với F”. Như vậy, để chứng minh 2 biểu thức logic là tương đương logic thì có thể lập bảng giá trị chân lý. Ví dụ: Chứng minh p  q r p r  q r Giải: ta lập bảng giá trị chân lý như sau: p q r p  q p r q r p  q r p r  q r 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 Nhìn vào giá trị chân lý trên 2 cột cuối ta thấy: c.Phép biến đổi công thức (biểu thức): Để biến đổi biểu thức một cách thuận tiện, ta qui ước các điều sau: 1.Không viết dấu ngoặc ngoài cùng đối với mỗi công thức (biểu thức). 2.Thay ký hiện  bởi dấu . hoặc bỏ đi. 3.Các phép toán được thực hiện theo thứ tự: , , ,  4.Nếu có dấu phủ định trên một biểu thức thì bỏ dấu ngoặc hai đầu biểu thức đó. Ví dụ :  ( p  q r ) được viết là p q r  p q  r được viết là p q  r d.Các luật của logic mệnh đề Biểu thức logic A gọi là hằng đúng nếu A nhận giá trị 1 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Biểu thức logic A gọi là hằng sai nếu A nhận giá trị 0 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Khi A là hằng đúng thì ta gọi A là một luật, ký hiện là = A. Khi A là hằng sai thì ta gọi A là một mâu thuẫn. Ví dụ : p  p 1 nên ta có một luật = p  p . Luật = p  p gọi là luật bài trung: Trong hai mệnh đề phủ định lẫn nhau, có ít nhất một mệnh đề đúng. 11
15. Các luật logic cơ bản 1. Luật phủ định kép: p p 2. Luật giao hoán: p q q  p , p q q  p 3. Luật kết hợp: p  (q  r) p  q  r , p  (q  r) p  q  r 4. Luật phân phối: p  (q  r) p  q  q  r , p  (q  r) p  q  q  r 5. Luật Demorgan: p q p  q , p q p  q 6. Luật về mối liên hệ giữa p với chính nó, với p , với 0 và 1: p  p p p  p p p 0 0 p  0 p p 1 p p 1 1 p  p 0 p  p 1 7. Luật kéo theo: p q p  q 8. Luật tương đương: p q p q  q p Nhận xét: Có thể dùng các luật logic để biến đổi tương đương các biểu thức logic, hay nói cách khác, để chứng minh 2 biểu thức logic tương đương ta có thể dùng phương pháp biến đổi logic. Ví dụ: Chứng minh p  q r p r  q r Ta biến đổi vế trái về vế phải như sau: Vế trái p  q  r (p  q)  r (p  r)  (q  r) (p r)  (q r)  Vế phải 1.3.4.Các dạng chính tắc a.Dạng chính tắc tuyển Giả sử p1, p2, , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, , pn được gọi là một biểu thức hội cơ bản nếu nó có dạng sau: F = q1 q2   qn với qi = pi hoặc qi pi (i = 1 n). Ví dụ: Biểu thức xyz hoặc x  y  z hoặc x  y  z là các biểu thức hội cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức E (p1, p2, , pn) theo các biến mệnh đề p1, p2, , pn được gọi là có dạng chính tắc tuyển khi E có dạng: E = E1 E2   Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức hội cơ bản theo các biến mệnh đề p1, p2, , pn. Ví dụ : Các biểu thức sau đây có dạnh chính tắc tuyển. E x, y, z x  y  z  x  y  z  x  y  z F p1 , p2 , p3 , p4 p1  p2  p3  p4  p1  p2  p3  p4  p1  p2  p3  p4 Định lý: Mọi biểu thức logic F(p1, p2, , pn) đều có thể viết dưới dạng chính tắc tuyển duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức hội cơ bản trong phép tuyển). Nói cách khác, ta có duy nhất một tập hợp các biểu thức hội cơ bản {E1, E2, , Em} sao cho biểu thức E (p1, p2, , pm) E1  E2   Em. Ví dụ : Tìm dạng chính tắc tuyển của biểu thức: E x,, y z x  z  x y E x, y, z x  z  x  y x  z  x  x  z  y x  z  x  y  z 12
16. x  y  y  z  x  y  z x  y  z  x  y  z  x  y  z x  y  z  x  y  z b. Dạng chính tắc hội Giả sử p1, p2, , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, , pn được gọi là một biểu thức tuyển cơ bản nếu nó có dạng sau: F = q1 q2   qn với qi = pi hoặc qi pi (i = 1 n). Ví dụ: Biểu thức x y z hoặc x  y  z hoặc x  y  z là các biểu thức tuyển cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức E (p1, p2, , pn) theo các biến mệnh đề p1, p2, , pn được gọi là có dạng chính tắc hội khi E có dạng: E = E1 E2   Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức tuyển cơ bản theo các biến mệnh đề p1, p2, , pn. Ví dụ : Các biểu thức sau đây có dạng chính tắc hội. E x, y, z x  y  z  x  y  z  x  y  z F p1 , p2 , p3 , p4 p1  p2  p3  p4  p1  p2  p3  p4  p1  p2  p3  p4 Định lý: Mọi biểu thức logic F(p1, p2, , pn) đều có thể viết dưới dạng chính tắc hội duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức tuyển cơ bản trong phép hội). Nói cách khác, ta có duy nhất một tập hợp các biểu thức tuyển cơ bản {E1, E2, , Em} sao cho biểu thức E (p1, p2, , pm) E1  E2   Em. Ví dụ 1: Tìm chính tắc hội của biểu thức sau: E x, y, z,t x  y y  z z  t E x, y, z,t x  y  zz  tt xx  y  z  tt xx  yy  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t Ví dụ 2: Tìm chính tắc tuyển của biểu thức: x y  z y x  y  z  y x  y  z  x  y  y xz  yz  xy  yy xz  yz  xy x y  y z  x  x yz  xy z  z xyz  xyz  xyz  xyz  xyz  xyz xyz  xyz  xyz  xyz 1.3.5.Vị từ, lượng từ a.Vị từ (Hàm mệnh đề) P(x) là một hàm mệnh đề (một biến) xác định trên tập X nếu với mỗi x X thì P(x) là một mệnh đề. Hàm mệnh đề một biến còn được gọi là vị từ 1-ngôi. 13
17. Nếu P(x) là một hàm mệnh đề xác định trên X thì x được gọi là biến tử, một phần tử cụ thể a X gọi là hằng tử, P(a) là một hàm mệnh đề hoàn toàn xác định. Tương tự ta có hàm mệnh đề m biến, hay vị từ m-ngôi với m N* b.Miền đúng của hàm mệnh đề Giả sử P(x) là một hàm mệnh đề trên X, khi đó miền đúng của P(x) là tập EP(x)={ a X P(a) là mệnh đề đúng} Ví dụ: 2 1. P(x): x -6x+5=0 với x R có EP(x)={ 1,5} 2 2. P(x): x -6x+5 0 với x R có EP(x)= ( ,1)  (5, ) Hàm mệnh đề P(x) xác định trên X gọi là hằng đúng nếu EP(x)=X, gọi là hằng sai nếu EP(x)=, gọi là thực hiện được nếu EP(x)  Ví dụ: 1. P(x): x2+1>0 là hằng đúng trên R 2. P(x): x2+1=0 là hằng sai trên R 3. P(x): 3x-4=0 là thực hiện được trên R nhưng không thực hiện được trên N Hai hàm mệnh đề P(x) và Q(x) cùng xác định trên tập X được gọi là tương đương logic, kí hiệu là P(x) Q(x) hoặc P(x)  Q(x) khi và chỉ khi EP(x)= EQ(x) c.Phép toán trên các hàm mệnh đề Phép phủ định Cho P(x) là một hàm mệnh đề xác định trên X, ta gọi phủ định của P(x) là hàm mệnh đề Px() xác định trên X, nhận giá trị 1 trên tập các phần tử a X , P(a)  0, nhận giá trị 0 trên miền đúng của P(x) E X \ E Ta có: P(x) P(x) E P(x) EP(x) Phép hội Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, hội của P(x) và Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử a X sao cho P(a) 1 Q(a) 1, nhận giá trị 0 trong các trường hợp còn lại. Ta có: EP(x)Q(x) EP(x)  EQ(x) 14
18. Phép tuyển Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, tuyển của P(x) và Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử a X sao cho P(a)  0  Q(a)  0 , nhận giá trị 1 trong các trường hợp còn lại. Ta có: EP(x)Q(x) EP(x)  EQ(x) Phép kéo theo Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) kéo theo Q(x) là hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử a X sao cho P(a) 1 Q(a)  0 , nhận giá trị 1 trong các trường hợp còn lại. Ta có: EP(x) Q(x) (X \ EP(x) )  EQ(x) Phép tương đương Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) tương đương Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử a X sao cho P(a)  Q(a) , nhận giá trị 0 trong các trường hợp còn lại. Ta có: EP(x)Q(x) (X \ (EP(x)  EQ(x) )) (EP(x)  EQ(x) ) d. Lượng từ Cho P(x) là hàm mệnh đề xác định trên X. Ta gọi x X P(x) hiểu là Với mọi x X, P(x) là mệnh đề đúng nếu EP(x)=X, sai trong các trường hợp khác. Ta gọi x X P(x) hiểu là tồn tại x X, P(x) là mệnh đề đúng nếu EP(x) , sai trong các trường hợp khác. Ký hiệu  gọi là lượng từ phổ dụng (với mọi), ký hiệu  gọi là lượng từ tồn tại Như vậy: x X P(x) đúng P(x) hằng đúng trên X x X P(x) đúng P(x) thực hiện được trên X Ví dụ: 1. x R (x 2 1 0) là mệnh đề đúng 2. x R (3x 1 0) là mệnh đề sai 3. x R (3x 1 0) là mệnh đề đúng 4. x N (3x 1 0) là mệnh đề sai e. Lượng từ trên các hàm mệnh đề nhiều biến Cho hàm mệnh đề 2 biến Px,y) xác định trên X x Y. Khi đó với mỗi y cố định x X P(x,y), x X P(x,y) là các mệnh đề, do đó ta được các hàm mệnh đề x X P(x,y), x X P(x,y) xác định theo y Y. Ta có thể áp dụng các lượng từ với mọi và tồn tại lên các hàm mệnh đề này để được các mệnh đề xác định: x X y Y P(x,y), x X y Y P(x,y) , x X y Y P(x,y) , x X y Y P(x,y) f. Mối liên hệ giữa 2 mệnh đề phổ dụng và tồn tại Cho P(x) là hàm mệnh đề xác định trên X, khi đó ta có: 1. x XP(x)  x X P ( x ) ; 2. x XP(x)  x X P ( x ) 1.4 Suy luận toán học & các phương pháp chứng minh 1.4.1 Qui tắc suy luận Giả sử A1, A2, , An, B là các biểu thức logic. Ta nói B là hệ quả logic của A1, A2, , An nếu với mọi bộ giá trị chân lý có thể nhận của bộ biến mệnh đề có mặt trong trong các biểu thức đó mà A1, A2, , An đồng thời nhận giá trị 1 đều có B nhận giá trị 1. 15
19. Khi B là hệ quả logic của A1, A2, , An thì nói rằng có một qui tắc suy luận từ các tiên đề A1, A2, , An tới hệ quả logic B. A1 , A2 , , An Qui tắc suy luận trên được kí hiệu là: hay A1, A2, , An = B B Ta có A1, A2, , An đồng thời nhận giá trị 1 khi và chỉ khi A1  A2   An nhận giá trị 1 Khi đó A1  A2   An B đúng A1  A2   An nhận giá 1 thì B cũng nhận giá trị 1 Hay có qui tắc suy luận có luật Như vậy để chứng minh qui tắc suy luận ta có thể dùng một trong 2 phương pháp sau: 1. Lập bảng giá trị chân lý, xét theo đúng định nghĩa 2. Chỉ ra mệnh đề là hằng đúng. p, p q Ví dụ 1: Chứng minh qui tắc suy luận q Cách 1: Lập bảng giá trị chân lý p q p q 0 0 1 0 1 1 1 0 0 1 1 1 Nhìn vào bảng giá trị chân lý ta thấy có một bộ giá trị của p,q làm cho p,q nhận giá trị 1 thì cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy luận Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh ( p  ( p q)) q 1( hằng đúng) Thực vậy: ( p  ( p q)) q p  (p  q) q (p  p)  (p  q) q p  q q p  q  q 1 (ĐPCM) p q, q r Ví dụ 2: Chứng minh qui tắc suy luận p r Cách 1: Lập bảng giá trị chân lý p q r p q q r p r 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 16
20. 1 1 0 1 0 0 1 1 1 1 1 1 Nhìn vào bảng giá trị chân lý ta thấy có 4 bộ giá trị của p,q, r làm cho p q và q r đồng thời nhận giá trị 1 thì p r cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy p q, q r luận p r Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh (( p q)  (q r)) ( p r) 1( hằng đúng) Thực vậy: (( p q)  (q r)) (p r) (p  q)  (q  r)  p  r (p  q)  p  (q  r)  r q  q  p  r 1 p  r 1 (ĐPCM) 1.4.2 Các qui tắc suy luận cơ bản Trong suy luận toán học người ta thường dùng 28 qui tắc suy luận cơ bản sau, các qui tắc này đã được chứng minh theo 2 phương pháp trên. 2 ví dụ vừa xét là qui tắc suy luận số1 và qui tắc số 3. p q, p p q,q 1. 2. q p p q, q r p  q,q  r 3. 4. p r p  r p q,q p p  q, p 5. 6. p  q q p r,q r p q, p r 7. 8. p  q r p q  r p q,r s p  q,r  s 9. 10. p  r q  s p  r  q  s p q,r s p  q,r  s 11. 12. p  r q  s p  r  q  s p, q p  q 13. 14. p  q p p p p 15. 16. ; p  q p p p q q p p  q 17. ; 18. q p p q p q p  q r p q r p  q r 19. 20. p q r p  q r p r 17
21. p q r p q, p q 21. 22. q p r q p q  q p q, q 23. 24. p p p p p  q r  r p  q p 25. 26. ; p p q p q x   x x  x Q x , P a 27. 28.  a Q a 1.4.3 Hai kiểu suy luận a.Suy luận diễn dịch (Suy diễn): Là suy luận theo các quy tắc suy luận, xác định rằng nếu các tiên đề là đúng thì kết luận rút ra cũng phải đúng. Ví dụ: Từ 2 tiền đề >3 và <4 suy ra 3< <4, trong suy luận này ta đã sử dụng qui tắc suy luận số 13. b.Suy luận có lý: Là suy luận không theo qui tắc suy luận nào để từ tiên đề đã có rút ra được kết luận xác định. Nếu các tiền đề đều đúng thì kết luận chưa chắc đã đúng mà chỉ mang tính chất dự đoán, giả thuyết. Trong toán học thường dùng 2 kiểu suy luận có lý, đó là phép qui nạp không hoàn và phép tương tự. Hai kiểu suy luận này có vai trò đặc biệt quan trọng trong phát minh sáng tạo, nó giúp con người đưa ra những phán đoán về các kết quả mới. 1.4.4 Các phương pháp chứng minh a. Khái niệm về chứng minh A1 , A2 , , An Khi có quy tắc suy luận nếu tất cả các tiền đề A1, A2, , An đều B đúng thì kết luận logic B gọi là kết luận chứng minh và mệnh đề B gọi là đã được chứng minh. Như vậy một kết luận chứng minh là một kết luận logic của các tiền đề đúng. Ví dụ: Có qui tắc suy luận: Với a,b R, nếu a=b thì a2=b2 Đặt A: a=b; B: a2=b2 1/ A:2=2 ; B:22=22 ; có A B nên B:22=22 là một kết luận logic và B cũng là một kết luận chứng minh vì tiền đề A là đúng. 2/ A: -2=2 ; B:(-2)2=22 ; có A B nên B:22=22 là một kết luận logic nhưng B không phải là một kết luận chứng minh vì tiền đề A là sai. b. Kết cấu của chứng minh Một chứng minh có 3 bộ phận cấu thành: 1. Luận đề: Là mệnh đề cần phải chứng minh 2. Luận cứ: Là các mệnh đề được thừa nhận được lấy ra làm tiên đề trong mỗi suy luận. 3. Luận chứng: Là các quy tắc suy luận được vận dụng trong mỗi bước suy luận của chứng minh. c. Các phương pháp chứng minh trong toán học i.Chứng minh theo phương pháp trực tiếp Mệnh đề B gọi là được chứng minh trực tiếp nếu ta chỉ ra được B là kí hiệu logic của các tiền đề đúng A1, A2, , An Ví dụ: Chứng minh trực tiếp định lý: Nếu n là số lẻ thì n2 cũng là số lẻ Chứng minh: Theo giả thiết n là số lẻ n=2k+1, k Z 18
22. n2=4k2+4k+1, k Z hay n2= 2(2k2+2k)+1=2k’+1, k’ Z n2 là số lẻ (ĐPCM) ii.Chứng minh theo phương pháp phản chứng: Là phương pháp sử dụng qui tắc suy luận số 26. p  q r  r p  q p 26. ; p q p q Ví dụ: Chứng minh rằng: Nếu 3n+2 là số lẻ thì n cũng lẻ Đặt p: 3n+2 là số lẻ q: n là số lẻ Ta phải chứng minh p q Giả thiết có q tức là n là số chẵn n=2k, k Z Khi đó ta có 3n+2=3.2k+2=2(3k+1)=2k’ , k’ Z 3n+2 là số chẵn, điều này mâu thuẫn với giả thiết p đã cho 3n+2 là số lẻ. Vậy theo quy tắc suy luận số 26 ta có ĐPCM hay p q iii. Chứng minh theo phương pháp phân chia trường hợp Cho P(x) là một hàm mệnh đề xác định trên X. Giả sử X= X1  X 2   X n với x X P(x),x X P(x), ,x X P(x) X  X  Khi đó ta có quy tắc suy luận 1 2 n i j x XP(x) Ví dụ: Cho n Z, hãy chứng minh n3+2n chia hết cho 3 Ta có n3+2n=n(n2+2) sẽ chia hết cho 3 khi n là bội của 3 Với mỗi n Z, gọi r = n mod 3 khi đó ta có: 1/ r=0 ; 2/ r=1; 3/ r=2 Có 3 trường hợp (r=0)(r=1)(r=2) Xét trường hợp1: với r=0, n có dạng n=3k, k Z n3+2n =3k(9k2+2) chia hết cho 3 Xét trường hợp 2: với r=1, n có dạng n=3k+1, k Z n3+2n =3(k+1)(9k2+6k+3)=(3k+1)3(3k2+2k+1) chia hết cho 3 Xét trường hợp 3: với r=2, n có dạng n=3k+2, k Z n3+2n =3(k+2)(9k2+12k+6)=(3k+2)3(3k2+4k+2) chia hết cho 3 Như vậy trong mọi trường hợp (r=0), (r=1), (r=2) có thể có ta đều chứng minh được n3+2n chia hết cho 3. Vậy có ĐPCM iv. Chứng minh theo qui nạp toán học: Giả sử P(n) là một khẳng định phụ thuộc vào số tự nhiên n, cần phải chứng minh P(n) đúng với n. Ta không thể dùng phép qui nạp hoàn toàn vì tập N là vô hạn, không thể tiến hành kiểm tra tất cả các trường hợp riêng. Nếu dùng phép quy nạp không hoàn toàn để kết luận thì có thể dẫn đến sai lầm. Để khắc phục khó khăn này ta dùng một phương pháp suy luận đặc biệt gọi là phương pháp qui nạp toán học. Giả sử cần chứng minh tính chất đúng đắn của khẳng định P(n) với mọi số tự nhiên n 0 (n Z+), ta thực hiện: 1. Trước tiên kiểm tra P(1) đúng 2. Sau đó chứng minh rằng, với mọi số tự nhiên k 1, từ tính đúng đắn của khẳng định n=k cũng suy ra được khẳng định đúng khi n=k+1. Khi khẳng định đúng với n=k+1 thì khẳng định P(n) được coi là đúng với mọi số tự nhiên n. Một hình thức khác của phương pháp qui nạp toán học: Chứng minh n n0 P(n) là đúng 1. Chỉ ra khẳng định P(n0) là đúng 2. Nếu khẳng định P(k) là đúng thì khẳng định P(k+1) cũng đúng với mọi số tự nhiên k n0 ( hay nếu P(1), P(2), ,P(k) đúng thì P(k+1) cũng đúng) 19
23. Kết luận, khẳng định P(n) đúng với mọi số nguyên n n0 Ví dụ 1: Chứng minh rằng với mọi số tự nhiên n 2 đều phân tích được thành tích của một hay nhiều thừa số nguyên tố. Gọi P(n) là khẳng định: Số tự nhiên n phân tích được thành tích của một hoặc nhiều thừa số nguyên tố. 1. Khi n=2, ta có P2): 2 hay P(2) là đúng 2. Giả sử các khẳng định P(2), P(3), ,P(k) đúng, ta cần chứng minh P(k+1) cũng đúng. Xét số tự nhiên k+1, có 2 khả năng xảy ra: * Nếu k+1 là số nguyên tố thì P(k+1): (k+1) tức P(k+1) là đúng * Nếu k+1 là hợp số thì k+1=a1.a2 với 2 a1 k và 2 a2 k Theo giả thiết qui nạp ta có a1, a2 có thể phân tích được thành tích của một hoặc nhiều thừa số nguyên tố, khi đó k+1= a1. a2 phân tích được thành tích của các thừa số nguyên tố, hay P(k+1) là đúng. Kết luận: Mọi số nguyên n 2 đều phân tích được thành tích của một hay nhiều thừa số nguyên tố. 2 Ví dụ 2: Chứng minh rằng Sn= 1 + 3 + 5 + + (2n-1) = n với mọi số tự nhiên n 1 Chứng minh: 2 1. Khi n=1, ta có S1=1=1 hay S1 là đúng 2. Giả sử khẳng định đúng với n=k>1, k Z+ 2 Nghĩa là ta có: Sk= 1 + 3 + +(2k-1)=k 2 2 Xét Sk+1=1 + 3 + +(2k-1) + (2k+1) = k +2k+1=(k+1) tức là khẳng định đúng với n=k+1. 2 Kết luận: Sn= 1 + 3 + 5 + + (2n-1) = n với mọi số tự nhiên n 1 20
24. CHƯƠNG 2 GIẢI THUẬT & CÁC PHƯƠNG PHÁP ĐẾM 2.1. Thuật toán và các đặc trưng cơ bản của thuật toán 2.1.1. Khái niệm thuật toán Một bài toán hay một vấn đề cần giải quyết thường được diễn đạt theo một sơ đồ chung dưới dạng: A B , trong đó A: Được hiểu là giả thiết, các điều kiện ban đầu hoặc là cái đã cho, đã có khi bắt đầu giải bài toán. B: được hiểu là kết luận, mục tiêu cần đạt được hoặc là cái phải tìm, phải làm ra khi kết thúc bài toán. : Được hiểu là suy luận, giải pháp cần xác định hoặc là một chuỗi các thao tác cần thực hiện, cần thi hành để có được cái phải tìm từ cái đã cho. Như vậy, giải bài toán có nghĩa là xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có cơ sở khoa học thích hợp để tìm được dữ liệu ra (kết quả) theo yêu cầu của bài toán. Một bài toán trên máy tính cũng mang đầy đủ các tính chất của một bài toán nói chung nhưng có thể diễn đạt theo một cách khác: Input: Các dữ liệu vào của bài toán hay A-Thông tin vào Output: Các dữ liệu ra thoả mãn yêu cầu của bài toán hay B-Thông tin ra : Chương trình tạo ra từ các lệnh cơ bản của máy cho phép biến đổi từ A thành B Khi xác định một bài toán trên máy tính thường gặp phải hai khó khăn chính như sau: 1. Thông Tin về A hay B không đầy đủ và không rõ ràng. 2. Thông tin về các điều kiện đặt ra cho cách giải thương không được nêu ra một cách minh bạch. Khi giải quyết bài toán cần khắc phục hoặc bằng các phương pháp khác nhau để hoàn thiện dần các thiếu sót về thông tin của A hoặc B nhằm giải quyết trọn vẹn bài toán theo đúng nhu cầu của người dùng. Ví dụ 1: Cho 2 số tự nhiên a, b. Tìm ước số chung lớn nhất của chúng. Xác định bài toán: A. Xác định thông tin vào: 2 số tự nhiên a, b B. Xác định thông tin ra: Số tự nhiên d thõa mãn: d là ước của a và d là ước của b; d lớn nhất trong tập các ước chung của a và b. Xác định các thao tác xử lý thông tin: Xây dựng một dãy hữu hạn các thao tác cho phép tính được d từ a và b. Ví dụ a=16 b=24 d=8 Ví dụ 2: Cho một dãy số nguyên dương a1, a2, , an Hãy tìm từ dãy trên một dãy con (không nhất thiết phải liên tiếp) tăng và có độ dài là dài nhất. Xác định bài toán: A. Xác định thông tin vào: + một dãy số nguyên dương a1, a2, , an + Mỗi số được xác định bởi 2 yếu tố là giá trị của số và vị trí (số thứ tự) của số đó trong dãy. B. Xác định thông tin ra: + Một dãy lấy từ dãy số đã cho: ai1, ai2, , aik (dãy con thu được sau khi đã gạch bỏ một số phần từ của dãy đã cho) Dãy con này phải có 2 tính chất: 1. Tăng ai1< ai2 < <aik 2. Có độ dài là dài nhất trong các dãy có thể lấy được. 21
25. Xác định các thao tác xử lý thông tin: 1. Lần lượt duyệt các phần tử của dãy đã cho 2. Phải quyết định xem loại bỏ phần tử nào để dãy còn lại là tăng và dài nhất. Nhận xét: 1. Việc xác định bài toán là khá quan trọng, nó ảnh hưởng rất lớn đến cách thức và chất lượng của việc giải quyết bài toán. 2. Một bài toán cho dù được diễn đạt bằng các thông tin chính xác thì cũng phải giả định là phần lớn thông tin về A và B là tiềm ẩn trong đầu người giải, thông báo về A hoặc B chỉ là biểu tượng gợi nhớ đến các thông tin tiềm ẩn đó. 3. Bước đầu tiên để xác định một bài toán là phải phát biểu lại bài toán một cách chính xác theo ngôn ngữ của riêng mình vì đó chính là cách ta tiếp cận bài toán, hiểu bài toán. Bước tiếp sau là tìm hiểu các thông tin vào A và thông tin ra B, tìm các mối liên hệ giữa chúng. Qua ví dụ trên, chúng ta thấy rằng để biểu diễn lời giải cho một bài toán trên máy tính (dù là rất đơn giản), chúng ta phải làm rõ tất cả mọi chi tiết của cách giải, hướng dẫn cụ thể từng bước, từng bước một thì máy tính mới có thể thi hành được. Cách biểu diễn lời giải vấn đề một cách rõ ràng, chi tiết để có thể thi hành được trên máy tính được gọi là thuật toán. Định nghĩa: Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề. 2.1.2. Các đặc trưng cơ bản của thuật toán Thuật toán có vai trò rất quan trọng trong khoa học máy tính. Để có thể lập trình giải bài toán trên máy tính, ta cần có một thuật toán bảo đảm những tính chất nhất định. Khi mô tả một thuật toán chúng ta cần chú ý đến các tính chất sau đây: 1. Nhập (input): Mỗi thuật toán cần có một số (có thể bằng 0) dữ liệu vào. Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu này cần được lấy từ tập hợp giá trị cụ thể nào đó. 2. Xuất (output): Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra. Đó là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào và tùy theo chức năng mà thuật toán đảm nhiệm, đó là kết quả của sự thực hiện thuật toán 3. Tính xác định (definiteness): ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng. Không thể gây nên sự nhập nhằng, lẫn lộn, tùy tiện. Hay nói cách khác, trong cùng một điều kiện, hai bộ xử lý cùng thực hiện một bước của thuật toán thì phải cho cùng một kết quả. 4. Tính hữu hạn dừng (finiteness): Một thuật toán bao giờ cũng phải dừng lại sau một số hữu hạn bước. 5. Tính đúng đắn: Sau khi thực hiện tất cả các lệnh của thuật toán ta phải được kết quả mong muốn, kết quả đó thường được xác định theo định nghĩa có trước. 5. Tính hiệu quả (về thời gian): Thuật toán cần phải được thực hiện một cách chính xác và trong một khoảng thời gian cho phép. Hoặc có thể hiểu: Tính hiệu quả của một thuật toán được đánh giá dựa trên các tiêu chuẩn sau: 1. Dung lượng bộ nhớ cần có 2. Số các phép tính cần thực hiện 3. Thời gian cần thiết để chạy chương trình 4. Có dễ hiểu đối với con người không 5. Có dễ cài đặt trên máy không. 6. Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài toán có dạng như mong muốn, chứ không phải chỉ áp dụng được cho một số trường hợp đặc biệt nào đó. Điều này 22
26. có nghĩa là thuật toán có thể làm việc với các dữ liệu khác nhau trong một miền xác định và luôn dẫn đến kết quả mong muốn. Mở rộng khái niệm thuật toán: Để có thể giải các bài toán bằng máy tính ta thường phải có quan niệm rộng hơn về thuật toán, với các đặc điểm sau: 1. Không cần xác định toàn bộ lời giải, các thao tác theo từng bước một cách chính xác, đơn trị và rõ ràng. Thay vào đó chỉ cần chỉ ra một cách chuyển từ một bước giải i tới bước giải kế tiếp i+1 và tìm cách chia nhỏ bài toán thành các bài toán con, đó chính là thuật toán đệ quy để giải các bài toán tổng quát. 2. Có nhiều bài toán không có cách giải đúng, hoặc cách giải đúng không thể chấp nhận được do hạn chế về thời gian chạy và kích thước bộ nhớ. Nhưng nếu cháp nhận kết quả gần đúng thì có thể tồn tại nhiều cách giải đỡ phức tạp và có hiệu quả hơn, đó chính là các thuật toán Heuristic để giải các bài toán gần đúng. 2.1.3. Các phương pháp biểu diễn thuật toán Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn ngữ toán học như: “ta có”, “điều phải chứng minh”, “giả thuyết”, và sử dụng những phép suy luận Toán học như phép suy ra, tương đương, Thuật toán là một phương pháp thể hiện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất định. Để có thể truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta có các phương pháp biểu diễn thuật toán sau: 1. Dùng ngôn ngữ tự nhiên 2. Dùng lưu đồ hay sơ đồ khối 3. Dùng mã giả a. Dùng ngôn ngữ tự nhiên Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật toán. Phương pháp này không yêu cầu người viết thuật toáncũng như người đọc thuật toán phải nắm được các quy tắc. Tuy vậy cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng ngôn ngữ tự nhiên. b. Dùng lưu đồ - sơ đồ khối Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý. Lưu đồ là một hệ thống các nút có hình dạng khác nhau theo qui ước, thể hiện các chức năng khác nhau và được nối với nhau bởi các cung. Lưu đồ được tạo bởi 4 thành phần chủ yếu sau đây: 1/ Nút giới hạn: được biểu diễn bởi hình ôvan có ghi chữ bên trong như : Các nút trên còn được gọi là nút đầu và nút cuối của lưu đồ. 2/ Nút thao tác: Gồm có 2 loại: Thao tác nhập/xuất được biểu diễn bởi hình bình hành và Thao tác xử lý được biểu diễn bởi hình chữ nhật. Ví dụ: k:=1; Nhập/ xuất a,b S:=S+k 23
27. 3/ Nút điều kiện: Thường là một hình thoi có ghi điều kiện cần kiểm tra. Trong các cung nối với nút này có 2 cung ra chỉ hướng đi theo 2 trường hợp: điều kiện đúng và điều kiện sai. F a=0 T 4/ Cung (mũi tên): là các đường nối từ nút này đến nút khác của lưu đồ, chỉ hướng đi của thuật toán. Hoạt động của thuật toán theo lưu đồ được bắt đầu từ nút đầu tiên. Sau khi thực hiện các thao tác hoặc kiểm tra điều kiện ở mỗi nút thì bộ xử lý sẽ theo một cung để đến nút khác. Quá trình thực hiện thuật toán dừng khi gặp nút kết thúc hay nút cuối. Ví dụ 1: Lập lưu đồ thuật toán giải phương trình bậc 1: ax+b = 0 Bắt đầu a, b True a 0 x False PT vô nghiệm PT vô số nghiệm Kết thúc Ví dụ 2: Lập sơ đồ khối biểu diễn thuật toán tìm USCLN của 2 số tự nhiên a, b 24
28. Begin a, b 0 a b End a:=a-b b:=b -a Hình 2.2: Lưu đồ thuật toán tìm ước số chung lớn nhất của 2 số a,b. 25
29. c. Dùng giả mã Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh, để mô tả một thuật toán nhỏ phải dùng một không gian rất lớn. Nếu biểu diễn thuật toán một cách hiệu quả, người ta thường dùng giả mã (pseudocode). Khi thể hiện thuật thuật toán bằng giả mã, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Dùng giả mã vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt được nội dung của thuật toán (tất nhiên là trong giả mã ta vẫn dùng một phần ngôn ngữ tự nhiên). Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn giả mã sẽ bị phụ thuộc vào ngôn ngữ lập trình đó, chẳng hạn là ngôn ngữ lập trình PASCAL, nhất là cấu trúc điều khiển ngôn ngữ lập trình cấu trúc chọn, cấu trúc lặp. Trong giả mã ta còn sử dụng cả các ký hiệu toán học, các biến, và đôi khi cả cấu trúc kiểu thủ tục. Cấu trúc thuật toán kiểu thủ tục thường được sử dụng để trình bày các thuật toán đệ qui hay các thuật toán quá phức tạp cần phải được trình bày thành nhiều cấp độ. Cùng với việc sử dụng các biến, trong thuật toán rất thường gặp một phát biểu, hành động đặt (hay gán) một giá trị cho một biến. Chẳng hạn như hành động tăng biết i lên 1 có thể được viết như sau: i := i + 1 hay i = i + 1 Các cấu trúc thường được sử dụng trong giả mã dựa theo ngôn ngữ lập trình PASCAL gồm: Cấu trúc chọn: if (điều kiện) then (hành động) if (điều kiện) then (hành động) else (hành động) Cấu trúc lặp: while (điều kiện) do (hành động) Repeat (hành động) Until (điều kiện) for (biến) := (giá trị đầu) to (giá trị cuối) do (hành động) for (biến) := (giá trị đầu) downto (giá trị cuối) do (hành động) Cấu trúc nhảy goto. Ngoài ra người ta còn sử dụng lệnh ngắt vòng lặp break. Dưới đây là các thuật toán được biểu diễn bằng giả mã (sử dụng các cấu trúc điều khiển của ngôn ngữ lập trình PASCAL). Trước khi viết các bước thực hiện thuật toán ta thường ghi rõ những gì được cho trước (phần nhập) và kết quả cần đạt được (phần xuất). Ví dụ 1: Giải phương trình bậc nhất ax+b=0; a, b, x R Input : các hệ số a,b Outputt: nghiệm x hoặc thông báo PT vô nghiệm Thuật toán với ngôn ngữ tự nhiên: 0. Bắt đầu thuật toán 1. Nhập hệ số a, b 2. Kiểm tra xem a =0 hay không + Nếu có thì kiểm tra tiếp xem b = 0 hay không - Nếu có thì kết luận phương trình vô số nghiệm, chuyển sang bước 5 - Nếu không thì kết luận phương trình không xác định, chuyển sang bước 5 + Nếu không thì chuyển sang bước 3 3. Tính nghiệm x=-b/a 4. Xuất nghiệm x 5. Kết thúc 26
30. Thuật toán giả mã: Begin 1. Read(a, b) 2. if a=0 then If b = 0 then Else Else 3. x:=-b/a; 4. Write(x) End; Ví dụ 2: Tìm USCLN của 2 số tự nhiên a, b. Input : Hai số tự nhiên a, b Outputt: Số tự nhiên d là ước của a và d là ước của b; d lớn nhất trong tập các ước chung của a và b. Thuật toán giả mã: Begin 1. Read(a,b) 2. While a b then a:=a-b Else b:=b-a 3.d:=a 4. Write(d) End; Hoặc có thể xây dựng thành thủ tục sau: Function USCLN1(a,b:word):word; Begin While a b then a:= a-b Else b:=b-a; USCLN:=a; End; Function USCLN2(a,b:word):word; Var r: word; Begin While b<>0 Do Begin r:= a mod b; a:= b; b:= r; End; USCLN:=a; End; 2.2. Thuật toán đệ quy 2.2.1. Khái niệm đệ quy Đệ quy là một khái niệm tồn tại trong cuộc sống, trong toán học, trong lập trình. Đệ quy cho một phương pháp ngắn gọn và sáng sủa để mô tả các đối tượng cũng như một số quá trình. Như vậy đệ quy là một phương pháp xác định tập hợp các đối tượng thỏa mãn một yêu cầu nào đó. Nó bao gồm các quy tắc, trong đó một số quy tắc dùng để xác 27
31. định các đối tượng ban đầu, còn quy tắc khác dùng để xác định các đối tượng tiếp theo nhờ các đối tượng ban đầu đã được xác định. Ví dụ 1: Định nghĩa số tự nhiên 0 là số tự nhiên n là số tự nhiên nếu (n -1) là số tự nhiên Định nghĩa trên được xuất phát từ hệ các mệnh đề Pê a nô về số tự nhiên : i.0 là một số tự nhiên ii.0 không phải là số tự nhiên kề sau của bất kỳ số tự nhiên nào iii.Mọi số tự nhiên n có một và chỉ một số tự nhiên n’ kề sau nó iv.Nếu m là số tự nhiên kề sau của số tự nhiên n và m là số tự nhiên kề sau của số tự nhiên k thì n = k v.Nếu A  N sao cho 1. 0 A 2. m A m’ A thì A  N Theo tiên đề 5 để có khái niệm với  số tự nhiên n ta có thể định nghĩa qui nạp như sau: Cho định nghĩa với n = 0 Nếu có định nghĩa với n thì có định nghĩa với n’ Thậy vậy, Gọi A là tập các phần tử n N đã được định nghĩa thì A thõa mãn v.1 và v.2 của tiên đề 5 nên A=N, tức là n N đều đã được định nghĩa. Ví dụ 2: Hàm giai thừa n! với n là số nguyên dương được tính như sau 0! =1 n! = n (n - 1)! nếu n > 0 1 nếu n=0 Hay n!= n(n-1)! nếu n>0 Như vậy, một khái niệm X gọi là định nghĩa theo đệ quy nếu trong định nghĩa X có sử dụng ngay chính khái niệm X. Thuật toán đệ quy: Nếu lời giải của bài toán T được thực hiện bởi lời giải của bài toán T’ có dạng như T thì đó là lời giải đệ quy. Giải thuật chứa lời giải đệ quy gọi là giải thuật đệ quy. Một thuật toán được gọi là đệ quy nếu nó giải quyết bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn. Ví dụ : Xét bài toán tìm một từ trong từ điển Cho một quyển từ điển được xếp theo vần a, b,c, và một từ cho trước. Hãy tìm và tra nghĩa của từ đã cho. Thuật toán dưới dạng giả mã BEGIN IF THEN ELSE BEGIN + ; + ; + IF THEN ELSE ; END; 28
32. END; Ta thấy sau mỗi lần từ điển được tách đôi thì một nửa thích hợp sẽ lại được tìm kiếm bằng một chiến thuật như đã dùng trước đó. Có một trường hợp đặc biệt, khác với mọi trường hợp trước, sẽ đạt được sau nhiều lần tách đôi, đó là trường hợp từ điển chỉ còn duy nhất một trang. Lúc đó việc tách đôi ngừng lại và bài toán đã đủ nhỏ để ta có thể giải quyết trực tiếp bằng cách tìm từ mong muốn trên trang đó, chẳng hạn bằng cách tìm tuần tự. Trường hợp đặc biệt này gọi là trường hợp suy biến. 2.2.2. Chương trình con đệ quy Một chương trình con (hàm hoặc thủ tục) được gọi là đệ quy nếu trong quá trình thực hiện nó có phần phải gọi đến chính nó. Có những ngôn ngữ lập trình cho phép chương trình con đệ quy nhưng cũng có những ngôn ngữ khác lại không cho phép. Pascal cho phép dùng đệ quy với chương trình con. Cấu trúc chính của một chương trình con đệ quy gồm 2 phần: Phần cơ sở và phần đệ quy Phần cơ sở: Bao gồm các trường hợp dừng mà có thể trực tiếp giải quyết được ngay (trường hợp suy biến). Phần đệ quy: Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán ở cấp độ thấp hơn (điều kiện kiểm soát đệ quy). Ví dụ 1: Hàm tính giai thừa của n Function gt(n: byte): longint; Begin If n = 0 then gt: = 1 (phần cơ sở) Else gt: = n * gt(n - 1); (phần đệ quy) End; Trong thuật toán tính giai thừa n ở trên, có một bước mà ta tính (n-1)! để từ đó tính ra kết quả. Ðó là bước 2 trong trường hợp n > 0. Chính bước tính (n-1)! này trong thuật toán làm cho thuật toán trở thành thuật toán đệ quy. Ta còn gọi bước này là bước thực hiện đệ quy. Khi có lệnh gọi hàm, chẳng hạn x:=gt(5) thì máy sẽ ghi nhớ là gt(5):=5*gt(4) và đi tính gt(4) Kế tiếp máy lại ghi nhớ gt(4):=4*gt(3) và đi tính gt(3) Kế tiếp gt(3):=3*gt(2) và đi tính gt(2) Kế tiếp gt(2):=2*gt(1) và đi tính gt(1) Kế tiếp gt(1):=1*gt(0) Theo định nghĩa của hàm gt thì gt(0)=1 máy sẽ quay ngược lại Gt(1)=1*1=1 Gt(2)=2*gt(1)=2 Gt(3)=3*gt(2)=3*2 Gt(4)=4*gt(3)=4*3*2 Gt(5)=5*gt(4)=5*4*3*2=120 Đặc điểm của chương trình con đệ quy: 1. Trong CTC đệ quy có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán đã thu nhỏ hơn trước (phần hạ bậc) 3. Có một trường hợp đặc biệt: trường hợp suy biến: bài toán sẽ được giải quyết khác hẳn và gọi đệ qui cũng kết thúc. Ví dụ 2: Tìm ước số chung lớn nhất của 2 số tự nhiên a, b Người ta nhận thấy: a nếu b=0 29
33. USCLN(a, b)= USCLN(b, phần dư a/b ) nếu b<>0 Do vậy hàm USCLN có thể viết đệ qui như sau: Function USCLN(a, b:Integer): Integer; Begin If b=0 then uscln:=a Else Uscln:=uscln(b, a mod b); End; Hay Function USCLN(a, b:Integer): Integer; Var r: integer; Begin r:= a mod b; If r=0 then uscln:=a Else Uscln:=uscln(b, r); End; Khi thiết kế thuật toán đệ quy thì ta cần phải thực hiện các yêu cầu sau: Xác định được phần cơ sở của thuật toán đệ quy Xác định được phần đệ quy Cần lưu ý rằng phần cơ sở luôn luôn phải có hay nói cách khác là phần đệ quy luôn luôn phải nằm trong điều kiện kiểm soát dừng đệ quy, vì nếu không thì thuật toán sẽ bị lặp vô hạn do việc gọi đệ quy luôn được thực hiện. 2.2.3. Một số bài toán đệ quy cơ bản a. Dãy số Fibonaci Bài toán được đặt ra đầu tiên bởi nhà toán học Fibonaci đưa ra vào thế kỷ XIII trong tác phẩm Liberabaci, dựa trên sự sinh sản của họ nhà thỏ. Nội dung của bài toán phát biểu như sau: Một cặp thỏ mới sinh (một con đực và một con cái) được thả lên một hòn đảo. Giả sử rằng một cặp thỏ chưa sinh sản được trước khi đầy hai tháng tuổi. Từ khi chúng đầy hai tháng tuổi, mỗi tháng chúng sinh được một cặp thỏ con (một con đực và một con cái). Hãy xây dựng công thức truy hồi tính số cặp thỏ có được sau n tháng, giả thiết các con thỏ là trường thọ. Ta có thể giải quyết bài toán này như sau: Gọi fn là số cặp thỏ có được sau n tháng thì Với n=1 (ở tháng thứ nhất) f1 = 1 (cặp ban đầu) Với n=2 (ở tháng thứ hai) f2 = 1 (cặp ban đầu chưa sinh sản được) Với n=3 ( ở tháng thứ 3) f3 = 2 (Cặp thỏ bố mẹ ban đầu và cặp thỏ con mới được sinh ra) f4 = 3 (cặp ban đầu sinh thêm, cặp con sinh ra ở n=3 chưa sinh được) f5 = 5 (cặp con sinh ở n=3 bắt đầu sinh sản được) f6 = 8 (cặp con sinh sản tiếp) Như vậy, nếu mỗi cặp thỏ ở tháng thứ (n - 1) đều sinh con thì fn = 2*(n - 1) nhưng không phải như vậy, trong các cặp thỏ ở tháng thứ (n -1) chỉ có một cặp thỏ đã có ở tháng thứ (n - 2) mới sinh con ở tháng thứ n thôi. Do đó fn = fn - 2 + fn - 1 Vì vậy ta có công thức đệ quy tính fn n=1, 2, 30
34. 1 nếu n 2 f = n fn – 2 + fn - 1 nếu n > 2 Dãy số 1 1 2 3 5 8 13 21 được gọi là dãy số Fibonaci Xây dựng hàm đệ quy tính fn Function Fibo (n: byte): Word; Begin If n <= 2 then Fibo: = 1 Else Fibo: = Fibo (n - 1) + Fibo (n - 2); End; b. Bài toán “Tháp Hà Nội” Đây là trò chơi xếp hình rất phổ cập vào cuối thế kỷ 19, nội dung của bài toán được phát biểu như sau: Tương truyền rằng tại một ngôi tháp tại Hà Nội có một tấm đế bằng đồng trên đó có ba cọc bằng kim cương. Từ lúc khai thiên lập địa, trên một trong ba cái cọc thượng đế đã để 64 chiếc đĩa bằng vàng với đường kính giảm dần. Ngày đêm các nhà sư dịch chuyển đĩa sang một chiếc cọc khác theo quy tắc: Mỗi lần chỉ được dịch chuyển một đĩa, mỗi đĩa có thể dịch chuyển từ một cọc này sang cọc khác bất kỳ, nhưng không được để một chiếc đĩa lên trên một đĩa khác có đường kính nhỏ hơn. Ngày tận thế sẽ đến khi tất cả các đĩa được chuyển sang một chiếc cọc khác. Giả sử Hn là số lần dịch chuyển cần thiết để giải bài toán Tháp Hà Nội có n đĩa. Hãy lập hệ thức truy hồi đối với dãy Hn. Ta có thể phát biểu bài toán tháp Hà Nội cổ dưới dạng sau: Có 3 cột A, B, C. Trên một cột, gọi là cột A có một chồng gồm n đĩa bằng gỗ hình tròn to nhỏ khác nhau được xuyên lỗ ở giữa tựa như những đồng xu và đặt chòng lên nhau để tạo thành một tòa tháp. Người chơi phải chuyển được tòa tháp sang cột B A theo các quy tắc sau: a. Người chơi được sử dụng cột còn lại để đặt tạm các tầng tháp b. Mỗi lần chỉ được chuyển 1 tầng tháp từ một cột sang một trong hai cột còn lại. c. Không bao giờ được đặt tầng tháp lớn lên trên tầng tháp nhỏ. Hãy tìm cách giải bài toán trên với số lần chuyển ít nhất. Hoặc bài toán: Có 3 cột A, B, C và n đĩa kích thước khác nhau ở cột A, đĩa to ở dưới đĩa bé ở trên. Hãy chuyển các đĩa từ cột A sang cột B sao cho: và n đĩa kích thước khác nhau ở cột A, đĩa to ở dưới đĩa bé ở trên. Hãy chuyển các đĩa từ cột A sang cột B sao cho: Mỗi lần chỉ chuyển được một đĩa. Một đĩa có thể chuyển sang một cột bất kỳ nhưng khi chuyển phải tuân theo quy tắc đĩa to ở dưới, đĩa bé ở trên. Ta có thể phân tích theo kiểu đệ quy như sau: Để chuyển n đĩa từ cột A sang cột B lấy C làm trung gian người ta tìm cách: Chuyển (n - 1) đĩa từ cột A sang cột C lấy B làm trung gian Chuyển chiếc to nhất (còn lại) từ cột A sang cột B Chuyển (n - 1) đĩa từ cột C sang cột B Ta xây dựng thủ tục chuyển theo thuật toán đệ quy như sau Procedure chuyen (n, A, B, C: byte); Begin 31
35. If n = 1 then writeln(A, ‘ ’,B) Else Begin chuyen (n - 1, A, C, B); chuyen (1, A, B, C); chuyen (n - 1, C, B, A); End; End; 2.3. Thuật toán quay lui 2.3.1. Bài toán liệt kê Nếu như trong bài toán đếm, ta chỉ cần đếm số cấu hình tổ hợp là bao nhiêu thì trong nhiều trường hợp, ta còn phải chỉ rõ những cấu hình tổ hợp đó là những cấu hình. Bài toán đưa ra danh sách tất cả cấu hình tổ hợp có thể có, được gọi là bài toán liệt kê. Bài toán: Cho một tập A và một tính chất T, hãy xây dựng tất cả các cấu hình (a1, a2, ,an) xuất phát từ A sao cho mỗi cấu hình đều thoả mãn tính chất T. Ví dụ: A = {0, 1}, T là 1 dãy có n phần tử. Xây dựng tất cả các cấu hình xuất phát từ A sao cho mỗi cấu hình đều thỏa mãn tính chất T chính là liệt kê tất cả các xâu nhị phân có độ dài n. Với n = 3 thì 23 = 8 dãy 1 0 1 0 1 1 0 0 1 0 1 0 1 000 001 010 011 100 101 110 111 Với bài toán này ta phải xây dựng thuật toán để xác định tất cả các cấu hình đảm bảo 2 nguyên tắc sau: Không được lặp lại một cấu hình Không được bỏ sót một cấu hình Có thể nói rằng phương pháp liệt kê là cách cuối cùng để có thể giải một số bài toán tổ hợp hiện nay. Khó khăn chính của phương pháp này là sự “bựng nổ tập hợp”. Để xây dựng chừng một tỷ cấu hình và giả thiết rằng mỗi thao tác xây dựng mất khoảng một giây, ta phải bỏ ra khoảng 31 năm mới giải xong. Tuy nhiên với sự phát triển của máy tính điện tử, bằng phương pháp liệt kê, nhiều bài toán tổ hợp đó tìm thấy lời giải. Mặt khác, chính sự nỗ lực tìm kiếm những giải pháp hữu hiệu cho những bài toán khó thuộc lĩnh vực này, đã thúc đẩy mạnh mẽ sự phát triển của nhiều ngành toán học. Trong phần này, chúng ta sẽ trình bày phương pháp liệt kê thường được sử dụng nhất, đó là thuật toán quay lui. 2.3.2. Thuật toán quay lui Tư tưởng của thuật toán quay lui xuất phát từ bài toán có tên gọi “Hoàng tử cứu công chúa“. Nội dung của bài toán như sau: Công chúa bị một con quỷ nhốt trong một cái hang sâu có rất nhiều đường đi (mỗi ngã rẽ đặc trưng bởi một đỉnh nào đó). Để cứu được công chúa thì bắt buộc hoàng tử phải tìm một cách nào đó để có thể đi qua tất cả các đường đi trong hang. Rõ ràng yêu cầu đề ra là khi đã đi rồi thì không được đi lại (không lặp) và hơn nữa phải không được bỏ sót một đường đi nào (vét cạn hết tất cả các đường đi). 32
36. Để làm được điều đó hoàng tử chỉ có cách là chuẩn bị một cuộn dây dài và buộc một đầu dây vào cửa hang sau đó bắt đầu đi vào hang theo nguyên tắc sau: Mỗi khi đi đến đâu thì đánh dấu các đường đã đi (tránh lặp lại) Nếu còn đi được thì cứ đi tiếp (để không bỏ sót) Nếu không còn đường đi nữa thì quay về mức trên vừa đi để tìm đường khác đi tiếp (quay lui) Vậy tư tưởng chính của thuật toán quay lui là việc xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng sao cho thoả mãn : Không được lặp lại cấu hình nào Không bỏ sót cấu hình nào Nội dung Thuật toán Giả sử cấu hình cần xây dựng có dạng x = (x1, x2, ,xn) trong đó xi A (i =1, 2, ,n) Mỗi cấu hình x đều thoả mãn tính chất T, người ta tiến hành quy nạp như sau: - Giả sử đã xác định được (i - 1) thành phần của cấu hình (x1, x2, ,xi - 1 ) lời giải bộ phận cấp (i - 1) - Tiến hành xây dựng thành phần thứ i của cấu hình xi bằng cách duyệt tất cả các khả năng đề cử của xi Đánh số các khả năng đề cử cho xi từ 1 đến ni Với mỗi khả năng j (j = 1,2, , ni ) xét 2 khả năng Khả năng 1: Nếu chấp nhận j thì ta sẽ đi xác định xi theo j sau đó kiểm tra nếu i = n thì ghi nhận thêm một cấu hình mới, nếu i do if then Begin If i = n then else Try (i+1); End; End; Sau khi xây dựng thủ tục đệ quy, chương trình chính có dạng: BEGIN Khoitao; {khởi tạo các giá trị ban đầu cho các biến sử dụng trong chương trình chính} Try (1); Readln; END. Trong thủ tục quay lui điều quan trọng nhất là ta phải xác định được tập đề cử xi và xác định điều kiện chấp nhận j. Thông thường giá trị này, ngoài việc phụ thuộc j , còn phụ thuộc vào việc đã chọn các khả năng tại i-1 bước trước. Trong những trường hợp như vậy, 33
37. cần phải ghi nhớ trạng thái mới sau khi xác định xi theo j và trả lại trạng thái cũ sau lời gọi của Try (i+1). Việc này được thực hiện thông qua biến trạng thái (mảng lôgic). Ví dụ 1: Hãy liệt kê tất cả các dãy nhị phân độ dài n Giả sử dãy nhị phân có độ dài n là một véc tơ nhị phân gồm n thành phần (a1, a2, ,an) trong đó ai {0, 1}. Cần xây dựng thành phần thứ i của cấu hình tức là xây dựng ai (ai {0, 1}) ai có tập giá trị đề cử là {0, 1} ai có điều kiện chấp nhận: Không có điều kiện chấp nhận Thủ tục quay lui xây dựng thành phần ai Procedure Try(i: integer); Var j: integer; Begin For j: = 0 to 1 do Begin a[i]: = j; If i = n then ghi nhận else Try (i+1); End; End; Trong thủ tục trên cần xây dựng thêm các thủ tục: ghi nhận, khởi tạo. Chương trình liệt kê dãy nhị phân Program Daynhiphan; Uses crt; var n,d:integer; a:array[1 20] of integer; procedure KHOITAO; begin write('nhap do dai day nhi phan n= '); readln(n); d:=0; end; procedure GHINHAN; var i:integer; begin d:=d+1; write('day nhi phan thu',d:3,': '); for i:=1 to n do write(a[i]:2);writeln; end; procedure TRY(i:integer); var j:integer; begin for j:=0 to 1 do begin a[i]:=j; if i=n then GHINHAN else Try(i+1); end; end; BEGIN 34
38. khoitao; Try(1); readln; END. Ví dụ 2: Liệt kê tất cả các hoán vị của tập n số tự nhiên đầu tiên {1, 2, , n} Gọi hoán vị của tập A = {1, 2, , n} là một bộ gồm n thành phần (a1, a2, ,an) trong đó ai A, i = 1,2, ,n và ai, aj đôi một khác nhau. Ta đi xây dựng thành phần thứ i của cấu hình ai ai có tập giá trị đề cử là 1, 2, ,n ai có điều kiện chấp nhận: Giá trị chưa được dùng và để kiểm soát người ta dùng mảng logic b: array[1 n] of Boolean; - Nếu b[j] = True thì j chưa dùng - Nếu b[j] = False thì j đã được dùng Với mỗi giá trị đề cử j nếu b[j] = True thì j được chấp nhận và ta đi xác định ai theo j và sau đó đặt b[j] = False (để xác định rằng j đã được dùng rồi) Thủ tục quay lui xây dựng thành phần thứ i của cấu hình Procedure Try(i: integer); Var j: integer; Begin For j: = 1 to n do If b[j] then {chấp nhận j} Begin a[i]: = j; {xác định a[i] theo j} b[j]: = False; {ghi nhận trạng thái mới} If i = n then ghi nhận Else Try (i+1); {xây dựng thành phần thứ i + 1} b[j]: = True; {trả lại trạng thái cũ} End; End; Chương trình liệt kê các hoán vị program hoanvi; uses crt; var n,d:integer; a:array[1 20] of integer; b:array[1 20] of boolean; procedure KHOITAO; var i:integer; begin write('n=');readln(n); for i:=1 to n do b[i]:=true; d:=0; end; procedure GHINHAN; var i:integer; begin d:=d+1; 35
39. write('Hoan vi thu',d:3,':'); for i:=1 to n do write(a[i]:3); writeln; end; procedure Try(i:integer); var j:integer; begin for j:=1 to n do if b[j]= true then {chap nhan j} begin a[i]:=j; {xac dinh a[i] theo j} b[j]:=false; {ghi nhan trang thai moi} if i=n then GHINHAN else Try(i+1); b[j]:=true; {tra lai trang thai cu} end; end; BEGIN khoitao;Try(1); readln; END. 2.4. Các nguyên lý đếm cơ bản 2.4.1. Phép đếm Cho A là một tập hợp khác rỗng, để xác định số phần tử của tập hợp A ta thường thực hiện việc đếm bằng cách lần lượt gán cho các phần tử của A các số tự nhiên kế tiếp nhau, và số tự nhiên đầu tiên (được dùng để gán cho phần tử đầu tiên được xem xét) là 1. Nếu quá trình này kết thúc với số tự nhiên n (được gán cho phần tử cuối cùng) thì ta nói A là một tập hợp hữu hạn và có n phần tử. 2.4.2. Nguyên lý đếm cộng Cơ sở của nguyên lý cộng là mối liên hệ giữa số phần tử của một tập hợp với số phần tử của các tập hợp con tạo thành phân hoạch của tập hợp đã cho, được phát biểu trong mệnh đề sau đây: Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau, nghĩa là A  B = . Khi ấy ta có: | A  B | = | A | + | B | Một cách tổng quát: Nếu A1, A2, , An là các tập hợp hữu hạn rời nhau, nghĩa là phần giao của hai tập hợp bất kỳ trong n tập hợp là rỗng, thì số phần tử của phần hội của các tập hợp trên bằng tổng của các số lượng phần tử trong mỗi tập hợp: | A1  A2  . . .  An | = | A1 | + | A2 | + . . . + | An | Nguyên lý cộng : Nếu có m1 cách chọn đối tượng a1, m2 cách chọn đối tượng a2, , mn cách chọn đối tượng an và nếu cách chọn đối tương ai không trùng bất kỳ cách chọn đối tượng aj nào (i j ,i,j=1, ,n) thì sẽ có tất cả m1 m2 mn cách chọn đối tượng a1  a2   an Ví dụ 1: Chúng ta cần chọn một sinh viên CNTT năm thứ 1 hay năm thứ 2 đi dự một hội thảo. Hỏi có bao nhiêu cách chọn lựa một sinh viên như thế biết rằng có 100 sinh viên CNTT năm thứ 1 và 200 sinh viên CNTT năm thứ hai ? Giải : Ta có thể thực hiện một trong 2 việc chọn lựa khác nhau: chọn một sinh viên CNTT năm 1, hoặc chọn một sinh viên CNTT năm 2. Để thực hiện công việc thứ nhất ta có 100 cách, và để thực hiện công việc thứ 2 ta có 200 cách. Vậy để chọn một sinh viên tin theo yêu cầu ta có 100+200 = 300 cách. 36
40. Chúng ta có thể mở rộng nguyên lý cộng cho trường hợp nhiều sự chọn lựa hơn như sau: Giả sử ta phải thực hiện một công việc bằng cách chọn một trong m sự chọn lựa các biện pháp khác nhau T1, T2, , Tm. Để thực hiện Ti, 1 i m, ta có ni cách. Vậy ta có số cách thực hiện công việc trên là n1 + n2 + + nm. Nguyên lý cộng dạng tổng quát này có thể được chứng minh bằng qui nạp. Ví dụ 2: Trong một đợt phổ biến đề tài tốt nghiệp. Ban chủ nhiệm Khoa công bố 3 danh sách đề tài bao gồm 23 đề tài về chủ đề “Xây dựng hệ thông tin quản lý”, 15 đề tài về chủ đề “Xây dựng chương trình thi trắc nghiệm”, 10 đề tài về chủ đề “Trí tuệ nhân tạo”. Hỏi một sinh viên có bao nhiêu khả năng lựa chọn một đề tài trong 3 danh sách đề tài trên? Giải: Sinh viên có thể chọn một đề tài trong danh sách thứ thứ nhất theo 23 cách, trong danh sách thứ hai theo 15 cách, và trong danh sách thứ ba theo 19 cách. Do đó số cách chọn đề tài là 23+15+19 = 57. Ví dụ 3: Xác định giá trị của k sau khi đoạn chương trình sau đây được thực hiện xong k := 0 for i1 := 1 to n1 do k := k + 1; for i2 := 1 to n2 do k := k + 1; for im := 1 to nm do k := k + 1; Lời giải. Giá trị của k ban đầu là 0. Sau đó là m vòng lặp khác nhau. Mỗi thao tác lặp trong một vòng lặp là cộng thêm 1 vào k. Vòng lặp thứ i có ni thao tác, và tất cả m vòng lặp không thể thực hiện 2 vòng lặp nào một cách đồng thời. Do đó số thao tác để thực hiện xong đoạn chương trình trên là n1 + n2 + + nm. Đây cũng chính là giá trị cuối cùng của k. 2.4.3. Nguyên lý nhân Nếu có m1 cách chọn đối tượng a1, và sau đó với mỗi cách chọn a1 như thế có m2 cách chọn đối tượng a2 , sau đó với mỗi cách chọn a1 và a2 như thế có m3 cách chọn đối tượng a3, , cuối cùng, với mỗi cách chọn a1, a2, ,an-1 như vậy, có mn cách chọn đối tượng an thì sẽ có tất cả m1 m2 mn cách chọn đối tượng (a1,a2 , ,an ) Ví dụ 1. Trong một trung tâm máy tính có 32 chiếc máy vi tính. Mỗi máy có 24 cổng. Hỏi có bao nhiêu cổng khác nhau trong trung tâm này. Giải. Thủ tục chọn cổng gồm hai việc, việc chọn máy và sau đó chọn cổng của chiếc máy này. Vì có 32 cách chọn máy và 24 cách chọn cổng bất kể máy nào đã được chọn. Do đó theo qui tắc nhân có 32*24 =768 cổng Quy tắc nhân phát biểu dưới dạng ngôn ngữ tập hợp như sau: Nếu A1 , A2 , , Am là các tập hợp hữu hạn, khi đó số phần tử của tích Đề các của các tập này bằng tích của số các phần tử của mọi tập thành phần N( A1 A2 Am ) = N(A1) N(A2) N(Am) Ví dụ 2. Có nhiều nhất bao nhiêu biển đăng ký xe ôtô nếu mỗi biển chứa một dãy ba chữ cái tiếp sau là ba chữ số. Giải. Có tất cả 26 cách chọn cho mỗi một trong ba chữ cái và 10 cách chọn cho mỗi chữ số. Do đó đó có nhiều nhất là 26.26.26.10.10.10.= 17 576 000 biển đăng ký xe. Ví dụ 3. Giá trị của biến k bằng bao nhiêu sau khi chương trình sau được thực hiện? k:= 0; for i1 :=1 to n1 for i2:=1 to n2 for im :=1 to nm Do k:=k+1; 37
41. Giải. Đầu tiên giá trị của k được gán bằng 0. Có m vòng lặp for lồng nhau. Sau mỗi lần lặp của vòng for, giá trị của k tăng lên 1. Vòng for thứ nhất lặp n1 lần, vòng for thứ hai lặp n2 lần, vòng for thứ m lặp nm lần. Vậy , theo nguyên lý nhân, kết thuc m vòng lặp for lồng nhau, giá trị cuối cùng của k là k = n1 *n2 * nm 2.4.4. Nguyên lý lồng chim bồ câu (nguyên lý Dirichlet) Peter Gustav Lejeune Dirichlet là nhà toán học người Đức sống ở thế kỷ 19 (1805-1859), ông phát biểu một nguyên tắc về phân chia phần tử vào các lớp, nguyên tắc này được gọi là là nguyên lý Dirichlet. Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn sẽ có nhiều hơn một con chim. Đị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 vào trong k hộp, thì có ít nhất một hộp chứa hai hoặc nhiều hơn hai đồ vật. Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó tổng số vât được chứa trong các hộp nhiều nhất là bằng k. Điều này trái với giả thiết là có ít nhất k+1 vật. X XX X X Nguyên lý lồng chim bồ câu cũng thường được gọi là nguyên lý Dirichlet mang tên nhà toán học người Đức ở thế kỷ 19. Ví dụ 1. Trong bất kỳ một nhóm 367 người thể nào cũng có ít nhất hai người trùng ngày sinh ( vì một năm có nhiều nhất 366 ngày) Đị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 N / k vật Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn = 1 vật. Khi đó tổng số vật được chứa trong các hộp nhiều nhất là: k( -1) < k(((N/k)+1)-1) = N (*) trong đó ta đã dùng bất đẳng thức < (N/k) + 1. Bất đẳng thức (*) trái với giả thiết. Ví dụ 2: Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất phải có bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau? Giải: Theo nguyên lý Dirichlet, số học sinh cần tìm là 102, vì có 101 kết quả điểm thi khác nhau. Ví dụ 3: Trong bất kỳ một nhóm gồm 21 chữ số của hệ thập phân đều có ít nhất 3 chữ số trùng nhau. Thật vậy: Vì nếu chứa 21 vật vào 10 hộp thì ít nhất có một hộp chứa nhiều hơn 2 vật Ví dụ 4: Trong 48 sinh viên của lớp CĐ có ít nhất 48/12 =4 người cùng tháng sinh 38
42. Ví dụ 5: Trong một trường đại học có 38 ca học phân cho các lớp. Nếu có 677 lớp khác nhau thì cần phải có bao nhiêu phòng học? Giải: Theo nguyên lý Dirichlet sẽ có 677 /38 =18 phòng học 2.4.5. Nguyên lý bù trừ Một số bài toán đếm phức tạp hơn, được dựa vào nguyên lý tổng quát của nguyên lý cộng. Nếu không có giả thiết về sự rời nhau giữa hai tập A, B thì N(A B) = N(A) + N(B) – N(A B) Mở rộng: Cho A1 , A2 , , Am là các tập hữu hạn khi đó m-1 N(A1 A2  Am) = N1 – N2 + +(-1) Nm trong đó Nk là tổng của tất cả các phần tử của tất cả các giao của k tập lấy từ m tập đã cho Ví dụ 1 : N(A B C) = N1 – N2 + N3 Trong đó: N1 = N(A) + N(B) + N(C) N2 = N(A B) + N(A C) + N(B C) N3 = N(A B C ) Ví dụ 2: Trong một lớp cao đẳng có 30 sinh viên giỏi toán, 25 sinh viên giỏi Tin, 7 sinh viên giỏi cả toán và tin. Hỏi trong lớp có bao nhiêu sinh viên, nếu mỗi sinh viên hoặc giỏi toán hoặc giỏi tin hoặc giỏi cả hai môn? Giải: Gọi A là tập các sinh viên giỏi Toán, B là tập các sinh viên giỏi Tin, khi đó A B là tập các sinh viên giỏi cả Toán và Tin. Vì mỗi sinh viên trong lớp hoặc giỏi Toán hoặc giỏi Tin Hoặc giỏi cả hai môn nên số sinh viên trong lớp là N(A B) N(A B) = N(A) + N(B) – N(A B) = 30 + 25 – 7 = 48 Ví dụ 3: Có bao nhiêu xâu nhị phân độ dài là 8 hoặc là bắt đầu bởi 00 hoặc là kết thúc bởi 11? Giải: Dễ thấy số xâu nhị phân độ dài 8 bắt đầu bởi 00 là 26 = 64 và số xâu nhị phân độ dài 8 kết thúc bởi 11 là 26 = 64. Ngoài ra số xâu nhị phân độ dài 8 bắt đầu bởi 00 và kết thúc 4 bởi 11 là 2 = 16. Vậy số xâu nhị phân hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11 là: 64 + 64 – 16 = 112. Ví dụ 4: Biết rằng có 100 sinh viên học tiếng Anh, 70 học sinh học tiếng Nga, và 50 học sinh học tiếng Pháp, 40 học sinh học cả tiếng Anh và tiếng Nga, 20 học sinh học cả tiếng Anh và tiếng Pháp, 12 học sinh hoạc cả tiếng Pháp và tiếng Nga. Néu tất cả 500 sinh viên đều theo học ít nhất một ngoại ngữ, thì có bao nhiêu sinh viên học cả ba thứ tiếng? Giải: Gọi A là tập các sinh viên học tiếng Anh, B là tập các sinh viên học tiếng Nga, C là tập các sinh viên học tiếng Pháp. Khi đó số sinh viên theo học cả ba thứ tiếng sẽ là N(A BC) Theo nguyên lý bù trừ ta có N(A B C) = N(A) + N(B) + N(C) - N(A B) - N(A C) - N(B C) + N(A B C ) mà N(A) = 100 , N(B) = 70 , N(C) = 50 , N(A B) =40 , N(A C) =20 N(B C) = 12 , N(A B C) =500 Suy ra N(A B C )= 500 – 100 – 70 -50 +40 + 20 + 12 = 352 Lưu ý: Nếu ta đồng nhất tập Ak với tính chất Ak cho trên một tập X nào đó và đếm xem có bao nhiêu phần tử của X không thỏa mãn bất cứ một tính chất Ak nào cả? Ký hiệu N là số phần tử cần đếm, N là số phần tử của X, ta có: m N = N - N(A1 A2 Am) = N - N1 + N2 - +(-1) Nm ( nguyên lý bù trừ) Trong đó Nk là tổng các phần tử của X thoả mãn k tính chất lấy từ m tính chất đã cho 39
43. 2.5. Hoán vị & tổ hợp 2.5.1. Hoán vị Định nghĩa: Cho tập hợp A gồm n phần tử. Một cách sắp xếp n phần tử này thành một dãy (không kín gồm n phần tử đó) gọi là một hoán vị của tập hợp A. Kí hiệu: Pn là số các hoán vị của n phần tử. Công thức tính: Pn = n! (1) Chứng minh: (Bằng phương pháp qui nạp) 1. Với n=1, ta có A={a} thì có một cách sắp xếp các phần tử của A thành dãy. Mặt khác, ta có 1!=1 Vậy P1=1! Hay công thức (1) đúng với n=1 2. Giả sử công thức (1) đúng với n=k ≥1 số hoán vị của tập hợp A gồm k phần tử là Pk = k!, ta cần chứng minh (1) cũng đúng với n= k+1. Thực vậy, xét tập hợp A gồm k+1 phần tử, tức là A={a1, a2, ,ak, ak+1} Vì tập A có k+1 phần tử nên có k+1 cách chọn phần tử đầu tiên của dãy, ứng với mỗi cách chọn phần tử đầu tiên này còn lại k phần tử theo giả thiết qui nạp, có k! cách sắp xếp k phần tử này. Do đó có tất cả (k+1)*k!=(k+1)! Cách sắp xếp (k+1) phần tử của tập hợp A, điều này chứng tỏ (1) đúng với n=k+1. Vậy ta có Pn= n! Ví dụ 1: Một bàn có 4 học sinh. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho 4 học sinh đó. Giải: Mỗi phương án lựa chọn để xếp chỗ ngồi là hoán vị từ 4 học sinh. Vậy có 4!=16 cách. Ví dụ 2: Có một người bán hàng phải đi bán hàng tại 8 thành phố. Anh ta bắt đầu cuộc hành trình tại một thành phố nào đó, nhưng có thể đến bảy 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ố này theo bao nhiêu lộ trình khác nhau? Giải: Số lộ trình có thể giữa các thành phố bằng số hoán vị của bảy phần tử, vì thành phố đầu tiên đã được xác định, nhưng bảy thành phố còn lại có thể có thứ tự tuỳ ý. Do đó có 7! = 5040 cách để người bán hàng chọn hành trình của mình. Ví dụ 3: Cho tập A={1, 3, 5,7}. Có bao nhiêu số gồm 4 chữ số khác nhau được thành lập từ A. Giải: Số gồm 4 chữ số khác nhau được thành lập từ A chính là một hoán vị của A, do đó số các số theo yêu cầu là P4=4!=1.2.3.4=24 (số theo yêu cầu) 2.5.2. Chỉnh hợp không lặp Định nghĩa: Cho tập hợp A gồm n phần tử, giả sử k là một số tự nhiên thõa mãn: 1 k n. Mỗi cách sắp xếp k phần tử của tập hợp A thành một dãy hở gọi là mộ chỉnh hợp không lặp chập k của n phần tử. k Kí hiệu: An là số chỉnh hợp chập k của tập A gồm n phần tử. Định lý 1: Số chỉnh hợp chập k của tập có n phần tử là n! = n(n - 1)(n - 2) (n – k + 1) = (n k)! Chứng minh: Thật vậy: Phần tử đầu tiên của chỉnh hợp có thể chọn bằng n cách, vì tập có n phần tử Phần tử thứ hai của chỉnh hợp được chọn từ (n – 1 ) phần tử còn lại của tập, tức là có (n – 1) cách chọn phần tử này Tương tự ta có (n – 2) cách chọn phần tử thứ ba, và cứ như thế ta có (n –k +1) cách chọn phần tử thứ k. Việc lựa chọ các phần tử là phụ thuộc nhau nên theo quy tắc nhân ta được: 40
44. n! Ak = n*(n – 1)*(n – 2)* *(n – k + 1) = n (n k)! k Đặc biệt khi k = n thì ta có A n= n! Ví dụ 1: Có bao nhiêu cách chọn 3 lớp khác nhau trong 10 lớp để trao giải nhất, nhì, ba trong cuộc thi phòng chống ma tuý (Nếu lớp nào cũng có khả năng đoạt giải) Giải: Mỗi một cách chọn ra 3 lớp đó chính là chỉnh hợp chập 3 của 10 phần tử. 10! A3 = =10*9*8 = 720 (cách) 10 (10 3)! Ví dụ 2: Cho tập A= {0, 1, 2, 3, 4, 5}. Có bao nhiêu số chẵn, mỗi số gồm 5 chữ số khác nhau được thành lập từ A. Giải: Ta xét các khả năng có thể xảy ra cho dạng số cần tìm: 1. Dạng abcd 0 4 Chọn a, b, c, d {1, 2, 3, 4, 5} có m1=A 5=1.2.3.4.5=120 (số) 2. Dạng abcd 2 Chọn a {1, 3, 4, 5} có m1=4 (Cách) 3 Chọn b, c, d {0, 1, 3, 4, 5}\{a} có m2= A 4=4.3.2=24 (Cách) Với trường hợp này ta có tất cả m1x m2=4.24=96 (số) 3. Dạng abcd 4 Chọn a {1, 3, 2, 5} có m1=4 (Cách) 3 Chọn b, c, d {0, 1, 2, 3, 5}\{a} có m2= A 4=4.3.2=24 (Cách) Với trường hợp này ta có tất cả m1x m2=4.24=96 (số) Các cách chọn của 3 trường hợp trên có quan hệ độc lập, vậy số các số theo yêu cầu là 120+96+96=312 (số) 2.5.3. Chỉnh hợp lặp Định nghĩa :Chỉnh hợp lặp chập k của n phần tử là một cách sắp xếp có thứ tự k phần tử của n phần tử, mỗi phần tử có thể lấy lặp lại. k Ký hiệu : Số chỉnh hợp lặp chập k của n phần tử là An Định lý 1: Số các chỉnh hợp lặp chập k từ tập n phần tử bằng nk: = nk Chứng minh : Phần tử đầu tiên của chỉnh hợp lặp có thể chọn bằng n cách, vì tập có n phần tử Phần tử thứ hai của chỉnh hợp được chọn từ n phần tử của tập vì phần tử có thể được lấy lặp lại, tức là có n cách chọn phần tử này Tương tự ta có n cách chọn phần tử thứ ba, và cứ như thế ta có n cách chọn phần tử thứ k. Theo quy tắc nhân ta được: = nk Ví dụ 1: Tính số dãy nhị phân có độ dài là 8. Giải : Mỗi dãy nhị phân độ dài 8 là một bộ gồm 8 thành phần, trong đó mỗi thành phần 8 chỉ nhận một trong hai giá trị 1 hoặc 0. Từ đó suy ra số các dãy nhị phân có độ dài 8 là 2 = 256. n Như vậy số dãy nhị phân có độ dài n sẽ là 2 Ví dụ 2: Cho tập A= 1,2,3. Hãy đếm các số có 2 chữ số được xây dựng từ tập hợp A. Giải: Số lượng các số có 2 chữ số được xây dựng từ tập A chính là chỉnh hợp lặp chập 2 của tập gồm 3 phần tử và bằng 32=9 (1,2) , (2,1) , (1,3) , (3,1), (2,3), (3,2),(1,1), (2, 2), (3, 3) 2.5.4. Hoán vị có lặp 41
45. Định nghĩa: Cho s phần tử khác nhau a1, a2, , as Một chỉnh hợp có lặp chập m của s phần tử đã cho, trong đó có k1 phần tử a1, k2 phần tử a2 , , ks phần tử as được gọi là một hoán vị có lặp cấp m (m=k1 + k2 + + ks) và có kiểu (k1, k2, , ks) của s phần tử. Kí hiệu: Cm(k1, k2, , ks) là số các hoán vị có lặp cấp m kiểu (k1, k2, , ks) m! Khi đó ta có Cm(k1, k2, , ks) = k1 !k2! ks ! (phần chứng minh coi như bài tập dành cho các bạn sinh viên) Ví dụ: Có bao nhiêu cách phân chia 10 người thành 3 nhóm sao cho số người trong mỗi nhóm theo thứ tự là: 2, 3, 5. Mỗi cách phân nhóm chính là một hoán vị có lặp cấp 10 kiểu (2,3,5) do đó số cách 10! phân nhóm theo yêu cầu là: C10(2,3,5)= 2520 2!3!5! 2.5.5. Tổ hợp không lặp Định nghĩa: Cho tập A gồm n phần tử, k là một số tự nhiên thõa mãn 1 k n. Mỗi tập hợp con gồm k phần tử của tập hợp A được gọi là một tổ hợp chập k của tập hợp A gồm n phần tử. ( Ngoài ra có thể định nghĩa theo cách khác: Tỏ hợp chập k của n phần tử là cách chọn không phân biệt thứ tự k phần tử lấy từ tập n phần tử đã cho, mỗi phần tử không được lấy lặp lại. k Ký hiệu : Cn là Số tổ hợp chập k của n phần tử n! Định lý : C k = n, k nguyên dương , 0 k n n k!(n k)! k Chứng minh: Ta sẽ tính số tổ hợp thông qua việc thiết lập công thức liên hệ giữa C n và k A n. k Ta có tất cả C n cách chọn k phần tử, với mỗi cách chọn này lại có k! cách sắp k xếp chúng thành một dãy có thứ tự. Như vậy có tất cả C n .k! cách sắp xếp k phần tử của một tập hợp gồm n phần tử thành một dãy. k Theo cách tính số chỉnh hợp chập k của n phần tử thì số cách sắp xếp này là A n , k k n! do đó C n.k!= A n = (n k)! n! Suy ra : C k n k!(n k)! k n k Hệ quả: Cho n , k là các số nguyên không âm sao cho k n. Khi đó Cn Cn Nhận xét: 0 n Nếu k=0, k=n thì C n=1, C n=1 k k k-1 C n=C n-1 + C n-1 với 0 k n Ví dụ 1: Có bao nhiêu cách tuyển 5 trong số 10 cầu thủ cầu lông để đi thi đấu. Lời giải: Số cách tuyển chính là số tổ hợp chập 5 của 10 phần tử: 10! C 5 252 10 5!(10 5)! Ví dụ 2: Có bao nhiêu cách lập một đề thi gồm 3 câu hỏi từ một tập 15 câu hỏi 15! Giải: Đó chính là số tổ hợp chập 3 của 15 phần tử: C 3 15 3!12! 2.5.6. Tổ hợp có lặp 42
46. Định nghĩa: Cho tập hợp A gồm n phần tử khác nhau, A={a1, a2, , an}, m là một số tự nhiên bất kỳ. Một tổ hợp có lặp chập m của n phần tử đã cho là một tập hợp chứa m phần tử, trong đó mỗi phần tử là một trong n phần tử đã cho. Cách tính số tổ hợp có lặp m m Số các tổ hợp có lặp chập m của n phần tử, kí hiệu là Cn C n m 1 (phần chứng minh coi như bài tập dành cho các bạn sinh viên) Ví dụ 1: Cho A={a, b} với a b . Các tổ hợp chập 3 của A là: (a,a,a); (a,a,b); (a,b,b); (b,b,b) 3 3 3 4! Số các tổ hợp có lặp chập 3 của A gồm 2 phần tử là C 2 C 2 3 1 C 4 4 1!3! Ví dụ 2: Cho biết giá trị của k sau khi đoạn chưong trình sau được thực hiện k:=0; For i1 := 1 to n do For i2 := 1 to i1 do For im := 1 to im-1 do k:=k+1; Giải: Ta thấy giá trị khởi tạo của k=0 và 1 được cộng dồn vào k mỗi lần vòng lặp lồng nhau được duyệt qua ứng với tập các số nguyên i1 , i2 , , im , trong đó 1 im im-1 i1 n Số bộ các số nguyên như thế là số cách chọn có lặp m số nguyên từ tập 1, 2, , n Thật vậy mỗi lần một tập các số nguyên như thế được chọn , chúng ta sắp xếp chúng theo thứ tự không giảm. Khi đó sẽ xác định duy nhất một bộ im, im-1 , , i1 . Ngược lại mọi bộ như thế sẽ ứng với một tập không có thứ tự m phần tử hay một tổ m hợp lặp chập m từ n phần tử. Suy ra k = C n+m-1 2.5. 7 Hệ số nhị thức Định lý 1: Cho n, k là các số nguyên dương, với n k, khi đó: k k 1 k C n 1 C n C n (Hằng đẳng thức Pascal) Chứng minh: Giả sử T là một tập có n+1 phần tử, gọi a là một phần tử bất kỳ của T; S=T- k {a}. Khi đó C n+1 là số các tập con có k phần tử của tập T, hoặc là chứa phần tử a cùng k-1 với k-1 phần tử của S, hoặc là chứa k phần tử của S và không chứa a. Vì có C n tập con k chứa k-1 phần tử của S và C n tập con chứa k phần tử của tập S, do vậy . Khai triển ta có hằng đẳng thức Pascal hay tam giác Pascal: 0 C 0 0 1 C 1 C 1 0 1 2 C 2 C 2 C 2 0 1 2 3 C 3 C 3 C 3 C 3 0 1 2 3 4 C 4 C 4 C 4 C 4 C 4 0 1 2 3 4 5 C 5 C 5 C 5 C 5 C 5 C 5 1 43
47. 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 Hằng đẳng thức Pascal chỉ ra rằng khi cộng 2 hệ số nhị thức liền kề trong tam giác sẽ nhận được hệ số nhị thức của hàng tiếp theo ở giữa. n k n Định lý 2: Cho n là số nguyên dương, khi đó C n 2 k 0 Chứng minh: Một tập hợp n phần tử có tất cả 2n tập con khác nhau (1) Mặt khác ta thấy, mỗi tập con có hoặc không có phần tử nào hoặc 1 phần tử, 2 phần tử, , hoặc n phần tử. 0 Số tập con có 0 phần tử là C n 1 Số tập con có 1 phần tử là C n 2 Số tập con có 2 phần tử là C n n Số tập con có n phần tử là C n n k Do đó ta có tất cả C n tập con của tập n phần tử. Kết hợp với (1) ta có k 0 Định lý 3: Cho x, y là 2 biến và n là một số nguyên dương, khi đó: n n k n k k (x + y) = Cn x y (n 2) k 0 Chứng minh: Ta chứng minh định lý này bằng suy luận tổ hợp. Các số hạng trong khai triển của (x+y)n sẽ có dạng xn-kyk với k=0,1,2, ,n .Để nhận được số hạng dạng xn-kyk n-k ta chọn x từ n-k tổng (x+y) và có C n cách chọn như vậy, khi đó y được chọn từ k tổng n-k k n-k k còn lại. Do đó hệ số của x y là C n=C n n Hệ quả : Khi x = y = 1 ta có C(n,k)= 2n k 0 44
48. n Khi x =1, y = -1 ta có C(n,k)(-1)k = 0 k 0 Ví dụ 1: Tìm khai triển của biểu thức (x+y)4 4 0 4 1 3 2 2 2 3 3 4 4 (x y) C4 x C4 x y C4 x y C4 xy C4 y (x+y)4 = x4 + 4x3y + 6x2y2+ 4xy3 + y4 Ví dụ 2: Tính hệ số của x12y13 trong khai triển của (x +y)25 13 25! C 25 = = 5 200 300 13!12! 2.5.8. Các thuật toán liệt kê tổ hợp và hoán vị Thuật toán1 : Xuất ra màn hình tất cả các chỉnh hợp chập k của n số nguyên dương - Với mỗi vị trí của chỉnh hợp ta lần lượt chọn các giá trị từ 1 đến n (chưa được chọn) vào vị trí này và đánh dấu số đã chọn. - Tiếp tục tìm các số ở vị trí tiếp theo cho đến khi chọn đủ k số vào vị trí của chỉnh hợp và sau đó xuất kết quả ra màn hình. Program CHINH_HOP; uses crt; Const maxn=10; Var n,k:byte; A,B:Array[1 maxn] of byte; dem:integer; procedure Nhap; var i:integer; Begin clrscr; write('Nhap n:');readln(n); write('Nhap k:');readln(k); For i:=1 to n do A[i]:=0; B:=A; dem:=0; end; Procedure Ghinhan; var i:integer; begin inc(dem); write('Chinh hop thu ',dem,'.'); for i:=1 to k do write(A[i]:3); writeln; end; Procedure Try(i:integer); var j:integer; begin for j:=1 to n do if B[j]=0 then begin 45
49. B[j]:=i; A[i]:=j; if i=n then ghinhan else try(i+1); A[i]:=0; B[j]:=0; end; end; Begin Nhap; Try(1); readln; End. Thuật toán 2 : Xuất ra màn hình tất cả các tổ hợp chập k của n số nguyên dương {1,2, ,n} - Với mỗi vị trí của tổ hợp ta lần lượt chọn các giá trị từ 1 đến n (Chưa được chọn và có giá trị lớn hơn giá trị của phần tử trước đó, nếu có) vào vị trí này và đánh dấu số đã chọn. - Tiếp tục tìm các số ở vị trí tiếp theo cho đến khi chọn đủ k số vào vị trí của tổ hợp và sau đó xuất kết quả ra màn hình Program TO_HOP; uses crt; Const maxn=10; Var n,k:byte; A,B:Array[0 maxn] of byte; dem:integer; procedure Nhap; var i:integer; Begin clrscr; write('Nhap n:');readln(n); write('Nhap k:');readln(k); For i:=1 to n do A[i]:=0; B:=A; dem:=0; end; Procedure Ghinhan; var i:integer; begin inc(dem); write('To hop thu ',dem,'.'); for i:=1 to k do write(A[i]:3); writeln; end; Procedure Try(i:integer); var j:integer; begin for j:=A[i-1]+1 to n do if B[j]=0 then begin 46
50. B[j]:=i; A[i]:=j; if i=k then ghinhan else try(i+1); A[i]:=0; B[j]:=0; end; end; Begin Nhap; Try(1); readln; End. Thuật toán3 : Nhập vào một chuỗi ký tự S. Xuất ra màn hình tất cả các hoán vị khác nhau của các ký tự trong chuỗi S (Các ký tự trong S không nhất thiết khác nhau) - Tương tự giải thuật tìm hoán vị một tập hợp nhưng khác khi chọn một phần tử nào trong S vào một vị trí nào đó của hoán vị ta phải kiểm tra xem phần tử đó đã sử dụng hay chưa và đồng thời có phần tử nào trong S giống với phần tử đang xét và có vị trí xuất hiện trong S trước phần tử này mà chưa được sử dụng hay không. Program hoanvilap; uses crt; Var s:string; KT:Array[1 255] of Boolean; B:Array[1 255] of Char; n:byte; dem:longint; Function OK(k:byte):boolean; Var j:byte; Begin OK:=False; For j:=1 to k-1 do if (S[k] = S[j]) and (not KT[j]) then Exit; OK:=True; end; Procedure Ghinhan; Var i:Byte; Begin Inc(dem); write('Hoan vi thu ',dem,'.'); For i:=1 to n do write(B[i]); Writeln; end; Procedure Try(i:byte); Var j:byte; Begin For j:=1 to n do If (not (KT[j])) and (OK(j)) then begin 47
51. KT[j]:=True; B[i]:=S[j]; If i=n then Ghinhan else Try(i+1); KT[j]:=False; B[i]:=#0; end; end; BEGIN clrscr; Write('S=');readln(S); n:=Length(S); dem:=0; Fillchar(KT,Sizeof(KT),0); Fillchar(B,Sizeof(B),0); Try(1); readln; END. 48
52. CHƯƠNG 3 LÝ THUYẾT ĐỒ THỊ & CÂY Lý thuyết đồ thị là một ngành khoa học có lịch sử phát triển khá sớm nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ tên là Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng. Đồ thị cũng được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn dùng đồ thị để xác định xem có thực hiện một mạch điện trên một bảng điện phẳng được không. Chúng ta cũng có thể phân biệt hai hợp chất hóa học có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ đồ thị. Chúng ta cũng có thể xác định xem hai máy tính có được nối với nhau bằng một đường truyền thông hay không nếu dùng mô hình đồ thị mạng máy tính. Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông. Chúng ta cũng có thể dùng đồ thị để lập lịch thi và phân chia kênh cho các đài truyền hình. 3.1. Đồ thị và các khái niệm cơ bản trong đồ thị 3.1.1. Định nghĩa Đồ thị (Graph) là một cấu trúc rời rạc gồm 2 thành phần G = (V, E). Trong đó V (Vertex) là tập hữu hạn các đỉnh, E (Edge) là tập hữu hạn các cạnh. V , tập V ta có thể đánh số V v12, v , , vnhoặc Vn 1,2, , . Mỗi cạnh tương ứng với cặp hai đỉnh (,)vvijviết là e ( vij , v ) ( i , j 1 n ). Nếu cạnh có quy định chiều thì được gọi là cạnh có hướng (cung). Nếu cạnh không quy định chiều thì được gọi là cạnh vô hướng. Đồ thị G = (V,E) được gọi là đơn đồ thị nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cung. Đồ thị G = (V,E) được gọi là đa đồ thị nếu giữa hai đỉnh bất kỳ được nối với nhau bởi hai cung trở lên. Đồ thị G = (V,E) được gọi là có hướng nếu có chứa cạnh có hướng Đồ thị G = (V,E) được gọi là vô hướng nếu tất cả các cạnh đều là vô hướng Một đồ thị vô hướng luôn được coi là đồ thị có hướng bằng cách thay một cung bất kỳ bằng hai cung ngược chiều nhau. Giả đồ thị (Pseudo graph): Nếu tồn tại một cạnh nối một đỉnh với chính nó gọi là khuyên Ví dụ: Cần thơ (v7) TN (v1) HCM (v ) 4 Long an(v8) Hà nội (v2) Khánh hòa (v6) HP(v ) 3 Huế (v5) 3.1.2. Biểu diễn đồ thị 49
53. Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị a. Biểu diễn bằng ma trận kề (ma trận lân cận kề) Cho đồ thi G = (V, E) với V gồm n đỉnh (n >=1). Để biểu diễn G người ta dùng một ma trận vuông A[nxn] các phần tử là 0,1 được xác định theo quy tắc sau 1 (vij , v ) E Aij 0 (vij , v ) E Ví dụ: với đồ thị được biểu diễn v1 v2 v3 v4 Ma trận kề được biểu diễn như sau: v1 v2 v3 v4 v1 0 1 1 1 v2 1 0 1 0 v3 1 1 0 0 v4 1 0 0 0 Trường hợp là đa đồ thị có khuyên: Nếu có k cạnh nối vi với vj Ai,j= nếu vi có khuyên Ví dụ: v2 v1 v5 v4 v3 50
54. v1 v2 v3 v4 v5 v1 0 3 0 1 0 v 3 0 1 1 1 A = 2 v3 0 1 1 1 0 v4 1 1 1 0 0 v5 0 1 0 0 1 Chú ý: Ma trận kề của một đồ thị tuỳ thuộc vào thứ tự liệt kê các đỉnh. Do vậy có n! ma trận liền kề khác nhau của một đồ thị n đỉnh. Với đồ thị vô hướng thì các phần tử đối xứng qua đường chéo chính. Ma trận kề của đồ thị có hướng không phải là ma trận đối xứng Tổng tất cả các giá trị trên hàng i chính là số bậc ra của đỉnh đó, tổng tất cả các giá trị trên cột j chính là số bậc vào của đỉnh đó Trong thực tế mỗi một cung sẽ luôn xác định một giá trị nào đó, giá trị đó có thể là độ dài, có thể là tiền đi lại, chi phí, giá trị này gọi là trọng số Cij được hiểu như sau: 0 nếu vi  vj Trọng số thực nếu (vi, vj ) E Cij = nếu (vi, vj ) E Ví dụ: 1 1 2 3 7 3 5 8 4 5 4 Ma trận trọng số của đồ thị được biểu diễn như sau 0 1 3 1 0 7 Cij 3 7 0 5 8 5 0 4 8 4 0 Ưu nhược điểm của phương pháp mô tả bằng ma trận kề, ma trận trọng số: Ưu điểm: biết được hai đỉnh u, v có kề nhau không, biết được trọng số của hai đỉnh u và v bất kỳ. Nhược điểm: tốn bộ nhớ. Với đồ thị n đỉnh cần n2 ô nhớ, nếu số cạnh của đồ thị ít thì phương pháp này quá lãng phí bộ nhớ. b. Biểu diễn đồ thị bằng ma trận liên thuộc Cho đồ thị vô hướng G = (V,E), với tập đỉnh V = 1,2, ,n và tập cạnh E = e1,e2, ,en. Để biểu diễn G người ta dùng ma trận liên thuộc M[nxm]. Trong đó 51
55. 1 nếu cạnh ej nối với đỉnh vi M = ij 0 nếu cạnh ej không nối với đỉnh vi Ví dụ: e 1 7 2 e3 e e4 e5 1 e2 3 4 5 e6 Ma trận liên thuộc của đồ thị được biểu diễn như sau: e1 e 2 e 3 e 4 e 5 e 6 e 7 1 1 1 1 0 0 0 1 2 0 0 0 1 1 0 1 3 1 0 0 0 0 0 0 4 0 1 0 1 0 1 0 5 0 0 1 0 1 1 0 c. Biểu diễn đồ thị bằng danh sách cạnh (cung) Trong trường hợp đồ thị thưa (m <6*n), người ta thường dùng cách biểu diễn đồ thị theo danh sách cạnh. Trong cách biểu diễn này chúng ta lưu trữ danh sách tất cả các cạnh. Mỗi cạnh e =(x,y) của đồ thị sẽ tương ứng với 2 biến dau[e], cuoi[e] Ví dụ: v1 v2 v3 v4 Đầu Cuối v1 v2 v1 v4 v2 v4 v3 v1 v3 v2 v4 v3 d. Biểu diễn đồ thị bằng danh sách kề Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng danh sách kề là cách biểu diễn thích hợp nhất. Với mỗi đỉnh v của đồ thị chúng ta lưu giữ các đỉnh kề với nó, mà ta ký hiệu là ke(v) 52
56. Ví dụ v1 v 2 v3 v4 Biểu diễn đồ thị trên bằng danh sách kề như sau: 1 2 4 Nil 2 4 Nil 3 1 2 Nil 4 3 Nil Như vậy, mỗi đỉnh của đồ thị có một danh sách các đỉnh kề với nó. Cấu trúc được mô phỏng như sau: Type Pointer=^Member; Member=Record Number:1 n;{số hiệu đỉnh kề} Next:Pointer; End; Graph=array[1 n] of Pointer; Var G:graph; 3.2. Bậc, đường đi, chu trình và tính liên thông của đồ thị 3.2.1. Bậc của đỉnh Hai đỉnh u và v của đồ thị G được gọi là kề nhau nếu (u,v) là 1 cạnh của đồ thị G. Và đặt e=(u,v) thì e gọi là cạnh liên thuộc với hai đỉnh u và v. Nếu một cạnh e = (u,v) là một cung của đồ thị có hướng thì ta nói v là đỉnh kề của đỉnh u, u được gọi là đỉnh đầu, v là đỉnh cuối. Bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với đỉnh đó và ký hiệu là deg(v). Ví dụ: a b h e c d f g Ta có deg(a) = 3; deg(b) = 2; deg(c) = 2; deg(d) =5; deg(e) = 2; deg(f) = 3; deg(g) = 1; deg(h) = 0 Chú ý: Nếu đỉnh có khuyên thì mỗi khuyên được cộng thêm 2 đơn vị vào bậc của đỉnh đó 53