Bài tập cho tin học cơ sở 3 năm 2024

Nội dung Text: Bài giảng Cơ sở toán học cho tin học

1. 21/07/20 CHƯƠNG I. TỔNG QUAN VỀ THUẬT TOÁN VÀ PHƯƠNG PHÁP ĐẾM CƠ SỞ TOÁN HỌC CHO TIN HỌC BM Công nghệ thông tin Bài giảng Cơ sở toán học cho tin học Nền tảng cơ bản cho các ứng dụng tin học BỘ MÔN CÔNG NGHỆ THÔNG TIN NỘI DUNG NỘI DUNG CHƯƠNG 1 • Chương 1. Tổng quan về thuật toán và phương 1.1. Tổng quan về thuật toán 1.1.1. Khái niệm thuật toán pháp đếm 1.1.2. Độ phức tạp của thuật toán • Chương 2. Logic và ứng dụng 1.1.3. Một số thuật cơ bản • Chương 3. Đại số Boole 1.2. Các phương pháp đếm 1.2.1. Các quy tắc đếm cơ bản • Chương 4. Lý thuyết đồ thị 1.2.2. Hoán vị, chỉnh hợp và tổ hợp • Chương 5. Cây và ứng dụng của cây 1.2.3. Hệ thức truy hồi 1.2.4. Quan hệ chia để trị Bài tập Chương 1 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 2 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 5 TÀI LIỆU THAM KHẢO 1.1.1 KHÁI NIỆM THUẬT TOÁN • Đỗ Đức Giáo, Toán rời rạc ứng dụng trong tin học, NXB • Thuật toán là một bảng liệt kê các chỉ dẫn (hay Giáo dục, 2008 quy tắc) cần thực hiện theo từng bước xác định • Đỗ Đức Giáo, Hướng dẫn giải bài tập Toán rời rạc, NXB nhằm giải một bài toán đã cho. Giáo dục, 2006 • Có nhiều cách trình bày thuật toán: dùng ngôn • Kenneth H. Rosen, Discrete Mathematics and It’s ngữ tự nhiên, ngôn ngữ lưu đồ (sơ đồ khối), ngôn Applications, 7th Edition McGraw Hill, USA, 2019 ngữ lập trình • https://www.cis.upenn.edu/~jean/discmath-root-b.pdf • https://voer.edu.vn 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 3 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 6 1
2. 21/07/20 Các đặc trưng của thuật toán Thuật toán tìm kiếm nhị phân • Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ. • Thuật toán này có thể được dùng khi bảng liệt kê • Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các có các số hạng được sắp theo thứ tự tăng dần. giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán. • Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. Chẳng hạn, nếu các số hạng là các số thì chúng • Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. được sắp từ số nhỏ nhất đến số lớn nhất hoặc • Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi nếu chúng là các từ hay xâu ký tự thì chúng được đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn. • Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp sắp theo thứ tự từ điển. Thuật toán thứ hai này gọi các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ là thuật toán tìm kiếm nhị phân liệu khác nhau trong một miền xác định. 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 7 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 10 THUẬT TOÁN TÌM KIẾM Thuật toán tìm kiếm nhị phân procedure tìm kiếm nhị phân (x: integer, a1,a2,...,an: integers tăng dần) • Bài toán tìm kiếm: Xác định phần tử x trong một i := 1 {i là điểm mút trái của khoảng tìm kiếm} bảng liệt kê các phần tử phân biệt a1, a2, ..., an j := n {j là điểm mút phải của khoảng tìm kiếm} hoặc xác định rằng nó không có mặt trong bảng while i < j begin liệt kê đó. Lời giải của bài toán trên là vị trí của số m:= [(i+j)/2] hạng của bảng liệt kê có giá trị bằng x (tức là i sẽ if x>am then i:=m+1 else j := m là nghiệm nếu x=ai và là 0 nếu x không có mặt end trong bảng liệt kê). if x = ai then location := i else location := 0 {location là chỉ số dưới của số hạng bằng x hoặc 0 nếu không tìm thấy x} 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 8 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 11 Thuật toán tìm kiếm tuyến tính Thuật toán tìm kiếm nhị phân int LinearSearch(int x, int a[], int N) int BinarySearch (int x,int a[], int N) { { int i,j,mid; int i = 0; i := 0; //{i là điểm mút trái của khoảng tìm kiếm} j := N-1; // {j là điểm mút phải của khoảng tìm kiếm} while ((i < n) && (x != a[i])) while (i a[mid] i=m+1 //i
3. 21/07/20 1.1.2 ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 1.1.3 MỘT SỐ THUẬT TOÁN CƠ BẢN • Thước đo hiệu quả của một thuật toán là thời gian mà máy tính sử dụng để giải bài toán theo thuật toán đang xét, khi các giá trị • Đệ quy đầu vào có một kích thước xác định. • Tìm kiếm • Thước đo thứ hai là dung lượng bộ nhớ đòi hỏi để thực hiện thuật toán khi các giá trị đầu vào có kích thước xác định. • Sắp xếp • Các vấn đề như thế liên quan đến độ phức tạp tính toán của một thuật toán. • V.v... • Sự phân tích thời gian cần thiết để giải một bài toán có kích thước đặc biệt nào đó liên quan đến độ phức tạp thời gian của thuật toán. • Sự phân tích bộ nhớ cần thiết của máy tính liên quan đến độ phức tạp không gian của thuật toán. 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 13 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 16 Tính độ phức tạp của thuật toán THUẬT TOÁN ĐỆ QUY • Xét trò chơi với n đĩa ban đầu ở cọc A (cọc B và C trống). • Đôi khi chúng ta có thể quy việc giải bài toán với • Gọi Sn là số lần chuyển đĩa để chơi xong trò chơi với n đĩa. • Nếu n=1 thì rõ ràng là S1=1. tập các dữ liệu đầu vào xác định về việc giải cùng • Nếu n>1 thì trước hết ta chuyển n-1 đĩa bên trên sang cọc bài toán đó nhưng với các giá trị đầu vào nhỏ hơn B (giữ yên đĩa thứ n ở dưới cùng của cọc A). Số lần chuyển • Trong lập trình, trong 1 hàm lại gọi đến chính hàm n-1 đĩa là Sn-1. Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, ta chuyển n-1 đĩa từ cọc B sang cọc C đó (số lần chuyển là Sn-1). • Như vậy, số lần chuyển n đĩa từ A sang C là: • Sn=Sn-1+1+Sn=2Sn-1+1=2(2Sn-2+1)+1=22Sn-2+2+1=.....=2n- 1S +2n-2+...+2+1=2n1. 1 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 14 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 17 ĐỘ PHỨC TẠP CỦA THUẬT TOÁN VD THUẬT TOÁN ĐỆ QUY Độ phức tạp Thuật ngữ O(1) Độ phức tạp hằng số • Tìm kiếm nhị phân theo đệ quy O(logn) Độ phức tạp lôgarit • Giai thừa O(n) Độ phức tạp tuyến tính • v.v. O(nlogn) Độ phức tạp nlogn O(nb) Độ phức tạp đa thức O(bn) (b>1) Độ phức tạp hàm mũ O(n!) Độ phức tạp giai thừa 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 15 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 18 3
4. 21/07/20 THUẬT TOÁN SẮP XẾP CƠ SỞ CỦA PHÉP ĐẾM • Bài toán: Cho dãy số nguyên a1, a2, …aN. Cần sắp • Những nguyên lý đếm cơ bản xếp dãy đã cho theo thứ tự (tang hay giảm dần) – Những nguyên lý đếm cơ bản: • Các thuật toán SX – Nguyên lý bù trừ: – SX Chọn – SX Chèn – SX Nổi bọt – SX Quick – SX Heap – V.v 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 19 22 1.2. Các phương pháp đếm Quy tắc cộng • CƠ SỞ CỦA PHÉP ĐẾM • Giả sử có k công việc T1, T2, ..., Tk. Các việc này • NGUYÊN LÝ DIRICHLET có thể làm tương ứng bằng n1, n2, ..., nk cách và • CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG giả sử không có hai việc nào có thể làm đồng thời. • SINH CÁC HOÁN VỊ VÀ TỔ HỢP Khi đó số cách làm một trong k việc đó là n1+n2+ • HỆ THỨC TRUY HỒI ... + nk. • QUAN HỆ CHIA ĐỂ TRỊ • VD: Một sinh viên có thể chọn bài thực hành máy tính từ một trong ba danh sách tương ứng có 23, 15 và 19 bài. Vì vậy, theo quy tắc cộng có 23 + 15 + 19 = 57 cách chọn bài thực hành. 20 23 Bài toán đếm Quy tắc cộng • Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc • Giá trị của biến m bằng bao nhiêu sau khi đoạn chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp chương trình sau được thực hiện? • Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo m := 0 yêu cầu của bài toán cần nghiên cứu for i1 := 1 to n1 • Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp được m := m+1; nghiên cứu từ thế kỷ 17, khi những câu hỏi về tổ hợp được nêu ra trong những công trình nghiên cứu các trò chơi may rủi for i2 :=1 to n2 • Liệt kê, đếm các đối tượng có những tính chất nào đó là một m := m+1; phần quan trọng của lý thuyết tổ hợp ....................... • Cần phải đếm các đối tượng để giải nhiều bài toán khác nhau for ik := 1 to nk m := m+1; 21 24 4
5. 21/07/20 Quy tắc cộng Quy tắc nhân – VD1 • Giá trị khởi tạo của m bằng 0. Khối lệnh này gồm k • Người ta có thể ghi nhãn cho những chiếc ghế trong vòng lặp khác nhau. Sau mỗi bước lặp của từng một giảng đường bằng một chữ cái và một số nguyên dương không vượt quá 100. Bằng cách như vậy, vòng lặp giá trị của k được tăng lên một đơn vị. nhiều nhất có bao nhiêu chiếc ghế có thể được ghi Gọi Ti là việc thi hành vòng lặp thứ i. Có thể làm Ti nhãn khác nhau? bằng ni cách vì vòng lặp thứ i có ni bước lặp. Do • Thủ tục ghi nhãn cho một chiếc ghế gồm hai việc, gán các vòng lặp không thể thực hiện đồng thời nên một trong 26 chữ cái và sau đó gán một trong 100 số theo quy tắc cộng, giá trị cuối cùng của m bằng số nguyên dương. Quy tắc nhân chỉ ra rằng có cách thực hiện một trong số các nhiệm vụ Ti, tức 26.100=2600 cách khác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán nhãn cho là m = n1+n2+ ... + nk. 2600 chiếc ghế. 25 28 Quy tắc cộng Quy tắc nhân – VD2 • Quy tắc cộng có thể phát biểu dưới dạng của ngôn • Có bao nhiêu xâu nhị phân có độ dài n. ngữ tập hợp như sau: Nếu A1, A2, ..., Ak là các tập hợp đôi một rời nhau, khi đó số phần tử của hợp các • Mỗi một trong n bit của xâu nhị phân có thể chọn tập hợp này bằng tổng số các phần tử của các tập bằng hai cách vì mỗi bit hoặc bằng 0 hoặc bằng 1. thành phần. Giả sử Ti là việc chọn một phần tử từ tập Ai với i=1,2, ..., k. Có |Ai| cách làm Ti và không có Bởi vậy theo quy tắc nhân có tổng cộng 2n xâu nhị hai việc nào có thể được làm cùng một lúc. phân khác nhau có độ dài bằng n. • Số cách chọn một phần tử của hợp các tập hợp này, một mặt bằng số phần tử của nó, mặt khác theo quy tắc cộng nó bằng |A1|+|A2|+ ... +|Ak|. Do đó ta có: • |A1  A2 ... Ak| = |A1| + |A2| + ... + |Ak|. 26 29 Quy tắc nhân Nguyên lý bù trừ • Giả sử một nhiệm vụ nào đó được tách ra thành k • Khi hai công việc có thể được làm đồng thời, ta việc T1, T2, ..., Tk. Nếu việc Ti có thể làm bằng ni không thể dùng quy tắc cộng để tính số cách thực cách sau khi các việc T1, T2, ... Ti-1 đã được làm, hiện nhiệm vụ gồm cả hai việc. Để tính đúng số khi đó có n1.n2....nk cách thi hành nhiệm vụ đã cho cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1, A2 là hai tập hữu hạn, khi đó • |A1  A2| = |A1| + |A2|  |A1  A2|. 27 30 5
6. 21/07/20 Nguyên lý bù trừ NGUYÊN LÝ DIRICHLET Từ đó với ba tập hợp hữu hạn A1, A2, A3, ta có: • Giả sử có một đàn chim bồ câu bay vào chuồng. |A1  A2  A3| = |A1| + |A2| + |A3|  |A1  A2|  |A2  A3|  Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất |A3  A1| - |A1  A2  A3|, trong một ngăn có nhiều hơn một con chim. và bằng quy nạp, với k tập hữu hạn A1, A2, ..., Ak ta có: Nguyên lý này dĩ nhiên là có thể áp dụng cho các | A1  A2  ...  Ak| = N1  N2 + N3  ... + (1)k-1Nk, đối tượng không phải là chim bồ câu và chuồng trong đó Nm (1  m  k) là tổng phần tử của tất cả các giao chim. m tập lấy từ k tập đã cho, nghĩa là • Mệnh đề (Nguyên lý): Nếu có k+1 (hoặc nhiều Nm =  | Ai1  Ai2  ...  Aim | hơn) đồ vật được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật. 1i1 i2 ...im  k 31 34 Nguyên lý bù trừ NGUYÊN LÝ DIRICHLET - VD • Bây giờ ta đồng nhất tập Am (1
7. 21/07/20 Hoán vị Chỉnh hợp lặp • Định nghĩa. Ta gọi hoán vị từ n phần tử của X là bộ có thứ tự gồm n • Định nghĩa. Ta gọi chỉnh hợp lặp chập m từ n phần tử của X là bộ có thành phần, mỗi thành phần đều là phần tử của X, các thành phần thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X. khác nhau từng đôi. • Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là 𝐴 • Ký hiệu số lượng hoán vị từ n phần tử là Pn. • Theo định nghĩa, một chỉnh hợp lặp chập m từ n phần tử của X có thể • Theo định nghĩa, một hoán vị từ n phần tử của X có thể biểu diễn bởi biểu diễn bởi (a1, a2, ..., an), ai  X, i = 1, 2, ..., n, ai aj, i j. (a1, a2, ..., am), ai  X, i = 1, 2, ..., m. • Định lý 1. • Dễ thấy tập tất cả các chỉnh hợp lặp chập m từ n phần tử của X chính Pn  n  (n  1)  ... 2 1  n! là Xm. Vì vậy, theo nguyên lý nhân ta có: 𝐴 = nm Hoán vị Chỉnh hợp lặp Ví dụ 1. 6 người đứng xếp thành một hàng ngang để chụp ảnh. Hỏi có thể bố trí bao nhiêu kiểu? Ví dụ 1. Tính số dãy nhị phân độ dài n. Giải: Mỗi kiểu ảnh là một hoán vị của 6 người. Từ đó nhận được số kiểu ảnh có thể bố • Giải: Mỗi dãy nhị phân độ dài n là một bộ gồm n thành phần, trí là 6! = 720. trong đó mỗi thành phần chỉ nhận một trong hai giá trị (1 hoặc 0). Ví dụ 2. Cần bố trí việc thực hiện n chương trình trên một máy vi tính. Hỏi có bao Từ đó suy ra số các dãy nhị phân độ dài n là 2n. nhiêu cách? xx…x Giải: đánh số các chương trình bởi 1, 2,..., n. Mỗi cách bố trí việc thực hiện các 0,1 chương trình trên máy có thể biểu diễn bởi 1 hoán vị của 1, 2, Do mỗi tập con của tập n phần tử tương ứng với một vectơ đặc …, n. Từ đó suy ra số cách bố trí cần tìm là n! trưng là một xâu nhị phân độ dài n, nên ta có Ví dụ 3. Có bao nhiêu cách bố trí n thợ thực hiện n việc sao cho mỗi thợ thực hiện một việc và mỗi việc do đúng một thợ thực hiện Hệ quả: Số lượng tập con của tập n phần tử là 2n. Giải: n! Chỉnh hợp lặp Chỉnh hợp lặp Định nghĩa. Ta gọi chỉnh hợp lặp chập m từ n phần tử của X là bộ có thứ Ví dụ 2. Cần phải phân bố 100 sinh viên vào 4 nhóm thực tập ACCESS, tự gồm m thành phần, mỗi thành phần đều là phần tử của X. FOXPRO, EXCEL, LOTUS. Mỗi sinh viên phải tham gia vào đúng một • Ví dụ: X = {a, b, c}, khi đó chỉnh hợp lặp chập 2 từ 3 phần tử của X là: nhóm và mỗi nhóm có thể nhận một số lượng không hạn chế sinh viên 1. (a, b) • Giải: 4 100 hay 100 4 ? 2. (a, c) • Mỗi cách phân bố cần tìm có thể biểu diễn bởi bộ có thứ tự gồm 100 3. (b, a) thành phần (b1, ..., b100) trong đó bi  {ACESS, FOXPRO, EXCEL, 4. (b, c) LOTUS} là nhóm thực tập của sinh viên thứ i. Từ đó suy ra số cách 5. (c, a) phân bố cần đếm là 4100. 6. (c, b) 7. (a, a) 8. (b, b) 9. (c, c) 7
8. 21/07/20 Chỉnh hợp không lặp Tổ hợp • Định nghĩa. Ta gọi chỉnh hợp không lặp chập m từ n phần tử của X là • Định nghĩa. Ta gọi tổ hợp chập m từ n phần tử của X là bộ không có bộ có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các các thành phần khác nhau từng đôi. thành phần khác nhau từng đôi. • Ký hiệu số lượng chỉnh hợp không lặp chập m từ n phần tử là 𝑃 . Rõ • Ví dụ: X = {a, b, c}, khi đó tổ hợp chập 2 từ 3 phần tử của X là: ràng, để tồn tại chỉnh hợp không lặp, thì m  n. 1. {a,b} Ví dụ: X = {a, b, c}, khi đó chỉnh hợp không lặp chập 2 từ 3 phần tử của 2. {a, c} X là: 3. {b, c} 1. (a, b) 2. (a, c) 3. (b, a) 4. (b, c) 5. (c, a) 6. (c, b) Chỉnh hợp không lặp Tổ hợp • Định nghĩa. Ta gọi chỉnh hợp không lặp chập m từ n phần tử của X là • Định nghĩa. Ta gọi tổ hợp chập m từ n phần tử của X là bộ không có bộ có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các các thành phần khác nhau từng đôi. thành phần khác nhau từng đôi. • Ký hiệu số lượng chỉnh hợp không lặp chập m từ n phần tử là 𝑃 . Rõ • Ký hiệu số lượng tổ hợp chập m từ n phần tử là 𝐶 (đôi khi ta sẽ sử ràng, để tồn tại chỉnh hợp không lặp, thì m  n. dụng ký hiệu C(n,m)) • Theo định nghĩa, một chỉnh hợp không lặp chập m từ n phần tử của X • Theo định nghĩa, một tổ hợp chập m từ n phần tử của X có thể biểu có thể biểu diễn bởi diễn bởi bộ không có thứ tự (a1, a2, ..., am), ai  X, i = 1, 2, ..., m, ai aj, i j. {a1, a2, ..., am}, ai  X, i = 1, 2, ..., m, ai aj, i j. • Việc đếm số lượng chỉnh hợp không lặp chập m từ n phần tử có thể • Với giả thiết X={1, 2,...,n}, một tổ hợp chập m từ n phần tử của X có thực hiện theo nguyên lý nhân. Ta có thể biểu diễn bởi bộ có thứ tự • Định lý 2. (a1, a2, ..., am), ai  X, i = 1, 2, ..., m, 1  a1 < a2 < ...
9. 21/07/20 Tổ hợp HỆ THỨC TRUY HỒI • Việc đếm các tổ hợp có khó khăn hơn so với việc đếm các cấu hình đã trình bày, tuy nhiên cách đếm dưới đây cho biết cách vận dụng các nguyên lý với các kết quả đếm • Gọi Pn là tổng số tiền có trong tài khoản sau n đã biết trong việc đếm 1 cấu hình mới. năm. Vì số tiền có trong tài khoản sau n năm bằng • Xét tập hợp tất cả các chỉnh hợp không lặp chập m của n phần tử. Chia chúng thành số có sau n  1 năm cộng lãi suất của năm thứ n, những lớp sao cho hai chỉnh hợp thuộc cùng một lớp chỉ khác nhau về thứ tự. Rõ nên ta thấy dãy {Pn} thoả mãn hệ thức truy hồi ràng các lớp này là 1 phân hoạch trên tập đang xét và mỗi lớp như thế là tương ứng với 1 tổ hợp chập m của n. Số chỉnh hợp trong mỗi lớp là bằng nhau và bằng m! (Số sau: hoán vị). Số các lớp là bằng số tổ hợp chập m của n. Theo nguyên lý cộng, tích của • Pn = Pn-1 + 0,11Pn-1 = (1,11)Pn-1 m! với số này là bằng số các chỉnh hợp không lặp chập m của n, nghĩa là bằng n(n- 1)...(n-m+1). Từ đó nhận được số tổ hợp chập m của n là: • với điều kiện đầu P0 = 10.000 đô la. Từ đó suy ra • Pn = (1,11)n * 10.000. Thay n = 30 cho ta P30 = n(n  1)(n  2)...(n  m  1) n! 228922,97 đô la. hay m! m!(n  m)! 52 Tổ hợp QUAN HỆ CHIA ĐỂ TRỊ Ví dụ 1. Có n đội bóng thi đấu vòng tròn. Hỏi phải tổ chức bao nhiêu • Nhiều thuật toán đệ quy chia bài toán với các thông tin trận đấu? vào đã cho thành một hay nhiều bài toán nhỏ hơn. Giải: Cứ 2 đội thì có 1 trận. Từ đó suy ra số trận đấu sẽ bằng số cách • Sự phân chia này được áp dụng liên tiếp cho tới khi có chọn 2 đội từ n đội, nghĩa là bằng thể tìm được lời giải của bài toán nhỏ một cách dễ C(n,2) = n(n-1)/2 dàng. Ví dụ 2: Một câu lạc bộ có 25 thành viên. • Chẳng hạn, ta tiến hành việc tìm kiếm nhị phân bằng a. Có bao nhiêu cách chọn ra 4 thành viên của câu lạc bộ để lập ra làm cách rút gọn việc tìm kiếm một phần tử trong một danh thành ban chấp hành câu lạc bộ? sách tới việc tìm phần tử đó trong một danh sách có độ dài giảm đi một nửa. Ta rút gọn liên tiếp như vậy Chọn 4 thành viên này không quan tâm thứ tự tổ hợp: cho tới khi còn lại một phần tử. b. Có bao nhiêu cách chọn ra 1 chủ tịch, 1 phó chủ tịch, 1 thư kí và 1 thủ quĩ? • Đệ quy gắn liền với quan hệ chia để trị Chọn 4 thành viên quân tâm đến thứ tự chỉnh hợp không lặp: 53 HỆ THỨC TRUY HỒI Xây dựng công thức đệ qui • Định nghĩa 1: Hệ thức truy hồi (hay công thức truy • Ví dụ. (Bài toán tháp Hà nội). Trò chơi tháp Hà nội hồi) đối với dãy số {an} là công thức biểu diễn an qua được trình bày như sau: “Có 3 cọc a, b, c. Trên một hay nhiều số hạng đi trước của dãy. Dãy số được cọc a có một chồng gồm n cái đĩa đường kính gọi là lời giải hay nghiệm của hệ thức truy hồi nếu các giảm dần từ dưới lên trên. Cần phải chuyển chồng số hạng của nó thỏa mãn hệ thức truy hồi này. đĩa từ cọc a sang cọc c tuân thủ qui tắc: • Ví dụ (Lãi kép): Giả sử một người gửi 10.000 đô la • mỗi lần chỉ chuyển 1 đĩa vào tài khoản của mình tại một ngân hàng với lãi suất • chỉ được xếp đĩa có đường kính nhỏ hơn lên trên kép 11% mỗi năm. Sau 30 năm anh ta có bao nhiêu đĩa có đường kính lớn hơn. Trong quá trình chuyển tiền trong tài khoản của mình? được phép dùng cọc b làm cọc trung gian”. 51 9
10. 21/07/20 CÂU HỎI VÀ BÀI TẬP CHƯƠNG 1 Nội dung 1. Trình các khái niệm: Thuật toán, độ phức tạp thuật toán? 2.1.Logic mệnh đề 2. Trình bày về các phép đếm: Khái niệm, cho VD minh họa? 2.1.1. Các phép toán và công thức Bài 1. Đếm số n gồm 2 chữ số, nếu: a. n chẵn 2.1.2. Điều kiện đồng nhất b. n lẻ gồm 2 chữ số khác nhau 2.1.3. Các quy tắc suy diễn trong logic mệnh đề c. n chẵn gồm 2 chữ số khác nhau Bài 2: Cho các chữ số {0, 1, 2, 3, 4, 5} 2.2. Logic vị từ a) Có bao nhiêu số có 3 chữ số khác nhau 2.2.1. Một số khái niệm b) Có bao nhiêu số chẵn có 3 chữ số khác nhau 2.2.2. Dạng chuẩn tắc hội và dạng chuẩn tắc tuyển 2.2.3. Nguyên lý quy nạp 2.2.4. Quy tắc suy diễn trong logic vị từ cấp 1 55 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 58 CÂU HỎI VÀ BÀI TẬP CHƯƠNG 1 2.1. Logic mệnh đề Bài 3. Một đội bóng đá có 20 cầu thủ. Cần chọn 11 • Định nghĩa: Mệnh đề là một khẳng định có giá trị chân cầu thủ, phân vào 11 vị trí trên sân để thi đấu chính lý xác định, đúng hoặc sai. thức. Hỏi có mấy cách chọn nếu: Câu hỏi, câu cảm thán, mệnh lệnh… không là mệnh đề. a) Ai cũng có thể chơi ở bất kỳ vị trí nào? • Ví dụ: b) Chỉ 1 cầu thủ được chỉ định làm thủ môn, các cầu – mặt trời quay quanh trái đất thủ khác chơi mọi vị trí còn lại – 1+1 = 2 c) Có 3 cầu thủ có thể làm thủ môn được, các cầu thủ – Hôm nay trời đẹp quá ! (ko là mệnh đề) khác chơi mọi vị trí – Học bài đi ! (ko là mệnh đề) – 3 là số chẵn phải không? (ko là mệnh đề) 56 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 59 2.1.Logic mệnh đề • Ký hiệu: người ta dùng các ký hiệu P, Q, R… để chỉ Chương 2. LOGIC VÀ ỨNG mệnh đề. DỤNG • Chân trị của mệnh đề: – Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng ta nói P có BM Công nghệ thông tin chân trị đúng, ngược lại ta nói P có chân trị sai. Bài giảng Cơ sở toán học cho tin học – Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1 (hay Đ,T) và 0 (hay S,F) 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 60 10
11. 21/07/20 2.1.Logic mệnh đề Các phép toán logic trên các mệnh đề • Kiểm tra các khẳng định sau có phải là mệnh đề b. Phép hội: của hai mệnh đề P, Q được kí hiệu không? bởi PQ (đọc là “P và Q”), là mệnh đề được định – Paris là thành phố của Mỹ. bởi : P  Q đúng  P và Q đồng thời đúng. – n là số tự nhiên. Bảng chân trị : P Q PQ – 3 là số nguyên tố. T T T – Cơ sở toán học cho tin học là môn bắt buộc của T F F Ví dụ: ngành HTTT. F T F – 3>4 và Trần Hưng Đạo là vị tướng – Bạn có khỏe không? – 2 là số nguyên tố và là số chẵn F F F – x2 +1 luôn dương. – An đang hát và uống nước 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 61 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 64 2.1.Logic mệnh đề Các phép toán logic trên các mệnh đề 2. Phân loại: Ví dụ: c. Phép tuyển: của hai mệnh đề P, Q được kí hiệu a. Mệnh đề phức hợp: là mệnh – 2 không là số nguyên tố bởi PQ (đọc là “P hay Q”), là mệnh đề được định đề được xây dựng từ các mệnh – 2 là số nguyên tố (sơ cấp) đề khác nhờ liên kết bằng các – Nếu 3>4 thì trời mưa bởi : PQ sai  P và Q đồng thời sai. liên từ (và, hay, khi và chỉ – An đang xem phim hay An Bảng chân trị : P Q PQ khi,…) hoặc trạng từ “không”. đang học bài T T T b. Mệnh đề sơ cấp (nguyên – Hôm nay trời đẹp và Ví dụ: T F T thủy): Là mệnh đề không thể 1+1=3 – 3>4 hay 3>5 F T T xây dựng từ các mệnh đề khác – 2 là số nguyên tố hay là số chẵn F F F thông qua liên từ hoặc trạng từ – “An đang giúp mẹ lau nhà hay rửa chén” “không”. – “Ba đang đọc báo hay xem phim” 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 62 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 65 Các phép toán logic trên các mệnh đề Các phép toán logic trên các mệnh đề a. Phép phủ định: phủ định của mệnh đề P được ký hiệu d. Phép kéo theo: của hai mệnh đề P, Q được kí hiệu là ¬P hay P đọc là “không” P hay “phủ định của” P) bởi P  Q (đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”) Bảng chân trị : là mệnh đề được định bởi: P  Q sai  P đúng và Q sai – T: True  1 Bảng chân trị : P Q PQ – F: False  0 Ví dụ: F T T Ví dụ: – Nếu 1 = 2 thì Lenin là người Việt Nam F F T – 2 là số nguyên tố. Phủ định: 2 không là số nguyên tố – Nếu trái đất quay quanh mặt trời thì 1+3=5 T T T – Nếu 2+1 = 0 thì tôi là chủ tịch nước T F F – 1 >2. Phủ định : 1≤ 2 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 63 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 66 11
12. 21/07/20 Các phép toán logic trên các mệnh đề Dạng mệnh đề e. Mệnh đề tương đương (phép kéo theo 2 chiều): Mệnh đề • Bảng chân trị của dạng mệnh đề E(p,q,r): là P tương đương Q được kí hiệu bởi P  Q (đọc là “P nếu và chỉ nếu Q” hay “P khi và chỉ khi Q” hay “P là điều kiện cần và đủ của bảng ghi tất cả các trường hợp chân trị có thể xảy Q”) là mệnh đề được định bởi: P  Q đúng  P và Q có cùng ra đối với dạng mệnh đề E theo chân trị của các trân trị. biến mệnh đề p, q, r. Bảng chân trị : P Q PQ • Nếu có n biến, bảng này sẽ có 2n dòng, chưa kể Ví dụ: T T T – 2=4 khi và chỉ khi 2+1=0 T F F dòng tiêu đề F T F – 6 chia hết cho 3 khi và chi khi 6 chia hết cho 2 F F T – London là thành phố nước Anh nếu và chỉ nếu TP. HCM là thủ đô của VN • Ví dụ: – 3>4 là điều kiện cần và đủ của 5 >6 – E(p,q,r) =(p  q)  r . Ta có bảng chân trị sau 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 67 Các phép toán logic trên các mệnh đề Dạng mệnh đề f. Phép loại trừ (XOR): của hai mệnh đề P, Q được kí • Mệnh đề E(p,q,r) = (p  q)  r theo 3 biến p,q,r hiệu bởi P  Q (đọc là “Loại trừ P hoặc loại trừ Q” hay có bảng chân trị sau: “Hoặc là P đúng hoặc là Q đúng nhưng không đồng thời p q r pq (pq)r cả 2 là đúng” là mệnh đề được định bởi: P  Q sai  P 0 0 0 0 1 và Q cùng trân trị 0 0 1 0 1 Bảng chân trị : P Q PQ 0 1 0 1 0 T T F T F T 0 1 1 1 1 F T T 1 0 0 1 0 Ví dụ: F F F 1 0 1 1 1 – I will earn an A in this subject or I will drop this subject 1 1 0 1 0 1 1 1 1 1 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 68 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 71 Dạng mệnh đề Dạng mệnh đề • Định nghĩa: là một biểu thức được cấu tạo từ: • Dạng mệnh đề được coi là hằng đúng (hay chân – Các mệnh đề (các hằng mệnh đề) lý) nếu nó luôn lấy giá trị 1 (T) – Các biến mệnh đề p, q, r, …, tức là các biến lấy giá trị là các • Dạng mệnh đề được coi là hằng sai (hay mâu mệnh đề nào đó thuẫn) nếu nó luôn lấy giá trị 0 (F) – Các phép toán , , , , ,  và dấu đóng mở ngoặc (). • Ví dụ: • Ví dụ: – B(p,q) = p  (p  q) – E(p,q) = p ∧ q – C(p,q) = p  pq – F(p,q,r) = (p  q)  q ∧ r 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 69 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 72 12
13. 21/07/20 Các luật logic III. Qui tắc suy diễn 1. Luật phủ định của phủ định 4. Luật kết hợp • Trong các chứng minh toán • Ta thường mô hình hóa (P  Q)  R ⇔ P  (Q  R) học, xuất phát từ một số PP khẳng định đúng p, q, phép suy luận đó dưới 2. Luật De Morgan (P  Q)  R  P  (Q  R) r…(tiền đề), ta áp dụng các dạng: P∧QPQ 5. Luật phân phối qui tắc suy diễn để suy ra chân lí của một mệnh đề h p PQPQ P  (Q  R) ⇔ (P  Q)  (P  R) mà ta gọi là kết luận. q 3. Luật giao hoán P  (Q  R) ⇔ (P  Q)  (P  R) • Nói cách khác, dùng các r PQQP 6. Luật lũy đẳng qui tắc suy diễn để chứng … P P⇔P minh: (p  q  r  … ) có hệ ℎ PQQP quả logic là h Augustus De Morgan P P⇔P (1806-1871) 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 73 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 76 Các luật logic Các qui tắc suy diễn 7. Luật trung hòa 10. Luật hấp thụ 1. Qui tắc khẳng định (Modus Ponens) P 1⇔ P P  (P  Q) ⇔ P • Qui tắc này được thể hiện bằng hằng đúng: P 0⇔ P P  (P  Q) ⇔ P 8. Luật về phần tử bù 11. Luật về phép kéo theo: [(p  q)  𝑝 ]  𝑞 P P⇔ 0 PQPQQP P P⇔ 1 Ví dụ: Nếu trời mưa thì đường trơn  Nếu đường không trơn thì trời không • Hoặc dưới dạng sơ đồ pq 9. Luật thống trị mưa 𝑝 P 0⇔0 𝑞 P 1⇔1 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 74 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 77 Áp dụng trong lập trình Các qui tắc suy diễn • Giả sử trong chương • Giả sử trong chương trình có câu lệnh sau : Nếu An học chăm thì An học • Hình vuông là hình bình trình có câu lệnh sau : while( (i10) OR (i= 10))) • Trước hết chúng ta sẽ áp dụng công thức De Morgan để biến đổi biểu thức sau cùng như sau : Mà An học chăm • Mà hình bình hành có hai • Ta có thể viết lại câu đường chéo cắt nhau tại lệnh này một cách đơn while( (i10) OR (i= 10) while( (i10 OR A[i]= 10) đường chéo cắt nhau tại ) Chiều nay đường ướt. trung điểm mỗi đường. 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 75 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 78 13
14. 21/07/20 Các qui tắc suy diễn Các qui tắc suy diễn 2. Quy tắc phủ định • Nếu trời mưa thì đường ướt. • Nếu đường ướt thì đường trơn • Qui tắc này được thể hiện bằng hằng đúng: Nếu trời mưa thì đường trơn. [(p  q)  𝑞 ]  𝑝̅ • Một con ngựa rẻ là một con ngựa hiếm (*) • Hoặc dưới dạng sơ đồ pq • Cái gì hiếm thì đắt 𝑞 Một con ngựa rẻ thì đắt ( do khẳng định (*)) 𝑝̅ 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 79 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 82 Các qui tắc suy diễn Các qui tắc suy diễn • Nếu An chăm học thì An đậu Cơ sở toán học cho tin học. 4. Qui tắc tam đoạn luận rời • An không đậu Cơ sở toán học cho tin học. Qui tắc này được thể hiện bằng hằng đúng: An không chăm học [(p  q)  𝑞 ]  p Hoặc dưới dạng sơ đồ pq 𝑞 p Ý nghĩa của qui tắc: nếu một trong hai trường hợp có thể xảy ra, chúng ta biết có một trường hợp không xảy ra thì chắc chắn trường hợp còn lại sẽ xảy ra. 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 80 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 83 Các qui tắc suy diễn Các qui tắc suy diễn 3. Qui tắc tam đoạn luận • Chủ nhật, An thường lên thư viện hoặc về quê Qui tắc này được thể hiện bằng hằng đúng: • Chủ nhật này, An không về quê Chủ nhật này, An lên thư viện [(p  q)  (q  r)]  (p  r) Hoặc dưới dạng sơ đồ pq qr p  r 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 81 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 84 14
15. 21/07/20 Các qui tắc suy diễn Các qui tắc suy diễn 5. Qui tắc nối liền • Qui tắc này được thể hiện bằng hằng đúng: Qui tắc này được thể hiện bằng hằng đúng: (p  q)  (p  q) [(𝑝  𝑝  …  𝑝 ) h]  [(𝑝  𝑝  …  𝑝  ℎ)  0] p Hoặc dưới dạng sơ đồ 𝑝 q • Dạng sơ đồ 𝑝 pq 𝑝 𝑝 Ví dụ: … …  Hôm nay An học bài. 𝑝 Hôm nay An phụ mẹ nấu ăn. 𝑝 Suy ra: Hôm nay An học bài và phụ mẹ nấu ăn h ℎ 0 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 85 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 88 Các qui tắc suy diễn Các qui tắc suy diễn 6. Qui tắc đơn giản 8. Qui tắc chứng minh theo trường hợp Qui tắc này được thể hiện bằng hằng đúng: (p  q)  p Dựa trên hằng đúng: pq [(p  r)  (q  r)]  [(p ∨ q)  r)] Hoặc dưới dạng sơ đồ p Ý nghĩa: nếu p suy ra r và q suy ra r thì p hay q cũng có thể Ví dụ: suy ra r. Hôm nay An học Cơ sở toán và học Anh văn Suy ra: Hôm nay An học Cơ sở toán 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 86 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 89 Các qui tắc suy diễn Các qui tắc suy diễn 7. Qui tắc mâu thuẫn (chứng minh bằng phản chứng) 9. Phản ví dụ Ta có tương đương logic Để chứng minh một phép suy luận là sai hay [(𝑝  𝑝  …  𝑝 ) h]  [(𝑝  𝑝  …  𝑝  ℎ)  0] Để chứng minh vế trái là một hằng đúng ta chứng minh 𝑝 𝑝 …𝑝 q nếu thêm phủ định của h vào các tiền đề thì được một mâu thuẫn. không là một hằng đúng. Ta chỉ cần chỉ ra một phản ví dụ. Ví dụ. Cho a, b, c là 3 đường thẳng phân biệt và a//c và b//c chứng minh a//b. 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 87 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 90 15
16. 21/07/20 Dạng chuẩn tắc của logic mệnh đề 2.2. Logic vị từ • Đi ểm yếu của logic m ệnh đề (1) Công thức Dạng chuẩn tắc Dạng chuẩn tắc nguyên tử hội tuyển – Không thể hiện được các phát biểu có các biến • Còn gọi là cơ sở hay nguyên thủy là các • DCTH Là hội của các • DCTT Là tuyển của các HSC Ví dụ: x = y + 3; x > 3 TSC biến mệnh đề A hoặc • A • A ¬A • A ∧B • A ∨B • Bởi vì các biến chưa có giá trị. Tuy nhiên, phát biểu dạng như • Tuyển sơ cấp (TSC) là • ¬A ∧ (B ∨ C) • (A ∧ B) ∨ C tuyển của các biến • (A ∨ B) ∧ (¬B ∨ C ∨ • (A ∧ ¬B ∧ ¬C) ∨ trên xuất hiện rất nhiều mệnh đề D) ∧ (D ∨ ¬E) (¬D ∧ E ∧ F ) • Hội sơ cấp (HSC) là hội của các biến mệnh đề 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 91 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 94 Phương pháp kiểm tra tính hằng đúng, hằng sai Logic vị từ Lập bảng gồm 2n hàng cho n biến và công thức A • Điểm yếu của logic mệnh đề (2) Lập bảng - Cột cuối chứa toàn số 1 thì A(…) hằng đúng - Cột cuối chứa toàn số 0 thì A)…) hằng sai – Những sự tương đương sau không biểu diễn - Cột cuối chứa cả số 0 và 1 thì A(…) thực hiện được được bằng logic mệnh đề Kiểm tra Biến đổi B1: Khử phép kéo theo B2: Đưa phép toán phủ định về trực tiếp tới từng biến – "Không phải tất cả bánh đều ăn được" và "Chỉ công thức A tương mệnh đề một số bánh ăn được" đương B3: Sử dụng luật phân bố đưa về DCTH, DCTT B4: Kết luận – "Not all integers are even" và "Some integers are not even" Áp dụng các quy tắc suy diễn Suy diễn – Để suy diễn, mỗi mệnh đề phải được liệt kê riêng lẽ 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 92 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 95 Ví dụ kiểm tra tính hằng đúng, hằng sai Logic vị từ • Khắc phục các điểm yếu nêu trên Kiểm tra công thức: A→(B→A) • Phát biểu x > 3 có 2 phần: • Bằng phương pháp Lập • Bằng phương pháp biến – B iến x – Tính chất của biến x (> 3), được gọi là vị từ (predicate) bảng đổi tương đương A B B→A A→(B→A) • Nói cách khác A →(B → A) ≡ A ∨ (B ∨ A) – P redic a te là v ị từ mô tả tí nh c hấ t của nhữ n g đố i tư ợ ng, 0 0 1 1 ho ặc qua n hệ giữ a c húng 0 1 0 1 ≡ ( A ∨ A) ∨ B • Ký hiệu phát biểu P(x) ⇒ P(2), P(4) là mệnh đề 1 0 1 1 ≡1 1 1 1 1 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 93 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 96 16
17. 21/07/20 Logic vị từ Logic vị từ 2. Các phép toán trên vị từ • ∀: được gọi là lượng từ phổ dụng Cho trước các vị từ p(x), q(x) theo một biến x ∈ A. Khi ấy, • ∃ : được gọi là lượng từ tồn tại ta cũng có các phép toán tương ứng như trên mệnh đề: • Ví dụ. Các mệnh đề sau đúng hay sai – Phủ định p(x) – “∀x∈R, x2 + 3x + 1 ≤ 0” (S) – Phép nối liền p(x) ∧ q(x) – “∃x∈R, x2 + 3x + 1 ≤ 0” (Đ) – Phép nối rời p(x) ∨ q(x) – “∀x∈R, x2 + 1 ≥ 2x” (Đ) – Phép kéo theo p(x) → q(x) – “∃x∈R, x2 + 1 < 0” (S) – Phép kéo theo hai chiều p(x) ↔ q(x) 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 97 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 100 Logic vị từ Logic vị từ • Khi xét một mệnh đề p(x) với x∈A. Ta có các trường • Định nghĩa. Cho p(x,y) là một vị từ theo hai biến x, y hợp sau xác định trên AxB. Ta định nghĩa các mệnh đề lượng từ – TH1. Khi thay x bởi 1 phần tử a tùy ý ∈A, ta có p(a) đúng. – TH2. Với một số giá trị a∈A, ta có p(a) đúng. hóa của p(x,y) như sau: – TH3. Khi thay x bởi 1 phần tử a tùy ý ∈A, ta có p(a) sai. “∀x ∈ A, ∀y ∈ B, p(x,y)” = “∀x ∈ A, (∀y ∈ B, p(x,y))” • Ví dụ. Cho vị từ p(x) với x∈R “∀x ∈ A, ∃y ∈ B, p(x,y)” = “∀x ∈ A, (∃y ∈ B, p(x,y))” – p(x) = “x2 +1>0” – p(x) = “x2 -2x+1 = 0” “∃x ∈ A, ∀y ∈ B, p(x,y)” = “∃x ∈ A, (∀y ∈ B, p(x,y))” – p(x) = “2x2 -2x+5 = 0” “∃x ∈ A, ∃y ∈ B, p(x,y)” = “∃x ∈ A, (∃y ∈ B, p(x,y))” 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 98 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 101 Logic vị từ Câu hỏi và Bài tập chương 2 Định nghĩa. Cho p(x) là một vị từ theo một biến xác định trên 1. Trình bày các phép toán, đk đồng nhất, các quy tắc suy diễn A. Ta định nghĩa các mệnh đề lượng từ hóa của p(x) như sau: trong logic mệnh đề? – Mệnh đề “Với mọi x thuộc A, p(x)”, kí hiệu bởi 2. Khái niệm logic vị từ, Dạng CTH và dạng CTT của logic vị từ? “∀x∈A, p(x)”, là mệnh đề đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a∈A. 3. Kiểm tra các suy luận sau – Mệnh đề “Tồn tại (ít nhất) hay có (ít nhất) một x thuộc A, p(x)” a) b) c) kí hiệu bởi p  (q r) p q p “∃x∈A, p(x)”, p∨s 𝑟∨s pr là mệnh đề đúng khi và chỉ khi có ít nhất một giá trị x = 𝑎 nào đó tq p∨r p  (q ∨ 𝑟) sao cho mệnh đề p(𝑎 ) đúng. 𝑠 𝑞  𝑠 𝑞∨𝑠 𝑟𝑡 s 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 99 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 102 17
18. 21/07/20 3.1. Khái niệm và hàm Boole Chương 3: Đại số Boole 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 106 Nội dung HÀM BOOLE 3.1. Khái niệm và hàm Boole 3.1.1. Khái niệm 3.1.2. Các phép toán 3.1.3. Hàm Boole 3.1.4. Biểu diễn hàm Boole 3.2. Mạch Logic 3.2.1. Các cổng logic 3.2.2. Các mạch logic 3.2.3. Cực tiểu hóa các mạch logic 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 104 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 107 3.1. Khái niệm và hàm Boole 3.2. Mạch Logic Định nghĩa: Tập hợp khác rỗng S cùng với các phép toán ký hiệu nhân (.), cộng (+), lấy bù (’) được gọi là một đại số Boole nếu các tiên đề sau đây được thoả mãn với mọi a, b, c 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 105 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 108 18
19. 21/07/20 3.2. Mạch Logic 3.2. Mạch Logic 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 109 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 112 3.2. Mạch Logic Bài tập chương 3 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 110 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 113 3.2. Mạch Logic Chương 4: Lý thuyết đồ thị 21/07/20 Bộ môn CNTT - Bài giảng Cơ sở toán học cho tin học 111 19
20. 21/07/20 NỘI DUNG Đồ thị có hướng, vô hướng 4.1. Khái niệm và biểu diễn đồ thị • Một đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E 4.2. Chu trình Euler và Chu trình Hamilton mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. 4.3. Một số bài toán trên đồ thị • Một đa đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. • Đồ thị vô hướng nhận được từ đồ thị có hướng G bằng cách xoá bỏ các chiều mũi tên trên các cung được gọi là đồ thị vô hướng nền của G. 115 118 4.1. Khái niệm và biểu diễn đồ thị Ví dụ 2: • Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. • Phân loại đồ thị tùy theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị. • Chúng ta cũng có thể dùng đồ thị để giải các bài toán như bài toán tính số các tổ hợp khác nhau của các chuyến bay giữa hai thành phố trong một mạng hàng không, hay để giải bài toán đi tham quan tất cả các đường phố của một thành phố sao cho mỗi đường phố đi qua đúng một lần, hoặc bài toán tìm số các màu cần thiết để tô các vùng khác nhau của một bản đồ 116 119 Ví dụ 1: Bậc của đỉnh • Định nghĩa: Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi là liền kề nếu (u,v)E. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. • Định nghĩa: Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. • Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0 117 120 20