RÚT GỌN HÀM LOGIC 3

- Mỗi tổ hợp trong một nhóm sẽ được so sánh với mỗi tổ hợp trong nhóm kế cận. Nếu 2 tổ hợp chỉ khác nhau một biến, ta có thể dùng biểu thức AB + A___ size 12{ {A} cSup { size 8{"___"} } } {}B = B để đơn giản được 1 biến. Biến đã đơn giản được thay bởi dấu -. Đánh dấu x vào các tổ hợp đã xét để tránh sai sót

Như vậy, tổ hợp thứ nhất của nhóm thứ nhất 0001 so sánh với tổ hợp thứ nhất của nhóm thứ hai 0101 vì chúng chỉ khác nhau ở biến B, vậy chúng có thể đơn giản thành 0-01. Hai số hạng 1 và 5 đã được gom lại thành nhóm (1,5) và được ghi vào bảng 2.

Tiếp tục so sánh tổ hợp 0001 này với các tổ hợp còn lại của nhóm 2 (0110, 1010, 1100), vì chúng khác nhau nhiều hơn 1 bit nên ta không được kết quả nào khác. Như vậy, ta đã so sánh xong tổ hợp thứ nhất, đánh dấu x trước tổ hợp này để ghi nhớ.

Công việc tiến hành tương tự cho nhóm thứ hai và thứ ba.

Lưu ý: Nhận xét về việc so sánh các tổ hợp với nhau ta thấy có thể thực hiện nhanh được bằng cách làm bài toán trừ 2 số nhị phân tương ứng của 2 tổ hợp, nếu kết quả là một số có trị = 2k (1, 2, 4,8 ...) thì 2 tổ hợp đó so sánh được và biến được đơn giản chính là biến có trọng số =2k (thí dụ 2 tổ hợp 1 và 5 có hiệu số là 4 nên đơn giản được biến B), nếu hiệu số ≠ 2k thì 2 tổ hợp đó không so sánh được, tức không có biến được đơn giản.

Kết quả cho bảng thứ hai

- Bảng thứ hai gồm các tổ hợp đã được rút gọn và chỉ còn lại 2 nhóm (giảm một nhóm so với bảng 1).

Bảng 2

Thực hiện công việc tương tự như trên với hai nhóm trong bảng thứ hai này, các số hạng sẽ được nhóm lại nếu chúng chỉ khác nhau một biến và có vị trí dấu - trùng nhau. Ta được bảng thứ 3.

Bảng 3:

Quan sát bảng thứ 3 ta thấy có các tổ hợp giống nhau, như vậy ta có thể lọai bỏ bớt các tổ hợp này và chỉ giữ lại một.

Kết quả của hàm rút gọn gồm tổng các số hạng tương ứng với các tổ hợp không gom thành nhóm trong các bảng đầu tiên, đó là tổ hợp (1,5) trong bảng 2, trị tương ứng là A___ size 12{ {A} cSup { size 8{"___"} } } {}C__ size 12{ {C} cSup { size 8{"__"} } } {}D với các tổ hợp còn lại trong bảng cuối cùng, đó là các tổ hợp (2,6 ; 10,14) mà trị tương ứng là C C__ size 12{ {C} cSup { size 8{"__"} } } {}D__ size 12{ {D} cSup { size 8{"__"} } } {} , (4,5 ; 12,13) cho B C__ size 12{ {C} cSup { size 8{"__"} } } {} và (4,6 ; 12,14) cho B D__ size 12{ {D} cSup { size 8{"__"} } } {} trong bảng 3. Vậy:

Đến đây, nếu quan sát các tổ hợp cho các kết quả trên, ta thấy các tổ hợp còn chứa các số hạng giống nhau (số 4 và số 12 chẳng hạn), như vậy kết quả trên có thể là chưa tối giản.

Giai đọan 2:

Để có thể rút gọn hơn nữa ta lập một bảng như sau:

Cột bên trái ghi lại các tổ hợp đã chọn được trong giai đoạn 1, các cột còn lại ghi các trị thập phân có trong hàm ban đầu.

Trên cùng hàng của tổ hợp ta đánh dấu * dưới các cột có số tương ứng (ví dụ hàng chứa tổ hợp 1,5 có các dấu * ở cột 1 và 5). Tương tự cho các tổ hợp khác.

