Bài thuyết trình đại số bool

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH ĐẠI HỌC CÔNG NGHỆ THÔNG TIN * Nội dung 1. Giới thiệu 2. Đại số Boole 3. Biểu diễn các hàm logic dưới dạng chính quy 4. Tối thiểu hóa các hàm logic 5. Các phần tử logic cơ bản 6. Bài tập Đại số bool * * * GIỚI THIỆU Trong đại số trừu tượng, đại số Boole là một cấu trúc đại số có các tính chất cơ bản của cả các phép toán trên tập hợp và các phép toán logic. Cụ thể, các phép toán trên tập hợp được quan tâm là phép giao, phép hợp, phép bù; và các phép toán logic là Và, Hoặc, Không. * Nội dung 1. Giới thiệu 2. Đại số Boole 3. Biểu diễn các hàm logic dưới dạng chính quy 4. Tối thiểu hóa các hàm logic 5. Các phần tử logic cơ bản 6. Bài tập Đại số bool * 2. Đại số Boole Các định nghĩa Biến : đại lượng nào đó, lấy giá trị 0 hoặc 1 Hàm : 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: VÀ (AND), HOẶC (OR), PHỦ ĐỊNH (NOT) Đại số bool * 2. Đại số Boole Biểu đồ Ven: Đại số bool * A hoặc B A và B 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) A B  Biểu diễn biến và hàm lôgic 2. Đại số Boole  Biểu diễn biến và hàm lôgic Bảng thật: Đại số bool * Hàm n biến sẽ có: n+1 cột (n biến và giá trị hàm) 2n hàng: 2n tổ hợp biến Ví dụ Bảng thật hàm Hoặc 2 biến 2. Đại số Boole  Biểu diễn biến và hàm lôgic Bìa Cac-nô: Đại số bool * Số ô trên bìa Cac-nô bằng số dòng bảng thật Ví dụ Bìa Cac-nô hàm Hoặc 2 biến A B 0 1 0 1 2. Đại số Boole  Biểu diễn biến và hàm lôgic Biểu đồ thời gian: Đại số bool * Là đồ thị biến thiên theo thời gian của hàm và biến lôgic Ví dụ Biểu đồ thời gian của hàm Hoặc 2 biến t t t A 1 0 F(A,B) 0 B 1 0 1 2. Đại số Boole  Các hàm lôgic cơ bản Hàm Phủ định: Đại số bool * Ví dụ Hàm 1 biến 2. Đại số Boole  Các hàm lôgic cơ bản Hàm Và: Đại số bool * Ví dụ Hàm 2 biến 2. Đại số Boole  Các hàm lôgic cơ bản Hàm Hoặc: Đại số bool * Ví dụ Hàm 3 biến 2. Đạ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ố: Phép bù: Đại số bool * 2. Đại số Boole  Định lý De Morgan Đại số bool * Trường hợp 2 biến Tổng quát  Tính chất đối ngẫu Nội dung 1. Giới thiệu 2. Đại số Boole 3. Biểu diễn các hàm logic dưới dạng chính quy 4. Tối thiểu hóa các hàm logic 5. Các phần tử logic cơ bản 6. Bài tập Đại số bool * 3. 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) Dạng hội (tích các tổng) Dạng chính qui Tuyển chính qui Hội chính qui Tối thiểu hoá hàm logic * Không phải dạng chính qui tức là dạng đơn giản hóa 3. Biểu diễn các hàm lôgic  Dạng tuyển chính qui Tối thiểu hoá hàm logic * 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 3. Biểu diễn các hàm lôgic  Dạng tuyển chính qui Tối thiểu hoá hàm logic * Ví dụ Cho hàm 3 biến F(A,B,C). Hãy viết biểu thức hàm dưới dạng tuyển chính qui. Tối thiểu hoá hàm logic * 3. 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: 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 Nhận xét Ví dụ Tối thiểu hoá hàm logic * 3. 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 3. Biểu diễn các hàm lôgic  Dạng hội chính qui Tối thiểu hoá hàm logic * Ví dụ Cho hàm 3 biến F(A,B,C). Hãy viết biểu thức hàm dưới dạng hội chính qui. Tối thiểu hoá hàm logic * 3. 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 hội chính qui Tối thiểu hoá hàm logic * 3. Biểu diễn các hàm lôgic  Biểu diễn dưới dạng số ABCD = Ax23 +B x22 + C x21 + D x20 = Ax8 +B x4 + C x2 + D x1 LSB (Least Significant Bit) MSB (Most Significant Bit) Nội dung 1. Giới thiệu 2. Đại số Boole 3. Biểu diễn các hàm logic dưới dạng chính quy 4. Tối thiểu hóa các hàm logic 5. Các phần tử logic cơ bản 6. Bài tập Tối thiểu hoá hàm logic * Tối thiểu hoá hàm logic * 4. Tối thiểu hóa các hàm lôgic Mục tiêu: Số số hạng ít nhất và số biến ít nhất trong mỗi số hạng Mục đích: Giảm thiểu số lượng linh kiện Phương pháp: - Đại số - Bìa Cac-nô -... Phương pháp đại số Tối thiểu hoá hàm logic * 4. Tối thiểu hóa các hàm lôgic 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. Có thể thêm số hạng đã có vào một biểu thức lôgic. Tối thiểu hoá hàm logic * 4. Tối thiểu hóa các hàm lôgic 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 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. 4. Tối tiểu hóa các hàm logic Bảng mã cho 2 biến bool (x, y) Tối thiểu hoá hàm logic * Phương pháp bìa Karnaugh Bảng mã cho hàm 3 biến bool (x, y, z) Bảng mã cho hàm bool 4 biến (x, y, z, t) Hoặc Tối thiểu hoá hàm logic * 4. Tối tiểu hóa các hàm logic 4. Tối tiểu hóa các hàm logic Các tế bào 1 ô và 2 ô T1(1ô) = xy ¬z t T2(1ô) = ¬xy ¬z ¬t T3(2ô) = (xV ¬x)y.z.t T4(2ô) = (xV ¬x). ¬y.z. ¬t = ¬yz ¬t T5(2ô) = ¬x. ¬y; T6(2ô) = x.y. ¬t Tối thiểu hoá hàm logic * Tế bào và tế bào lớn f ∈ Fn (n ≤ 4) và S = kar(f) Một tế bào trong S là một hình chữ nhật (mở rộng) có 2r ô (r = 0, 1, 2, 3, 4 ; 2r = 1, 2, 4, 8, 16). Một tế bào lớn trong S là tế bào tối đại trong S (không có tế bào của S chứa nó và to hơn nó). Ví dụ tế bào 4. Tối tiểu hoác các hàm logic Tối thiểu hoá hàm logic * Ví dụ tế bào lớn T1 = xy T2 = y ¬ z ¬ t T3 = yzt T4 = ¬ yz ¬ t T5 = ¬ x ¬ yt THUẬT TOÁN TÌM ĐA THỨC TỐI TIỂU Bước 1: vẽ biểu đồ karnaugh của f Bước 2: Xác định tất cả các tế bào của karf(f) Bước 3: Xác định các tế bào m nhất thiết phải chọn Phải chọn tế bào lớn T khi tồn tại một ô của karf(f) mà ô này chỉ nằm trong tế bào lớn T và không nằm trong bất kỳ tế bào lớn nào khác Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn Nếu các tế bào lớn chọn được ở bước 3 đã phủ được karf(f) thì ta có duy nhất một phủ tối tiểu gồm các tế bào lớn của karf(f) Nếu các tế bào lớn chọn được ở bước 3 chưa phủ được karf(f) thì : Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này, ta sẽ chọn một trong các tế bào lớn này. Cứ tiếp tục như thế ta sẽ tìm được tất cả các phủ gồm các tế bào lớn của karf(f) Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn(tt) - Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồm các tế bào lớn của karf(f) Bước 5: Xác định các công thức đa thức tối tiểu của f Từ các phủ tối tiểu gồm các tế bào lớn của karf(f) tìm được ở bước 4 ta xác định được các công thức đa thức tương ứng của f Loại bỏ các công thức đa thức mà có một công thức nào đó thực sự đơn giản hơn chúng Các công thức đa thức còn lại chính là các công thức đa thức tối tiểu của f VÍ DỤ 1: Bước 1: vẽ biểu đồ karnaugh của f Bước 2: Xác định tất cả các tế bào của karf(f) Bước 2: Xác định tất cả các tế bào của karf(f) Bước 2: Xác định tất cả các tế bào của karf(f) Bước 2: Xác định tất cả các tế bào của karf(f) Bước 2: Xác định tất cả các tế bào của karf(f) Bước 2: Xác định tất cả các tế bào của karf(f) Bước 2: Xác định tất cả các tế bào của karf(f) Bước 3: Xác định các tế bào lớn nhất thiết phải chọn Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn Bước 5: Xác định các công thức đa thức tối tiểu của f Ứng với phủ tối tiểu gồm các tế bào lớn tìm được ở bước 4 ta tìm được duy nhất một công thức đa thức tối tiểu của f: X V YZ Nội dung 1. Giới thiệu 2. Đại số Boole 3. Biểu diễn các hàm logic dưới dạng chính quy 4. Tối thiểu hóa các hàm logic 5. Các phần tử logic cơ bản 6. Bài tập Đại số bool * 5. Các phần tử lôgic cơ bản Có 3 phép toán logic cơ bản: VÀ (AND) HOẶC (OR) ĐẢO (NOT) Phần tử logic cơ bản (mạch logic cơ bản, cổng logic) thực hiện phép toán logic cơ bản: AND gate OR gate NOT inverter Các mạch số đặc biệt khác: các cổng NAND, NOR, XOR, XNOR Các phần tử logic cơ bản * A. AND gate Chức năng: Đầu ra chỉ bằng 1 khi tất cả các đầu vào bằng 1 Cổng AND 2 đầu vào: Ký hiệu: Bảng sự thật: Biểu thức: out = A . B Các phần tử logic cơ bản * B. OR gate Chức năng: Đầu ra chỉ bằng 0 khi tất cả các đầu vào bằng 0 Cổng OR 2 đầu vào: Ký hiệu: Bảng sự thật: Biểu thức: out = A + B Các phần tử logic cơ bản * C. NOT inverter Chức năng: Thực hiện phép toán logic ĐẢO (NOT) Cổng ĐẢO chỉ có 1 đầu vào: Ký hiệu: Bảng sự thật: Biểu thức: out = A’ Các phần tử logic cơ bản * D. Cổng VÀ ĐẢO (NAND gate) Chức năng: Đầu ra chỉ bằng 0 khi tất cả các đầu vào bằng 1 Cổng AND ĐẢO 2 đầu vào: Ký hiệu: Bảng sự thật: Biểu thức: out = (A . B)’ Các phần tử logic cơ bản * E. Cổng HOẶC ĐẢO (NOR gate) Chức năng: Đầu ra chỉ bằng 1 khi tất cả các đầu vào bằng 0 Cổng HOẶC ĐẢO 2 đầu vào: Ký hiệu: Bảng sự thật: Biểu thức: out = (A + B)’ Các phần tử logic cơ bản * F. Cổng XOR (XOR gate) Chức năng: Exclusive-OR Đầu ra chỉ bằng 0 khi tất cả các đầu vào giống nhau Cổng XOR 2 đầu vào: Ký hiệu: Bảng sự thật: Biểu thức: Các phần tử logic cơ bản * G. Cổng XNOR (XNOR gate) Chức năng: Exclusive-NOR Đầu ra chỉ bằng 1 khi tất cả các đầu vào giống nhau Cổng XNOR 2 đầu vào: Ký hiệu: Bảng sự thật: Biểu thức: Các phần tử logic cơ bản * Các phần tử logic cơ bản * h. Ví dụ (x + y’)z + x’ Nội dung 1. Giới thiệu 2. Đại số Boole 3. Biểu diễn các hàm logic dưới dạng chính quy 4. Tối thiểu hóa các hàm logic 5. Các phần tử logic cơ bản 6. Bài tập Đại số bool * Bài tập * 5. Bài tập Chứng minh các biểu thức sau: a) b) c) 2. Tối thiểu hóa các hàm sau bằng phương pháp đại số: a) b) Bài tập * 5. Bài tập 3. 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) Bài tập * Giải bài tập 1. a) Bài tập * Giải bài tập 1. b) Bài tập * Giải bài tập 1. c) Bài tập * 2. a) Giải bài tập Bài tập * 2. b) Giải bài tập Bài tập * a) F(A,B,C,D) = R(0,2,5,6,9,11,13,14) 1 1 1 1 1 1 1 3. Giải bài tập Bài tập * c) F(A,B,C,D) = R(2,4,5,6,7,9,12,13) 1 1 1 1 1 3. Giải bài tập Bài tập * 0 0 0 3. d) Bài tập * 1 1 1 Giải bài tập chương 1 Bài tập * Bìa Các-nô 5 biến Bài tập * 3 e F(A,B,C,D,E)=R(0,1,9,11,13,15,16,17,20,21,25,26,27,30,31) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 *