Giáo trình Kỹ thuật số - Chương 2: Đại số Boole

 
1 
0 
1 
1 
1 
Viãút theo dảng chênh tàõc 1 ta cọ: 
f(x1, x2) = 0.x 1 x 2 + 1.x 1.x2 + 1.x1.x 2 + 1.x1.x2 
= x 1. x2 + x1.x 2 + x1.x2 
= x 1. x2 + x1(x 2 + x2) 
= x 1. x2 + x1 = x1 + x2
Viãút theo dảng chênh tàõc 2 ta cọ: 
f(x1, x2) = [0+x1+x2].[1+x1+x 2].[1+x 1+ x2].[1+x 1+x 2] 
= [x1+ x2].1.1.1 = x1 + x2
Váûy, duì viãút theo dảng chênh tàõc 1 hay chênh tàõc 2 ta âãưu cọ haìm 
mảch: 
f(x1, x2) = x1 + x2 
2.2.2.3. Phỉång phạp biãøu diãùn bàịng baíng Karnaugh 
Âáy laì cạch biãøu diãùn lải cuía phỉång phạp baíng dỉåïi dảng baíng 
gäưm cạc ä vuäng cọ dảng nhỉ hçnh bãn. 
Chỉång 2. Âải säú BOOLE Trang 21 
Trãn baíng naìy ngỉåìi ta bäú trê cạc biãún vaìo theo haìng hồûc theo cäüt 
cuía baíng. Trong trỉåìng håüp säú lỉåüng biãún vaìo laì chàơn, ngỉåìi ta bäú trê 
säú lỉåüng biãún vaìo theo haìng ngang bàịng säú lỉåüng biãún vaìo theo cäüt 
doüc cuía baíng. Trong trỉåìng håüp säú lỉåüng biãún vaìo laì leí, ngỉåìi ta bäú trê 
säú lỉåüng biãún vaìo theo haìng ngang nhiãưu hån säú lỉåüng biãún vaìo theo 
cäüt doüc 1 biãún hồûc ngỉåüc lải. 
Cạc täø håüp giạ trë cuía biãún vaìo theo haìng ngang hồûc theo cäüt doüc 
cuía baíng âỉåüc bäú trê sao cho khi ta âi tỉì mäüt ä sang mäüt ä lán cáûn våïi 
nọ chè laìm thay âäøi mäüt giạ trë cuía biãún, nhỉ váûy thỉï tỉû bäú trê hay sàõp 
xãúp cạc täø håüp giạ trë cuía biãún vaìo theo haìng ngang hồûc theo cäüt doüc 
cuía baíng Karnaugh hoaìn toaìn tuán thuí theo maỵ Gray. Giạ trë ghi trong 
mäùi ä vuäng naìy chênh laì giạ trë cuía haìm ra tỉång ỉïng våïi cạc täø håüp 
giạ trë cuía biãún vaìo. ÅÍ nhỉỵng ä maì giạ trë haìm laì khäng xạc âënh, cọ 
nghéa laì giạ trë cuía haìm laì tuìy yï (hay tuìy âënh), ngỉåìi ta kê hiãûu bàịng 
chỉỵ x. Nãúu cọ n biãún vaìo seỵ cọ 2n ä vuäng. 
2.3. TÄÚI THIÃØU HAÌM BOOLE 
2.3.1. Âải cỉång 
Trong thiãút bë mạy tênh ngỉåìi ta thỉåìng thiãút kãú gäưm nhiãưu modul 
(kháu) vaì mäùi modul naìy âỉåüc âàûc trỉng bàịng mäüt phỉång trçnh logic. 
Trong âọ, mỉïc âäü phỉïc tảp cuía så âäư tuìy thuäüc vaìo phỉång trçnh logic 
biãøu diãùn chụng. Viãûc âảt âỉåüc âäü äøn âënh cao hay khäng laì tuìy thuäüc 
vaìo phỉång trçnh logic biãøu diãùn chụng åí dảng täúi thiãøu họa hay chỉa. 
Âãø thỉûc hiãûn âỉåüc âiãưu âọ, khi thiãút kãú mảch säú ngỉåìi ta âàût ra váún âãư 
täúi thiãøu họa cạc haìm logic. Âiãưu âọ cọ nghéa laì phỉång trçnh logic 
biãøu diãùn sao cho thỉûc sỉû goün nháút (säú lỉåüng cạc phẹp tênh vaì säú lỉåüng 
cạc säú âỉåüc biãøu diãùn dỉåïi dảng tháût hồûc buì laì êt nháút). 
Tuy nhiãn trong thỉûc tãú, khäng phaíi lục naìo cuỵng âảt âỉåüc låìi giaíi 
täúi ỉu cho baìi toạn täúi thiãøu họa. 
Baìi giaíng Kyỵ Thuáût Säú Trang 22 
2.3.2. Cạc bỉåïc tiãún haình täúi thiãøu họa 
- Duìng cạc phẹp täúi thiãøu âãø täúi thiãøu họa cạc haìm säú logic. 
- Rụt ra nhỉỵng thỉìa säú chung nhàịm mủc âêch täúi thiãøu họa thãm 
mäüt bỉåïc nỉỵa cạc phỉång trçnh logic. 
2.3.3. Cạc phỉång phạp täúi thiãøu họa 
2.3.3.1. Phỉång phạp giaíi têch 
Âọ laì phỉång phạp täúi thiãøu họa haìm Boole (phỉång trçnh logic) dỉûa 
vaìo cạc tiãn âãư, âënh lyï cuía âải säú Boole. 
Vê dủ: 
f(x1, x2) = x 1x2 + x1 x 2 + x1x2 = (x 1 + x1)x2 + x1 x 2
= x2 + x1 x 2 = x2 + x1
Vê dủ: 
f(x1, x2, x3) = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 x 3 + x1x2x3
 = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 (x 3 + x3) 
 = x 1x2x3 + x1 x 2(x 3 + x3) + x1x2
