›
›

Bài giảng Điện tử số: Các hàm logic cơ bản

pdf 30 trang hapham 2920
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Điện tử số: Các hàm logic cơ bản", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_dien_tu_so_cac_ham_logic_co_ban.pdf

Nội dung text: Bài giảng Điện tử số: Các hàm logic cơ bản

  1. 11/13/2009 Môn học Điện tử số Bộ môn Kỹ thuật Máy tính Viện CNTT&TT- ĐH BKHN Hungpn-fit@mail.hut.edu.vn 1 Tài liệu tham khảo Kỹ thuật số Lý thuyết mạch lôgic và kỹ thuật số Kỹ thuật điện tử số Foundation of Digital Logic Design, G.Langholz, A. Kandel, J. Mott, World Scientific, 1998 Introduction to Logic Design, 2nd Ed,, Alan B, Marcovitz, Mc. Graw Hill,2005 dce.hut.edu.vn 2 1
  2. 11/13/2009 Nội dung môn học Chương 1. Các hàm logic cơ bản Chương 2. Các cổng logic cơ bản và mạch thực hiện Chương 3. Hệ tổ hợp Chương 4. Hệ dãy Chương 5. Phân tích tổng hợp hệ dãy 3 Chương 1 Các hàm logic cơ bản 4 2
  3. 11/13/2009 1.1. Đại số Boole ?  Giới thiệu - Môn đại số do George Boole sáng lập vào thập kỷ 70. - Là cơ sở lý thuyết, là công cụ cho phép nghiên cứu, mô tả, phân tích, thiết kế và xây dựng các hệ thống số, hệ thống logic, mạch số ngày nay. 5 1.1. Đại số Boole ?  Các định nghĩa • Biến lôgic: đại lượng biểu diễn bằng ký hiệu nào đó, lấy giá trị 0 hoặc 1 • Hàm lôgic: nhóm các biến lôgic liên hệ với nhau qua các phép toán lôgic, lấy giá trị 0 hoặc 1 • Phép toán lôgic cơ bản: có 3 phép toán logic cơ bản: • Phép Và - "AND" • Phép Hoặc - "OR" • Phép Đảo - "NOT” 6 3
  4. 11/13/2009 1.1. Đại số Boole  Biểu diễn biến và hàm lôgic • Cách 1: Biểu đồ Ven Mỗi biến lôgic chia không gian thành 2 không gian con: • 1 không gian con: biến lấy giá trị đúng (=1) • Không gian con còn lại: biến lấy giá trị sai (=0) 7 1.1. Đại số Boole • Cách 1: Biểu đồ Ven A A A+B A.B A.B A+B 8 4
  5. 11/13/2009 1.1. Đại số Boole  Biểu diễn biến và hàm lôgic • Cách 2: Biểu thức đại số Ký hiệu phép Và (AND): . Ký hiệu phép Hoặc (OR): + Ký hiệu phép Đảo (NOT): VD: F = A AND B OR C hay F = A.B + C 9 1.1. Đại số Boole  Biểu diễn biến và hàm lôgic • Cách 3: Bảng thật A B F(A,B) Hàm n biến sẽ có: n+1 cột (n biến và giá trị 0 0 0 hàm) 0 1 1 2n hàng: 2n tổ hợp biến Ví dụ Bảng thật hàm 1 0 1 Hoặc 2 biến 1 1 1 10 5
  6. 11/13/2009 1.1. Đại số Boole  Biểu diễn biến và hàm lôgic • Cách 4: Bìa Cac-nô - Đây là cách biểu diễn tương đương của bảng thật. -Trong đó, mỗi ô trên bìa tương B 0 1 ứng với 1 dòng của bảng thật. A -Tọa độ của ô xác định giá trị của 0 0 1 tổ hợp biến. -Giá trị của hàm được ghi vào ô tương ứng. 1 1 1 Ví dụ Bìa Cac-nô hàm Hoặc 2 biến 11 1.1. Đại số Boole  Biểu diễn biến và hàm lôgic • Cách 5: Biểu đồ thời gian A Là đồ thị biến thiên 1 theo thời gian của 0 hàm và biến lôgic B t 1 Ví dụ Biểu đồ 0 thời gian của F(A,B) t 1 hàm Hoặc 2 biến 0 t 12 6
  7. 11/13/2009 1.1. Đại số Boole  Các hàm lôgic cơ bản • Hàm Phủ định: Ví dụ Hàm 1 biến A F(A) F(A) A 0 1 1 0 13 1.1. Đại số Boole  Các hàm lôgic cơ bản • Hàm Và: A B F(A,B) Ví dụ Hàm 2 biến 0 0 0 0 1 0 F(A,B) AB 1 0 0 1 1 1 14 7
  8. 11/13/2009 1.1. Đại số Boole  Các hàm lôgic cơ bản A B C F Hàm Hoặc: • 0 0 0 0 0 0 1 1 0 1 0 1 Ví dụ Hàm 3 biến 0 1 1 1 F(A,B,C) A B C 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 15 1.1. Đại số Boole  Tính chất các hàm lôgic cơ bản . Tồn tại phần tử trung tính duy nhất cho phép toán Hoặc và phép toán Và: A + 0 = A A.1 = A . Giao hoán: A + B = B + A A.B = B.A . Kết hợp: A + (B+C) = (A+B) + C = A + B + C A . (B.C) = (A.B) . C = A . B . C . Phân phối: A(B+C) = AB + AC A + (BC) = (A+B)(A+C) . Không có số mũ, không có hệ số: A A A A A.A A A . Phép bù: A A A A 1 A.A 0 16 8
  9. 11/13/2009 1.1. Đại số Boole  Định lý Đờ Mooc-gan . Trường hợp 2 biến A B A.B A.B A B . Tổng quát F(Xii , ,.) F(X ,., )  Tính chất đối ngẫu 0 1 A B B A A.B B.A A 1 1 A.0 0 17 1.2. Biểu diễn các hàm lôgic  Dạng tuyển và dạng hội • Dạng tuyển (tổng các tích) F(x,y,z) xyz x y x z • Dạng hội (tích các tổng) F(x,y,z) (x y z)(x y)(x y z)  Dạng chính qui • Tuyển chính qui F(x,y,z) xyz x yz xyz • Hội chính qui F(x,y,z) (x y z)(x y z)(x y z) Không phải dạng chính qui tức là dạng đơn giản hóa 18 9
  10. 11/13/2009 1.2. Biểu diễn các hàm lôgic  Dạng tuyển chính qui  Định lý Shannon: Tất cả các hàm lôgic có thể triển khai theo một trong các biến dưới dạng tổng của 2 tích lôgic: F(A,B, ,Z) A.F(0,B, ,Z) A.F(1,B, ,Z) Ví dụ F(A,B) A.F(0,B) A.F(1,B) F(0,B) B.F(0,0) B.F(0,1) F(1,B) B.F(1,0) B.F(1,1) F(A,B) AB.F(0,0) AB.F(0,1) AB.F(1,0) AB.F(1,1) Nhận xét 2 biến Tổng 4 số hạng, 3 biến Tổng 8 số hạng n biến Tổng 2n số hạng 19 1.2. Biểu diễn các hàm lôgic  Dạng tuyển chính qui Nhận xét Giá trị hàm = 0 số hạng tương ứng bị loại Giá trị hàm = 1 số hạng tương ứng bằng tích các biến Cách áp dụng nhanh định lý Shannon: Từ bảng thật, ta chỉ quan tâm tới giá trị của hàm bằng 1. Với mỗi giá trị bằng 1, ta thành lập biểu thức tổ hợp tích các biến theo quy tắc giá trị biến bằng 1 thì giữ nguyên, giá trị biến bằng 0 thì đảo. Biểu thức cuối cùng là tổng của các tổ hợp biến nói trên. 20 10
  11. 11/13/2009 1.2. Biểu diễn các hàm lôgic  Dạng tuyển chính qui A B C F 0 0 0 0 0 0 1 1 Ví dụ 0 1 0 1 Cho hàm 3 biến F(A,B,C). Hãy viết biểu thức hàm 0 1 1 1 dưới dạng tuyển chính qui. 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 21 1.2. Biểu diễn các hàm lôgic  Dạng tuyển chính qui A B C F 0 0 0 0 0 0 1 1 F(A,B,C) A B C A B C 0 1 0 1 A B C A B C 0 1 1 1 A B C 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 22 11
  12. 11/13/2009 1.2. Biểu diễn các hàm lôgic  Dạng hội chính qui  Định lý Shannon: Tất cả các hàm lôgic có thể triển khai theo một trong các biến dưới dạng tích của 2 tổng lôgic: F(A,B, ,Z) [A F(1,B, ,Z)].[A F(0,B, ,Z)] Ví dụ F(A,B) [A F(1,B)][A F(0,B)] F(0,B) [B F(0,1)][B F(0,0)] F(1,B) [B F(1,1)][B F(1,0)] F(A,B) [A B F(1,1)][A B F(1,0)] Nhận xét [A B F(0,1)][A B F(0,0)] 2 biến Tích 4 số hạng, 3 biến Tích 8 số hạng n biến Tích 2n số hạng 23 1.2. Biểu diễn các hàm lôgic  Dạng hội chính qui Nhận xét Giá trị hàm = 1 số hạng tương ứng bị loại Giá trị hàm = 0 số hạng tương ứng bằng tổng các biến Cách áp dụng nhanh định lý Shannon: Từ bảng thật, ta chỉ quan tâm tới giá trị của hàm bằng 0. Với mỗi giá trị bằng 0, ta thành lập biểu thức tổ hợp tổng các biến theo quy tắc giá trị biến bằng 1 thì đảo, giá trị biến bằng 0 thì giữ nguyên. Biểu thức cuối cùng là tích của các tổ hợp biến nói trên. 24 12
  13. 11/13/2009 1.2. Biểu diễn các hàm lôgic  Dạng hội chính qui A B C F 0 0 0 0 0 0 1 1 Ví dụ 0 1 0 1 Cho hàm 3 biến F(A,B,C). Hãy viết biểu thức hàm 0 1 1 1 dưới dạng hội chính qui. 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 25 1.2. Biểu diễn các hàm lôgic A B C F  Dạng hội chính qui 0 0 0 0 0 0 1 1 0 1 0 1 F (A B C)(A B C)(A B C) 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 26 13
  14. 11/13/2009 1.2. Biểu diễn các hàm lôgic  Biểu diễn dưới dạng số . Dạng tuyển chính qui • Dạng tuyển chính quy quan tâm A B F1 tới những tổ hợp biến mà tại đó hàm nhận giá trị bằng 1 0 0 0 • Việc biểu diễn hàm tuyển chính 0 1 1 quy dưới dạng số liệt kê các tổ hợp biến mà tại đó hàm có giá trị 1 0 0 bằng 1. 1 1 1 F1(A,B)= R(1,3) 27 1.2. Biểu diễn các hàm lôgic  Biểu diễn dưới dạng số . Dạng hội chính qui - Dạng hội chính quy quan tâm tới A B F1 những tổ hợp biến mà tại đó hàm 0 0 0 nhận giá trị bằng 0. - Việc biểu diễn hàm logic hội chính 0 1 1 quy dưới dạng số liệt kê các tổ hợp 1 0 0 biến mà tại đó hàm có giá trị bằng 0. 1 1 1 F1(A,B)= I(0,2) 28 14
  15. 11/13/2009 1.2. Biểu diễn các hàm lôgic  Biểu diễn dưới dạng số .Dạng tuyển chính qui A B C F2 F2(A,B,C)= R(1,2,4,6) 0 0 0 0 .Dạng hội chính qui 0 0 1 1 0 1 0 1 . F2(A,B,C)= I(0,3,5,7) 0 1 1 0 1 0 0 1 Kết luận: 1 hàm logic bất kỳ đều có thể 1 0 1 0 chuyển về dạng tuyển chính quy (hoặc hội 1 1 0 1 chính quy) nhờ áp dụng định lý Shannon. 1 1 1 0 29 1.3. Tối thiểu hóa các hàm lôgic  Bài toán tối thiểu hóa: • Tiêu chí: - Số lượng biến tự là tối thiểu - Số lượng biến tự trong một biểu thức tổng các tích hoặc tích các tổng là tối thiểu - Số lượng các số hạng trong biểu thức tổng các tích hoặc tích các tổng là tối thiểu. • Mục đích: Giảm thiểu số lượng linh kiện • Phương pháp: - Đại số - Bìa Cac-nô - 30 15
  16. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic . Phương pháp đại số - Dùng các phép biến đổi đại số logic thông thường - Dựa trên các tính chất, định lý cơ bản (1) AB AB B (A B)(A B) B (1') (2) A AB A A(A B) A (2') (3) A AB A B A(A B) AB (3') 31 1.3. Tối thiểu hóa các hàm lôgic . Phương pháp đại số • Một số quy tắc tối thiểu hóa: Có thể tối thiểu hoá một hàm lôgic bằng cách nhóm các số hạng. ABC ABC ABCD AB ABCD A(B BCD) A(B CD) Có thể thêm số hạng đã có vào một biểu thức lôgic. ABC ABC ABC ABC ABC ABC ABC ABC ABC ABC BC AC AB 32 16
  17. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic . Phương pháp đại số • Một số quy tắc tối thiểu hóa:  Có thể loại đi số hạng thừa trong một biểu thức lôgic AB BC AC AB BC AC(B B) AB BC ABC ABC AB(1 C) BC(1 A) AB BC Trong 2 dạng chính qui, nên chọn cách biểu diễn nào có số lượng số hạng ít hơn. 33 1.3. Tối thiểu hóa các hàm lôgic Phương pháp bìa Các-nô (Karnaugh) - Bìa Karnaugh là phương pháp biểu diễn tương đương của bảng thật cho hàm Boole. - Bìa Karnaugh có thể sử dụng cho số lượng biến bất kỳ, nhưng thường nhiều nhất là 6 biến. 34 17
  18. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic  Phương pháp bìa Các-nô (Karnaugh) - Nếu số biến là n => 2n ô. - 2n ô được sắp xếp sao cho phù hợp với quá trình tối thiểu hóa - 2 ô liền kề nhau chỉ sai khác nhau 1 giá trị của 1 biến (tương ứng với tổ hợp biến khác nhau 1 giá trị) - Bìa Các-nô có tính không gian BC A 00 01 11 10 0 0 1 3 2 1 4 5 7 6 35 1.3. Tối thiểu hóa các hàm lôgic . Phương pháp bìa Cac-nô C BC A AB 0 1 00 01 11 10 00 0 1 0 0 1 3 2 01 2 3 1 4 5 7 6 11 6 7 10 4 5 36 18
  19. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic • Phương pháp bìa Cac-nô CD AB 00 01 11 10 00 0 1 3 2 01 4 5 7 6 11 12 13 15 14 10 8 9 11 10 37 1.3. Tối thiểu hóa các hàm lôgic Các quy tắc sau phát biểu cho dạng tuyển chính quy. Để dùng cho dạng hội chính quy phải chuyển tương đương 38 19
  20. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic • Qui tắc 1: nhóm các ô sao cho số lượng ô trong nhóm là một số luỹ thừa của 2. Các ô trong nhóm có giá trị hàm cùng bằng 1. CD CD AB 00 01 11 10 AB 00 01 11 10 00 00 1 1 01 1 1 01 1 1 11 1 1 11 1 1 10 1 1 10 1 1 39 1.3. Tối thiểu hóa các hàm lôgic • Qui tắc 2: Số lượng ô trong nhóm liên quan với số lượng biến có thể loại đi. Nhóm 2 ô loại 1 biến, nhóm 4 ô loại 2 biến, nhóm 2n ô loại n biến. Biến loại đi là biến có thay đổi giá trị BC A 00 01 11 10 F(A,B,C) A B C A B C 0 1 B C 1 1 40 20
  21. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic BC A 00 01 11 10 0 1 1 F(A,B,C) A C B C 1 1 BC A 00 01 11 10 0 1 1 1 F(A,B,C) B C A B 1 1 41 1.3. Tối thiểu hóa các hàm lôgic CD AB 00 01 11 10 00 1 1 01 1 1 F(A,B,C,D) B C B D 11 1 1 10 1 1 42 21
  22. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic CD • Qui tắc 3: Trường AB 00 01 11 10 hợp có những giá trị hàm là không xác định 00 1 1 (không chắc chắn luôn bằng 0 hoặc không chắc chắn luôn bằng 1), có 01 1 1 thể coi giá trị hàm là bằng 1 để xem có thể 11 nhóm được với các ô mà giá trị hàm xác định bằng 1 hay không. 10 F(A,B,C,D) B C B C 43 1.3. Tối thiểu hóa các hàm lôgic Phương pháp bìa Các-nô (Karnaugh) - Bìa 5 biến E 0 1 CD CD AB 00 01 11 10 AB 00 01 11 10 00 1 1 00 1 1 01 1 1 01 11 1 1 11 1 1 10 10 1 1 Bìa 5 biến được xem như gồm 2 bìa 4 biến ghép với nhau. 44 22
  23. 11/13/2009 1.3. Tối thiểu hóa các hàm lôgic  Phương pháp bìa Các-nô (Karnaugh) - Bìa 6 biến F E 0 1 CD CD AB 00 01 11 10 AB 00 01 11 10 00 1 1 00 1 1 0 01 1 1 01 11 1 1 11 1 1 10 10 1 1 CD CD AB 00 01 11 10 AB 00 01 11 10 00 1 1 00 1 1 1 01 1 1 01 11 1 1 11 1 1 10 10 1 1 45 Bài tập chương 1 (1/3) 1. Chứng minh các biểu thức sau: a) AB A B A B A B b) AB A C (A C)(A B) c) AC B C A C B C 2. Xây dựng bảng thật và viết biểu thức lôgic của hàm F xác định như sau: a) F(A,B,C) = 1 ứng với tổ hợp biến có số lượng biến bằng 1 là một số chẵn hoặc không có biến nào bằng 1. Các trường hợp khác thì hàm bằng 0 b) F(A,B,C,D) = 1 ứng với tổ hợp biến có ít nhất 2 biến bằng 1. Các trường hợp khác thì hàm bằng 0. 46 23
  24. 11/13/2009 Bài tập chương 1 (2/3) 3. Trong một cuộc thi có 3 giám khảo. Thí sinh chỉ đạt kết quả nếu có đa số giám khảo trở lên đánh giá đạt. Hãy biểu diễn mối quan hệ này bằng các phương pháp sau đây: a) Bảng thật b) Bìa Cac-nô c) Biểu đồ thời gian d) Biểu thức dạng tuyển chính quy e) Biểu thức dạng hội chính qui f) Các biểu thức ở câu d), e) dưới dạng số. 47 Bài tập chương 1 (3/3) 4. Tối thiểu hóa các hàm sau bằng phương pháp đại số: a) F(A,B,C,D) (A BC) A(B C)(AD C) b) F(A,B,C) (A B C)(A B C)(A B C)(A B C) 5. Tối thiểu hóa các hàm sau bằng bìa Các-nô: a) F(A,B,C,D) = R(0,2,5,6,9,11,13,14) b) F(A,B,C,D) = R(1,3,5,8,9,13,14,15) c) F(A,B,C,D) = R(2,4,5,6,7,9,12,13) d) F(A,B,C,D) = I(1,4,6,7,9,10,12,13) e) F(A,B,C,D,E)=R(0,1,9,11,13,15,16,17, 20,21,25,26,27,30,31) 48 24
  25. 11/13/2009 Giải bài tập chương 1 1. a) AB A B (AB)(A B) =(A+B)(A+B) =AA AB AB BB AB AB 49 Giải bài tập chương 1 1. b) AB AC (A C)(A B) AB AC (AB A)(AB C) (A B)(AB C) AAB AC AB BC AC BC AA AB C(A B) A(A B) (A C)(A B) 50 25
  26. 11/13/2009 Giải bài tập chương 1 1. c) AC BC AC B C AC BC (A C)(B C) A B B C AC B C AC A B C A B C B C AC 51 Giải bài tập chương 1 A B t C t t F t 52 26
  27. 11/13/2009 Giải bài tập chương 1 4. a) F(A,B,C,D) (A BC) A(B C)(AD C) (A BC) A(B C)(AD C) (A BC) (A BC)(AD C) (A BC) (AD C) A(1 D) C(1 B) AC 53 Giải bài tập chương 1 4. b) F(A,B,C) (A B C)(A B C)(A B C)(A B C) F (A B CC)(A B CC) (A B)(A B) AA AB AB B B(A A 1) B 54 27
  28. 11/13/2009 Giải bài tập chương 1 5. a) F(A,B,C,D) = R(0,2,5,6,9,11,13,14) CD AB 00 01 11 10 00 1 1 01 1 1 11 1 1 10 1 1 55 Giải bài tập chương 1 5. c) F(A,B,C,D) = R(2,4,5,6,7,9,12,13) CD AB 00 01 11 10 00 1 01 1 1 1 1 11 1 1 10 1 56 28
  29. 11/13/2009 Giải bài tập chương 1 CD 5. d) AB 00 01 11 10 00 0 01 0 0 0 11 0 0 10 0 0 F(A,B,C,D) (B C D)(A B C)(A B C)(B C D)(A B C D) 57 Giải bài tập chương 1 CD AB 00 01 11 10 00 1 01 1 1 1 11 1 1 10 1 1 58 29
  30. 11/13/2009 Giải bài tập chương 1 5. e) C=0 C=1 DE AB 00 01 11 10 10 11 01 00 00 0 1 3 2 6 7 5 4 01 8 9 11 10 14 15 13 12 11 24 25 27 26 30 31 29 28 10 16 17 19 18 22 23 21 20 59 Giải bài tập chương 1 F(A,B,C,D,E)=R(0,1,9,11,13,15,16,17,20,21,25,26,27,30,31) C=0 C=1 DE AB 00 01 11 10 10 11 01 00 1 1 00 0 1 3 2 6 7 5 4 1 1 1 1 01 8 9 11 10 14 15 13 12 1 1 1 1 1 11 24 25 27 26 30 31 29 28 1 1 1 1 10 16 17 19 18 22 23 21 20 60 30