Chöông 2: ÑAÏI SOÁ LOGIC - Đại số logic còn được gọi là đại số Boole, do nhà toàn học người Anh George Boole đưa ra năm 1847 - Là công cụ toán học được dùng cho hệ đếm nhị phân, hệ thống đếm chỉ dùng hai chữ số là 0 và 1 để biểu diễn các con số - Đặc điểm của đại số logic là các hàm và các biến chỉ nhận một trong hai giá trị 0 hoặc 1. - Hai giá trị này biểu thị hai trạng thái logic khác nhau đúng hoặc sai, - Đối với mạch điện tử hai giá trị 1 hoặc 0 dùng để biểu thị hai mức điện áp: điện áp cao (VH) hoặc thấp (VL), công tắc đóng hoặc ngắt, có hoặc không có dòng điện chạy trong mạch. Chöông 2: ÑAÏI SOÁ LOGIC 2.1 Ba phép tính cơ bản trong đại số logic Laø caáu truùc ñaïi soá ñöôïc ñònh nghóa treân 1 taäp phaàn töû nhò phaân B = {0, 1} vaø caùc pheùp toaùn nhò phaân: AND (. y (x AND y) 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 x x’ (NOT x, x ) 0 1 1 0 Chöông 2: ÑAÏI SOÁ LOGIC 2.2 Các định luật cơ bản của đại số Boole - Các mệnh đề cơ sở - Định luật hấp thụ - Định luật phủ định của phủ định - Định luật kết hợp Chöông 2: ÑAÏI SOÁ LOGIC 2.2 Các định luật cơ bản của đại số Boole - Định luật giao hoán - Định luật phân phối - Định lý De Morgan Mở rộng x1 + x2 +.
+ xn Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic a) Khái niệm minterm (số hạng tối thiểu) và maxterm (số hạng tối đa) - Một hàm logic có n biến, mỗi biện nhận một trong hai giá trị 0 hoặc 1, như vậy sẽ có 2n tổ hợp biến - Mỗi tổ hợp biến có thể tạo thành một số hạng là tích của tất cả các biến có trong cùng 1 tổ hợp biến (gọi là minterm): gọi là số hạng tối thiểu vì nó là tích các biến có trong một tổ hợp biến, tích này chỉ bằng 1 khi tất cả các biến đều bằng 1 - Mỗi tổ hợp biến có thể tạo thành một số hạng là tổng tất cả các biến có trong một tổ hợp biến (gọi là maxterm): chỉ cần 1 trong các biến bằng 1 thì maxterm bằng 1, maxterm bằng 0 chỉ trong một trường hợp duy nhất khi tất cả các biến đều bằng 0. - Một hàm có n biến ta có 2n minterm và 2n maxterm Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic a) Khái niệm minterm (số hạng tối thiểu) và maxterm (số hạng tối đa) - Ví dụ một hàm F(A, B, C) có 3 biến là A, B, C ta có 8 tổ hợp biến được xếp theo mã nhị phân là: 000, 001, 010, 011, 100, 101, 110, 111. Tương ứng có 8 minterm (m0, m1……m7) và 8 maxterm (M0, M1….,M7) Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic b) Các tính chất của minterm và maxterm - Hai maxterm và minterm của số hạng có cùng chỉ số là phủ định của nhau - Tổng logic của tất cả minterm =1 - Tích logic của tất cả các maxterm =0 - Tích hai minterm khác nhau bất kỳ =0 - Tổng hai maxterm khác nhau bất kỳ =1 Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic - Có 4 phương pháp được dùng để biểu diễn hàm logic là: bảng chân lý, bảng Karnaugh, phương trình logic, ký hiệu logic - Cần nắm vững từng phương pháp biểu diễn hàm, biết vận dụng những ưu việt của từng phương pháp, chuyển đổi từ phương pháp này sang phương pháp kia. Bảng chân lý - Bảng chân lý miêu tả mối quan hệ giữa các giá trị của hàm số tương ứng với mọi giá trị có thể của biến - Bảng chân lý biểu thị hàm logic dưới dạng bảng số một cách rõ ràng tường minh - Dùng các chữ cái A, B, C…hoặc X1, X2, X3….để ký hiệu các biến, và dùng F, Y, Z, W để ký hiệu hàm logic Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Bảng chân lý - Mỗi biến đầu vào có thể nhận hai giá trị 0 và 1, nếu hàm có n biến thì sẽ có 2n tổ hợp các giá trị khác nhau của chúng.
- Để nhận được bảng chân lý chúng ta cần phải liệt kê tất cả các giá trị của hàm ở đầu ra tương ứng với các tổ hợp biến lối vào. - Để khỏi bỏ sót hoặc trùng lặp ta nên sắp xếp các tổ hợp biến lối vào tuần tự theo số đếm nhị phân - Ưu điểm của bảng trạng thái: rõ ràng, trực quan - Nhược điểm chủ yếu của bảng chân lý là phức tạp nếu số biến quá nhiều, không thể dùng các công thức và định lý để tính toán. Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Bảng chân lý - Ví dụ ta có hàm logic: - Ta có bảng chận lý được trình bày như sau. Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic - Biểu diễn hàm logic bằng các phương trình logic cho thấy mối quan hệ giữa hàm và biến thông qua các phép toán cộng, nhân và phủ định, là phương pháp biểu diễn thích hợp trong mọi trường hợp, kể cả các quan hệ logic phức tạp, hàm nhiều biến - Dùng phương trình logic sẽ đơn giản, gọn ghẽ hơn là dùng bảng chân lý và rất tiện để thực hiện các phép toán logic và tối thiểu hóa các hàm bằng phương pháp đại số - Phương trình logic được xác lập theo các cách sau: + Dạng tuyển SOP: lấy tổng của các tích tức tổng của các minterm (đủ biến), ký hiệu bằng chữ mi F fi mi Chỉ lấy tổng các minterm nào có giá trị tương ứng của hàm fi=1 Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic + Dạng hội POS: lấy tích của các tổng tức tích của các maxterm (đủ biến), ký hiệu bằng chữ Mi F ( fi M i ) Chỉ lấy tích các maxterm nào có giá trị tương ứng của hàm có fi=0 Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic Ví dụ: Một hàm 3 biến có bảng chân lý được cho trong bảng sau: Ta có thể xác định hàm logic theo 2 cách nói trên Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic Ví dụ: Một hàm 3 biến có bảng chân lý được cho trong bảng sau: Cách 1: lấy tổng chuẩn các minterm ứng với fi=1 ta có: Cách 2: lấy tích chuẩn các maxterm ứng với fi=0 ta có Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic Ví dụ: Biểu diễn hàm sau theo dạng minterm F(A, B, C)=A+BC - Đây là dạng minterm không đầy đủ, muốn đưa về dạng chuẩn tắc (đủ biến) ta sử dụng một số định lý để biến đổi Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic Ví dụ: Biểu diễn hàm sau theo dạng maxterm F(A, B, C)=A+BC=(A+B)(A+C) - Đây là dạng maxterm không đầy đủ, muốn đưa về dạng chuẩn tắc (đủ biến) ta sử dụng một số định lý để biến đổi Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic Ví dụ: x y z F F(x, y, z) = x y z + x y z + x y z + x y z + x y z 0 0 0 0 = m1 + m2 + m5 + m6 + m7 0 0 1 1 0 1 0 1 = m(1, 2, 5, 6, 7) 0 1 1 0 = (1, 2, 5, 6, 7) 1 0 0 0 1 0 1 1 F(x, y, z) = (x + y + z) (x + y + z) (x + y + z) 1 1 0 1 = M0.
M4 1 1 1 1 = M(0, 3, 4) = (0, 3, 4) Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Phương trình logic Ví dụ: Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Bảng Karnaugh - Bảng Karnaugh dạng maxterm: với tổ hợp biến nào mà hàm có giá trị 0 thì ô vuông đó được ghi giá trị 0, các tổ hợp biến có giá trị 1 thì bỏ trống. Ví dụ của các hàm 2, 3 biến Chöông 2: ÑAÏI SOÁ LOGIC 2.3 Phương pháp biểu diễn hàm logic c) Phương pháp biểu diễn hàm logic Bảng Karnaugh Ví dụ của các hàm 4 biến * Bìa 3 bieán: F AB C 00 01 11 10 0 0 2 6 4 1 1 3 7 5 F (A, B, C) = (2, 4, 7) + d(0, 1) = (3, 5, 6). D(0, 1) F AB F AB C 00 01 11 10 C 00 01 11 10 0 X 1 1 0 X 0 1 X 1 1 X 0 0 22 F AB * Bìa 4 bieán: CD 00 01 11 10 00 0 4 12 8 01 1 5 13 9 11 3 7 15 11 10 2 6 14 10 * Bìa 5 bieán: F A 0 1 BC 00 01 11 10 10 11 01 00 DE 00 0 4 12 8 24 28 20 16 01 1 5 13 9 25 29 21 17 11 3 7 15 11 27 31 23 19 10 2 6 14 10 26 30 22 18 23 Chöông 2: ÑAÏI SOÁ LOGIC 2.