Lịch sử và thuật ngữ Bìa Karnaugh

Được Edward W. Veitch sáng tạo vào năm 1952, biểu đồ Veitch được Maurice Karnaugh, một kĩ sư viễn thông làm việc tại Bell Labs, phát triển thêm vào năm 1953. Từ đó bìa Karnaugh còn được gọi là bìa Karnaugh–Veitch.

Cách dùng trong luận lý Boole

Thông thường, để thu gọn biểu thức của một hàm Boole cần mất rất nhiều phép toán, nhưng người ta có thể sử dụng bìa Karnaugh để làm điều đó.

Những vấn đề có thể giải quyếtː

• Bìa Karnaugh tận dụng khả năng so trùng mẫu cực tốt của não người để quyết định số hạng nào nên được kết hợp với nhau để tạo ra biểu thức đơn giản nhất.
• Bìa Karnaugh cho phép nhận biết và loại trừ các tranh đoạt điều khiển (race hazard) tiềm ẩn một cách nhanh chóng, những thứ mà chỉ có các phương trình Boole không thể thực hiện được.
• Bìa Karnaugh là một phương tiện tuyệt vời để đơn giản hóa phương trình có tối đa sáu biến số, nhưng với nhiều biến hơn nó sẽ trở nên khó cho não bộ chúng ta nhận ra được những mẫu hình ảnh khác nhau.
• Đối với những bài toán liên quan đến nhiều hơn sáu biến, người ta thường giải quyết bằng cách dùng biểu thức Boole hơn là dùng bìa Karnaugh.
• Bìa Karnaugh cũng hữu ích trong việc giảng dạy về hàm Boole và rút gọn.

Tính chất

Bìa Karnaugh có thể có số biến bất kỳ, nhưng hoạt động tốt nhất trong khoảng giữa 2 và 6 biến. Mỗi biến có hai khả năng xảy ra với mỗi một khả năng của các biến khác trong hệ thống. Bìa Karnaugh được tổ chức sao cho tất cả các khả năng của hệ thống được sắp xếp theo dạng lưới và giữa hai ô kề nhau chỉ có một biến là thay đổi giá trị. Điều này cho phép giảm tranh đoạt.

Khi sử dụng bìa Karnaugh để tạo ra hàm rút gọn tối ưu, một người sẽ “phủ” các số 1 trên bìa bằng một hình chữ nhật “bao phủ”, trong đó có chứa một số ô bằng với lũy thừa bậc n của cơ số 2, với n là số biến (ví dụ, 2 biến 4 ô sẽ dùng bìa 2×2, 3 biến 8 ô dùng bìa 2×4, 4 biến 16 ô dùng bìa 4×4, v.v.). Khi người đó đã phủ các số 1, một số hạng trong tổng của các tích được tạo ra bằng cách tìm các biến không thay đổi trong toàn bộ vùng bao phủ, và số 1 nghĩa là chính biến đó và 0 là phủ định của biến. Lặp lại bước này cho tất cả các số đã phủ lên sẽ cho ra một hàm tương đương.

Người ta cũng có thể sử dụng số 0 (zero) để tạo ra một hàm rút gọn tối đa. Quy trình hoàn toàn y hệt như với số 1 trừ số được tạo ra là thừa số trong tích của các tổng – và 1 có nghĩa là phủ định của biến trong khi 0 nghĩa là chính nó.

Mỗi hình vuông trong bìa Karnaugh tương ứng với một minterm (và maxterm). Hình bên phải cho thấy vị trí của mỗi minterm trong bìa.

Một sơ đồ Venn gồm bốn tập hợp được gán nhãn A, B, C, và D — ở hình bên phải tương ứng với các minterm của bìa K 4 biến số như ở trên:

• Chẳng hạn biến A của bìa K tương ứng với tập A trong sơ đồ Venn;
• Chẳng hạn minterm m0 của bìa K tương ứng với vùng 0 trong sơ đồ Venn

Minterm m9 là ABCD=1001 tương ứng với nơi chỉ có tập A & D giao nhau. Do đó, một minterm nào đó sẽ xác định một phép giao độc nhất trong tất cả bốn tập hợp.

Sơ đồ Venn có thể bao gồm số tập hợp vô hạn và vẫn phù hợp với bìa Karnaugh tương ứng. Với số tập hợp và biến tăng lên, cả sơ đồ Venn và bìa Karnaugh cũng tăng lên về độ phức tạp khi vẽ và xử lý.

Kích thước của bìa

Trong một bìa Karnaugh có �biến, một số hạng Boole gồm � biến thì bìa sẽ là một hình chữ nhật tương ứng có diện tích 2�. Bìa có kích thước thông thường là 2 biến với diện tích 2×2; 3 biến là 2×4; và 4 biến là 4×4 (xem ở dưới).

• 

  Bìa 2 biến

• 

  Bìa 3 biến

• 

  Bìa 4 biến

Ví dụ

Xem xét hàm luận lý gồm bốn biến sau (theo nhị phân, sẽ có tối đa 16 tổ hợp):

�(�,�,�,�)=�(6,8,9,10,11,12,13,14)

Các giá trị trong � liệt kê các minterm trong bìa (có nghĩa là những hàng có đầu ra là một trong bảng chân trị).