Bài giảng môn Thiết kế luận lí 1 - Chương 2: Đại số Boole & các cổng luận lý - Nguyễn Quang Huy

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

1. dce 2014 Khoa KH & KTMT Bộ môn Kỹ Thuật Máy Tính
2. dce 2014 Đại số Boole & các cổng luận lý
3. 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
4. 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
5. 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
6. 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) • Địnhlý1( Null Law) – x + 1 = 1 – x • 0 = 0 • Địnhlý2( Involution) – (x’ )’ = x • Địnhlý3( Idempotency) – x + x = x – x • x = x • Địnhlý4( Absorption) – x + x • y = x – x • (x + y) = x 09/03/2014 ©2014, CE Department 11
7. 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 ABCx ABx 0000 001 0011 010 0101 101 0110 110 1000 1010 A 1100 x B ? 1111 09/03/2014 ©2014, CE Department 13
8. dce 2014 Các phép toán chuyển mạch • Đại số chuyển mạch sử xyx • y x + yx’ dụng các phép toán trong 00001 luận lý mệnh đề với tên gọi khác 01011 10010 • Phép toán AND 11110 – 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
9. 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
10. 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 xyx’ y’ x’ y’ E1 = x + x’ y’ E2 = x + y’ 0011111 0110000 1001011 1100011 09/03/2014 ©2014, CE Department 19
11. 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
12. 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
13. 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 = ( x y + x’ y’ )’ 09/03/2014 ©2014, CE Department 25
14. 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
15. dce 2014 Tính phổ biến của cổng NAND 09/03/2014 ©2014, CE Department 29
16. 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’ B C ( 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