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

Chia sẻ: Luong My | Ngày: | Loại File: PDF | Số trang:34

0
33
lượt xem
7
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đại số Boole được thế giới biết đến lần đầu tiên bởi George Boole qua tác phẩm " An Investigation of the Laws of Thought" vào năm 1854. Các hằng và biến Boole chỉ được mang 2 giá trị 0 hoặc 1

Chủ đề:
Lưu

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

  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 Tài li u tham kh o • “Digital Systems, Principles and Applications”, 8th/5th Edition, R.J. Tocci, Prentice Hall • “Digital Logic Design Principles”, N. Balabanian & B. Carlson – John Wiley & Sons Inc., 2004 ©2012, CE Department 2
  3. dce 2012 Đại số Boole & BK TP.HCM các cổng luận lý ©2012, CE Department
  4. dce 2012 N i dung • Đ i s Boole • Đ i s chuy n m ch • Các c ng lu n lý ©2012, CE Department 4
  5. dce 2012 Đ i s Boole • Đ i s Boole đư c th gi i bi t đ n l n đ u tiên b i George Boole qua tác ph m “An Investigation of the Laws of Thought” vào năm 1854 • Các h ng 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 m t kho ng đi n áp trên đư ng dây ho c t i ngõ nh p/ngõ xu t c a m ch – Giá tr 0 ho c 1 đư c g i là m c lu n lý (logic level) A F M ch ngõ nh p ngõ xu t lu n lý x y ©2012, CE Department 5
  6. dce 2012 Đ i s Boole • Đ i s Boole, cũng tương t như các h đ i s khác, đư c xây d ng thông qua vi c xác đ nh nghĩa m t s nh ng v n đ cơ b n sau: – Mi n (domain), là t p h p (set) các ph n t (element) mà trên đó đ nh nghĩa nên h đ i s – T p h p các phép toán (operation) th c hi n đư c trên mi n – M t t p h p các đ nh đ (postulate), hay tiên đ (axiom) đư c công nh n không qua ch ng minh. Đ nh đ ph i đ m b o tính nh t quán (consistency) và tính đ c l p (independence) – M t t p h p các h qu (consequence) đư c g i là đ nh lý (theorem), đ nh lu t (law) hay quy t c (rule) ©2012, CE Department 6
  7. dce 2012 Đ nh đ Huntington • Phát bi u b i nhà toán h c Anh E.V.Huntington trên cơ s h th ng hóa các công trình c a G. Boole –S d ng các phép toán trong lu n lý m nh đ (propositional logic) • Tính đóng (closure) – T n t i mi n B v i ít nh t 2 ph n t phân bi t và 2 phép toán + và • sao cho: • N u 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 c ng lu n lý - logical addition) • N u 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
  8. dce 2012 Đ nh đ Huntington … • Tính đ ng nh t (identity) N u x là m t ph n t trong mi n B thì – T n t i 1 ph n t 0 trong B , g i là ph n t đ ng nh t v i phép toán + , th a mãn tính ch t x + 0 = x – T n t i 1 ph n t 1 trong B , g i là ph n t đ ng nh t v i phép toán • , th a mãn tính ch t x • 1 = x • Tính giao hoán (commutative) – Giao hoán c a phép + : x + y = y + x – Giao hoán c a phép • : x • y = y • x ©2012, CE Department 8
  9. 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) N u x là 1 ph n t trong mi n B thì s t n t i m t ph n t khác g i là x’ (hay x ), là ph n t bù c a x th a mãn: – x + x’ = 1 và – x • x’ = 0 ©2012, CE Department 9
  10. dce 2012 Tính đ i ng u (duality) • Quan sát các đ nh đ Hungtinton, ta th y chúng mang tính đ i x ng (symmetry) t c là các đ nh đ xu t hi n theo c p • M i đ nh đ trong 1 c p có th đư c xây d ng t đ nh đ còn l i b ng 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 m t k t qu nào đó t các đ nh đ b ng cách – Hoán đ i phép toán + v i phép toán • – Hoán đ i ph n t đ ng nh t 0 v i ph n t đ ng nh t 1 • Đi u này th hi n tính đ i ng u đ i s Boole ©2012, CE Department 10
  11. 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 b ng ph n ch ng (contradiction) – Ch ng minh b ng quy n p (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
  12. 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
  13. dce 2012 B ng s th t (Truth table) • Phương ti n mô t s ph thu c c a ngõ xu t vào m c lu n lý (logic level) t i các ngõ nh p c a m ch – Li t kê t t c các t h p có th c a m c lu n lý t i các ngõ nh p và k t qu m c lu n lý tương ng t i ngõ xu t c a m ch – S t h p c a b ng 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 1 1 0 0 A ? x 1 1 1 1 B ©2012, CE Department 13
  14. dce 2012 Đ i s chuy n m ch (switching algebra) • Đ i v i đ i s Boole, mi n không b h n ch (không có gi i h n đ t ra đ i v i s lư ng các ph n t trong mi n) • Các đ nh đ Huntington gi i h n xem xét đ i s Boole v i 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 b ng m ch đi n v i các chuy n m ch (switch) – Chuy n m ch là thi t b có 2 v trí b n: t t (off) hay m (on) – 2 v trí này phù h p đ 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 g i là các h ng chuy n m ch (switching constant) – Các bi n (variable) bi u di n các h ng chuy n m ch đư c g i là các bi n chuy n m ch (switching variable) tín hi u ©2012, CE Department 14
  15. dce 2012 Các phép toán chuy n m ch • Đ i s chuy n m ch s x y x•y x+y x’ d ng các phép toán trong 0 0 0 0 1 lu n lý m nh đ v i tên 0 1 0 1 1 g i khác 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 v i phép nhân B ng 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 v i phép c ng tương đương v i lu n lý phép bù lu n lý ©2012, CE Department 15
  16. dce 2012 Các phép toán chuy n m ch … • Các phép toán chuy n m ch có th đư c hi n th c b i m ch ph n c ng • B ng s th t có th s d ng như 1 công c dùng đ xác minh quan h gi a các phép toán chuy n m ch • S d ng b ng 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
  17. dce 2012 Bi u th c (expression) chuy n m ch • Bi u th c chuy n m ch là m t quan h h u h n các h ng, bi n, bi u th c chuy n m ch liên k t v i nhau b i 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 d ng đ ám ch bi n hay bù c a bi n ©2012, CE Department 17
  18. dce 2012 Bi u th c (expression) chuy n m ch... • M t bi u th c có th đư c chuy n thành nhi u d ng tương đương b ng cách s d ng 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’ • T i sao ph i chuy n đ i d ng c a các bi u th c ? • Các thành ph n th a (redundant) trong bi u th c – literal l p ( x x hay x + x) – bi n và bù ( x x’ hay x + x’) – h ng (0 hay 1) • Không hi n th c các thành ph n th a c a bi u th c vào m ch ©2012, CE Department 18
  19. dce 2012 Hàm (function) chuy n m ch • Hàm chuy n m ch (switching function) là m t phép gán xác đ nh và duy nh t c a nh ng giá tr 0 và 1 cho t t c các t h p giá tr c a các bi n thành ph n • Hàm đư c xác đ nh b i danh sách các tr hàm t i m i t h p giá tr c a bi n (b ng s th t) – T n t i nhi u bi u th c bi u di n cho 1 hàm • S lư ng hàm chuy n m ch v i 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
  20. 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 v i (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 v i (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
Đồng bộ tài khoản