Bài giảng Kỹ thuật điện tử số - Bài: Đại số Boole. Đại số logic - Lê Minh Thùy

Nội dung text: Bài giảng Kỹ thuật điện tử số - Bài: Đại số Boole. Đại số logic - Lê Minh Thùy

1. 3. Đại số Boole Đại số logic Lê Minh Thùy – 3I 1
2. Nội dung 3.1 Giới thiệu 3.2 Các tiên đề trong đại số logic 3.3 Các phần tử logic cơ bản 3.4 Các định lý 3.4.1 Định lý cho một biến 3.4.2 Cho 2 và 3 biến 3.4.3 Cho n biến (các ví dụ chứng minh một số định lý) 3.5 Nguyên lý của tính đối ngẫu (duality) – (các ví dụ) 3.6 Cách rút gọn và biểu diễn hàm logic 3.6.1 Thông qua bảng chân lý 3.6.2 Thông qua minterm và maxterm 3.6.3 Tối thiểu hóa hàm logic 3.7 Tổng hợp mạch logic tổ hợp: Các mạch chuyển đổi Ví dụ: Tổng hợp mạch chuyển từ BCD sang 7-thanh 2
3. Tài liệu tham khảo • Digital Design: Principles & Practices – John F Wakerly – Printice Hall 3
4. 3.1 Giới thiệu • Mạch logic/số: – Mạch logic tổ hợp (Combinational logic circuit): là mạch mà giá trị output chỉ phụ thuộc duy nhất vào sự tổ hợp của các inputs. – Mạch logic dãy ( Sequential circuit): output tại một thời điểm phụ thuộc không chỉ giá trị input tại thời điểm đó mà còn phụ thuộc vào dãy các input trong quá khứ. • Mạch logic tổ hợp: biểu diễn và tổng hợp mạch 4
5. 3.1 Giới thiệu • 1854 nhà toán học Anh, Gorge Boole (1815- 1864) phát minh ra hệ thống đại số chỉ có hai giá trị • Năm 1938, tại Bell Lab, Claude E. Shannon đã chỉ ra cách áp dụng đại số Boole vào phân tích và mô tả các mạch sử dụng rơle (còn gọi là switching algebra), và cũng được áp dụng cho các phân tích mạch số hiện nay. 5
6. 3.2 Các tiên đề • Tiên đề 1: (A1) X = 0 if X ≠ 1 (A1‟) X = 1 if X ≠ 0 • Tiên đề 2: (định nghĩa toán tử đảo) (A2): If X = 0 then X’ = 1 (A2‟): If X = 1 then X’ = 0 Toán tử “ ‘ “ là toán tử đảo hay bù (một số ký hiệu khác của toán tử đảo: ~, XX ) Tuy nhiên việc sử dụng ‘ thường được sử dụng trong các ngôn ngữ lập trình HDLs) 6
7. 3.2 Các tiên đề • Tiên đề 3 , 4 và 5 :Định nghĩa các toán tủ VÀ/AND và HOẶC/OR logic: Toán tử AND sử dụng ký hiệu · Toán tử OR sử dụng ký hiệu + Tất cả các hệ thống logic đều có thể mô tả và phân tích dựa trên 5 tiên đề trên 7
8. 3.3 Các phần tử logic cơ bản 8
9. Các phần tử logic cơ bản • Phần tử NOT hay còn gọi là Inverter: cho giá trị output có mức logic ngược với mức logic của giá trị input Ký hiệu Bảng chân lý Biểu thức đại số F=A‟ hoặc F= A 9
10. Các phần tử logic cơ bản • Phần tử AND Ký hiệu Bảng chân lý Biểu thức đại số F=A.B hoặc F=AB 10
11. Các phần tử logic cơ bản • Phần tử OR Ký hiệu Bảng chân lý Biểu thức đại số F=A+B 11
12. Các phần tử logic cơ bản mở rộng • Phần tử NAND Ký hiệu Bảng chân lý hoặc hoặc Biểu thức đại số hoặc 12
13. Các phần tử logic cơ bản mở rộng • Phần tử NOR (SV chép bài trên lớp) 13
14. Các phần tử logic cơ bản mở rộng • Phần tử XOR (SV chép bài trên lớp) • 14
15. Các phần tử logic cơ bản mở rộng • Phần tử XNOR (đảo của XOR) (SV chép bài trên lớp) • 15
16. 3.4 Các định lý 3.4.1 Định lý cho một biến Việc chứng minh các định lý này có thể sử dụng phương pháp quy nạp hoàn toàn (vì số giá trị của các biến chỉ có 0 và1 nên rất dễ áp dụng phương pháp quy nạp) 16
17. 3.4.2 Cho 2 và ba biến Chú ý: để thuận tiện thường viết X · Y thay cho ( X · Y ) 17
18. 3.4.3 Cho n biến Để chứng minh sử dụng phương pháp quy nạp hữu hạn: • chứng minh đúng với n = 2 • giả thiết đúng với n = i, chúng minh đúng với n = i+1 18
19. Ví dụ: chứng minh bằng bảng chân lý 19
20. 3.5 Nguyên lý đối ngẫu • Các định lý hay đồng nhất thức trong đại số logic sẽ luôn đúng nếu thay 0 và 1 tráo đổi cho nhau và đồng thời · và + cũng được tráo đổi cho nhau. • Hàm đối ngẫu: – Cho hàm logic F(X1,X2, ,Xn, + , · , ‟) – Hàm đối ngẫu của F được định nghĩa là hàm có cùng dạng biểu thức với các toán tử · và + được đổi chỗ cho nhau D F (X1,X2, ,Xn, + , · , ‟) = F(X1,X2, ,Xn, · , + , ‟) + và · đổi chỗ 20
21. Nguyên lý đối ngẫu và định lý DeMorgan D ‟ ‟ ‟ [F(X1,X2, ,Xn)]‟ = F (X1 , X2 , ,Xn ) D ‟ ‟ ‟ F(X1,X2, ,Xn) = [F (X1 , X2 , ,Xn )]‟ (định lý DeMorgan) 21
22. Ví dụ: Chứng minh định lý De Morgan 22
23. Ví dụ 23
24. Ví dụ: Chứng minh F1=F2 (1/3) Minh chứng rằng F1=F2 sử dụng bảng chân lý Chúng ta cũng có thể sử dụng định lý T5+ T8 để chứng minh 24
25. Ví dụ: Chứng minh F1=F2 (2/3) 25
26. Ví dụ: Chứng minh F1=F2 (3/3) 26
27. 3.5.1 Biểu diễn hàm logic thông qua bảng chân lý Bảng sự thực (không bao gồm cột ROW), tuy nhiên thường được sử dụng để chỉ giá trị tổ hợp của các biến 31
28. Ví dụ 1: minimization 33
29. Ví dụ 2: Minimization 34
30. Ví dụ 3 35
31. Một số khái niệm • Hệ số chữ (literal): là một biến đơn , hoặc phần bù của nó. Ví dụ: X, Y, X‟, • Số hạng tích (product term): là một literal hoặc tích logic của nhiều literal Ví dụ: Z‟, X ¢ Y, X‟ ¢ Y ¢ Z‟ • Biểu thức tổng của các tích: là một tổng logic của các số hạng tích • Số hạng tổng (sum term): là một literal hoặc tổng logic của nhiều literal Ví dụ: X‟, X+Y+Z‟ • Biểu thức tích của các tổng: là tích logic của các số hạng tổng 36
32. • Một số hạng chuẩn (normal term): là một số hạng tích hoặc tổng mà trong đó không có biến nào xuất hiện hơn một lần • Ví dụ các số hạng không chuẩn: • X + Y + X‟, Y ¢ X ¢ X‟ ¢ Z • Ví dụ các số hạng chuẩn: • X + Y, X ¢ Y ¢ Z • minterm n biến: là một số hạng tích chuẩn của n literal • maxterm n biến: là số hạng tổng chuẩn của n literal 37
33. • Minterm: có thể được định nghĩa là số hạng tích ứng với một hàng của bảng chân lý sao cho tích đó bằng 1 • Maxterm: có thể được định nghĩa là số hạng tổng ứng với một hàng của bảng chân lý sao cho tổng đó bằng 0 39
34. 3.5.2 Biểu diễn hàm qua minterm và maxterm • Hàm logic có thể biểu diễn dưới dạng: – canonical sum: tổng của các minterm (tổng của các tích) ứng với các hàng của bảng chân lý mà tại đó giá trị hàm bằng 1 – canonical product: tích của các maxterm(tích của các tổng) ứng với các hàng của bảng chân lý mà tại đó giá trị hàm bằng 0 41
35. Tổng của các minterm Tích của các maxterm 42
36. • Để đơn giản trong ký hiệu, người ta thường sử dụng dạng viết rút gọn sau: X, Y , Z là các biến, đi kèm với chỉ số các hàng tương ứng của các 43 minterm hoặc maxterm
37. Tối thiểu hóa hàm logic • Hàm logic có thể biểu diễn thông qua: – canonical sum – canonical product Tuy nhiên đó là các dạng chưa được tối thiểu. • Để giảm số input hay số gate sử dụng trong mạch cần phải tối thiểu hóa mạch. 44
38. Bìa Karnaugh • Là cách biểu diễn đồ họa của bảng chân lý 45
39. • K-map : n biến sẽ có 2n ô • Mỗi một ô trong K-map ứng với một hàng trong bảng chân lý. • Quy ước các ô kề nhau thì tổ hợp các biến chỉ được khác nhau một giá trị • K-map chỉ thuận tiện sử dụng cho hàm logic có 6 biến trở xuống • Từ K-map có thể viết được các canonical sum hoặc canonical product tương tự như bảng chân lý 46
40. Tối thiểu hóa dạng tổng các tích „ „ 47
41. • Quy tắc nhóm các ô của K-map: – Nhóm 2k các ô có giá trị 1 kề nhau sao cho k là max ( 1 ≤ k ≤ n, với n là số biến) – Có chính xác (n-k) biến có giá trị không đổi trong số các ô được nhóm • Dạng tích: – nếu biến có giá trị là 1 trong 2k ô được nhóm thì product term sẽ chứa biến đó – nếu biến có giá trị 0 trong 2k ô được nhóm thì product term sẽ chứa bù của biến đó – nếu biến có cả giá trị 1 và 0 trong 2k ô được nhóm thì nó sẽ không xuất hiện trong product term 48
42. các nhóm không đúng 49
43. Ví dụ • Bảng Karnaugh đối với cổng OR 2 biến X Y X Y F=X+Y 50
44. ví dụ 51
45. • Dạng tối giản sử dụng K-map không phải là duy nhất 52
46. Tối thiểu hóa dạng tích các tổng • Nhóm 2k các ô có giá trị 0 kề nhau sao cho k là max: – nếu biến có giá trị là 1 trong 2k ô được nhóm thì sum- term sẽ chứa bù của biến đó – nếu biến có giá trị 0 trong 2k ô được nhóm thì sum- term sẽ chứa biến đó – nếu biến có cả giá trị 1 và 0 trong 2k ô được nhóm thì nó sẽ không xuất hiện trong sum term 53
47. Các tổ hợp đầu vào “Don‟t-Care” • Trong trường hợp ứng với một số tổ hợp giá trị các inputs giá trị hàm logic có thể tùy ý (bằng 0 hoặc bằng 1) các tổ hợp “don‟t-care” • Sử dụng các tổ hợp “don‟t-care” trong tối giản hàm: – Cho phép tổ hợp don‟t-care tham gia vào các ô sao cho số ô 2k là lớn nhất – Không nhóm các ô chỉ toàn don‟t-care 54
48. Chuyển đổi sang mạch logic tích cực thấp • Ba mạch logic số biểu diễn biểu thức F=AB+CD Các biểu thức biểu diễn các mạch số này? 57
49. 3.7 Tổng hợp mạch logic tổ hợp: Các mạch chuyển đổi • Mạch chuyển đổi (Code converter) từ BCD sang 7-thanh (7-segment) 58
50. BCD và I/O 59
51. BCD 7-Segment: Bảng chân lý A B C D 60
52. Biểu diễn K-map cho „a‟ 61
53. Các phương pháp tối giản sử dụng chương trình • Khi số biến lớn, sử dụng thuật toán: – Queen-McCluskey (tham khảo) – Espresso II, Espresso-MV (tham khảo) 62