Bài giảng Cơ sở Toán học - Nguyễn Văn Phong

Nội dung text: Bài giảng Cơ sở Toán học - Nguyễn Văn Phong

1. CƠ SỞ TOÁN HỌC Nguyễn Văn Phong Toán cao cấp - MS: MAT1006 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 1 / 27
2. Nội dung 1 LOGIC Khái niệm Các phép toán Tương đương logic Hệ quả logic 2 TẬP HỢP Khái niệm Quan hệ giữa các tập hợp Các phép toán trên tập hợp Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 1 / 27
3. Khái niệm Các phát biểu (khẳng định) hoặc đúng, hoặc sai nhưng không thể vừa đúng vừa sai. Các mệnh đề đúng được gọi là có chân trị đúng và các mệnh đề sai có chân trị sai. - Ký hiệu: p, q, r, : chỉ các mệnh đề - Ký hiệu: 1: Chân trị đúng; 0: Chân trị sai Ví dụ. p : "4 là số nguyên tố" - là mệnh đề có chân trị 0 q : "1 + 1 = 3" - là mệnh đề có chân trị 0 r : "x > 2" - không là mệnh đề t : "2 là số chẵn" - là mệnh đề có chân trị 1 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 2 / 27
4. Các phép toán Phép phủ định. Phủ định của mệnh đề p, ký hiệu p¯ và đọc là không p, có chân trị là 1 khi p có chân trị là 0 Bảng chân trị p p¯ 0 1 1 0 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 3 / 27
5. Các phép toán Phép nối liền (phép hội). Mệnh đề p ∧ q, đọc là p và q, chỉ có chân trị 1 khi p và q cùng có chân trị 1. Bảng chân trị p q p ∧ q 0 0 0 0 1 0 1 0 0 1 1 1 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 4 / 27
6. Các phép toán Phép nối rời (phép tuyển). Mệnh đề p ∨ q, đọc là p hay q, chỉ có chân trị 0 khi p và q cùng có chân trị 0. Bảng chân trị p q p ∨ q 0 0 0 0 1 1 1 0 1 1 1 1 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 5 / 27
7. Các phép toán Phép kéo theo. Mệnh đề p → q, đọc là p kéo theo q, (hay nếu p thì q), chỉ có chân trị 0 khi p có chân trị 1 và q có chân trị 0. Bảng chân trị p q p → q 0 0 1 0 1 1 1 0 0 1 1 1 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 6 / 27
8. Các phép toán Phép kéo theo hai chiều. Mệnh đề (p → q) ∧ (q → p), ký hiệu là p ↔ q, đọc là p nếu và chỉ nếu q, chỉ có chân trị 1 khi cả p và q có cùng chân trị. Bảng chân trị p q p → q q → p p ↔ q 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 7 / 27
9. Định nghĩa. Dạng mệnh đề. Là một mệnh đề phức hợp (hay gọi là một biểu thức mệnh đề) được thành lập bằng cách kết hợp từ các biến mệnh đề đơn giản p, q, r, và các phép toán. - Ký hiệu: A, B, C, - Ví dụ: Dạng mệnh đề: A(p, q, r) := [(p → q) ∧ r] Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 8 / 27
10. Định nghĩa. Hằng đúng. Một dạng mệnh đề được gọi là hằng đúng (chân lý), ký hiệu là 1, nếu nó luôn có chân trị 1 bất chấp chân trị của các biến mệnh đề tạo thành nó. Hằng sai. Một dạng mệnh đề được gọi là hằng sai (mâu thuẫn), ký hiệu là 0, nếu nó luôn có chân trị 0 bất chấp chân trị của các biến mệnh đề tạo thành nó. Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 9 / 27
11. Tương đương logic Định nghĩa. Hai dạng mệnh đề A và B được gọi là tương đương logic, ký hiệu A ⇔ B, nếu dạng mệnh đề A ↔ B là hằng đúng. Ví dụ. Với các dạng mệnh đề A = (p ∨ q), B = p¯ ∧ q¯, ta có p q p ∨ q A p¯ q¯ B A ↔ B 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 10 / 27
12. Tương đương logic Định lý Cho p, q, r là các mệnh đề, ta có: 1. (p¯) ⇔ p (luật phủ định đôi) 2. (p ∨ q) ⇔ p¯ ∧ q;¯ (p ∧ q) ⇔ p¯ ∨ q¯ (luật De Morgan) 3. p ∨ q ⇔ q ∨ p; p ∧ q ⇔ q ∧ p (luật giao hoán) 4. p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r; p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r (luật kết hợp) 5. p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r); p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) (luật phân bố) 6. p ∨ p ⇔ p; p ∧ p ⇔ p (luật luỹ đẳng) Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 11 / 27
13. Tương đương logic Định lý Cho p, q, r là các mệnh đề, ta có: 7. p ∨ 0 ⇔ p; p ∧ 1 ⇔ p (luật trung hoà) 8. p ∨ p¯ ⇔ 1; p ∧ p¯ ⇔ 0 (luật về phần tử bù) 9. p ∨ 1 ⇔ 1; p ∧ 0 ⇔ 0 (luật thống trị) 10. p ∨ (p ∧ q) ⇔ p; p ∧ (p ∨ q) ⇔ p (luật hấp thụ) Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 12 / 27
14. Tương đương logic Định lý Cho p, q, r là các mệnh đề, ta có: i) (p → q) ⇔ (q¯ → p¯) (phép chứng minh đảo đề) ii) (p → q) ⇔ p ∧ q¯ (phép chứng minh phản ví dụ) iii) p ⇔ (p¯ → 0) (phép chứng minh phản chứng) iv) [p → (q ∨ r)] ⇔ [(p ∨ q¯) → r] Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 13 / 27
15. Hệ quả logic Định nghĩa. Dạng mệnh đề B được gọi là hệ quả logic của dạng mệnh đề A, ký hiệu A ⇒ B, nếu dạng mệnh đề A → B là hằng đúng. Ví dụ. Với các dạng mệnh đề A = p ∧ q, B = p ∨ q, ta có p q A B A → B 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 14 / 27
16. Hệ quả logic Định lý Cho p, q, r là các mệnh đề, ta có: i) [(p → q) ∧ p] ⇒ q (phép khẳng định) ii) [(p → q) ∧ q¯] ⇒ p¯ (phép phủ định) iii) [(p → q) ∧ (q → r)] ⇒ (p → r) (tam đoạn luận) iv) [(p ∨ q) ∧ p¯] ⇒ q (tam đoạn luận rời) v) [(p → r) ∧ (q → r)] ⇒ [(p ∨ q) → r] (chứng minh theo trường hợp) Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 15 / 27
17. Khái niệm Sự gom góp các đối tượng có cùng tính chất với nhau cho ta hình ảnh về tập hợp. Các đối tượng được gọi là các phần tử của tập hợp. Ký hiệu: A, B, C, chỉ các tập hợp Nếu a là một phần tử của A, ký hiệu a ∈ A. Ngược lại nếu a không là phần tử của A, ký hiệu a ∈/ A. Tập rổng, ký hiệu ∅, là tập không có phần tử nào cả. Tập hợp có thể được xác định bằng nhiều cách như: Liệt kê, Biểu thức mệnh đề, giản đồ Venn. Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 16 / 27
18. Ví dụ A = {2, 4, 6, 8}  2 A = x ∈ R p(x) = x − 2x + 9 ≥ 0 Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 17 / 27
19. Quan hệ giữa các tập hợp Tập con. Tập hợp A được gọi là một tập con của tập hợp B, ký hiệu A ⊂ B , khi mọi phần tử của A đều là phần tử của B, nghĩa là ∀x, x ∈ A → x ∈ B Quy ước: ∅ ⊂ A, ∀A Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 18 / 27
20. Quan hệ giữa các tập hợp Hai tập bằng nhau. Tập hợp A và B được gọi là bằng nhau, ký hiệu A = B , khi mọi phần tử của A đều là phần tử của B và ngược lại nghĩa là ∀x, x ∈ A ↔ x ∈ B Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 19 / 27
21. Các phép toán trên tập hợp Với A, B là các tập con của tập X , ta có Phép lấy phần bù. Phần bù của A trong X , ký hiệu CX A hay A¯, là tập con của X bao gồm các phần tử không thuộc về A. A¯ = {x ∈ X |x ∈/ A} Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 20 / 27
22. Các phép toán trên tập hợp Với A, B là các tập con của tập X , ta có Phép lấy phần hội. Phần hội của A với B, ký hiệu A ∪ B, là tập con của X gồm các phần tử thuộc về A hay thuộc về B. A ∪ B = {x ∈ X |x ∈ A ∨ x ∈ B } Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 21 / 27
23. Các phép toán trên tập hợp Với A, B là các tập con của tập X , ta có Phép lấy phần giao. Phần giao của A với B, ký hiệu A ∩ B, là tập con của X gồm các phần tử thuộc về A và thuộc về B. A ∩ B = {x ∈ X |x ∈ A ∧ x ∈ B } Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 22 / 27
24. Các phép toán trên tập hợp Với A, B là các tập con của tập X , ta có Phép lấy phần hiệu. Phần phần của A với B, ký hiệu A\B, là tập con của X gồm các phần tử thuộc về A và không thuộc về B. A\B = {x ∈ X |x ∈ A ∧ x ∈/ B } Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 23 / 27
25. Một số tính chất Với A, B, C là các tập con của tập X , ta có Định lý i) A¯
    = A ii) A ∪ B = B ∪ A; A ∩ B = B ∩ A iii) (A ∪ B) ∪ C = A ∪ (B ∪ C); (A ∩ B) ∩ C = A ∩ (B ∩ C) iv) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) v) (A ∪ B) = A¯ ∩ B;¯ (A ∩ B) = A¯ ∪ B¯ Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 24 / 27
