Bảng Karnaugh

Bảng Karnaugh, hay còn gọi là sơ đồ Karnaugh hoặc biểu đồ Veitch, là công cụ giúp đơn giản hóa các biểu thức đại số Boolean. Điều đặc biệt của bảng Karnaugh là mỗi ô chỉ thay đổi một biến, và các hàng cũng như cột được sắp xếp theo nguyên lý mã Gray.

Những thông tin lịch sử và thuật ngữ

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

Ứng dụng trong lý thuyết Boolean

Thông thường, việc đơn giản hóa biểu thức hàm Boolean đòi hỏi nhiều phép toán phức tạp, nhưng bìa Karnaugh có thể giúp làm điều này dễ dàng hơn.

Các vấn đề có thể được giải quyết gồm:

• Bảng Karnaugh tận dụng khả năng nhận diện mẫu của con người để kết hợp các hạng tử nhằm tạo ra biểu thức tối giản nhất.
• Bảng Karnaugh giúp nhanh chóng phát hiện và loại bỏ các tranh chấp điều khiển (race hazard) tiềm ẩn, điều mà các phương trình Boolean không thể làm được.
• Bảng Karnaugh là công cụ hữu ích để đơn giản hóa các phương trình với tối đa sáu biến, nhưng với nhiều biến hơn, việc nhận diện mẫu trở nên khó khăn hơn cho con người.
• Đối với các bài toán có nhiều hơn sáu biến, thường sử dụng các biểu thức Boolean thay vì bảng Karnaugh.
• Bảng Karnaugh cũng rất hữu ích trong việc giảng dạy về hàm Boolean và kỹ thuật đơn giản hóa.

Đặc điểm

Bảng Karnaugh có thể xử lý nhiều biến, nhưng hiệu quả nhất khi có từ 2 đến 6 biến. Mỗi biến có hai trạng thái cho mỗi trạng thái của các biến khác trong hệ thống. Bảng Karnaugh được thiết kế theo dạng lưới, trong đó các trạng thái được sắp xếp sao cho chỉ có một biến thay đổi giữa các ô kề nhau, giúp giảm thiểu tranh chấp.

Khi sử dụng bảng Karnaugh để tối ưu hóa hàm, người dùng sẽ 'bao phủ' các ô chứa số 1 bằng các hình chữ nhật, với số ô trong mỗi hình là lũy thừa bậc n của cơ số 2 (ví dụ: 2 biến với 4 ô dùng bảng 2x2, 3 biến với 8 ô dùng bảng 2x4, 4 biến với 16 ô dùng bảng 4x4, v.v.). Sau khi bao phủ các số 1, người dùng sẽ xác định các biến không thay đổi trong vùng bao phủ để tạo ra các hạng tử tương ứng. Số 1 đại diện cho biến và số 0 đại diện cho phủ định của biến. Lặp lại quy trình này cho tất cả các số 1 sẽ cho ra hàm tương đương.

Số 0 cũng có thể được sử dụng để tối ưu hóa hàm theo cách tương tự như số 1. Quy trình giống như vậy nhưng với số 0 đại diện cho biến chính và số 1 đại diện cho phủ định của biến trong các tích tổng.

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

Sơ đồ Venn với bốn tập hợp được ký hiệu A, B, C, và D tương ứng với các minterm của bảng Karnaugh với 4 biến như trong hình bên phải.

• Ví dụ, biến A trên bảng Karnaugh tương ứng với tập A trong sơ đồ Venn;
• Ví dụ, minterm m0 trên bảng Karnaugh tương ứng với khu vực 0 trong sơ đồ Venn

Minterm m9, với ABCD=1001, biểu thị vị trí chỉ có tập A và D giao nhau. Do đó, mỗi minterm xác định một phép giao duy nhất trong bốn tập hợp.

Sơ đồ Venn có thể chứa số lượng tập hợp vô hạn và vẫn tương thích với bảng Karnaugh. Khi số lượng tập hợp và biến tăng lên, độ phức tạp của cả sơ đồ Venn và bảng Karnaugh cũng tăng theo.

Kích thước của bảng

Trên một bảng Karnaugh với $n$ biến, một số hạng Boole với $k$ biến, bảng sẽ là hình chữ nhật với diện tích $2^n$. Kích thước thông thường của bảng là 2 biến với diện tích 2x2; 3 biến với diện tích 2x4; và 4 biến với diện tích 4x4 (xem chi tiết dưới đây).

• Bảng Karnaugh 2 biến
• Bảng Karnaugh 3 biến
• Bảng Karnaugh 4 biến

Ví dụ minh họa

Xem xét hàm logic với bốn biến (theo hệ nhị phân, có thể có tối đa 16 tổ hợp):

$f(A,B,C,D)=E(0,2,3,8,9,10,11)$

