Bài giảng Thiết kế luận lí 1 - Chương 2: Đại số Boole & các cổng luận lý - Nguyễn Quang Huy

Nội dung text: Bài giảng Thiết kế luận lí 1 - Chương 2: Đại số Boole & các cổng luận lý - Nguyễn Quang Huy

1. dce 2012 Khoa KH & KTMT Bộ môn Kỹ Thu ật Máy Tính BK TP.HCM ©2012, CE Department
2. dce 2012 Đạ i số Boole & BK TP.HCM ácc cc áccổng lu ận lýlý ©2012, CE Department
3. dce 2012 Đ i s Boole • Đ i s Boole đư c th gi i bi t đ n ln đ u tiên bi George Boole qua tác ph m “An Investigation of the Laws of Thought ” vào năm 1854 • Các hng và bi n Boole ch đư c mang 2 giá tr 0 ho c 1 ( LOW / HIGH ) – Các bi n Boole bi u di n cho mt kho ng đin áp trên đư ng dây ho c ti ngõ nh p/ngõ xu t ca mch – Giá tr 0 ho c 1 đư c gi là mc lu n lý (logic level ) A F Mch ngõ nh p ngõ xu t lu n lý x y ©2012, CE Department 5
4. dce 2012 Đ nh đ Huntington • Phát bi u bi nhà toán hc Anh E.V.Huntington trên cơ s h th ng hóa các công trình ca G. Boole –S dng các phép toán trong lu n lý mnh đ (propositional logic ) • Tính đóng (closure ) – Tn ti mi n B vi ít nh t 2 ph n t phân bi t và 2 phép toán + và • sao cho: •Nu x và y là các ph n t thu c B thì x + y cũng là 1 ph n t thu c B (phép cng lu n lý - logical addition ) •Nu x và y là các ph n t thu c B thì x • y cũng là 1 ph n t thu c B (phép nhân lu n lý - logical multiplication ) ©2012, CE Department 7
5. dce 2012 Đ nh đ Huntington • Tính phân ph i (distributive ) – Phép • có tính phân ph i trên phép + x • (y + z) = (x • y) + (x • z) – Phép + có tính phân ph i trên phép • x + (y • z) = (x + y) • (x + z) • Bù (complementation ) Nu x là 1 ph n t trong mi n B thì s tn ti mt ph n t khác gi là x’ (hay x ), là ph n t bù ca x th a mãn: – x + x’ = 1 và – x • x’ = 0 ©2012, CE Department 9
6. dce 2012 Các đ nh lý c ơ b n ( fundamental theorem ) • Các đ nh lý đư c ch ng minh t các đ nh đ Huntington và các đ nh đ đ i ng u theo 2 cách – Ch ng minh bng ph n ch ng (contradiction ) – Ch ng minh bng quy np (induction ) • Đ nh lý 1 (Null Law ) – x + 1 = 1 – x • 0 = 0 • Đ nh lý 2 (Involution ) – (x’ )’ = x • Đ nh lý 3 (Idempotency ) – x + x = x – x • x = x • Đ nh lý 4 (Absorption ) – x + x • y = x – x • (x + y) = x ©2012, CE Department 11
7. dce 2012 Bng s th t (Truth table) • Ph ươ ng ti n mô t s ph thu c ca ngõ xu t vào mc lu n lý (logic level) ti các ngõ nh p ca mch – Li t kê tt c các t hp có th ca mc lu n lý ti các ngõ nh p và kt qu mc lu n lý tươ ng ng ti ngõ xu t ca mch –S t hp ca bng N-ngõ nh p: 2N A B C x A B x 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 0 A 1 1 0 0 x B ? 1 1 1 1 ©2012, CE Department 13
8. dce 2012 Các phép toán chuy n m ch • Đ i s chuy n mch s x y x • y x + y x’ dng các phép toán trong 0 0 0 0 1 lu n lý mnh đ vi tên gi khác 0 1 0 1 1 1 0 0 1 0 • Phép toán AND 1 1 1 1 0 – Phép toán 2 ngôi tươ ng đươ ng vi phép nhân Bng s th t các phép chuy n m ch lu n lý • Phép toán OR • Phép toán NOT – Phép toán 2 ngôi tươ ng – Phép toán 1 ngôi đươ ng vi phép cng tươ ng đươ ng vi lu n lý phép bù lu n lý ©2012, CE Department 15
9. dce 2012 Bi u th c ( expression ) chuy n m ch • Bi u th c chuy n mch là mt quan h hu hn các hng, bi n, bi u th c chuy n mch liên kt vi nhau bi các phép toán AND , OR và NOT • Ví d y + 1 , x x’ + x , z ( x + y’ )’ E = ( x + y z ) ( x + y’ ) + ( x + y )’ • literal đư c s dng đ ám ch bi n hay bù ca bi n ©2012, CE Department 17
10. dce 2012 Hàm ( function ) chuy n m ch • Hàm chuy n mch (switching function ) là mt phép gán xác đ nh và duy nh t ca nh ng giá tr 0 và 1 cho tt c các t hp giá tr ca các bi n thành ph n • Hàm đư c xác đ nh bi danh sách các tr hàm ti mi t hp giá tr ca bi n (bng s th t) –Tn ti nhi u bi u th c bi u di n cho 1 hàm • S lư ng hàm chuy n mch vi n bi n là 2 lu th a 2n x y x’ y’ x’ y’ E1 = x + x’ y’ E2 = x + y’ 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 1 ©2012, CE Department 19
11. dce 2012 Cng lu n lý • Đ đ i s chuy n mch có th th c hi n các công vi c trong đ i th t, cn ph i có – Thi t b vt lý th c hi n các phép toán chuy n mch – Tín hi u vt lý (đin áp, ) thay th cho các bi n chuy n mch • Cng (gate ) hay cng lu n lý (logic gate ) là tên chung dùng đ gi các thi t b vt lý th c hi n các phép toán chuy n mch vi đ chính xác (accuracy ) và th i gian tr (delay ) ch p nh n đư c ©2012, CE Department 21
12. dce 2012 Bi u t ư ng c a các c ng lu n lý •Cng AND x x . y y •Cng NOR x (x + y)’ •Cng OR y x x + y y •Cng XOR x x⊕⊕⊕ y • Cng NOT y (c ng đ o - inverter ) x x’ •Cng XNOR x (x⊕⊕⊕ y)’ y •Cng NAND • Các c ng nhi u x (x . y)’ y hơn 2 ngõ nh p ©2012, CE Department 23
13. dce 2012 Di n d ch bi u t ư ng c ng lu n lý •Dng tươ ng đươ ng ca cng AND – Ngõ xu t mc cao khi tt c các ngõ nh p mc cao – Ngõ xu t mc th p khi mt trong các ngõ nh p mc th p •Mt s cu trúc ca cng XOR – E = x ⊕⊕⊕ y = x y’ + x’ y = (xy + x’y’)’ ©2012, CE Department 25
14. dce 2012 Mch tích h p •Cng NOT 7404 •Cng OR 7432 •Cng AND 7408 •Cng NOR 7402 •Cng NAND 7400 •Cng Ex-OR 7486 ©2012, CE Department 27
15. dce 2012 Tính ph bi n c a c ng NAND ©2012, CE Department 29
16. dce 2012 Xác đ nh giá tr ngõ xu t m ch lu n lý •S dng bi u th c Boole cho ngõ xu t ca mch lu n lý –Vi A = 0, B = 1, C = 1, D = 1 x = A’BC (A+D)’ = 0’. 1 . 1 . (0 + 1)’ = 1 . 1 . 1 . 1’ = 1 . 1 . 1 . 0 = 0 • S dng tr c ti p sơ đ mch lu n lý mà không cn s dng bi u th c Boolean ©2012, CE Department 31
17. dce 2012 Đ c thêm • Ch ươ ng 3: Logic Gates and Boolean Algebra trong sách Digital system ca Ronal Tocci ©2012, CE Department 33