Bài tập tối thiểu hóa hàm logic bằng bảng Karnaugh

Mạch logic tổ hợp là mạch logic mà tín hiệu ra của mạch chỉ phụ thuộc vào tín hiệu đầu vào, không phụ thuộc vào thứ tự, thời gian tác động của tín hiệu vào.

• Không có nhớ.
• Không có yếu tố thời gian.
• Cùng một tổ hợp tín hiệu vào, tín hiệu ra là duy nhất.
• Mạch vòng hở.

2. Tổng hợp mạch logic tổ hợp

2.1. Dạng tổng chuẩn đầy đủ

• Chỉ quan tâm đến tổ hợp các giá trị của biến làm cho hàm có giá trị 1. Mỗi tổ hợp này tương ứng với một tích của tất cả các biến.
• Trong mỗi tích, các biến có giá trị 1 thì được biểu diễn ở trạng thái thường, các biến có giá trị 0 thì được biểu diễn ở trạng thái phủ định.
• Hàm logic dạng tổng chuẩn đầy đủ sẽ là tổng các tích đó.

Ví dụ: Ta có thể biểu diễn hàm f(x, y) = Σ(0,3) như sau:

2.2. Dạng tích chuẩn đầy đủ

• Chỉ quan tâm đến tổ hợp các giá trị của biến làm cho hàm có giá trị 0. Mỗi tổ hợp này tương ứng với một tổng của tất cả các biến.
• Trong mỗi tổng, các biến có giá trị 0 thì được biểu diễn ở trạng thái thường, các biến có giá trị 1 thì được biểu diễn ở trạng thái phủ định.
• Hàm logic dạng tích chuẩn đầy đủ sẽ là tích các tổng đó.

Ví dụ: Ta có thể biểu diễn hàm f(x,y) = Π(1,2) như sau:

3. Tối thiểu hóa hàm logic

3.1. Phương pháp đại số

• Dựa vào các hệ thức cơ bản để giải.
• Nhược điểm: không biết rõ đã tối thiểu hay chưa.

Ví dụ: Rút gọn hàm f(a,b)

3.2. Phương pháp bìa Karnaugh

Biểu diễn hàm đã cho dưới dạng bảng Karnaugh: có n biến thì lập 2n ô.

Nhóm các ô có giá trị 1 và không xác định ở cạnh nhau hoặc đối xứng
nhau thành các vòng:

• Số ô trong 1 vòng là 2m, m lớn nhất có thể.
• Các vòng có thể giao nhau nhưng không được trùm lên nhau.
• Các vòng phải phủ hết các ô có giá trị 1.
• Số vòng phải là tối thiểu.

Mỗi vòng tương ứng với tích các biến có giá trị không thay đổi trong vòng đó với biểu diễn tương ứng với giá trị của các biến.

Hàm rút gọn bằng tổng các tích tương ứng với các vòng.

• Hàm f có 3 biến a, b, c nên ta lập bảng Karnaugh có 23 = 8 ô.
• Các tổ hợp làm cho hàm f = 1 là: 000, 010, 101, 110, 111. Ta điền giá trị 1 vào ô trong bảng Karnaugh tương ứng với các tổ hợp trên.
• Nhóm các ô sao cho số lượng ô trong nhóm là một số luỹ thừa của 2. Các ô trong nhóm có giá trị hàm cùng bằng 1.
• Mỗi nhóm (vòng) tương ứng với tích các biến có giá trị không đổi (các biến có giá trị thay đổi thì bỏ đi), ghi lại tích các biến (biến có giá trị 1 thì biểu diễn ở dạng thường, biến có giá trị 0 thì biểu diễn ở dạng phủ định).
• Hàm rút gọn là tổng các tích trên.

3.3. Phương pháp Quine Mc.Clusky

Bước 1: Biểu diễn các tổ hợp biến theo mã nhị phân (phủ định = 0).

Bước 2: Sắp xếp tăng dần và nhóm các tổ hợp biến theo số chữ số 1 có trong mã nhị phân tương ứng.

Bước 3: Ghép từng tổ hợp của nhóm thứ i với từng tổ hợp của nhóm thứ i + 1

• Hai tổ hợp ghép được nếu chỉ khác nhau 1 bit ở cùng 1 vị trí.
• Điền dấu “-” vào vị trí khác đó.
• Đánh dấu “√” vào tổ hợp đã ghép.

Bước 4: Lặp lại bước 2 và bước 3 cho đến khi không còn ghép được nữa.

Bước 5: Lập bảng phủ tối thiểu: ghi lại các tổ hợp không có dấu “√”.

Bước 6: Tìm tập con nhỏ nhất. Hàm tối thiểu là tổng các tích đã được lựa chọn trong bảng phủ.

Lần 1:

• Nhóm có 1 bit 1 là 0001 và 0100; nhóm có 2 bit 1 là 0011, 0101, 1010, 1100; nhóm có 3 bit 1 là 1101; nhóm có 4 bit 1 là 1111.
• Tìm và ghép từng tổ hợp của nhóm 1 với từng tổ hợp của nhóm 2, ta được các nhóm (1,3), (1,5), (4,5), (4,12). Đánh dấu “√” vào các tổ hợp đã ghép 1, 4, 3, 5, 12.
• Tìm và ghép từng tổ hợp của nhóm 2 với từng tổ hợp của nhóm 3, ta được các nhóm (5,13) và (12,13). Tiếp tục đánh dấu “√” vào các tổ hợp 13.
• Tìm và ghép từng tổ hợp của nhóm 3 với từng tổ hợp của nhóm 4, ta được nhóm (13,15). Tiếp tục đánh dấu “√” vào các tổ hợp 15.

→ Sau lần 1 ta được các tổ hợp đã ghép có 1 dấu “-“.

Lần 2:

• Nhóm có 1 bit 1 là 00-1, 0-01, 010-, -100; nhóm có 2 bit 1 là -101, 110-; nhóm có 3 bit 1 là 11-1;
• Tìm và ghép từng tổ hợp của nhóm 1 với từng tổ hợp của nhóm 2 có cùng vị trí “-“, ta được các nhóm (4,5,12,13) và (4,12,5,13). Đánh dấu “√” vào các tổ hợp đã ghép (4,5), (12,13), (4,12), (5,13).

→ Sau lần 2 ta được các tổ hợp đã ghép có 2 dấu “-“.

Hai nhóm (4,5,12,13) và (4,12,5,13) thực chất là 1 tổ hợp nên ta không thể ghép được nữa. Các tổ hợp chưa được ghép là: 1010, 00-1, 0-01, 11-1, -10-.

• Biểu diễn lại các tổ hợp chưa ghép dưới dạng tích các biến và xếp theo cột bên trái bảng phủ.
• Đánh dấu “+” vào ô nếu tổ hợp chưa được ghép là một phần con của tổ hợp ban đầu.

• Gạch đường màu đỏ nếu trong cột chỉ có 1 dấu “+”.

• Gạch đường màu xanh vào các hàng có dấu “+” bị gạch đỏ.

• Gạch đường màu vàng vào các cột có dấu “+” bị gạch xanh.
• Khi tất cả các cột đã được gạch thì ta được kết quả là các tổ hợp bị gạch bên trái bảng, nghĩa là chỉ cần 4 tổ hợp là đủ để biểu biễn các tổ hợp ban đầu.

4. Thiết kế mạch tổ hợp

• Bước 1: Phân tích bài toán đã cho để gắn hàm và biến, xác lập mối quan hệ logic giữa hàm và các biến đó.
• Bước 2: Lập bảng trạng thái tương ứng.
• Bước 3: Dùng các phương pháp để tối thiểu hóa biểu thức đầu ra.
• Bước 4: Vẽ mạch điện thể hiện.

Ví dụ: Bồn chứa nước được cấp bởi 2 bơm L1 và L2. Bơm chạy là mức cao (1), bơm dừng là mức thấp (0). A, B, C là 3 công tắc phao. Khi nước dâng lên tác động vào phao qui ước là 1, phao ở trạng thái bình thường là 0. Hãy thiết kế mạch theo yêu cầu sau: mức nước dưới A thì L1 và L2 cùng hoạt động, mức nước trên A dưới B thì L2 hoạt động, mức nước trên B dưới C thì L1 hoạt động, mức nước trên C thì cả 2 dừng.