›
›

Bài giảng Kỹ thuật số - Chương 2: Đại số boole-cổng logic - Nguyễn Trọng Luật

Download
ÑAÏI SOÁ BOOLE – COÅNG LOGIC  
I. Caáu truùc ñaïi soá Boole:  
Laø caáu truùc ñaïi soá ñöôïc ñònh nghóa treân 1 taäp phaàn töû nhò  
phaân B = {0, 1} vaø caùc pheùp toaùn nhò phaân: AND (.), OR (+),  
NOT (’).  
x y x . y (x AND y)  
0 0 0  
0 1 0  
1 0 0  
1 1 1  
x y x + y (x OR y)  
0 0  
0 1  
1 0  
1 1  
0
1
1
1
x
x’ (NOT x, x )  
0
1
1
0
3C-1  
* Thöù töï pheùp toaùn: theo thöù töï daáu ngoaëc (), NOT, AND, OR  
1. Caùc tieân ñeà (Axioms):  
a. Tính kín (Closure Property)  
b. Phaàn töû ñoàng nhaát (Identity Element):  
x . 1 = 1 . x = x  
x + 0 = 0 + x = x  
c. Tính giao hoaùn (Commutative Property):  
x . y = y . x  
x + y = y + x  
d. Tính phaân boá (Distributive Property):  
x . ( y + z ) = x . y + x . z  
x + ( y . z ) = ( x + y ) . ( x + z )  
e. Phaàn töû buø (Complement Element):  
2
3C-2  
x + x = 1  
x . x = 0  
2. Caùc ñònh lyù cô baûn (Basic Theorems):  
a. Ñònh lyù 1:  
x = x  
b. Ñònh lyù 2:  
x + x = x  
x . x = x  
x . 0 = 0  
c. Ñònh lyù 3:  
x + 1 = 1  
d. Ñònh lyù 4: ñònh lyù haáp thu (Absorption)  
x + x . y = x  
x . (x + y) = x  
e. Ñònh lyù 5: ñònh lyù keát hôïp (Associative)  
x + (y + z) = (x + y) + z  
x . (y . z) = (x . y) . z  
f. Ñònh lyù 6: ñònh lyù De Morgan  
x + y = x . y  
x . y = x + y  
Môû roäng:  
x1 + x2 + .. + xn = x1 . x2 .. xn  
3
x1 . x2 .. xn = x1 + x2 + .. + xn  
3C-3  
II. Haøm Boole (Boolean Function):  
1. Ñònh nghóa:  
* Haøm Boole laø 1 bieåu thöùc ñöôïc taïo bôûi caùc bieán nhò  
phaân vaø caùc pheùp toaùn nhò phaân NOT, AND, OR.  
F (x, y, z) = x . y + x . y . z  
* Vôùi giaù trò cho tröôùc cuûa caùc bieán, haøm Boole seõ coù giaù  
trò laø 0 hoaëc 1.  
x y z  
F
* Baûng giaù trò:  
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
1
0
0
0
0
1
1
4
3C-4  
2. Buø cuûa 1 haøm:  
- Söû duïng ñònh lyù De Morgan:  
F = x . y + x . y . z  
F = x . y + x . y . z  
= ( x . y ) . ( x . y . z )  
F = ( x + y ) . ( x + y + z )  
- Laáy bieåu thöùc ñoái ngaãu vaø laáy buø caùc bieán:  
* Tính ñoái ngaãu (Duality): Hai bieåu thöùc ñöôïc goïi laø ñoái  
ngaãu cuûa nhau khi ta thay pheùp toaùn AND baèng OR,  
pheùp toaùn OR baèng AND, 0 thaønh 1 vaø 1 thaønh 0.  
F = x . y + x . y . z  
Laáy ñoái ngaãu: ( x + y ) . ( x + y + z )  
5
3C-5  
Buø caùc bieán:  
F = ( x + y ) . ( x + y + z )  
III. Daïng chính taéc vaø daïng chuaån cuûa haøm Boole:  
1. Caùc tích chuaån (minterm) vaø toång chuaån (Maxterm):  
- Tích chuaån (minterm): mi (0 ≤ i ≤ 2n-1) laø caùc soá haïng tích  
(AND) cuûa n bieán maø haøm Boole phuï thuoäc vôùi quy öôùc  
bieán ñoù coù buø neáu noù laø 0 vaø khoâng buø neáu laø 1.  
- Toång chuaån (Maxterm): Mi (0 ≤ i ≤ 2n-1) laø caùc soá haïng  
toång (OR) cuûa n bieán maø haøm Boole phuï thuoäc vôùi quy  
öôùc bieán ñoù coù buø neáu noù laø 1 vaø khoâng buø neáu laø 0.  
x y z  
0 0 0  
0 0 1  
0 1 0  
0 1 1  
1 0 0  
1 0 1  
1 1 0  
1 1 1  
minterm  
m0 = x y z  
m1 = x y z  
m2 = x y z  
m3 = x y z  
m4 = x y z  
m5 = x y z  
m6 = x y z  
m7 = x y z  
Maxterm  
M0 = x + y + z  
M1 = x + y + z  
M2 = x + y + z  
M3 = x + y + z  
M4 = x + y + z  
M5 = x + y + z  
M6 = x + y + z  
M7 = x + y + z  
mi = Mi  
6
3C-6  
2. Daïng chính taéc (Canonical Form):  
a. Daïng chính taéc 1:  
laø daïng toång cuûa caùc tích chuaån (minterm) laøm cho  
haøm Boole coù giaù trò 1  
F(x, y, z) = x y z + x y z + x y z+ x y z + x y z  
= m1 + m2 + m5 + m6 + m7  
= m(1, 2, 5, 6, 7)  
x y z F  
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
1
1
0
0
1
1
1
= (1, 2, 5, 6, 7)  
F(x, y, z) =  
(x + y + z)(x + y + z) (x + y + z)  
= M0 . M3 . M4  
= M(0, 3, 4) = (0, 3, 4)  
b. Daïng chính taéc 2:  
laø daïng tích cuûa caùc toång chuaån (Maxterm) laøm cho  
7
haøm Boole coù giaù trò 0  
3C-7  
* Tröôøng hôïp haøm Boole tuøy ñònh (don’t care):  
Haøm Boole n bieán coù theå khoâng ñöôïc ñònh nghóa heát  
taát caû 2n toå hôïp cuûa n bieán phuï thuoäc. Khi ñoù taïi caùc  
toå hôïp khoâng söû duïng naøy, haøm Boole seõ nhaän giaù trò  
tuøy ñònh (don’t care), nghóa laø haøm Boole coù theå nhaän  
giaù tri 0 hoaëc 1.  
x y z  
F
0 0 0  
0 0 1  
0 1 0  
0 1 1  
1 0 0  
1 0 1  
1 1 0  
1 1 1  
X
1
1
0
0
1
1
X
F (x, y, z) = (1, 2, 5, 6) + d (0, 7)  
= (3, 4) . D (0, 7)  
8
3C-8  
3. Daïng chuaån (Standard Form):  
a. Daïng chuaån 1:  
laø daïng toång caùc tích (S.O.P – Sum of Product)  
F (x, y, z) = x y + z  
* F (x, y, z) = x y + z  
= x y (z + z) + (x + x) (y + y) z  
= x y z + x y z + x y z + x y z + x y z + x y z  
= m6 + m7 + m1 + m5 + m3  
= (1, 3, 5, 6, 7)  
* F (x, y, z) = x y + z  
= (x + z) (y + z)  
= (x + y y + z) (x x + y + z)  
= (x + y + z) (x + y + z) (x + y + z) (x + y + z)  
= M2 . M0 . M4  
= (0, 2, 4)  
9
3C-9  
b. Daïng chuaån 2:  
laø daïng tích caùc toång (P.O.S – Product of Sum)  
F (x, y, z) = (x + z) y  
* F (x, y, z) = (x + z) y = x y + y z  
= x y (z + z) + (x + x) y z  
= x y z + x y z + x y z + x y z  
= m4 + m5 + m0  
= (0, 4, 5)  
* F (x, y, z) = (x + z) y  
= (x + y y + z) (x x + y + z z)  
= (x + y + z) (x + y + z)  
(x + y + z)(x + y + z)(x + y + z)(x + y + z)  
= M3 . M1 . M7 . M6 . M2  
= (1, 2, 3, 6, 7)  
10  
3C-10  
IV. Coång logic:  
1. Coång NOT:  
x
x
t
x
x
2. Coång AND:  
x
y
x
y
z = x.y  
z
x y  
z
0 0  
0 1  
1 0  
1 1  
0
0
0
1
Vôùi coång AND coù nhieàu ngoõ vaøo,  
ngoõ ra seõ laø 1 neáu taát caû caùc ngoõ vaøo ñeàu laø 1  
11  
3C-11  
3. Coång OR:  
x
y
x
y
z = x+y  
x y  
z
0 0  
0 1  
1 0  
1 1  
0
1
1
1
z
Vôùi coång OR coù nhieàu ngoõ vaøo,  
ngoõ ra seõ laø 0 neáu taát caû caùc ngoõ vaøo ñeàu laø 0  
4. Coång NAND:  
x
x
y
z = x.y  
y
x y  
z
z
0 0  
0 1  
1 0  
1 1  
1
1
1
0
Vôùi coång NAND coù nhieàu ngoõ vaøo,  
ngoõ ra seõ laø 0 neáu taát caû caùc ngoõ vaøo ñeàu laø 1  
12  
3C-12  
5. Coång NOR:  
x
y
x
y
z = x+y  
x y  
z
0 0  
0 1  
1 0  
1 1  
1
0
0
0
z
Vôùi coång NOR coù nhieàu ngoõ vaøo,  
ngoõ ra seõ laø 1 neáu taát caû caùc ngoõ vaøo ñeàu laø 0  
6. Coång XOR (Exclusive_OR):  
x
y
x
z = xy  
y
x y  
z
0 0  
0 1  
1 0  
1 1  
0
1
1
0
z
Vôùi coång XOR coù nhieàu ngoõ vaøo, ngoõ ra seõ laø  
1 neáu toång soá bit 1 ôû c1a3ùc ngoõ vaøo laø 3sCo-1á 3leû  
z = xy = x y + x y = (x + y)(x + y)  
7. Coång XNOR (Exclusive_NOR):  
x
y
x
z = xy  
y
x y  
z
0 0  
0 1  
1 0  
1 1  
1
0
0
1
z
Vôùi coång XNOR coù nhieàu ngoõ vaøo, ngoõ ra seõ laø 1  
neáu toång soá bit 1 ôû caùc ngoõ vaøo laø soá chaün  
z = xy = x y + x y = (x + y)(x + y)  
14  
3C-14  
V. Ruùt goïn haøm Boole:  
Ruùt goïn (toái thieåu hoùa) haøm Boole nghóa laø ñöa haøm Boole  
veà daïng bieåu dieãn ñôn giaûn nhaát, sao cho:  
- Bieåu thöùc coù chöùa ít nhaát caùc thöøa soá vaø moãi thöøa soá  
chöùa ít nhaát caùc bieán.  
- Maïch logic thöïc hieän coù chöùa ít nhaát caùc vi maïch soá.  
1. Phöông phaùp ñaïi soá:  
Duøng caùc ñònh lyù vaø tieân ñeà ñeå ruùt goïn haøm.  
F (A, B, C) = (2, 3, 5, 6, 7)  
= ABC + ABC + ABC + ABC + ABC  
= AB(C + C) + AC(B + B) + AB(C + C)  
= AB + AC + AB  
= (A + A)B + AC  
15  
= B + AC  
3C-15  
2. Phöông phaùp bìa KARNAUGH:  
a. Caùch bieåu dieãn:  
- Bìa K goàm caùc oâ vuoâng, moãi oâ vuoâng bieåu dieãn cho toå  
hôïp n bieán. Nhö vaäy bìa K cho n bieán seõ coù 2n oâ.  
- Hai oâ ñöôïc goïi laø keà caän nhau khi toå hôïp bieán maø chuùng  
bieåu dieãn chæ khaùc nhau 1 bieán.  
- Trong oâ seõ ghi giaù trò töông öùng cuûa haøm Boole taïi toå hôïp  
đoù. ÔÛû daïng chính taéc 1 thì ñöa caùc giaù trò 1 vaø X leân caùc oâ,  
khoâng ñöa caùc giaù trò 0. Ngöôïc laïi, daïng chính taéc 2 thì chæ ñöa  
giaù trò 0 vaø X.  
F (A, B) = (0, 2) + d(3) = (1) . D(3)  
* Bìa 2 bieán:  
F
F
F
A
A
A
0 1  
0 1  
1 1  
0 1  
B
B
B
0 2  
1 3  
0
0
0
1
X
0X  
1
1
3C-16  
* Bìa 3 bieán:  
F
AB  
00 01 11 10  
C
0 2 6 4  
0
1 3 7 5  
1
F (A, B, C) = (2, 4, 7) + d(0, 1) = (3, 5, 6) . D(0, 1)  
F
F
AB  
AB  
00 01 11 10  
00 01 11 10  
C
C
X 1  
1
X
0
0
0
X
1
X 0  
0
1
1
17  
3C-17  
F
CD  
AB  
* Bìa 4 bieán:  
00 01 11 10  
12  
1 5 13 9  
0 4  
8
00  
01  
11  
10  
15 11  
3 7  
2 6 14 10  
* Bìa 5 bieán:  
F
A
0
1
BC  
00 01 11 10 10 11 01 00  
12 24 28 20 16  
1 5 13 9 25 29 21 17  
DE  
0 4  
8
00  
01  
11  
10  
15 11 27 31 23 19  
3 7  
2 6 14 10 26 30 22 18  
18  
3C-18  
b. Ruùt goïn bìa Karnaugh:  
* Nguyeân taéc:  
- Lieân keát ñoâi: Khi lieân keát (OR) hai oâ coù giaù trò 1 (OÂ_1)  
keà caän vôùi nhau treân bìa K, ta seõ ñöôïc 1 soá haïng tích maát ñi 1  
bieán so vôùi tích chuaån (bieán maát ñi laø bieán khaùc nhau giöõa 2 oâ).  
Hoaëc khi lieân keát (AND) hai oâ coù giaù trò 0 (OÂ_0) keà caän vôùi  
nhau treân bìa K, ta seõ ñöôïc 1 soá haïng toång maát ñi 1 bieán so vôùi  
toång chuaån (bieán maát ñi laø bieán khaùc nhau giöõa 2 oâ).  
F
F
AB  
AB  
00 01 11 10  
1 1  
00 01 11 10  
C
C
0
0
0
0
1
1
B C  
A +B  
19  
3C-19  
- Lieân keát 4: Töông töï nhö lieân keát ñoâi khi lieân keát 4  
OÂ_1 hoaëc 4 OÂ_ 0 keà caän vôùi nhau, ta seõ loaïi ñi ñöôïc 2 bieán (2  
bieán khaùc nhau giöõa 4 oâ)  
F
F
AB  
AB  
00 01 11 10  
00 01 11 10  
C
C
0 1  
1
0
1
1
0 0 0 0  
1
1
B
C
20  
3C-20  
Tải về để xem bản đầy đủ
pdf 44 trang baolam 9381
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật số - Chương 2: Đại số boole-cổng logic - Nguyễn Trọng Luật", để 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:

  • pdfbai_giang_ky_thuat_so_chuong_2_dai_so_boole_cong_logic_nguye.pdf