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

dce
 2014
 Khoa KH & KTMT
 Bộ môn Kỹ Thu ật Máy Tính
dce
 2014 Tài li ệu tham khảo
 •“Digital Systems, Principles and Applications ”, 
 11th Edition, Ronald J. Tocci, Neal S. Widmer, 
 Gregory L. Moss
 09/03/2014 ©2014, CE Department 2
dce
2014
 Đại số Boole &
 các cổng luận lý
dce
 2014 Nội dung
 • Đạ i số Boole
 • Đạ i số chuy ển mạch
 • Các cổng lu ận lý
 09/03/2014 ©2014, CE Department 4
dce
 2014 Đạ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
 09/03/2014 ©2014, CE Department 5
dce
 2014 Đạ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 )
 09/03/2014 ©2014, CE Department 6
dce
 2014 Đị 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 )
 09/03/2014 ©2014, CE Department 7
dce
 2014 Đị 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
 09/03/2014 ©2014, CE Department 8
dce
 2014 Đị 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
 09/03/2014 ©2014, CE Department 9
dce
 2014 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
 09/03/2014 ©2014, CE Department 10
dce
 2014 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
 09/03/2014 ©2014, CE Department 11
dce
 2014 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’
 09/03/2014 ©2014, CE Department 12
dce
 2014 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
 A 1 1 0 0
 x
 B ? 1 1 1 1
 09/03/2014 ©2014, CE Department 13
dce
 2014 Đạ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
 09/03/2014 ©2014, CE Department 14
dce
 2014 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
 gọi 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 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ý
 09/03/2014 ©2014, CE Department 15
dce
 2014 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
 09/03/2014 ©2014, CE Department 16
dce
 2014 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
 09/03/2014 ©2014, CE Department 17
dce
 2014 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
 09/03/2014 ©2014, CE Department 18
dce
 2014 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
 09/03/2014 ©2014, CE Department 19
dce
 2014 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
 09/03/2014 ©2014, CE Department 20
dce
 2014 Cổng luận lý
 • Để đạ i số chuy ển mạch có th ể th ực hi ện các công
 vi ệc trong đời th ật, cần ph ải có
 – Thi ết bị vật lý th ực hi ện các phép toán chuy ển mạch
 – Tín hi ệu vật lý (điện áp, ) thay th ế cho các bi ến chuy ển
 mạch
 •Cổng (gate ) hay cổng lu ận lý (logic gate ) là tên
 chung dùng để gọi các thi ết bị vật lý th ực hi ện các
 phép toán chuy ển mạch với độ chính xác (accuracy )
 và th ời gian tr ễ (delay ) ch ấp nh ận được
 09/03/2014 ©2014, CE Department 21
dce
 2014 Cổng luận lý
 •Mỗi cổng được bi ểu di ễn bởi 1 bi ểu tượng
 (schematic symbol ) đặ c tr ưng cùng với 1 số chân
 (pin , terminal ) tượng tr ưng cho các bi ến chuy ển
 mạch
 Một bi ểu th ức chuy ển mạch bất kỳ luôn có th ể được
 hi ện th ực trong đời th ật bằng cách kết nối các cổng
 lu ận lý lại với nhau
 
 Mạch luận lý (logic circuit ) hay mạch chuy ển mạch
 (switching circuit )
 09/03/2014 ©2014, CE Department 22
dce
 2014 Bi ểu t ượng của các cổng luận lý
 •Cổng AND x x . y
 y
 •Cổng NOR x
 (x + y)’
 •Cổng OR y
 x x + y
 y •Cổng XOR 
 x
 x⊕⊕⊕ y
 •Cổng NOT y
 (c ổng đả o - inverter )
 x x’ •Cổng XNOR 
 x
 (x⊕⊕⊕ y)’
 y
 •Cổng NAND
 • Các c ổng nhi ều 
 x (x . y)’
 y hơn 2 ngõ nh ập
 09/03/2014 ©2014, CE Department 23
dce
 2014 Dạng t ương đương
 09/03/2014 ©2014, CE Department 24
dce
 2014 Di ễn dịch bi ểu t ượng cổng luận lý
 •Dạng tương đương của cổng AND
 – Ngõ xu ất ở mức cao khi tất cả các ngõ nh ập ở mức cao
 – Ngõ xu ất ở mức th ấp khi một trong các ngõ nh ập ở mức
 th ấp
 •Một số cấu trúc của cổng XOR
 – E = x ⊕ y = x y’ + x’ y = (xy + x’y’)’
 09/03/2014 ©2014, CE Department 25
dce
 2014 Tích cực cao – Tích cực thấp
 • Hai tr ạng thái ho ạt độ ng của thi ết bị là tích cực
 (activity ) và không tích cực (inactivity )
 – Xét các thí dụ đố i với điện tho ại, đèn, độ ng cơ, v.v
 • Tích cực cao (active high )
 tích cực → lu ận lý 1 → mức điện áp cao H
 • Tích cực th ấp (active low)
 tích cực → lu ận lý 0 → mức điện áp th ấp L
 09/03/2014 ©2014, CE Department 26
dce
 2014 Mạch tích hợp
 •Cổng NOT 7404 •Cổng OR 7432
 •Cổng AND 7408 •Cổng NOR 7402
 •Cổng NAND 7400 •Cổng Ex-OR 7486
 09/03/2014 ©2014, CE Department 27
dce
 2014 Tập phổ bi ến của các phép toán
 •Một tập các phép toán đượ c gọi là ph ổ bi ến (universal ) nếu
 mọi hàm chuy ển mạch đề u có th ể đượ c bi ểu di ễn một cách
 tườ ng minh ch ỉ bởi các phép toán của tập trên
 • Đố i với các phép toán chuy ển mạch đã xét, ta có một số các
 tập ph ổ bi ến sau
 –Tập { NOT , AND , OR }
 –Tập { NOT , AND }
 –Tập { NOT , OR }
 –Tập { NAND }
 –Tập { NOR }
 –Tập ...
 Bất kỳ hàm chuy ển mạch nào cũng đề u có th ể đượ c bi ểu di ễn một
 cách tườ ng minh ch ỉ bởi các phép toán NOT và AND
 ...
 09/03/2014 ©2014, CE Department 28
dce
 2014 Tính phổ bi ến của cổng NAND
 09/03/2014 ©2014, CE Department 29
dce
 2014 Tính phổ bi ến của cổng NOR
 09/03/2014 ©2014, CE Department 30
dce
 2014 Xác đị nh giá tr ị ngõ xuất mạch luận lý
 •Sử dụng bi ểu th ức Boole cho ngõ xu ất của mạch lu ận lý
 –Với 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ử dụng tr ực ti ếp sơ đồ mạch lu ận lý mà không cần sử
 dụng bi ểu th ức Boolean
 09/03/2014 ©2014, CE Department 31
dce
 2014 Gi ản đồ xung theo thời gian (Timing Waveform)
 09/03/2014 ©2014, CE Department 32