CHƯƠNG 1: CƠ SỞ LOGIC §1 PHÁP TÍ NH MỆNH ĐỀ Trong toán học ta quan tâm đến những mệnh đề có giá trị hân lý xác định (đúng hoặc sai nhưng không thể vừa đúng vừa sai). Các khẳng định như vậy được gọi là mệnh đề. Các mệnh đề đúng được nói là có giá tr ị chân lý đúng (hay chân tr ị đúng), các mệnh đề sai được nói là có chân tr ị sai. Các khẳng định sau là mệnh đề: Môn Toán rời rạc là môn bắt buộc cho ngành Tin học.
4 là số nguyên tố. Hai mệnh đề đầu có chân trị 1, mệnh đề thứ ba có chân trị 0. Các khẳng định dưới dạng tán than hoặc mệnh lệnh không phải mệnh đề vì nó không có chân trị xác định. Khẳng định “ là số nguyên tố ” không phải mệnh đề.
Tuy nhiên, nếu thay n bằng một số nguyên cố định thì ta sẽ có một mệnh đề: chẳng hạn với = 3 ta có một mệnh đề đúng, trong khi với = 4 ta có một mệnh đề sai. Khẳng định này được gọi là một v ị t ừ và cũng là đối tượn khảo sát của logic. Ta thường ký hiệu các mệnh đề bởi các chữ , , , … và chân trị đúng (sai) được ký hiệu bởi 1 (0). Đôi khi ta còn dùng các ký hiệu , để chỉ chân trị đúng và dể chỉ chân trị sai.
Phân tích kỹ các ví dụ ta thấy các mệnh đề được chia ra làm 2 loại: Các mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết chúng lại bằng các liên từ(và, hay, nếu… thì… ) hoặc trạng từ “không”. Ta nói các mệnh đề này là mệnh đề phức hợp. Ví dụ: “Nếu trời đẹp thì tôi đi dạo” là một mệnh đề phức hợp. Các mệnh đề không thể xây dựng từ các mệnh đề khác bằng các liên từ hoặc trạng từ “không”.
Ta nói các mệnh đề này là mệnh đề nguyên thủy hay sơ cấp. Ví dụ: “Hôm nay trời đẹp”, “3 là số nguyên tố” là các mệnh đề nguyên thủy. Mục đích của phép tính mệnh đề là nghiên cứu chân trị của một mệnh đề phức hợp từ chân trị của các mệnh đề đơn giản hơn và các phép nối của những mệnh đề này thể hiện qua lien từ hoặc trạng từ “không”. Các phép nối: Phép phủ định: ph ủ định của mệnh đề P được ký hiệu bởi ¬ (đọc là không P).
Chân trị của ¬ là 0 nếu chân trị của là 1 và ngược lại. Ta có bảng sau gọi là b ảng chân tr ị của phép phủ định: GS. Nguyễn Hữu Anh 4 ¬ 0 1 1 0 Phép nối liền: m ệnh đề n ối liền của hai mệnh đề P, Q được ký hiệu bởi P∧Q (đọc là P và Q). Chân trị của P∧Q là 1 nếu cả P lẫn Q đều có chân trị 1.
Trong các trường hợp khác, P∧Q có chân trị 0. Nói cách khác phép nối liền được xác định bởi b ảng chân tr ị sau: ∧ 0 0 0 0 1 0 1 0 0 1 1 1 Ví dụ: mệnh đề “Hôm nay trời đẹp và trận bóng đá sẽ hấp dẫn” được xem là một mệnh đề đúng nếu cả hai điều kiện “trời đẹp” và “trận bóng đá sẽ hấp dẫn” đều xảy ra. Ngược lại nếu một mệnh đề đúng một mệnh đề sai hoặc cả hai mệnh đề đều sai thì mệnh đề là một mệnh đề sai. Phép nối rời: mệnh đề n ối r ời của hai mệnh đề P, Q được ký hiệu bởi P∨Q (đọc là P hoặc Q).
Chân trị của P∨Q là 0 nếu cả P lẫn Q đều có chân trị 0. Trong các trường hợp khác, P∨Q có chân trị 1. Nói cách khác phép nối rời được xác định bởi b ảng chân tr ị sau: ∨ 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ: “Ba đang đọc báo hay xem tivi” là một mệnh đề đúng nếu lúc này ba đọc báo, xem tivi hay vừa đọc báo vừa xem tivi (!). Ngược lại nếu cả hai việc trên đều không xảy ra, ví dụ Ba đang làm việc thì mệnh đề là mệnh đề sai.
Chú ý rằng trong mệnh đề P∨Q, từ “hay” được dung theo nghĩa bao gồm,nghĩa là và có thể đồng thời đúng. Tuy nhiên theo ngôn ngữ hằng ngày ta thường hiểu ∨ theo nghĩa loại trừ, nghĩa là đúng hay đúng nhưng không đồng thời đúng. Để phân biệt rõ rang, trong trường hợp loại trừ ta sẽ sử dụng từ “hoặc”: “ hoặc ” và ký hiệu ∨ ( hay nhưng không đồng thời cả hai). Bảng chân trị của ∨ là: GS.
Nguyễn Hữu Anh 5 ∨ 0 0 0 0 1 1 1 0 1 1 1 0 Phép kéo theo: nếu P thì Q được ký hiệu là → (cũng đọc là kéo theo , hay là điều kiện đủ của , hay là điều kiện đủ của ). Để xác định chân trị cho → ta hãy xem ví dụ mệnh đề “nếu trời đẹp thì tôi đi dạo”. Ta có các trường hợp sau: tr ời đẹp và tác giả của kh ẳng định đang đi dạo: khi ấy hiển nhiên là mệnh đề đúng. tr ời đẹp và tác giả ng ồi nhà: mệnh đề rõ ràng sai.
tr ời xấu và tác gi ả đi dạo: mệnh đề vẫn đúng tr ời xấu và tác giả ng ồi nhà: mặc dù trời xấu nhưng tác giả không vi phạm khẳng định của mình nên mệnh đề phải được xem là đúng. Từ đó ta có b ảng chân tr ị của phép kéo theo như sau: → 0 0 1 0 1 1 1 0 0 1 1 1 Chú ý: 1. Với quy ước về chân trị như trên, ta sẽ cò những khẳng định đúng rất ngộ nghĩnh như: “nếu 2=1 thì Quang Trung và Trần Hưng Đạo là một người” 2. Cần phân biệt mệnh đề → với lệnh ℎ trong một số ngôn ngữ lập trình ví dụ như Pascal, Basic.
Trong → thì cả và là mệnh đề còn trong lệnh ℎ ℎì là một mệnh đề còn là một dãy liên tiếp dòng lệnh sẽ được thực hiện nếu mệnh đề P có chân trị 1 và sẽ được bỏ qua nếu P có chân trị là 0. Nhắc lại rằng các dòng lệnh là những mệnh lệnh mà máy phải thực hiện nên không phải là một mệnh dề theo nghĩa ta xét. Dù sao cũng có một sự tương tự giữa hai đối tượng “ → ” và “ ℎ ”. Hơn nữa có thể lợi dụng các tương đương logic để thực hiện lệnh “ ℎ ” có hiệu quả.
Trong ngôn ngữ hằng ngày, người ta thường hay nhầm lẫn phép kéo theo với kéo theo hai chiều, chẳng hạn như phát biểu ”giảng viên khoa Toán dạy nghiêm túc” mà viết theo phép nối là “nếu anh là giáo viên khoa Toán thì anh dạy nghiêm túc” thường bị phản ứng giáo viên các khoa khác vì họ cho rằng người nói đã ám chỉ “nếu là giảng viên khoa khác thì dạy không nghiêm túc”. Thật ra khi phát biểu, người nói có khi cũng muốn ám chỉ “nếu anh là giáo viên khoa Toán thì anh dạy nghiêm túc”. Ở đây nếu viết phát biểu ban đầu dưới dạng → thì hai phát biểu hiểu nhầm sẽ có dạng ( ¬ ) → ( ¬ ) và →. Tuy nhiên, nếu bao gồm them một trong hai phát biểu sau, thì phát biểu → thành một phép kéo theo hai chiều theo nghĩa dưới đây.
Nguyễn Hữu Anh 6 Phép kéo theo hai chiều: mệnh đề nếu thì và ngược lại được ký hiệu là ↔ (cũng đọc là khi và chỉ khi , nếu và chỉ nếu , hay P là điều kiện cần và đủ để có ). Theo trên, cả hai chiều → và → đều đúng nên nếu đúng thì cũng đúng và ngược lại. Do đó ta có b ảng chân tr ị của phép kéo theo hai chiều như sau: ↔ 0 0 1 0 1 0 1 0 0 1 1 1 §2 DẠNG MỆNH ĐỀ Trong Đại số ta có các biểu thức đại số được xây dựng từ: các số nguyên, hữu tỉ, thực,… mà ta gọi là h ằng số. các biến , , … có thể lấy giá trị là các hằng số.
các phép toán thao tác trên các hằng số và các biến theo một thứ tự nhất định. Khi thay thế các biến trong một biểu thức đại số bởi các hằng số thì kết quả thực hiện phép toán trong biểu thức sẽ là một hằng số nào đó. Trong phép toán mệnh đề ta cũng có các “biểu thức logic” tương tự mà ta gọi là các d ạng mệnh đề được xây dựng từ: các mệnh đề (hằng mệnh đề). các biến mệnh đề , , … có thể lấy giá trị là các mệnh đề nào đó.
các phép nối thao tác trên các hằng mệnh đề và biến mệnh đề theo một thứ tự nhất định. Ở đây thứ tự được xác định bởi các dấu “()” để chỉ rõ phép nối thực hiện trên cặp mệnh đề nào, đúng ra là trên các biểu th ức con nào. Ví dụ như: ( , , ) = ( ∧ ) ˅ ((¬ ) → ) là một dạng mệnh đề trong đó , , là các biến mệnh đề còn là một hằng mệnh đề. Giả sử , là 2 dạng mệnh đề, khi ấy ¬ , ∧ , → , ↔ là các dạng mệnh đề.
Bằng cách này ta có thể xây dựng được các dạng mệnh đề càng ngày càng phức tạp. Mặt khác, điều ta quan tâm đối với một dạng mệnh đề ( , , , …) là chân trị của mệnh đề đó có được ( , , , …) khi thay các biến mệnh đề , , , … bởi các hằng mệnh đề , , , … có chân trị xác định, nghĩa là sự phụ thuộc của chân trị của ( , , , …) theo các chân trị của , , , … chứ không phải theo các thể hiện cụ thể , , , … qua các mệnh đề cu thể , , , … Nói cách khác mỗi một dạng mệnh đề ( , , , …) có một bảng chân trị xác định trong đó mỗi dòng cho biết chân trị của ( , , , …) theo các chân trị cụ thể của , , ,… GS. Nguyễn Hữu Anh 7 Ví dụ: 1. Ta hãy xây dựng bảng chân trị của hai dạng mệnh đề ˅( ˄ ) và ( ˅ ) ˄ theo các biến mệnh đề , , .