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

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

1. dce 2012 Tài li u tham kh o •“Digital Systems, Principles and Applications ”, 8th /5 th Edition, R.J. Tocci, Prentice Hall •“Digital Logic Design Principles ”, N. Balabanian & B. Carlson – John Wiley & Sons Inc., 2004 ©2012, CE Department 2
2. dce 2012 Ni dung • Đ i s Boole • Đ i s chuy n mch • Các cng lu n lý ©2012, CE Department 4
3. dce 2012 Đ i s Boole • Đ i s Boole, cũng tươ ng t nh ư các h đ i s khác, đư c xây dng thông qua vi c xác đ nh ngh ĩa mt s nh ng vn đ cơ bn sau: – Mi n (domain ), là tp hp (set ) các ph n t (element ) mà trên đó đ nh ngh ĩa nên h đ i s – Tp hp các phép toán (operation ) th c hi n đư c trên mi n –Mt tp hp các đ nh đ (postulate ), hay tiên đ (axiom ) đư c công nh n không qua ch ng minh. Đ nh đ ph i đ m bo tính nh t quán (consistency ) và tính đ c lp (independence ) –Mt tp hp các h qu (consequence ) đư c gi là đ nh lý (theorem ), đ nh lu t (law ) hay quy tc (rule ) ©2012, CE Department 6
4. dce 2012 Đ nh đ Huntington • Tính đ ng nh t (identity ) Nu x là mt ph n t trong mi n B thì –Tn ti 1 ph n t 0 trong B , gi là ph n t đ ng nh t vi phép toán + , th a mãn tính ch t x + 0 = x –Tn ti 1 ph n t 1 trong B , gi là ph n t đ ng nh t vi phép toán • , th a mãn tính ch t x • 1 = x • Tính giao hoán (commutative ) – Giao hoán ca phép + : x + y = y + x – Giao hoán ca phép • : x • y = y • x ©2012, CE Department 8
5. dce 2012 Tính đ i ng u ( duality ) • Quan sát các đ nh đ Hungtinton, ta th y chúng mang tính đ i xng (symmetry ) tc là các đ nh đ xu t hi n theo cp •Mi đ nh đ trong 1 cp có th đư c xây dng t đ nh đ còn li bng cách – Thay đ i các phép toán 2 ngôi ( + | • ) – Thay đ i các ph n t đ ng nh t ( 0 | 1 ) • Có th suy ra mt kt qu nào đó t các đ nh đ bng cách – Hoán đ i phép toán + vi phép toán • – Hoán đ i ph n t đ ng nh t 0 vi ph n t đ ng nh t 1 • Điu này th hi n tính đ i ng u đ i s Boole ©2012, CE Department 10
6. dce 2012 Các đ nh lý c ơ b n • Đ nh lý 5 (Simplification ) – x + x’ y = x + y – x (x’ + y ) = x y • Đ nh lý 6 (Associative Law ) – x + (y + z) = (x + y ) + z = x + y + z – x (y z) = (x y) z = x y z • Đ nh lý 7 (Consensus ) – x y + x’ z + y z = x y + x’ z – (x + y)(x’ + z)(y + z) = (x + y)(x’ + z) • Đ nh lý 8 (De Morgan’s Law ) – (x + y)’ = x’ y’ – (x y)’ = x’ + y’ ©2012, CE Department 12
7. dce 2012 Đ i s chuy n m ch ( switching algebra ) • Đ i vi đ i s Boole, mi n không b hn ch (không có gi i hn đ t ra đ i vi s lư ng các ph n t trong mi n) • Các đ nh đ Huntington gi i hn xem xét đ i s Boole vi 2 ph n t đ ng nh t mà thôi
   Đ i s Boole 2 ph n t •Năm 1937, Claude Shannon hi n th c đ i s Boole 2 ph n t bng mch đin vi các chuy n mch (switch ) – Chuy n mch là thi t b có 2 v trí bn: tt (off ) hay m (on ) – 2 v trí này phù hp đ bi u di n cho 0 hay 1
   Đ i s Boole 2 ph n t còn đư c g i là đ i s chuy n m ch – Các ph n t đ ng nh t đư c gi là các hng chuy n mch (switching constant ) – Các bi n (variable ) bi u di n các hng chuy n mch đư c gi là các bi n chuy n mch (switching variable )  tín hi u ©2012, CE Department 14