Các giá trị trong $E$ đại diện cho các minterm có trong bảng Karnaugh (những hàng có giá trị đầu ra là một trong bảng chân trị).

Bảng chân trị

Dựa trên các minterm đã xác định, chúng ta có thể xây dựng bảng chân lý.

#	$A$	$B$	$C$	$D$	$f(A,B,C,D)$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

Bảng Karnaugh

Với các biến đầu vào có thể kết hợp theo 16 cách khác nhau, bảng Karnaugh sẽ có 16 ô. Cách sắp xếp hiệu quả nhất là dùng lưới 4x4.

Các giá trị nhị phân trên bảng biểu diễn kết quả đầu ra của hàm với mọi tổ hợp đầu vào. Chúng ta đặt số 0 ở góc trên bên trái vì $f=0$

{displaystyle f=0} khi $A=0$, $B=0$, $C=0$, $D=0$. Ngược lại, chúng ta ghi số 1 ở góc dưới bên phải vì $A=1$, $B=0$, $C=1$, $D=0$ dẫn đến $f=1$. Lưu ý rằng các giá trị được sắp xếp theo mã Gray, vì vậy một biến chỉ thay đổi khi chuyển từ ô này sang ô kế cận.

Khi bảng Karnaugh đã được hoàn thành, bước tiếp theo là xác định các số hạng tối giản để sử dụng trong biểu thức cuối cùng. Những số hạng này được xác định bằng cách bao phủ các số 1 trên bảng. Các vùng bao phủ phải là hình chữ nhật và diện tích của chúng phải là lũy thừa của hai (như 1, 2, 4, 8, …). Những hình chữ nhật này phải lớn nhất có thể mà không chứa số 0. Các vùng tốt nhất được đánh dấu bằng các đường màu xanh lá, đỏ và xanh biển.

Đối với mỗi vùng bao phủ, chúng ta xác định các biến có cùng trạng thái trong toàn bộ vùng đó. Đối với vùng đầu tiên (màu đỏ), chúng ta có các biến sau:

• Biến $A$ luôn có giá trị (1) trong toàn bộ vùng, vì vậy nó được đưa vào số hạng của vùng màu đỏ.
• Biến $B$ không giữ trạng thái đồng nhất (chuyển từ 1 sang 0), nên bị loại.
• $C$ không thay đổi, luôn là 0.
• $D$ thay đổi trạng thái.

Do đó, số hạng đầu tiên trong biểu thức Boole sẽ là $A\stackrel{¯<!--\; ¯\; -->}{C}$.

Với vùng màu xanh lá, ta thấy rằng biến $A$ và $B$ không thay đổi trạng thái, trong khi $D$ và $C$ có sự thay đổi. Do $B$ là 0 và cần được phủ định, số hạng thứ hai sẽ là $A\stackrel{¯<!--\; ¯\; -->}{B}$.

Tương tự, hình chữ nhật màu xanh biển cho ra số hạng $BC\stackrel{¯<!--\; ¯\; -->}{D}$. Cuối cùng, biểu thức rút gọn là: $A\stackrel{¯<!--\; ¯\; -->}{C}+A\stackrel{¯<!--\; ¯\; -->}{B}+BC\stackrel{¯<!--\; ¯\; -->}{D}$.

Nối qua cạnh.

Mạng lưới có thể được nối qua cạnh, nghĩa là các hình chữ nhật có thể bao phủ các cạnh, ví dụ như $A\stackrel{¯<!--\; ¯\; -->}{D}$ vẫn là một số hạng hợp lệ, dù không thuộc tập hợp tối thiểu, nó bao phủ các minterm 8, 10, 12 và 14.

Một số hạng khó nhận diện hơn là $\stackrel{¯<!--\; ¯\; -->}{B}\stackrel{¯<!--\; ¯\; -->}{D}$ bao phủ bốn góc của bảng, bao gồm các minterm 0, 2, 8 và 10.

Đảo ngược (Tìm POS (Product of Sums))

Việc đảo ngược hàm được thực hiện tương tự như trước, bằng cách nhóm các giá trị 0 lại với nhau.

Ba số hạng bao phủ phần đảo nằm trong vùng màu xám với các khung màu khác nhau là:

• Màu nâu—$\stackrel{¯<!--\; ¯\; -->}{A}\stackrel{¯<!--\; ¯\; -->}{B}$
• Màu vàng—$\stackrel{¯<!--\; ¯\; -->}{A}\stackrel{¯<!--\; ¯\; -->}{C}$
• Màu xanh biển—$BCD$

Kết quả sẽ là:

$\stackrel{¯<!--\; ¯\; -->}{F}=\stackrel{¯<!--\; ¯\; -->}{A}\stackrel{¯<!--\; ¯\; -->}{B}+\stackrel{¯<!--\; ¯\; -->}{A}\stackrel{¯<!--\; ¯\; -->}{C}+BCD$

