Bìa Karnaugh là một bảng ô vuông, mỗi ô ứng với một dòng của bảng chân trị, xếp sao cho hai ô cạnh nhau chỉ khác đúng một biến. Nhờ cách xếp đó, muốn rút gọn một biểu thức logic chỉ cần khoanh các nhóm 1, 2, 4, 8 ô chứa số 1 nằm liền nhau: mỗi nhóm thành một tích ngắn, cộng các tích lại là ra biểu thức gọn. Phương pháp do Maurice Karnaugh ở Bell Labs đưa ra năm 1953, dùng tốt nhất cho hàm có từ 2 tới 4 biến.
Vì sao cần một tấm bìa
Rút gọn bằng đại số Boole thì đúng, nhưng khó: phải nhìn ra đặt nhân tử nào, thêm bớt hạng tử nào. Hai người làm cùng một bài có thể ra hai kết quả, và không ai chắc kết quả đã gọn nhất chưa.
Ý tưởng then chốt nằm ở một phép biến đổi rất quen: x·y + x·y' = x·(y + y') = x. Hai tích chỉ khác nhau ở một biến (một bên có y, một bên có y') thì gộp lại được và biến đó biến mất. Bìa Karnaugh chỉ làm một việc: xếp các tích sao cho những cặp "chỉ khác một biến" nằm cạnh nhau, để mắt người nhìn ra ngay thay vì phải dò.
Năm 1952 Edward Veitch đã đề xuất một dạng sơ đồ tương tự; năm sau Karnaugh cải tiến cách xếp và cách dùng, và tên ông gắn với phương pháp tới nay.
Cách dựng bìa: thứ tự 00, 01, 11, 10
Ký hiệu: A, B, C, D là các biến (0 hoặc 1); · là "và", + là "hoặc", dấu phẩy trên A' là "không A". Mỗi tổ hợp giá trị đánh số bằng cách đọc như số nhị phân; với ba biến, A là bit cao nhất: số thứ tự = 4A + 2B + C. Ví dụ A = 1, B = 0, C = 1 là ô số 5, gọi là m5. Viết f = Σm(0, 2, 5) nghĩa là f bằng 1 ở các ô 0, 2, 5 và bằng 0 ở các ô còn lại.
Bìa ba biến có 2 hàng (A = 0, A = 1) và 4 cột cho BC. Điểm mấu chốt là thứ tự cột: 00, 01, 11, 10, không phải 00, 01, 10, 11. Đi từ 01 sang 11 chỉ đổi một bit; nếu xếp 01 rồi 10 thì đổi hai bit một lúc, và cặp ô cạnh nhau không còn gộp được. (Thứ tự này là mã Gray hai bit.)
Thêm một quy ước quan trọng: mép trái và mép phải được coi là kề nhau (cột 10 và cột 00 chỉ khác một bit), mép trên và mép dưới cũng vậy. Có thể hình dung tấm bìa cuộn tròn lại.
Luật khoanh nhóm
- Chỉ khoanh ô chứa 1 (và ô "không quan tâm" nếu có, xem bên dưới), không bao giờ khoanh ô 0.
- Mỗi nhóm là hình chữ nhật có số ô là luỹ thừa của 2: 1, 2, 4, 8, 16. Không có nhóm 3 ô, 6 ô.
- Nhóm nằm ngang hoặc dọc, được vắt qua mép; không khoanh chéo.
- Nhóm càng lớn càng tốt: nhóm 2ᵏ ô loại được k biến.
- Số nhóm càng ít càng tốt; một ô được nằm trong nhiều nhóm nếu điều đó giúp nhóm to hơn.
- Mỗi ô 1 phải nằm trong ít nhất một nhóm.
Đọc một nhóm: biến nào giữ nguyên giá trị trên mọi ô của nhóm thì ở lại (giữ 1 thì viết A, giữ 0 thì viết A'); biến nào có lúc 0 lúc 1 thì bỏ.
Ba ví dụ giải đầy đủ
Ví dụ 1: hàm ba biến
Rút gọn f(A, B, C) = Σm(0, 2, 4, 5, 6). Điền bìa (dòng là A, cột là BC theo thứ tự Gray; số trong ngoặc là số ô):
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 (m0) | 0 (m1) | 0 (m3) | 1 (m2) |
| 1 | 1 (m4) | 1 (m5) | 0 (m7) | 1 (m6) |
Khoanh nhóm:
- Nhóm 4 ô vắt mép: cột 00 và cột 10 (kề nhau qua mép), cả hai hàng — m0, m2, m4, m6. Trên nhóm này A thay đổi, B thay đổi, chỉ C luôn bằng 0. Nhóm cho C'.
- Ô m5 còn lẻ: ghép với m4 bên trái thành nhóm 2 ô. Trên đó A = 1, B = 0, C đổi. Nhóm cho A·B'.
Kết quả: f = C' + A·B'. Từ năm tích ba biến (15 ký hiệu biến) còn lại ba ký hiệu.
Kiểm đủ tám ô với f = C' + A·B':
| Ô | A B C | C' | A·B' | f tính được | f đề cho |
|---|---|---|---|---|---|
| m0 | 0 0 0 | 1 | 0 | 1 | 1 |
| m1 | 0 0 1 | 0 | 0 | 0 | 0 |
| m2 | 0 1 0 | 1 | 0 | 1 | 1 |
| m3 | 0 1 1 | 0 | 0 | 0 | 0 |
| m4 | 1 0 0 | 1 | 1 | 1 | 1 |
| m5 | 1 0 1 | 0 | 1 | 1 | 1 |
| m6 | 1 1 0 | 1 | 0 | 1 | 1 |
| m7 | 1 1 1 | 0 | 0 | 0 | 0 |
Ví dụ 2: hàm bốn biến và nhóm bốn góc
Rút gọn f(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10). Số ô = 8A + 4B + 2C + D. Bìa 4 × 4, cả hàng (AB) lẫn cột (CD) đều theo thứ tự 00, 01, 11, 10:
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 (m0) | 1 (m1) | 0 (m3) | 1 (m2) |
| 01 | 0 (m4) | 1 (m5) | 0 (m7) | 0 (m6) |
| 11 | 0 (m12) | 0 (m13) | 0 (m15) | 0 (m14) |
| 10 | 1 (m8) | 1 (m9) | 0 (m11) | 1 (m10) |
- Bốn góc m0, m2, m8, m10: hàng trên và hàng dưới kề nhau qua mép, cột trái và cột phải cũng vậy, nên bốn góc là một nhóm 4. Trên đó B = 0 và D = 0, A và C thay đổi: B'·D'.
- Nhóm 4 m0, m1, m8, m9 (hai cột đầu, hàng 00 và 10): B = 0, C = 0: B'·C'.
- Ô m5: hàng xóm của nó là m1, m4, m7, m13; chỉ m1 là ô 1. Nhóm 2 ô m1, m5: A = 0, C = 0, D = 1, B thay đổi: A'·C'·D.
Kết quả: f = B'·C' + B'·D' + A'·C'·D. Bảy tích bốn biến (28 ký hiệu) còn 7 ký hiệu.
Thử lại bằng vài ô cụ thể, cả ô 1 lẫn ô 0:
- m10 (A = 1, B = 0, C = 1, D = 0): B'·D' = 1 ⇒ f = 1. Đúng, m10 có trong đề.
- m5 (0, 1, 0, 1): B'·C' = 0, B'·D' = 0, A'·C'·D = 1 ⇒ f = 1. Đúng.
- m4 (0, 1, 0, 0): cả ba tích đều bằng 0 (hai tích đầu cần B = 0, tích cuối cần D = 1) ⇒ f = 0. Đúng, m4 không có trong đề.
- m11 (1, 0, 1, 1): B'·C' = 0 vì C = 1; B'·D' = 0 vì D = 1; A'·C'·D = 0 vì A = 1 ⇒ f = 0. Đúng.
Ví dụ 3: ô "không quan tâm" giúp gọn hơn nữa
Một mạch nhận một chữ số thập phân 0–9 viết bằng 4 bit (mã BCD) và bật đèn khi chữ số ≥ 5. Sáu mã 10–15 không bao giờ xuất hiện, nên ở đó f muốn bằng gì cũng được — ghi X, gọi là ô "không quan tâm". Đề: f = Σm(5, 6, 7, 8, 9), không quan tâm ở 10–15.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 0 | 0 |
| 01 | 0 | 1 (m5) | 1 (m7) | 1 (m6) |
| 11 | X | X | X | X |
| 10 | 1 (m8) | 1 (m9) | X | X |
- Coi mọi X là 1: hai hàng 11 và 10 thành nhóm 8 ô, chỉ A giữ nguyên (= 1): A.
- m5, m7 cùng m13, m15 (cột 01 và 11, hàng 01 và 11): B = 1, D = 1: B·D.
- m6, m7 cùng m14, m15 (cột 11 và 10, hàng 01 và 11): B = 1, C = 1: B·C.
Kết quả: f = A + B·D + B·C, hay A + B·(C + D). Kiểm với mọi chữ số: 0, 1, 2, 3 có A = 0, B = 0 ⇒ 0. Số 4 = 0100: A = 0, B = 1 nhưng C = D = 0 ⇒ 0. Số 5 = 0101: B·D = 1. Số 6 = 0110: B·C = 1. Số 7 = 0111: 1. Số 8 = 1000 và 9 = 1001: A = 1. Đúng hết. Nếu không tận dụng X, kết quả phải là A·B'·C' + A'·B·D + A'·B·C — dài gần gấp đôi.
Lỗi hay gặp
| Lỗi | Hậu quả | Cách tránh |
|---|---|---|
| Xếp cột 00, 01, 10, 11 | Gộp nhầm hai ô khác nhau hai biến, kết quả sai | Luôn viết thứ tự 00, 01, 11, 10 cho cả hàng và cột |
| Khoanh nhóm 3 hoặc 6 ô | Không đọc ra được một tích | Chỉ nhóm 1, 2, 4, 8, 16 ô hình chữ nhật |
| Quên vắt mép, quên bốn góc | Đúng nhưng chưa gọn nhất | Luôn soát cột đầu – cột cuối, hàng đầu – hàng cuối |
| Khoanh nhóm chỉ toàn X | Thêm hạng tử thừa | X chỉ dùng để mở rộng nhóm có chứa ô 1 |
| Đánh số ô sai thứ tự biến | Điền 1 vào sai chỗ ngay từ đầu | Ghi rõ "số ô = 8A + 4B + 2C + D" trước khi điền |
Bìa cũng dùng được theo chiều ngược lại: khoanh các ô 0 để ra dạng tích các tổng, khi dạng đó gọn hơn hoặc khi mạch cần dựng bằng cổng NOR. Với 5, 6 biến, bìa phải chồng nhiều lớp và mắt người dễ sót; từ đó trở lên người ta dùng thuật toán Quine – McCluskey hoặc phần mềm rút gọn.
Bài tập
- Rút gọn f(A, B, C) = Σm(1, 3, 5, 7). — Đáp án: bốn ô cùng có C = 1: f = C.
- Rút gọn f(A, B, C) = Σm(2, 3, 6, 7). — Đáp án: f = B.
- Rút gọn f(A, B, C) = Σm(0, 4). — Đáp án: m0 = 000, m4 = 100, A đổi: f = B'·C'.
- Rút gọn f(A, B, C) = Σm(1, 2, 3). — Đáp án: hai nhóm (1, 3) và (2, 3): f = A'·C + A'·B = A'·(B + C).
- Rút gọn f(A, B, C, D) = Σm(0, 2, 8, 10). — Đáp án: bốn góc: f = B'·D'.
Dùng vào đâu
- Thi Kỹ thuật số, Điện tử số: bìa Karnaugh 3–4 biến, có ô không quan tâm, là dạng bài gần như chắc chắn có.
- Lập trình: một chuỗi if lồng nhau nhiều điều kiện có thể viết thành bảng chân trị rồi rút gọn bằng bìa, giảm điều kiện thừa và lộ ra trường hợp bị bỏ quên.
- Logic học: tấm bìa là một cách nhìn trực quan luật x·y + x·y' = x — gộp hai trường hợp chỉ khác nhau ở một điều kiện không ảnh hưởng tới kết quả.
Câu hỏi thường gặp
Bìa Karnaugh là gì?
Bìa Karnaugh là bảng ô vuông biểu diễn bảng chân trị của một hàm logic, xếp sao cho hai ô kề nhau chỉ khác một biến. Khoanh các nhóm ô 1 kề nhau giúp rút gọn biểu thức logic nhanh và ít sai hơn biến đổi đại số.
Vì sao bìa Karnaugh xếp theo thứ tự 00, 01, 11, 10?
Vì theo thứ tự này, hai cột kề nhau (kể cả cột đầu và cột cuối) chỉ khác đúng một bit. Chỉ những ô khác nhau một biến mới gộp được, nên xếp kiểu 00, 01, 10, 11 sẽ cho kết quả sai.
Một nhóm trên bìa Karnaugh được có bao nhiêu ô?
Số ô phải là luỹ thừa của 2: 1, 2, 4, 8, 16, và nhóm phải là hình chữ nhật (được vắt qua mép bìa). Nhóm 2 ô loại 1 biến, nhóm 4 ô loại 2 biến, nhóm 8 ô loại 3 biến.
Ô "không quan tâm" (X) trên bìa Karnaugh dùng thế nào?
Ô X là tổ hợp đầu vào không bao giờ xảy ra hoặc không ảnh hưởng kết quả. Có thể coi X là 1 khi nó giúp nhóm lớn hơn, coi là 0 khi không cần; nhưng không khoanh nhóm chỉ gồm toàn X.
Bìa Karnaugh dùng được cho bao nhiêu biến?
Thuận tiện nhất cho 2 tới 4 biến. Với 5, 6 biến vẫn làm được bằng cách chồng nhiều bìa nhưng dễ sót nhóm; nhiều biến hơn thì dùng thuật toán như Quine – McCluskey hoặc phần mềm.
