zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Báo xấu

109
lượt xem 11
download

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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ý

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’ + 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
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
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
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
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
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
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
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
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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.