›
›

Bài giảng Toán rời rạc - Chương 1: Cơ sở logic

pdf 69 trang hapham 330
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương 1: Cơ sở logic", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_roi_rac_chuong_1_co_so_logic.pdf

Nội dung text: Bài giảng Toán rời rạc - Chương 1: Cơ sở logic

  1. Giới thiệu TOÁN RỜI RẠC lvluyen@hcmus.edu.vn ∼luyen/trr FB: fb.com/trr2015 Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 1
  2. Tài liệu 1 Giáo trình: Nguyễn Hữu Anh, Toán Rời Rạc, Nhà Xuất Bản Lao Động 2001 2 Tham khảo thêm: Kenneth H. Rosen, Discrete mathematics and its applications, Seventh Edition, 2011 Thang điểm đánh giá - Giữa kỳ 30% (thi vào ngày 1 tháng 12) - Thi cuối kỳ 70% Lưu ý. Trong quá trình học, một số bạn sẽ được gọi lên bảng làm bài. Tùy theo bài làm mà có được xem xét cộng thêm điểm vào điểm giữa kỳ hay không. lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 2
  3. Nội quy - Lớp không điểm danh nhưng đã đi học thì không được đi trể - Chuyển điện thoại sang chế độ im lặng và không sử dụng điện thoại trong lớp - Đi học phải có giấy và viết lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 3
  4. TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Nội dung môn học gồm 6 chương 1. Cơ sở logic 2. Tập hợp và ánh xạ 3. Phép đếm và hệ thức đệ quy 4. Tập hợp số nguyên 5. Quan hệ 6. Hàm Boole lvluyen@hcmus.edu.vn Toán Rời Rạc 13/10/2015 Trang 4
  5. TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Chương 1 CƠ SỞ LOGIC lvluyen@hcmus.edu.vn ∼luyen/trr FB: fb.com/trr2015 Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 5
  6. Nội dung Chương 1. CƠ SỞ LOGIC 1. Mệnh đề 2. Dạng mệnh đề 3. Vị từ, lượng từ 4. Quy tắc suy luận 5. Nguyên lý quy nạp lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 6
  7. 1.1. Mệnh đề 1 Định nghĩa và chân trị của mệnh đề 2 Phân loại mệnh đề 3 Các phép toán trên mệnh đề lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 7
  8. 1.1.1. Định nghĩa và chân trị của mệnh đề Định nghĩa. Mệnh đề là một phát biểu có giá trị chân lý xác định, đúng hoặc sai. Nhận xét. Câu hỏi, câu cảm thán, mệnh lệnh không là mệnh đề. Ví dụ. Phát biểu nào sau đây là mệnh đề a) Mặt trời quay quanh trái đất b) 1 + 1 = 2 c) Hôm nay trời đẹp quá! (không là mệnh đề) d) Học bài đi! (không là mệnh đề) e) 3 là số lẻ phải không? (không là mệnh đề) Chúng ta dùng các ký hiệu P, Q, R, . . . để chỉ mệnh đề. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 8
  9. Chân trị của mệnh đề Một mệnh đề chỉ có thể đúng hoặc sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngược lại ta nói P có chân trị sai. 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 ) Ví dụ. Kiểm tra các phát biểu sau có phải là mệnh đề không? Nếu có, hãy xác định chân trị. a) Paris là thành phố của Mỹ. b) n là số tự nhiên. c) Con nhà ai mà xinh thế! d) 3 là số nguyên tố. e) Toán rời rạc là môn bắt buộc của ngành Tin học. f) Bạn có khỏe không? g) x2 + 1 luôn dương. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 9
  10. 1.1.2. Phân loại mệnh đề Mệnh đề gồm 2 loại: 1 Mệnh đề phức hợp: là mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết bằng các liên từ (và, hay, khi và chỉ khi, ) hoặc trạng từ “không”. 2 Mệnh đề sơ cấp (nguyên thủy): Là mệnh đề không thể xây dựng từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không”. Ví dụ. Phân loại các mệnh đề sau: a) 2 không là số nguyên tố b) 2 là số nguyên tố c) Nếu 3 > 4 thì trời mưa d) An đang xem phim hay An đang học bài e) Hôm nay trời đẹp và 1 + 1 = 3 lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 10
  11. 1.1.3. Các phép toán trên mệnh đề a. Phép phủ định Phủ định của mệnh đề P được ký hiệu là ¬P hay P (đọc là “không” P hay “phủ định của” P ), là mệnh đề được định bởi: ¬P đúng ⇔ P sai. Bảng chân trị : P ¬P 1 0 0 1 Ví dụ. 1 P =“2 là số nguyên tố”⇒ ¬P = “2 không là số nguyên tố” 2 Q =“1 > 2”⇒ ¬Q= “1 ≤ 2” lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 11
  12. b. Phép nối liền (hội, giao) Phép nối liền của hai mệnh đề P và Q được kí hiệu bởi P ∧ Q (đọc là “P và Q”), là mệnh đề được định bởi: P ∧ Q đúng ⇔ P và Q đồng thời đúng. Bảng chân trị : P Q P ∧ Q 0 0 0 0 1 0 1 0 0 1 1 1 Ví dụ. Xác định chân trị của các mệnh đề sau: a) 3 > 4 và Trần Hưng Đạo là vị tướng b) 2 là số nguyên tố và là số chẵn c) An đang hát và uống nước lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 12
  13. c. Phép nối rời (tuyển, hợp) Phép nối rời của hai mệnh đề P và Q được kí hiệu bởi P ∨ Q (đọc là “P hay Q”), là mệnh đề được định bởi: P ∨ Q sai ⇔ P và Q đồng thời sai. Bảng chân trị : P Q P ∨ Q 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ. Xác định chân trị của các mệnh đề sau: a) 3 > 4 hay Paris là thủ đô của Anh b) Mặt trời mọc ở hướng Đông hay 1 + 3 = 5 c) π > 4 hay trời không mưa d) 2 là số nguyên tố hay là số chẵn lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 13
  14. d. Phép kéo theo Mệnh đề P kéo theo Q của hai mệnh đề P và Q, kí hiệu 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 ”) là mệnh đề được định bởi: P → Q sai ⇔ P đúng và Q sai. Bảng chân trị: P Q P → Q 0 0 1 0 1 1 1 0 0 1 1 1 lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 14
  15. Ví dụ. Xác định chân trị của các mệnh đề sau: a) Nếu 1 = 2 thì tôi là người Việt Nam b) Nếu trái đất quay quanh mặt trời thì 1 + 3 = 5 c) π < 4 kéo theo 5 < 6 d) Nếu 2 + 1 = 0 thì tôi là chủ tịch nước e. Phép kéo theo hai chiều Mệnh đề P kéo theo Q và ngược lại của hai mệnh đề P và Q, 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 Q”) là mệnh đề được định bởi: P ↔ Q đúng ⇔ P và Q có cùng chân trị. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 15
  16. Bảng chân trị : P Q P ↔ Q 0 0 1 0 1 0 1 0 0 1 1 1 Ví dụ. Xác định chân trị của các mệnh đề sau: a) 2 = 4 khi và chỉ khi 2 + 1 = 0 b) 6 chia hết cho 3 khi và chi khi 6 chia hết cho 2 c) London là một thành phố nước Anh nếu và chỉ nếu thành phố HCM là thủ đô của VN d) π > 4 là điều kiện cần và đủ của 5 < 6 lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 16
  17. 1.2. Dạng mệnh đề 1 Định nghĩa và chân trị của dạng mệnh đề 2 Sự tương đương logic 3 Các luật logic lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 17
  18. 1.2.1. Định nghĩa và chân trị của dạng mệnh đề Định nghĩa. Dạng mệnh đề là một biểu thức được cấu tạo từ: - Các mệnh đề (các hằng mệnh đề 0, 1) - Các biến mệnh đề p, q, r, . . . , tức là các biến lấy giá trị là các mệnh đề nào đó - Các phép toán ¬, ∧, ∨, →, ↔ và dấu đóng mở ngoặc (). Ví dụ. a) E(p, q) = ¬(¬p ∨ q) ∨ 1 b) F (p, q, r) = (p → q) ∨ ¬(q ∨ r) Định nghĩa. Bảng chân trị của dạng mệnh đề E(p, q, r) là bảng ghi tất cả các trường hợp chân trị có thể xảy ra đối với dạng mệnh đề E theo chân trị của các biến mệnh đề p, q, r. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 18
  19. Ví dụ. Cho p, q, r là biến mệnh đề. Lập bảng chân trị của dạng mệnh đề sau E(p, q, r) = (p ∨ q) → r. Giải. p q r p ∨ q (p ∨ q) → r 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 Nhận xét. Nếu có n biến, bảng này sẽ có 2n dòng, chưa kể dòng tiêu đề. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 19
  20. Độ ưu tiên các phép toán mệnh đề trong dạng mệnh đề Thứ tự ưu tiên lần như sau mức 1: ¬ mức 2: ∧, ∨ mức 3: →, ↔ Các phép toán trên cùng mức có cùng độ ưu tiên. Ví dụ. a) ¬p ∨ q → r ∨ s có nghĩa là ((¬p) ∨ q) → (r ∨ s). b) ¬p ∧ q ∨ r là nhập nhằng. Ta cần phải dùng các dấu ngoặc để chỉ rõ nghĩa. Ví dụ.(tự làm) Lập bảng chân trị của các dạng mệnh đề sau: a) A(p, q) = ¬(p ∧ q) ∧ p b) B(p, q, r) = p ∧ (q ∨ r) ↔ ¬q lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 20
  21. Định nghĩa. Dạng mệnh đề được gọi là 1 hằng đúng nếu nó luôn lấy giá trị 1 2 hằng sai (hay mâu thuẫn) nếu nó luôn lấy giá trị 0. Ví dụ. Kiểm tra các dạng mệnh đề sau là hằng đúng hay hằng sai a) A(p) = ¬(¬p) ↔ p b) B(p, q) = (p ∧ q) ∧ (¬p ∨ ¬q) c) C(p, q) = p ∨ (p ∧ q) → ¬p d) D(p, q, r) = [p ∨ (p ∧ q)] ∧ ¬p → r e) E(p, q, r) = (p → q) ∨ ¬p → r lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 21
  22. Ví dụ. Gọi P, Q, R là các mệnh đề: P := “Bình đang học Toán” Q := “Bình đang học Tin học” R := “Bình đang học Anh văn” Hãy viết lại các mệnh đề dưới đây dưới dạng hình thức trong đó sử dụng các phép toán a) Bình đang học Toán và Anh văn nhưng không học Tin học b) Bình đang học Toán và Tin học nhưng không học cùng một lúc Tin học và Anh văn c) Không đúng là Bình đang học Anh văn mà không học Toán d) Không đúng là Bình đang học Anh văn hay Tin học mà không học Toán e) Bình không học Tin học lẫn Anh văn nhưng đang học Toán lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 22
  23. Ví dụ. Gọi P, Q, R là các mệnh đề sau: P =“ABC là tam giác cân” Q=“ABC là tam giác đều” R := “Tam giác ABC có ba góc bằng nhau” Hãy viết các mệnh đề sau theo ngôn ngữ thông thường a) Q → P b) ¬P → Q c) P ∧ ¬Q d) R → P lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 23
  24. 1.2.2. Tương đương logic Định nghĩa. Hai dạng mệnh đề E và F được gọi là tương đương logic nếu chúng có cùng bảng chân trị. Ký hiệu. E ⇔ F (hay E ≡ F ). Ví dụ. ¬(p ∨ q) ⇔ ¬p ∧ ¬q Ví dụ. Chứng minh các tương đương logic sau 1 ¬(¬p) ⇔ p 2 p ∨ p ⇔ p 3 p ∨ (p ∧ q) ⇔ p 4 p → q ⇔ ¬p ∨ q 5 p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) Mệnh đề. Hai dạng mệnh đề E và F tương đương logic khi và chỉ khi E ↔ F là một hằng đúng. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 24
  25. Định nghĩa. Dạng mệnh đề F được nói là hệ quả logic của dạng mệnh đề E nếu E → F là một hằng đúng. Khi đó ta viết E ⇒ F. Ví dụ. Xét dạng mệnh đề (p → q) ∧ ¬q → ¬p. Ta chứng minh được đây là dạng mệnh đề hằng đúng. Suy ra ¬p là hệ quả logic của (p → q) ∧ ¬q. Hay được viết dưới dạng (p → q) ∧ ¬q ⇒ ¬p. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 25
  26. Các quy tắc thay thế Qui tắc 1 Trong dạng mệnh đề E, nếu ta thay thế biểu thức con F bởi một dạng mệnh đề tương đương logic thì dạng mệnh đề thu được vẫn còn tương đương logic với E. Ví dụ. ¬(¬p) → r ⇔ p → r ¬(p ∨ q) ∧ r ⇔ (¬p ∧ ¬q) ∧ r Qui tắc 2 Giả sử dạng mệnh đề E là hằng đúng, nếu ta thay thế một biến p bằng một dạng mệnh đề nào đó thì mệnh đề có được vẫn là hằng đúng. Ví dụ. Ta biết E(p) = ¬p ∨ p là hằng đúng. Do đó ¬(q → r) ∨ (q → r) vẫn là hằng đúng lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 26
  27. 1.2.3. Các luật logic 1. Phủ định của phủ định ¬¬p ⇔ p 2. Luật De Morgan ¬(p ∧ q) ⇔ ¬p ∨ ¬q ¬(p ∨ q) ⇔ ¬p ∧ ¬q 3. Luật giao hoán p ∨ q ⇔ q ∨ p p ∧ q ⇔ q ∧ p 4. Luật kết hợp (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r) 5. Luật phân phối p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 27
  28. 6. Luật lũy đẳng p ∨ p ⇔ p p ∧ p ⇔ p 7. Luật trung hòa p ∨ 0 ⇔ p p ∧ 1 ⇔ p 8. Luật về phần tử bù p ∧ ¬p ⇔ 0 p ∨ ¬p ⇔ 1 9. Luật thống trị p ∧ 0 ⇔ 0 p ∨ 1 ⇔ 1 10. Luật hấp thụ p ∨ (p ∧ q) ⇔ p p ∧ (p ∨ q) ⇔ p lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 28
  29. 11. Luật về phép kéo theo p → q ⇔ ¬p ∨ q ⇔ ¬q → ¬p Nhận xét. ¬(p → q) ⇔ p ∧ ¬q. Ví dụ. Cho p, q là các biến mệnh đề. Hãy dùng các luật logic chứng minh [(p → q) ∧ p] → q là hằng đúng. Giải. Ta có [(p → q) ∧ p] → q ⇔ ¬[(p → q) ∧ p] ∨ q ⇔ [¬(p → q) ∨ ¬p] ∨ q ⇔ ¬(p → q) ∨ (¬p ∨ q) ⇔ ¬(p → q) ∨ (p → q) ⇔ 1 Ví dụ.(tự làm) Cho p, q là các biến mệnh đề. Chứng minh rằng p → (p ∨ q) là hằng đúng lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 29
  30. Ví dụ. Cho p, q, r là các biến mệnh đề. Chứng minh rằng: (¬p → r) ∧ (q → r) ⇔ (p → q) → r Giải. Ta có (¬p → r) ∧ (q → r) ⇔ (p ∨ r) ∧ (¬q ∨ r)(luật về phép kéo theo) ⇔ (p ∧ ¬q) ∨ r (luật phân phối) ⇔ ¬(¬p ∨ q) ∨ r (luật phủ định) ⇔ ¬(p → q) ∨ r (luật về phép kéo theo) ⇔ (p → q) → r (luật về phép kéo theo) Ví dụ.(tự làm) Cho p, q, r là các biến mệnh đề. Chứng minh rằng (p → q) ∧ [¬q ∧ (q → r)] ⇔ ¬q ∧ ¬p lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 30
  31. Ví dụ. Phủ định các mệnh đề sau a) Ngày mai nếu trời mưa hay trời lạnh thì tôi sẽ không ra ngoài b) 15 chia hết cho 3 nhưng không chia hết cho 4 c) Hình tứ giác này không phải là hình chữ nhật mà cũng không phải là hình thoi d) Nếu An không đi làm ngày mai thì sẽ bị đuổi việc Ví dụ.(tự làm) Cho 3 biến mệnh đề x, y và z. Đặt A = [(x ∨ y) → (x ∨ z)],B = [¬x → (y → z)]. a) Chứng minh A ⇔ B. b) Nếu y sai thì chân trị của A ra sao ? lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 31
  32. 1.3. Vị từ và lượng từ 1 Định nghĩa 2 Các phép toán trên vị từ 3 Mệnh đề lượng từ hóa vị từ 4 Phủ định mệnh đề lượng từ hóa vị từ 5 Các quy tắc phổ dụng lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 32
  33. 1.3.1. Định nghĩa Nhắc lại. Tập hợp là một khái niệm cơ bản của Toán học, dùng để chỉ một nhóm các đối tượng nào đó. Ký hiệu. A, B, X, . . . Nếu x là phần tử của tập hợp A, ta kí hiệu x ∈ A, ngược lại ta ký hiệu x∈ / A. Ví dụ. 1 N = {0, 1, 2, } là tập hợp các số tự nhiên. 2 Z = {0, 1, −1, 2, −2, } tập hợp các số nguyên. m 3 = | m, n ∈ , n 6= 0 tập hợp các số hữu tỉ. Q n Z 4 R: Tập hợp các số thực. 5 C: Tập hợp các số phức. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 33
  34. Định nghĩa. Vị từ là một phát biểu p(x, y, ), trong đó x, y, . . . là các biến thuộc tập hợp A, B, . . . cho trước sao cho: - Bản thân p(x, y, . . .) không phải là mệnh đề. - Nếu thay x, y, . . . thành giá trị cụ thể thì p(x, y, . . .) là mệnh đề. Ví dụ. 1 r(x, y, z) = “x2 + y2 > z”. 2 q(x, y) = “x2 + y = 1”. 3 p(n) = “n + 1 là số nguyên tố”. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 34
  35. 1.3.2. Các phép toán trên vị từ Cho trước các vị từ p(x), q(x) theo một biến x ∈ A. Khi ấy, ta cũng có các phép toán tương ứng như trên mệnh đề - Phủ định ¬p(x) - Phép nối liền p(x) ∧ q(x) - Phép nối rời p(x) ∨ q(x) - Phép kéo theo p(x) → q(x) - Phép kéo theo hai chiều p(x) ↔ q(x) Ví dụ. 1 ¬(x2 > 1) 2 (x2 + 3 > 1) ∧ (2x − 1 1 thì x > 5 lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 35
  36. Các trường hợp của vị từ Khi xét một vị từ p(x) với x ∈ A. Ta có các trường hợp sau: TH 1. Khi thay x bởi một phần tử a tùy ý thuộc A, ta có p(a) đúng. TH 2. Với một số giá trị a thuộc A, ta có p(a) đúng. TH 3. Khi thay x bởi một phần tử a tùy ý thuộc A, ta có p(a) sai. Ví dụ. Với x ∈ R, các vị từ sau thuộc trường hợp nào 1 q(x) = “x2 − 2x + 1 = 0” 2 r(x) = “x2 + 3 = 0” 3 p(x) = “x2 + 1 > 0” lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 36
  37. 1.3.3. Mệnh đề lượng từ hóa vị từ Định nghĩa. Cho p(x) là một vị từ theo một biến xác định trên A. Ta định nghĩa các mệnh đề lượng từ hóa của p(x) như sau: Mệnh đề “Với mọi x thuộc A sao cho p(x) ”, kí hiệu bởi “∀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. - Mệnh đề “Tồn tại một x thuộc A sao cho p(x)” kí hiệu bởi : “∃x ∈ A, p(x)”, là mệnh đề đúng khi và chỉ khi có ít nhất một giá trị x = a0 nào đó sao cho mệnh đề p(a0) đúng. Lưu ý. Từ "tồn tại" có thể được thay thế bởi “có” hay “có ít nhất". lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 37
  38. Ví dụ. Các mệnh đề sau đúng hay sai a) “∀x ∈ R, x + 1 > 0” b) “∃x ∈ R, x + 1 > 0” 2 c) “∀x ∈ R, x + 1 > 5” 2 d) “∃x ∈ R, x + 1 > 5” e) “∀n ∈ Z, 2n + 1 lẻ” f) “∃n ∈ Z, 3n + 1 chẵn” lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 38
  39. Định nghĩa. Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A × B. Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau: (i) “∀x ∈ A, ∀y ∈ B, p(x, y)” := “∀x ∈ A, (∀y ∈ B, p(x, y))” (ii) “∀x ∈ A, ∃y ∈ B, p(x, y)” := “∀x ∈ A, (∃y ∈ B, p(x, y))” (iii) “∃x ∈ A, ∀y ∈ B, p(x, y)” := “∃x ∈ A, (∀y ∈ B, p(x, y))” (iv) “∃x ∈ A, ∃y ∈ B, p(x, y)” := “∃x ∈ A, (∃y ∈ B, p(x, y))” Ví dụ. Mệnh đề “∀x ∈ R, ∀y ∈ R, x + 2y < 1” đúng hay sai? Giải. Mệnh đề sai vì tồn tại x0 = 0, y0 = 1 ∈ R mà x0 + 2y0 = 1. Ví dụ. Mệnh đề “∀x ∈ R, ∃y ∈ R, x + 2y < 1” đúng hay sai? Giải. Mệnh đề đúng vì với mỗi x = a ∈ R, tồn tại ya ∈ R như ya = −a/2, sao cho a + 2ya < 1. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 39
  40. Định lý. Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A × B. Khi đó: i) “∀x ∈ A, ∀y ∈ B, p(x, y)” ⇔ “∀y ∈ B, ∀x ∈ A, p(x, y)” ii) “∃x ∈ A, ∃y ∈ B, p(x, y)” ⇔ “∃y ∈ B, ∃x ∈ A, p(x, y)” iii) “∃x ∈ A, ∀y ∈ B, p(x, y)‘ ⇒ “∀y ∈ B, ∃x ∈ A, p(x, y)” Chiều đảo của 3) nói chung không đúng. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 40
  41. 1.3.4. Phủ định của mệnh đề lượng từ hóa vị từ Phủ định của mệnh đề lượng từ hóa vị từ p(x, y, ) có được bằng các thay ∀ thành ∃ , thay ∃ thành ∀ và vị từ p(x, y, ) thành ¬p(x, y, ). Ví dụ. Phủ định các mệnh đề sau a) ∀x ∈ A, 2x + 1 > 0 2 b) ∃x ∈ N, ∀y ∈ R, (x + y > 1) → (x 0, ∃δ > 0, ∀x ∈ R, |x − a| 1) ∧ (x ≥ y) c) ∃ε > 0, ∀δ > 0, ∃x ∈ R, |x − a| ≥ δ ∨ |f(x) − f(a)| ≥ ε lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 41
  42. Ví dụ.(tự làm) Phủ định các mệnh đề sau 2 2 2 a) ∃x ∈ R, ∀y ∈ R, (x > y) ∨ (x − 1 > y) → (x ≥ y ) b) ∃x ∈ Z, ∃y ∈ Z, (2x + y = 5) và (x − 3y = −1) Ví dụ.(tự làm) Phủ định các mệnh đề sau 1 Có ít nhất một số nguyên chẵn 2 Ai cũng có ít nhất một người bạn thân Ví dụ.(tự làm) Cho C = “∀x ∈ R, ∃y ∈ Z, y 6= x và |y − x| ≤ 1”. Viết mệnh đề phủ định C. Ví dụ.(tự làm) Cho C = “∃x ∈ R, ∃y ∈ Z, 2x + y > 5 và 5y − x = 1”. C đúng hay sai ? Tại sao ? Viết mệnh đề phủ định C. 2 −x Ví dụ.(tự làm) Cho C = “∃x ∈ R, ∀y ∈ Z, 8y − 2y ≤ 3 ”. Xét chân trị của C và viết mệnh đề phủ định C của C. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 42
  43. 2 x Ví dụ.(tự làm) Cho A = “∀x ∈ R, ∃y ∈ Z, y + 6y > 3 ”. Viết mệnh đề phủ định A của A và xét chân trị của A. Ví dụ.(tự làm) Cho mệnh đề 2 2 A = “∃x ∈ R, ∀y ∈ R, (x ≥ y ) → (x ≥ y và xy ≤ 0)”. Viết mệnh đề phủ định của A. 2 Ví dụ.(tự làm) Cho C = “∃x ∈ R, ∀y ∈ R, sin y − cos y ≤ 1 − x ”. Xét chân trị của C và viết mệnh đề phủ định của C. Ví dụ.(tự làm) Cho A = “Nếu Tuấn thắng trận chung kết thì tất cả các bạn trong lớp đến chúc mừng". Hãy viết mệnh đề phủ định của A. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 43
  44. 1.3.5. Các quy tắc phổ dụng Đặc biệt hóa phổ dụng ∀x ∈ A, p(x) a ∈ A ∴ p(a) Ví dụ. “Mọi người đều chết“ “Socrate là người“ Vậy “Socrate cũng chết“ Tổng quát hóa phổ dụng Nếu với mỗi a ∈ X ta có p(a) là mệnh đề đúng thì khẳng định “∀x ∈ X, p(x)” là mệnh đề đúng. Ví dụ. Mỗi số thực đều có bình phương không âm nên mọi số thực đều có bình phương không âm. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 44
  45. 1.4. Quy tắc suy luận 1 Các quy tắc suy luận 2 Các phương pháp chứng minh lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 45
  46. Giới thiệu Ví dụ. Xem xét suy luận sau: - Nếu nghệ sĩ Văn Ba không trình diễn hay số vé bán ra ít hơn 50 thì đêm diễn sẽ bị hủy bỏ và ông bầu rất buồn. - Nếu đêm biểu diễn bị hủy bỏ thì phải trả lại tiền vé cho người xem. - Nhưng tiền vé đã không được trả lại cho người xem. Vậy nghệ sĩ Văn Ba có trình diễn. Hỏi Suy luận trên đúng hay sai? Ví dụ. Xem xét suy luận sau: Ông Minh nói rằng nếu không được tăng lương thì ông ta sẽ nghỉ việc. Mặt khác, nếu ông ấy nghỉ việc và vợ ông ấy bị mất việc thì phải bán xe. Biết rằng nếu vợ ông Minh hay đi làm trễ thì trước sau gì cũng sẽ bị mất việc. Và cuối cùng ông Minh đã được tăng lương. Suy ra, nếu ông Minh không bán xe thì vợ ông ta đã không đi làm trễ Hỏi Suy luận trên đúng hay sai? lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 46
  47. 1.4.1. Các quy tắc suy luận Trong các chứng minh toán học, xuất phát từ một số khẳng định đúng p, q, r, . . . (tiền đề), ta áp dụng các qui tắc suy luận để suy ra chân lí của một mệnh đề h mà ta gọi là kết luận. Nói cách khác, dùng các qui tắc suy luận để chứng minh: (p ∧ q ∧ r ∧ ) có hệ quả logic là h. Ta thường mô hình hóa phép suy luận đó dưới dạng: p q r ∴ h Viết dưới dạng hằng đúng: (p ∧ q ∧ r ∧ ) → h lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 47
  48. a. Qui tắc khẳng định (Modus Ponens) Sơ đồ p → q p ∴ q Thể hiện bằng hằng đúng ((p → q) ∧ p) → q Ví dụ. - Trời mưa thì đường ướt. - Mà chiều nay trời mưa. Suy ra: Chiều nay đường ướt. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 48
  49. b. Quy tắc phủ định Sơ đồ p → q ¬q ∴ ¬p Thể hiện bằng hằng đúng [(p → q) ∧ ¬q] → ¬p Ví dụ. - Nếu An đi học đầy đủ thì sẽ đậu môn Toán Rời Rạc. - An không đậu Toán Rời Rạc. Suy ra: An không đi học đầy đủ. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 49
  50. c. Quy tắc tam đoạn luận Sơ đồ p → q q → r ∴ p → r Thể hiện bằng hằng đúng [(p → q) ∧ (q → r)] → (p → r) Ví dụ. - Nếu trời mưa thì đường ướt - Nếu đường ướt thì đường trơn Suy ra: Nếu trời mưa thì đường trơn Ví dụ. Xem xét suy luận sau đúng hay sai? - Một con ngựa rẻ là một con ngựa hiếm - Cái gì hiếm thì đắt Suy ra: Một con ngựa rẻ thì đắt lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 50
  51. d. Quy tắc tam đoạn luận rời Sơ đồ p ∨ q ¬p ∴ q Thể hiện bằng hằng đúng [(p ∨ q) ∧ ¬p] → q Ví dụ. - Tối nay An sẽ đi uống cafe với bạn hoặc ở nhà học bài - Tối nay An không học bài ở nhà Suy ra: Tối nay, An đi uống cafe với bạn lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 51
  52. e. Những quy tắc suy luận đơn giản Quy tắc Sơ đồ Hằng đúng p q Nối liền (p ∧ q) → (p ∧ q) ∴ p ∧ q p ∧ q Đơn giản (p ∧ q) → p ∴ p p Cộng p → (p ∨ q) ∴ p ∨ q lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 52
  53. Ví dụ. Xem xét suy luận sau: - Nếu nghệ sĩ Văn Ba không trình diễn hay số vé bán ra ít hơn 50 thì đêm diễn sẽ bị hủy bỏ và ông bầu rất buồn. - Nếu đêm biểu diễn bị hủy bỏ thì phải trả lại tiền vé cho người xem. - Nhưng tiền vé đã không được trả lại cho người xem. Vậy nghệ sĩ Văn Ba có trình diễn. Hỏi Suy luận trên đúng hay sai? Nếu ta đặt: Ta có sơ đồ suy luận sau: p: “nghệ sĩ Văn Ba đã trình diễn” (¬p ∨ q) → (r ∧ s) q: “số vé bán ra ít hơn 50” r → t r: “đêm diễn sẽ bị hủy bỏ” ¬t t: “trả lại tiền vé cho người xem” ∴ p s: “ông bầu rất buồn” lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 53
  54. Ví dụ. Chứng minh suy luận sau p → (q → r) p ∨ s t → q ¬s ∴ ¬r → ¬t Giải. p ∨ s p → (q → r) t → q ¬s p q → r ∴ p ∴ q → r ∴ t → r Tam đoạn luận rời Khẳng định Tam đoạn luận Cuối cùng ta có t → r ⇔ ¬r → ¬t (Luật phép kéo theo) lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 54
  55. Ví dụ.(tự làm) Chứng minh các suy luận sau: t → u p ∧ q r → (s ∨ t) p → q p → (q → r) p → (r ∧ q) (¬p ∨ q) → r ¬q ¬q → ¬p ¬(s ∨ u) r → (s ∨ t) ¬r p ∴ p ¬s ∴ ¬(p ∨ r) ∴ r ∴ t lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 55
  56. f. Quy tắc mâu thuẫn Ta có tương đương logic [(p1 ∧ p2 ∧ ∧ pn) → q] ⇔ [(p1 ∧ p2 ∧ ∧ pn ∧ ¬q) → 0]. Do đó nếu chứng minh được dạng mệnh đề ở bên phải là một hằng đúng thì dạng mệnh đề ở bên trái cũng là một hằng đúng. Nói cách khác nếu thêm giả thiết phụ ¬p vào các tiền đề cho trước mà dẫn đến một mâu thuẫn thì q là hệ quả logic của các tiền đề cho trước. Ví dụ. Chứng minh suy luận sau p → r ¬p → q q → s ∴ ¬r → s lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 56
  57. Giải. Phủ định kết luận ¬(¬r → s) ⇔ ¬(r ∨ s) ⇔ ¬r ∧ ¬s Ta thêm điều này vào tiền đề. Khi đó ta sẽ chứng minh suy luận sau: p → r ¬p → q q → s ¬r ∧ ¬s ∴ 0 Ta lần lược thực hiện các quy tắc suy luận sau: p → r q → s ¬p → q ¬q ¬r ∧ ¬s ¬r ¬r ∧ ¬s ¬s ¬p q ∴ ¬r ∴ ¬p ∴ ¬s ∴ ¬q ∴ q ∴ 0 Như vậy suy luận trên đã được chứng minh lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 57
  58. Ví dụ. Xem suy luận sau đúng hay sai? Ông Minh nói rằng nếu không được tăng lương thì ông ta sẽ nghỉ việc. Mặt khác, nếu ông ấy nghỉ việc và vợ ông ấy bị mất việc thì phải bán xe. Biết rằng nếu vợ ông Minh hay đi làm trễ thì trước sau gì cũng sẽ bị mất việc. Và cuối cùng ông Minh đã được tăng lương. Suy ra, nếu ông Minh không bán xe thì vợ ông ta đã không đi làm trễ. Nếu ta đặt: Ta có sơ đồ suy luận sau: p: “ông Minh được tăng lương” ¬p → q q: “ông Minh nghỉ việc” (q ∧ r) → s r: “vợ ông Minh mất việc” t → r s: “gia đình phải bán xe” p t: “vợ ông hay đi làm trể” ∴ ¬s → ¬t lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 58
  59. Phản ví dụ B Để chứng minh suy luận đúng, chúng ta sẽ sử dụng các luật logic và quy tắc suy luận. B Để chỉ một suy luận sai (hay còn gọi là ngụy biện) ta sẽ đưa giá các giá trị làm cho các tiền đề đúng nhưng kết luận thì sai. Ví dụ. Kiểm tra suy luận sau đúng hay sai ¬p → q (q ∧ r) → s t → r p ∴ ¬s → ¬t Giải. Cho s = 0, t = 1, p = 1, q = 0, r = 1, ta thấy các tiền đề đều đúng, nhưng kết luận sai. Suy ra suy luận trên là sai. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 59
  60. 1.4.2. Các phương pháp chứng minh Mỗi bài toán chứng minh gồm 2 phần chính: giả thiết và kết luận. Quá trình chứng minh bài toán là quá trình sử dụng các tiên đề, luật logic, các quy tắc suy luận, và áp dụng các phương pháp chứng minh để từ giả thiết đã cho ta có được kết luận. Trong phần này ta tìm hiểu các phương pháp chứng minh sau: 1 Chứng minh trực tiếp 2 Chứng minh gián tiếp 3 Chứng minh phản chứng 4 Chứng minh theo từng trường hợp lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 60
  61. a. Chứng minh trực tiếp Để chứng minh A suy ra B, chúng ta giả sử A đúng, sau đó áp dụng các quy tắc suy luận, các luật logic, các tiên đề, để chỉ ra B đúng. Ví dụ. Chứng minh rằng, nếu n là một số lẻ thì n2 cũng là số lẻ. Giải. Vì n là số lẻ nên n = 2k + 1 với k ∈ Z. Ta có n2 = (2k + 1)2 = 4k2 + 4k + 1. Do 4k2 + 4k chẵn nên n2 là số lẻ. Ví dụ.(tự làm) Cho ABC là tam giác và M là trung điểm của BC. Chứng minh rằng nếu AM = MB thì tam giác ABC vuông tại A. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 61
  62. b. Chứng minh gián tiếp Ta có A → B ⇔ ¬B → ¬A. Do đó để chứng minh A đúng suy ra B đúng, ta có thể giả sử B sai và chứng minh A sai. Ví dụ. Cho n là một số nguyên, nếu 5n là số lẻ thì n là số lẻ Giải. Ta sẽ dùng phương pháp chứng minh gián tiếp. Nghĩa là, cho n là số chẵn cần chứng minh 5n là số chẵn. Vì n là số chẵn nên n = 2k (với k ∈ Z). Do đó 5n = 5.2k = 10k là một số chẵn. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 62
  63. c. Chứng minh phản chứng Ta có A → B ⇔ ¬A ∨ B. Suy ra ¬(A → B) ⇔ A ∧ ¬B. Như vậy để chứng minh từ A đúng suy ra B đúng, ta có thể giả sử B sai. Sau đó dùng các tiền đề, các luật logic, các quy tắc suy luận, chứng tỏ điều này mâu thuẫn. √ Ví dụ. Chứng minh rằng 2 là số vô tỉ. √ √ Giải. Giả sử 2 là số hữu tỉ, nghĩa là 2 có thể biểu diễn thành √ m 2 = (m, n ∈ ). n Z Ta có thể giả sử m, n là hai số nguyên tố cùng nhau. Bình phương 2 vế ta có m2 2 = ⇔ m2 = 2n2. n2 lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 63
  64. m2 2 = ⇔ m2 = 2n2. n2 Từ đây suy ra m là số chẵn (vì bình phương số lẻ là số lẻ). Do đó m = 2k (với k ∈ Z). Ta có (2k)2 = 2n2 ⇔ 4k2 = 2n2. Suy ra n2 = 2k2. Như vậy n cũng là một số chẵn. Do m, n đều là số chẵn nên chúng không là số nguyên tố cùng nhau (mâu thuẫn) Ví dụ.(tự làm) Trong mặt phẳng, nếu hai đường thẳng cùng song song với đường thẳng thứ ba thì chúng song song với nhau. Gợi ý. Sử dụng tiên đề Euclide: “Qua một điểm nằm ngoài một đường thẳng ta vẽ được một và chỉ một đường thẳng song song với đường thẳng đã cho." lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 64
  65. d. Chứng minh theo trường hợp Ta có (A ∨ B) → C ⇔ (A → C) ∧ (B → C) Do đó, để chứng minh (A ∨ B) → C ta chỉ cần chứng minh A → C và B → C là được. Ví dụ. Chứng minh rằng n3 + 2n luôn chia hết cho 3 với mọi số nguyên n. Giải. Chia hai trường hợp Trường hợp 1. n chia hết cho 3, hiển nhiên n3 + 2n chia hết cho 3. Trường hợp 2. n không chia hết cho 3, khi ấy ta có thể viết n = 3k ± 1 với k ∈ Z nào đó. Ta có n2 + 2 = (3k ± 1)2 + 2 = 9k2 ± 6k + 3 = 3(3k2 ± 2k + 1). Suy ra n(n2 + 2) cũng chia hết cho 3. Như vậy n3 + 2n chia hết cho 3 với mọi số nguyên n. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 65
  66. 1.5. Nguyên lý quy nạp Với những bài toán chứng minh tính đúng đắn của một biểu thức mệnh đề có chứa tham số n, như P (n). Quy nạp toán học là một kỹ thuật chứng minh P (n) đúng với mọi số n ≥ N0. Quy nạp yếu Gồm 2 bước: - Bước cơ sở: Chỉ ra P (N0) đúng. - Bước quy nạp: Chứng minh nếu P (k) đúng thì P (k + 1) đúng. Trong đó P (k) được gọi là giả thiết quy nạp. Ví dụ. Chứng minh 1 + 3 + ··· + (2n − 1) = n2 với mọi số nguyên dương n. Giải. Gọi P (n) = “1 + 3 + ··· + (2n − 1) = n2” - Bước cơ sở: Hiển nhiên P (1) đúng vì 1 = 12. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 66
  67. - Bước quy nạp: Giả sử P (k) đúng, tức là 1 + 3 + 5 + ··· + (2k − 1) = k2. Ta cần chứng minh P (k + 1) đúng, tức là 1 + 3 + 5 + ··· + (2k + 1) = (k + 1)2. Từ giả thiết quy nạp ta có 1 + 3 + 5 + ··· + (2k + 1) =1+3+5+ ··· + (2k − 1) + (2k + 1) = k2 + (2k + 1). = (k + 1)2. Suy ra, P (k + 1) đúng. Vậy theo nguyên lý quy nạp P (n) đúng với mọi số nguyên dương n. n(n + 1) Ví dụ.(tự làm) Chứng minh 1 + 2 + ··· + n = với mọi số 2 nguyên dương n. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 67
  68. Quy nạp mạnh Gồm 2 bước: - Bước cơ sở: Chỉ ra P (N0) ∧ P (N0 + 1) ∧ đúng. - Bước quy nạp mạnh: Chứng minh nếu P (m) đúng với mọi m ≤ k thì P (k + 1) đúng. Ví dụ. Mọi số tự nhiên lớn hơn 1 đều phân tích được thành tích những thừa số nguyên tố. Giải. Gọi P (n) = “n phân tích được thành tích những thừa số nguyên tố" - Bước cơ sở: Hiển nhiên P (2) đúng vì 2 = 2 là số nguyên tố. - Bước quy nạp mạnh: Giả sử P (m) đúng với mọi m ≤ k, tức là, với 1 < m ≤ k phân tích được thành tích những thừa số nguyên tố. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 68
  69. Ta cần chứng minh P (k + 1) đúng, tức là k + 1 phân tích được thành tích những thừa số nguyên tố. Nếu k + 1 là số nguyên tố thì P (k + 1) đúng, ngược lại, gọi p là một ước nguyên tố của k + 1. Nếu k + 1 là số nguyên tố. Khi đó k + 1 = p.t với 1 < p, t < k + 1. Vì p và t nhỏ hơn k + 1 nên theo giả thiết quy nạp p và t phân tích được thành tích những thừa số nguyên tố. Do đó k + 1 phân tích được thành tích những thừa số nguyên tố. Ví dụ.(tự làm) Chứng minh tích của ba số tự nhiên liên tiếp thì chia hết cho 6. lvluyen@hcmus.edu.vn Chương 1. Cơ sở logic 13/10/2015 Trang 69