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.

Ví dụ về bìa Karnaugh

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

Chuyển các minterm sang bìa Karnaugh

4 sơ đồ Venn với các số (0-15) và các tên (A-D) nối với nhau trên sơ đồ minterm

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ó ${\displaystyle n}$biến, một số hạng Boole gồm ${\displaystyle k}$ biến thì bìa sẽ là một hình chữ nhật tương ứng có diện tích ${\displaystyle 2^{n}}$. 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).

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

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

Các giá trị trong ${\displaystyle E}$ 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:

#	${\displaystyle A}$	${\displaystyle B}$	${\displaystyle C}$	${\displaystyle D}$	${\displaystyle 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ì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.

Bìa K cho thấy các minterm và ô bao phủ các minterm mong muốn

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ì ${\displaystyle f=0}$ khi ${\displaystyle A=0}$, ${\displaystyle B=0}$, ${\displaystyle C=0}$, ${\displaystyle D=0}$. tương tự chúng ra đánh dấu góc phải bên dưới là 1 vì ${\displaystyle A=1}$, ${\displaystyle B=0}$, ${\displaystyle C=1}$, ${\displaystyle D=0}$ cho ra ${\displaystyle f=1}$. 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 ${\displaystyle A}$ 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 ${\displaystyle B}$ không ngữ nguyên được trạng thái (chuyển từ 1 sang 0), và do đó sẽ bị loại trừ.
• ${\displaystyle C}$ không đổi, nó lúc nào cũng là 0.
• ${\displaystyle D}$ thay đổi.

Do đó số hạng đầu tiên của biểu thức Boole sẽ là ${\displaystyle A{\overline {C}}}$.

Đối với vùng bao phủ màu xanh lá chúng ta nhìn thấy ${\displaystyle A}$ và ${\displaystyle B}$ giữ nguyên trạng thái, còn ${\displaystyle D}$ thay đổi, ${\displaystyle C}$ thay đổi. ${\displaystyle B}$ 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à ${\displaystyle A{\overline {B}}}$.

Tương tự, hình chữ nhật màu xanh biển cho ra số hạng ${\displaystyle BC{\overline {D}}}$. Cuối cùng biểu thức thu được là: ${\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}}$.

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 đó ${\displaystyle A{\overline {D}}}$ 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à ${\displaystyle {\overline {B}}\,{\overline {D}}}$ 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—${\displaystyle {\overline {A}}\,{\overline {B}}}$
• vàng—${\displaystyle {\overline {A}}\,{\overline {C}}}$
• xanh biển—${\displaystyle BCD}$

Nó sẽ cho ra:

${\displaystyle {\overline {F}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}$

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

${\displaystyle {\overline {\overline {F}}}={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}}$

${\displaystyle F=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)}$

Tùy định

Minterm 15 bỏ qua và thay thế bằng một tùy định, nó sẽ bỏ hoàn toàn số hạng xanh lá cây nhưng làm chặt chẽ thêm số hạng đảo màu xanh nước biển

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:

${\displaystyle F=A+BC{\overline {D}}.}$

Chú ý rằng số hạng đầu tiên chỉ là ${\displaystyle A}$ chứ không phải ${\displaystyle A{\overline {C}}}$. 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 ${\displaystyle \left(A+{\overline {D}}\right)}$ thay vì ${\displaystyle \left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)}$ với kết quả tương tự.

Tranh đoạt điều khiển

Bìa K ở trên có số hạng ${\displaystyle A{\overline {D}}}$ được thêm vào để tránh 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 ${\displaystyle A{\overline {D}}}$ 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 ${\displaystyle \left(A+{\overline {D}}\right)}$ 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 ${\textstyle \sum m()}$ không có tranh đoạt đ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 đề 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

• 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 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

Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Bìa Karnaugh.

• 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 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 Lưu trữ 2007-12-14 tại Wayback Machine
• The first Karnaugh Map software, 1999, freeware, downloadable
• Karnaugh Maps 101
• Karnaugh Maps - a worked example Lưu trữ 2010-03-29 tại Wayback Machine
• Minimisation of Boolean Functions(Karnaugh Map) Lưu trữ 2010-01-23 tại Wayback Machine
• 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 Lưu trữ 2010-01-22 tại Wayback Machine

Ứng dụng

• Dùng bìa Karnaugh để quản lý đèn giao thông Lưu trữ 2013-11-02 tại Wayback Machine