Bản đồ Karnaugh — Hướng dẫn rút gọn K-Map

Bản đồ Karnaugh, hay K-map, là một bảng lưới dùng để rút gọn biểu thức Boolean mà không cần làm quá nhiều phép biến đổi đại số bằng tay. Bạn điền các giá trị đầu ra từ bảng chân trị lên lưới, nhóm các ô $1$ liền kề, rồi viết một hạng tử đơn giản hơn cho mỗi nhóm.

Điều kiện sử dụng rất quan trọng: K-map thực tế nhất với các hàm nhỏ, thường có hai, ba hoặc bốn biến. Khi số biến tăng lên, bản đồ sẽ khó đọc hơn và các phương pháp khác thường phù hợp hơn.

Bản Đồ Karnaugh Thể Hiện Điều Gì

K-map chứa cùng thông tin như bảng chân trị, nhưng các ô được sắp theo thứ tự Gray code thay vì thứ tự nhị phân thông thường. Cách sắp xếp đó khiến các ô kề nhau chỉ khác đúng một biến.

Sự khác nhau ở một biến đó chính là điểm cốt lõi. Nếu hai ô liền kề đều là $1$, biến thay đổi có thể bị loại khỏi hạng tử đã rút gọn.

Cách Nhóm Ô Giúp Loại Biến

Quy tắc trực quan này xuất phát từ các đồng nhất thức Boolean như

$$XY + X\overline{Y} = X$$

Hai hạng tử này chỉ khác nhau ở $Y$, nên $Y$ bị triệt tiêu và phần chung $X$ được giữ lại. K-map cho phép bạn nhìn ra trực tiếp mẫu triệt tiêu đó trên lưới.

Ví Dụ Về Bản Đồ Karnaugh

Giả sử

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

Điều này có nghĩa là $F=1$ với các minterm $1$, $3$, $4$, $5$ và $7$.

Với K-map $3$ biến, dùng $A$ cho các hàng và $BC$ cho các cột theo thứ tự Gray code $00$, $01$, $11$, $10$:

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

Hãy bắt đầu với nhóm hợp lệ lớn nhất. Bốn ô $1$ ở hai cột giữa tạo thành một nhóm. Trong bốn ô đó, $C=1$ giữ nguyên còn $A$ và $B$ thay đổi, nên nhóm này được rút gọn thành

$$C$$

Vẫn còn một ô $1$ chưa được phủ: minterm $4$, tức là $(A,B,C)=(1,0,0)$. Hãy ghép nó với minterm kề bên là $5$, tức $(1,0,1)$.

Trong cặp này, $A=1$ và $B=0$ giữ nguyên còn $C$ thay đổi, nên cặp đó được rút gọn thành

$$A\overline{B}$$

Vì vậy biểu thức rút gọn là

$$F(A,B,C) = C + A\overline{B}$$

Biểu thức ngắn hơn này tương đương với danh sách minterm ban đầu.

Quy Tắc Cho Các Nhóm Hợp Lệ Trong K-Map

Dùng các nhóm có kích thước là lũy thừa của hai: $1$, $2$, $4$, $8$, v.v.

Hãy dùng các nhóm hợp lệ lớn nhất có thể. Nhóm càng lớn thường loại được càng nhiều biến.

Hãy nhớ rằng bản đồ có tính quấn vòng. Mép trái kề với mép phải, và mép trên kề với mép dưới.

Các ô chéo nhau không được xem là kề nhau.

Được phép chồng lấp nếu điều đó giúp tạo ra một nhóm lớn hơn hoặc đơn giản hơn.

Những Lỗi Thường Gặp Với Bản Đồ Karnaugh

Dùng Thứ Tự Nhị Phân Thông Thường

Nếu bạn gán nhãn hàng hoặc cột là $00$, $01$, $10$, $11$, thì quan hệ kề nhau sẽ sai. K-map phải dùng thứ tự Gray code để các ô kề nhau chỉ khác đúng một bit.

Tạo Nhóm Ba Ô

Nhóm gồm ba ô không bao giờ hợp lệ. Kích thước nhóm phải là lũy thừa của hai.

Bỏ Qua Tính Kề Nhau Qua Mép

Một số cách rút gọn tốt nhất dùng các ô nằm ở hai mép đối diện của bản đồ. Nếu bạn quên quy tắc quấn vòng, đáp án thường sẽ dài hơn mức cần thiết.

Ép Mỗi Ô $1$ Chỉ Thuộc Đúng Một Nhóm

Đó không phải là quy tắc. Dùng lại một ô đôi khi là cách tốt nhất để tạo nhóm lớn hơn và biểu thức cuối ngắn hơn.

Khi Nào Dùng Bản Đồ Karnaugh

K-map rất phổ biến trong logic số và các môn nhập môn kỹ thuật máy tính vì nó biến việc rút gọn Boolean thành một quá trình trực quan. Nó đặc biệt hữu ích khi bạn muốn có biểu thức tổng các tích đơn giản hơn trước khi vẽ hoặc triển khai mạch logic.

Nó cũng rất tốt để xây dựng trực giác. Ngay cả khi phần mềm xử lý các thiết kế lớn hơn, việc học K-map vẫn giúp bạn dễ thấy vì sao một số hạng tử Boolean có thể gộp lại còn những hạng tử khác thì không.

Thử Một Bài Tương Tự

Hãy thử tự rút gọn $F(A,B,C)=\sum m(0,2,4,6,7)$. Vẽ bản đồ, tạo các nhóm hợp lệ lớn nhất trước, rồi chỉ giữ lại các biến không đổi trong mỗi nhóm.

Nếu muốn đi thêm một bước, hãy thử một phiên bản có giá trị don't-care và chỉ dùng chúng khi chúng giúp bạn tạo được một nhóm hợp lệ lớn hơn.