Bài giảng MH/MĐ: Toán ứng dụng - Bài 1: Cơ sở Logic

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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC KẾ HOẠCH BÀI GIẢNG STT TÊN BÀI HỌC THỜI GIAN (G) GHI CHÚ TỔNG LT TH 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 4 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM 12.5 8.5 4 Kiểm tra định kỳ lần 2 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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ả.  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 đề 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). - 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) TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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  TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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: 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” P P (hoặc ) 1 0 0 1 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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: 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" P Q P  Q 0 0 0 0 1 0 1 0 0 1 1 1 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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: Ví dụ: P : “An đang đọc báo " Q : “ An đang đá banh" P  Q : "An đọc báo" hoặc “An đang đá banh" P Q P  Q 0 0 0 0 1 1 1 0 1 1 1 1 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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: Ví dụ: P : “chạch đẻ ngọn đa" Q : “ta lấy nàng" P  Q : Nếu ................... thì ............................ P Q P  Q 0 0 1 0 1 1 1 0 0 1 1 1 P: giả thuyết; Q: kết luận; Cách đọc: "P kéo theo Q" "Nếu P thì Q" "Q chỉ nếu P" TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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: 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ách đọc: "P nếu và chỉ nếu Q" "Nếu P thì Q và ngược lại" P Q P  Q 0 0 1 0 1 0 1 0 0 1 1 1 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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ý) Ví dụ: Xét mệnh đề phức hợp (P  P) P Q P P Q P  Q (P Q)  (P  Q) 0 0 0 1 1 0 1 1 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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) TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 () TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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ị . TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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) TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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.  Một bộ phận nào đó của máy tính bị hỏng. 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 đề. P1 P2 P3 . . . Pn  Q TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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]  TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 3. SUY LUẬN TOÁN HỌC 3.2. Qui tắc suy diễn Qui tắc tam đoạn luận: TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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: TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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): Ý 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. ]0)...21[(]))...21[(  QPnPPQPnPP TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CƠ SỞ LOGIC 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ổ