Bài giảng môn Kỹ thuật số - Chương 2: Đại số Boole
"Don't study, don't know - Studying you will know!"
NGUYEN TRUNG HOA
Bai giang Ky Thuát Sä
Trang 12
Chæång 2
ÂAI SÄ BOOLE
2.1. CAC TIÃN ÂÃ VA ÂËNH LY ÂAI SÄ BOOLE
2.1.1. Cac tiãn âã
Cho mät táp håp B hæu han trong âo ngæåi ta trang bë cac phep toan
+ (cäng logic), x (nhán logic), - (bu logic ) va hai phán tæ 0 va 1 láp
thanh mät cáu truc âai sä Boole.
∀x,y ∈ B thç: x + y ∈ B, x.y ∈ B thoa man 5 tiãn âã sau:
2.1.1.1. Tiãn âã giao hoan
∀x,y ∈ B: x + y = y + x
2.1.1.2. Tiãn âã phäi håp
∀x,y,z ∈ B: (x + y) + z = x + ( y + z ) = x + y + z
(x. y).z = x.(y. z) = x.y.z
2.1.1.3. Tiãn âã phán bố
∀x,y,z ∈ B: x.(y + z ) = x.y + x.z
x + (y.z) = (x + y)(x + z)
2.1.1.4. Tiãn âã vã phán tæ trung hoa
Trong táp B tän tai hai phán tæ trung hoa, âo la phán tæ âån vë va
phán tæ kh, phán tæ âån vë ky hiãu la 1, phán tæ 0 ky hiãu la 0.
∀x ∈ B:
x + 1 = 1
x . 1 = x
x + 0 = x
x . 0 = 0
2.1.1.5. Tiãn âã vã phán tæ bu
∀x ∈ B, bao giå cung tän tai phán tæ bu tæång æng sao cho luän
thoa man:
x + x = 0
Chæång 2. Âai sä BOOLE
Trang 13
x. x = 0
Nãu B = B* = {0, 1} va thoa man 5 tiãn âã trãn thç cung láp thanh
cáu truc âai sä Boole nhæng la cáu truc âai sä Boole nho nhát.
2.1.2. Cac âënh ly
2.1.2.1 Ván âã âäi ngáu trong âai sä Boole
Hai mãnh âã (hai biãu thæc, hai âënh ly) âæåc goi la âäi ngáu våi
nhau nãu trong mãnh âã nay ngæåi ta thay phep toan cäng thanh phep
toan nhán va ngæåc lai,thay 0 bàng 1 va ngæåc lai thç se suy ra âæåc
mãnh âã kia.
Khi hai mãnh âã âäi ngáu våi nhau, nãu 1 trong 2 mãnh âã âæåc
chæng minh la âung thç mãnh âã con lai la âung.
Vê du:
x.(y + z ) = ( x. y) + ( x. z )
x + (y. z ) = ( x + y )( x + z )
x + x = 1
Vê du:
x. x = 0
2.1.2.2. Cac âënh ly
a. Âënh ly vã phán tæ bu la duy nhát
∀x, y ∈ B:
x + y = 1
⎫
⇒ y = x
⎬
⎭
x.y = 0
∀x ∈ B:
x + x +. . . . . + x = x
x. x. x. . . . . . x = x
b. Âënh ly De Morgan
∀x, y, z ∈ B, ta co:
x + y + z = x.y.z
x.y.z = x + y + z
∀x ∈ B, ta co:
x
= x
∀x, y, z ∈ B, ta co:
Bai giang Ky Thuát Sä
Trang 14
x + y + z = x + y + z = x.y.z
x. y. z = x.y.z =x + y + z
∀x, y ∈ B, ta co:
x. (x + y) = x.y
x + (x . y) = x + y
∀x, y ∈ B, ta co:
x + x. y = x
x.(x + y) = x
Våi 0, 1 ∈ B, ta co:
0 = 1 va 1 = 0
2.2. HAM BOOLE VA CAC PHÆÅNG PHAP BIÃU DIÃN
2.2.1. Ham Boole
2.2.1.1. Âënh nghéa
Ham Boole la mät anh xa Boole tæ âai sä Boole vao chênh no. Tæc
la ∀x, y ∈ B âæåc goi la biãn Boole thç ham Boole, ky hiãu la f, âæåc
hçnh thanh trãn cå så liãn kãt cac biãn Boole bàng cac phep toan +
(cäng logic ), x (nhán logic ), hoàc nghëch âao logic (-). Ham Boole
âån gian nhát la ham Boole theo 1 biãn Boole.
Ky hiãu: f(x) = x
f(x) = x
f(x) = α (α: la hàng sä )
Trong træång håp täng quat, ta co ham Boole theo n biãn Boole
âæåc ky hiãu nhæ sau: f(x1, x2,. . . . . ., xn )
2.2.1.2. Cac tênh chát cua ham Boole
Nãu f(x1, x2, ..., xn) la mät ham Boole thç:
+ α.f(x1, x2, ..., xn) cung la mät ham Boole.
+ f (x1, x2, ..., xn)
cung la mät ham Boole.
Nãu f1(x1, x2, ..., xn) va f2(x1, x2, ..., xn) la nhæng ham Boole thç:
+ f1(x1, x2, ..., xn) + f2(x1, x2, ..., xn) cung la mät ham Boole.
+ f1(x1, x2, ..., xn).f2(x1, x2, ..., xn)
cung la mät ham Boole.
Chæång 2. Âai sä BOOLE
Trang 15
Váy, mät ham Boole f cung âæåc hçnh thanh trãn cå så liãn kãt cac
ham Boole bàng cac phep toan + (cäng logic), x (nhán logic) hoàc
nghëch âao logic (-).
2.2.1.3. Gia trë cua ham Boole
Goi f (x1, x2, ..., xn) la mät ham Boole theo biãn Boole.
Trong f ngæåi ta thay cac biãn xi bàng cac gia trë cu thã αi (i = 1, n )
thç ham f (α1, α2, α3,..., αn) âæåc goi la gia trë cua ham Boole theo n
biãn.
Vê du:
Xet ham f(x1, x2 ) = x1 + x2
Xet B = B* ={0,1}
x1
0
0
1
1
x2 f(x1, x2)
⇒
⇒
⇒
⇒
Nãu x1 = x2 =0
f(0,0) = 0
f(0,1) = 1
f(1,0) = 1
f(1,1) = 1
0
1
0
1
0
1
1
1
Nãu x1 = 0, x2 = 1
Nãu x1 = 1, x2 = 0
Nãu x1 = 1, x2 = 1
Ta láp âæåc bang gia trë cua ham trãn.
Vê du: f (x1, x2, x3 ) = x1 + x2.x3
Xet B = B* = {0,1 }
Bang gia trë cua ham:
x1 x2 x3 f (x1, x2, x3)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
0
1
1
1
1
1
Bai giang Ky Thuát Sä
Trang 16
2.2.2. Cac phæång phap biãu diãn ham Boole
2.2.2.1. Phæång phap bang
La phæång phap thæång dung âã biãu diãn ham sä noi chung.
Phæång phap nay gäm mät bang âæåc chia lam hai phán:
- Mät phán danh cho biãn âã ghi cac tä håp gia trë co thã co cua
biãn.
- Mät phán danh cho ham âã ghi cac gia trë cua ham ra tæång æng
våi cac tä håp cua cac biãn vao.
2.2.2.2. Phæång phap giai têch
La phæång phap biãu diãn ham Boole dæåi dang täng cac têch sä,
hoàc dæåi dang têch cua cac täng sä. Dang täng cua cac têch sä goi la
dang chênh tàc thæ nhát, con dang têch cua cac täng la dang chênh tàc
thæ hai cua ham Boole, va hai dang chênh tàc nay la âäi ngáu nhau.
a. Dang chênh tàc 1(Dang täng cua cac têch sä)
Xet cac ham Boole âån gian sau âáy: f(x) = x, f(x) = x , f(x) = α.
Xet f(x) = x:
Ta co:
x =0. x + 1. x
màt khac:
f
⎧
⎨
f
⎩
(
( )
0
1
)
=1
= 0
f x = x ⇒
( )
suy raf(x) = x co thã biãu diãn:
f(x) = x = f(0). x + f (1).x
trong âo: f (0), f (1) âæåc goi la gia trë cua ham Boole theo mät biãn.
Xet f(x) = x :
Ta co:
x = 1. x + 0. x
Màt khac:
f
⎧
⎨
f
⎩
(
( )
0
1
)
= 0
=1
f x = x ⇒
( )
Suy ra: f(x) = x co thã biãu diãn:
f(x) = x = f(0). x + f(1).x
Chæång 2. Âai sä BOOLE
Trang 17
Xet f(x) = α:
Ta co: α = α.1 = α(x + x ) = x .α + α.x
Màt khac:
f
⎧
⎨
f
⎩
(
( )
0
1
)
= α
= α
f x = α ⇒
( )
Suy ra f(x) = α co thã âæåc biãu diãn:
f(x) = α = f(0). x + f(1).x
Kãt luán:
Du la f(x) = x, f(x) = x hay f(x) = α, ta âãu co dang:
f(x) = f(0).x + f(1).x
Váy f(x) = f(0).x + f(1).x trong âo f (0), f (1) âæåc goi la gia trë cua
ham Boole theo mät biãn, âæåc goi la dang chênh tàc thæ nhát (dang
täng cua cac têch) theo mät biãn.
Trong træång håp hai biãn f(x1, x2) thç cach biãu diãn cung hoan
toan dæa trãn cach biãu diãn cua dang chênh tàc thæ nhát theo 1 biãn
(trong âo xem mät biãn la hàng sä).
Ta co:
f(x1, x2 ) = f(0, x2).
x 1 + f(1,x2).x1
ma:
va:
f(0, x2) = f(0,0 ). x 2 + f(0,1).x2
f(1, x2) = f(1,0). x 2 + f(1,1). x2
Suy ra:
f(x1, x2 ) = f(0,0) x 1 x 2 + f(0, 1)
x
1x2 + f(1,0 )x1 x 2 + f(1,1)x1x2
2
Váy:
f (x1, x2) = 2 −1f(α ,α )x x
1
2
α
α
∑
1
2
2
1
e=0
trong âo e la sä tháp phán tæång æng våi ma (α1, α2) va:
x1 nãu α1 = 1
x 1 nãu α1 = 0
x1α
1
=
x2 nãu α2 = 1
x 2 nãu α2 = 0
xα2
2
=
Bai giang Ky Thuát Sä
Täng quat cho n biãn:
f(x1, x2, ..., xn) =
Trang 18
n
2 −1
α
α
α
2
n
1
f(α ,α ,....,α )x x ...x
∑
1
2
n
1
2
n
e=0
trong âo e la sä tháp phán tæång æng våi ma nhë phán (α1, α2, ...., αn);
α
va:
xi nãu αi = 1
x i nãu αi = 0
i
=
xi
Vê du:
23 −1
α
1
α
2
α
3
f(x1, x2, x3) =
f (α1, α2, α3). x1 . x2 . x3
∑
e=0
f(x1, x2, x3) = f(0,0,0)x 1 x 2 x 3 + f(0,0,1)x 1 x 2 x3 + f(0,1,0)x 1x2 x 3
+ f(0,1,1)x 1 x2 x3 + f(1,0,0) x1 x 2 x 3 + f(1,0,1)x1 x 2 x3
+ f(1,1,0) x1 x2 x 3 + f(1,1,1) x1 x2 x3
Váy dang chênh tàc thæ nhát la dang täng cua cac têch ma trong mäi
têch sä chæa âáy âu cac biãn Boole dæåi dang thát hoàc dang bu
(nghëch âao).
b. Dang chênh tàc 2 (têch cua cac täng):
Âáy la dang âäi ngáu cua dang chênh tàc 1 nãn biãu thæc täng quat
cua dang chênh tàc thæ hai cho n biãn la:
n−1
2
α
α
2
α
n
1
f(x1, x2, ..., xn) =
[f(α1, α2, α3) + x1 + x2 + ...+ xn )]
∏
e=0
trong âo e la sä tháp phán tæång æng cua ma nhë phán (α1, α2, ...., αn);
va:
x i nãu αi = 1
xi nãu αi = 0
α
i
=
xi
Vê du:
f(x1,x2)=[f(0,0)+x1+x2][f(0,1)+x1+x 2][f(1,0)+x 1+x2][f(1,1)+x 1+x 2]
Chæång 2. Âai sä BOOLE
Trang 19
f(x1, x2, x3) = [f(0,0,0)+x1+ x2+x3].[f(0,0,1)+x1+x2+x 3].
[f(0,1,0)+x1+x 2+x3].[f(0,1,1)+x1+x 2+x 3].
[f(1,0,0)+x 1+x2+x3].[f(1,0,1)+x 1+x2+x 3].
[f(1,1,0)+x 1+x 2+x3].[f(1,1,1)+x 1+x 2+x 3]
Váy, dang chênh tàc thæ hai la dang têch cua cac täng sä ma trong
âo mäi täng sä nay chæa âáy âu cac biãn Boole dæåi dang thát hoàc
dang bu.
Chu y:
Xet vê du 1: f(x1, x2) = x1 + x2 ,
Viãt dæåi dang chênh tàc 1:
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
Tæ vê du trãn ta tháy: Dang chênh tàc thæ nhát la dang liãt kã tát ca
cac tä håp nhë phán cac biãn vao sao cho tæång æng våi nhæng tä håp
âo gia trë cua ham ra bàng 1. Khi liãt kã nãu biãn tæång æng bàng 1
âæåc viãt å dang thát (x), va biãn tæång æng bàng 0 âæåc viãt å dang
bu (x ).
Xet vê du 2: f(x1, x2, x3) = x1 + x2.x3
Viãt dæåi dang chênh tàc 2:
f(x1, x2, x3) = [0+x1+x2+x3].[0+x1+x2+x 3].[0+x1+x 2+x3].
[1+x1+x 2+x 3].[1+x 1+x2+x3].[1+x 1+x2+x 3].
[1+x 1+x 2+x3].[1+x 1+x 2+x 3]
Hay: f(x1, x2, x3) = x1 + x2.x3 = [x1+x2+x3].[x1+x2+x 3].[x1+x 2+x3]
Váy, dang chênh tàc thæ hai la dang liãt kã tát ca cac tä håp nhë phán
cac biãn vao sao cho tæång æng våi nhæng tä håp âo gia trë cua ham ra
bàng 0. Khi liãt kã nãu biãn tæång æng bàng 0 âæåc viãt å dang thát
(x), va biãn tæång æng bàng 1 âæåc viãt å dang bu (x ).
Xet vê du âån gian sau âã hiãu ro hån vã cach thanh láp bang gia trë
cua ham, tçm ham mach va thiãt kã mach: Hay thiãt kã mach âiãn sao
Bai giang Ky Thuát Sä
Trang 20
cho khi cäng tàc 1 âong thç âen âo, cäng tàc 2 âong âen âo, ca hai
cäng tàc âong âen âo.
Giai
Ta qui âënh:
- Cäng tàc hå : 0 Âen tàt : 0
- Cäng tàc âong: 1 Âen âo : 1
Luc âo ta co bang trang thai mä ta hoat âäng cua mach:
Cäng tàc 1 Cäng tàc 2
Âen
x1
x2
f(x1,x2)
0
0
1
1
0
1
0
1
0
1
1
1
Viãt theo dang chênh tàc 1 ta co:
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 dang chênh tàc 2 ta co:
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 dang chênh tàc 1 hay chênh tàc 2 ta âãu co ham
mach:
f(x1, x2) = x1 + x2
2.2.2.3. Phæång phap biãu diãn bàng bang Karnaugh
Âáy la cach biãu diãn lai cua phæång phap bang dæåi dang bang
gäm cac ä vuäng co dang nhæ hçnh bãn.
Chæång 2. Âai sä BOOLE
Trang 21
Trãn bang nay ngæåi ta bä trê cac biãn vao theo hang hoàc theo cät
cua bang. Trong træång håp sä læång biãn vao la chàn, ngæåi ta bä trê
sä læång biãn vao theo hang ngang bàng sä læång biãn vao theo cät
doc cua bang. Trong træång håp sä læång biãn vao la le, ngæåi ta bä trê
sä læång biãn vao theo hang ngang nhiãu hån sä læång biãn vao theo
cät doc 1 biãn hoàc ngæåc lai.
Cac tä håp gia trë cua biãn vao theo hang ngang hoàc theo cät doc
cua bang âæåc bä trê sao cho khi ta âi tæ mät ä sang mät ä lán cán våi
no chè lam thay âäi mät gia trë cua biãn, nhæ váy thæ tæ bä trê hay sàp
xãp cac tä håp gia trë cua biãn vao theo hang ngang hoàc theo cät doc
cua bang Karnaugh hoan toan tuán thu theo ma Gray. Gia trë ghi trong
mäi ä vuäng nay chênh la gia trë cua ham ra tæång æng våi cac tä håp
gia trë cua biãn vao. Å nhæng ä ma gia trë ham la khäng xac âënh, co
nghéa la gia trë cua ham la tuy y (hay tuy âënh), ngæåi ta kê hiãu bàng
chæ x. Nãu co n biãn vao se co 2n ä vuäng.
2.3. TÄI THIÃU HAM BOOLE
2.3.1. Âai cæång
Trong thiãt bë may tênh ngæåi ta thæång thiãt kã gäm nhiãu modul
(kháu) va mäi modul nay âæåc âàc træng bàng mät phæång trçnh logic.
Trong âo, mæc âä phæc tap cua så âä tuy thuäc vao phæång trçnh logic
biãu diãn chung. Viãc âat âæåc âä än âënh cao hay khäng la tuy thuäc
vao phæång trçnh logic biãu diãn chung å dang täi thiãu hoa hay chæa.
Âã thæc hiãn âæåc âiãu âo, khi thiãt kã mach sä ngæåi ta âàt ra ván âã
täi thiãu hoa cac ham logic. Âiãu âo co nghéa la phæång trçnh logic
biãu diãn sao cho thæc sæ gon nhát (sä læång cac phep tênh va sä læång
cac sä âæåc biãu diãn dæåi dang thát hoàc bu la êt nhát).
Tuy nhiãn trong thæc tã, khäng phai luc nao cung âat âæåc låi giai
täi æu cho bai toan täi thiãu hoa.
Bai giang Ky Thuát Sä
Trang 22
2.3.2. Cac bæåc tiãn hanh täi thiãu hoa
- Dung cac phep täi thiãu âã täi thiãu hoa cac ham sä logic.
- Rut ra nhæng thæa sä chung nhàm muc âêch täi thiãu hoa thãm
mät bæåc næa cac phæång trçnh logic.
2.3.3. Cac phæång phap täi thiãu hoa
2.3.3.1. Phæång phap giai têch
Âo la phæång phap täi thiãu hoa ham Boole (phæång trçnh logic) dæa
vao cac tiãn âã, âënh ly cua âai sä Boole.
Vê du:
f(x1, x2) = x 1x2 + x1 x 2 + x1x2= (x 1 + x1)x2 + x1 x 2
= x2 + x1 x 2 = x2 + x1
Vê du:
f(x1, x2, x3) = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 x 3 + x1x2x3
= x 1x2x3 + x1 x 2 x3 + 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 phap bang Karnaugh
a. Täi thiãu hoa ham Boole bàng bang Karnaugh
Âã täi thiãu hoa ham Boole bàng phæång phap bang Karnaugh phai
tuán thu theo qui tàc vã ä kã cán: “Hai ä âæåc goi la kã cán nhau la hai
ä ma khi ta tæ ä nay sang ä kia chè lam thay âäi gia trë cua 1 biãn. “
Quy tàc chung cua phæång phap rut gon bàng bang Karnaugh la
gom (kãt håp) cac ä kã cán lai våi nhau. Khi gom 2 ä kã cán nhau se
loai âæåc 1 biãn (2 ä =21 loai 1 biãn). Khi gom 4 ä kã cán se loai âæåc
2 biãn (4 ä =22 loai 2 biãn). Khi gom 8 ä kã cán se loai âæåc 3 biãn (8
ä = 23 loai 3 biãn ).
Täng quat, khi gom 2n ä kã cán se loai âæåc n biãn. Nhæng biãn bë loai
la nhæng biãn khi ta âi vong qua cac ä kã cán ma gia trë cua chung thay
âäi.
Chæång 2. Âai sä BOOLE
Trang 23
Nhæng âiãu cán læu y:
- Vong gom âæåc goi la håp lã khi trong vong gom âo co êt nhát 1 ä
chæa thuäc vong gom nao.
- Viãc kãt håp nhæng ä kã cán våi nhau con tuy thuäc vao phæång
phap biãu diãn ham Boole theo dang chênh tàc 1 hoàc chênh tàc 2.
Âiãu nay co nghéa la: nãu ta biãu diãn ham Boole theo dang chênh tàc
1 thç ta chè quan tám nhæng ä kã cán nao co gia trë bàng 1 va tuy âënh,
ngæåc lai nãu ta biãu diãn ham Boole dæåi dang chênh tàc 2 thç ta chè
quan tám nhæng ä kã cán nao co gia trë bàng 0 va tuy âënh. Ta quan
tám nhæng ä tuy âënh sao cho nhæng ä nay kãt håp våi nhæng ä co gia
trë bàng 1 (nãu biãu diãn theo dang chênh tàc 1) hoàc bàng 0 (nãu biãu
diãn theo dang chênh tàc 2) se lam cho sä læång ä kã cán la 2n lån
nhát.
- Cac ä kã cán muän gom âæåc phai la kã cán vong tron nghéa la ä
kã cán cuäi cung la ä kã cán âáu tiãn.
c. Cac vê du
Vê du 1: Täi thiãu hoa ham sau bàng phæång phap bang Karnaugh.
f(x1,x2)
x1
x2
0
0 0
1 1
1
1
1
Täi thiãu hoa theo dang chênh tàc 2:
f(x1,x2) = x1 + x2
Vê du 2: Täi thiãu hoa ham sau bàng phæång phap bang Karnaugh.
f(x1,x2,x3)
Vong gom 1: x
Vong gom 2: x2.x3
x1,x2
x3
00 01 11 10
0 0 0 1 1
1 0 1 1 1
Täi gian theo dang chênh tàc 1: Ta chè quan tám âãn nhæng ä co gia
trë bàng 1 va tuy âënh, nhæ váy se co 2 vong gom âã phu hãt cac ä co
gia trë bàng 1: vong gom 1 gäm 4 ä kã cán, va vong gom 2 gäm 2 ä kã
cán (hçnh ve).
Bai giang Ky Thuát Sä
Trang 24
Âäi våi vong gom 1: Co 4 ä = 22 nãn se loai âæåc 2 biãn. Khi âi
vong qua 4 ä kã cán trong vong gom chè co gia trë cua biãn x1 khäng
âäi (luän bàng 1), con gia trë cua biãn x2 thay âäi (tæ 1→0) va gia trë
cua biãn x3 thay âäi (tæ 0→1) nãn cac biãn x2 va x3 bë loai, chè con lai
biãn x1 trong kãt qua cua vong gom 1. Vç x1=1 nãn kãt qua cua vong
gom 1 theo dang chênh tàc 1 se co x1 viãt å dang thát: x1
Âäi våi vong gom 2: Co 2 ä = 21 nãn se loai âæåc 1 biãn. Khi âi
vong qua 2 ä kã cán trong vong gom gia trë cua biãn x2 va x3 khäng
âäi, con gia trë cua biãn x1 thay âäi (tæ 0→1) nãn cac biãn x2 va x3
âæåc giæ lai, chè co biãn x1 bë loai. Vç x2=1 va x3=1 nãn kãt qua cua
vong gom 2 theo dang chênh tàc 1 se co x2 va x3 viãt å dang thát: x2.x3
Kãt håp 2 vong gom ta co kãt qua täi gian theo dang chênh tàc 1:
f(x1, x2, x3) = x1 + x2.x3
Täi gian theo dang chênh tàc 2: Ta quan tám âãn nhæng ä co gia trë
bàng 0 va tuy âënh, nhæ váy cung co 2 vong gom (hçnh ve), mäi vong
gom âãu gäm 2 ä kã cán.
Âäi våi vong gom 1: Co 2 ä = 21 nãn loai âæåc 1 biãn, biãn bë loai la
x2 (vç co gia trë thay âäi tæ 0→1). Vç x1=0 va x3=0 nãn kãt qua cua
vong gom 1 theo dang chênh tàc 2 se co x1 va x3 å dang thát: x1+ x3.
Âäi våi vong gom 2: Co 2 ä = 21 nãn loai âæåc 1 biãn, biãn bë loai la
x3 (vç co gia trë thay âäi tæ 0 → 1). Vç x1=0 va x2=0 nãn kãt qua cua
vong gom 2 theo dang chênh tàc 2 se co x1 va x2 å dang thát: x1 + x2.
f(x1,x2,x3)
x1,x2
Vong gom 1: x+ x
x3
00 01 11 10
0 0 0 1 1
1 0 1 1 1
Vong gom 2: x+ x
Kãt håp 2 vong gom co kãt qua cua ham f viãt theo dang 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. Âai sä BOOLE
Trang 25
= x1(1+ x2 + x3) + x2.x3
= x1 + x2.x3
Nhán xet: Trong vê du nay, ham ra viãt theo dang chênh tàc 1 va
ham ra viãt theo dang chênh tàc 2 la giäng nhau. Tuy nhiãn co træång
håp ham ra cua hai dang chênh tàc 1 va 2 la khac nhau, nhæng gia trë
cua ham ra æng våi mät tä håp biãn âáu vao la giäng nhau trong ca 2
dang chênh tàc.
Chu y: Ngæåi ta thæång cho ham Boole dæåi dang biãu thæc rut gon.
Vç co 2 cach biãu diãn ham Boole theo dang chênh tàc 1 hoàc 2 nãn se
co 2 cach cho gia trë cua ham Boole æng våi 2 dang chênh tàc âo:
Dang chênh tàc 1: Täng cac têch sä.
f(x1, x2, x3) = Σ(3, 4, 7) + d(5, 6)
Trong âo d: gia trë cac ä nay la tuy âënh (d: don’t care)
f(x1,x2,x3)
x1,x2
x3
00 01 11 10
0 0 X 1
0 1 1 X
0
1
Luc âo bang Karnaugh se âæåc cho nhæ hçnh trãn. Tæ biãu thæc rut
gon cua ham ta tháy tai cac ä æng våi tä håp nhë phán cac biãn vao co
gia trë la 3, 4, 7 thç ham ra co gia trë bàng 1; tai cac ä æng våi tä håp
nhë phán cac biãn vao co gia trë la 5,6 thç ham ra co gia trë la tuy âënh;
ham ra co gia trë bàng 0 å nhæng ä con lai æng våi tä håp cac biãn vao
co gia trë la 0, 1, 2.
Dang chênh tàc 2: Têch cac täng sä.
Phæång trçnh logic trãn cung tæång âæång:
f(x1, x2, x3) = Π(0, 1, 2) + d(5, 6)
Bai giang Ky Thuát Sä
Trang 26
Vê du 3: Täi thiãu hoa ham 4 biãn sau âáy:
f(x1,x2,x3,x4)
x3,x4
f(x1,x2,x3,x4)
x1,x2
x1,x2
x3,x4
00 01 11 10
00 01 11 10
00
01
11
10
00
x
x
0
1
x
0
x
1
1
1
x
x
x
x
1
1
x
x
0
1
x
0
x
1
1
1
X
X
x
x
1
1
01
11
10
Vong gom 1
Vong gom 2
Ta thæc hiãn täi thiãu hoa theo dang chênh tàc 1: Tæ ban âä
Karnaugh ta co 2 vong gom, vong gom 1 gäm 8 ä kã cán va vong gom
2 gäm 8 ä kã cán. Kãt qua täi thiãu hoa nhæ sau:
Vong gom 1: x 4
Vong gom 2: x1
Váy: f(x1, x2, x3, x4) = x 4 + x1
16 trang
25160
Free
Bạn đang xem tài liệu "Bài giảng môn Kỹ thuật số - Chương 2: Đại số Boole", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mon_ky_thuat_so_chuong_2_dai_so_boole.pdf
