Bài giảng Kỹ thuật điện tử số: Đại số Boole - Đại số logic giới thiệu với người đọc về đại số Boole - đạo số logic, các tiên đề trong đại số logic, các định lý, nguyên lý của tính đối ngẫu, cách biểu diễn hàm logic.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Kỹ thuật điện tử số: Đại số Boole - Đại số logic
- ð i s Boole
ð i s logic
Nguy n Qu c Cư ng – 3I
1
N i dung
• Gi i thi u
• Các tiên ñ trong ñ i s logic
• Các ñ nh lý
• Nguyên lý c a tính ñ i ng u (duality)
• Cách bi u di n hàm logic
2
- Tài li u tham kh o
• Digital Design: Principles & Practices – John F
Wakerly – Printice Hall
3
Gi i thi u
• 1854 nhà toán h c Anh, Gorge Boole (1815-
1864) phát minh ra h th ng ñ i s ch có hai
giá tr
• Năm 1938, t i Bell Lab, Claude E. Shannon ñã
ch ra cách áp d ng ñ i s Boole vào phân tích
và mô t các m ch s d ng rơle (còn g i là
switching algebra), và cũng ñư c áp d ng cho
các phân tích m ch s hi n nay.
4
- Tiên ñ
• Tiên ñ 1:
(A1) X = 0 if X ≠ 1
(A1’) X = 1 if X ≠ 0
• Tiên ñ 2: (ñ nh nghĩa toán t ñ o)
(A2): If X = 0 then X’ = 1
(A2’): If X = 1 then X’ = 0
Toán t “ ‘ “ là toán t ñ o hay bù
(m t s ký hi u khác c a toán t ñ o: ~ X , X )
Tuy nhiên vi c s d ng ‘ thư ng ñư c s d ng trong
các ngôn ng l p trình HDLs)
5
• Tiên ñ 3 , 4 và 5 :ð nh nghĩa các toán VÀ và
HO C logic:
Toán t AND s d ng ký hi u ·
Toán t OR s d ng ký hi u +
T t c các h th ng logic ñ u có th mô t và phân tích d a trên 5 tiên ñ trên
6
- Ký hi u các ph n t logic trên sơ ñ
7
ð nh lý cho m t bi n
Vi c ch ng minh các ñ nh lý này có th s d ng phương pháp quy n p
hoàn toàn (vì s giá tr c a các bi n ch có 0 và1 nên r t d áp d ng
phương pháp quy n p)
8
- cho 2 và ba bi n
Chú ý: ñ thu n ti n thư ng vi t X · Y thay cho ( X · Y )
9
Cho n bi n
ð ch ng minh s d ng phương pháp quy n p h u h n:
• ch ng minh ñúng v i n = 2
• gi thi t ñúng v i n = i, chúng minh ñúng v i n = i+1
10
- Nguyên lý ñ i ng u
• Các ñ nh lý hay ñ ng nh t th c trong ñ i s
logic s luôn ñúng n u thay 0 và 1 tráo ñ i cho
nhau và ñ ng th i · và + cũng ñư c tráo ñ i cho
nhau.
• Hàm ñ i ng u:
– Cho hàm logic F(X1,X2,…,Xn, + , · , ’)
– Hàm ñ i ng u c a F ñư c ñ nh nghĩa là hàm có cùng
d ng bi u th c v i các toán t · và + ñư c ñ i ch
cho nhau
FD(X1,X2,…,Xn, + , · , ’) = F(X1,X2,…,Xn, · , + , ’)
+ và · ñ i ch 11
Nguyên lý ñ i ng u và ñ nh lý DeMorgan
[F(X1,X2,…,Xn)]’ = FD(X1’, X2’,…,Xn’)
F(X1,X2,…,Xn) = [FD(X1’, X2’,…,Xn’)]’
(ñ nh lý DeMorgan)
12
- Bi u di n hàm logic thông qua b ng
B ng s th c (không bao
g m hàng ROW), tuy nhiên
thư ng ñư c s d ng ñ
ch giá tr t h p c a các
bi n
13
14
- M t s khái ni m
• H s ch (literal): là m t bi n ñơn , ho c ph n bù c a
nó. Ví d : X, Y, X’,...
• S h ng tích (product term): là m t literal ho c tích logic
c a nhi u literal
Ví d : Z’, X ¢ Y, X’ ¢ Y ¢ Z’
• Bi u th c t ng c a các tích: là m t t ng logic c a các s
h ng tích
• S h ng t ng (sum term): là m t literal ho c t ng logic
c a nhi u literal
Ví d : X’, X+Y+Z’
• Bi u th c tích c a các t ng: là tích logic c a các s h ng
t ng
15
• M t s h ng chu n (normal term): là m t s h ng tích
ho c t ng mà trong ñó không có bi n nào xu t hi n hơn
m tl n
• Ví d các s h ng không chu n:
• X + Y + X’, Y ¢ X ¢ X’ ¢ Z
• Ví d các s h ng chu n:
• X + Y, X ¢ Y ¢ Z
• minterm n bi n: là m t s h ng tích chu n c a n literal
• maxterm n bi n: là s h ng t ng chu n c a n literal
16
- 17
• Minterm: có th ñư c ñ nh nghĩa là s h ng tích
ng v i m t hàng c a b ng chân lý sao cho tích
ñó b ng 1
• Maxterm: có th ñư c ñ nh nghĩa là s h ng
t ng ng v i m t hàng c a b ng chân lý sao
cho t ng ñó b ng 0
18
- 19
Bi u di n hàm qua minterm và maxterm
• Hàm logic có th bi u di n dư i d ng:
– canonical sum: t ng c a các minterm ng v i các
hàng c a b ng chân lý mà t i ñó giá tr hàm b ng 1
– canonical product: tích c a các maxterm ng v i các
hàng c a b ng chân lý mà t i ñó giá tr hàm b ng 0
20
- 21
• ð ñơn gi n trong ký hi u, ngư i ta thư ng s
d ng d ng vi t rút g n sau:
X, Y , Z là các bi n, ñi kèm v i ch s các hàng tương ng c a các
minterm ho c maxterm
22
- T i thi u hóa hàm logic
• Hàm logic có th bi u di n thông qua:
– canonical sum
– canonical product
Tuy nhiên ñó là các d ng chưa ñư c t i thi u.
• ð gi m s input hay s gate s d ng trong
m ch c n ph i t i thi u hóa m ch.
23
Bìa Karnaugh
• Là cách bi u di n ñ h a c a b ng chân lý
24
- • K-map : n bi n s có 2n ô
• M i m t ô trong K-map ng v i m t hàng trong
b ng chân lý.
• Quy ư c các ô k nhau thì t h p các bi n ch
ñư c khác nhau m t giá tr
• K-map ch thu n ti n s d ng cho hàm logic có
6 bi n tr xu ng
• T K-map có th vi t ñư c các canonical sum
ho c canonical product tương t như b ng chân
lý
25
T i thi u hóa d ng t ng các tích
‘
‘
26
- • Quy t c nhóm các ô c a K-map:
– Nhóm 2k các ô có giá tr 1 k nhau sao cho k là max (
1 ≤ k ≤ n, v i n là s bi n)
– Có chính xác (n-k) bi n có giá tr không ñ i trong s
các ô ñư c nhóm
• D ng tích:
– n u bi n có giá tr là 1 trong 2k ô ñư c nhóm thì
product term s ch a bi n ñó
– n u bi n có giá tr 0 trong 2k ô ñư c nhóm thì product
term s ch a bù c a bi n ñó
– n u bi n có c giá tr 1 và 0 trong 2k ô ñư c nhóm thì
nó s không xu t hi n trong product term
27
các nhóm không ñúng
28
- ví d
29
• D ng t i gi n s d ng K-map không ph i là duy
nh t
30
- T i thi u hóa d ng tích các t ng
• Nhóm 2k các ô có giá tr 0 k nhau sao cho k là
max:
– n u bi n có giá tr là 1 trong 2k ô ñư c nhóm thì sum-
term s ch a bù c a bi n ñó
– n u bi n có giá tr 0 trong 2k ô ñư c nhóm thì sum-
term s ch a bi n ñó
– n u bi n có c giá tr 1 và 0 trong 2k ô ñư c nhóm thì
nó s không xu t hi n trong sum term
31
Các t h p ñ u vào “Don’t-Care”
• Trong trư ng h p ng v i m t s t h p giá tr
các inputs giá tr hàm logic có th tùy ý (b ng 0
ho c b ng 1) các t h p “don’t-care”
• S d ng các t h p “don’t-care” trong t i gi n
hàm:
– Cho phép t h p don’t-care tham gia vào các ô sao
cho s ô 2k là l n nh t
– Không nhóm các ô ch toàn don’t-care
32
- 33
Các phương pháp t i gi n s d ng chương
trình
• Khi s bi n l n, s d ng thu t toán:
– Queen-McCluskey (tham kh o)
– Espresso II, Espresso-MV (tham kh o)
34
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
