RÚT GỌN HÀM LOGIC 2

Các tổ hợp biến có trong hàm logic hiện diện trong bảng Karnaugh dưới dạng các số 1 trong các ô, vậy việc gom thành nhóm các tổ hợp kề nhau được thực hiện theo qui tắc sau:

- Gom các số 1 kề nhau thành từng nhóm sao cho số nhóm càng ít càng tốt. Điều này có nghĩa là số số hạng trong kết quả sẽ càng ít đi.

- Tất cả các số 1 phải được gom thành nhóm và một số 1 có thể ở nhiều nhóm.

- Số số 1 trong mỗi nhóm càng nhiều càng tốt nhưng phải là bội của 2^k (mỗi nhóm có thể có 1, 2, 4, 8 ... số 1). Cứ mỗi nhóm chứa 2^k số 1 thì tổ hợp biến tương ứng với nhóm đó giảm đi k số hạng.

- Kiểm tra để bảo đảm số nhóm gom được không thừa.

- Kết quả cuối cùng được lấy như sau:

Hàm rút gọn là tổng của các tích: Mỗi số hạng của tổng tương ứng với một nhóm các số 1 nói trên và số hạng này là tích của các biến, biến A (hay A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {}) là thừa số của tích khi tất cả các số 1 của nhóm chỉ chứa trong phân nửa bảng trong đó biến A có giá trị 1 (hay 0). Nói cách khác nếu các số 1 của nhóm đồng thời nằm trong các ô của biến A và A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {} thì biến A sẽ được đơn giản. Hình dưới đây minh họa việc lấy các thừa số trong tích

Thí dụ đối với bảng (H 2.9) ta có kết quả như sau:

- Hàm Y là hàm 4 biến A,B,C,D

(H 2.9)

- Nhóm 1 chứa 2 số 1 (k=1), như vậy nhóm 1 sẽ còn 3 biến, theo hàng, 2 số 1 này ở 2 ô ứng với A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {}B và AB, biến A sẽ được đơn giản và theo cột thì 2 ô này ứng với tổ hợp .

Kết quả ứng với nhóm 1 là:

- Nhóm 2 chứa 4 số 1 (4=2² , k=2), như vậy nhóm 2 sẽ còn 2 biến, theo hàng, 4 số 1 này ở 2 ô ứng với tổ hợp A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {} và A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {}B, biến B sẽ được đơn giản và theo cột thì 4 ô này ứng với tổ hợp CD và C, cho phép đơn giản biến D .

Kết quả ứng với nhóm 2 là: A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {}C.

- Nhóm 3 chứa 4 số 1 (4=2² , k=2), như vậy nhóm 2 sẽ còn 2 biến, theo hàng, 4 số 1 này ở ô ứng với tổ hợp A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {}B, theo cột 4 số 1 này chiếm hết 4 cột nên 2 biến Cvà D được đơn giản.

Kết quả ứng với nhóm 3 là: A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {}B.

Và hàm Y rút gọn là: Y =

Dưới đây là một số thí dụ

Thí dụ 1 :Rút gọn hàmY =

(H 2.10)

(H 2.10)

cho

Thí dụ 2 :Rút gọn hàmY =f(A,B,C,D) = Σ(0,2,4,5,8,10,12,13) với A=MSB

(H 2.11)

(H 2.11) cho

Thí dụ 3 :Rút gọn hàm S cho bởi bảng sự thật:

Bảng Karnaugh: (H 2.12)

(H 2.12)

Kết quả

:

Để rút gọn các hàm nhiều biến (5 và 6 biến) người ta có thể dùng bảng Karnaugh 4 biến. Dưới đây là vài thí dụ:

Thí dụ 4: Rút gọn hàm f(A,B,C,D,E) =  (0,2,8,10,13,15,16,18,24,25,26,29,31) với (7,9,14,30) không xác định

• Trước nhất vẽ 2 bảng Karnaugh cho 4 biến BCDE, một ứng với A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {} và một với A
• Bảng ứng với A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {} dùng cho các số từ 0 đến 15
• Bảng ứng với A dùng cho các số từ 16 đến 31
• Nhóm các số 1 có cùng vị trí ở hai bảng, kết quả sẽ đơn giản biến A

- Nhóm các số 1 của từng bảng cho đến hết , kết quả được xác định như cách làm thông thường, nhớ A và A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {} trong từng nhóm (H 2.13).

(H 2.13)

nhóm (1) cho :

; (2) cho : BCE ; (3) cho :

Vậy

Thí dụ 5: Rút gọn hàm

f(A,B,C,D,E,F)=(2,3,6,7,8,9,12,13,14,17,24,25,28,29,30,40,41,44,45,46,56,57,59,60,61,63)

Tương tự như trên nhưng phải vẽ 4 bảng cho:

A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {} cho các số (0-15) ; A__ size 12{ { size 24{A} } cSup { size 8{"__"} } } {}B cho các số (16-31) ;

AB cho các số (48-63) và A cho các số (32-47).

(H 2.14)

Kết quả: (1) cho

;

Vậy:

Phương pháp Quine-Mc. Cluskey cũng dựa trên tính kề của các tổ hợp biến để đơn giản số biến trong các số hạng của biểu thức dạng tổng (minterm). Trong quá trình đơn giản này có thể xuất hiện các số hạng giống nhau mà ta có thể bỏ bớt được.

Phương pháp được thực hiện qua 2 giai đọan:

Giai đọan 1: Dựa trên tính kề của các tổ hợp biến để đơn giản số biến trong các số hạng của biểu thức dạng tổng (minterm).

Giai đọan 2: Kiểm tra và thực hiện việc tối giản .

Thí dụ dưới đây minh họa cho việc thực hiện phương pháp để rút gọn một hàm logic.

Thí dụ 1: Rút gọn hàm f(A,B,C,D) = Σ(1,2,4,5,6,10,12,13,14)

Giai đọan 1

- Các minterm được nhóm lại theo số số 1 có trong tổ hợp và ghi lại trong bảng theo thứ tự số 1 tăng dần:

Trong thí dụ này có 3 nhóm:

Nhóm chứa một số 1 gồm các tổ hợp 1, 2, 4

Nhóm chứa hai số 1 gồm các tổ hợp 5, 6, 10, 12

Nhóm chứa ba số 1 gồm các tổ hợp 13, 14

Bảng 1: