Bài giảng Nhập môn toán cao cấp

Nội dung text: Bài giảng Nhập môn toán cao cấp

1. TRƯỜNG ĐẠI HỌC ĐỒNG THÁP KHOA TOÁN NGUYỄN DƯƠNG HOÀNG BÀI GIẢNG NHẬP MÔN TOÁN CAO CẤP ĐỒNG THÁP -2011
2. Mục lục I LÍ THUYẾT TẬP HỢP 3 §1 KHÁI NIỆM VỀ TẬP HỢP . . . . . . . . . . . . . . . . . .3 1.1 Tập hợp- Phần tử- Biểu diễn tập hợp . . . . . . . . .3 1.2 Quan hệ bao hàm- Tập con . . . . . . . . . . . . . .4 1.3 Các phép toán về tập hợp . . . . . . . . . . . . . . .5 §2 QUAN HỆ . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 2.1 Tích Đề các . . . . . . . . . . . . . . . . . . . . . . .8 2.2 Quan hệ 2 ngôi . . . . . . . . . . . . . . . . . . . . .8 2.3 Quan hệ tương đương . . . . . . . . . . . . . . . . . .9 2.4 Quan hệ thứ tự . . . . . . . . . . . . . . . . . . . . . 10 §3 ÁNH XẠ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . . 11 §4 GIẢI TÍCH TỔ HỢP . . . . . . . . . . . . . . . . . . . . . . 12 4.1 Quy tắc cộng và quy tắc nhân . . . . . . . . . . . . . 12 4.2 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Chỉnh hợp lặp . . . . . . . . . . . . . . . . . . . . . . 13 4.4 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.6 Nhị thức Niu-tơn . . . . . . . . . . . . . . . . . . . . 14 II LOGIC 18 §1 LOGIC MỆNH ĐỀ . . . . . . . . . . . . . . . . . . . . . . . 18 1.1 Mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2 Các phép toán về mệnh đề, các kí hiệu quan hệ . . . 19 1.3 Lượng từ . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4 Công thức . . . . . . . . . . . . . . . . . . . . . . . . 21 1.5 Các công thức tương đương . . . . . . . . . . . . . . 21 1
3. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 1.6 Các công thức tương đương logic cơ bản . . . . . . . 22 1.7 Các công thức tương đương khác . . . . . . . . . . . 23 1.8 Luật logic . . . . . . . . . . . . . . . . . . . . . . . . 23 1.9 Hệ quả logic . . . . . . . . . . . . . . . . . . . . . . . 24 1.10 Các bài toán giải bằng công cụ logic mệnh đề . . . . 24 1.11 Ứng dụng của logic mệnh đề trong các hệ thống tìm tin tự động hóa . . . . . . . . . . . . . . . . . . . . . 27 §2 VỊTỪ 29 2.1 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Hàm mệnh đề một biến . . . . . . . . . . . . . . . . 33 2.4 Hàm mệnh đề hai biến . . . . . . . . . . . . . . . . . 33 §3 CÁC PHÉP TOÁN LOGIC TRÊN CÁC HÀM MỆNH ĐỀ . 34 3.1 Phép phủ định . . . . . . . . . . . . . . . . . . . . . 34 3.2 Phép tuyển . . . . . . . . . . . . . . . . . . . . . . . 34 3.3 Phép hội . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Phép kéo theo . . . . . . . . . . . . . . . . . . . . . . 35 3.5 Phép tương đương . . . . . . . . . . . . . . . . . . . 35 §4 ĐẠI SỐ BOOLE . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1 Sơ lược về đại số Boole . . . . . . . . . . . . . . . . . 35 4.2 Hệ đếm nhị phân . . . . . . . . . . . . . . . . . . . . 37 DANH MỤC TÀI LIỆU THAM KHẢO 47 2
4. Chương I LÍ THUYẾT TẬP HỢP Mục tiêu chương: Về Kiến thức: Sinh viên cần nằm vững những kiến thức cơ bản về tập hợp, quan hệ, ánh xạ, giải tích tổ hợp. Xác định được mối liên hệ giữa những nội dung kiến thức này. Về kĩ năng: Giải được các bài tập liên quan của các chủ đề kiến thức của chương, bước đầu biết vận dụng trong đời sống thực tế. Về thái độ : Nghiêm túc, có tinh thần hợp tác trong học tập §1 KHÁI NIỆM VỀ TẬP HỢP 1.1 Tập hợp- Phần tử- Biểu diễn tập hợp 1.1.1. Khái niệm về tập hợp và phần tử Tất cả những đối tượng xác định nào đó hợp lại tạo thành một tập hợp, mỗi đối tượng là một phần tử của tập hợp Ví dụ 1 : Tập hợp những người Việt Nam trên thế giới tạo thành tập hợp người Việt Nam. Mỗi người Việt Nam là một phần tử của tập hợp đó. Ví dụ 2 : Tập hợp tất cả các điểm trong không gian tạo thành tập hợp các điểm trong không gian. Mỗi điểm là một phần tử của tập hợp đó. 1.1.2. Khái niệm thuộc và kí hiệu ∈ Nếu a là phần tử của tập hợp E ta nói " a thuộc E" và viết a ∈ E Nếu a không là phần tử của tập hợp E ta nói " a không thuộc E" và viết a∈E Ví dụ 3 : 4 ∈ N; 3∈ tập số chẵn. 1.1.3. Cách mô tả tập hợp 3
5. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 1. Liệt kê ra tất cả các phần tử của tập hợp Ví dụ 4 : A = {x, y, z, t} 2. Nêu ra các tính chất đặc trưng của các phần tử tạo thành tập hợp. Nếu tập hợp E gồm các phần tử x có tính chất P ta viết: E = {x|xcó tính chất P} Ví dụ 5 : P = {các số chẵn} Tập các số chẵn có thể mô tả như sau: P = {m|m = 2k, k ∈ Z} 1.1.4. Một số tập hợp số thường gặp Tập hợp số tự nhiên N = {0, 1, 2, 3, ···} Tập hợp N∗ = {1, 2, 3, ···} = N\{0} Tập hợp các số nguyên Z = {· · · , −3, −2, −1, 0, 1, 2, 3, ···} p Tập hợp các số hữu tỉ = { |q 6= 0, p ∈ , q ∈ } Q q Z Z Tập hợp các số thực: R = {các số thực} 1.1.5. Tập rỗng Định nghĩa 1 : Tập rỗng là tập hợp không có phần tử nào Kí hiệu là ∅ Ví dụ: {x ∈ R|x2 + 1 = 0} = ∅ Định nghĩa 2 : Ta nói tập hợp A bằng tập hợp B nếu A và B trùng nhau, nghĩa là mọi phần tử của A cũng là phần tử của B và ngược lại 1.2 Quan hệ bao hàm- Tập con Định nghĩa 3 : Nếu mọi phần tử của A cũng là phần tử của B, thì ta nói: • A bao hàm trong B • B bao hàm A • A là tập con của B ta viết A ⊂ B hay B ⊃ A ∅ là tập con của mọi tập hợp 4
6. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 1.3 Các phép toán về tập hợp 1.3.1. Phép hợp Định nghĩa 4 : Hợp của 2 tập hợp A và B là tập hợp tạo thành bởi tất cả các phần tử thuộc A hoặc thuộc B. Kí hiệu A ∪ B 1.3.2. Phép Giao Định nghĩa 5 : Phép giao của hai tập hợp A và B là tập hợp tạo bởi tất cả các phần tử vừa thuộc A vừa thuộc B. Kí hiệu A ∩ B Định nghĩa 6 : A ∩ B = ∅ ta nói A và B rời nhau. 1.3.3. Tính chất • A ∪ B = B ∪ A • A ∩ B = B ∩ A • A ∪ A = A • A ∩ A = A • (A ∪ B) ∪ C = A ∪ (B ∪ C) • (A ∩ B) ∩ C = A ∩ (B ∩ C) • (A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) • (A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 1.3.4. Hiệu của hai tập hợp Định nghĩa 7 : Hiệu của hai tập hợp A và B là tập tạo bởi tất cả các phần tử thuộc A mà không thuộc B. Kí hiệu: A\B = {x ∈ A ∧ x∈B} 1.3.5. Tập bù Định nghĩa 8 : Xét tập E và A là tập con của E, nghĩa là A ⊂ E. Lúc đó E\A gọi là tập bù của A trong E. 1.3.6. Định luật De Morgan 5
7. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Với mọi A ⊂ E, B ⊂ E ta có A ∪ B = A ∩ B, A ∩ B = A ∪ B 1.3.7. Hiệu đối xứng Cho hai tập A và 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 thuộc đồng thời cả A và B, kí hiệu là A 4 B. Ta có A 4 B = (A \ B) ∪ (B \ A). CHÚ Ý: Người ta thường minh họa mỗi tâp bởi một đường cong kín, mỗi phần tử của nó được biểu diễn bởi một dấu gạch chéo hoặc dấu chấm, gọi là mô tả theo " lược đồ Venn’. Chẳng hạn Tập A có các phần Tử là a,b,c được minh họa như sau. VD: a/Cho A = {0, 1, 2, 4, 5},B = {0, 3, 5, 6} A ∪ B = {0, 1, 2, 4, 5, 6} A \ B = {1, 2, 4} B \ A = {3, 6} A 4 B = {1, 2, 3, 4, 6} Các tập này có thể xác định theo lươc đồ Venn như trong hình dưới. b/Cho A = {x ∈ N|xcó chữ số tận cùng bên phải là 0}. 6
8. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng B = {x ∈ N|xcó chữa số tận cùng bên phải là 5}. Khi đó . . . A ∪ B = {x ∈ N|x.5}. c/ Cho A = {x ∈ N|x.2}vàB = {x ∈ N|x.3}. Khi đó . . . A ∩ B = {x ∈ N|x.2vàx.3} = {x ∈ N|x.6}. 1.3.8. Mở rộng các phép toán tập hợp • 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 Cho tập X và các tập A1,A2, ··· ,An. Mở rộng tính chất (iii) của định lí 1 ta có: n n [ [ X ∩ ( Ai) = (X ∩ Ai) i=1 i=1 n n \ \ X ∪ ( Ai) = (X ∪ Ai) i=1 i=1 Mở rộng tính chất (iv) ta có: n n [ \ X \ ( Ai) = (X \ Ai) i=1 i=1 n n \ [ X \ ( Ai) = (X \ Ai) i=1 i=1 1.3.9. Tập hợp các tập con của một tập hợp Cho X là một tập. Nếu coi mỗi tập con của X là một phần tử thì ta có tập ℘(X) có các phần tử là các tập con của X. Như vậy: ℘(X) = {A|A ⊂ X} Ví dụ: a) X = Ø thì ℘(Ø) = {Ø}; ℘({Ø}) = {Ø0{Ø}} b) X = {a, b} thì ℘(X) = {Ø}; {a}; {b}, {X} 7
9. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng §2 QUAN HỆ 2.1 Tích Đề các 2.1.1. Tích hai tập hợp Định nghĩa 9 : Tích Đề các của hai tập hợp A và B là tập hợp tất cả các cặp (a,b), a trước b sau, được tạo nên do lấy a ∈ A, b ∈ B một cách bất kì. Kí hiệu A × B 2.1.2. Tích ba tập hợp A1 × A2 × A3 2.1.3. Tích n tập hợp Kí hiệu A1 × A2 × · · · An 2.2 Quan hệ 2 ngôi 2.2.1. Định nghĩa và ví dụ Ta gọi một quan hệ m- ngôi trên tập X là một tập con S của lũy thừa m Đề-các X . Nếu S là quan hệ m-ngôi trên X thì khi (a1, a2, ··· , am) ∈ S ta nói a1, a2, ··· , am có S-quan hệ với nhau. Quan hệ 2- ngôi được gọi vắn tắt là quan hệ. Như vậy quan hệ 2-ngôi S trên X là một tập con S ⊂ X2 Ví dụ: a) X là tập các công dân nước Việt Nam. S là tập tất cả các bộ ba (x,y,z) trong đó x là chồng của y, z là con của x và y. Khi đó S ⊂ X3 là một quan hệ 3 ngôi trên X. b) X là tập sinh viên của một lớp, S là tập các cặp (x,y) trong đó x, y cùng tuổi, S ⊂ X2 là quan hệ trên X. 2.2.2. Tính chất của quan hệ 2-ngôi Cho quan hệ S trên X. Nếu (x, y) ∈ S thì ta nói x có S quan hệ với y và viết x S y. 1) Quan hệ S gọi là có tính phản xạ nếu với mọi x ∈ X ta có xSx. 2) Quan hệ S gọi là có tính đối xứng nếu với mọi x, y ∈ X, xSy thì ySx. 8
10. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 3) Quan hệ S gọi là có tính chất phản đối xứng hay phản xứng nếu với mọi x, y ∈ X, xSy và ySx thì x=y. 4) Quan hệ S gọi là có tính bắc cầu nếu với mọi x, y ∈ X, xSy và ySz thì xSz. Ví dụ: a) Trong một lớp học, quan hệ xSy nếu x, y cùng tuổi có tính chất phản xạ, đối xứng, bắc cầu. b) Trong tập số tự nhiên N, quan hệ xSy nếu x ≤ y có các tính chất phản xạ, phản xứng, bắc cầu. c) Trong tập các tam giác, quan hệ "đồng dạng" có các tính chất phản xạ, đối xứng,bắc cầu. 2.3 Quan hệ tương đương 2.3.1. Định nghĩa Một quan hệ S trên tập X gọi là quan hệ tương đương nếu S có tính chất phản xạ, đối xứng, bắc cầu. Kí hiệu xSy là x ∼ y (đọc x tương đương y) 2.3.2. Lớp tương đương Cho tập X và quan hệ ∼ là quan hệ tương đương trên X. Với mọi x ∈ X, tập [x] = {y ∈ X|y ∼ x} gọi là lớp tương đương chứa x. Định lý 1: Các lớp tương đương khác rỗng, 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ì x ∼ x nên x ∈ [x], tức là [x] 6= φ. Để chứng minh phần còn lại ta giả sử hai lớp [x] và [y] có [x] ∩ [y] 6= φ, ta cần chứng minh [x]=[y]. Chọn z ∈ [x] ∩ [y]. Bởi z ∈ [x] nên x ∼ z, z ∈ [y] nên z ∼ y. Từ đó t ∈ [x] ⇔ t ∼ x ⇔ t ∼ z ⇔ t ∼ y ⇔ t ∈ [y] Vậy [x] = [y] Chú ý: Từ định lí 1 suy ra rằng y ∈ [x] khi và chỉ khi [x] = [y] và x ∼ y khi và chỉ khi [x] = [y]. Các lớp tương đương chia X thành các tập con rời nhau (một cách chia như vậy gọi là một phân hoạch trên tập X). Tập hợp mà mỗi phần tử là 9
11. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng một lớp tương đương của tập X theo quan hệ tương đương ∼ gọi là tập thương của X theo quan hệ ∼, kí hiệu là X\∼ Vậy X\∼ = {[x]|x ∈ X} Ví dụ: a) X là tập hợp các sinh viên trong lớp học, x ∼ y nếu x và y ngồi cùng bàn. Dễ kiểm tra ∼ là một quan hệ tương đương trên X. Các lớp tương đương theo quan hệ ∼ là những sinh viên ngồi cùng bàn. Tập X\∼ có phần tử là tập các sinh viên ngồi cùng bàn. . b) Trên tập Z các số nguyên xét quan hệ a ∼ b nếu a − b.3, kiểm tra ∼là quan hệ tương đương trên Z. Xét các lớp tương đương theo quan hệ này. . Ta có a ∼ b ⇔ a − b.3 ⇔ a và b chia cho 3 có cùng số dư. Khi chia cho 3 số dư có thể là 0;1;2, do vậy ta có các lớp tương đương là: 0 = {3k|k ∈ Z}, các số chia hết cho 3. 1 = {3k + 1|k ∈ Z}, các số chia cho 3 dư 1. 2 = {3k + 2|k ∈ Z}, các số chia cho 3 dư 2. Vậy Z\∼ = {0, 1, 2} có 3 phần tử. 2.4 Quan hệ thứ tự 2.4.1. Định nghĩa Một quan hệ S trên tập X gọi là quan hệ thứ tự nếu S có các tính chất phản xạ, phản xứng, bắc cầu. Nếu S là quan hệ thứ tự thì thay cho cách viết xSy ta viết x ≤ y Tập X cùng quan hệ thứ tự ≤ trên nó gọi là tập được sắp thứ tự, khi đó kí hiệu (X, ≤) Ví dụ: 1) Trong N, Z, Q, R quan hệ ≤ thông thường là quan hệ thứ tự. 2) Trong N ∗ xét quan hệ "chia hết": a chia hết cho b nếu tồn tại q ∈ N ∗ sao cho aq = b, kí hiệu a\b. Quan hệ này là quan hệ thứ tự. 3) Quan hệ bao hàm (⊂) trong tập hợp ℘(X) các tập con của một tập X là qun hệ thứ tự. 2.4.2. Quan hệ thứ tự toàn phần và bộ phận Cho X là một tập được sắp thứ tự, Nếu với x, y ∈ X ta có x ≤ y hoặc y ≤ x thì ta nói x và y so sánh được với nhau. Nếu với mọi x, y ∈ X đều 10
12. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng so sánh được với nhau thì ta nói X là tập sắp thứ tự toàn phần (còn gọi là sắp thứ tự tuyến tính hay sắp thẳng). Trong trường hợp trái lại ta nói X là tập sắp thứ tự bộ phận. §3 ÁNH XẠ 3.1 Định nghĩa và ví dụ 3.1.1. Định nghĩa Cho hai tập hợp X và Y. Một ánh xạ f từ X vafoY là một quy tắc đặt tương ứng mỗi x ∈ X với một phần tử duy nhất y = f(x) ∈ Y Kí hiệu: f :X → Y x 7→ y = f(x) Tập X gọi là tập nguồn của ánh xạ. Tập Y gọi là tập đích của ánh xạ. Phần tử y=f(x) gọi là ảnh của phần tử x ∈ X qua ánh xạ f. Phần tử x ∈ X để f(x) = y gọi là một tạo ảnh của y ∈ Y . Từ định nghĩa suy ra: mỗi x ∈ X có duy nhất một ảnh y = f(x) ∈ Y ; mỗi y ∈ Y có thể có một tạo ảnh, có nhiều tạo ảnh hoặc không có tạo ảnh nào. Tất cả các tạo ảnh của y ∈ Y kí hiệu là f −1(y) f −1(y) = {x ∈ X|f(x) = y} 3.1.2. Ví dụ Giả sử cho: X = {a, b, c, d} là tập hợp các cuốn sách. Y = {1, 2, 3, 4, 5} là tập hợp các học sinh. Giả sử các cuốn sách được giao cho các em học sinh mượn sử dụng theo bảng sau: X a b c d Y 3 1 3 4 Ta thấy mỗi phần tử của X đều đặt tương ứng với một và chỉ một phần tử của Y, nên phép đặt tương ứng trên đã xác định một ánh xạ: f : X → Y 11
13. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng §4 GIẢI TÍCH TỔ HỢP 4.1 Quy tắc cộng và quy tắc nhân 4.1.1. Quy tắc cộng Nếu một công việc chia làm k trường hợp để thực hiện, trường hợp 1 có n1 cách thực hiện công việc, trường hợp 2 có n2 cách thực hiện công việc, , trường hợp k có nk cách thực hiện công việc, và không có bất kì một cách thực hiện nào ở trường hợp này lại trùng với một cách thực hiện ở trường hợp khác thì có n1 + n2 + ··· + nk cách thực hiện xong công việc. Ví dụ: Từ các chữ số 1,2,3 có thể lập ra được bao nhiêu số có các chữ số khác nhau? GIẢI: Ta chia ra ba trường hợp - Lập các số có 1 chữ số: có 3 số là 1,2,3; - Lập các số có hai chữ số: có 6 số là 12, 13, 21, 23, 31, 32; - Lập các số có 3 chữ số: có 6 số là: 123, 132, 213, 231, 312, 321; Theo quy tắc cộng có 3+6+6=15 số. 4.1.2. Quy tắc nhân Nếu một công việc chia làm k giai đoạn, giai đoạn 1 có n1 cách thực hiện, giai đoạn 2 có n2 cách thực hiện, , giai đoạn k có nk cách thực hiện thì có n1.n2 ··· nk cách thực hiện xong toàn bộ công việc. Ví dụ: Một thiết bị tạo thành bởi 3 bộ phận. Bộ phận 1 có 10 loại, bộ phận 2 có 7 loại, bộ phận 3 có 5 loại. Hỏi thiết bị trên có bao nhiêu loại. Giải: Giai đoạn 1 chọn bộ phận 1 có 10 cách; giai đoạn 2 chọn bộ phận 2 có 7 cách; giai đoạn 3 chọn bộ phân 3 có 5 cách. Theo quy tắc nhân có 10.7.5=350 loại thiết bị. 4.2 Chỉnh hợp Một chỉnh hợp chập k từ n phần tử là một bộ có kể thứ tự gồm k phần tử khác nhau lấy từ n phần tử đã cho. Số các chỉnh hợp chập k từ n phần tử k kí hiệu là An n! Công thức tính: Ak = n(n − 1) ··· (n − k + 1) = n (n − k)! Ví dụ: Có bao nhiêu số có 3 chữ số gồm toàn các chữ số lẽ khác nhau? 12
14. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Giải: Một số có 3 chữ số lẻ khác nhau tương ứng với một bộ có kể thứ tự gồm 3 chữ số khác nhau lấy từ 5 chữ số 1,3,5,7,9. Từ đó các số thỏa mãn 3 bài toán là A5 = 5.4.3 = 60 4.3 Chỉnh hợp lặp Một chỉnh hợp lặp chập k từ n phần tử là một bộ có kể thứ tự gồm k phần tử không cần khác nhau lấy ra từ n phần tử đã cho. Số các chỉnh hợp chập −k k k từ n phần tử kí hiệu là An = n Ví dụ: Có bao nhiêu cách xếp 8 người lên 5 toa tàu? Giải: Một cách xếp 8 người lên 5 toa tàu tương ứng với một chỉnh hợp −8 8 lặp chập 8 từ 5 phần tử. Do đó số cách là A5 = 5 = 390625. 4.4 Hoán vị Một hoán vị từ n phần tử là một bộ có kể thứ tự gồm n phần tử khác nhau đã cho. Số các hoán vị từ n phần tử kí hiệu là Pn n Công thức tính: Pn = An = n! Ví dụ: Một tổ có 10 học sinh. Hỏi có bao nhiêu cách tổ này đứng thành một hàng dọc. Giải: Một cách đứng thành một hàng dọc tương ứng với một hoán vị từ 10 phần tử. Do đó số cách đứng thành một hàng dọc là: P10 = 10! = 3628800 4.5 Tổ hợp Một tổ hợp chập k từ n phần tử là một tập con gồm k phần tử láy từ n phần tử đã cho. Một tập con gồm k phần tử còn gọi là một bộ không kể thứ tự gồm k phần tử khác nhau. k Số tổ hợp chập k từ n phần tử kí hiệu là Cn n(n − 1) ··· (n − k + 1) n! Công thức tính: Ck = = n k! k!(n − k)! Ví dụ: Một lô hàng có 10 sản phẩm. Hỏi có bao nhiêu cách chọn ra 3 sản phẩm? 13
15. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Giải: Mỗi cách chọn tương ứng với một tổ hợp chập 3 từ 10 phần tử. 3 Vậy số cách chọn là C10 = 120. Tổ hợp có hai tính chất quan trọng sau đây: Định lý 1. k n−k 1) Cn = Cn với mọi k = 0, 1, 2, ··· , n k k−1 k 2) Cn = Cn−1 + Cn−1 với mọi k = 0, 1, 2, ··· , n − 1 4.6 Nhị thức Niu-tơn n n X k n−k k (a + b) = Cna b k=0 Ví dụ. Chứng minh rằng: 0 1 n n 1) Cn + Cn + ··· + Cn = 2 0 1 n n 2) Cn − Cn + ··· + (−1) Cn = 0 BÀI TẬP CHƯƠNG 1 Đề 1. Liệt kê các phần tử của các tập hợp sau: a) A = {x ∈ R|(x − 1)(2x2 + 3x + 1) = 0} b) B = {x ∈ Z|xx = x} c) C = {x ∈ N|x là ước của 24} d) D = {x ∈ N|x2 + 4x − 5 = 0} Đề 2. Viết lại các tập hợp sau bằng cách chỉ ra một tính chất đặc trưng của các phần tử. a) A = {5, 10, 15, 20, 25} b) B = {−2, −1, 0, 1, 2} 1 1 1 c) C = {1, , , , ···} 2 4 8 d) D = {∅} Đề 3. Xét quan hệ giữa các tập A và B cho dưới đây: a) A = {n ∈ N|n2 < 7}; B = {n ∈ N|n3 < 10} 14
16. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng b) A = {các đa giác có chu vi 4m}, B = {các hình vuông có diện tích 1 m2} Đề 4. Cho A = {−2, −1, 0, 3, 4},B = {−1, 2, 3, 5} a) Xác định các tập A ∩ B, A ∪ B, A \ B, B \ A, A∆B b) Tìm tất cả các tập con của A mà nó cũng là tập con của B. Đề 5. Cho A = {−2, −1, 0, 1, 4},B = {0, 1, 2}. Hãy xác định các tập sau đây: a) {(x, y) ∈ A × B|x < y} b) {(x, y) ∈ A × B|x2 ≤ y2} Đề 6. Xác định xem quan hệ R trên tập Z các số nguyên có tính chất phản xạ, đối xứng, bắc cầu không, với xRy nếu và chỉ nếu: a) x 6= y b) xy ≥ 0 c) x = y + 1 hay x = y − 1 d) x là bội của y e) x và y cùng âm hoặc cùng không âm. f) x = y2 g) x ≥ y2 Hướng dẫn: a) R chỉ có tính chất đối xứng. b) R chỉ có tính chất đối xứng và bắc cầu. c) R chỉ có tính chất đối xứng. d) R chỉ có tính chất đối xứng và bắc cầu. e) R chỉ có tính chất phản xạ, đối xứng và bắc cầu. f) R chỉ có tính chất phản đối xứng. g) R chỉ có tính chất phản đối xứng và bắc cầu. Đề 7. Trong số 50 học sinh của lớp có 25 học sinh có năng khiếu Toán, 17 có năng khiếu Văn, 12 không có năng khiếu cả Văn và Toán. Tìm số học sinh của lớp có năng khiếu cả Văn và Toán. Đề 8. Trên tập Z, xét tính chất của các quan hệ sau đây: 15
17. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng a) aRb nếu a+b lẻ. b) aSb nếu a+b Chẵn. Đề 9. Gọi X là tập các học sinh trong một lớp. Trên X xác định các quan hệ: aS1b nếu a và B cùng năm sinh, aS2b nếu a, b cùng giới tính. a) Chứng tỏ S1,S2 là quan hệ tương đương. b) Xác định tập thương X/S1 và X/S2. Đề 10. Trên R xét quan hệ : aSb nếu a3 ≤ b3 aT b nếu a2 ≤ b2 Chứng tỏ S là quan hệ thứ tự toàn phần trên R còn T không là quan hệ thứ tự trên R Đề 11. Từ các chữ số 1,2,3,4,5,6 có thể lập được bao nhiêu số có 4 chữ số a) Các chữ số không cần khác nhau. b) Các chữ số khác nhau. c) Số đầu và số cuối trùng nhau, khác với 3 số giữa. Đề 12. Bảy người (A,B,C,D,E,F,G) lên một đoàn tàu có 10 toa. Hỏi có bao nhiêu cách lên: a) Một cách tùy ý. b) Mỗi người một toa khác nhau. c) A và B lên cùng một toa, những người khác tùy ý. Đề 13. Trong một cuộc liên hoan của một lớp học, tất cả mọi người đều bắt tay nhau và người ta đếm được tất cả 1225 cái bắt tay. Hãy tìm số người của lớp đó. Đề 14. Một lớp học có 20 nam, 10 nữ. Có bao nhiêu cách chọn 3 người trực lớp. a) Một cách tùy ý. b) Có đúng một nữ. c) Có ít nhất một nữ. d) Có nhiều nhất hai nữ. 16
18. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Đề 15. Trên một đường tròn cho n điểm A1,A2, ··· ,An. Hỏi lấy các điểm này làm đỉnh thì: a) Xác định được bao nhiêu tam giác. b) Xác định được bao nhiêu tứ giác lồi. c) Xác định được bao nhiêu đa giác lồi. 17
19. Chương II LOGIC Mục tiêu chương: Về Kiến thức: Sinh viên cần nằm vững những kiến thức cơ bản về mệnh đề, các kiến thức liên quan đến mệnh đề, vị từ, các kiến thức liên quan đến vị từ. Xác định được mối liên hệ giữa những nội dung kiến thức này. Về kĩ năng: Giải được các bài tập liên quan của các chủ đề kiến thức của chương, bước đầu biết vận dụng trong đời sống thực tế. Về thái độ : Nghiêm túc, có tinh thần hợp tác trong học tập §1 LOGIC MỆNH ĐỀ 1.1 Mệnh đề 1.1.1. Phán đoán Một suy nghĩ muốn khẳng định hoặc phủ định một điều gì đó có tính chất hoặc là đúng, hoặc là sai mà không thể vừa đúng lại vừa sai được gọi là một phán đoán. 1.1.2. Mệnh đề Diễn đạt phán đoán bằng một câu ngữ pháp ta có một mệnh đề toán học. Nói cách khác mệnh đề toán học là một câu có tính chất hoặc đúng, hoặc là sai mà không thể vừa đúng lại vừa sai. Như vậy có thể xem mệnh đề toán học là một đại lượng nhận mọt trong hai giá trị, hoặc là đúng, hoặc là sai • Mệnh đề đúng có giá trị chân lý là 1 • Mệnh đề sai có giá trị chân lý là 0 18
20. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng √ Ví dụ: Mệnh đề ”√ 2 là số vô tỉ" có giá trị chân lý là 1 Mệnh đề ” 8 là số nguyên tố" có giá trị chân lý là 0 1.2 Các phép toán về mệnh đề, các kí hiệu quan hệ Cho trước các mệnh đề, kí hiệu bởi các chữ x, y, z, Chúng được gọi là các biến mệnh đề sơ cấp. Sử dụng các liên từ như: không, và, hoặc là, liên kết các mệnh đề sơ cấp ta được các mệnh đề phức hợp. Ứng với mỗi liên từ, chúng ta có một phép toán logic. 1.2.1. Phép phủ định Phép phủ định là phép toán logic cho Bảng chân lý ứng với mỗi mệnh đề sơ cấp x, một x x mệnh đề sơ cấp kí hiệu là x 1 0 0 1 Viết dưới dạng phương trình ta có: 1 = 0; 0 = 1 1.2.2. Phép hội Phép hội là một phép toán logic cho ứng với hai mệnh đề sơ cấp x và y một mẹnh đề mới, kí hiệu là x ∧ y, ( hoặc viết gọn xy) được xác định bằng bảng chân lí: x y x ∧ y 1 1 1 1 0 0 0 1 0 0 0 0 Viết dưới dạng phương trình ta có: 1 ∧ 1 = 1, 1 ∧ 0 = 0, 0 ∧ 1 = 0, 0 ∧ 0 = 0 1.2.3. Phép Tuyển (hoặc là) Phép hội là một phép toán logic cho ứng với hai mệnh đề sơ cấp x và y một mẹnh đề mới, kí hiệu là x ∨ y, được xác định bằng bảng chân lí: x y x ∨ y 1 1 1 1 0 1 0 1 1 0 0 0 19
21. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Viết dưới dạng phương trình ta có: 1 ∨ 1 = 1, 1 ∨ 0 = 1, 0 ∨ 1 = 1, 0 ∧ 0 = 0 1.2.4. Phép kéo theo (nếu thi Phép kéo theo là một phép toán logic cho ứng với hai mệnh đề sơ cấp x và y một mệnh đề mới, kí hiệu là x ⇒ y,(đọc là nếu x thì y) được xác định bằng bảng chân lí: x y x ⇒ y 1 1 1 1 0 0 0 1 1 0 0 1 Viết dưới dạng phương trình ta có: 1 ⇒ 1 = 1, 1 ⇒ 0 = 0, 0 ⇒ 1 = 1, 0 ⇒ 0 = 0 1.2.5. Phép đẳng giá (phép tương đương Phép đẳng giá là một phép toán logic cho ứng với hai mệnh đề sơ cấp x và y một mệnh đề mới, kí hiệu là x ⇔,(đọc là x tương đương y) được xác định bằng bảng chân lí: x y x ⇔ 1 1 1 1 0 0 0 1 0 0 0 1 Viết dưới dạng phương trình ta có: 1 ⇔ 1 = 1, 1 ⇔ 0 = 0, 0 ⇔ 1 = 0, 0 ⇔ 0 = 1 1.2.6. Phép tuyển chọn (phép cộng logic Phép tuyển chọn là một phép toán logic cho ứng với hai mệnh đề sơ cấp x và y một mệnh đề mới, kí hiệu là x ⊕ y,(đọc là x cộng y) được xác định bằng bảng chân lí: 20
22. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng x y x ⊕ y 1 1 0 1 0 1 0 1 1 0 0 0 Viết dưới dạng phương trình ta có: 1 ⊕ 1 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1, 0 ⊕ 0 = 0 1.3 Lượng từ 1.3.1. Các kí hiệu lượng từ Các kí hiệu ∃; ∀ gọi là những kí hiệu lượng từ, ∃ là lượng từ tồn tại, ∀ là lượng từ với mọi. Khi đặt một lượng từ trước một tính chất, ta được mệnh đề đúng hoặc sai 1.3.2. Quan hệ giữa các lượng từ 1. (∃x)P (x) ⇔ (∀x)P (x) 2. (∀x)P (x) ⇔ (∃x)P (x) 1.4 Công thức Từ các biến mệnh đề sơ cấp, nhờ các phép toán logic cơ bản, ta lập được các mệnh đề phức hợp, chúng được gọi là các công thức. Ta thường kí hiệu công thức bởi các chữ F, G, H, R, Chẳng hạn công thức sau: • F = ((xy) ⇒ z) • G = (x ⇒ (y ⇒ z)) • R = (xy ∨ z) 1.5 Các công thức tương đương Hai công thức F và G được gọi là tương đương logic nếu chúng nhận cùng một giá trị chân lí với mọi hệ thống giá trị của các biến mệnh đề sơ cấp. Kí hiệu F=G Chẳng hạn: Nếu F = ((xy) ⇒ z) và G = (x ⇒ (y ⇒ z)) thì F=G 21
23. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Thuật toán đơn giản nhất để nhận biết sự tương đương logic của hai công thức F và G là lập bảng chân lí. x y z xy y ⇒ z ((xy) ⇒ z) (x ⇒ (y ⇒ z)) 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 Từ bảng chân lí này ta suy ra công thức ((xy) ⇒ z) = (x ⇒ (y ⇒ z)) 1.6 Các công thức tương đương logic cơ bản (chỉ chứa ∨; ∧; −) Bằng cách lập giá trị chân lí, chúng ta nhận được 13 công thức tương đương logic cơ bản sau đây: 1. x = x 8. (x ∨ y) = x.y 2. xy = yx 9. (xy) = x ∨ y 3. x ∨ y = y ∨ x 10. x ∨ x = x 4. (xy)z = x(yz) 11. x.x = x 5. (x ∨ y) ∨ z = x ∨ (y ∨ z) 12. x.1 = x 6. x(y ∨ z) = xy ∨ xz 13. x ∨ 0 = x 7. x ∨ (yz) = (x ∨ y)(x ∨ z) Nhận xét. a) Các công thức 2, 3, 4, 5 chứng tỏ rằng phép hội và phép tuyển có tính chất giao hán và kết hợp. Công thức 6 cho thấy phép hội có tính chất phân phối đối với phép tuyển, công thức 7 cho thấy phép tuyển có tính chất phân phối đối với phép hội. b) Quy ước về bỏ dấu ngoặc: Thứ tự thực hiện các phép toán logic là phép hội, phép tuyển, phép kéo theo, phép đẳng giá. 22
24. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Nếu có dấu phủ định trên công thức thì có thể bỏ các dấu ngoặc ở hai đầu công thức. Chẳng hạn (x ⇒ (yz)) = x ⇒ yz 1.7 Các công thức tương đương khác 14. x ⇔ y = (x ⇒ y)(y ⇒⇒ x) 15. x ⇒ y = x ∨ y 16. x ⊕ y = x.y ∨ x.y 17. x ⊕ y = y ⊕ x 18. x ⊕ (y ⊕ z) = (y ⊕ x) ⊕ z 19. x(y ⊕ z) = xy ⊕ xz 20. x ⊕ 1 = x 21. x ⊕ 1 = x 22. x ⊕ x = 0. Nhận xét: Nhờ các hệ thức 8, 9, 14, 15. Ta có thể đưa một công thức bất kì về dạng chỉ chứa 2 phép toán, hoặc là phép hội và phép phủ định, hoặc là phép tuyển và phép phủ định. 1.8 Luật logic Một công thức được gọi là hằng đúng nếu nó nhận giá trị 1 với mọi hệ thống giá trị của các biến mệnh đề sơ cấp. Mỗi một công thức hằng đúng cho ta một luật logic. Luật logic là cơ sở của phép suy luận đúng. Chúng ta xét ba luật logic cơ bản. 1.8.1. Luật đồng nhất (Dựa vào công thức x ⇒ x = 1) Luật đồng nhất nói lên tính chất xác định của quá trình suy luận. Nó đòi hỏi, trong khi xem xét một đối tượng, phải luôn suy nghĩ trong phạm vi (ngoại diên) của đối tượng đó. Không được đồng nhất các khái niệm có nội hàm và ngoại diên khác với khái niệm đang xem xét. 1.8.2. Luật bài trung (Dựa vào công thức x ∧ x = 1) Theo luật bài trung, một sự vật hoặc là tồn tại, hoặc là không tồn tại, hoặc là đúng hoặc là sai. 23
25. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Luật bài trung là cơ sở của phép chứng minh bằng Phương pháp phản chứng của một mệnh đề toán học. 1.8.3. Luật phi mâu thuẫn (Dựa vào công thức x.x = 1) Theo luật phi mâu thuẫn, một sự vật không thể vừa tồn tại, vừa không tồn tại, vừa đúng lại vừa sai. Luật phi mâu thuẫn là cơ sở của phép bác bỏ khi muốn chứng minh một mệnh đề toán học nào đó là sai. 1.9 Hệ quả logic Nếu công thức x ⇒ y = 1 thì mệnh đề y gọi là hệ quả logic của mệnh đề x. Nếu y là hệ quả logic của x và x lại là hệ quả logic của y thì các mệnh đề x và y gọi là tương đương logic. Trong các chứng minh toán học, chúng ta có thể thay thế một công thức này bằng công thức khác tương đương logic với công thức đó. 1.10 Các bài toán giải bằng công cụ logic mệnh đề 1. Các bước giải: Bước 1. Phiên dịch đề bài từ ngôn ngữ đời thường sang ngôn ngữ của logic mệnh đề: - Tìm xem bài toán được tạo thành từ những mệnh đề nào. - Diễn đạt các điều kiện (đã cho và phải tìm) trong vài toán bằng ngôn ngữ của logic mệnh đề. Bước 2. Phân tích mối liên hệ giữa điều kiện đã cho với kết luận của bài toán bằng ngôn ngữ của logic mệnh đề. Bước 3 : Dùng các phương pháp suy luận logic dẫn dắt từ các điều kiện đã cho tới kết luận của bài toán. 2. Các ví dụ minh họa: Ví dụ 1: Cup Tiger 98 có 4 đội lọt vào vòng bán kết: Việt Nam, Singapor, Thái Lan và Inđônêxia. Trước khi thi đấu vòng bán kết, ba bạn Dũng, Quang, Tuấn dự đoán như sau: Dũng: Singapor nhì, còn Thái Lan ba. Quang: Việt Nam nhì, còn Thái Lan thứ tư. Tuấn: Singapor nhất và Inđônêxia nhì. 24
26. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Kết quả mỗi bạn dự đoán đúng một đội và sai một đội. Hõi mỗi đội đã đoạt giải mấy? Giải: Kí hiệu các mệnh đề: - d1, d2 là hai dự đoán của Dũng. - q1, q2 là hai dự đoán của Quang. - t1, t2 là hai dự đoán của Tuấn. Có hai khả năng: - Nếu G(d1) = 1 thì g(t1) = 0. Suy ra G(t2) = 1. Điều này vô lí vì cả hai đội Singapor và Inddoonexxia đều đạt giải nhì. - Nếu G(d1) = 0 thì G(d2) = 1. Suy ra G(q2) = 0 và G(q1) = 1. Suy ra G(q2) = 0 và G(q1) = 1. Suy ra G(t2) = 0 và G(t1) = 1. Vậy Singapor nhất, Việt Nam nhì, Thái Lan ba còn Inđônêxia giải tư. Ví dụ 2: Trong bản báo cáo tổng kết về công tác vệ sinh phòng dịch trong nhà trường có đoạn viết "Học sinh muốn học tập tốt cần phải có sức khỏa tốt. Những học sinh không chấp hành nghiêm chỉnh các quy định về vệ sinh phòng dịch (VSPD) đều không có sức khỏe tốt và nguyên nhân là do cô giáo không dạy cho HS đầy đủ những quy định về VSPD. Muốn giáo viên dạy tốt những quy định này nhà trường phải có đầy đủ tài liệu phục vụ giảng dạy cho GV" Từ đoạn bào cáo trên, bạn hãy chứng tỏ rằng "Học sinh muốn học tập tốt thì nhà trường phải có đủ tài liệu phục vụ giảng dạy cho giáo viên" Giải: Ta kí hiệu: - h= "Học sinh muốn học tập tốt". - s= "Học sinh có sức khỏe tốt". - v= "Học sinh chấp hành những quy định về VSPD". - g= "Cô giáo giảng dạy cho học sinh đầy đủ những quy định về VSPD" - t= "Nhà trường có đủ tài liệu phục vụ giảng dạy cho giáo viên. Nội dung của đoạn báo cáo có thể tóm tắt bằng ngôn ngữ của logic mệnh đề như sau: h ⇒ s (1) v ⇒ s (2) g ⇒ v (3) g ⇒ t (4) Từ (2) và (3) suy ra s ⇒ v (2’) và v ⇒ g (3’) Từ (1), (2’), (3’), (4) và phép suy luận bắc cầu ta suy ra h ⇒ t tức là 25
27. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng "Học sinh muốn học tập tốt thì nhà trường phải có đủ tài liệu phục vụ giảng dạy cho giáo viên". Ví dụ 3: Ba người bạn A, B, C thỏa thuận với nhau một điều như sau: nếu một ai đó trong bọn họ không có mặt ở nhà ngoài giờ làm việc thì ít nhất một trong hai người còn lại, người mà lúc đó đang có mặt ở nhà phải biết người vắng nhà nói trên đang ở đâu. Bạn hãy cho biết A, B, C đang ở đâu, nếu: a) Không ai trong bọn họ biết các bạn mình đang ở đâu? b) Có đúng hai trong bọn họ không biết bạn mình đang ở đâu. Giải: Ta dùng kí hiệu Oa,Ob,Oc theo thứ tự để chỉ mệnh đề "A ở nhà", "B ở nhà", "C ở nhà" và dùng kí hiệu ab để chỉ mệnh đề "A biết B đang ở đâu". Cũng tương tự đối với các kí hiệu ac, ba, bc, ca, cb. Các điều kiện đã cho trong đề bài có thể biểu diễn bởi các công thức sau: Oa ⇒ (Ob ∧ ba) ∨ (Oc ∧ ca) (1) Ob ⇒ (Oa ∧ ab) ∨ (Oc ∧ cb) (2) Oc ⇒ (Oa ∧ ac) ∨ (Ob ∧ bc) (3) a) Đề bài cho biết "Không ai trong bọn họ biết bạn mình đang ở đâu". Điều đó có nghĩa là G(ab) = G(ba) = G(ac) = G(ca) = G(bc) = G(cb) = 1. Trong các công thức (1), (2), (3) chỉ chứa các mệnh đề ab, ba, ac, ca, bc, cb, vì vậy để giải câu a cần sử dụng các phương pháp suy luận logic để dẫn dắt từ các công thức (1), (2), (3) đến các công thức có chứa các mệnh đề phủ định của các mệnh đề đó. Áp dụng các đẳng thức về phép phủ định từ các công thức (1), (2), (3) ta có: (Ob ∧ ba) ∨ (Oc ∧ ca) ⇒ Oa (Oa ∧ ab) ∨ (Oc ∧ cb) ⇒ Ob (Oa ∧ ac) ∨ (Ob ∧ bc) ⇒ Oc Hay (Ob ∧ ba) ∧ (Oc ∧ ca) ⇒ Oa (Oa ∧ ab) ∧ (Oc ∧ cb) ⇒ Ob (Oa ∧ ac) ∧ (Ob ∧ bc) ⇒ Oc 26
28. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Cuối cùng ta được 0 (Ob ∨ ba) ∧ (Oc ∨ ca) ⇒ Oa (1 ) 0 (Oa ∨ ab) ∧ (Oc ∨ cb) ⇒ Ob (2 ) 0 (Oa ∨ ac) ∧ (Ob ∨ bc) ⇒ Oc (3 ) Vì G(ab) = G(ba) = G(ac) = G(ca) = G(bc) = G(cb) = 1 nên G(Ob ∨ ba) ∧ (Oc ∨ ca) = G(Oa ∨ ab) ∧ (Oc ∨ cb) = G(Oa ∨ ac) ∧ (Ob ∨ bc) = 1 Mặt khác các công thức (1’), (2’), (3’) đều có giá trị chân lí bằng 1 của mệnh đề kéo theo ta suy ra G(Oa) = G(Ob) = G(Oc) = 1 Vậy cả ba bạn đang ở nhà. b) Giả sử B, C đều không biết bạn mình đang ở đâu. Thế thì G(ba) = G(ca) = 1. Từ đó suy ra G(Ob ∨ ba) ∧ (Oc ∨ ca) = 1 Từ (1’) suy ra G(Oa) = 1, tức là A đang ở nhà. Tương tự cho các trường hợp còn lại. 1.11 Ứng dụng của logic mệnh đề trong các hệ thống tìm tin tự động hóa Trong các hệ thống tìm tin tự động hiện đại, người ta mô tả mỗi tài liệu bằng cách liệt kê các dấu hiệu cần tìm. Các dấu hiệu đó có thể phản ánh như các thành phần của miêu tả thư mục cũng như nội dung của mỗi tài liệu, được gọi là mẫu tìm và được lưu trong bộ nhớ của máy tính. Yêu cầu của người dùng tin về sách báo và tài liệu được đưa vào bộ nhập của hệ thống tìm tin và trở thành một lệnh tìm. Trong trường hợp đơn giản nhất, lệnh tìm được biểu diễn thành một bảng thống kê các dấu hiệu cần tìm của tài liệu mà người đọc yêu cầu. Khi đó việc tìm tin được tập trung vào bộ phận kiểm tra để kiểm tra xem có các mẫu tìm thỏa mãn các yêu cầu có trong lệnh tìm hay không. Tuy nhiên, có những trường hợp mà yêu cầu của người đọc không thể biểu diễn bằng cách liệt kê đơn giản các dấu hiệu. Trong yêu cầu của người đọc có chứa những nội dung chưa xác định, phải lựa chọn, đôi khi có cả những dấu hiệu không đòi hỏi. Trong trường hợp tổng quát, lệnh tìm được 27
29. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng biểu diễn dưới dạng một mệnh đề phức hợp được thành lập nhờ các liên từ "và", "hoặc", "không", trong đó mỗi mệnh đề đơn giản có dạng: P="Trong tài liệu có dấu hiệu phải tìm x" Trong những mệnh đề khác nhau x nhận những giá trị khác nhau. Đôi khi, người ta nói "Tài liệu nói về dấu hiệu x". Khi đó việc tìm tin tự động có hai bước: - Bước thứ nhất, mỗi một mẫu tìm đều được kiểm tra xem nó có các dấu hiệu trong lệnh tìm hay không. Nếu trong mẫu tìm có dấu hiệu x thì p=1. Nếu trong mẫu tìm không có dấu hiệu x thì p=0. - Bước hai, theo kết quả của bước thứ nhất, tìm giá trị chân lí của mệnh đề phức hợp bằng các phép toán logic. Nếu mệnh đề phức hợp có giá trị bằng 1 thì coi như yêu cầu của người đọc thỏa mãn. Trong trường hợp ngược lại thì không. Ví dụ. Giả sử có một yêu cầu của người đọc như sau:"Tài liệu giảng dạy toán hoặc kĩ thuật tính toán trong hệ thống đào tạo cán bộ thư viện bậc đại học chưa xuất bản" Rõ ràng, ở đây người đọc chưa biết tên gọi cụ thể của tài liệu mà chỉ nêu lên chủ đề của tài liệu, hơn nữa đây là tài liệu viết tay. Giả sử trong hệ thống tìm tin, khi miêu tả tài liệu người ta dùng kí hiệu sau: A - Tài liệu nói về giảng dạy, B - Tài liệu nói về toán học, C - Tài liệu nói về kỉ thuật tính toán, D - Tài liệu nó về giáo dục Đại học, E - Tài liệu nói về thư viện, F - Tài liệu đã xuất bản. Tất cả những dấu hiệu này đều được người đọc nêu lên, trong đó dấu hiệu B và C là dấu hiệu lựa chọn không phải thỏa mãn đồng thời cùng một lúc, còn dấu hiệu F là không mong muốn. Khi đó lệnh tìm được biểu diễn dưới dạng một mệnh đề phức hợp sau: A.(B ∨ C).(D.E).F Giả sử hệ thống phải đáp ứng yêu cầu trên có hai tài liệu sau: 1) Một bài biết tay nhan đề "Áp dụng kĩ thuật tính toán vào giảng dạy trong hệ thống đào tạo cán bộ thư viện bậc đại học" 28
30. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 2) Một luận văn với chủ đề "Hướng cơ bản ứng dụng kĩ thuật tính toán trong công tác thư viện" Các tài liệu này được xử lí đánh chỉ số thành các mẫu tìm. Thể thức so sánh tự động mẫu tìm của các tài liệu đã nêu ra với lệnh tìm được mô phỏng như sau: 1) Máy tính xét các mẫu tìm và xác định giá trị chân lí của tất cả các mệnh đề đơn giản có trong lệnh tìm Tài liệu 1 Tài liệu 2 A=1 A=0 B=0 B=0 C=1 C=1 D=1 D=0 E=1 E=1 F=0 F=0 2) Máy tính căn cứ vào giá trị chân lí trên tính giá trị chân lí của mệnh đề phức hợp. Với tài liệu 1 : A.(B ∨ C).(D.E).F = 1 Với tài liệu 2: A.(B ∨ C).(D.E).F = 0 Như vậy tài liệu 1 đáp ứng nhu cầu người đọc. §2 VỊ TỪ 2.1 Ví dụ Trong mỗi mệnh đề có chủ ngữ và vị ngữ (hoặc chủ từ và vị từ). Ví dụ 1 : Giả sử N = {1, 2, 3, ···} là tập hợp các số tự nhiên và chữ P biểu thị tính chất một số tự nhiên là số nguyên tố. Khi đó mệnh đề "Số tự nhiên a là số nguyên tố " có thể viết dưới dạng P(a), và trong cách ghi chép này hý hiệu a biểu thị chủ từ, còn kí hiệu P biểu thị vị từ, mà ta gọi là vị từ của số nguyên tố. Mệnh đề này đúng hay sai (tức là lấy giá trị một hoặc (không) tùy theo a. Chẳng hạn P(2)=P(3)=1; P(1)=p(4)=0. Thực chất vị từ P là một ánh xạ từ tập N vào tập hợp gồm 2 phần tử B = {0, 1} 29
31. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Ví dụ 2: Giả sử Z = {0, ±1, ±2, ···} là tập hợp số nguyên và C là tính chất cặp số nguyên a, b cùng dấu. Khi đó mệnh đề "Các số nguyên a, b cùng dấu" sẽ được viết dưới dạng C(a,b) và nó sẽ là đúng hoặc sai tùy theo a và b, C(0,a) và C(a,0) theo quy ước có thể xem là bằng một với bất kì a). Vị từ C là vị từ trên tập hợp Z. Nó không còn phụ thuộc vào một số như trong ví dụ 1 mà phụ thuộc vào cặp số. Vị từ C là một ánh xạ của tập tất cả các cặp số nguyên vào tập hợp có hai phần tử B = {0, 1} 2.2 Định nghĩa Định nghĩa 1: Giả sử n là một số tự nhiên bất kì. Khi đó ta gọi vị từ n - nguyên (hoặc n - ngôi) các định trên tập M là một ánh xạ đơn trị P của tập hợp Đề các bậc n của M vào tập hợp gồm 2 giá trị B = {0, 1}. Kí hiệu: P : M n → B Như vậy vị từ n - nguyên P trên tập M là một hàm n ngôi xác định trên M và lấy giá trị trong tập hợp B = {0, 1}. Vì thế cũng như với hàm số, ta dùng kí hiệu: P (x1, x2, ··· , xn),Q(x1, x2, ··· , xn), v.v để chỉ vị từ n - nguyên. Trong trường hợp muốn nhấn mạnh rằng vị từ P là n - nguyên thì ta viết P (n) thay cho P. Nếu qua ánh xạ P, ảnh của hệ thống (a1, a2, ··· , an) là một thì ta viết P (a1, a2, ··· , an) = 1 và nói rằng giá trị của vị từ P ứng với hệ thống (a1, a2, ··· , an) là đúng. Còn nếu ảnh của hệ thống (a1, a2, ··· , an) qua ánh xạ P là không thì ta viết P (a1, a2, ··· , an) = 0 và nói rằng giá trị của vị từ P ứng với hệ thống (a1, a2, ··· , an) là sai. Vị từ n - nguyên với n=1 gọi là đơn nguyên, với n=2 gọi là nhị nguyên và với n=3 gọi là tam nguyên. Vị từ 0 - nguyên là mệnh đề đúng hoặc sai bất kì. Các ví dụ: Giả sử N là tập số tự nhiên. 1. Vị từ đồng nhất E : N 2 → B: E(a1, a2) = 1 khi và chỉ khi a1 = a2. 2. Vị từ thứ tự Q : N 2 → B: Q(a1, a2) = 1 khi và chỉ khi a1 ≤ a2. 3. Vị từ chia hết D : N 2 → B: D(a1, a2) = 1 khi và chỉ khi a1 chia hết cho a2 4. Vị từ lấy tổng S : N 3 → B: S(a1, a2, a3) = 1 khi và chỉ khi a1 + a2 = a3 30
32. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 5. Vị từ lấy tích P : N 3 → B: P (a1, a2, a3) = 1 khi và chỉ khi a1.a2 = a3 Định nghĩa 2: Mỗi tập con A của tập hợp M n gọi là một quan hệ n - nguyên xác định trên tập M. Với n=1,2,3 quan hệ n - nguyên gọi là đơn nguyên, nhị nguyên, tam nguyên. Nếu (a1, a2, ··· , an) ∈ A ta nói rằng các phần tử a1, a2, ··· , an của tập hợp M có quan hệ A. Như vậy các khái niệm vị từ n - nguyên và khái niệm quan hệ n - nguyên xác định trên cùng một tập số M. n n Thật vậy, giả sử A ⊂ M . Nếu với mỗi hệ thống (a1, a2, ··· , an) ∈ M ta đặt P (a1, a2, ··· , an) = 1 khi và chỉ khi (a1, a2, ··· , an) ∈ A thì ta được vị từ n - nguyên trên tập M. Ngược lại nếu P là một vị từ n - nguyên trên M bằng cách đặt (a1, a2, ··· , an) ∈ A khi và chỉ khi P (a1, a2, ··· , an) = 1 ta được một tập con A trong M n. Như vậy là mỗi vị từ n - nguyên P trên tập M xác định duy nhất một quan hệ n - nguyên trên tập M và ngược lại mỗi quan hệ n - nguyên A trên tập M xác định duy nhất một vị từ n - nguyên P trên tập M Các ví dụ: Các vị từ đã xét trong các ví dụ trên xác định trên tập số tự nhiên: 1. Vị từ E xác định quan hệ bằng nhau A1: (a1, a2) ∈ A1 khi và chỉ khi E(a1, a2) = 1 2. Vị từ Q xác định quan hệ thứ tự A2: (a1, a2) ∈ A2 khi và chỉ khi Q(a1, a2) = 1 3. Vị từ D xác định quan hệ A3: (a1, a2) ∈ A3 khi và chỉ khi D(a1, a2) = 1 4. Vị từ S xác định quan hệ A4: (a1, a2, a3) ∈ A4 khi và chỉ khi S(a1, a2, a3) = 1 5. Vị từ P xác định quan hệ A5: (a1, a2, a3) ∈ A5 khi và chỉ khi P (a1, a2, a3) = 1 Định nghĩa 3: Phép toán n - nguyên xác định trên tập M là một ánh xạ đơn trị α từ tập hợp Đecac bậc n của tập hợp M vào tập hợp M: α : M n → M Với n=1,2,3 phép toán n - nguyên gọi là đơn nguyên, nhị nguyên, tam nguyên. Với định nghĩa trên, nếu α là một phép toán n - nguyên trên tập M thì 31
33. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng n với mỗi một hệ thống có thứ tự (a1, a2, ··· , an) ∈ M có một phần tử duy nhất b ∈ M sao cho α(a1, a2, ··· , an) = b Ví dụ: các phép toán nhị nguyên trên tập hợp các số nguyên Z là các phép tính công, trừ và tính nhân. Phép toán đơn nguyên trên Z là phép toán lấy số đối: α : a → (−a) Với mỗi phép toán n - nguyên α trên tập M có thể xác định một vị từ n+1 nguyên Pα bằng cách đặt Pα(a1, a2, ··· , an) = 1 khi và chỉ khi α(a1, a2, ··· , an) = an+1. Viết vắn tắt: Pα(a1, a2, ··· , an) = 1 ⇔ α(a1, a2, ··· , an) = an+1 Chú ý : Tương ứng vừa chỉ ra giữa phép toán và vị từ không là một-một. Cụ thể là không phải mỗi vị từ n+1 - nguyên P có thể cho ứng với một phép toán n - nguyên α sao cho P = Pα. Việc đó chỉ có thể làm được trong trường hợp vị từ P có tính chất sau đây: với mỗi phần tử (a1, a2, ··· , an) trong M có duy nhất phần tử b ∈ M sao cho: P (a1, a2, ··· , an, b) = 1 Nếu x1, x2, ··· , xn là các biến mà miền giá trị của chúng là tập hợp M, còn P là một vị từ n - nguyên xác định trên tập hợp M thì để biểu thị vị từ này ta dùng biểu thức P (x1, x2, ··· , xn), biểu thức này chỉ trở thành mệnh đề khi tất cả các biến x1, x2, ··· , xn trong đó đã được thay thế bằng các phần tử của tập hợp M. Do đó P (x1, x2, ··· , xn) gọi là dạng mệnh đề. Bằng cách thay trong dạng mệnh đề P (x1, x2, ··· , xn) một vài biến bằng những phần tử bất kì của tập M ta sẽ được những vị từ mới và những dạng mệnh đề mới. Đôi khi một dạng mệnh đề có thể suy biến thành một mệnh đề hoàn toàn xác định. Chẳng hạn D(x1, x2) là một dạng mệnh đề, nhưng D(5, 2) là một mệnh đề. Dạng mệnh đề còn gọi là mệnh đề không xác định Như vậy: Mệnh đề không xác định là một câu có chứa biến và không phải là mệnh đề nhưng sẽ trở thành mệnh đề khi ta thay biến bằng một phần tử cụ thể thuộc một tập xác định Chẳng hạn, mệnh đề không xác định một biến x là số nguyên tố xác định trên tập số tự nhiên N 32
34. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Mệnh đề không xác định: "Phương trình sin x = a+b vô nghiệm là mệnh đề không xác định 2 biến a, b xác định trên tập số thực a, b ∈ R. Các mệnh đề không xác định gọi là các hàm mệnh đề hoặc vị từ. 2.3 Hàm mệnh đề một biến F : A → {0; 1} Cho tập A khác rỗng. Ánh xạ là hàm mệnh đề một biến x 7→ F (x) xác định trên hợp A. Kí hiệu: x ∈ A, F (x) hoặc F (x), x ∈ A Ví dụ: F (x) = {x2 − 3x + 2 = 0}, x ∈ R - Phần tử a ∈ A được gọi là thỏa mãn hàm mệnh đề F (x), x ∈ A nếu F (a) = 1. - Phần tử b ∈ A được gọi là không thỏa mãn hàm mệnh đề F (x), x ∈ A nếu F (b) = 0. Kí hiệu tập hợp: F = {a ∈ A : F (a) = 1} gọi là tập đúng của hàm mệnh đề F(x). Gọi F = A \ F = {x ∈ A : F (x) = 0}. Ta có biểu đồ: Nhận xét: Mỗi hàm mệnh đề F (x), x ∈ A xác định một tập con của tập hợp A là F = {x ∈ A : F (x) = 1} tức là xác định một tính chất nào đó của tập hợp A. 2.4 Hàm mệnh đề hai biến F : A × B → {0; 1} Cho hai tập hợp khác rỗng A và B. Ánh xạ là hàm (x, y) 7→ F (x, y) mệnh đề hai biến xác định trên hợp A và B. Kí hiệu: x ∈ A, y ∈ B, F (x, y) hoặc F (x, y), x ∈ A, y ∈ B Phần tử (a, b) ∈ (A × B) được gọi là thỏa mãn hàm mệnh đề F (x, y), nếu F (a, b) = 1. 33
35. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Ta gọi tập hợp: F = {(a, b) ∈ (A × B): F (a, b) = 1} gọi là tập đúng của hàm mệnh đề F(x,y). Nhận xét: (a, b) ∈ A × B ⇒ F (a, b) = 1, do đó hàm mệnh đề F (x, y) trên A, B xác định một tập con của tích Decaster A × B tức là xác định một quan hệ hai ngôi trên A × B Tương tự ta có khái niệm hàm mệnh đề 3, 4, , n biến Ví dụ: F (x, y) = {x; y ∈ M : x < y} với M = {3; 4; 5; 6}. Khi đó ta có: F = (3; 4), (3; 5), (3; 6), (4; 5), (4; 6), (5; 6) §3 CÁC PHÉP TOÁN LOGIC TRÊN CÁC HÀM MỆNH ĐỀ 3.1 Phép phủ định Cho hàm mệnh đề một biến F(x) xác định trên tập A hàm mệnh đề phủ định của hàm mệnh đề F(x), kí hiệu là F (x) cũng xác định trên tập A và nhận giá trị 1 với các phần tử x thuộc A nếu như F(x) nhận giá trị 0. Như vậy hàm mệnh đề F(x) phân tập A thành hai tập con: F = {x ∈ A : F (x) = 1} F = {x ∈ A : F (x) = 0} = {x ∈ A : F (x) = 1} 3.2 Phép tuyển Cho hai hàm mệnh đề F(x) và G(x) cùng xác định trên tập A. Tuyển của hai vị từ F(x), G(x) là một vị từ, kí hiệu là F (x) ∨ G(x) mà F (x) ∨ G(x) nhận giá trị 0 với các phần tử x ∈ A sao cho cả hai vị từ F(x) và G(x) đều nhận giá trị 0. Ta có {x ∈ A : F (x) ∨ G(x) = 1} = {x ∈ A : F (x) = 1} ∪ {x ∈ A : G(x) = 1} Ta có biểu đồ sau: 34
36. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 3.3 Phép hội Cho hai vị từ F(x) và G(x) cùng xác định trên tập A. Hội của hai vị từ F(x) và G(x) là vị trí, kí hiệu là F (x) ∧ G(x) mà vị từ F (x) ∧ G(x) nhận gía trị 1 với các phần tử x ∈ A cho cả hai vị từ F(x) và G(x) nhận giá trị 1. Ta có {x ∈ A : F (x) ∧ G(x)} = {x ∈ A : F (x) = 1} ∩ {x ∈ A : G(x) = 1} Ta có sơ đồ sau: 3.4 Phép kéo theo Cho hai vị từ F(x) và G(x) cùng xác định trên tập A vị từ kéo theo của F(x) và G(x), kí hiệu là F (x) ⇒ G(x) mà vị từ F (x) ⇒ G(x) nhận giá trị 0 nếu với x ∈ A ta có F(x) nhận giá trị 1 còn G(x) nhận giá trị 0. Ta có {x ∈ A : F (x) ⇒ G(x) = 0} = {x ∈ A : F (x) = 1} ∩ {x ∈ A : G(x) = 0} Với chú ý F (x) ⇒ G(x) = F (x) ∨ G(x). Nên {x ∈ A : F (x) ⇒ G(x) = 1} = {x ∈ A : F (x) ∨ G(x) = 1} = {x ∈ A : F (x) = 1} ∩ {x ∈ A : G(x) = 1} 3.5 Phép tương đương Cho hai vị từ F(x) và G(x) cùng xác định trên tập A vị từ tương đương của hai vị từ F(x) và G(x) là một vị từ, kí hiệu là F (x) ⇔ G(x) mà vị từ này nhận giá trị 1 nếu với x ∈ A mà cả hai vị từ G(x), F(x) nhận giá trị 1 hoặc cùng nhận giá trị 0. Các kí hiệu ∃; ∀ gọi là những kí hiệu lượng từ, ∃ là lượng từ tồn tại, ∀ là lượng từ với mọi. Khi đặt một lượng từ trước một tính chất, ta được mệnh đề đúng hoặc sai. §4 ĐẠI SỐ BOOLE 4.1 Sơ lược về đại số Boole (Nhà toán học Ireland: G.Boole 1815-1864) 35
37. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Cho một tập hợp các phần tử có bản chất bất kì kí hiệu là A, B, C, , X, Y, ? Trong tập này ta xác định một quan hệ bằng nhau, kí hiệu "=" có các tính chất" i) Phản xạ: với mọi A ta có A=A ii) Đối xứng: với mọi A, B nếu A=B thì B=A iii) Bắc cầu: với mọi A, B, C nếu A=B, B=C thì A=C. Trong tập hợp này xác định hai phép toán: Phép toán cộng kí hiệu là: "⊕" Phép toán nhân kí hiệu là: "" Các phép toán này thỏa mãn các điều kiện sau đây: (Tiên đề) 1. Tồn tại phần tử trung hòa đối với phép cộng,kí hiệu là 0 sao cho với mọi X, ta có X ⊕ 0 = X 2. Tồn tại phần tử trung hòa, ta có X 1 = X 3. Phép cộng có tính giao hoán: ∀X, Y ta có X ⊕ Y = Y ⊕ X 4. Phép nhân có tính giao hoán: ∀X, Y ta có X Y = Y X 5. Phép nhân phân phối đối với phép cộng ∀X, Y, Z ta có X (Y ⊕ Z) = (X Y ) ⊕ (X Z) 6. Phép cộng phân phối đối với phép nhân: ∀X, Y, Z ta có X ⊕ (Y Z) = (X ⊕ Y ) (X ⊕ Z) 7. Đối với mọi X, đều tồn tại X sao cho X ⊕ X = 1 8. X X = 0 Nhận xét: Đại số các tập hợp và đại số logic (Đại số mệnh đề) là hai mô hình cụ thể đại số vừa xây dựng trên đây. Ta xét bảng so sánh sau đây: 36
38. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Đại số Boole Đại số logic Đại số tập hợp Các biến của đại số Các biến mệnh đề sơ Cho tập hợp P và A, Boole: A, B, C, ,X, cấp: A, B, C, ,X, B, C, là các tập con Y Y của P "=" bằng nhau của ⇔ Sự tương đương (=) sự bằng nhau các biến A, B, C logic của các biến của các tập hợp mệnh đề sơ cấp ⊕: Phép toán cộng ∨: Phép toán tuyển ∪: Phép hợp hai tập hợp : Phép toán nhân ∧: Phép toán hội ∩: Phép giao của hai tập hợp A: Phần bù của A A: Mệnh đề phủ định A: Phần bù của tập của A A 0: Phần tử trung hòa 0: Mệnh đề hằng sai ø: Tập hợp rỗng của phép cộng 1: Phần tử trung hòa 1: Mệnh đề hằng P: Tập hợp toàn thể của phép nhân đúng Dễ dàng kiểm tra được đại số Boole và các mô hình cụ thể của nó thỏa mãn 13 công thức về logic. 4.2 Hệ đếm nhị phân a. Biến nhị phân và các phép toán cơ bản Giả sử cho X là một tập hợp gồm 8 phần tử. X = {a, b, c, d, e, f, g, h} Xét hai tập con A và B của X A = {a, c, e, f} B = {b, c, e, f, g} Nhờ khái niệm ánh xạ đặc trưng, ta có thể biểu diễn tập con A và B như sau: a b c d e f g h A= 1 0 1 0 1 1 0 0 a b c d e f g h B= 0 1 1 0 1 1 1 0 37
39. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Khi đó giao của A và B là tập A ∩ B = {c, e, f} Hay A ∩ B = 0 0 1 0 1 1 0 0 Khi đó trong A ∩ B được tạo thành 0 trong A, 0 trong B cho 0 trong A ∩ B, 0 trong A, 1 trong B cho 0 trong A ∩ B, 1 trong A, 0 trong B cho 0 trong A ∩ B 1 trong A, 1 trong B cho 1 trong A ∩ B Ta có thể biểu diễn kết quả trên trong bảng sau: trong B 0 1 Trong A 0 0 0 trong A ∩ B 1 0 1 Như vậy, ứng với bảng trên ta có thể xây dựng phép toán tích trên tập I = {0, 1}, gọi là tích Boole mà ta kí hiệu là (.), như sau: 0.0=0 0.1=0 1.0=0 1.1=1 Bây giờ xét hợp cả hai tập hợp A và B, ta có A ∪ B = {a, b, c, e, f, g} Hay A ∪ B = 1 1 1 0 1 1 1 0 Khi đó trong A ∪ B được tạo thành 0 trong A, 0 trong B cho 0 trong A ∪ B, 0 trong A, 1 trong B cho 1 trong A ∪ B, 1 trong A, 0 trong B cho 1 trong A ∪ B 1 trong A, 1 trong B cho 1 trong A ∪ B Ta có thể biểu diễn kết quả trên trong bảng sau: trong B 0 1 Trong A 0 0 1 trong A ∪ B 1 1 1 Từ bảng trên, ta có thể xây dựng một phép toán trên tập I = {0, 1} gọi là tổng Boole kí hiệu là (+), như sau: 0+0=0 38
40. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 0+1=1 1+0=0 1+1=1 Xét phần bù của tập A, ta có A = {b, d, g, h} a b c d e f g h Hay A= 0 1 0 1 0 0 1 1 Ta nhận thấy A được tạo thành như sau: 0 trong A cho 1 trong A, 1 trong A cho 0 trong A Như vậy, các phép toán giao, hợp, phần bù trên các tập con của lý thuyết tập hợp tương ứng với các phép toán tích Boole, tổng Boole, phần bù thực hiện trên các chỉ số "thuộc" 0 và 1 của tập con đang xét. Các phép toán đó là các phép toán cơ bản của đại số Boole mà ta có thể định nghĩa tổng quát như sau: Giả sửa, b là các biến nhị phân (biến Boole) tức là nó chỉ nhận hai giá trị 0 v à 1. Ta gọi tích của a và b kí hiệu là a.b, tổng của a và b khí hiệu là a+b, phần bù của a kí hiệu là a là các phép toán được xác định như sau: a b a.b a+b a 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 Ta nhận thấy các phép toán nhị phân Boole (.), (+), (−) được xây dựng như thế tuân theo đúng quy tắc của các phép toán hội ∧, tuyển ∨, và phủ định − trong logic mệnh đề, khi ta thay a, b là các biến mệnh đề. b. Tính chất của các phép toán Boole Giả sử a,b,c là các biến nhị phân. Các phép toán Boole có các tính chất sau: 1) tính giao hoán a+b=b+a a.b=b.a 2) Tính kết hợp a+(b+c)=(a+b)+c a.(b.c)=(a.b).c 3) Tính phân phối 39
41. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng a+(b.c)=(a+b).(a+c) a.(b+c)=(a.b)+(a.c) 4. Tính lũy đẳng a+a=a a.a=a 5. Tính trung tính a+o=a a.1=a a+1=1 a.0=0 6. Tính đối hợp (a)=a 7. Luật bài trung và phi mâu thuẫn a+a=1 a.a=0 8. Quy tắc De morgan a + b = a.b a.b = a + b 9. Tính chất hấp thụ a=a.b=a a.(a+b)=a Ta chứng minh các tính chất trên dựa vào bảng giá trị c. Biểu thức Boole Khi kết hợp các biến nhị phân bằng các phép toán (+), (.), (−), ta tạo thành các biểu thức của các biến nhị phân, còn gọi là biểu thức Boole. Các biểu thức Boole cũng là những biến nhị phân, tức là nó chỉ nhận các giá trị 0 hoặc 1. Ví dụ: f(x, y, z) = (x + y).(z + x.y) f(x, y) = (x + y).(x + y).(x + y).(x + y) là những biểu thức Boole Sử dụng các tính chất của biểu thức Boole ta có thể biến đổi một biểu thức Boole thành một biểu thức có dạng đơn giản hơn. Ví dụ: 40
42. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng f(x, y, z) =(x + y + z).(x + y) =x.y.z(x + y) 1) =x.x.y.z + x.y.y.z =0 + x.y.y.z =x.y.z Giả sử f(x,y,z) và g(x,y,z) là hai biểu thức Boole. Ta gọi đẳng thức f(x,y,z)=g(x,y,z) là một phương trình Boole. Nghiệm của phương trình là giá trị các biến làm cho phương trình trở thành một dẳng thức đúng. Để giải phương trình Boole người ta dùng phương pháp lập bảng giá trị. Ví dụ: Giải phương trình x.y + z = x.y.z + y Giải tìm nghiệm là: (0,0,1); (0,1,0); (0,1,1); (1,0,0); (1,0,1); (1,1,0). Như vậy, logic mệnh đề và đại số Boole là cơ sở logic của máy tính điện tử. Còn cơ sở số học của máy tính điện tử là hệ đếm nhị phân. BÀI TẬP CHƯƠNG 1 Đề 1. Liệt kê các phần tử của các tập hợp sau: a) A = {x ∈ R|(x − 1)(2x2 + 3x + 1) = 0} b) B = {x ∈ Z|xx = x} c) C = {x ∈ N|x là ước của 24} d) D = {x ∈ N|x2 + 4x − 5 = 0} Đề 2. Viết lại các tập hợp sau bằng cách chỉ ra một tính chất đặc trưng của các phần tử. a) A = {5, 10, 15, 20, 25} b) B = {−2, −1, 0, 1, 2} 1 1 1 c) C = {1, , , , ···} 2 4 8 d) D = {∅} Đề 3. Xét quan hệ giữa các tập A và B cho dưới đây: a) A = {n ∈ N|n2 < 7}; B = {n ∈ N|n3 < 10} 41
43. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng b) A = {các đa giác có chu vi 4m}, B = {các hình vuông có diện tích 1 m2} Đề 4. Cho A = {−2, −1, 0, 3, 4},B = {−1, 2, 3, 5} a) Xác định các tập A ∩ B, A ∪ B, A \ B, B \ A, A∆B b) Tìm tất cả các tập con của A mà nó cũng là tập con của B. Đề 5. Cho A = {−2, −1, 0, 1, 4},B = {0, 1, 2}. Hãy xác định các tập sau đây: a) {(x, y) ∈ A × B|x < y} b) {(x, y) ∈ A × B|x2 ≤ y2} Đề 6. Trong số 50 học sinh của lớp có 25 học sinh có năng khiếu Toán, 17 có năng khiếu Văn, 12 không có năng khiếu cả Văn và Toán. Tìm số học sinh của lớp có năng khiếu cả Văn và Toán. Đề 7. Trên tập Z, xét tính chất của các quan hệ sau đây: a) aRb nếu a+b lẻ. b) aSb nếu a+b Chẵn. Đề 8. Gọi X là tập các học sinh trong một lớp. Trên X xác định các quan hệ: aS1b nếu a và B cùng năm sinh, aS2b nếu a, b cùng giới tính. a) Chứng tỏ S1,S2 là quan hệ tương đương. b) Xác định tập thương X/S1 và X/S2. Đề 9. Trên R xét quan hệ : aSb nếu a3 ≤ b3 aT b nếu a2 ≤ b2 Chứng tỏ S là quan hệ thứ tự toàn phần trên R còn T không là quan hệ thứ tự trên R Đề 10. Từ các chữ số 1,2,3,4,5,6 có thể lập được bao nhiêu số có 4 chữ số a) Các chữ số không cần khác nhau. b) Các chữ số khác nhau. c) Số đầu và số cuối trùng nhau, khác với 3 số giữa. 42
44. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Đề 11. Bảy người (A,B,C,D,E,F,G) lên một đoàn tàu có 10 toa. Hỏi có bao nhiêu cách lên: a) Một cách tùy ý. b) Mỗi người một toa khác nhau. c) A và B lên cùng một toa, những người khác tùy ý. Đề 12. Trong một cuộc liên hoan của một lớp học, tất cả mọi người đều bắt tay nhau và người ta đếm được tất cả 1225 cái bắt tay. Hãy tìm số người của lớp đó. Đề 13. Một lớp học có 20 nam, 10 nữ. Có bao nhiêu cách chọn 3 người trực lớp. a) Một cách tùy ý. b) Có đúng một nữ. c) Có ít nhất một nữ. d) Có nhiều nhất hai nữ. Đề 14. Trên một đường tròn cho n điểm A1,A2, ··· ,An. Hỏi lấy các điểm này làm đỉnh thì: a) Xác định được bao nhiêu tam giác. b) Xác định được bao nhiêu tứ giác lồi. c) Xác định được bao nhiêu đa giác lồi. Đề 15. Dùng lượng từ ∃ hoặc ∀ để biểu diễn các mệnh đề dưới đây, sau đó thiết lập mệnh đề phủ định của chúng. a) Một số học sinh không hiểu bài. b) Có quả ớt không cay. c) Tất cả chất khí đều không dẫn điện. Đề 16. Bạn hãy chứng tỏ những kết luận sau đây là sai: 1) Có một số tự nhiên mà mọi số chẵn đều nhỏ hơn nó. 2) Mọi người đàn ông đều có một người đàn bà là vợ của người ấy. 3) Mỗi tháng đều có ba ngày chủ nhật là ngày lẻ. 43
45. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng Đề 17. Cho trước các mệnh đề: 1) Trẻ sơ sinh chưa có tư duy logic. 2) Chúng ta không dám coi thường những người chinh phục được cá sấu. 3) Chúng ta coi thường những những người chưa có tư duy logic. Đề 18. Rút gọn công thức 1) A = x ∨ y ⇒ (x ⇒ z) 2) B = (x ⇔ y) ∨ x 3) C = x ⇒ y ∨ (x ⇒ y) 4) D = (xy ∨ xy)z ∨ (xy ∨ xy).z Đề 19. Ba tên Cam, Quýt và Cuội bị tố cáo đã tham gia vào một vụ cướp nhà băng. Bọn chúng lẫn trốn bằng xe riêng. Trong cuộc điều tra: • Tên Cam khai bọn chúng đi trên chiếc TOYOTA màu xanh. • Tên Quýt khai đó là chiếc MERCESDES màu đen. • Riêng tên Cuội thì cam đoan rằng chún bỏ chạy trên chiếc FORD không phải màu xanh. Giả sử rằng, trong các lời khai trên của mỗi tên chỉ đúng: hoặc là màu xe, hoặc là nhãn hiệu Oto. Hỏi chiếc Oto đó màu gì? của hãng xe nào? Đề 20. Sau khi làm bài kiểm tra, trên đường về nhà. Bạn An nói: Mình được điểm 10. Bạn Bình khẳng định mình được 6. Còn bạn Cúc vẻ không tự tin: mình không đạt điểm 10. Sau khi thầy giáo trả bài: Một trong 3 bạn đạt điểm 6, một bạn đạt điểm 10. So với dự kiến ban đầu thì có hai bạn trả lời đúng, một người sai. Hỏi điểm bài kiểm tra của mỗi bạn. Đề 21. Bốn đội bóng A, B, C, D tham gia vào một cuộc thi đấu để xếp hạng. • Một người dự đoán: B hạng nhì, C hạng ba • Người thứ hai dự đoán: A hạng nhì, C hạng tư 44
46. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng • Người thứ ba dự đoán: B hạng nhất, D hạng nhì. Kết quả cho thấy mỗi người có một phần đúng và một phần sai. Vậy kết quả xếp hạng thế nào. Đề 22. Trong phòng có 100 người quen với ít nhất là 67 người khác. Chứng minh rằng trong phòng phải có 4 người từng đôi một quen nhau. Đề 23. Một gia đình có 5 người: bố, mẹ, em gái, một anh trai và một chị gái. Những buổi đi xem hát vào tối thứ 7 bao giờ cũng tuân theo quy luật sau: a) Nếu bố đi thì mẹ, ít nhất một trong hai chị,em gái cùng đi. b) Hai chị em gái không đồng thời cùng đi. c) Anh trai và em gái hoặc cùng đi hoặc không cùng đi. Hỏi, tuân theo quy tắc trên thì những ai trong gia đình đi xem hát trong mỗi trường hợp sau: TH1: Mẹ không đi và anh trai đi. TH2: Bố và ít nhất một trong hai chị em cùng đi. Đề 24. Một giải bóng đá có n đội tham dự, các đội thi đấu vòng tròn mọt lượt. Trong mỗi trận, đội thắng được hai điểm. Đội hòa được 1 điểm và đội thua không điểm. Các đội có cùng số điểm sẽ được xếp hạng theo các chỉ số phụ nào đó. Khi kết thúc giải, đội vô địch được 8 điểm, đội xếp thứ nhì được 6 điểm, đội xếp thứ ba được 5 điểm. Các đội còn lại có số điểm khác nhau, hãy cho biết số đội đã tham dự giải và số điểm các đội còn lại (có giải thích rõ). Đề 25. Sau một thời gian dài xa cách, hai người bạn cũ gặp lại nhau. Một trong hai người thông báo là anh ta đã có 3 người con trai và tích các tuổi của chúng bằng 36; còn tổng các tuổi của chúng thì bằng số cửa sổ của ngôi nhà cạnh chỗ họ đang gặp nhau. Sau đó, người thứ hai lập tức đọc ngay được số tuổi đám trẻ con một cách chính xác. Hỏi tuổi của mỗi đứa trẻ. Đề 26. Cho định lý: "Nếu đường thẳng c bất kì của mặt phẳng đã cắt đường thẳng a thì cũng cắt đường thẳng b thì hai đường thẳng a và b song song với nhau". 1) Viết cấu trúc logic của định lí đã cho. 45
47. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng 2) Sử dụng hình thức phản đảo, chứng minh định lí đã cho. Đề 27. Có tất cả 105 học sinh làm một đề kiểm tra. Đề kiểm tra gồm 1 bài toán Đại số, 1 bài toán Hình học và 1 bài toán Lượng giác. Biết rằng: 70 em giải được bài toán đại số; 59 em giải được bài toán hình học và 62 em giải được bài toán Lượng giác; 90 em làm được bài toán Đại số hoặc Hình học; 89 em giải được bài toán Hình học hoặc Lượng giác; 91 em học sinh giải được bài toán Đại số hoặc Lượng giác; còn 6 em không làm được bài toán nào. Hỏi có bao nhiêu em học sinh giải được cả ba bài toán của đề kiểm tra.(20 em). Đề 28. Có 10 người đi họp. Mỗi người quen với ít nhất là 5 người khác. Chứng tỏ rằng, nếu cần sắp xếp 4 người vào một bàn tròn gồm 4 chỗ ngồi thì có thể xếp sao cho người nào cũng ngồi giữa hai quen của mình. 46
48. Nhập môn toán cao cấp TS Nguyễn Dương Hoàng TÀI LIỆU THAM KHẢO 1. Đậu Thế Cấp(2005),Tập hợp logic, NXBGD. 2. Trần Thọ Châu(2005),Logic Toán, NXBĐHQG Hà Nội. 3. Nguyễn Mạnh Trinh (2002), Bước đầu làm quen với Logic Toán, NXBGD. 4. Đào Hữu Hồ (1997), Xác suất - Thống kê, NXBGD Hà Nội. 5. Đặng Hấn (1996), Xác suất - Thống kê, NXB Thống kê. 6. Đặng Hấn (1996), Bài tập xác suất - Thống kê, NXB Thống kê. 7. Trần Đức Ngôn (1997), Tra cứu thông tin trong hoạt động thư viện thông tin, NXBGD ĐHSP. 8. Đinh Văn Gắng (1997), Bài tập xác suất - Thống kê, NXBGD ĐHSP. 9. Đoàn Phan Tân (1992), Một số phương pháp toán học trong công tác TVTT, Trường ĐHVH Hà Nội. 47