I) Quy iuật gộp (dán) cá&.số hạng nhỗ nhất trên bàng Karnaugh
Trên bảng Karnaugh của biến, tất cả các sổ hạng nhỏ nhát kể nhau đéu cố thể gộp với nhau, khi gộp lại thỉ cđ thể khử bỏ biến liên quan. Cụ thể, cứ 2 số hạng nhỏ nhất gộp lại thi khử bỏ được một biến, cú 4 sổ hạng nhỏ nhát gộp lạỉ (thành một số hạng) thì khử bỏ được 2 biến, cứ 8 số hạng nhỏ nhất gộp lại thì khử được 3 biến. Ndi tổng quát, 2" số hạng nhỏ nhất gộp lại (thành một số hạng) thl khử được n biến. Vì rằng, 2" số hạng nhỏ nhất cộng với nhau (gộp lại), trừ các thừa số chung rổi thì còn lại 2" số hạng dạng tích, vừa đúng bằng toàn bộ số hạng nhỏ nhất của n biến cẩn khử bỏ. Tã đã biết tính chất của số hạng nhỏ nhăt, tổng của chúng bằng 1.
Các hỉnh 3 -3 -2 , hĩnh 3 -3 -3 , hình 3 -3 -4 vẽ tương ứng các trường hợp ctí 2, 4,
8 số hạng nhỏ nhất được gộp.
(c) A B C -f ABC = AB
\ c D
aồsT ,00 01 11 10
R
AB^CD 00 01 11 10
00
01 11 10
(13 15)
--
(0 ABCD + ABCD = ABD
AỔ'CD
00 01 ỉ ỉ 10
00 01 II 10
_ a ) cr
(e)ABCD + ABCD - BCD (g)ABCD + ABCD * ABD
Hĩnh 3 - 3 -2 . BC
00 01 n 10
i
6;
BC
00 01 11 10
f6~ íì
(d) Ạ B C D + A B C D + + ABCD + A B C D = AD
( b ) A B C + A B C + A B C + A B C = B
BC
00 01 11 10
(c)A BC + ABC + A BC + ABC == c
(e)A B cp +_A B c D +
ABCD + A B C D = AB
Hình 3-3-3
(0 A B C D + A B C D + _ + A B C D + A B C D * B D
. CD
\ 00 01 11 10 \ CD00 01 11 10
00 00- ì) á /
01( 4 5 7 0 01
11 11
10 10
( g l Ạ J c D + A B_c D + _ + A B C D + A B C D = B D
8a-CSKT. 113
CD
00 01 11 ÌO
00 01 II 10
A 5 7 6"\
I42 13 15
(a) B
AB"CD 00
01 11 10
(b) B
[ . 1 3 2]
8 9 11
CD
00 01 11 10
12
(c) D
14 10
AH'CD 00 01 11 10
00 01 11 10
/0
4 5
12 13
V
(d) c
fflnh 3 - 3 - 4 .
2) Đùng bảng Karnaugh tối thiểu hóa hàm logic Nđi chung, quy trình cd 3 bước
- Vẽ bảng Karnaugh của hàm xét - Gộp các số hạng nhỏ nhất
- Chọn số hạng viết biểu thức OR-AND tối thiểu Ví dụ 3 -3 -8 : Dùng hình vẽ tối thiểu hốa hàm
z = 2 (1,3,4,5,10,11,12,13)
Giải : “ Vẽ bảng Karnaugh của hàm z : Vẽ bảng Karnaugh của 4 biến A,BjC,D. Trôn hình đánh dấu tất cả các số hạng nhỏ nhất của hàm. Xem hlnh 3 -3 -5
- Gộp các số hạng nhỏ nhất.
AB"CD
00 01
u
10
00 01 11 10
rn"
4 J2 --- /13
lò)
m n h 3 - 3 - 5 .
Theo phương pháp đâ giới thiệu trước đây, khoanh vòng các sổ hạng nhỏ nhất cđ thể gộp. Từ hỉnh 3 -3 -5 , ta cd :
2(4,5,12,13) = BC 2 (1 ,3 ) = ÃBD 2 (10,11) = ABC 2 (1 ,5 ) = ÃCD 2 (3 ,1 1 ) = BCD
- Chọn số hạng viết biểu thức OR-AND tối thiểu.
Nguyên tác chọn số hạng :
- Phải bao gổm tẫt cả các số hạng nhỏ nhất của hàm - SỐ các số hạng được chọn phải là ít nhất
- SỐ thừa số của mỗi số hạng cũng phải là ít nhất.
Trọng ví dụ này, cd thể chọn B C , A B D , ABC Vậy kết quả tối thiểu hđa, ta có :
z = BC + ÃBD + ABC 3) Mấy vấn đê cằn lưu ý
- Vòng gộp phải càng to càng tốt. Tương ứng số các số hạng nhỏ nhất được gộp lại càng nhiểu ; do đó, sau khi gộp, số hạng câng ít thừa số.
- Mỗi vòng gộp bao gổm ít nhất một số hạng nhỏ nhất không ctí trong vòng khác. Vòng nào bao gổm các số hạng đều đã cđ trong vòng khác, thì vòng đó là thừa. Mặt khác, mỗi số hạng nhỏ nhất cđ thể được sử dụng nhiễu lẩn (có mật trong nhiều vòng khác nhau)
- Phải khoanh vòng sao cho toàn bộ số hạng nhỏ nhất của hàm sổ đéu có các vòng, không sđt. Các thừa số tương ứng của số hạng vòng gộp xét làm thành số hạng của hàm đă tối thiểu hổa.
- TVong một số trường hợp, có thể cd nìiiểu cách khoanh vòng, nghĩa là ctí thể co' nhiểu hàm tối thiếu. Những hàm tối thiểu này cẩn phải được so sánh, kiểm tra để chọn ra đâu là hàm tối thiểu thực sự (tối thiểu của tối thiểu !)
- Khi gộp các số hạng nhỏ nhất, nghĩa là khi khoanh vòng, cd 2 điểu sau đây dễ quên ; một là, phải nhớ rằng 4 ô ở 4 gdc bảng Karnaugh cũng ctí thể gộp với nhau (xem hình 3 -3 -3 g ) ; hai là, vẽ vòng lớn trước, vòng bé sau, kiểm tra xem : mỗi vòng cd ít nhất một số hạng nhỏ nhất không cđ trong vòng khác. Không lưu ý đến những vấn đề này, biểu thức hàm số đạt được không chác là tối thiểu.
Ví dụ 3 -3 -9 : Dùng hinh vẽ tối thiểu hda hàm
z = 2(1,4,5.3,8,12,13,15)
Giải :
- Vẽ bảng Karnaugh của hàm z xem hình 3 - 3 - 6
115
- Gộp các số hạng nhỏ nhất
Tuy vòng + nij + nij2 + m j3 là to nhất, nhưng các ròng khác đâ bao gồm m^, nij, mj2, m j3, nên vòng này thừa.
- Biểu thức OR-AND tối thiểu : z = ÃCD + ÃBD + ACD + ABD
Ví dụ 3 -3 -1 0 : Dùng hình vẽ tối thiểu hđa hàm
CD
00 01 11 10
00 01 11 10
T
l ) L l (l
r 0
i
z = A e c - B (AC D + A CD) Giải :
- Biến đổi hàm z thành dạng biểu thức OR-AND
Hình 3 - 3 - 6 .
z = A e c . B(ACD + ACD)
AB' CD
00 01 11 10
00
01 11 10
1 1 1
1 1
1 1
1 1 1
Hình 3 - 3 - 7 .
= A 0 C + B( ACD + ACD)
= Ã c + AC + A B C D + ÃBCD - Vẽ bảng Karnaugh như hình 3 -3 -7 - Gộp các số hạng nhỏ nhất
Lưu ý các ô 4 gốc bảng cđ thể gộp là ĩĩìq, mj, mg, mj(j. (Nếu gộp thành hai vòng nhỏ niQ, m2 và mg, ĩxiịo thl vẫn chưa được tối thiểu)
- Viết hàm tối thiểu : z = A c + AC + B D
4) Dùng băng Karnaugh tìm hàm OR-AND tố i thiểu của hàm đảo
N ếu trên bảng Karnaugh của hàm số, ta gộp tất cả các số hạng nhỏ nhất ứng với giá trị 0 của hàm xét, thì ta được biểu thức OR-AND tối thiểu của hàm đảo
z .
Ví dụ 3 .3 .1Ị_; Cho z = AB + BC + CA. Dùng hình vẽ tìm ra biểu thức OR-AND tối thiểu của z .
Giải :
- Vẽ bảng Karnaugh của hàm z
Hình 3.3.8 \ BC
- Gộp các số hạng nhỏ nhất ứng với z = 0
00 01 11 10
+ mj = A , iĩIq + m2 = A c , ixIq + = B c
- Viết biểu thức hàm OR-AND tối thiểu của z
z = Ã B + BC .+ Ã c
0 o ) 1
L a 1 1 1
Hình 3 - 3 - 8 .