Logic mệnh đề là phần cơ bản nhất của logic hình thức: nó nghiên cứu cách các câu có giá trị đúng hoặc sai kết hợp với nhau qua các phép nối như “không”, “và”, “hoặc”, “nếu… thì”. Giá trị đúng sai của câu ghép được xác định hoàn toàn bởi giá trị của các câu thành phần, và bảng chân trị là công cụ để tính điều đó.
Học logic mệnh đề cho bạn ba thứ dùng được: kiểm tra một lập luận có hợp lệ không bằng phép tính máy móc, viết lại một điều kiện phức tạp thành dạng tương đương dễ hiểu hơn (rất hữu ích khi viết điều khoản hợp đồng hay câu lệnh lập trình), và nhận ra những chỗ ngôn ngữ tự nhiên mơ hồ mà logic buộc phải chọn một nghĩa.
Mệnh đề là gì và vì sao phải hình thức hoá
Mệnh đề là câu khẳng định có giá trị chân lý xác định: đúng hoặc sai. “Hà Nội là thủ đô của Việt Nam” là mệnh đề đúng; “7 là số chẵn” là mệnh đề sai. Câu hỏi, câu mệnh lệnh, câu cảm thán không phải mệnh đề. Câu “x lớn hơn 5” cũng chưa phải mệnh đề cho đến khi x được gán giá trị; câu này thuộc phạm vi của logic vị từ.
Logic mệnh đề bỏ qua cấu trúc bên trong của mệnh đề đơn và thay chúng bằng biến như P, Q, R. Việc trừu tượng hoá này là lý do logic có sức mạnh: một khi đã chứng minh khung “nếu P thì Q; P; vậy Q” luôn hợp lệ, ta không cần kiểm tra lại cho từng nội dung cụ thể. Nó cũng là lý do người mới học thấy logic xa lạ, vì ngôn ngữ tự nhiên mang đầy sắc thái mà biến P không giữ được.
Hình thức hoá còn có giá trị phát hiện mơ hồ. Câu quy định “sinh viên có điểm trung bình từ 8,0 hoặc có giải thưởng nghiên cứu và không bị kỷ luật được nhận học bổng” có hai cách đọc: (A hoặc B) và C, hoặc A hoặc (B và C). Với sinh viên có điểm 8,5 nhưng bị kỷ luật, hai cách đọc cho hai kết quả khác nhau. Ngôn ngữ tự nhiên không có dấu ngoặc; logic buộc bạn đặt chúng.
Năm phép nối và bảng chân trị
Với hai mệnh đề P và Q, có bốn tổ hợp giá trị. Bảng dưới cho giá trị của năm phép nối chuẩn trên từng tổ hợp (Đ là đúng, S là sai).
| P | Q | không P | P và Q | P hoặc Q | nếu P thì Q | P khi và chỉ khi Q |
|---|---|---|---|---|---|---|
| Đ | Đ | S | Đ | Đ | Đ | Đ |
| Đ | S | S | S | Đ | S | S |
| S | Đ | Đ | S | Đ | Đ | S |
| S | S | Đ | S | S | Đ | Đ |
Hai điểm cần chú ý. Thứ nhất, “hoặc” trong logic là tuyển bao hàm: đúng cả khi hai vế cùng đúng. Tiếng Việt đời thường hay dùng “hoặc” theo nghĩa loại trừ (“chọn trà hoặc cà phê”), ứng với một phép nối khác là tuyển loại trừ, đúng khi đúng một vế. Thứ hai, “nếu P thì Q” chỉ sai trong đúng một trường hợp: P đúng mà Q sai. Hai dòng cuối, khi P sai, phép kéo theo đều đúng, điều khiến nhiều người khó chịu và là chủ đề của mục tiếp theo.
Với n biến, bảng chân trị có 2 mũ n dòng. Ba biến là 8 dòng, mười biến đã là 1.024 dòng; đây là lý do kiểm tra bằng bảng chân trị chỉ thực tế với lập luận ngắn.
Phép kéo theo: phép nối gây tranh cãi nhất
Phép kéo theo trong logic cổ điển gọi là kéo theo vật chất: “nếu P thì Q” tương đương với “không P hoặc Q”. Hệ quả là “nếu 2 cộng 2 bằng 5 thì Trái Đất vuông” là mệnh đề đúng, vì tiền kiện sai. Cũng vậy, “nếu Trái Đất quay quanh Mặt Trời thì nước sôi ở 100 độ C dưới áp suất tiêu chuẩn” đúng, dù hai vế chẳng liên quan gì nhau. Đây gọi là các nghịch lý của kéo theo vật chất.
Cách hiểu dễ nhất là xem “nếu P thì Q” như một lời hứa. Giáo viên nói: “Nếu em đạt 9 điểm thì em được miễn thi cuối kỳ”. Lời hứa chỉ bị phá khi học sinh đạt 9 mà vẫn phải thi. Nếu học sinh không đạt 9, dù được miễn hay không, giáo viên đều không thất hứa. Logic cổ điển gán “đúng” cho mọi trường hợp không phá lời hứa.
Không phải ai cũng hài lòng. Năm 1912, C. I. Lewis đề xuất kéo theo chặt, đòi hỏi không thể có P đúng mà Q sai, mở đầu logic mô thái hiện đại. Các nhà logic liên quan (relevance logic) như Anderson và Belnap đòi hỏi tiền kiện và hậu kiện phải có liên hệ nội dung. Còn câu điều kiện phản thực tế (“nếu hôm qua trời mưa thì trận đấu đã bị hoãn”) được phân tích bằng ngữ nghĩa thế giới khả hữu của Robert Stalnaker và David Lewis. Logic cổ điển vẫn là chuẩn cho toán học vì nó đơn giản và đủ dùng ở đó, nhưng nó không phải mô hình đầy đủ của “nếu” trong ngôn ngữ người.
Hằng đúng, mâu thuẫn và các luật tương đương
Một công thức đúng ở mọi dòng của bảng chân trị là hằng đúng; sai ở mọi dòng là mâu thuẫn; còn lại là khả đúng. Hai công thức tương đương khi chúng có cùng cột giá trị. Các luật tương đương sau được dùng nhiều nhất để biến đổi công thức:
- Luật De Morgan: “không (P và Q)” tương đương “không P hoặc không Q”; “không (P hoặc Q)” tương đương “không P và không Q”. Ví dụ: phủ định của “hồ sơ đủ giấy tờ và nộp đúng hạn” là “hồ sơ thiếu giấy tờ hoặc nộp trễ”, không phải “thiếu giấy tờ và nộp trễ”.
- Phủ định kép: “không không P” tương đương P. Trong logic trực giác của Brouwer và Heyting, luật này không còn hiển nhiên theo chiều từ “không không P” suy ra P.
- Phản đảo: “nếu P thì Q” tương đương “nếu không Q thì không P”. Đây là cơ sở của chứng minh phản chứng và của suy luận modus tollens.
- Phân phối: “P và (Q hoặc R)” tương đương “(P và Q) hoặc (P và R)”, và ngược vai “và”, “hoặc” cũng đúng.
- Luật bài trung và luật phi mâu thuẫn: “P hoặc không P” là hằng đúng; “P và không P” là mâu thuẫn. Từ một mâu thuẫn, logic cổ điển cho phép suy ra bất kỳ điều gì, gọi là nguyên lý ex falso quodlibet (từ cái sai suy ra mọi thứ); các logic cận nhất quán được xây dựng để tránh hệ quả này.
Trong lập trình, luật De Morgan được dùng hằng ngày để đơn giản hoá điều kiện. Một câu lệnh kiểu “nếu không (đã đăng nhập và có quyền)” thường dễ đọc hơn khi viết lại thành “nếu chưa đăng nhập hoặc không có quyền”, và lỗi viết sai phủ định là nguồn lỗi bảo mật thường gặp.
Kiểm tra một lập luận bằng bảng chân trị
Một lập luận hợp lệ khi không có dòng nào mà mọi tiền đề đều đúng còn kết luận sai. Quy trình máy móc như sau, minh hoạ bằng lập luận: “Nếu nhà máy giảm phát thải thì được giảm thuế. Nhà máy không được giảm thuế. Vậy nhà máy không giảm phát thải.”
- Đặt biến cho mệnh đề đơn. P: nhà máy giảm phát thải. Q: nhà máy được giảm thuế.
- Viết tiền đề và kết luận dạng ký hiệu. Tiền đề 1: nếu P thì Q. Tiền đề 2: không Q. Kết luận: không P.
- Lập bảng đủ mọi tổ hợp của P và Q (bốn dòng), tính cột cho từng tiền đề và kết luận.
- Tìm các dòng mà mọi tiền đề đều đúng. Ở đây chỉ có dòng P sai, Q sai.
- Kiểm tra kết luận ở các dòng đó. Ở dòng P sai, kết luận “không P” đúng. Không có phản ví dụ, vậy lập luận hợp lệ. Đây là dạng modus tollens.
- Đối chiếu với dạng hỏng. Nếu tiền đề 2 là “nhà máy được giảm thuế” và kết luận “nhà máy đã giảm phát thải”, bảng sẽ cho thấy dòng P sai, Q đúng làm mọi tiền đề đúng mà kết luận sai: đó là khẳng định hậu kiện.
Phương pháp này chỉ trả lời câu hỏi hợp lệ. Nó không nói gì về việc tiền đề 1 có đúng trong thực tế không, tức chính sách thuế có thật sự quy định như vậy hay không.
Từ Boole đến mạch điện và máy tính: dòng thời gian
Logic mệnh đề hiện đại hình thành trong khoảng tám mươi năm và nhanh chóng rời khỏi triết học để vào kỹ thuật.
- Thế kỷ 3 trước Công nguyên: các nhà logic phái Khắc kỷ, nổi bật là Chrysippus, đã phân tích các phép nối mệnh đề và các sơ đồ suy luận như modus ponens, theo một hướng khác với logic thuật ngữ của Aristotle, vốn xoay quanh quan hệ giữa các khái niệm như “mọi”, “một số”.
- 1847: George Boole xuất bản The Mathematical Analysis of Logic; cùng năm Augustus De Morgan xuất bản Formal Logic. Boole xử lý mệnh đề như đại lượng đại số chỉ nhận giá trị 0 và 1.
- 1854: Boole xuất bản An Investigation of the Laws of Thought, hoàn thiện đại số mang tên ông.
- 1879: Gottlob Frege công bố Begriffsschrift, hệ thống logic hình thức đầy đủ đầu tiên, gồm cả lượng từ.
- 1921: bảng chân trị được trình bày có hệ thống bởi Ludwig Wittgenstein trong Tractatus và độc lập bởi Emil Post, người còn chứng minh tính đầy đủ của logic mệnh đề.
- 1937: Claude Shannon, trong luận văn thạc sĩ tại MIT, chỉ ra mạch rơ-le và công tắc có thể được thiết kế và tối giản bằng đại số Boole, đặt nền cho thiết kế mạch số.
- 1971: Stephen Cook chứng minh bài toán thoả được của logic mệnh đề (SAT) là NP-đầy đủ, đưa nó vào trung tâm của lý thuyết độ phức tạp tính toán.
Ngày nay các bộ giải SAT xử lý được công thức có hàng triệu biến trong những bài toán thực tế như kiểm chứng phần cứng và lập lịch, dù về lý thuyết bài toán vẫn khó trong trường hợp xấu nhất.
Giới hạn: điều logic mệnh đề không nắm được
Lập luận “mọi kỹ sư đều học toán; An là kỹ sư; vậy An học toán” hiển nhiên hợp lệ, nhưng logic mệnh đề không chứng minh được. Lý do: ba câu là ba mệnh đề đơn khác nhau P, Q, R, và khung “P; Q; vậy R” không hợp lệ. Muốn nắm được, phải nhìn vào bên trong mệnh đề, tới chủ ngữ, vị ngữ và lượng từ “mọi”, “có ít nhất một”. Đó là logic vị từ bậc nhất, do Frege và sau đó Russell, Whitehead phát triển.
Logic mệnh đề cũng giả định mỗi mệnh đề chỉ có hai giá trị. Jan Łukasiewicz giới thiệu logic ba giá trị khoảng năm 1920 để xử lý mệnh đề về tương lai chưa xác định; Lotfi Zadeh đề xuất tập mờ năm 1965, mở đường cho logic mờ, nơi “phòng này nóng” có thể đúng ở mức 0,7. Logic mô thái thêm các toán tử “tất yếu”, “có thể”; logic thời gian thêm “luôn luôn”, “sẽ có lúc”, và được dùng để kiểm chứng phần mềm.
Một giới hạn khác thuộc về con người hơn là hệ thống: logic mệnh đề cho biết cái gì theo sau cái gì, không cho biết nên tin tiền đề nào. Khi một lập luận hợp lệ dẫn tới kết luận ta thấy vô lý, logic chỉ bảo rằng ít nhất một tiền đề sai; chọn bỏ tiền đề nào là việc của bằng chứng và phán đoán. Như một nhận xét quen thuộc trong triết học: modus ponens của người này là modus tollens của người kia.
Câu hỏi thường gặp
Logic mệnh đề có liên quan gì tới đại số Boole học ở môn tin học?
Hai thứ là một cấu trúc nhìn từ hai phía. Đại số Boole dùng 1 và 0 thay cho đúng và sai, phép nhân cho “và”, phép cộng có điều chỉnh cho “hoặc”, phần bù cho “không”. Mọi luật tương đương của logic mệnh đề, như De Morgan và phân phối, đều có bản tương ứng trong đại số Boole, và đó là cơ sở để tối giản mạch số bằng bìa Karnaugh hay các thuật toán tương tự.
Tại sao một tập phép nối như “không” và “và” là đủ?
Mọi hàm chân lý, tức mọi cách gán đúng sai cho các tổ hợp đầu vào, đều biểu diễn được bằng “không” kết hợp với “và” hoặc với “hoặc”; tập như vậy gọi là đầy đủ chức năng. Thậm chí một phép nối duy nhất là NAND (không đồng thời) cũng đủ, điều Henry Sheffer chỉ ra năm 1913. Đây là lý do các chip số có thể xây hoàn toàn từ cổng NAND.
Dạng chuẩn tắc hội và tuyển dùng để làm gì?
Dạng chuẩn tắc tuyển là “hoặc” của các cụm “và”, dạng chuẩn tắc hội là “và” của các cụm “hoặc”. Mọi công thức đều đưa được về hai dạng này. Dạng hội là đầu vào chuẩn của các bộ giải SAT; dạng tuyển đọc thẳng từ bảng chân trị bằng cách lấy các dòng cho kết quả đúng. Chúng cho phép so sánh và xử lý công thức một cách máy móc.
Logic mệnh đề có đầy đủ và nhất quán không?
Có. Các hệ chứng minh chuẩn cho logic mệnh đề vừa nhất quán, tức không chứng minh được mâu thuẫn, vừa đầy đủ, tức mọi hằng đúng đều chứng minh được, như Post chứng minh năm 1921. Nó cũng quyết định được: luôn có thuật toán trả lời một công thức có phải hằng đúng hay không. Các định lý bất toàn của Gödel áp dụng cho hệ đủ mạnh để chứa số học, không áp dụng ở đây.
Học logic mệnh đề có giúp lập luận tốt hơn trong đời thường không?
Có, nhưng hẹp hơn người ta kỳ vọng. Nó giúp nhận ra các lỗi cấu trúc như khẳng định hậu kiện, phủ định sai một câu ghép và đọc nhầm điều kiện. Phần lớn lỗi lập luận đời thường lại nằm ở tiền đề, bằng chứng và mức độ liên quan, thuộc phạm vi của logic phi hình thức và tư duy thống kê. Logic mệnh đề là nền móng cần có, không phải toàn bộ ngôi nhà.