Bài giảng Kỹ thuật số - Chương 2: Đại số logic (Boolean Algebra)

Chia sẻ: Nguyệt Thượng Vô Phong | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

10
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật số - Chương 2: Đại số logic (Boolean Algebra). Chương này cung cấp cho sinh viên những nội dung kiến thức gồm: đại số logic (đại số Boole); hàm logic; các phương pháp biểu diễn hàm logic; tối thiểu hóa hàm logic; thực hiện hàm logic;... Mời các bạn cùng tham khảo!

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 Kỹ thuật số - Chương 2: Đại số logic (Boolean Algebra)

Chương 2 Đại số logic (Boolean Algebra)
Nội dung chương 2 ▪ Đại số logic (Đại số Boole) ▪ Hàm logic ▪ Các phương pháp biểu diễn hàm logic ▪ Tối thiểu hóa hàm logic ▪ Thực hiện hàm logic 2
Đại số logic – Đại số Boole (Boolean Algebra) ▪ Trong các mạch số – các tín hiệu thường được cho ở 2 mức điện áp (0V và 5V) – linh kiện điện tử làm việc ở một trong hai trạng thái: Tắt hoặc Dẫn; – mô tả bằng hệ nhị phân (binary) bằng các bit 0 hoặc 1 ▪ Cần công cụ toán học thích hợp để mô tả? ▪ Đại số logic (Đại số Boole) – George Boole giới thiệu 1854 – công cụ toán học quan trọng để phân tích và thiết kế các mạch số 3
George Boole (1815 – 1864) George Boole (2 November 1815 – 8 December 1864) was an English mathematician, philosopher and logician. His work was in the fields of differential equations and algebraic logic, and he is now best known as the author of The Laws of Thought. As the inventor of the prototype of what is now called Boolean Logic, which became the basis of the modern digital computers. Source: http://en.wikipedia.org/wiki/George_Boole 4
Các tiên đề của đại số logic ▪ Tập hợp B hữu hạn; 3 phép toán + (cộng logic), x (nhân logic), - (bù logic/nghịch đảo logic); 2 phần tử 0 và 1 ➔ cấu trúc đại số Boole ▪  x,y  B thì: x+y  B, x*y  B 1. Tiên đề giao hoán x,y  B: x+y =y+x 2. Tiên đề phối hợp x,y,z  B: (x+y)+z = x+(y+z) = x+y+z (x.y).z = x.(y.z) = x.y.z 5
Các tiên đề của đại số logic (tt) 3. Tiên đề phân phối x,y, z  B: x.(y + z ) = x.y + x.z x + (y.z) = (x + y).(x + z) 4. Tiên đề về phần tử trung hòa – phần tử đơn vị (1) và phần tử không (0) x  B: x+1= 1 x. 1= x x+0= x x. 0= 0 5. Tiên đề về phần tử bù: x  B, luôn tồn tại phần tử bù tương ứng thỏa mãn: x+ =1 và x. = 0 6
Đối ngẫu trong đại số logic ▪ Đối ngẫu (Duality): – Hai mệnh đề (hai biểu thức, hai định lý) được gọi là đối ngẫu với nhau nếu trong mệnh đề này người ta thay phép toán cộng thành phép toán nhân và ngược lại, thay 0 bằng 1 và ngược lại, thì sẽ suy ra được mệnh đề kia. – Khi hai mệnh đề đối ngẫu với nhau, nếu 1 trong 2 mệnh đề được chứng minh là đúng thì mệnh đề còn lại là đúng. ▪ Ví dụ 1.8: x.(y+z) = (x.y) + (x.z) x + (y.z) = (x+y).(x+z) ▪ Ví dụ 1.9: x+ =1 x. = 0 7
Các định lý cơ bản của đại số logic 8
Các đlý cơ bản của đại số logic (tt) 9
Các đlý cơ bản của đại số logic (tt) 10
Hàm logic và biểu diễn hàm logic ▪ Hàm logic (Hàm Boole) – Định nghĩa – Tính chất – Giá trị của hàm logic ▪ Các phương pháp biểu diễn hàm logic – Bảng giá trị (Bảng chân trị, Bảng sự thật / Truth Table) – Biểu thức đại số • Dạng tổng các tích số (dạng chính tắc 1) • Dạng tích các tổng số (dạng chính tắc 2) – Bản đồ Karnaugh (K-map) ▪ Tối thiểu hóa hàm logic 11
Hàm logic (Hàm Boole) ▪ Hàm Boole là một ánh xạ từ đại số Boole vào chính nó: x, y  B, hàm logic (Boole) f được hình thành trên cơ sở liên kết các biến logic bằng các phép toán + (cộng logic), x / . (nhân logic), nghịch đảo logic (-). ▪ Hàm logic 1 biến ▪ Hàm logic nhiều biến (n biến: x1, x2, ..., xn) ▪ Một hàm logic được hình thành trên cơ sở liên kết các hàm logic khác bằng các phép toán: +, x, - 12
Thứ tự ưu tiên thực hiện phép toán ▪ trong dấu ( ) ▪ NOT (bù) ▪ AND (nhân) ▪ OR (cộng) Ví dụ: ▪ f1 = x + y.z ▪ f2 = x1x2 + x3x4 13
Giá trị hàm logic ▪ Trong f(x1, x2, ..., xn) thay các biến xi bằng các giá trị cụ thể i (0 hoặc 1) thì f(1, 2, ..., n) được gọi là giá trị của hàm logic theo n biến, hay theo tổ hợp biến (1, 2, ..., n) → hàm n biến có 2n tổ hợp các biến ▪ Ví dụ 1.10: Xét hàm f(x1, x2 ) = x1 + x2, xét tập B = {0,1} ▪ Ví dụ 1.11: xem bài giảng 14
Biểu diễn hàm logic ▪ Biểu diễn hàm logic bằng bảng giá trị: 2 phần – Phần dành cho biến: tổ hợp giá trị có thể có của biến vào – Phần dành cho hàm: giá trị của hàm ra tương ứng với các tổ hợp biến vào ▪ Hàm n biến có 2n tổ hợp giá trị khác nhau của các biến 15
Bài tập ▪ Thiết kế mạch điều khiển đèn phòng học – Phòng học có 3 cửa, mỗi cửa có 1 công tắc để điều khiển hệ thống đèn gồm nhiều đèn được mắc song song – Khi công tắc bất kỳ thay đổi trạng thái (từ bật sang tắt hay ngược lại) sẽ có tác dụng điều khiển thay đổi trạng thái của đèn (từ tắt chuyển sang sáng hay ngược lại) ▪ Yêu cầu: a) Vẽ sơ đồ khối của mạch? b) Xác định các biến (logic) vào ra của mạch? c) Lập bảng giá trị (Truth Table) mô tả hoạt động của mạch? d) Viết phương trình logic của mạch? e) Vẽ sơ đồ mạch? 16
Bài tập (tt) x1 x2 x3 Đ 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 17
Biểu diễn hàm bằng biểu thức đại số ▪ Dạng tổng các tích số (của các biến logic): CT1 ▪ Dạng tích các tổng số (của các biến logic): CT2 ▪ Hai dạng này là đối ngẫu nhau ▪ Viết biểu thức tổng quát hàm n biến ở dạng CT1 ▪ Biểu thức tổng quát của hàm n biến ở dạng CT2 được suy ra từ dạng CT1 dựa theo tính đối ngẫu ▪ Chứng minh chi tiết: xem bài giảng 18
Dạng chính tắc 1 (CT1) – Tổng các tích số ▪ Cho hàm logic n biến y = f(x1, x2, ..., xn) ▪ trong đó – e là số thập phân tương ứng mã nhị phân (1, 2, ..., n) – và: 19
CT1 – Tổng các tích số (tt) ▪ Viết biểu thức của hàm 3 biến theo dạng CT1? 20