Bìa Karnaugh

Bìa Karnaugh, hay sơ đồ Các-nô, biểu đồ Veitch, là một công cụ để thuận tiện trong việc đơn giản các biểu thức đại số Boole. Bìa Karnaugh độc đáo ở chỗ giữa các ô chỉ có sự thay đổi của một biến mà thôi; hay nói cách khác, các hàng và cột được sắp xếp theo nguyên lý mã Gray.

== Lịch sử và thuật ngữ ==
Đượ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 2x2, 3 biến 8 ô dùng bìa 2x4, 4 biến 16 ô dùng bìa 4x4, 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ó formula_1biến, một số hạng Boole gồm formula_2 biến thì bìa sẽ là một hình chữ nhật tương ứng có diện tích formula_3. Bìa có kích thước thông thường là 2 biến với diện tích 2x2; 3 biến là 2x4; và 4 biến là 4x4 (xem ở dưới).

== 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):

Các giá trị trong formula_5 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ị).

===Bảng chân lý===
Sử dụng các minterm đã được định nghĩa, bảng chân trị có thể được tạo ra:
===Bìa===
Các biến nhập vào có thể được kết hợp theo 16 cách khác nhau, do đó bìa Karnaugh của chúng ta sẽ có 16 vị trí. Cách thuận tiện nhất để sắp xếp cái này là trong lưới 4x4.

Các số nhị phân trong bìa đại diện cho các kết quả đầu ra của hàm đối với bất kỳ tổ hợp đầu vào cho trước nào. Chúng ta viết 0 ở góc trên bên trái của bìa vì formula_6 khi formula_7, formula_8, formula_9, formula_10. tương tự chúng ra đánh dấu góc phải bên dưới là 1 vì formula_11, formula_8, formula_13, formula_10 cho ra formula_15. Chú ý rằng các giá trị được sắp xếp theo dạng mã Gray, do đó một cách chính xác một biến thay đổi trong hai biến đối với hai ô kế cận.

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

Đối với mỗi vùng bao phủ này chúng ta tìm những biến có cùng trạng thái trong mỗi ô trong vùng bao phủ. Đối với nhóm đầu tiên (màu đỏ) chúng ta tìm thấy:
- Biến formula_16 có cùng trạng thái (1) trong toàn bộ vùng, do đó nó sẽ được đưa vào số hạng tương ứng với vùng màu đỏ.
- Biến formula_17 không ngữ nguyên được trạng thái (chuyển từ 1 sang 0), và do đó sẽ bị loại trừ.
- formula_18 không đổi, nó lúc nào cũng là 0.
- formula_19 thay đổi.
Do đó số hạng đầu tiên của biểu thức Boole sẽ là formula_20.

Đối với vùng bao phủ màu xanh lá chúng ta nhìn thấy formula_16 và formula_17 giữ nguyên trạng thái, còn formula_19 thay đổi, formula_18 thay đổi. formula_17 là 0 và phải được phủ định trước khi ghi vào số hạng. Do đó số hạng thứ hai sẽ là formula_26.

Tương tự, hình chữ nhật màu xanh biển cho ra số hạng formula_27. Cuối cùng biểu thức thu được là: formula_28.

===Nối qua cạnh===
Mạng lưới được nối qua cạnh, có nghĩa là các hình chữ nhật có thể bao xung quanh các cạnh, do đó formula_29 là một số hạng đúng, mặc dù không phải là một phần của tập hợp tối thiểu-nó bao phủ các minterm 8, 10, 12 & 14.

Có lẽ số hạng bao phủ xung quanh khó thấy nhất là formula_30 bao phủ bốn góc-nó sẽ phủ các minterm 0, 2, 8, 10.

===Nghịch đảo (Tìm POS (Product of Sums))===
Nghịch đảo của hàm được giải theo cách tương tự, bằng cách nhóm các số 0.

Ba số hạng bao phủ phần đảo nằm trong ô màu xám với các khung có màu khác nhau:
- nâu—formula_31
- vàng—formula_32
- xanh biển—formula_33

Nó sẽ cho ra:

Bằng cách sử dụng Định luật De Morgan, tích các tổng có thể xác định được:

===Tùy định===
Bìa Karnaugh cũng cho phép sự tối thiểu hóa dễ dàng các hàm mà bản chân trị có cả các điều kiện "tùy định" (tức là tập các đầu vào mà người thiết kế không quan tâm đến giá trị đầu ra là gì) vì các điều kiện "tùy định" có thể được bao hàm trong một khung để khiến cho nó lớn hơn mà không nhất thiết phải quan tâm đó là số nào. Chúng thường được vẽ trên bìa bằng dấu gạch/X thay vì số. Giá trị của nó có thể là "0", "1", hoặc gạch ngang/X tùy vào người đó đang dùng "0" hay "1" để rút gọn bìa K hơn nữa. Nếu "tùy định" không giúp ích gì trong việc rút gọn bìa K, thì hãy sử dụng gạch ngang/X.

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

Nó sẽ cho ra phương trình rút gọn mới:

