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

Đạ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
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế luận lý 1 - Đại số Boole & các cổng luận lý dce 2012 Khoa KH & KTMT Bộ môn Kỹ Thuật Máy Tính BK TP.HCM ©2012, CE Department 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 dce 2012 Đại số Boole & BK TP.HCM các cổng luận lý ©2012, CE Department 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 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 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 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 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 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 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 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 dce 2012 Các đ nh lý cơ b n … • Đ nh lý 5 (Simplification) – x + x’ y = x + y – x (x’ ...