Logic mệnh đề

Logic mệnh đề (logic toán học) là công cụ diễn đạt của toán học. Logic xuất hiện dưới nhiều thuật ngữ khác nhau và trong đủ loại định lí toán học.

Logic dùng để làm gì

Logic là khoa học nghiên cứu về suy luận, về tính đúng sai, về việc chứng minh và bác bỏ. Logic chỉ quan tâm đến hình thức của phát biểu, không quan tâm phát biểu đó nói cụ thể về điều gì, cũng không quan tâm đến các cách hiểu tâm lí hay những thứ tương tự.

Chẳng hạn, với câu “số 2 là số chẵn và là số lẻ”, ta có thể kết luận rằng cả câu này sai, vì số 2 không phải là số lẻ. Logic nói chung giải quyết những vấn đề như vậy.

Mệnh đề

Dĩ nhiên, nền tảng của logic mệnh đề là mệnh đề. Mệnh đề là một câu khẳng định mà ta xác định được nó đúng hay sai. Ví dụ về các mệnh đề đơn giản:

• Hà Nội là thủ đô của Việt Nam.
• Số tự nhiên 5 là số lẻ.
• HTML là một ngôn ngữ lập trình.
• 2 cộng 3 bằng 6.

Tất cả các câu trên đều là mệnh đề, dù là mệnh đề đúng (hai câu đầu) hay mệnh đề sai (hai câu cuối). Ngược lại, câu hỏi hoặc câu mà ta không thể xác định rõ là đúng hay sai thì không phải là mệnh đề. Lại xét ví dụ:

• Năm sau Hà Nội vẫn là thủ đô của Việt Nam chứ?
• Màu xanh lá là màu đẹp nhất.

Câu thứ nhất không thể là mệnh đề vì đó là câu hỏi. Với câu thứ hai, ta không xác định được đây là mệnh đề đúng hay sai. Câu như vậy gọi là giả thuyết (phỏng đoán).

Logic toán học cổ điển không xử lí tốt những câu mơ hồ kiểu “Nam cao” hay “Bài hát này hay”. Những câu như vậy được xử lí tốt hơn trong logic mờ (fuzzy logic), vốn được xây dựng để làm việc với sự mơ hồ.

Mệnh đề nguyên tử

Ở phần đầu, ta đã có ví dụ mệnh đề “số 2 là số chẵn và là số lẻ”. Có thể gọi mệnh đề này là mệnh đề phức hợp, vì thực ra mệnh đề này ghép từ hai mệnh đề ngắn hơn: “số 2 là số chẵn” và “số 2 là số lẻ”. Hai mệnh đề này được nối với nhau bằng phép liên kết “và” (hay “và đồng thời”).

Mệnh đề nguyên tử là mệnh đề không thể chia nhỏ hơn nữa; theo một nghĩa nào đó, đó là khẳng định đơn giản nhất. Các mệnh đề ví dụ ở trên thực ra đều là mệnh đề nguyên tử:

• Hà Nội là thủ đô của Việt Nam.
• Số tự nhiên 5 là số lẻ.
• HTML là một ngôn ngữ lập trình.
• 2 cộng 3 bằng 6.

Từ nay ta kí hiệu các mệnh đề nguyên tử bằng chữ cái thường, quen thuộc nhất là p, q, r, … và gọi chúng là biến mệnh đề.

Các phép liên kết mệnh đề

Logic toán học thường làm việc với một số phép liên kết mệnh đề nhất định. Bốn phép liên kết hai ngôi cơ bản là:

• p ∧ q là phép hội của hai mệnh đề, đọc là “mệnh đề p và mệnh đề q”
• p ∨ q là phép tuyển của hai mệnh đề, đọc là “mệnh đề p hoặc mệnh đề q”
• p ⇒ q là mệnh đề kéo theo, đọc là “nếu mệnh đề p thì mệnh đề q”
• p ⇔ q là mệnh đề tương đương, đọc là “mệnh đề p khi và chỉ khi mệnh đề q”

Ví dụ cụ thể về các phép liên kết mệnh đề:

