1. Bìa Karnaugh là gì
Bìa Karnaugh là bảng chân trị được vẽ lại thành một lưới. Maurice Karnaugh giới thiệu nó tại Bell Labs năm 1953 như một cách rút gọn mạch chuyển mạch bằng mắt, và đến nay nó vẫn là cách nhanh nhất để tối giản một hàm Boole nhỏ bằng tay: không cần đại số, không cần thuộc định luật, chỉ cần những hình chữ nhật.
Mỗi ô của bìa chứa một dòng của bảng chân trị. Điều khiến bìa hơn hẳn một phép sắp xếp lại là thứ tự đặt các dòng ấy: những ô nằm cạnh nhau chỉ khác nhau đúng một biến.
Chỉ tính chất đó thôi đã làm hết mọi việc. Nếu hai ô kề nhau cùng đúng thì biến thay đổi giữa chúng không thể là thứ làm biểu thức đúng: nó bị loại bỏ, và một số hạng phủ cả hai ô. Rút gọn trở thành việc vẽ những hình chữ nhật lớn nhất có thể.
2. Vì sao thứ tự các cột trông lạ
Các cột của bìa Karnaugh không đếm 00, 01, 10, 11 mà chạy 00, 01, 11, 10 - mã Gray phản xạ, một thứ tự trong đó mỗi giá trị chỉ khác giá trị kế tiếp một bit. Đếm theo nhị phân sẽ đặt 01 cạnh 10, vốn khác nhau hai bit, và khi đó các ô kề nhau chẳng nói lên điều gì.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Các mép cũng là hàng xóm của nhau. Cột đầu và cột cuối chỉ khác nhau một biến, hàng trên cùng và hàng dưới cùng cũng vậy, nên một nhóm có thể chạy vượt qua mép này và tiếp tục ở mép kia - đó là lý do bốn góc của bìa bốn biến hợp thành một nhóm duy nhất. Thật ra bìa Karnaugh được vẽ trên một mặt xuyến; tờ giấy phẳng chỉ là cho tiện.
3. Gộp các số 1
Để đọc được tổng các tích tối giản trên bìa, hãy phủ mọi ô mang số 1 bằng các nhóm hình chữ nhật, theo bốn quy tắc:
- Một nhóm là hình chữ nhật gồm 1, 2, 4, 8 … ô - mỗi cạnh là một lũy thừa của hai.
- Một nhóm có thể vòng qua mép bìa, theo chiều ngang, chiều dọc, hoặc cả hai.
- Các nhóm có thể chồng lên nhau. Phủ một ô hai lần không mất gì; bỏ sót một ô lại làm đổi hàm.
- Hãy làm mỗi nhóm lớn hết mức có thể, rồi dùng càng ít nhóm càng tốt sao cho phủ hết các số 1.
Mỗi nhóm cho một số hạng. Cách đọc là hỏi xem biến nào giữ nguyên trên toàn nhóm: những biến ấy có mặt trong số hạng - để nguyên ở chỗ chúng bằng 1, phủ định ở chỗ chúng bằng 0 - còn mọi biến thay đổi đều bị loại. Nhóm hai ô mất một biến, nhóm bốn ô mất hai, nhóm tám ô mất ba. Biểu thức tối giản là phép tuyển của các số hạng.
4. Một ví dụ có lời giải
Lấy (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Bìa của nó có bốn biến: A và B theo hàng, C và D theo cột.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Hai nhóm phủ hết các số 1. Nhóm thứ nhất là khối bốn ô nằm ở hai hàng có A = 0 và hai cột có C = 1: bên trong nó cả B lẫn D đều thay đổi nên bị loại, số hạng là ¬A ∧ C. Nhóm thứ hai là trọn hàng có A và B cùng bằng 1, trải khắp bốn cột: C và D thay đổi dọc theo hàng, còn lại A ∧ B.
Vậy dạng tối giản là (¬A ∧ C) ∨ (A ∧ B). Số hạng thứ ba của biểu thức ban đầu, B ∧ C ∧ D, đã biến mất: mọi ô nó phủ đều đã được một trong hai nhóm phủ rồi. Đó chính là luật hấp thụ khi ta nhìn thấy được nó.
5. Nguyên tố và nguyên tố thiết yếu
Nhóm không thể mở rộng thêm được gọi là một hạng nguyên tố. Liệt kê các hạng nguyên tố là nửa dễ của bài toán; chọn giữ lại những hạng nào mới là nửa hay sai.
Nếu một ô nào đó chỉ được đúng một hạng nguyên tố phủ thì hạng ấy là thiết yếu: không dạng tối giản nào bỏ nó đi được, vì không còn gì khác phủ ô đó. Hãy lấy các hạng thiết yếu trước, rồi phủ phần còn lại bằng ít nhóm nhất có thể trong số các nhóm còn lại.
Cách tham lam - cứ lấy nhóm lớn nhất còn lại - nghe hấp dẫn nhưng không phải lúc nào cũng đúng. Trên một bảng phủ tuần hoàn, nơi không hạng nào là thiết yếu và mỗi ô đều được phủ hai lần, lựa chọn tham lam có thể kết thúc với nhiều hơn một số hạng so với đáp án tốt nhất. Bìa trên trang này thay vào đó duyệt hết mọi lựa chọn còn lại, việc mà ở bốn biến gần như không tốn gì.
6. Gộp các số 0 để thay thế
Mọi điều ở trên cũng đúng y như vậy với các số 0. Hãy phủ chúng bằng những hình chữ nhật ấy, đọc mỗi nhóm với các biến bị phủ định - biến bằng 1 trên toàn nhóm sẽ xuất hiện dưới dạng phủ định, biến bằng 0 thì để nguyên - rồi nối các nhóm bằng ∧ thay cho ∨.
Kết quả là một tích các tổng: phép hội của những phép tuyển, sai đúng tại những ô mà biểu thức sai, và do đó đúng ở mọi nơi khác. Dạng nào ngắn hơn là tùy hàm - công thức có ít số 1 thì tổng các tích ngắn, còn ít số 0 thì tích các tổng ngắn - nên trước khi chọn, đáng để đọc cả hai trên bìa.
7. Bìa lớn hơn và các ô tùy định
Năm và sáu biến có thể vẽ thành hai hoặc bốn bìa bốn biến chồng lên nhau, coi các ô cùng vị trí ở những lớp kề nhau là kề nhau. Cách đó chạy được, nhưng tính kề - thứ làm nên vẻ trực quan của phương pháp - giờ là điều phải nhớ chứ không còn nhìn thấy. Xa hơn nữa, thuật toán Quine-McCluskey làm đúng công việc ấy dưới dạng bảng: nó chính là hình thức máy móc của phép gộp này, và cũng là thứ chạy phía sau các bìa ở đây.
Thiết kế phần cứng thêm một ý nữa. Một số tổ hợp đầu vào không bao giờ xảy ra - chữ số thập phân mã hóa nhị phân không bao giờ là 1010 - nên người thiết kế không quan tâm mạch làm gì với chúng. Những ô đó được đánh dấu X và có thể đọc là giá trị nào cũng được, miễn làm nhóm lớn hơn. Bìa trong máy tính này dựng từ một công thức, vốn gán giá trị cho mọi phép gán, nên không ô nào là tùy định.
8. Tự thử xem
Nhập vào máy tính một biểu thức từ hai đến bốn biến, bìa của nó sẽ được vẽ ngay dưới bảng chân trị, mỗi nhóm khoanh bằng một màu riêng và dạng tối giản viết bên dưới. Chuyển sang tích các tổng để thấy các số 0 được gộp thay vì các số 1.