8. dce 2012 Các phép toán chuy n m ch • Các phép toán chuy n mch có th đư c hi n th c bi mch ph n cng •Bng s th t có th s dng nh ư 1 công c dùng đ xác minh quan h gi a các phép toán chuy n mch •S dng bng s th t đ ch ng minh đ nh lý De Morgan (x + y)’ = x’ y’ x y x’ y’ x + y (x + y)’ x’ y’ 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 ©2012, CE Department 16
9. dce 2012 Bi u th c ( expression ) chuy n m ch •Mt bi u th c có th đư c chuy n thành nhi u dng tươ ng đươ ng bng cách s dng các lu t Boole E = (x + y z)(x + y’ ) + (x + y)’E3 =x + x’ y’ E1 = x x + x y’ + x y z + y y’ z + x’ y’ E4 =x + y’ E2 = x + x (y’ + y z) + x’ y’ • Ti sao ph i chuy n đ i dng ca các bi u th c ? • Các thành ph n th a (redundant ) trong bi u th c – literal lp ( x x hay x + x) – bi n và bù ( x x’ hay x + x’ ) – hng (0 hay 1) • Không hi n th c các thành ph n th a ca bi u th c vào mch ©2012, CE Department 18
10. dce 2012 Các phép toán chuy n m ch khác • Phép toán NAND • Phép toán Exclusive OR – Phép toán 2 ngôi tươ ng – E = x ⊕⊕⊕ y = x’ y + x y’ đươ ng vi (NOT AND ) • Phép toán NOR • Phép toán XNOR (Ex. NOR) – Phép toán 2 ngôi tươ ng – E = ( x ⊕⊕⊕ y )’ = x y + x’ y’ đươ ng vi (NOT OR ) Bi n NAND NOR Ex. OR XNOR x y (x . y)’ (x + y)’ x ⊕⊕⊕ y (x ⊕⊕⊕ y)’ 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 ©2012, CE Department 20
11. dce 2012 Cng lu n lý •Mi cng đư c bi u di n bi 1 bi u tư ng (schematic symbol ) đ c tr ưng cùng vi 1 s chân (pin , terminal ) tư ng tr ưng cho các bi n chuy n mch Mt bi u th c chuy n mch bt kỳ luôn có th đư c hi n th c trong đ i th t bng cách kt ni các cng lu n lý li vi nhau
    Mch lu n lý (logic circuit ) hay mch chuy n mch (switching circuit ) ©2012, CE Department 22
12. dce 2012 Dng t ươ ng đươ ng ©2012, CE Department 24
13. dce 2012 Tích c c cao – Tích c c th p • Hai tr ng thái ho t đ ng ca thi t b là tích cc (activity ) và không tích cc (inactivity ) – Xét các thí d đ i vi đin tho i, đèn, đ ng cơ, v.v • Do thói quen, qui ư c tích cc ng vi lu n lý 1 còn không tích cc ng vi lu n lý 0 • Tích cc cao (active high ) tích c c →→→ lu n lý 1 →→→ mc đin áp cao H • Tích cc th p (active low ) tích c c →→→ lu n lý 0 →→→ mc đin áp th p L ©2012, CE Department 26
14. dce 2012 Tp ph bi n c a các phép toán •Mt tp các phép toán đư c gi là ph bi n (universal ) nu mi hàm chuy n mch đ u có th đư c bi u di n mt cách tư ng minh ch bi các phép toán ca tp trên • Đ i vi các phép toán chuy n mch đã xét, ta có mt s các tp ph bi n sau –Tp { NOT , AND , OR } – Tp { NOT , AND } –Tp { NOT , OR } –Tp { NAND } –Tp { NOR } –Tp Bt kỳ hàm chuy n mch nào cũng đ u có th đư c bi u di n mt cách tư ng minh ch bi các phép toán NOT và AND ©2012, CE Department 28
15. dce 2012 Tính ph bi n c a c ng NOR ©2012, CE Department 30
16. dce 2012 Gi n đ xung theo th i gian (Timing Waveform) ©2012, CE Department 32
17. dce 2012 Bài t p •Tt c bài tp trong sách Digital System ca Ronal Tocci Ch ươ ng 3: Logic Gates and Boolean Algebra  Th y Nguy n Quang Huy Email huynguyen@cse.hcmut.edu.vn ©2012, CE Department 34