Bảng 4

Xét các cột chỉ chứa một dấu *, đó là các cột 1,2,10 và 13, các tổ hợp ở cùng hàng với các dấu * này sẽ được chọn, đó là các tổ hợp (1,5), (2,6 ; 10,14), (4,5 ; 12,13), tương ứng với A___ size 12{ {A} cSup { size 8{"___"} } } {}C__ size 12{ {C} cSup { size 8{"__"} } } {}D + C D__ size 12{ {D} cSup { size 8{"__"} } } {} + B C__ size 12{ {C} cSup { size 8{"__"} } } {}. Đánh dấu X dưới các cột tương ứng với các số có trong các tổ hợp đã chọn. Nếu tất cả các cột đều được đánh dấu thì các tổ hợp đã chọn đủ để diễn tả hàm ban đầu.

Trong trường hợp của bài toán này, sau khi chọn các tổ hợp nói trên thì tất cả cột đã được đánh dấu do đó kết quả cuối cùng là (sau khi loai bỏ tổ hợp B D__ size 12{ {D} cSup { size 8{"__"} } } {}):

Thí dụ 2: Rút gọn hàm f(A,B,C,D) = Σ(3,4,6,7,8,11,12,15)

Giai đọan 1

Bảng 1:

So sánh các tổ hợp của 2 nhóm gần nhau ta được kết quả cho bảng thứ hai

- Bảng thứ hai gồm các tổ hợp đã được rút gọn và chỉ còn lại 3 nhóm (giảm một nhóm so với bảng 1).

Bảng 2

Bảng 3:

Kết quả của hàm rút gọn gồm tổng các số hạng tương ứng với các tổ hợp không gom thành nhóm: (4,6), (4,12), (8,12), (6,7) và (3,7;11,15)

Giai đọan 2:

Bảng 4

Các cột 3, và 8 chỉ chứa một dấu *, các tổ hợp ở cùng hàng với các dấu * này sẽ được chọn, đó là các tổ hợp (3,7;11,15) và , (8,12), tương ứng với CD và A C__ size 12{ {C} cSup { size 8{"__"} } } {}D__ size 12{ {D} cSup { size 8{"__"} } } {}.

Đánh dấu X dưới các cột tương ứng với các số có trong các tổ hợp đã chọn.

Đến đây ta thấy còn 2 cột 4 và 6 chưa có dấu X, trong lúc chúng ta còn đến 3 tổ hợp để chọn. Dĩ nhiên trong trường hợp này ta chỉ cần chọn tổ hợp (4,6) ( A___ size 12{ {A} cSup { size 8{"___"} } } {}BD__ size 12{ {D} cSup { size 8{"__"} } } {}) thay vì chọn (4,12) và (6,7) thì đủ dấu X để lấp đầy các cột.

Tóm lại:

Thí dụ về bài toán đầy đủ:

Thí dụ 1:

Cho hàm logic F(A, B, C) thỏa tính chất: F(A,B,C) = 1 nếu có một và chỉ một biến bằng 1

a- Lập bảng sự thật cho hàm F.

b- Rút gọn hàm F.

c- Diễn tả hàm F chỉ dùng hàm AND và NOT

Giải

a. Dựa vào điều kiện của bài toán ta có bảng sự thật của hàm F:

b. Rút gọn hàm F

Bảng Karnaugh

c. Diễn tả hàm F chỉ dùng hàm AND và NOT

Dùng địnhlý De Morgan, lấy đảo 2 lần hàm F:

Thí dụ 2:

Cho hàm logic F(A, B, C, D) thỏa tính chất: F(A,B,C,D) = 1 khi có ít nhất 3 biến bằng 1

a- Rút gọn hàm F.

b- Diễn tả hàm F chỉ dùng hàm OR và NOT

Giải

a- Rút gọn hàm F

Ta có thể đưa hàm vô bảng Karnaugh mà không cần vẽ bảng sự thật.

Ta đưa số 1 vào tất cả các ô chứa 3 trị 1 trở lên

Và kết quả của hàm rút gọn là:

F(A,B,C,D) = ABC + ABD + ACD + BCD

b- Diễn tả hàm F chỉ dùng hàm OR và NOT

Dùng định lý De Morgan cho từng số hạng trong tổng

Viết lại hàm F: