Trong logic mệnh đề, một công thức là hằng đúng nếu nó đúng trong mọi trường hợp của các biến (ví dụ "trời mưa hoặc không mưa"), là mâu thuẫn nếu nó sai trong mọi trường hợp ("trời vừa mưa vừa không mưa"), và là tiếp liên nếu đúng hay sai còn tuỳ trường hợp ("trời mưa"). Hằng đúng đúng nhờ hình thức chứ không nhờ sự đời — nên nó không cho biết gì về thế giới, nhưng lại là nền của mọi suy luận hợp lệ.
Ba loại câu qua ví dụ đời thường
Thử ba câu dự báo về ngày mai:
- "Mai trời mưa." — Có thể đúng, có thể sai; phải đợi tới mai mới biết. Đây là câu tiếp liên (contingent): giá trị của nó phụ thuộc vào sự việc.
- "Mai trời mưa hoặc không mưa." — Không cần đợi; câu này đúng bất kể thời tiết. Đây là hằng đúng (tautology). Người dự báo nói câu này không bao giờ sai, nhưng cũng chẳng giúp ai quyết định mang áo mưa.
- "Mai trời vừa mưa vừa không mưa (cùng lúc, cùng nơi)." — Sai bất kể thời tiết. Đây là mâu thuẫn (contradiction).
Điểm mấu chốt: việc xếp loại hằng đúng hay mâu thuẫn chỉ dựa vào khuôn của câu — "A hoặc không A", "A và không A" — không dựa vào A nói về cái gì. Thay "mai trời mưa" bằng "đội nhà thắng" hay "số 91 là số nguyên tố", khuôn vẫn quyết định kết quả.
Định nghĩa bằng bảng chân trị
Ký hiệu: p, q là các biến mệnh đề; ¬ "không"; ∧ "và"; ∨ "hoặc" (bao hàm); → "nếu… thì…", chỉ sai khi vế trước đúng, vế sau sai. Một công thức có n biến cần 2ⁿ dòng; xếp loại bằng cách nhìn cột cuối:
| Loại | Cột kết quả | Ví dụ | Phủ định của nó là |
|---|---|---|---|
| Hằng đúng | Toàn Đ | p ∨ ¬p | Mâu thuẫn |
| Mâu thuẫn | Toàn S | p ∧ ¬p | Hằng đúng |
| Tiếp liên | Có Đ, có S | p → q | Tiếp liên |
Thêm hai khái niệm đi kèm: một công thức thoả được nếu có ít nhất một dòng Đ (tức hằng đúng hoặc tiếp liên); không thoả được chính là mâu thuẫn.
Một bảng mẫu với hai biến, ghi Đ là đúng, S là sai:
| p | q | p ∨ ¬p | p ∧ ¬p | p → q | q → p | (p → q) ∨ (q → p) |
|---|---|---|---|---|---|---|
| Đ | Đ | Đ | S | Đ | Đ | Đ |
| Đ | S | Đ | S | S | Đ | Đ |
| S | Đ | Đ | S | Đ | S | Đ |
| S | S | Đ | S | Đ | Đ | Đ |
Cột cuối gây bất ngờ: (p → q) ∨ (q → p) là hằng đúng. Bằng lời: với hai câu bất kỳ, hoặc câu này kéo theo câu kia, hoặc câu kia kéo theo câu này. "Nếu mèo biết bơi thì ngày mai thứ Ba, hoặc nếu ngày mai thứ Ba thì mèo biết bơi" — luôn đúng! Lý do nằm ở cách logic định nghĩa phép kéo theo (chỉ sai khi trước đúng, sau sai): nếu vế đầu sai thì p đúng, q sai, khi ấy q → p chắc chắn đúng. Đây là một trong những điểm khiến phép kéo theo trong logic khác chữ "nếu" của đời thường.
Hằng đúng là cái khung của suy luận hợp lệ
Đây là lý do khái niệm này quan trọng, không chỉ là chuyện phân loại.
Lập luận hợp lệ ⇔ một câu điều kiện hằng đúng
Lập luận với các tiền đề P₁, P₂, …, Pₙ và kết luận K hợp lệ khi và chỉ khi công thức (P₁ ∧ P₂ ∧ … ∧ Pₙ) → K là hằng đúng. Ví dụ, modus ponens hợp lệ vì ((p → q) ∧ p) → q là hằng đúng; khẳng định hậu kiện không hợp lệ vì ((p → q) ∧ q) → p không phải hằng đúng — nó sai ở dòng p sai, q đúng.
Hai công thức tương đương ⇔ một câu "khi và chỉ khi" hằng đúng
Dấu ↔ đọc là "khi và chỉ khi", đúng khi hai vế cùng đúng hoặc cùng sai. A tương đương B (viết A ≡ B) đúng khi A ↔ B là hằng đúng. Luật De Morgan, luật phản đảo (p → q ≡ ¬q → ¬p), luật phủ định kép (¬¬p ≡ p) đều là các hằng đúng dạng này. Mỗi phép biến đổi khi rút gọn biểu thức logic là một lần dùng một hằng đúng.
Ba quy luật tư duy dưới dạng công thức
Quy luật đồng nhất (p → p), quy luật cấm mâu thuẫn (¬(p ∧ ¬p)) và quy luật bài trung (p ∨ ¬p) trong logic mệnh đề cổ điển đều là hằng đúng. Ý nghĩa triết học của chúng là đề tài của logic học đại cương; ở đây chỉ cần thấy chúng là ba dòng toàn chữ Đ.
Kiểm hằng đúng mà không cần lập đủ bảng
Với 3 biến bảng có 8 dòng, 4 biến đã 16 dòng, 10 biến thì 1.024 dòng. Có một mẹo: giả sử công thức sai rồi tìm mâu thuẫn. Nếu giả sử sai dẫn tới vô lý thì công thức không thể sai — tức hằng đúng. Nếu giả sử sai dẫn tới một cách gán giá trị trơn tru thì đó chính là dòng làm công thức sai.
Ví dụ 1. Kiểm ((p → q) ∧ (q → r)) → (p → r).
- Giả sử công thức sai. Câu "nếu… thì…" sai khi vế trước đúng, vế sau sai: vậy (p → q) ∧ (q → r) đúng và p → r sai.
- p → r sai ⇒ p đúng, r sai.
- p → q đúng, p đúng ⇒ q đúng.
- q → r đúng, q đúng ⇒ r đúng. Mâu thuẫn với bước 2.
- Kết luận: công thức không thể sai — hằng đúng. (Đây chính là tính bắc cầu của phép kéo theo.)
Ví dụ 2. Kiểm (p → q) → (q → p).
- Giả sử sai: p → q đúng và q → p sai.
- q → p sai ⇒ q đúng, p sai.
- Kiểm lại p → q với p sai, q đúng: đúng. Không có mâu thuẫn.
- Kết luận: công thức sai ở dòng p sai, q đúng — nên không phải hằng đúng. Nó cũng không phải mâu thuẫn (thử p, q cùng đúng: cả công thức đúng). Vậy là tiếp liên. Bằng lời: một câu đúng không bảo đảm câu đảo của nó đúng.
Khi tiền đề là mâu thuẫn
Một hệ quả lạ của định nghĩa: nếu các tiền đề mâu thuẫn với nhau thì mọi kết luận đều suy ra được một cách hợp lệ. Lý do: (p ∧ ¬p) → q là hằng đúng, vì vế trước không bao giờ đúng nên cả câu không bao giờ sai. Các nhà logic Trung Cổ gọi nguyên lý này bằng câu Latin ex falso quodlibet — "từ điều sai, ra bất cứ điều gì".
Về thực hành, điều này giải thích vì sao một bộ quy định tự mâu thuẫn là nguy hiểm: từ nó người ta "suy" được gì cũng được. Một số hệ logic không cổ điển (logic cận nhất quán) được dựng ra chính để chặn hệ quả này, nhưng đó là chủ đề nâng cao.
Bài tập
Xếp loại mỗi công thức: hằng đúng, mâu thuẫn hay tiếp liên.
- p → (q → p). Đáp án: Hằng đúng. Giả sử sai ⇒ p đúng và q → p sai ⇒ q đúng, p sai — mâu thuẫn với p đúng.
- (p ∨ q) ∧ ¬p ∧ ¬q. Đáp án: Mâu thuẫn. Muốn đúng thì p sai, q sai, nhưng khi đó p ∨ q sai.
- (p ∧ q) → (p ∨ q). Đáp án: Hằng đúng. Vế trước đúng chỉ khi p, q cùng đúng, lúc đó vế sau cũng đúng.
- (p ∨ q) → (p ∧ q). Đáp án: Tiếp liên. Sai khi p đúng, q sai; đúng khi p, q cùng đúng.
- ((p → q) → p) → p (luật Peirce). Đáp án: Hằng đúng. Giả sử sai ⇒ p sai và (p → q) → p đúng. Với p sai, p → q đúng, nên (p → q) → p thành "đúng → sai" — sai. Mâu thuẫn.
- ¬(p → q) ↔ (p ∧ ¬q). Đáp án: Hằng đúng: p → q chỉ sai khi p đúng, q sai — đúng là nội dung của p ∧ ¬q.
Dùng vào đâu
- Rút gọn biểu thức logic trong bài tập toán rời rạc, trong điều kiện code, trong thiết kế mạch: mỗi bước là thay một vế bằng vế tương đương.
- Nhận ra câu "không cho thông tin": những dự đoán kiểu "giá sẽ tăng hoặc không tăng" không bao giờ sai, vì chúng là hằng đúng trá hình.
- Kiểm một bộ quy định, một đặc tả phần mềm có tự mâu thuẫn không: đó là câu hỏi "công thức hội các điều khoản có thoả được không" — bài toán SAT nổi tiếng trong khoa học máy tính.
- Học tiếp: kiểm lập luận bằng bảng chân trị và viết chứng minh từng dòng; cả hai đều dựa trên mối nối "hợp lệ ⇔ hằng đúng" ở trên.
Câu hỏi thường gặp
Hằng đúng là gì?
Hằng đúng (tautology) là công thức logic đúng trong mọi trường hợp gán đúng sai cho các biến, ví dụ "p hoặc không p". Trên bảng chân trị, cột kết quả của nó toàn chữ Đ. Hằng đúng đúng nhờ hình thức nên không mang thông tin về thế giới.
Mâu thuẫn trong logic là gì?
Mâu thuẫn là công thức sai trong mọi trường hợp, ví dụ "p và không p". Cột kết quả trên bảng chân trị toàn chữ S. Phủ định của một mâu thuẫn là một hằng đúng và ngược lại.
Tiếp liên là gì?
Tiếp liên (contingent) là công thức có trường hợp đúng, có trường hợp sai, như "p → q". Phần lớn câu nói hằng ngày về sự việc đều là tiếp liên: muốn biết đúng sai phải nhìn vào thực tế.
Hằng đúng liên quan gì đến lập luận hợp lệ?
Một lập luận hợp lệ khi và chỉ khi câu "nếu (tất cả tiền đề) thì (kết luận)" là hằng đúng. Vì vậy kiểm hợp lệ và kiểm hằng đúng là cùng một việc, làm được bằng bảng chân trị hoặc bằng cách giả sử sai rồi tìm mâu thuẫn.
Làm sao kiểm nhanh một công thức có phải hằng đúng không?
Giả sử công thức sai, rồi suy ra giá trị của từng biến. Nếu đi tới mâu thuẫn thì công thức là hằng đúng; nếu tìm được một cách gán không mâu thuẫn thì đó là trường hợp làm công thức sai.
