Luật De Morgan gồm hai đẳng thức: phủ định của "p và q" là "không p hoặc không q"; phủ định của "p hoặc q" là "không p và không q". Nói gọn: khi đưa chữ "không" vào trong ngoặc, mỗi vế bị phủ định và chữ "và" đổi thành "hoặc", chữ "hoặc" đổi thành "và". Quên đổi chữ nối là lỗi phổ biến nhất khi phủ định một câu ghép.
Hai câu thường ngày, hai cách phủ định
Phủ định một câu "và". Quy chế học bổng ghi: "Được học bổng nếu điểm trung bình từ 8,0 trở lên và hạnh kiểm tốt." Bạn Khoa không được học bổng. Vậy điều gì đã thiếu? Không nhất thiết là thiếu cả hai. Chỉ cần điểm dưới 8,0 hoặc hạnh kiểm chưa tốt — một trong hai là đủ để trượt.
Phủ định một câu "hoặc". Bảo tàng ghi: "Miễn vé cho khách dưới 6 tuổi hoặc trên 60 tuổi." Một người phải mua vé khi nào? Khi người đó không dưới 6 tuổi và không trên 60 tuổi — tức là từ 6 đến 60 tuổi. Chỉ "không dưới 6 tuổi" thôi chưa đủ để phải mua: người 70 tuổi cũng không dưới 6 tuổi mà vẫn được miễn.
Hai ví dụ cho thấy hai chiều của cùng một luật.
Phát biểu và kiểm bằng bảng chân trị
Ký hiệu: ¬ là "không", ∧ là "và" (đúng khi cả hai vế đúng), ∨ là "hoặc" bao hàm (đúng khi ít nhất một vế đúng), ≡ đọc là "tương đương" — hai biểu thức đúng sai giống hệt nhau trong mọi trường hợp.
¬(p ∧ q) ≡ ¬p ∨ ¬q. ¬(p ∨ q) ≡ ¬p ∧ ¬q
Bảng chân trị (Đ là đúng, S là sai) kiểm cả hai luật trên bốn khả năng:
| p | q | ¬(p ∧ q) | ¬p ∨ ¬q | ¬(p ∨ q) | ¬p ∧ ¬q |
|---|---|---|---|---|---|
| Đ | Đ | S | S | S | S |
| Đ | S | Đ | Đ | S | S |
| S | Đ | Đ | Đ | S | S |
| S | S | Đ | Đ | Đ | Đ |
Cột 3 trùng cột 4, cột 5 trùng cột 6 ở cả bốn dòng — hai luật đúng. Để ý thêm: ¬(p ∧ q) chỉ sai ở một dòng (cả hai đúng), còn ¬(p ∨ q) chỉ đúng ở một dòng (cả hai sai). Đó là lý do câu "không phải vừa… vừa…" rất dễ đúng, còn câu "chẳng… cũng chẳng…" rất khó đúng.
Nhiều vế cũng vậy
Luật mở rộng cho bất kỳ số vế nào: ¬(p ∧ q ∧ r) ≡ ¬p ∨ ¬q ∨ ¬r, và ¬(p ∨ q ∨ r) ≡ ¬p ∧ ¬q ∧ ¬r. Một hồ sơ yêu cầu đủ năm giấy tờ thì "hồ sơ không hợp lệ" nghĩa là thiếu ít nhất một trong năm; còn "không có giấy nào trong năm loại" là chuyện khác hẳn.
Những lỗi hay gặp
| Câu gốc | Phủ định SAI (quên đổi chữ nối) | Phủ định ĐÚNG |
|---|---|---|
| An và Bình cùng đi dã ngoại. | An không đi và Bình không đi. | An không đi hoặc Bình không đi (ít nhất một người vắng). |
| Hôm nay mình ăn phở hoặc ăn bún. | Hôm nay mình không ăn phở hoặc không ăn bún. | Hôm nay mình không ăn phở và không ăn bún. |
| Số n chẵn và chia hết cho 3. | n lẻ và không chia hết cho 3. | n lẻ hoặc n không chia hết cho 3. |
| 1 < x < 5 (tức x > 1 và x < 5). | x ≤ 1 và x ≥ 5 (không số nào thoả). | x ≤ 1 hoặc x ≥ 5. |
Dòng cuối là lỗi kinh điển của học sinh khi giải bất phương trình: phủ định của một khoảng là hợp của hai nửa đường thẳng, không phải giao của chúng. Viết "x ≤ 1 và x ≥ 5" là viết ra một tập rỗng.
Câu tiếng Việt nhập nhằng phạm vi của chữ "không"
"An và Bình không đi" thường được hiểu là cả hai đều không đi (¬p ∧ ¬q). "Không phải An và Bình đều đi" lại là ¬(p ∧ q). Chỉ khác vị trí chữ "không" mà nghĩa khác hẳn. Khi viết điều khoản hay đề bài, đặt chữ "không" ở đâu cũng là quyết định logic. Các câu mơ hồ kiểu này được bàn kỹ hơn ở mảng logic trong lời nói hằng ngày.
De Morgan ở những nơi khác ngoài logic
Tập hợp
Thay "và" bằng giao (∩), "hoặc" bằng hợp (∪), "không" bằng phần bù, ta có: phần bù của A ∪ B bằng giao các phần bù; phần bù của A ∩ B bằng hợp các phần bù. Vẽ hai vòng tròn giao nhau rồi tô màu là thấy ngay. Ví dụ ở bảo tàng: tập khách được miễn vé là hợp của "dưới 6" và "trên 60"; tập khách phải mua là phần bù của hợp đó, tức giao của "từ 6 trở lên" và "từ 60 trở xuống".
Lập trình
Trong nhiều ngôn ngữ, !(a && b) tương đương !a || !b, và !(a || b) tương đương !a && !b. Ví dụ: vòng lặp "lặp khi chưa tìm thấy và chưa hết giờ" sẽ dừng khi "đã tìm thấy hoặc đã hết giờ". Viết sai điều kiện dừng thành "đã tìm thấy và đã hết giờ" là vòng lặp chạy tiếp sau khi đã tìm thấy — một lỗi kinh điển.
Mạch điện
Một cổng NAND (phủ định của AND) có thể thay bằng cổng OR với hai đầu vào đã đảo — đó là De Morgan bằng dây đồng. Phần này thuộc logic và máy tính.
Lượng từ
Phiên bản cho "tất cả" và "có một": phủ định của "mọi x đều thoả P" là "có một x không thoả P". "Tất cả" giống một chuỗi "và" dài, "có một" giống một chuỗi "hoặc" dài, nên luật này là De Morgan mở rộng. Cách phủ định câu có "tất cả / có một / không ai" là bài nhập môn của logic phổ thông.
Tên của luật
Luật mang tên nhà toán học Anh Augustus De Morgan (1806–1871), người trình bày các quy tắc này trong khuôn khổ logic hình thức mới của thế kỷ 19; cuốn Formal Logic của ông ra năm 1847, cùng năm với cuốn sách đầu tiên của George Boole về đại số logic. Ý tưởng thì cũ hơn nhiều: các nhà logic thời Trung Cổ, trong đó có William of Ockham, đã phát biểu những quy tắc tương tự bằng lời. Đóng góp của thế kỷ 19 là viết chúng thành định luật của một phép tính, dùng được như đẳng thức đại số.
Bài tập
- Phủ định câu "Hôm nay trời nắng và có gió." Đáp án: "Hôm nay trời không nắng hoặc không có gió."
- Phủ định câu "Cuối tuần cả nhà đi biển hoặc về quê." Đáp án: "Cuối tuần cả nhà không đi biển và không về quê."
- Phủ định điều kiện 2 ≤ x ≤ 7. Đáp án: x < 2 hoặc x > 7.
- Rút gọn ¬(¬p ∨ q). Đáp án: Theo De Morgan được ¬¬p ∧ ¬q, tức p ∧ ¬q. (Vì p → q tương đương ¬p ∨ q, kết quả này cũng là phủ định của "nếu p thì q": p xảy ra mà q không xảy ra.)
- Viết lại điều kiện !(diem >= 5 || co_mien_thi) mà không dùng dấu phủ định bên ngoài ngoặc. Đáp án: diem < 5 && !co_mien_thi — điểm dưới 5 và không được miễn thi.
Dùng vào đâu
- Đọc điều kiện tuyển sinh, khuyến mãi, học bổng: mỗi khi có "và", "hoặc", hỏi ngay "trượt thì là do thiếu một hay thiếu tất cả".
- Giải bất phương trình, tìm miền giá trị: lấy phần bù của một khoảng thì đổi "và" thành "hoặc".
- Viết code và truy vấn dữ liệu: điều kiện dừng vòng lặp, bộ lọc "không thuộc nhóm A hoặc nhóm B".
- Học tiếp: hằng đúng và các phép biến đổi tương đương; luật De Morgan là một trong những hằng đúng dùng nhiều nhất khi rút gọn biểu thức logic.
Câu hỏi thường gặp
Luật De Morgan là gì?
Là hai quy tắc phủ định câu ghép: phủ định của "p và q" là "không p hoặc không q"; phủ định của "p hoặc q" là "không p và không q". Khi đưa phủ định vào trong, chữ "và" đổi thành "hoặc" và ngược lại.
Phủ định của "và" là gì?
Phủ định của "p và q" là "không p hoặc không q": chỉ cần một vế sai là câu "và" đã sai. Ví dụ phủ định của "An và Bình cùng đi" là "An không đi hoặc Bình không đi", không phải "cả hai đều không đi".
Phủ định của "1 < x < 5" là gì?
Là "x ≤ 1 hoặc x ≥ 5". Điều kiện 1 < x < 5 là câu "và" (x > 1 và x < 5), nên phủ định của nó là câu "hoặc" của hai phủ định. Viết "x ≤ 1 và x ≥ 5" là sai vì không số nào thoả.
Luật De Morgan dùng trong lập trình thế nào?
Để viết lại điều kiện có dấu phủ định: !(a && b) tương đương !a || !b, và !(a || b) tương đương !a && !b. Nó đặc biệt hữu ích khi viết điều kiện dừng vòng lặp và bộ lọc dữ liệu.
Ai phát hiện ra luật De Morgan?
Luật mang tên Augustus De Morgan, người đưa nó vào logic hình thức thế kỷ 19 (cuốn Formal Logic năm 1847). Tuy vậy, các nhà logic Trung Cổ như William of Ockham đã phát biểu những quy tắc tương tự bằng lời từ trước.