= x 1x2x3 + x1(x 2 + x2) 
= x 1x2x3 + x1
= x1 + x2 x3 
2.3.3.2. Phỉång phạp baíng Karnaugh 
a. Täúi thiãøu họa haìm Boole bàịng baíng Karnaugh 
Âãø täúi thiãøu họa haìm Boole bàịng phỉång phạp baíng Karnaugh phaíi 
tuán thuí theo qui tàõc vãư ä kãú cáûn: “Hai ä âỉåüc goüi laì kãú cáûn nhau laì hai 
ä maì khi ta tỉì ä naìy sang ä kia chè laìm thay âäøi giạ trë cuía 1 biãún. “ 
Quy tàõc chung cuía phỉång phạp rụt goün bàịng baíng Karnaugh laì 
gom (kãút håüp) cạc ä kãú cáûn lải våïi nhau. Khi gom 2 ä kãú cáûn nhau seỵ 
loải âỉåüc 1 biãún (2 ä =21 loải 1 biãún). Khi gom 4 ä kãú cáûn seỵ loải âỉåüc 
2 biãún (4 ä =22 loải 2 biãún). Khi gom 8 ä kãú cáûn seỵ loải âỉåüc 3 biãún (8 
ä = 23 loải 3 biãún ). 
Täøng quạt, khi gom 2n ä kãú cáûn seỵ loải âỉåüc n biãún. Nhỉỵng biãún bë loải 
laì nhỉỵng biãún khi ta âi voìng qua cạc ä kãú cáûn maì giạ trë cuía chụng thay 
âäøi. 
Chỉång 2. Âải säú BOOLE Trang 23 
Nhỉỵng âiãưu cáưn lỉu yï: 
- Voìng gom âỉåüc goüi laì håüp lãû khi trong voìng gom âọ cọ êt nháút 1 ä 
chỉa thuäüc voìng gom naìo. 
- Viãûc kãút håüp nhỉỵng ä kãú cáûn våïi nhau coìn tuìy thuäüc vaìo phỉång 
phạp biãøu diãùỵn haìm Boole theo dảng chênh tàõc 1 hồûc chênh tàõc 2. 
Âiãưu naìy cọ nghéa laì: nãúu ta biãøu diãùn haìm Boole theo dảng chênh tàõc 
1 thç ta chè quan tám nhỉỵng ä kãú cáûn naìo cọ giạ trë bàịng 1 vaì tuìy âënh, 
ngỉåüc lải nãúu ta biãøu diãùn haìm Boole dỉåïi dảng chênh tàõc 2 thç ta chè 
quan tám nhỉỵng ä kãú cáûn naìo cọ giạ trë bàịng 0 vaì tuìy âënh. Ta quan 
tám nhỉỵng ä tuìy âënh sao cho nhỉỵng ä naìy kãút håüp våïi nhỉỵng ä cọ giạ 
trë bàịng 1 (nãúu biãøu diãùn theo dảng chênh tàõc 1) hồûc bàịng 0 (nãúu biãøu 
diãùn theo dảng chênh tàõc 2) seỵ laìm cho säú lỉåüng ä kãú cáûn laì 2n låïn 
nháút. 
- Cạc ä kãú cáûn muäún gom âỉåüc phaíi laì kãú cáûn voìng troìn nghéa laì ä 
kãú cáûûn cuäúi cuỵng laì ä kãú cáûn âáưu tiãn. 
c. Cạc vê dủ 
Vê dủ 1: Täúi thiãøu họa haìm sau bàịng phỉång phạp baíng Karnaugh. 
 0 1 x2