Chú ý rằng số hạng đầu tiên chỉ là formula_16 chứ không phải formula_20.
Trong trường hợp này, giá trị tùy định đã bỏ đi một số hạng (xanh lá); rút gọn số hạng khác (đỏ); và bỏ được tranh đoạt điều khiển (màu vàng như sẽ thấy trong phần dưới).

tương tự, vì trường hợp nghịch đảo không còn phải bao phủ minterm 15, minterm 7 có thể bị bao phủ bằng formula_40 thay vì formula_41 với kết quả tương tự.

==Tranh đoạt điều khiển==
Bìa Karnaugh hữu ích trong việc tìm ra và loại bỏ tranh đoạt điều khiển. Bị dễ dàng nhìn ra bằng cách dùng bìa Karnaugh, vì một tranh đoạt điều khiển có thể tồn tại khi di chuyển giữa một cặp liền kề, nhưng rời rạc, những vùng được khoanh trên bìa.

- Ở ví dụ trên, một tranh đoạt điều khiển tiềm ẩn tồn tại khi C là 1 và 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 trạng thái xanh lá cây). Trong trường hợp này, ngõ ra được định nghĩa là 1 không đổi, nhưng vì sự chuyển đổi này không được một số hạng cụ thể nào bao phủ trong phương trình, khả năng xảy ra một "lỗi" (đột ngột chuyển qua 0 trong thời gian ngắn) tồn tại.
- Một lỗi khó nhìn ra hơn là khi D là 0 và A và B cùng là 1, với C thay đổi từ 1 sang 0 (di chuyển từ trạng thái xanh sang trạng thái đỏ). Trong trường hợp này lỗi bao xung quanh từ đỉnh đến cuối bìa.

Dù những lỗi này có xảy ra hay không phụ thuộc vào bản chất vật lý khi hiện thực, và việc chúng ta có cần quan tâm về chúng hay không tùy thuộc vào ứng dụng.

Trong trường hợp này, một số hạng cộng thêm formula_29 sẽ loại bỏ tranh đoạt điều khiển tiềm ẩn, nối giữa trạng thái ngõ ra xanh lá cây và xanh nước biển hoặc trạng thái ngõ ra xanh nước biển và đỏ: nó là vùng màu vàng.

Số hạng là dư thừa nói theo luận lý tĩnh của hệ thống, nhưng sự dư thừa như vậy, hay theo cách nói đồng thuận, thường là cần thiết để đảm bảo hiệu suất động không có tranh đoạt.

tương tự, một số hạng cộng thêm formula_40 phải được thêm vào trường hợp nghịch đảo để loại bỏ một khả năng tranh đoạt điều khiển khác.

==Bìa có 2 biến==
Dưới là tất cả những trường hợp có thể của bìa Karnaugh 2x2 có 2 biến.
Liệt kê theo từng bìa là các minterm đóng vai trò là hàm của phương trình rút gọn formula_44 không có tranh đoạt điều khiển ("xem phần trước").
== Các vấn đề với bìa Karnaugh ==
Bìa Karnaugh nói chung trở nên ngày càng lộn xộn hơn và khó nhìn khi thêm vào càng nhiều biến. Một nguyên tắc chung đó là bìa Karnaugh sẽ làm việc tốt với tối đa bốn biến, và không nên được dùng với số biến nhiều hơn sáu. Đối với những biểu thức có số lượng biến lớn, có thể dùng giải thuật Quine-McCluskey. Nói chung ngày nay quy trình rút gọn được thực hiện bằng máy tính, trong đó Trình rút gọn luận lý Espresso đã trở thành chương trình rút gọn tiêu chuẩn.

== Phần mềm ==
Có nhiều phần mềm để giải bài toán bìa Karnaugh. Có một phần mềm miễn phí dành cho Linux và Windows là GKMap.

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

==Tham khảo==
- William W. Wickes 1968, "Logic Design with Integrated Circuits", John Wiley & Sons, Inc., NY. No ISBN. Library of Congress Catalog Number: 68-21185. Wickes describes the Veitch diagram as "a refinement of the Venn diagram in that circles are replaced by squares and arranged in a form of matrix. The Veitch diagram labels the squares with the minterms. Karnaugh assigned 1s and 0s to the squares and their labels and deduced the numbering scheme in common use (cf pp. 36–49).

==Liên kết ngoài==
- Phần mềm bìa Karnaugh - Công cụ miễn phí cho bìa Karnaugh.
- Java applet để giải bìa Karnaugh 5 biến.
- Karma 3, A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
- Browser based Karnaugh Map software
- The first Karnaugh Map software, 1999, freeware, downloadable
- Karnaugh Maps 101
- Karnaugh Maps - a worked example
- Minimisation of Boolean Functions(Karnaugh Map)
- Open source Karnaugh Maps minimization software
- Deriving a formula using Karnaugh Maps to determine if rectangles can overlap, an in-depth article by Herbert Glarner
- Free Palm-based Software: Boolean Function Simplification Tool v1.0

=== Ứng dụng ===
- Dùng bìa Karnaugh để quản lý đèn giao thông