Cùng một tấm biển, viết hai lần#
Một tấm biển trên cửa ghi:
“Nếu bạn có chìa khóa hoặc mã, cửa sẽ mở.”
Ai đó viết lại thành hai quy tắc riêng:
“Nếu bạn có chìa khóa, cửa sẽ mở. Và nếu bạn có mã, cửa sẽ mở.”
Cùng một tấm biển, hay khác nhau? Hãy quyết định trước khi đọc tiếp.
Đó là cùng một tấm biển. Ai vào được theo tấm đầu thì vào được theo tấm sau, và ngược lại.
Nhưng hãy nhìn từ nối nhỏ bé. Tấm biển đầu nói hoặc. Tấm biển sau nói và. Không ai chuyển chữ “không” đi đâu. Không ai thêm gì. Từ đó tự đổi.
Phép đổi đó là toàn bộ nội dung của trang này, và là điều duy nhất hay bị viết sai nhất.
“Giống nhau” ở đây nghĩa là gì#
Đặt chữ cho ba phần: a là “bạn có chìa khóa”, b là “bạn có mã”, c là “cửa mở”. Khi đó hai tấm biển là:
(a ∨ b) → c ≡ (a → c) ∧ (b → c)
Năm ký hiệu, và đó là tất cả những gì bạn cần cho trang này:
| Ký hiệu | Đọc là | Nghĩa là |
|---|---|---|
| ∨ | “hoặc” | ít nhất một trong hai đúng |
| ∧ | “và” | cả hai đều đúng |
| ¬ | “không” | điều ngược lại |
| → | “nếu … thì” | một lời hứa: bất cứ khi nào vế trái đúng, vế phải đúng |
| ≡ | “là cùng một mệnh đề với” | hai vế luôn trùng nhau |
Hai mệnh đề tương đương logic (logically equivalent), viết P ≡ Q, khi chúng cho kết quả giống nhau với mọi tổ hợp đúng và sai có thể có. Không phải thường giống nhau. Luôn luôn giống nhau, không có ngoại lệ — đó là lý do chứng minh điều này nghĩa là kiểm tra mọi trường hợp.
Hai cách chứng minh#
Có hai cách được chấp nhận để chứng tỏ hai mệnh đề tương đương, và một môn học thường yêu cầu một cách cụ thể.
| Bảng chân trị | Chuỗi các luật | |
|---|---|---|
| Cách làm | Lập cả hai cột, so sánh | Viết lại một vế từng bước cho đến khi nó thành vế kia |
| Cần | Cẩn thận và kiên nhẫn | Các luật có tên, được nhớ chính xác |
| Kích thước | 2ⁿ hàng cho n chữ cái | Thường 3–6 dòng |
| Thất bại khi | Có nhiều chữ cái — 5 nghĩa là 32 hàng | Bạn không nhận ra luật đúng |
| Còn cho bạn | Hàng chính xác mà hai thứ khác nhau | Hiểu vì sao chúng trùng nhau |
“Dùng bảng chân trị, chứng minh…” và “Dùng các luật De Morgan để chứng minh…” là những câu hỏi khác nhau có cùng đáp án. Nộp một cái bảng khi đề yêu cầu các luật là không trả lời câu hỏi đã được hỏi, và thường không được điểm.
Cách 1 — bảng chân trị#
Một bảng chân trị liệt kê mọi tổ hợp đúng và sai có thể có, rồi tính xem mỗi vế bằng bao nhiêu. Ba chữ cái nghĩa là 2³ = 8 tổ hợp, nên tám hàng.
1 nghĩa là đúng và 0 nghĩa là sai — ký hiệu dùng trong các bảng chân trị bên dưới.
| a | b | c | a ∨ b | (a∨b) → c | a → c | b → c | (a→c) ∧ (b→c) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Cột 5 và cột 8 trùng nhau ở cả tám hàng, nên hai mệnh đề tương đương. Chứng minh xong.
Hai hàng cuối đáng để chậm lại. Ở đó, không ai có chìa khóa hoặc mã, nên a ∨ b sai — và một mệnh đề nếu–thì có nửa đầu sai được tính là đúng. Tấm biển không bị phá bởi một người chưa từng thử cánh cửa. Các hàng mà không có gì xảy ra vẫn phải khớp, và chúng là những hàng người ta điền cẩu thả nhất.
Cách 2 — một chuỗi các luật có tên#
Cách còn lại viết lại một vế, từng bước một, cho đến khi nó biến thành vế kia — nêu tên luật biện minh cho mỗi bước.
| Bước | Biểu thức | Luật được dùng |
|---|---|---|
| 0 | (a ∨ b) → c | chỗ chúng ta bắt đầu |
| 1 | ¬(a ∨ b) ∨ c | mũi tên–hoặc: p → q ≡ ¬p ∨ q |
| 2 | (¬a ∧ ¬b) ∨ c | De Morgan |
| 3 | (¬a ∨ c) ∧ (¬b ∨ c) | phân phối |
| 4 | (a → c) ∧ (b → c) | mũi tên–hoặc một lần nữa, hai lần, theo chiều ngược lại |
Bốn dòng. Và không như bảng, nó giải thích phép đổi thay vì chỉ báo cáo nó. ∨ trở thành ∧ ở bước 2, vì De Morgan biến “không (cái này hoặc cái kia)” thành “không cái này và không cái kia”. Mọi thứ sau đó là sổ sách.
Viết lại p → q thành ¬p ∨ q. Mũi tên khó thao tác; ∧, ∨ và ¬ có các luật bạn có thể áp dụng. Đổi trước, làm sau, đổi lại ở cuối.
Các luật bạn phải gọi được tên#
Một chứng minh bằng chuỗi chỉ được điểm nếu mỗi dòng nêu một luật, nên nhớ tên quan trọng như nhớ các bước đi.
| Tên | Nội dung |
|---|---|
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q · ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Mũi tên–hoặc | p → q ≡ ¬p ∨ q |
| Phản đảo | p → q ≡ ¬q → ¬p |
| Phủ định một mũi tên | ¬(p → q) ≡ p ∧ ¬q |
| Phân phối | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| Phủ định kép | ¬¬p ≡ p |
| Đồng nhất / thống trị | p ∧ 1 ≡ p · p ∨ 1 ≡ 1 |
| Phủ định | p ∨ ¬p ≡ 1 · p ∧ ¬p ≡ 0 |
| Hấp thụ | p ∨ (p ∧ q) ≡ p |
Cái làm người ta ngạc nhiên#
Vì chữ “hoặc” bên trái biến thành chữ “và” bên phải, phỏng đoán tự nhiên là chữ “và” bên trái vẫn là “và”. Không phải vậy. Nó cũng đổi:
(a ∧ b) → c ≡ (a → c) ∨ (b → c)
Chuỗi ngắn: ¬(a ∧ b) ∨ c ≡ (¬a ∨ ¬b) ∨ c ≡ (¬a ∨ c) ∨ (¬b ∨ c) ≡ (a → c) ∨ (b → c). Bước giữa chỉ viết c hai lần, điều này hợp lệ vì p ∨ p ≡ p.
Vậy cả hai dạng đều đổi từ nối của chúng. Và cụ thể:
(a ∧ b) → c không phải là (a → c) ∧ (b → c)
đây là đáp án sai hấp dẫn nhất trong chủ đề này. Một hàng là đủ bác bỏ nó: lấy a = 1, b = 0, c = 0. Khi đó a ∧ b là 0, nên vế trái đúng. Nhưng a → c là 0, nên vế phải sai. Hai đáp án khác nhau trong cùng một hàng nghĩa là không tương đương.
Bác bỏ chỉ cần một hàng#
Chứng minh hai thứ tương đương nghĩa là kiểm tra mọi hàng. Chứng minh chúng không tương đương chỉ cần đúng một hàng mà chúng khác nhau. Hãy nói to hàng đó thay vì vẫy tay về phía cái bảng.
Hãy viết như thế này: “Tại a = 1, b = 0, c = 0 vế trái đúng và vế phải sai, nên hai vế không tương đương.” Một dòng, đầy đủ, xong.
Đó là cùng sự không đối xứng như “mọi” so với “có một”. Một sự tương đương là khẳng định về mọi tổ hợp, nên một phản ví dụ duy nhất phá hủy nó.
Những chỗ dễ sai#
- Trả lời bằng sai phương pháp. Nếu đề nói “dùng bảng chân trị”, hãy lập bảng. Nếu đề nói “dùng các luật De Morgan”, hãy viết chuỗi. Đúng nhưng sai định dạng thì không phải là đúng.
- Không nêu tên các luật. Một chuỗi các phép viết lại không giải thích không phải là chứng minh. Mỗi dòng đều phải có lý do.
- Giữ nguyên từ nối. ¬(a ∨ b) là ¬a ∧ ¬b, không phải ¬a ∨ ¬b. De Morgan đổi nó, và phép đổi đó tạo ra mọi kết quả ở trên.
- Đoán rằng (a ∧ b) → c tách bằng chữ “và”. Nó tách bằng chữ “hoặc”. Hãy kiểm tra tại a = 1, b = 0, c = 0.
- Thiếu hàng. n chữ cái nghĩa là 2ⁿ hàng. Ba chữ cái là tám, không phải sáu. Một bảng thiếu một hàng không chứng minh được gì.
- Vội vàng ở các hàng mà không có gì xảy ra. Khi nửa đầu của một mệnh đề nếu–thì sai, cả mệnh đề đúng. Những hàng dễ nhất trên trang, và hay bị điền sai nhất.
- Bác bỏ bằng cả một cái bảng. Đúng nhưng lãng phí. Hãy nêu đúng một hàng.
Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí
Luyện tập Toán rời rạc miễn phí và dùng được khi không có mạng — các bài luyện chọn theo chủ đề về sự tương đương, bảng chân trị và các luật có tên.
Luyện các sự tương đương logic →Câu hỏi thường gặp#
Bảng chân trị cần bao nhiêu hàng?
Hai lũy thừa số chữ cái khác nhau. Hai chữ cái cho bốn hàng, ba chữ cho tám, bốn chữ cho mười sáu. Thiếu một hàng làm chứng minh mất hiệu lực, vì một sự tương đương là khẳng định về mọi tổ hợp đúng và sai có thể có.
Vì sao chữ “hoặc” bên trái biến thành chữ “và” bên phải?
Vì bước đầu tiên viết lại mệnh đề nếu–thì thành “không (a hoặc b), hoặc c”, và De Morgan biến “không (a hoặc b)” thành “không a và không b”. Chữ “và” xuất hiện ngay ở đó và tồn tại đến hết chuỗi, cho ra (a → c) và (b → c).
(a và b) → c có giống (a → c) và (b → c) không?
Không. Nó bằng (a → c) hoặc (b → c), với chữ “hoặc”. Lấy a đúng, b sai, c sai. Khi đó a và b sai, nên vế trái tự động đúng. Nhưng a → c sai, nên vế phải sai. Chỉ một hàng đó là đủ kết luận.
Khi nào tôi nên dùng chuỗi các luật thay vì bảng chân trị?
Dùng bảng khi có ít chữ cái và bạn muốn chắc chắn mà không cần nhớ. Dùng chuỗi khi có nhiều chữ cái — năm chữ cái là ba mươi hai hàng — hoặc khi câu hỏi yêu cầu rõ các luật có tên. Một chuỗi còn cho bạn thấy vì sao hai mệnh đề trùng nhau, điều mà bảng không bao giờ làm được.
Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.