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

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

1. Chương 1 CƠ SỞ LOGIC 1
2. Logic là gì? 2
3. Logic dùng để làm gì? 3
4. Mệnh đề là gì? 4
5. Mệnh đề là gì (tt)? 5
6. Đây không phải là mệnh đề 6
7. Các phát biểu sau có là mệnh đề không? 1. Thời tiết hôm nay thế nào? 2. x+y=y+x với mọi x,y thuộc R. 3. Sinh viên không thích học toán rời rạc. 4. I am lying on you. 5. Nếu Bình chơi võ lâm truyền kỳ nhiều quá thì Bình sẽ bị bạn gái bỏ. 6. Đường phố Sài gòn không bao giờ ngập lụt kể cả khi trời mưa rất to. 7
8. Một số quy ước 8
9. Các toán tử (phép toán) logic 9
10. Bảng chân trị của các toán tử logic 10
11. Diễn giải ngôn ngữ tự nhiên 11
12. Diễn giải ngôn ngữ tự nhiên (tt) 12
13. Biểu thức mệnh đề là gì? ⚫ Biểu thức mệnh đề (hay dạng mệnh đề) là sự kết hợp giữa các mệnh đề và các phép toán logic. ⚫ Ví dụ: 13
14. Bảng chân trị của biểu thức mệnh đề 14
15. Biểu thức mệnh đề (tt) 15
16. Biểu thức mệnh đề (tt) 16
17. Biểu thức mệnh đề (tt) 17
18. Biểu thức mệnh đề (tt) 18
19. Hai quy tắc thay thế Quy tắc thứ nhất: Quy tắc thứ hai: 19
20. Các luật logic 20
21. Các luật logic (tt) 21
22. Các luật logic (tt) 22
23. Suy luận (suy diễn) là gì? Mỗi quy tắc suy diễn là một hằng đúng! 23
24. Các quy tắc suy diễn Note: modus = "method of operating" 24
25. Các quy tắc suy diễn (tt) 25
26. Vị từ và lượng từ ⚫ Xét phát biểu sau: x>5. Ta thấy: ⚫ - Đó không là một mệnh đề. ⚫ - Phát biểu này gồm 2 phần: • x là một biến (chẳng hạn là biến thực). • “>5” là tính chất của x, được gọi là vị từ. 26
27. Lượng từ hóa vị từ ⚫ Trở lại ví dụ trên, “x>5” không phải là mệnh đề. Nhưng: • - 10>5 (thay x=10) là mệnh đề. • - “Tồn tại số thực x>5” là mệnh đề. • - “Mọi số thực x đều lớn hơn 5” là mệnh đề. ⚫ Các từ: “tồn tại” và “mọi” được gọi là các lượng từ, kí hiệu là: 27
28. Thứ tự của các lượng từ ⚫ Nếu là các lượng từ cùng loại thì không phân biệt thứ tự. ⚫ Ngược lại, nếu là các lượng từ khác loại thì cần chú ý đến thứ tự của chúng. 28
29. Ý nghĩa của lượng từ 29
30. Phủ định của lượng từ 30
31. Suy diễn trong logic vị từ 31
32. Nguyên lý quy nạp 32
33. Nguyên lý quy nạp ⚫ Ví dụ: chứng minh rằng ⚫ 1 + 3 + 5 + + (2k-1) = k2 (*) ⚫ Bước cơ sở: với k = 1 ta có 1 = 1 (*) đúng. ⚫ Bước quy nạp: Giả sử ⚫ 1 + 3 + + (2n-1) = n2 ⚫ ta sẽ chứng tỏ: ⚫ 1 + 3 + + (2n-1) + (2n+1) = (n+1)2 ⚫ Thật vậy, ta có ⚫ VT = n2 + (2n+1) = (n+1)2 = VP 33