• Ở trung tâm Đà Lạt trời đang mưa và có nắng. (phép hội)
• Ở trung tâm Đà Lạt trời đang mưa hoặc có nắng. (phép tuyển)
• Mèo là động vật có vú và cá voi là loài cá. (phép hội)
• Nếu ăn quá nhiều kem thì sẽ bị đau họng. (mệnh đề kéo theo)
• Nếu số x chia hết cho 4 thì số đó cũng chia hết cho 2. (mệnh đề kéo theo)
• Lan xinh và thông minh. (phép hội)
• Ca sĩ thành công khi và chỉ khi xinh đẹp. (mệnh đề tương đương)
• Nếu trời không mưa thì ta không bị ướt. (mệnh đề kéo theo)
• Nếu con mèo nhà tôi biết hát thì tôi là ông hoàng hài hước. (mệnh đề kéo theo)

Còn một phép liên kết mệnh đề thông dụng nữa: phép phủ định. Phép phủ định kí hiệu là $\bar{p}$ (cách viết trong sách giáo khoa) hoặc ¬p.

Công thức

Từ các biến mệnh đề (mệnh đề nguyên tử) và các phép liên kết mệnh đề, ta có thể lập nên những mệnh đề phức tạp hơn, gọi là công thức. Mọi ví dụ trong danh sách câu ở trên thực ra đều là công thức: ta có hai công thức nguyên tử, chẳng hạn “Ở trung tâm Đà Lạt trời đang mưa” và “có nắng”, rồi nối chúng bằng phép liên kết mệnh đề. Ở câu đầu, ta nối chúng bằng “và” và được công thức “Ở trung tâm Đà Lạt trời đang mưa và có nắng”; ở câu thứ hai, ta dùng “hoặc” và được công thức “Ở trung tâm Đà Lạt trời đang mưa hoặc có nắng”.

Về mặt hình thức, công thức được định nghĩa như sau:

• Mỗi biến mệnh đề (mệnh đề nguyên tử) là một công thức (nói chính xác hơn, đó là công thức nguyên tử).
• Nếu A và B là công thức thì ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) cũng là công thức.

Định nghĩa này hợp lí: ý thứ nhất nói rằng mỗi mệnh đề nguyên tử đồng thời là một công thức. Vậy nếu có hai mệnh đề nguyên tử, chẳng hạn “Ở trung tâm Đà Lạt trời đang mưa” và “có nắng”, thì ta cũng có hai công thức. Lúc này có thể áp dụng ý thứ hai để lập công thức phức tạp hơn, chẳng hạn:

• Ở trung tâm Đà Lạt trời đang mưa và có nắng.
• Ở trung tâm Đà Lạt trời đang mưa hoặc có nắng.
• Nếu ở trung tâm Đà Lạt có nắng thì trời đang mưa.
• Ở trung tâm Đà Lạt có nắng khi và chỉ khi trời đang mưa.

Dĩ nhiên, công thức không nhất thiết phải đúng. Giờ ta đã có thêm một loạt công thức mới, nên có thể ghép thành những công thức còn phức tạp hơn nữa. Đặt A = “Ở trung tâm Đà Lạt có nắng hoặc trời đang mưa.” (ta đã biết đây là công thức) và B = “có cầu vồng” (cũng ở trung tâm Đà Lạt, để khỏi phải nhắc lại mãi). Khi đó ta lập được các công thức mới. Dấu ngoặc trong câu chỉ để đánh dấu phép liên kết áp dụng cho phần nào.

• A ∧ B: (Ở trung tâm Đà Lạt có nắng hoặc trời đang mưa) và (có cầu vồng).
• A ∨ B: (Ở trung tâm Đà Lạt có nắng hoặc trời đang mưa) hoặc (có cầu vồng).
• A ⇒ B: Nếu (ở trung tâm Đà Lạt có nắng hoặc trời đang mưa) thì (có cầu vồng).
• A ⇔ B: (Ở trung tâm Đà Lạt có nắng hoặc trời đang mưa) khi và chỉ khi (có cầu vồng).

Tất cả các câu trên đều là công thức. Ta lại có thể lấy một trong các công thức này và ghép thêm một công thức khác. Nhờ vậy có thể tạo ra cả những câu quái dị như “Nếu ở trung tâm Đà Lạt có nắng hoặc trời đang mưa hoặc có cầu vồng thì có nắng hoặc trời đang mưa khi và chỉ khi có cầu vồng.”

Phần tiếp theo sẽ xét tính đúng sai của công thức.