Sử dụng Định lý De Morgan, ta có thể xác định các tích tổng sau đây:

$\stackrel{¯<!--\; ¯\; -->}{\stackrel{¯<!--\; ¯\; -->}{F}}=\stackrel{¯<!--\; ¯\; -->}{\stackrel{¯<!--\; ¯\; -->}{A}\stackrel{¯<!--\; ¯\; -->}{B}+\stackrel{¯<!--\; ¯\; -->}{A}\stackrel{¯<!--\; ¯\; -->}{C}+BCD}$

$F=\left(A+B\right)\left(A+C\right)\left(\stackrel{¯<!--\; ¯\; -->}{B}+\stackrel{¯<!--\; ¯\; -->}{C}+\stackrel{¯<!--\; ¯\; -->}{D}\right)$

Có thể tùy chỉnh

Bảng Karnaugh giúp tối ưu hóa dễ dàng các hàm mà chứa các điều kiện 'tùy ý' (tức là các đầu vào mà người thiết kế không quan tâm đến giá trị đầu ra), vì các điều kiện 'tùy ý' có thể được bao hàm trong một khung lớn hơn mà không cần quan tâm đến số cụ thể. Chúng thường được biểu thị bằng dấu gạch/X thay vì số. Giá trị có thể là '0', '1', hoặc dấu gạch ngang/X tùy thuộc vào việc dùng '0' hay '1' để rút gọn bảng Karnaugh. Nếu 'tùy ý' không giúp ích trong việc rút gọn, hãy dùng dấu gạch ngang/X.

Ví dụ bên phải tương tự như ví dụ trước, nhưng minterm 15 được thay thế bằng tùy ý. Điều này cho phép số hạng đỏ mở rộng xuống dưới, từ đó loại bỏ hoàn toàn số hạng xanh lá.

Phương trình rút gọn mới sẽ là:

$F=A+BC\stackrel{¯<!--\; ¯\; -->}{D}.$

Lưu ý rằng số hạng đầu tiên là $A$, không phải $A\stackrel{¯<!--\; ¯\; -->}{C}$. Trong trường hợp này, giá trị tùy ý đã loại bỏ một số hạng (xanh lá); tối ưu hóa số hạng khác (đỏ); và giải quyết xung đột điều khiển (màu vàng như sẽ thấy trong phần tiếp theo).

Tương tự, khi trường hợp nghịch đảo không cần bao phủ minterm 15, minterm 7 có thể được bao phủ bởi $\left(A+\stackrel{¯<!--\; ¯\; -->}{D}\right)$ thay vì $\left(\stackrel{¯<!--\; ¯\; -->}{B}+\stackrel{¯<!--\; ¯\; -->}{C}+\stackrel{¯<!--\; ¯\; -->}{D}\right)$ với kết quả tương đương.

Tranh chấp điều khiển

Bảng Karnaugh rất hữu ích trong việc phát hiện và loại bỏ tranh chấp điều khiển. Điều này dễ dàng nhận thấy khi sử dụng bảng Karnaugh, vì tranh chấp điều khiển có thể xuất hiện khi di chuyển giữa hai vùng liền kề nhưng rời rạc trên bảng.

• Trong ví dụ trên, một tranh chấp điều khiển tiềm tàng xảy ra khi C là 1, D là 0, A là 1, và B thay đổi từ 1 sang 0 (di chuyển từ trạng thái xanh nước biển sang xanh lá cây). Lỗi có thể xảy ra khi không có số hạng cụ thể nào bao phủ trong phương trình, dẫn đến sự chuyển đổi đột ngột thành 0.
• Một lỗi khó nhận ra hơn là khi D là 0 và A, B đều là 1, với C thay đổi từ 1 sang 0 (di chuyển từ xanh sang đỏ). Lỗi này bao quanh từ đỉnh đến cuối bảng.

Sự xuất hiện của các lỗi này phụ thuộc vào thực tế vật lý khi triển khai, và việc chúng ta có cần chú ý đến chúng hay không còn tùy thuộc vào ứng dụng cụ thể.

Trong trường hợp này, thêm một số hạng $A\stackrel{¯<!--\; ¯\; -->}{D}$ sẽ giải quyết tranh chấp điều khiển tiềm ẩn, kết nối giữa các trạng thái đầu ra xanh lá cây và xanh nước biển hoặc xanh nước biển và đỏ: đây là khu vực màu vàng.

Mặc dù số hạng này có vẻ dư thừa theo lý thuyết tĩnh của hệ thống, nhưng sự dư thừa như vậy, hoặc theo cách gọi khác, thường cần thiết để đảm bảo hiệu suất động không gặp tranh chấp.