f(x1,x2) x1
0 0 1 
1 1 1 
Täúi thiãøu họa theo dảng chênh tàõc 2:
f(x1,x2) = x1 + x2
Vê dủ 2: Täúi thiãøu họa haìm sau bàịng phỉång phạp baíng Karnaugh. 
 00 01 11 10x3
f(x1,x2,x3) 
0 0 0 1 1
1 0 1 1 1
Voìng gom 2: x2.x3
Voìng gom 1: x1x1,x2 
Täúi giaín theo dảng chênh tàõc 1: Ta chè quan tám âãún nhỉỵng ä cọ giạ 
trë bàịng 1 vaì tuìy âënh, nhỉ váûy seỵ cọ 2 voìng gom âãø phuí hãút cạc ä cọ 
giạ trë bàịng 1: voìng gom 1 gäưm 4 ä kãú cáûn, vaì voìng gom 2 gäưm 2 ä kãú 
cáûn (hçnh veỵ). 
Baìi giaíng Kyỵ Thuáût Säú Trang 24 
Âäúi våïi voìng gom 1: Cọ 4 ä = 22 nãn seỵ loải âỉåüc 2 biãún. Khi âi 
voìng qua 4 ä kãú cáûn trong voìng gom chè cọ giạ trë cuía biãún x1 khäng 
âäøi (luän bàịng 1), coìn giạ trë cuía biãún x2 thay âäøi (tỉì 1→0) vaì giạ trë 
cuía biãún x3 thay âäøi (tỉì 0→1) nãn cạc biãún x2 vaì x3 bë loải, chè coìn lải 
biãún x1 trong kãút quaí cuía voìng gom 1. Vç x1=1 nãn kãút quaí cuía voìng 
gom 1 theo dảng chênh tàõc 1 seỵ cọ x1 viãút åí dảng tháût: x1 
Âäúi våïi voìng gom 2: Cọ 2 ä = 21 nãn seỵ loải âỉåüc 1 biãún. Khi âi 
voìng qua 2 ä kãú cáûn trong voìng gom giạ trë cuía biãún x2 vaì x3 khäng 
âäøi, coìn giạ trë cuía biãún x1 thay âäøi (tỉì 0→1) nãn cạc biãún x2 vaì x3 
âỉåüc giỉỵ lải, chè cọ biãún x1 bë loải. Vç x2=1 vaì x3=1 nãn kãút quaí cuía 
voìng gom 2 theo dảng chênh tàõc 1 seỵ cọ x2 vaì x3 viãút åí dảng tháût: x2.x3 
Kãút håüp 2 voìng gom ta cọ kãút quaí täúi giaín theo dảng chênh tàõc 1: 
 f(x1, x2, x3) = x1 + x2.x3
Täúi giaín theo dảng chênh tàõc 2: Ta quan tám âãún nhỉỵng ä cọ giạ trë 
bàịng 0 vaì tuìy âënh, nhỉ váûy cuỵng cọ 2 voìng gom (hçnh veỵ), mäùi voìng 
gom âãưu gäưm 2 ä kãú cáûn. 
Âäúi våïi voìng gom 1: Cọ 2 ä = 21 nãn loải âỉåüc 1 biãún, biãún bë loải laì 
x2 (vç cọ giạ trë thay âäøi tỉì 0→1). Vç x1=0 vaì x3=0 nãn kãút quaí cuía 
voìng gom 1 theo dảng chênh tàõc 2 seỵ cọ x1 vaì x3 åí dảng tháût: x1+ x3. 
Âäúi våïi voìng gom 2: Cọ 2 ä = 21 nãn loải âỉåüc 1 biãún, biãún bë loải laì 
x3 (vç cọ giạ trë thay âäøi tỉì 0 → 1). Vç x1=0 vaì x2=0 nãn kãút quaí cuía 
voìng gom 2 theo dảng chênh tàõc 2 seỵ cọ x1 vaì x2 åí dảng tháût: x1 + x2. 
 00 01 11 10x3
