Bài giảng Toán ứng dụng - Bài 1: Cơ sở logic

Nội dung text: Bài giảng Toán ứng dụng - Bài 1: Cơ sở logic

1. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: TRƯỜNG CAO ĐẲNG NGHỀ CÔNG NGHỆ THÔNG TIN MH/MĐ: TOÁN ỨNG DỤNG Tài liệu dạy và học TS. Võ Văn Tuấn Dũng, Giáo trình Toán rời rạc. Nhà xuất bản Lao động-Xã hội, 2009 Kenneth H. Rossen, Toán học rời rạc ứng dụng trong Tin học. Nhà xuất bản Giáo dục, 2007
2. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: KẾ HOẠCH BÀI GIẢNG THỜI GIAN (G) TÊN BÀI HỌC GHI CHÚ TỔNG LT TH STT 1 CƠ SỞ LÔGIC 5 3 2 2 BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI 10 6.5 3.5 Kiểm tra định kỳ lần 1 3 LÝ THUYẾT ĐỒ THỊ 7.5 5.5 2 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN 4 12.5 8.5 4 Kiểm tra định kỳ lần 2 TÌM KIẾM 5 CÂY VÀ CÁC ỨNG DỤNG 7.5 5.5 2 ÔN TẬP 2.5 1 1.5 TỔNG CỘNG 45 30 15 CƠ SỞ LOGIC
3. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: MÔN HỌC: TOÁN ỨNG DỤNG Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM Bài 5: CÂY VÀ CÁC ỨNG DỤNG CƠ SỞ LOGIC
4. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Bài 1: CƠ SỞ LOGIC 1. MỆNH ĐỀ 1.1 Khái niệm 1.2 Các phép toán trên mệnh đề 1.3 Mệnh đề phức hợp và tương đương logic 1.4 Độ ưu tiên của các phép tóan 2. CÁC QUI LUẬT LOGIC 2.1 Một số qui luật logic thường dùng 2.2 Ví dụ minh họa 3. SUY LUẬN TOÁN HỌC 3.1 Suy luận và chứng minh 3.2 Qui tắc suy diễn CƠ SỞ LOGIC
5. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.1. Khái niệm về mệnh đề: Mệnh đề toán học là khái niệm cơ bản của toán học không được định nghĩa mà chỉ được mô tả. Mệnh đề toán học (gọi tắt là mệnh đề) là một khẳng định có giá trị chân lý xác định (đúng hoặc sai, nhưng không thể vừa đúng vừa sai).  Chúng ta ký hiệu các mệnh đề bởi các chữ cái P, Q, R,  Chân trị của mệnh đề - 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, True) và 0(hay F, False) CƠ SỞ LOGIC
6. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ Ví dụ: “5 là số nguyên dương” là một mệnh đề đúng, “Số 123 chia hết cho 3” là một mệnh đề đúng “Paris là thủ đô của nước Anh” là một mệnh đề sai. “ Bạn có khỏe không ? ” không phải là một mệnh đề toán học vì đây là một câu hỏi không thể phản ánh một điều đúng hay một điều sai CƠ SỞ LOGIC
7. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.2. Các phép toán trên mệnh đề: Tên gọi Biểu tượng Phép phủ định ¬ Phép hội  Phép tuyển  Phép kéo theo Phép tương đương  CƠ SỞ LOGIC
8. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.2. Các phép toán trên mệnh đề: Phủ định của mệnh đề P được ký hiệu là P (đọc là "không phải P") là một mệnh đề có giá trị được xác định bởi bảng chân trị sau: P P (hoặc ) 1 0 0 1 Ví dụ: P : “An là người giỏi nhất lớp"  P : KHÔNG PHẢI "An là người giỏi nhất lớp” CƠ SỞ LOGIC
9. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.2. Các phép toán trên mệnh đề: Phép hội của hai mệnh đề P và Q được ký hiệu bởi P  Q (đọc là "P và Q") là một mệnh đề có giá trị được xác định bởi bảng chân trị sau: P Q P  Q 0 0 0 0 1 0 1 0 0 1 1 1 Ví dụ: P : “2 là số nguyên tố " Q : “2 là số chẵn" P  Q : "2 là số nguyên tố” và “2 là số chẵn" CƠ SỞ LOGIC
10. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.2. Các phép toán trên mệnh đề: Phép tuyển của hai mệnh đề P và Q được ký hiệu bởi P  Q (đọc là "P hoặc Q") là một mệnh đề có giá trị được xác định bởi bảng chân trị sau: P Q P  Q 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ: P : “An đang đọc báo " Q : “ An đang đá banh" P  Q : "An đọc báo" hoặc “An đang đá banh" CƠ SỞ LOGIC
11. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.2. Các phép toán trên mệnh đề: Mệnh đề P kéo theo mệnh đề Q được ký hiệu bởi P Q là một mệnh đề có giá trị được xác định bởi bảng chân trị sau: P Q P Q P: giả thuyết; Q: kết luận; 0 0 1 Cách đọc: 0 1 1 "P kéo theo Q" 1 0 0 "Nếu P thì Q" 1 1 1 "Q chỉ nếu P" Ví dụ: P : “chạch đẻ ngọn đa" Q : “ta lấy nàng" P Q : Nếu thì CƠ SỞ LOGIC
12. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.2. Các phép toán trên mệnh đề: Mệnh đề P tương đương mệnh đề Q được ký hiệu bởi P  Q là một mệnh đề có giá trị được xác định bởi (P Q)  (Q P) có bảng chân trị sau: P Q P  Q Cách đọc: "P nếu và chỉ nếu Q" 0 0 1 "Nếu P thì Q và ngược lại" 0 1 0 1 0 0 1 1 1 Ví dụ: P  Q: "Một số chia hết cho 3 khi và chỉ khi nó có tổng các chữ số chia hết cho 3" CƠ SỞ LOGIC
13. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.3. Mệnh đề phức hợp và tương đương logic: Định nghĩa 1: Mệnh đề được xây dựng từ một số mệnh đề ban đầu nhờ liên kết chúng lại bằng các phép toán logic (phủ định, hội, tuyển, kéo theo và tương đương) gọi là mệnh đề phức hợp hay công thức. Mệnh đề không được xây dựng từ các mệnh đề khác qua các phép toán logic gọi là mệnh đề sơ cấp. Định nghĩa 2: Hằng đúng hay định lý (đôi khi còn gọi là luật) là mệnh đề phức hợp luôn luôn có giá trị đúng. Hằng sai hay gọi là mâu thuẫn là mệnh đề phức hợp luôn có giá trị sai. CƠ SỞ LOGIC
14. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.3. Mệnh đề phức hợp và tương đương logic: Ví dụ: Mệnh đề phức hợp (P Q)  (P  Q) là một hằng đúng (hay định lý) P Q P P Q P  Q (P Q)  (P  Q) 0 0 0 1 1 0 1 1 Ví dụ: Xét mệnh đề phức hợp (P  P) CƠ SỞ LOGIC
15. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.3. Mệnh đề phức hợp và tương đương logic: Định nghĩa 3: Mệnh đề phức hợp E và F là tương đương logic nếu chúng có cùng bảng chân trị. Khi đó ta viết E  F hay E=F. Mệnh đề F gọi là hệ quả logic của mệnh đề E nếu mệnh đề (E F) là hằng đúng. Mệnh đề phức hợp E và F là tương đương logic khi và chỉ khi (EF) là hằng đúng. Ví dụ: P  (Q R) = P  (Q  R ) vì (Q R) tương đương logic với (Q  R) CƠ SỞ LOGIC
16. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.4. Độ ưu tiên của các phép toán logic: Cấp ưu tiên Thực hiện 1 Các phép toán trong ngoặc 2 Phép phủ định () 3 Phép hội () 4 Phép tuyển () 5 Phép kéo theo ( ), Phép tương đương () CƠ SỞ LOGIC
17. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. MỆNH ĐỀ 1.4. Độ ưu tiên của các phép toán logic: Nếu 2 phép toán có cùng cấp ưu tiên thì thực hiện phép đứng bên trái trước. Ví dụ: P  Q R  S tương đương với (P  Q) (R  S) (P  Q)  R  S tương đương với (P  Q)  (R  S ) P  Q R  S tương đương với ((P  Q) R)  S CƠ SỞ LOGIC
18. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. CÁC QUI LUẬT LOGIC 2.1. Một số qui luật logic thường được sử dụng trong lập luận và chứng minh CƠ SỞ LOGIC
19. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. CÁC QUI LUẬT LOGIC * Có thể chứng minh các định lý trên bằng cách lập bảng chân trị . CƠ SỞ LOGIC
20. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. CÁC QUI LUẬT LOGIC 2.2 Một số ví dụ minh họa: Ví dụ 1: Chứng minh ((P  Q ) R) = (P (Q R)) Ví dụ 2: Chứng minh mệnh đề dưới đây là hằng đúng ((P Q )  P) Q Augustus De Morgan (1806-1871) CƠ SỞ LOGIC
21. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.1. Suy luận và chứng minh Suy luận là rút ra mệnh đề mới từ một hay nhiều mệnh đề đã có. Mệnh đề đã có được gọi là giả thiết hay tiền đề, Mệnh đề mới được gọi là kết luận. Ví dụ: Máy tính không hoạt động được. Điện không bị cắt. P1 P Một bộ phận nào đó của máy tính bị hỏng. 2 P3 Máy tính hoạt động bình thường. Cài đặt thêm một . phần mềm mới. Máy tính chạy chậm hẳn. . . Phần mềm này có vấn đề. Pn Q CƠ SỞ LOGIC
22. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.1. Suy luận và chứng minh Chứng minh: Xuất phát từ một số khẳng định đúng P1, P2, gọi là giả thiết. Dùng các qui tắc suy diễn để suy ra Q có giá trị đúng. Q là hệ quả logic của P1P2P3  Pn P1P2P3  Pn Q là một hằng đúng P1 P2 P3 . . . Pn Q CƠ SỞ LOGIC
23. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.2. Qui tắc suy diễn Qui tắc Modus Ponens (qui tắc khẳng định): [(P Q) P] Q CƠ SỞ LOGIC
24. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.2. Qui tắc suy diễn Qui tắc Modus Tollens (qui tắc phủ định): [(P Q) P] CƠ SỞ LOGIC
25. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.2. Qui tắc suy diễn Qui tắc tam đoạn luận: CƠ SỞ LOGIC
26. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.2. Qui tắc suy diễn Qui tắc tam đoạn luận rời: CƠ SỞ LOGIC
27. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.2. Qui tắc suy diễn Qui tắc mâu thuẩn (chứng minh phản chứng): [(P1 P2   Pn) Q)] [(P1 P2   Pn  Q) 0] Ý nghĩa của qui tắc: Để chứng minh vế trái là một hằng đúng ta chứng minh nếu thêm phủ định của q vào các tiền đề thì được một mâu thuẫn. Ví dụ: Cho a, b, c là 3 đường thẳng phân biệt và a//c và b//c chứng minh a//b. CƠ SỞ LOGIC
28. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. SUY LUẬN TOÁN HỌC 3.2. Qui tắc suy diễn Ví dụ Kiểm tra tính đúng sai của kết luận dưới đây: Nếu tôi học thì tôi sẽ không hỏng môn toán. Nếu tôi không chơi bóng rổ thì tôi học. Nhưng tôi đã hỏng môn Toán ___ Do đó tôi đã chơi bóng rổ CƠ SỞ LOGIC