26. Một số tính chất Với A, B, C là các tập con của tập X , ta có Định lý vi) A ∪ A = A; A ∩ A = A vii) A ∪ ∅ = A; A ∩ X = A viii) A ∪ X = X;A ∩ ∅ = ∅ ix) A ∪ A¯ = X;A ∩ A¯ = ∅ x) A ∪ (A ∩ B) = A; A ∩ (A ∪ B) = A Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 25 / 27
27. Một số tính chất Với A, B, C là các tập con của tập X , ta có Mệnh đề i) A ∩ B ⊂ A ⊂ A ∪ B ii) Nếu A ⊂ B và B ⊂ C thì A ⊂ C iii) A ⊂ B ⇔ B¯ ⊂ A¯ ⇔ A¯ ∪ B = X ⇔ A ∩ B¯ = ∅ Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 26 / 27
28. Tập hợp tích Định nghĩa. Với hai tập hợp X , Y , tích Descartes của X và Y , ký hiệu X × Y , là tập hợp tất cả các bộ thứ tự (x, y) với x ∈ X , y ∈ Y , X × Y = { (x, y) | x ∈ X , y ∈ Y } Tổng quát, với n tập X1, X2, , Xn, ta có X1 × × Xn = { (x1, , xn) | x1 ∈ X1, , xn ∈ Xn } Nguyễn Văn Phong (BMT - TK) Cơ Sở Toán Học Toán cao cấp - MS: MAT1006 27 / 27