f(x1,x2,x3) 
0 0 0 1 1
1 0 1 1 1 Voìng gom 2: x1 + x2
Voìng gom 1: x1 + x3x1,x2
Kãút håüp 2 voìng gom cọ kãút quaí cuía haìm f viãút theo dảng chênh tàõc 
2: 
 f (x1, x2, x3) = (x1+x3).(x1+x2) 
 = x1.x1 + x1.x2 + x1.x3 + x2.x3
 = x1 + x1.x2 + x1.x3 + x2.x3
Chỉång 2. Âải säú BOOLE Trang 25 
 = x1(1+ x2 + x3) + x2.x3
 = x1 + x2.x3
Nháûn xẹt: Trong vê dủ naìy, haìm ra viãút theo dảng chênh tàõc 1 vaì 
haìm ra viãút theo dảng chênh tàõc 2 laì giäúng nhau. Tuy nhiãn cọ trỉåìng 
håüp haìm ra cuía hai dảng chênh tàõc 1 vaì 2 laì khạc nhau, nhỉng giạ trë 
cuía haìm ra ỉïng våïi mäüt täø håüp biãún âáưu vaìo laì giäúng nhau trong caí 2 
dảng chênh tàõc. 
Chụ yï: Ngỉåìi ta thỉåìng cho haìm Boole dỉåïi dảng biãøu thỉïc rụt goün. 
Vç cọ 2 cạch biãøu diãùn haìm Boole theo dảng chênh tàõc 1 hồûc 2 nãn seỵ 
cọ 2 cạch cho giạ trë cuía haìm Boole ỉïng våïi 2 dảng chênh tàõc âọ: 
Dảng chênh tàõc 1: Täøng cạc têch säú. 
f(x1, x2, x3) = Σ(3, 4, 7) + d(5, 6) 
Trong âọ d: giạ trë cạc ä naìy laì tuìy âënh (d: don’t care) 
 00 01 11 10
0 0 0 X 1
1 0 1 1 X
x3
f(x1,x2,x3) x1,x2 
Lục âọ baíng Karnaugh seỵ âỉåüc cho nhỉ hçnh trãn. Tỉì biãøu thỉïc rụt 
goün cuía haìm ta tháúy tải cạc ä ỉïng våïi täø håüp nhë phán cạc biãún vaìo cọ 
giạ trë laì 3, 4, 7 thç haìm ra cọ giạ trë bàịng 1; tải cạc ä ỉïng våïi täø håüp 
nhë phán cạc biãún vaìo cọ giạ trë laì 5,6 thç haìm ra cọ giạ trë laì tuìy âënh; 
haìm ra cọ giạ trë bàịng 0 åí nhỉỵng ä coìn lải ỉïng våïi täø håüp cạc biãún vaìo 
cọ giạ trë laì 0, 1, 2. 
Dảng chênh tàõc 2: Têch cạc täøng säú. 
Phỉång trçnh logic trãn cuỵng tỉång âỉång: 
f(x1, x2, x3) = (0, 1, 2) + d(5, 6) Π
Baìi giaíng Kyỵ Thuáût Säú Trang 26 
Vê dủ 3: Täúi thiãøu họa haìm 4 biãún sau âáy: 
 00 01 11 10
00 x x 1 x 
01 x 0 1 x 
11 0 x x 1 
10 1 1 x 1 
x1,x2x3,x4
Voìng gom 1 
Voìng gom 2
f(x1,x2,x3,x4)
 00 01 11 10
00 x x 1 x 
01 x 0 1 x 
11 0 x X 1 
10 1 1 X 1 
xf(x
x3,x4
1,x2,x3,x4) 
1,x2 
Ta thỉûc hiãûn täúi thiãøu họa theo dảng chênh tàõc 1: Tỉì baín âäư 
Karnaugh ta cọ 2 voìng gom, voìng gom 1 gäưm 8 ä kãú cáûn vaì voìng gom 
2 gäưm 8 ä kãú cáûn. Kãút quaí täúi thiãøu họa nhỉ sau: 
Voìng gom 1: x 4
Voìng gom 2: x1 
Váûy: f(x1, x2, x3, x4) = x 4 + x1