Tương tự, một số hạng bổ sung $\left(A+\stackrel{¯<!--\; ¯\; -->}{D}\right)$ cần được thêm vào trong trường hợp nghịch đảo để loại bỏ một khả năng tranh chấp điều khiển khác.

Bảng có 2 biến

Dưới đây là các trường hợp có thể xuất hiện trên bảng Karnaugh 2x2 với 2 biến. Các minterm trong từng bảng đóng vai trò trong hàm phương trình tối giản $\sum <!--\; \sum \; -->m\left(\right)$ mà không có tranh chấp điều khiển (xem phần trước).

• E(); K=0
• E(1); K=A'B'
• E(2); K=AB'
• E(3); K=A'B
• E(4); K=AB
• E(1,2); K=B'
• E(1,3); K=A'
• E(1,4); K=A'B' + AB
• E(2,3); K=AB' + A'B
• E(2,4); K=A
• E(3,4); K=B
• E(1,2,3); K=A' + B'
• E(1,2,4); K=A + B'
• E(1,3,4); K=A' + B
• E(2,3,4); K=A + B
• E(1,2,3,4); K=1

Các vấn đề liên quan đến bảng Karnaugh

Bảng Karnaugh thường trở nên phức tạp và khó nhìn khi số lượng biến tăng lên. Một quy tắc chung là bảng Karnaugh hiệu quả nhất với tối đa bốn biến và không nên dùng cho nhiều hơn sáu biến. Đối với các biểu thức có nhiều biến, giải thuật Quine-McCluskey có thể được áp dụng. Hiện nay, quá trình tối giản thường được thực hiện bằng máy tính, với Trình tối giản luận lý Espresso là phần mềm tiêu chuẩn.

Phần mềm

Có nhiều phần mềm hỗ trợ giải bài toán bìa Karnaugh. Một lựa chọn miễn phí cho cả hệ điều hành Linux và Windows là GKMap.

• Rút gọn mạch điện
• Trình rút gọn luận lý Espresso
• Đừng nhầm bìa Karnaugh (ở trên) với đồ thị chu trình Carnot của động cơ nhiệt.
• Danh sách các chủ đề liên quan đến đại số Boole
• Giải thuật Quine-McCluskey
• Sơ đồ Venn

• Karnaugh, Maurice (tháng 11 năm 1953). “The Map Method for Synthesis of Combinational Logic Circuits”. Transactions of American Institute of Electrical Engineers part I. 72 (9): 593–599.
• Katz, Randy (1994). Contemporary Logic Design. The Benjamin/Cummings Publishing Company. tr. 70-85. doi:10.1016/0026-2692(95)90052-7. ISBN 0-8053-2703-7.
• William W. Wickes 1968, Logic Design with Integrated Circuits, John Wiley & Sons, Inc., NY. No ISBN. Library of Congress Catalog Number: 68-21185. Wickes mô tả sơ đồ Veitch như là “một cải tiến của sơ đồ Venn, với các hình tròn được thay thế bằng các hình vuông và sắp xếp theo dạng ma trận. Sơ đồ Veitch gán các minterm vào các ô vuông. Karnaugh đã gán các giá trị 1 và 0 cho các ô và nhãn của chúng và phát triển hệ thống đánh số phổ biến hiện nay (xem trang 36–49).

Liên kết ngoài

• Phần mềm bìa Karnaugh Lưu trữ 2010-01-08 tại Wayback Machine - Công cụ miễn phí cho bìa Karnaugh.
• Java applet để giải bìa Karnaugh với 5 biến.
• Karma 3, bộ công cụ tổng hợp logic bao gồm cả bìa Karnaugh, tối giản Quine-McCluskey, BDDs, xác suất, mô-đun giảng dạy và nhiều hơn nữa. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
• Phần mềm bìa Karnaugh dựa trên trình duyệt Lưu trữ 2007-12-14 tại Wayback Machine
• Phần mềm bìa Karnaugh đầu tiên, 1999, miễn phí, có thể tải về
• Karnaugh Maps 101
• Karnaugh Maps - ví dụ đã làm Lưu trữ 2010-03-29 tại Wayback Machine
• Tối giản hàm Boolean (bìa Karnaugh) Lưu trữ 2010-01-23 tại Wayback Machine
• Phần mềm tối giản bìa Karnaugh mã nguồn mở
• Xây dựng công thức bằng cách sử dụng bìa Karnaugh để xác định nếu các hình chữ nhật có thể chồng lên nhau, bài viết chi tiết của Herbert Glarner
• Phần mềm Palm miễn phí: Công cụ đơn giản hóa hàm Boolean v1.0 Lưu trữ 2010-01-22 tại Wayback Machine

Ứng dụng

• Sử dụng bìa Karnaugh để điều khiển đèn giao thông Lưu trữ ngày 02-11-2013 tại Wayback Machine